RSA-algoritmi – mitä se on ja miten se toimii

Käytetyt käsitteet

RSA käyttää useita kryptografian käsitteitä:

• Yksisuuntainen funktio, joka on helppo laskea; sen kumoavan funktion löytäminen tai laskeminen on hyvin vaikeaa.
• RSA käyttää käsitettä nimeltä diskreetti logaritmi. Se toimii aivan kuten normaali logaritmi: Erona on se, että käytetään vain kokonaislukuja, ja yleensä kyseessä on moduulioperaatio. Esimerkkinä a^x =b, modulo n. Diskreetissä logaritmissa on kyse pienimmän x:n löytämisestä, joka täyttää yhtälön, kun a b ja n annetaan
• Shorin algoritmi voi mahdollisesti torjua sen.

Avainten luominen

RSA-algoritmin avaimet luodaan seuraavasti:

1. Valitse kaksi erilaista suurta satunnaista alkulukua p {\displaystyle p} ja q {\displaystyle q} . Tämä on pidettävä salassa.
2. Laske n = p q {\displaystyle n=pq} .
• n {\displaystyle n} on julkisen ja yksityisen avaimen moduuli.
3. Lasketaan totientti: ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
4. Valitaan sellainen kokonaisluku e {\displaystyle e} , että 1 < e < ϕ ( n ) {\displaystyle 1<e<\phi (n)} , ja e {\displaystyle e} on co-primus ϕ ( n ) {\displaystyle \phi (n)} kanssa.
   Toisin sanoen: e {\displaystyle e} ja ϕ ( n ) {\displaystyle \phi (n)} eivät jaa muita tekijöitä kuin 1 {\displaystyle 1}. : gcd ( e , ϕ ( n ) ) = 1 {\displaystyle \gcd(e,\phi (n))=1} ; Katso suurin yhteinen jakaja.
• e {\displaystyle e} vapautetaan julkisen avaimen eksponentiksi.
5. Lasketaan d {\displaystyle d} täyttämään kongruenssisuhde d e ≡ 1 ( mod ϕ ( n ) ). {\displaystyle de\equiv 1\!\!\!\!\!\!{\pmod {\phi (n)}}} .
   Eli: d e = 1 + x ⋅ ϕ ( n ) {\displaystyle de=1+x\cdot \phi (n)} jollekin kokonaisluvulle x {\displaystyle x} . (Yksinkertaisesti sanottuna: Lasketaan d = ( 1 + x ⋅ ϕ ( n ) ) / e {\displaystyle d=(1+x\cdot \phi (n))/e} kokonaisluvuksi).
• d {\displaystyle d} pidetään yksityisen avaimen eksponenttina.

Huomautuksia edellä mainituista vaiheista:

• Vaihe 1: Luvuille voidaan tehdä todennäköisyystestit alkulukujen ensisijaisuuden varalta.
• Vaihe 3: muutettu PKCS#1 v2.0:ssa muotoon λ ( n ) = l c m ( p - 1 , q - 1 ) {\displaystyle \lambda (n)={\rm {lcm}}(p-1,q-1)} ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} sijaan.
• Vaihe 4: Suosittu valinta julkisten eksponenttien arvoksi on e = 2 16 + 1 = 65537 {\displaystyle e=2^{16}+1=65537} . Joissakin sovelluksissa valitaan pienempiä arvoja, kuten e = 3 {\displaystyle e=3} , 5 {\displaystyle 5} tai 35 {\displaystyle 35} sijaan. Tämä tehdään, jotta salaus ja allekirjoituksen todentaminen olisi nopeampaa pienissä laitteissa, kuten älykorteissa, mutta pienet julkiset eksponentit voivat johtaa suurempiin tietoturvariskeihin.
• Vaiheet 4 ja 5 voidaan suorittaa laajennetulla euklidisella algoritmilla [fi]; katso modulaarinen aritmetiikka.

 Julkinen avain muodostuu moduulista n {\displaystyle n\,} ja julkisesta (tai salaus)eksponentista e {\displaystyle e\,} . Henkilökohtainen avain muodostuu p,q:sta ja yksityisestä (tai salauksen purku-) eksponentista d {\displaystyle d\,} , joka on pidettävä salassa.

• Tehokkuuden vuoksi yksityinen avain voidaan tallentaa eri muodossa:
• p {\displaystyle p} ja q {\displaystyle q} : avainten luomisessa käytetyt alkuluvut;
• d mod ( p - 1 ) {\displaystyle d{\bmod {(}p-1)} ja d mod ( q - 1 ) {\displaystyle d{\bmod {(}q-1)} : kutsutaan usein dmp1 ja dmq1;
• q - 1 mod p {\displaystyle q^{-1}{\bmod {p}}}} : kutsutaan usein iqmp:ksi.
• Kaikki yksityisen avaimen osat on pidettävä salassa tässä muodossa. p {\displaystyle p\,} ja q {\displaystyle q\,} ovat arkaluonteisia, koska ne ovat n {\displaystyle n\,} kertoimia ja mahdollistavat d {\displaystyle d\,} laskennan, kun e {\displaystyle e\,} on annettu. Jos p {\displaystyle p\,} ja q {\displaystyle q\,} eivät ole tallennettu tähän yksityisen avaimen muotoon, ne poistetaan turvallisesti yhdessä muiden avaimen luomisesta peräisin olevien väliarvojen kanssa.
• Vaikka tämä muoto mahdollistaa nopeamman salauksen purkamisen ja allekirjoittamisen CRT-lausekkeen (Chinese Remainder Theorem) avulla, se on huomattavasti vähemmän turvallinen, koska se mahdollistaa sivukanavahyökkäykset [fi]. Tämä on erityinen ongelma, jos se toteutetaan älykorteissa, jotka hyötyvät eniten tehokkuuden parantumisesta. 
  (Aloita y ≡ x e ( mod n ) {\displaystyle y\equiv x^{e}\!\!\!\!\!\!\!\!{\pmod {n}}}) ja anna kortin purkaa se. Se laskee siis ( y d mod p ) {\displaystyle (y^{d}{\bmod {p}})} tai ( y d mod q ) {\displaystyle (y^{d}{\bmod {q}})} , joiden tulokset antavat jonkin arvon z {\displaystyle z} . Aiheutetaan nyt virhe jossakin laskutoimituksessa. Silloin gcd ( z - x , n ) {\displaystyle \gcd(z-x,n)} paljastaa p {\displaystyle p} tai q {\displaystyle q} .) .)

Viestin salaus

Alice antaa julkisen avaimensa ( n , e ) {\displaystyle (n,e)} Bobille ja pitää yksityisen avaimensa salassa. Bob haluaa lähettää viestin M {\displaystyle M} Alicelle.

Ensin hän muuttaa M {\displaystyle M} luvuksi m {\displaystyle m} , joka on pienempi kuin n {\displaystyle n} , käyttämällä sovittua palautuvaa protokollaa, jota kutsutaan pehmustusjärjestelmäksi. Tämän jälkeen hän laskee salatekstin c {\displaystyle c\,} , joka vastaa:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

Tämä voidaan tehdä nopeasti käyttämällä menetelmää, jossa potenssi saadaan neliöimällä. Tämän jälkeen Bob lähettää Alicelle c .

Viestin purkaminen

Liisa voi palauttaa m {\displaystyle m\,} c {\displaystyle c\,} käyttämällä yksityistä avainta d {\displaystyle d\,} seuraavalla tavalla:

Kun on annettu m {\displaystyle m\,} , hän voi palauttaa alkuperäiset erilliset alkuluvut, ja soveltamalla kiinalaista jäännöslausetta näihin kahteen kongruenssiin saadaan seuraavat tulokset.

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Niinpä,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Siksi:

m = c d m o d n {\displaystyle m=c^{d}\ mod\ n}

Toimiva esimerkki

Tässä on esimerkki RSA-salauksesta ja -purusta. Tässä käytetyt alkuluvut ovat liian pieniä, jotta voimme salata mitään turvallisesti. Voit käyttää OpenSSL:ää oikean avainparin luomiseen ja tutkimiseen.

1. Valitse kaksi satunnaista alkulukua p {\displaystyle p} ja q {\displaystyle q\,} :

p = 61 {\displaystyle p=61} ja q = 53 {\displaystyle q=53\,} ;

2. Lasketaan n = p q {\displaystyle n=pq\,} :

n = 61 × 53 = 3233 {\displaystyle n=61\times 53=3233\!} ;

3. Lasketaan totientti ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} :

ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120\!} ;

4. Valitse e > 1 {\displaystyle e>1} coprime kuin 3120 {\displaystyle 3120\,} :

e = 17 {\displaystyle e=17\,} ;

5. Valitse d {\displaystyle d\,} siten, että e d ≡ 1 mod ϕ ( n ) {\displaystyle ed\equiv 1{\bmod {\phi (n)}}} :

d = 2753 {\displaystyle d=2753\,} , jolloin 17 × 2753 = 46801 = 1 + 15 × 3120 {\displaystyle 17\times 2753=46801=1+15\times 3120} .

 Julkinen avain on ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Täytetylle viestille m {\displaystyle m\,} salausfunktio c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} muuttuu:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,}

Yksityinen avain on ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Salausfunktio m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} muuttuu:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,}

 Esimerkiksi m = 123
salataksesi {\displaystyle m=123} lasketaan

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}}

Salaus c = 855 {\displaystyle c=855} lasketaan

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}} 233=123}

Molemmat näistä laskutoimituksista voidaan laskea nopeasti ja helposti käyttämällä modulaarisen potensoinnin neliö- ja moninkertaistamisalgoritmia.

RSA-yhtälön johtaminen Eulerin lauseesta

RSA voidaan helposti johtaa Eulerin lauseen ja Eulerin totienttifunktion avulla.

Aloitetaan Eulerin lauseesta,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

meidän on osoitettava, että salauksen purkaminen oikealla avaimella antaa alkuperäisen viestin. Kun otetaan huomioon pehmustettu viesti m, salausteksti c lasketaan seuraavasti

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}

Kun tämä korvataan salauksen purkualgoritmilla, saadaan seuraava tulos

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}}

Haluamme osoittaa, että tämä arvo on myös yhteneväinen m:n kanssa. e:n ja d:n arvot valittiin siten, että ne täyttävät,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

Toisin sanoen, on olemassa jokin kokonaisluku k, jonka avulla

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Nyt korvaamme salatun ja sitten puretun viestin,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}}

Sovellamme Eulerin teoreemaa ja saamme tuloksen.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

Pehmustejärjestelmät

Käytännössä RSA:ta käytettäessä siihen on yhdistettävä jonkinlainen pehmustejärjestelmä, jotta mikään M:n arvo ei johda turvattomaan salaustekstiin. Ilman pehmustusta käytetyllä RSA:lla voi olla joitakin ongelmia:

• Arvot m = 0 tai m = 1 tuottavat aina salaustekstejä, jotka ovat vastaavasti 0 tai 1, eksponentiaalisuuden ominaisuuksien vuoksi.
• Kun salaus tehdään pienillä salauseksponenteilla (esim. e = 3) ja pienillä m:n arvoilla, (ei-modulaarinen) tulos m e {\displaystyle m^{e}} voi olla tiukasti pienempi kuin moduuli n. Tällöin salaustekstit voidaan helposti purkaa ottamalla salaustekstin eet-juuresta moduulista välittämättä.
• RSA-salaus on deterministinen salausalgoritmi. Siinä ei ole satunnaiskomponenttia. Sen vuoksi hyökkääjä voi onnistuneesti käynnistää salausjärjestelmää vastaan valitun selkotekstin hyökkäyksen. Hän voi luoda sanakirjan salaamalla todennäköisiä salatekstejä julkisella avaimella ja tallentamalla tuloksena saadut salatekstit. Hyökkääjä voi sitten tarkkailla viestintäkanavaa. Heti kun hän näkee salakirjoitustekstejä, jotka vastaavat hänen sanakirjassaan olevia salakirjoitustekstejä, hyökkääjät voivat käyttää tätä sanakirjaa saadakseen selville viestin sisällön.

Käytännössä kaksi ensimmäistä ongelmaa voi syntyä, kun lähetetään lyhyitä ASCII-viestejä. Tällaisissa viesteissä m voi olla yhden tai useamman ASCII-koodatun merkin ketjutus. Viesti, joka koostuu yhdestä ASCII-merkistä NUL (jonka numeerinen arvo on 0), koodataan muotoon m = 0, jolloin salatun tekstin arvo on 0 riippumatta siitä, mitä e:n ja N:n arvoja käytetään. Vastaavasti yksittäinen ASCII SOH (jonka numeerinen arvo on 1) tuottaisi aina salaustekstin, jonka arvo on 1. Järjestelmissä, joissa käytetään tavanomaisesti pieniä e:n arvoja, kuten 3, kaikki yksittäiset ASCII-merkkiset viestit, jotka on koodattu tätä järjestelmää käyttäen, eivät olisi turvallisia, koska suurimman m:n arvo olisi 255, ja 255³ on pienempi kuin mikä tahansa järkevä moduuli. Tällaiset salatekstit voitaisiin palauttaa yksinkertaisesti ottamalla salatekstin kuutiojuuri.

Näiden ongelmien välttämiseksi käytännön RSA-toteutukset tyypillisesti upottavat jonkinlaisen strukturoidun, satunnaistetun täytteen arvoon m ennen sen salaamista. Tämä pehmuste varmistaa, että m ei kuulu turvattomien salatekstien joukkoon ja että tietty viesti, kun se on täytetty, salataan joksikin monista erilaisista mahdollisista salateksteistä. Jälkimmäinen ominaisuus voi nostaa sanakirjahyökkäyksen kustannukset yli kohtuullisen hyökkääjän kykyjen.

PKCS:n kaltaiset standardit on suunniteltu huolellisesti täyttämään viestit turvallisesti ennen RSA-salausta. Koska näissä järjestelmissä selkotekstiä m täydennetään jollakin määrällä ylimääräisiä bittejä, täydennyksettömän viestin M koon on oltava jonkin verran pienempi. RSA-pehmustejärjestelmät on suunniteltava huolellisesti, jotta voidaan estää monimutkaiset hyökkäykset. Tätä voidaan helpottaa ennustettavalla viestin rakenteella. PKCS-standardin varhaisissa versioissa käytettiin ad hoc -rakenteita, jotka myöhemmin havaittiin haavoittuviksi käytännölliselle mukautuvalle valittuun salaustekstiin kohdistuvalle hyökkäykselle. Nykyaikaisissa rakenteissa käytetään turvallisia tekniikoita, kuten optimaalista epäsymmetristä salauspehmustetta (OAEP), viestien suojaamiseksi ja näiden hyökkäysten estämiseksi. PKCS-standardissa on myös käsittelyjärjestelmiä, jotka on suunniteltu tarjoamaan lisäturvaa RSA-allekirjoituksille, esimerkiksi Probabilistic Signature Scheme for RSA (RSA-PSS).

Viestien allekirjoittaminen

Oletetaan, että Alice käyttää Bobin julkista avainta lähettääkseen hänelle salatun viestin. Viestissä hän voi väittää olevansa Alice, mutta Bobilla ei ole mitään keinoa todentaa, että viesti on todella Alicelta, koska kuka tahansa voi käyttää Bobin julkista avainta salattujen viestien lähettämiseen. Viestin alkuperän todentamiseksi RSA:ta voidaan siis käyttää myös viestin allekirjoittamiseen.

Oletetaan, että Alice haluaa lähettää allekirjoitetun viestin Bobille. Hän tuottaa viestistä hash-arvon, korottaa sen potenssiin d mod n (kuten viestiä purettaessa) ja liittää sen viestin "allekirjoitukseksi". Kun Bob vastaanottaa allekirjoitetun viestin, hän nostaa allekirjoituksen potenssiin e mod n (aivan kuten viestin salauksen yhteydessä) ja vertaa tuloksena saatua hash-arvoa viestin todelliseen hash-arvoon. Jos nämä kaksi vastaavat toisiaan, Bob tietää, että viestin kirjoittajalla oli Alicen salainen avain ja että viestiä ei ole sen jälkeen peukaloitu.

Huomaa, että RSA-PSS:n kaltaiset turvalliset pehmustejärjestelmät ovat yhtä tärkeitä viestin allekirjoittamisen turvallisuuden kannalta kuin viestin salaamisenkin kannalta ja että samaa avainta ei pitäisi koskaan käyttää sekä salaamiseen että allekirjoittamiseen.