RSA-eljárás

A Wikipédiából, a szabad enciklopédiából

Az RSA-eljárás nyílt kulcsú (vagyis „aszimmetrikus”) titkosító algoritmus, melyet 1976-ban Ron Rivest, Adi Shamir és Len Adleman fejlesztett ki (és az elnevezést nevük kezdőbetűiből kapta). Ez napjaink egyik leggyakrabban használt titkosítási eljárása.[1] Az eljárás elméleti alapjait a moduláris- és a prímszámelmélet egyes tételei jelentik.

RSA-séma tétele[szerkesztés | forrásszöveg szerkesztése]

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, \varphi(N), 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[szerkesztés | forrásszöveg szerkeszté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 üzentet 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 = p q -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, \ d e \equiv 1\pmod{\varphi(N)}. Azaz de = 1 + k\varphi(N)\, bármely 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[szerkesztés | forrásszöveg szerkesztése]

Alíz (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ő az ismételt négyzetre emeléses hatványozással. B ezután továbbítja "üzenetét" A-nak.

Üzenet dekódolása[szerkesztés | forrásszöveg szerkesztése]

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

e d \equiv 1\pmod{p - 1}\, és
e d \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[szerkesztés | forrásszöveg szerkesztése]

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 = p q \,-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 d e \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[szerkesztés | forrásszöveg szerkeszté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 tanusí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öt üzenetet, az aláírást felemeli A nyilvános e\, kitevőjére, s veszi moduló 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[szerkesztés | forrásszöveg szerkesztése]

Jelenlegi matematikai ismereteink szerint egy megfelelő gondossággal 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 titkosított adat visszafejtésére nem létezik kellő gyorsaságú algoritmus, ezért a jövőben ilyen algoritmus felfedezése lehetséges.

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 prímtényezőit. Ha egy szám két igen nagy prímszám szorzata, akkor ennek prímtényezős felbontása még nagyon gyors számítógépekkel is nagyon sokáig tart.

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 polinom időn belül, mely az RSA és hasonló algoritmusok elavulásához vezetne.

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Lovász - Pelikán - Vesztergombi: Diszkrét matematika. 255.old. Typotex Kiadó, 2006. ISBN 963-9664-02-2

Felhasznált irodalom[szerkesztés | forrásszöveg szerkesztése]

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

További információk[szerkesztés | forrásszöveg szerkesztése]