美国多位部长花公款“毫不手软”购置豪华引公愤

RSA Securityn valmistama laite, joka tuottaa valtuutusavaimia. Laitteen algoritmi tuottaa vaihtuvan salasanan 60 sekunnin v?lein. RSA SecurID toimii siten, ett? kirjautumiseen tarvitaan k?ytt?j?tunnus ja p??sykoodi, joka koostuu k?ytt?j?n salasanasta (esimerkiksi 1234) ja laitteen n?ytt?m?st? koodista (esimerkiksi 567890), jolloin p??sykoodi on 1234567890.

百度 　　从具体榜单来看，计算机类专业虽然几经起伏，但在近五年中竞争力非常稳健。

RSA on julkisen avaimen salausalgoritmi, jota k?ytet??n laajalti muun muassa elektronisessa kaupank?ynniss?. Ron Rivest, Adi Shamir ja Len Adleman kehittiv?t algoritmin vuonna 1977; menetelm?n nimi tulee heid?n sukunimiens? alkukirjaimista.

RSA:n kuvaus julkaistiin vuonna 1978 Communications of the ACM -julkaisussa. Julkaisussa motivaatioksi mainittiin Diffie-Hellman avaintenvaihtoa kuvaava artikkeli New Directions in Cryptography. RSA oli ensimm?inen k?yt?nn?llinen julkisen avaimen salaus. RSA:n turvallisuus perustuu olettamukseen, jonka mukaan eritt?in suurien alkulukujen (jaollinen vain itsell??n) tulon tekij?ihinjako on vaikeaa. Kyseess? on yksisuuntainen modulaari funktio, joka on helppo laskea mutta todella hankalaa ja aikaa viev?? laskea taaksep?in.

MIT sai Yhdysvalloissa RSA:ta koskevan patentin vuonna 1983. Patentti raukesi syyskuussa 2000. Patentti ei koskenut muita maita, koska algoritmi oli jo julkaistu ennen patenttihakemusta.

RSA perustuu julkiseen ja yksityiseen avaimeen ja siihen, ettei yksityist? avainta voida nykytekniikalla k?yt?nn?ss? johtaa julkisesta avaimesta. Julkisen avaimen avulla voidaan luoda salattuja viestej?, jotka voidaan lukea ainoastaan yksityisen avaimen avulla. N?in taho, joka esimerkiksi haluaa tarjota kenelle tahansa mahdollisuuden l?hett?? itselleen salattuja viestej?, voi julkaista julkisen avaimen kaikille, mutta pit?? yksityisen avaimen itsell??n. T?ll?in kuka tahansa voi l?hett?? kyseiselle vastaanottajalle salatun viestin, jonka ainoastaan vastaanottaja voi yksityisell? avaimellaan avata. T?t? kutsutaan ep?symmetriseksi salaukseksi erotuksena vanhemmasta symmetrisest? salauksesta, jossa l?hett?j?ll? ja vastaanottajalla on sama salausavain, jonka on pysytt?v? salassa.

Toisaalta my?s yksityisell? avaimella voidaan luoda salattuja viestej?, jotka voidaan avata vain julkisella avaimella; t?m?n ominaisuuden avulla yksityisen avaimen haltija voi allekirjoittaa viestins? siten, ett? julkisen avaimen haltijat voivat olla varmoja siit?, ett? viestit ovat per?isin h?nelt?.

Toiminta

Avainten luonti

Oletetaan ett? Liisa haluaa Pekan l?hett?v?n h?nelle yksityisen viestin turvatonta reitti? pitkin. H?n toimii seuraavasti luodakseen julkisen avaimen ja yksityisen avaimen:

1. Valitse kaksi suurta alkulukua p ≠ q satunnaisesti ja toisistaan riippumatta. Laske N = p q.
2. Valitse kokonaisluku e siten ett? 1 < e < N jolle (p-1)(q-1) on suhteellinen alkuluku.
3. Valitse d siten, ett? d e ≡ 1 (mod (p-1)(q-1)).
4. Tuhoa kaikki p:t? ja q:ta koskevat tiedot.

• (Kohdat 2 ja 3 voidaan suorittaa laajennetulla Eukleideen algoritmilla; ks. modulaariaritmetiikka.)

N ja e muodostavat julkisen avaimen ja N sek? d muodostavat yksityisen avaimen. Huomaa, ett? ainoastaan d on salainen ja ett? N on julkisesti saatavilla. Liisa l?hett?? julkisen avaimen Pekalle ja pit?? yksityisen avaimen salaisena.

Viestin salaaminen

Sitten lasketaan salattu viesti c kun n on Pekan alkuper?inen viesti:

$c\equiv n^{e}\ (\mathrm {mod} \ N)$

Salauksen purkaminen

Liisa saa c:n Pekalta ja tiet?? salaisen avaimensa d. H?n voi palauttaa n:n c:st? seuraavan kaavan avulla:

$n\equiv c^{d}\ (\mathrm {mod} \ N)$

Purku toimii, koska

$c^{d}\equiv n^{e\cdot d}\ (\mathrm {mod} \ N)$

ja ed ≡ 1 (mod p-1) ja ed ≡ 1 (mod q-1). Fermat’n pieni lause antaa

$n^{e\cdot d}\equiv n\ (\mathrm {mod} \ p)$     ja     $n^{e\cdot d}\equiv n\ (\mathrm {mod} \ q)$

jonka mukaan (koska p ja q ovat erisuuria alkulukuja)

$n^{e\cdot d}\equiv n\ (\mathrm {mod} \ pq)$

Esimerkki

Valitaan vaikkapa alkuluvut 5 ja 11. Niiden tulo (N) on 55. ?(55) = 40. Valitaan julkinen avain e, siten ett? (P, ?(R)) = 1. (7, 40) = 1. Julkinen avain e = 7. Henkil?kohtaisen avaimen d ratkaisuun tarvitaan luvun 7 k??nteisluku mod ?(55) = 40. T?h?n voidaan l?yt?? ratkaisu 7x ≡ 1 (mod 40), joka on x ≡ 23 (mod 40). d on siis 23. N?in saadaan avainparit (e = 7, N = 55) ja (d = 23, N = 55)

Salattava sanoma olkoon: TERVE koodattuna numeroiksi merkkikoodauksella: 28, 7, 26, 31, 7

Koodataan se julkisella avaimella e, jolla on arvo 7.

28^7 (mod 55) = 13492928512 (mod 55) = 52

7^7 (mod 55) = 823543 (mod 55) = 28

26^7 (mod 55) = 8031810176 (mod 55) = 16

31^7 (mod 55) = 27512614111 (mod 55) = 26

7^7 (mod 55) = 823543 (mod 55) = 28

Sanoma on siis salattuna 52, 28, 16, 26, 28.

Sanoman purkaminen tapahtuu henkil?kohtaisella avaimella d, jolla on arvo 23.

52^23 (mod 55) = 2.9381698884548476032434836e+39 (mod 55) = 28

28^23 (mod 55) = 1.9259043800372760688541191e+33 (mod 55) = 7

16^23 (mod 55) = 4951760157141521099596496896 (mod 55) = 26

26^23 (mod 55) = 3.5025714498220057526153130e+32 (mod 55) = 31

28^23 (mod 55) = 1.9259043800372760688541191e+33 (mod 55) = 7

Selkokielell? siit? tulee j?lleen TERVE.

Allekirjoittaminen

P??artikkeli: Digitaalinen allekirjoitus

RSA:ta voidaan k?ytt?? my?s viestien allekirjoittamiseen. Sek? l?hett?j? ett? vastaanottaja laskevat tiivistefunktion (esimerkiksi MD5, SHA-1) avulla viestin kryptografisen tiivisteen. L?hett?j? koodaa tiivisteen salaista avaintaan k?ytt?en (kuten purkaisi julkisella avaimella salatun viestin), ja l?hett?? koodatun tiivisteen viestin mukana vastaanottajalle. Vastaanottaja avaa koodatun tiivisteen k?ytt?en julkista avainta (kuin salaisi sen). Mik?li tiivisteen koodauksen avaaminen tuottaa viestin alkuper?isen tiivisteen, vastaanottaja voi pit?? varmana sit?, ett? viestin allekirjoittaja on k?ytt?nyt julkista avainta vastaavaa salaista avainta.

Algoritmit

RSA:n toteutus perustuu nopeaan potenssiinkorotusalgoritmiin j??nn?sluokkarenkaassa modulo $N$. Potenssiinkorotuksen toteuttamiseksi tarvitaan nopea kertolaskualgoritmi samassa renkaassa.

J?rjestelm?n avainten valinnassa tarvitaan isoja alkulukuja, jotka on mahdollisimman satunnaisesti valittu. T?t? varten tarvitaan nopeita ja luotettavia alkulukutestej?.

Turvallisuus

Toistaiseksi ei ole todistettu, ett? N:n tekij?ihinjako olisi ainoa tapa p??tell? n c:n perusteella. Helpompaa menetelm?? ei kuitenkaan ole toistaiseksi keksitty. Niinp? yleisesti oletetaan, ettei Eeva voi lukea viesti?, jos N on tarpeeksi suuri.

RSA-pulmaksi kutsutaan selkokielisen tekstin etsimist? salatun tekstin ja julkisen avaimen perusteella.

Peter Shor osoitti 1993 ett? kvanttitietokone voisi periaatteessa suorittaa tekij?ihinjaon polynomisessa ajassa. Jos kvanttitietokoneista tulee k?ytt?kelpoisia, Shorin algoritmi tekee RSA:sta vanhentunutta teknologiaa.

Kirjallisuutta

• Singh, Simon 1999: Koodikirja : salakirjoituksen historia muinaisesta Egyptist? kvanttikryptografiaan. Helsinki: Tammi

Aiheesta muualla

• Jussi Palola: RSA-salausalgoritmi ja alkuluvut (gradu)