RSA-eljárás

A Wikipédiából, a szabad enciklopédiából
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.[1] 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.[2]

RSA-séma tétele[szerkesztés]

Legyen p, q két nagy prím, és . Definiáljuk a T, M kulcspárt a következőképpen

legkisebb pozitív maradéka (mod N), .
legkisebb pozitív maradéka (mod N), .

Itt -re teljesül

. Nyilvános: és , titkos: és . Ekkor , é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 függvényértéket a kulcstulajdonos, a függvényértéket pedig bárki gyorsan ki tudja számítani.

Működése[szerkesztés]

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, -t és -t
  2. Számoljuk ki -t.
    • lesz a modulusa mind a nyilvános, mind a titkos kulcsnak is.
  3. Számoljuk ki az Euler-féle függvény értékét N-re: .
  4. Válasszunk egy olyan egész számot,-t melyre teljesül 1 < < , és és legnagyobb közös osztója 1. Azaz .
    • Az -t nyilvánosságra hozzuk, mint a nyilvános kulcs kitevője.
  5. Számítsuk ki -t, hogy következő kongruencia teljesüljön, . Azaz valamely pozitív egészre.
    • -t titokban tartjuk, mint a titkos kulcs kitevője.
  • A nyilvános kulcs az modulusból és a nyilvános kitevőből áll.
  • A titkos kulcs az modulusból és a titkos 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:
    • és : a kulcskészítéshez szükséges prímek,
    • és -et: gyakran dmp1 és dmq1-nek nevezik.
    • -et pedig iqmp-nek
  • A titkos kulcs minden része ezek alapján titokban tartandó. és nagyon fontosak, hiszen ezek a faktorai -nek, és gyors kiszámolását teszik lehetővé adott á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 és közötti relatív prím kapcsolat azért fontos, mert ez biztosítja, hogy a diofantoszi egyenletnek van megoldása, s az könnyen meg is kapható az euklideszi algoritmus segítségével!
  • Népszerű választás -re a . Néhány alkalmazásnál ehelyett -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]

Aliz (A) továbbítja a nyilvános kulcsát ( & )-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: < . Ezután kiszámítja kódszöveget a következő módon:

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]

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

Tudva -et vissza tudja kapni az eredeti szöveg üzenetet M-et.


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

.

Mivel

és

a kis Fermat-tétel kimondja

és
.

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

S így,

-t kapjuk, mely ugyanolyan gyorsan számolható, mint az üzenet titkosításánál kapott kongruencia.

Egyszerű RSA-példa[szerkesztés]

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
    és
  2. Számítsuk ki -t
  3. Számítsuk ki értékét.
  4. Válasszunk olyan -et, mely relatív prím 3120-hoz
  5. Számítsuk ki -t a kongruencia által. (-t egyedüli módon határozzuk meg és értékekből)
    17 * 2753 = 46801 = (15 * 3120) + 1.


A nyilvános kulcs , . Egy például ASCII-ba átkódolt üzenetre az RSA-eljárás a következő:

.

A titkos kulcs , . A dekódoló eljárás pedig:

.


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

Ahhoz, hogy visszafejtsük -t, így számolunk:

.

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]

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 -edik hatványára, majd veszi a kapott számot modulo (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 kitevőjére, s veszi modulo 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]

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.

Jegyzetek[szerkesztés]

  1. Lovász - Pelikán - Vesztergombi: Diszkrét matematika. 255. old. Typotex Kiadó, 2006. ISBN 963-9664-02-2
  2. Smart, Nigel: Dr Clifford Cocks CB. Bristoli Egyetem, 2008. február 19.

Források[szerkesztés]

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

További információk[szerkesztés]