RSA-eljárás

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,  é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 
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:
Véletlenszerűen válasszunk két nagy prímet, -t és -t
Számoljuk ki -t.
 lesz a modulusa mind a nyilvános, mind a titkos kulcsnak is.
Számoljuk ki az Euler-féle  függvény értékét N-re: .
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.
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 
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 
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 
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.

Válasszunk két prímszámot
 és 
Számítsuk ki -t

Számítsuk ki  értékét.

Válasszunk olyan -et, mely relatív prím 3120-hoz

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 
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 
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

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ó

Kriptográfiai algoritmusok
Számelmélet