Export page to Open Document format View page as slide show

Tietoturva

Epäsymmetrinenkryptografia

  • Julkisenavaimen järjestelmät: 1976 Diffie-Hellman
    • Kahdenavaimen menetelmä symmetrisen avaimen vaihtoon.
  • Erilaisia salausalgortimeja
    • RSA, ElGamal, Elliptisiin käyriin perustuvat salaimet.
  • Eri avain salauksen ja purkamiseen
    • Viesti salataan vastaanottajan julkisella avaimella. E_{kPublic}(M) =C
    • Vastaanottaja purkaa viestin omalla yksityisellä avaimellaan. D_{kPrivate}(C) = M
    • Algoritmin toiminna johdosta ainoastaan yksityisen avaimen tietäjä voi avata viestin.
  • Julkisella ja yksityisellä avaimella on matemaattinen yhteys
    • Yksityisestä avaimesta voi laskea julkisen avaimen
    • Julkisesta avaimesta ei voi päätellä yksityistä avainta.
  • Julkinen avain voidaan laittaa jakoon vaikka omalle kotisivulle tai julkistaa puhelinluettelossa
    • Salatun viestin lähettäminen ei vaadi salaisuuden jakoa
  • Turvallisuus perustuu vaikeisiin matemaattisiin ongelmiin.
    • esim: Alkulukujen kertolasku on helppo toiseen suuntaan, mutta tulon tekijöihin jako on vaikeaa, kun luvut ovat suuria.
  • Edut
    • Ainoastaan yksityinen avain täytyy pitää salassa
    • Avainten hallinta verkossa vaatii ainoastaan funktionaalisesti luotetun tahon
      • Ei tarvi paljastaa salaisuuttaa ulkopuolisille
    • Avainpareja voidaan käyttää pitkä aika (jopa vuosia)
  • Heikkoudet
    • Tietojen käsittelynopeudet monta kertaluokkaa huonommat kuin symmetrisillä järjestelmillä
      • Käytetään yleensä vain pienen tietomäärän salaukseen kuten symmetrisen avaimen vaihtoon.
    • Tarvittavat avaimet suuria
    • Avainten generointi hidasta
    • Vaikea todistaa turvalliseksi
      • Perustuu oletettavasti vaikeisiin numeroteoreetisiin ongelmiin
      • Menetelmien historia lyhyt, voi löytyä uusia tapoja ratkaista algoritmi.
    • Kuinka todistaa julkinen avain oikeaksi

Triviaali kellosalain

  • Triviaali kello salain
    • Valitaan julkinen modulus n = 12
    • Valitaan salaiseksi avaimeksi kpriv numero väliltä 1-12.
    • Lasketaan julkinen avain kpub = n-kpriv
  • Salaus (salattava arvo oltava alle 12)
    • C= M+kpub
  • Purku
    • M= C+kpriv
  • Kuinka toteutettaisiin salaus jos julkinen avain olisi salaisen avaimen käänteisluku mod n?
  • Salain ei ole missään suhteessa turvallinen, koska julkisen avaimen avulla on helppo laskea salainen avain tai vaikka purkaa viesti.

RSA

  • Kehittäjät Ron Rivest, Adi Shamir, Leonard Adleman
  • Avaimenluonti RSA:ssa
  1. Luodaan kaksi suurta alkulukua p ja q, jotka ovat suurinpiirtein samaa kokoluokkaa (yhtämonta numeroa / digittiä).
  2. Laske n=pqand \phi=(p-1)(q-1)
  3. Valitse satunnainen avain e, 1<e<\phiniin että gcd(e,\phi)=1. (Eli e ja \phi ovat toisilleen suhteellisia alkulukuja)
  4. laske avain d, 1<d<\phi, niin että ed\equiv_{\phi}1 eli d=e^{-1}mod(\phi) (Esimerkiksi ratkaisemalla laajennetulla eclideaan algoritmilla kaavan ed-\phi k=1)
  5. Julkinen avain on (n,e), salainen avain on d.
    • p , q ja \phi tulee pitää salassa (tai tuhota).

Viestien salaus ja purku RSA:lla

  • Mikäli viesti M on suurempi kuin julkinen modulo n
    • Jaa viesti M lohkoihin jotka ovat pienempiä kuin n (eli jos n on 512 bittiä, nin lohkon pitää olla tätä pienempi).
  • Salaa lohkot kaavalla
    c_{i}=M_{i}^{e}mod\: n , jossa i on lohkon järjestysnumero
  • Purku toteutetaan kaavalla M_{i}=c_{i}^{d}mod\: n
  • Todistus: c_{i}^{d}=(M_{i}^{e})^{d}=M_{i}^{ed}=M_{i}^{k*\phi+1}=M_{i}M_{i}^{k\phi}=M_{i}*1\,(\,mod\, n\,)
    • Avaimen generoinnista: ed-\phi k=1\rightarrow ed=1+\phi k
    • Muistetaan Eulerin teoreema a^{\phi(p)}\equiv_{p}1 if gcd (a,p) = 1
  • RSA operaatiot voidaan tehdä kummassa ärjestyksessä tahansa
    • Salaus voidaan tehdä joko julkisella tai salaisella avaimella. Purku toteutetaan sillä avaimella jota ei käytetty.

RSA esimerkki

  • Olkoon p=47\; q=71\Rightarrow n=p*q=3337
  • e:llä ei voi olla yhteistä tekijää (p-1)(q-1)=46*70=3220 kanssa .
  • valitaan e=79 ; gcd(79,3220)=1
  • laske d=79^{-1}mod\:3220=1019
  • Olkoon viesti 1010110000 joka on kokonaisluku 688, joka on pienempi kuin 3337
  • Salaus: 688^{79}mod\:3337=1570 , joka on binäärinä (11000100010) on salattu viesti
  • Salauksen purku: 1570^{1019}mod\:3337=688

Speeding up RSA

  • Choosing e cleverly can speed up the RSA calculations, Common choices are 3, 17 ja 65537
    • 65537=2^{16}+1,has only two 1 bits in binary form (first and last bit), which speeds up calculations.
    • Note! : There are risks on using small e (see RSA security)
  • If p and q has been stored it is possible to speed up operations done with private key by using chinese remainder theorem

RSA Turvallisuus

  • Turvallisuus perustuu suuren luvun tekijöihin jaon oletettuun vaikeuteen.
    • yritetään jakaa n tekijöihin jotta saadaan ratkaistua p ja q joiden avulla voidaan laskea d.
      • Vuonna 1994 luku jossa oli 129 digittiä (~428 bittiä) jaettiin tekijöihin Quadratic sieve algoritmilla. Vuonna 2005, 200 (663 bittiä) digitin numero jaettiin tekijöihin lattice sieve algoritmilla
    • Ei ole matemaattista todistusta siitä että n pitää jakaa tekijöihin, salaisen avaimen tai selkotekstin paljastamiseen (kukaan vain ei ole vielä keksinyt muuta menetelmää)
  • Hyökkäys \phi vastaan ei ole yhtään helpompi kuin n:n tekijöihin jako. ( \phi on n:n kanssa samaa suuruusluokkaa)
    • kokeilemalla d:n löytäminen on vkompleksisuudeltaan samaa luokkaa kuin tekijöihin jaot
  • Raa-an voiman hyökkäys
    • Kokeile kaikkia mahdollisia salaisia avaimia d, viestin löytämiseksi
    • Yhtä hidasta kuin n:n tekijöihin jako (mikäli d on tarpeeksi suuri)
  • Ajastus hyökkäys (esimerkiksi salaavilla toimikorteilla)
    • Mitataa aikaa joka menee viestin purkamiseen jotta salainen avain saadaan selville. (salauksen purkuun kuluva aika riippuu avaimesta)
    • Vastakeinona voidaan salauksen purkuun lisätä satunnaisen datan salausta. (Blinding)

Elliptiset käyrät

  • Elliptic curves
  • Elliptinen käyrä on y^{2}=x^{3}+ax+b, jossa x, y, a ja b ovat reaalinumeroita.
  • jos x^{3}+ax+b ei ole toistuvia tekijöitä (tai jos 4a^{3}+27b^{2}\neq0) voidaan käyrää käyyttä elliptisten käyren kryptografiassa (ECC)

Elliptisten käyrien matematiikka

  • Pisteiden yhteenlasku käyrällä
    • Piirretään suora yhteenlaskettavien pisteiden väliin ja etsitään kolmas piste jossa suora leikkaa käyrän. Otetaan tästä pisteestä reflekti x akselilla( x=-x ) , jotta saadaan lopullinen piste.
    • Jos suora ei leikkaa käyrää kolmatta kertaa, kutsutaan pistettä ääretömyyden pisteeksi ( 9point of infinity)
    • Lasketaan P + Q = R, jossa P = (xP,yP) ja Q = (xQ,yQ) ja P,Q eivät ole toistensa vastapisteitä e.g. R\neq0
      • s=\frac{P_{y}-Q_{y}}{P_{x}-Q_{x}} e.g. (kulmakerroin suoralle joka kulkee P:n ja Q:n kautta)
      • R_{x}= s^{2}-P_{x}-Q_{x} ja R_{y}=-P_{y}+s(P_{x}-R_{x})
  • Pisteen laskeminen yhteen itsensä kanssa (e.g. P+P=2P)
    • Piirretään tangentti käyrälle pisteessä P ja lasketaan missä tangentti leikkaa käyrän. Otetaan reflektio jälleen x-akselin suhteen jottaa saadaan tulos eli piste 2P
      • Suurempien kertoimien laskeminen: 3P=2P+P, 4P=2(2P) jne.
    • Laske R kun 2P = R R\neq0
      • s=\frac{3P_{x}^{2}+a}{2P_{Y}}
      • R_{x}=s^{2}-2P_{x} ja R_{y}=s(P_{x}-R_{x})-P_{y}

Elliptic curve mod p

  • Rajataan mahdolliset koordinaatit p:tä pienemmäksi. Eli rajataan käytössä oleva alue käyrällä.
  • Otetaan esimerkiksi käyrä: y^{2}\equiv_{}x^{3}+4x+4
    • jos p = 5, (eli käytetään mod 5) niin x:n arvot voivat olla 0,1,2,3,4 sekä point of infinity eli ääretön

x\equiv_{5}0\Rightarrow y^{2}\equiv_{5}0+4*0+4=4\Rightarrow y\equiv2,-2\rightarrow y\equiv_{5}2,3 (5-2=3)( 2^{2}=4\, and\,3^{2}=9\Rightarrow9\, mod\,5=4)
x\equiv_{5}1\Rightarrow y^{2}\equiv_{5}4\Rightarrow y\equiv_{5}2,3 x\equiv_{5}2\Rightarrow y^{2}\equiv_{5}0\Rightarrow y\equiv_{5}0
x\equiv_{5}3\Rightarrow y^{2}\equiv_{5}3 No solution x\equiv_{5}4\Rightarrow y^{2}\equiv_{5}4\Rightarrow y\equiv_{5}2,3
x=\infty\Rightarrow y=\infty

  • Joten maholliset pisteet käyrällä mod 5 ovat (0,2),(0,3),(1,2),(1,3),(2,0),(4,2),(4,3) ja (\infty,\infty)
  • Pisteiden yhteenlaskenta toimii kuten normaalistikin elliptisillä käyrillä. Muista että: \frac{a}{b}=a*b^{-1}
    • Lisätään (1,2) ja (4,3) yhteen yllämainitulla käyrällä
      kulmakerroin m\equiv_{5}\frac{3-2}{4-1}\equiv\frac{1}{3}\equiv2, (3*2\equiv_{5}1)
      x_{3}\equiv_{5}m^{2}-x_{1}-x_{2}\equiv_{5}2^{2}-1-4\equiv_{5}4
      y_{3}\equiv_{5}m(x_{1}-x_{3})-y_{1}\equiv_{5}2(1-4)-2\equiv_{5}2
    • Joten: (1,2) + (4,3) = (4,2)

Elliptic curve discrete logarithm problem(ECDLP)

  • Elliptisten käyrien diskreetin logaritmin ongelma
  • Otettaessa kaksi pistettä G ja Y elliptisellä käyrällä siten että Y=kG (eli Y on G yhdistettynä itseensä k kertaa), ratkaise kokonaisluku k.
  • Diskreeteissä logaritmeissa on kokeiltava kakki mahdolliset potenssit, elliptisissä käyrissä kaikki mahdolliset k:t
  • Kun k tiedetään voidaan laskemista nopeuttaa eikä kaikkia arvoja tarvitse laskea.

Elliptisten käyrien kryptografia (Elliptic curve cryptography, ECC)

  • Määritetään käyrä y^{2}\equiv_{5}x^{3}+ax+b\,\, mod\, p e.g. E_{p}(a,b)
  • Avainten generointi:
    • Valitään peruspiste B käyrältä.
    • Otetaan satunnainen kokonaisluku k, joka on salainen avain.
    • Lasketaan piste K skalaaritulona K=k*B
    • Julkinen avain on [K,B,a,b,p] salainen avain on [k,B,a,b,p] ( k on ainoa salaisuus)
  • Salaus
    • Määritellään viesti käyrän pisteenä M
    • Valitaan satunnainen luku r ja lasketaan C_{0}=r*B ja C_{1}=M+r*K
    • Viesti salattuna on pistepari [C_{0}\,\, C_{1} ]
  • Salauksen purku
    • Laske: C_{1}-k*C_{2}=M
    • Todiste:
      • C_{1}=M+rK , C_{0}=r*B ja K=k*B
      • joten: M+rK-k(r*B)\rightarrow M+r(k*B)-k(r*B)=M

Tiedon muokkaus käyrän pisteeksi.

  • Yksinkertainen menetelmä (Koblitz)
    • Otetaan viesti m (kokonaislukuna) käyrän x koordinaattina.
    • viesti jäettavavä k:ta pienempiin lohkoihin.
  • Joskus ei löydy x:n arvolle sopivaa y:tä käyrältä
    • lisätään täyte bittejä m:n perään ja muutetaan niitä kunnes löytyy oikea piste.
    • kaikissa viesteissä tulee olla samamäärä täyte bittejä.

Elliptic curve uses

  • ECIES (Elliptic Curve Integrated Encryption Scheme)
    • The actual message is encrypted with symmetric algorithm, but with use of elliptic curves the symmetric key can be transmitted to the receiver along with the encrypted message
  • PSEC (Provable Secure Encryption Curve scheme)
    • Like ECIES
  • ECDSA (Elliptic curve digital signature algorithm)
    • Signatures with Elliptic curves can be done in similar fashion than DSA (which is related to ElGamal)
    • Will be talked more on signature lectures

Elliptiset käyrät käytännössä

  • Elliptiset käyrät voivat käyttää pienempiä avaimia kuin RSA ja muut asymmetriset salausmenetelmät (224 bittinen ECC avain vastaa 2048 bitttistä RSA avainta turvallisuuden kannalta)
    • ECC on kokonaisuudessa nopeampi kuin RSA
    • ECC on nopeampi salauksen purussa ja allekirjoituksessa ja hitaampi salauksessa ja allekirjoituksen varmistuksessa kuin RSA.
  • Käytettävät käyrät määritellään standardeissa.
  • Monet osat elliptisissä käyrissä on patentoitu joka omalta osaltaan on hidastanut niiden käyttöön ottoa.
Last modified: 2013/07/01 14:42