Julkinen salakirjoitus RSA (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)).

eli

ed = k(p - 1)(q - 1) + 1 jollekin kokonaisluvulle k.

Merkitään kokonaislukuja (mod n) Zn = {0, 1, 2, ..., n - 1}. Kryptausfunktio on

f : Zn --> Zn : f(x) = xe (mod n),

ja dekryptausfunktio

g : Zn --> Zn : 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.

Vihje 1/2 Ratkaisu Vastaus