RSA-eljárás

nyílt kulcsú titkosító algoritmus
(RSA szócikkből átirányítva)
Ez a közzétett változat, ellenőrizve: 2024. április 17.

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]

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

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ő moduláris 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.

  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.
  • Simon Singh: Kódkönyv: a rejtjelezés és rejtjelfejtés története, Park Kiadó, 2002

További információk

szerkesztés