Informatika | Felsőoktatás » RSA titkosítási algoritmus

RSA titkosı́tási algoritmus 1. Történeti áttekintés Az RSA betűszó az első nyilvános kulcsú (aszimmetrikus) titkosı́tási rendszer publikálóinak nevéből származik. Ronald Rivest, Adi Shamir és Leonard Adleman 1978-ban ı́rták le az algoritmusukat, s adtak elsőként olyan gyakorlati eljárást, amely bizonyı́totta, hogy a Diffie és Hellman által két évvel korábban felfedezett nyilvános kulcsú titkosı́tási elv a gyakorlatban is működik. Az ötlet jövedelmezővé tételére céget alapı́tottak, s a jó marketingjüknek is köszönhetően az RSA eljárás azóta nagy karriert futott be, a leginkább használt asszimmetrikus rendszernek számı́t. Sok kutató foglalkozik vele, s bár biztosságát ezideig nem bizonyı́tották, a legmegbı́zhatóbb nyilvános kulcsú titkosı́tási szisztéma. A nyilvános kulcsú titkosı́tási rendszert valójában már a 1960-as évek végén

felfedezték Angliában, de nemzetbiztonsági okokból nem került nyilvánosságra. Diffie és Hellman újrafelfedezése után is csak az állami titkosszolgálatok használhatták, majd 1991-ben Phil Zimmermann elkészı́tette az algoritmus PC-n használható változatát – melynek egyik része az RSA algoritmust használta – és feltette az Internetre. Ez volt a PGP (Pretty Good Privacy) program, mellyel az e-maileket lehetett tikosı́tani, és megnehezı́tette az nemzetbiztonsági hivatalok számára az e-mail forgalom megfigyelését. 1993-ban Zimmermannt az RSA cég és az amerikai vámhivatal beperelte, az első az RSA algoritmus licenc nélküli, jogosulatlan használatért, a másik a fegyverexportra vonatkozó törvények megsértéséért. Végül az ügy vádemelés nélkül zárult 1996-ban 2. Előkészı́tés Tételezzük fel, hogy van egy társaság, akik az egymás közötti kommunikációhoz az

RSA algoritmuson alapuló nyilvános kulcsú kriptorendszert szeretnék használni. Ahhoz, hogy az elképzelést megvalósı́tsák, a technikai feltételeken túl szükségük van a nyilvános, valamint a titkos kulcsok generálására. Ezt általában egy erre a célra szakosodott intézmény végzi el, s adja ki a felhasználók számára. Az RSA eljárás esetében a következőképpen zajlik le a kulcsok előállı́tása. 1. p és q két különböző, előre meghatározott nagyságrendű (jelenleg kb 150 decimális jegyűnél nagyobb) prı́mszám előállı́tása; 2. legyen n = p · q, és ϕ(n) = (p − 1)(q − 1) = n + 1 − p − q; 3. e ∈ N választása úgy, hogy 0 < e < ϕ(n) és gcd(e, ϕ(n)) = 1; 4. d ∈ N kiszámı́tása, melyre 0 < d < ϕ(n) és ed ≡ 1 (mod ϕ(n)); 5. p, q, ϕ(n) megsemmisı́tése, (n, e) lesz a nyilvános kulcs, d a titkos kulcs Megjegyzések (az

előkészı́tés egyes lépéseihez). 1. Ha p és q például pontosan 150 jegyűek, akkor 10150 < p, q < 10151 Ebben az intervallumban átlagosan minden 173-adik páratlan szám prı́m Mivel létezik gyors eljárás annak eldöntésére, hogy egy adott szám prı́m vagy összetett, ezért néhány próbálkozás után, rövid időn belül lehet a feltételeknek megfelelő prı́mszámokat generálni. 2. Nyilvánvalóan ebben a lépésben nincs sem elvi, sem gyakorlati nehézség 1 3. Először véletlenszerűen választanak egy e-jelöltet az adott intervallumból, majd az Euklideszi-algoritmus segı́tségével kiszámı́tják a legnagyobb közös osztót Ha az 1, akkor e megfelel, ha nem akkor a következő e-jelölt az előző jelölt plusz 1 lesz. Mivel az Euklideszialgoritmus gyors, ı́gy belátható időn belül eljutnak egy alkalmas e értékhez 4. e multiplikatı́v inverzének

meghatározásához az Euklideszi-algoritmus folytatását használják, amely pillanatok alatt megadja a d értéket. 5. Az adott felhasználó (n, e) publikus kulcsát minden felhasználó számára elérhető módon nyilvánosságra hozzák, d pedig csak az adott felhasználó által ismert titkos kulcs lesz. Az előkészı́téshez szükséges, de a felhasználás szempontjából felesleges értékeket biztonsági okokból megsemmisı́tik. Jelöljük most a felhasználókat az A, B, . betűkkel Az alábbi táblázat összefoglalja a kulcsok kiosztását. Felhasználók Nyilvános kulcsok Titkos kulcsok A (nA , eA ) dA B . . (nB , eB ) . . dB . . 1. táblázat Nyilvános és titkos kulcsok 3. Az RSA algoritmus részletezése 3.1 Üzenetküldés Tegyük fel, hogy az A felhasználó üzenetet szeretne küldeni B-nek. A következőket kell tennie. 1. Kikeresi a nyilvános ”telefonkönyvből” B

nyilvános (nB , eB ) kulcsát 2. A küldendő M üzenetet A felszabdalja M1 , M2 , azonos hosszúságú blokkokra, majd kódolással előállı́tja belőlük az x1 , x2 , . természetes számokat (nyı́lt üzenet) A blokkok hosszát úgy kell méretezni, hogy a belőlük származó xi számok nB -nél kisebbek legyenek (i = 1, 2, . ) 3. Jelölje x = xi az Mi szegmenshez rendelt természetes számot Az üzenet titkosı́tása a y ≡ xeB ( mod nB ) hatvány kiszámı́tásával történik. Ezután A elküldi B-nek az y1 , y2 , természetes számokból álló titkosı́tott üzenetet. 3.2 Üzenet fogadása B megkapja az y1 , y2 , . természetes számokból álló titkosı́tott üzenetet 2 1. Legyen y = yi (i = 1, 2, ) B felhasználva a dB titkos kulcsát kiszámı́tja az z ≡ y dB ( mod nB ) számot. Később megmutatjuk, hogy z éppen x lesz Ezzel B hozzájutott az x1 , x2 , természetes

számokból álló nyı́lt szöveghez. 2. A kódolási séma ismeretében B dekódolja az x1 , x2 , nyı́lt szöveget, és visszakapja belőlük az M1 , M2 , . szövegblokkokat 3. M1 , M2 , -t összeolvasva B megkapja az A felhasználó által küldött M üzenetet 3.3 Az algoritmus helyességének igazolása Azt kell megmutatni, hogy y dB ≡ x ( mod nB ). Az egyszerűség kedvéért a bizonyı́tás hátralevő részében mindenhonnan lehagyjuk a B indexet. Mivel d multiplikatı́v inverze e-nek, ezért e · d ≡ 1 (mod ϕ(n)), azaz ϕ(n) |(e · d − 1). Tehát létezik k ∈ N, melyre k · ϕ(n) = e · d − 1, vagyis e · d = k · ϕ(n) + 1. Ezt felhasználva y d ≡ (xe )d = xe·d = xk·ϕ(n)+1 ( mod n). I. Ha most gcd(x, n) = 1 akkor az Euler-Fermat tétel szerint ¡ ¢k xk·ϕ(n)+1 = xϕ(n) · x ≡ 1k · x = x ( mod n). II. Ha gcd(x, nB ) 6= 1, akkor p |x vagy q |x Mindkét esetben ugyanúgy kell eljárni Tehát tegyük

fel, hogy p |x. Ekkor q nem oszthatja x-et, mert ellenkező esetben p · q = n is osztaná x-et, de az lehetetlen mivel x < n. Vegyük észre, hogy p |x miatt p |xk·ϕ(n)+1 is teljesül, következésképpen ¡ ¢ p | xk·ϕ(n)+1 − x . (1) Másrészt ¡ ¢k·(p−1) xk·ϕ(n)+1 = xk·(p−1)(q−1)+1 = xq−1 · x ≡ 1k·(p−1) · x = x ( mod q), tehát ¡ ¢ q | xk·ϕ(n)+1 − x . Az (1) és (2) relációkból adódóan p · q = n is osztja a közös jobb oldalt, és ı́gy xk·ϕ(n)+1 ≡ x ( mod n). 4. Mintapélda A mintapélda a mintafeladatok.pdf fileban található 3 (2)