RSA¶
Tässä osiossa sovellamme käytännön matematiikkaa kryptografiassa. Asiaa ei ole paljon, mutta se vaatii keskittymistä. RSA:n periaatteet ovat käytössä tänä päivänä kaikkialla ja hyödynnämme niitä ehkä tietämättämme päivittäin käyttäessämme digitaalisia palveluita.
Kenties kaikkien aikojen kuuluisin yksittäinen salausmenetelmä julkaistiin melko pian Diffien ja Hellmanin artikkelin jälkeen. Sitä kutsutaan RSA-menetelmäksi sen keksijöiden Ronald Rivestin, Adi Shamirin ja Leonard Adlemanin sukunimien alkukirjaimien mukaan. Diskreetin logaritmin ongelman sijasta RSA perustuu lukujen tekijöihin jaon vaikeuteen, jota käsitellään tämän moduulin aikaisemmassa osiossa.
Vaikka RSA yleisesti tunnetaankin sen vuonna 1977 julkaisseiden Rivestin, Shamirin ja Adlemanin mukaan, vastaavan menetelmän kehitti Englannin tiedustelupalvelulle työskennellyt Clifford Cocks jo vuonna 1973, mutta hänen kirjoittamansa muistio pidettiin salassa vielä kymmeniä vuosia varsinaisen RSA-artikkelin ilmestymisen jälkeen. On myös merkille pantavaa, että Cocks kuvasi menetelmänsä jo ennen Diffien ja Hellmanin artikkeliakin.
RSA-lukujen laskenta¶
RSA-lukujen laskenta on hieman monimutkaista. Alla oleva video esittää samat asiat kuin sen jälkeen oleva teksti. Videota ja tekstin esimerkkejä kannattaa pyöritellä kynällä ja paperilla muutamaan kertaan. Kun olet sisäistänyt RSA:n laskennan, huomaat ettei se olekaan niin vaikeaa kuin miltä se saattoi aluksi vaikuttaa.
Katso ensin alla oleva video ja sen jälkeen käy kynällä ja paperilla läpi videon jälkeen esitetty esimerkki.
RSA-lukujen laskenta tapahtuu seuraavasti:
RSA-menetelmässä valitaan satunnaisesti kaksi alkulukua \(p\) ja \(q\). Nämä alkuluvut pidetään salaisena.
Lasketaan näiden lukujen tulo \(n = pq\). Tämä on julkisen avaimen ensimmäinen osa.
Samoin kuin diskreetin logaritminkin tapauksessa, tekijöihin jakamisen uskotaan vastaavan 128 bitin turvatasoa, kun \(n\) on 3072 bittiä pitkä.
Kun \(n\) on laskettu, valitaan vielä luku \(e\) ja lasketaan luku \(d\).
Yleensä julkiseksi eksponentiksi \(e\):ksi valitaan suhteellisen pieni luku.
Tämän jälkeen lasketaan salainen avain \(d\).
\(e\):n ja \(d\):n on tuotettava modulorenkaassa (p-1)(q-1) tulos 1. Eli \(e \cdot d \pmod{(p-1)(q-1)} = 1\).
\(d\) on luvun \(e\) käänteisluku moduloon \((p-1)(q-1)\).
Olemme nähneet vastaavan käänteislukujen käytön modulon kanssa AES:n s-boksien korvauksien laskemisessa.
Jotta \(e\):llä olisi olemassa käänteisluku, ei sillä ja \((p-1)(q-1)\):llä saa olla yhteisiä tekijöitä.
Näin on saatu muodostettua RSA-menetelmällä \(d\) eli salainen avain ja lukupari \((n,e)\) eli julkinen avain.
Vihje
RSA-menetelmässä käytössä olevasta julkisen avaimen osasta \(e\) voidaan käyttää myös nimitystä julkinen eksponentti. Yleisesti, esimerkiksi varmenteiden allekirjoituksissa, \(e\) saa arvon 65537.
RSA-avainten luominen parametrien avulla¶
Suoritetaan seuraavaksi RSA-avaimien luominen pienillä luvuilla.
Alice luo RSA-avaimen pienillä luvuilla. Tällöin hän esimerkiksi valitsee:
Hän valitsee kaksi alkulukua, \(p=151\) ja \(q=197\).
Näiden tulo on \(n=29747\) ja \((p-1)(q-1) = 29400\).
Valituista arvoista \(p\), \(q\) on laskettu \(n\) sekä \((p-1)(q-1)\), joka on nimeltään Eulerin totient funktio.
Seuraavaksi Alice valitsee julkisen avaimen toisen osan \(e\) ja laskee salaisen avaimen \(d\). Hän valitsee arvon \(e=17\), jolloin \(d=20753\), koska \(17 \cdot 20753 \pmod{29400} = 1\).
\(d=20753\)¶
\((n=29747, e=17)\)¶
Nyt Alice on saanut laskettua RSA:ssa tarvittavan salaisen avaimen \(d=20753\) ja julkisen avaimen, joka muodostuu kahdesta luvusta \((n=29747,e=17)\).
Tehdään sama myös Python-koodilla. Koodisolun jälkeisen tehtävän voi tehdä joko kynällä ja paperilla tai muokkaamalla seuraavaa koodia.
# Valitaan alkuluvut, joiden tulo on julkisen avaimen toinen osa
p = 151
q = 197
print("RSA alkuluvut asetettu, p={} ja q={}".format(p, q))
# Lasketaan n ja (p-1)(q-1)
n = p*q
p1q1 = (p-1)*(q-1)
print("RSA luku n = {}".format(n))
print("Euler totient (p-1)(q-1) = {}".format(p1q1))
# Alice valitsee julkisen avaimen toisen osan, yleensä pieni luku
e = 17
d = 0
# Etsimme salaisen avaimen d, jolla (e*d) mod (p-1)(n-1) == 1
# Käydään järjestyksessä lukuja läpi. Tämä on epätehokas tapa, mutta selkeä.
for i in range(p1q1):
# Lasketaan e*d mod (p-1)(q-1)
välitulos = (e*i) % p1q1
if välitulos == 1:
print("Löysimme salaisen avaimen d = {}".format(i))
d = i
print("Poistutaan etsintäluupista.")
break
# Näytetään mitä saatiin
print("###############################")
print("Salainen avain d = {}".format(d))
print("Julkinen avainpari (n, e) = ({},{})".format(n,e))
RSA-salatun viestin enkoodaus¶
Kun Bob haluaa lähettää viestin \(m\) Alicelle, hänellä pitää olla hallussaan Alicen julkinen avainpari \((N_A,e_A)\). Tämän lisäksi viestin tulee olla riittävän pieni, jotta se voidaan esittää \(n\) :ää pienempänä positiivisena kokonaislukuna.
Tämä rajoite \(n\):n koolle on yksi syy sille, miksi RSA:ta ei juuri käytetä tiedon salaamiseen vaan allekirjoittamiseen.
Tiedon salaaminen tapahtuu laskemalla salattu viesti \(c\):
Oletetaan, että Bob haluaa lähettää Alicelle viestin \(m=313\). Tällöin Bob salaa viestin \(m\) laskemalla \(c = 313^{17} \pmod{29747} = 515\) ja lähettää salakielisen viestin \(c\) Alicelle.
RSA-salatun viestin dekoodaus¶
Kun Alice vastaanottaa salatun viestin \(c\), hän voi purkaa Bobin lähettämän viestin salauksen laskemalla:
Nyt Alice voi purkaa Bobin lähettämän viestin laskemalla \(m = 515^{20753} \pmod{29747} = 313\).
Miksi salauksen purku toimii näin?
Tämä voidaan nähdä niin sanotun Eulerin lauseen perusteella, jonka mukaan \(m^{(p-1)(q-1)} \equiv 1 \pmod{pq}\).
Koska \(e\) ja \(d\) on määritelty otsikon RSA-lukujen laskenta yhteydessä näytetyllä tavalla, saadaan \(c^d = m^{ed} = m^{1+k(p-1)(q-1)} = m(1)^k = m\).
Katsomme samaa asiaa Python koodin avulla.Voit käyttää oheista koodisolua seuraavan tehtävän ratkaisemiseksi.
# Salauksessa lasketaan c^d (mod n) eli modulo_potenssiin käyttöön
from xip import modulo_potenssiin
# Tuotetaan Alicen avaimet, joita Bob käyttää
p = 151
q = 197
n_a = p*q
p1q1_a = (p-1)*(q-1)
e_a = 17
for i in range(p1q1_a):
välitulos = (e_a*i) % p1q1_a
if välitulos == 1:
d_a = i
break
# Näytetään Alicen avaimet
print("{}-ALICE-KEYGEN-{}".format(30*"#",30*"#"))
print("Alicen Salainen avain d = {} ja julkinen avainpari (n, e) = ({},{})".format(d_a,n_a,e_a))
# Bob salaa viestin 313
viesti = 313
salattu_viesti = modulo_potenssiin(viesti, e_a, n_a)
# Näytetään Bobin salaama viesti
print("{}--BOB-ENCODE--{}".format(30*"#",30*"#"))
print("Selväkielinen viesti {}".format(viesti))
print("Salakielinen viesti {}".format(salattu_viesti))
# Alice dekoodaa salatun viestin.
purettu_viesti = modulo_potenssiin(salattu_viesti, d_a, n_a)
print("{}-ALICE-DECODE-{}".format(30*"#",30*"#"))
print("Salattu viesti {}".format(salattu_viesti))
print("Purettu viesti {}".format(purettu_viesti))
Uhkakuvat RSA-menetelmälle¶
Carol ei pysty laskemaan salauksen purkua, koska hänellä ei ole Alicen salaista avainta \(d\). On kuitenkin ilmeistä, että jos Carol saa selville \(n\):n tekijät \(p\):n ja \(q\):n, turvallisuus on menetetty. Tällöin Carol voi helposti laskea \(d\):n julkisesta \(e\):stä. Salainen avain voidaan tuolloin laskea \(d = e^{-1} \pmod{(p-1)(q-1)}\).
Ei ole varsinaisesti osoitettu, että RSA:n turvallisuus olisi yhtenevä tekijöihin jaon vaikeuden kanssa, mutta koska yli 40 vuodessa ei ole helpompaakaan tapaa löydetty (oikein valituille parametreille), niin yleisesti uskotaan näin olevan. Toisaalta ei ole myöskään osoitettu, että tekijöihin jakoonkaan (tai diskreetin logaritmin ongelmaan) ei olisi olemassa tehokasta menetelmää, mutta koska tätä ongelmaa on tutkittu vieläkin pidempään, pidetään sellaisen löytymistä epätodennäköisenä.
Kvanttitietokoneiden kehittyminen muuttaa kuitenkin tätä tilannetta ratkaisevasti, kuten kurssin viimeisessä moduulissa käy ilmi.
Yhteenveto¶
Julkisen avaimen salausmenetelmän lisäksi RSA:ta käytetään erityisesti digitaalisiin allekirjoituksiin. Tätä aihetta käsitellään tarkemmin seuraavassa opetusmoduulissa.
Nyt esiteltyjen julkisen avaimen menetelmien lisäksi on olemassa elliptisiin käyriin perustuvia menetelmiä (engl. elliptic curve cryptography, ECC). Niissä matematiikka menee varsin hankalaksi nopeasti. Elliptisiin käyriin perustuvia kryptografisia menetelmiä käytetään siksi, että niillä saavutetaan pienemmillä avainten bittimäärillä suurempia turvatasoja. Voit lukea niistä lisää esimerkiksi suositun elliptisen käyrän ed25529 kuvauksesta.
Olemme nyt perehtyneet RSA-mentelmään ja:
osaamme suorittaa epäsymmetristen avaimien generoinnin
ymmärrämme julkisen avaimen ja salaisen avaimen eron
ymmärrämme, että myös \(n\):n laskemisessa käytetyt \(p\) ja \(q\) ovat salassa pidettävää tietoa
Tässä opetusmoduulissa esitetyt laskentamenetelmät otetaan seuraavassa moduulissa käyttöön julkisen avaimen infrastruktuurin luomisessa. Siinä rakennamme luottamusketjuja ja tuotamme digitaalisia allekirjoituksia hyödyntämällä epäsymmetrisiä menetelmiä.
Tällaisia infrastuktuureja käytämme ehkä tietämättämme päivittäin, kun surffaamme netissä.