1(mod(p - 1)(q - 1)).
RSA -salakirjoituksen nimi tulee kolmen matemaatikon (Rivest, Shamir ja Adleman) nimien alkukirjaimista. Se on tällä hetkellä laajimmin käytetty julkisen salakirjoituksen muoto.
Julkinen salakirjoitus perustuu kahden avaimen ideaan, jossa kryptausavain on julkinen (kaikkien tiedossa), mutta dekryptausavain on vain käyttäjänsä tiedossa. Kryptaus- ja dekryptausfunktiot ovat toisistaan riippuvia, mutta niiden päätteleminen toisistaan on kohtuullisessa ajassa mahdotonta. Tämä johtuu tekijöihinjakoalgoritmin hitaudesta riittävän suurilla luvuilla. Esimerkiksi 1000 -numeroisen luvun täydellinen tekijöihinjako ei onnistu kohtuullisessa ajassa edes nykyisillä supertietokoneilla.
RSA-kryptokoodissa valitaan kaksi (isoa) alkulukua p ja q, lasketaan niiden tulo n = pq sekä valitaan kokonaisluvut e ja d siten, että
ed 1(mod(p - 1)(q - 1)).
ed = k(p - 1)(q - 1) + 1 jollekin kokonaisluvulle k.
Merkitään kokonaislukuja (mod n)
n = {0, 1, 2, ..., n - 1}. Kryptausfunktio
on
f : n 
n : f(x) = xe (mod n),
g : n n : g(y) = yd (mod n).
Luvut e ja d voidaan valita siten, että ensin etsitään kokeilemalla sellainen e, jolle on voimassa
syt(e, (p - 1)(q - 1)) = 1,
ja ratkaisemalla sen jälkeen d kongruenssista
ed 1 (mod(p - 1)(q - 1)).
Näistä julkistetaan n ja e, muut pidetään salaisina.
Olkoon p = 37, n = 1961 ja e = 19. Laske pienin mahdollinen positiivinen d:n arvo kyseiseen RSA–systeemiin.
q = 
= 53,
Tämän jälkeen ratkaistaan d yhtälöstä de = k(p - 1)(q - 1) + 1, josta saadaan
d = 
.
| Piilota ratkaisu |