RSA-eljárás

Adi Shamir, az RSA egyik alkotója, 2009-ben

Az RSA-eljárás nyílt kulcsú (vagyis „aszimmetrikus”) titkosító algoritmus, melyet 1977-ben Ron Rivest, Adi Shamir és Len Adleman tett közzé (és az elnevezést nevük kezdőbetűiből kapta). Ez napjaink egyik leggyakrabban használt titkosítási eljárása. Az eljárás elméleti alapjait a moduláris számelmélet és a prímszámelmélet egyes tételei jelentik. Egy ezzel megegyező algoritmust fejlesztett ki Clifford Cocks matematikus is, amelyet a brit Government Communications Headquarters (GCHQ) már 1973-ban használt titokban, de ezt csak 1997-ben tehette közzé, a titkosítás feloldása után.

RSA-séma tétele

Legyen p, q két nagy prím, $N=pq$ és $(t,\varphi (N))=1$. Definiáljuk a T, M kulcspárt a következőképpen

$T(r)=r^{t}$ legkisebb pozitív maradéka (mod N), $r=1,2,\ldots ,N$.

$M(s)=s^{m}$ legkisebb pozitív maradéka (mod N), $s=1,2,\ldots ,N$.

Itt $\ m$-re teljesül

$mt=1+k\varphi (N)$. Nyilvános: $N,t$ és $T$, titkos: $p,q,m$ és $M$. Ekkor $M=T^{-1}$, és M a T ismeretében sem határozható meg.

A p és q prímeket a kulcstulajdonos véletlen számok prímtesztelésével nyeri, ezek segítségével m-et gyorsan meg tudja határozni. Az $M(s)$ függvényértéket a kulcstulajdonos, a $T(r)$ függvényértéket pedig bárki gyorsan ki tudja számítani.

Működése

Az RSA-titkosításhoz egy nyílt és egy titkos kulcs tartozik. A nyílt kulcs mindenki számára ismert, s ennek segítségével kódolhatják mások nekünk szánt üzeneteiket. A nyílt kulccsal kódolt üzenetet csak a titkos kulccsal tudjuk „megfejteni”. Az RSA-eljáráshoz a következő módon generáljuk a kulcsokat:

1. Véletlenszerűen válasszunk két nagy prímet, $\ p$-t és $\ q$-t
2. Számoljuk ki $\ N=pq$-t.
   • $\ N$ lesz a modulusa mind a nyilvános, mind a titkos kulcsnak is.
3. Számoljuk ki az Euler-féle $\ \varphi$ függvény értékét N-re: $\ \varphi (N)=(p-1)(q-1)$.
4. Válasszunk egy olyan egész számot,$\ e$-t melyre teljesül 1 < $e\,$ < $\varphi (N)\,$, és $e\,$ és $\varphi (N)\,$ legnagyobb közös osztója 1. Azaz $\ lnko(e,\varphi (N))=1$.
   • Az $e\,$-t nyilvánosságra hozzuk, mint a nyilvános kulcs kitevője.
5. Számítsuk ki $d\,$-t, hogy következő kongruencia teljesüljön, $\ de\equiv 1{\pmod {\varphi (N)}}$. Azaz $de=1+k\varphi (N)\,$ valamely $k\,$ pozitív egészre.
   • $d\,$-t titokban tartjuk, mint a titkos kulcs kitevője.

• A nyilvános kulcs az $N\,$ modulusból és a nyilvános $e\,$ kitevőből áll.
• A titkos kulcs az $N\,$ modulusból és a titkos $d\,$ kitevőből áll, melyeket természetesen nem osztunk meg mással.
• A hatékonyság érdekében a titkos kulcs egy más formáját szokás tárolni:
  • $p\,$ és $q\,$: a kulcskészítéshez szükséges prímek,
  • $d\mod (p-1)\,$ és $d\mod (q-1)\,$-et: gyakran dmp1 és dmq1-nek nevezik.
  • $q^{-1}\mod (p)\,$-et pedig iqmp-nek
• A titkos kulcs minden része ezek alapján titokban tartandó. $p\,$ és $q\,$ nagyon fontosak, hiszen ezek a faktorai $N\,$-nek, és $d\,$ gyors kiszámolását teszik lehetővé adott $e\,$ által (mely ugyebár nyilvános).
• Az N szám bináris alakban írt bitjeinek a száma adja a rejtjelzőkód hosszúságát, ami a gyakorlatban általában n=512, 1024, 2048 szokott lenni.
• Fontos megjegyezni, hogy $e\,$ és $\varphi \,$ közötti relatív prím kapcsolat azért fontos, mert ez biztosítja, hogy a $de=1+k\varphi (N)\,$ diofantoszi egyenletnek van megoldása, s az könnyen meg is kapható az euklideszi algoritmus segítségével!
• Népszerű választás $e\,$-re a $2^{16}+1=65537$. Néhány alkalmazásnál ehelyett $e\,$-t 3, 5, vagy 35-nek választják inkább. Ez azért hasznos mert kisebb eszközökön meggyorsíthatja a számolást, például bankkártyákon. Viszont ezek a kisebb nyilvános kitevők nagyobb kockázati tényezőket okoznak.

Üzenetkódolás

Aliz (A) továbbítja a nyilvános kulcsát ($N\,$ & $e\,$)-t Bobnak (B) és a titkos kulcsát titokban tartja. B ezután szeretné elküldeni üzenetét (M) A-nak

Először is M-et számokká alakítja (valamilyen egyezményes úton, pl.: ASCII kódolás), s darabolja úgy, hogy a kapott m értékre igaz legyen: $m\,$ < $N\,$. Ezután kiszámítja $c\,$ kódszöveget a következő módon:

$c=m^{e}\mod {N}$

Ez gyorsan végezhető moduláris hatványozással. B ezután továbbítja „üzenetét” A-nak.

Üzenet dekódolása

A ezután saját titkos kulcsát, $d\,$-t használva vissza tudja fejteni $m\,$-et $c\,$-ből a következőképpen:

$m=c^{d}\mod {N}$

Tudva $m\,$-et vissza tudja kapni az eredeti szöveg üzenetet M-et.

A dekódolási folyamat a következők miatt működik:

$c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {N}}$.

Mivel

$ed\equiv 1{\pmod {p-1}}\,$ és

$ed\equiv 1{\pmod {q-1}}\,$

a kis Fermat-tétel kimondja

$m^{ed}\equiv m{\pmod {p}}$ és

$m^{ed}\equiv m{\pmod {q}}$.

Mivel $p\,$ és $q\,$ eltérő prím számok, alkalmazva a kínai maradéktételt ezekre a kongruenciákra

$m^{ed}\equiv m{\pmod {pq}}$

S így,

$c^{d}\equiv m{\pmod {N}}$-t kapjuk, mely ugyanolyan gyorsan számolható, mint az üzenet titkosításánál kapott kongruencia.

Egyszerű RSA-példa

A következőkben láthatunk egy példát RSA-kódolásra és dekódolásra. A használt paraméterek szándékosan kicsik, de ha gondoljuk használhatjuk az OpenSSL-t eltérő kulcspárok generálására.

1. Válasszunk két prímszámot

   $p=61$ és $q=53$

2. Számítsuk ki $N=pq\,$-t

   $N=61*53=3233$

3. Számítsuk ki $\varphi (N)=(p-1)(q-1)\,$ értékét.

   $\varphi (N)=(61-1)(53-1)=3120$

4. Válasszunk olyan $e>1$-et, mely relatív prím 3120-hoz

   $e=17$

5. Számítsuk ki $d\,$-t a $de\equiv 1{\pmod {\varphi (N)}}\,$ kongruencia által. ($d$-t egyedüli módon határozzuk meg $e$ és $\varphi (N)$ értékekből)

   $d=2753$

   17 * 2753 = 46801 = (15 * 3120) + 1.

A nyilvános kulcs $N=3233$, $e=17$. Egy például ASCII-ba átkódolt $m\,$ üzenetre az RSA-eljárás a következő:

$c=m^{e}\mod {N}=m^{17}\mod 3233\,$.

A titkos kulcs $N=3233$, $d=2753$. A dekódoló eljárás pedig:

$m=c^{d}\mod {N}=c^{2753}\mod 3233\,$.

Például az $m=123$ üzenet rejtjelezéséhez a következőképp számolunk:

$c=123^{17}\mod 3233=855$

Ahhoz, hogy visszafejtsük $c=855$-t, így számolunk:

$m=855^{2753}\mod 3233=123$.

Ezen számítások mindegyike gyorsan, és hatékonyan számolható az ismételt négyzetre emeléses hatványozás segítségével.

Az üzenetek megjelölése

Bár az RSA jól adja át a nyilvános kulcsú titkosítás tulajdonságait, egy dolgot még nem tárgyaltunk, mely a titkosítás egyik alapkövetelménye, miszerint hogyan tehetjük biztossá, hogy tényleg a feladótól kaptuk az üzenetet, és nem valaki más küldött az ő nevében? Az alábbiakban ezt tárgyaljuk.

Tegyük fel, hogy Alíz (A) Bob (B) nyilvános kulcsát használja, hogy egy titkosított üzenetet küldjön neki. Az üzenetében bizonygathatja, hogy ő valóban A, de B-nek mégsem lesz semmi konkrét bizonyítéka, hogy ténylegesen A írt neki, hiszen a nyilvános kulcsát mindenki használhatja arra, hogy titkos üzenetet írjon neki. Ilyen bizonytalanságok elkerülése végett is használható az RSA, hogy RSA szintű biztonsággal tanúsíthassuk szerzői kilétünket. Ezzel a lépéssel pedig az RSA valódi nyilvános kulcsú titkosító eljárássá növi ki magát.

Tehát A szeretne küldeni egy üzenetet B-nek. Kivág az üzenetéből egy kis töredéket – ebből lesz a megjelölt üzenet – veszi ennek mondjuk az ASCII értékét, ezt az értéket felemeli a $d\,$-edik hatványára, majd veszi a kapott számot modulo $N\,$ (pont így csinálná, amikor dekódolna egy üzenetet), s a kapott végeredményt aláírásként hozzácsatolja az egyszerű módon titkosított üzenethez. (Mint látjuk ez is ugyanolyan hatásos mint ha az egész üzenetével az előbb vázolt műveleteket hajtotta volna végre csupán így sokkal gyorsabbá vált, hogy csak egy kis töredék értékre mutatta meg, hogy tényleg A az üzenet szerzője).

Hogyan dekódolja az aláírást B?

Mikor megkapja a megjelölt üzenetet, az aláírást felemeli A nyilvános $e\,$ kitevőjére, s veszi modulo $N\,$ az értéket (pont, mint amikor A-nak kódolna egy üzenetet), mivel a két művelet egymás inverzei, ezért összehasonlítja az eredményként kapott kivágott üzenetet az üzenetben szereplő egyszerű módon kódolt szövegrészlettel, s ha a kettő megegyezik, B biztosan tudhatja, hogy az üzenet szerzője A titkos kulcsának birtokában volt.

Biztonság

Jelenlegi matematikai ismereteink szerint egy megfelelő gondossággal (nagyon nagy számok alkalmazásával) kivitelezett RSA-titkosítás eredménye számításelméleti okok miatt nem fejthető vissza olyan gyorsan, hogy érdemes legyen megpróbálni. Azonban matematikailag nem bizonyított, hogy a jövőben valamilyen gyors algoritmus felfedezése ne lenne lehetséges, még ha jelenleg a titkosított adat visszafejtésére nem is létezik ilyen.

Az eljárás a nagy számok faktorizációjának problémáján alapul, vagyis hogy egy kellően nagy számról nehéz megállapítani annak osztóit, ha a szám két nagy prímszám szorzata. A prímtényezőkre való felbontás még nagyon gyors számítógépekkel is nagyon sokáig tart, nagyon nagy számok esetében.

1994-ben megjelent Peter Shor Shor's algorithm című publikációja, mely megmutatja, hogy egy kvantumszámítógép elviekben végre tudja hajtani a faktorizációt belátható időn belül, ami az RSA és hasonló algoritmusok elavulásához vezetne.

Források

• Simon Singh: Kódkönyv: a rejtjelezés és rejtjelfejtés története, Park Kiadó, 2002

További információk

• Alice és Bob - 9. rész: Alice és Bob nyilvános kulcsot használ
• Alice és Bob - 21. rész: Alice és Bob titkosít
• Alice és Bob - 22. rész: Alice, Bob és a kínaiak
• Alice és Bob - 23. rész: Alice és Bob prímszámok után nyomoz
• Netes RSA titkosító