Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

2.6. Az RSA-algoritmus

2.6. Az RSA-algoritmus

Sok esetben – többek között a majd ismertetésre kerülő RSA algoritmusban – szükség van egészek hatványa valamely modulus szerinti maradékának meghatározására. Legyen . A feladat meghatározása lehetőleg elfogadható idő alatt. Ilyennek bizonyul a moduláris hatványozás algoritmusa. Ötlete a szám bináris felírásából jön. Legyenek a bitjei: . A legmagasabb helyiértékű bit 1-es. Ha -nek ki akarjuk számítani az értékét, akkor ezt megtehetjük a hatványaival történő számítással, Ugyanezt az eredményt megkaphatjuk a gazdaságosabb Horner séma szerint:

Itt láthatóan csak kettővel való szorzást és egy nulla vagy egy hozzáadását kell végezni, melyek számítástechnikailag hatékony műveletek. Ez annál inkább hasznos, mivel még a értékét sem kell kiszámítani az algoritmusban, hiszen az adott, hanem csak az egyes bitjeit kell elérni, ami eltolásokkal hatékonyan megvalósítható. A szám a kitevőben van, ezért a hatványozás során a kettővel való szorzásnak a négyzetreemelés az egy hozzáadásának pedig az alappal történő szorzás felel meg. Minden lépés után vehető a modulo szerinti maradék, így a használt számtartomány mérete mérsékelt marad.

A megfelelő algoritmus pszeudokódja:

Az algoritmusban ténylegesen a értékét nem kell kiszámítani, mert az végül a értékét adja majd.

2.7. Példa. .

Az RSA algoritmus fel fogja tételezni, hogy nagy prímszámaink vannak. Ilyenek keresésére egy eszköz lehet (nem a leghatékonyabb és nem abszolút biztos) az alábbi tételen alapuló algoritmus.

2.20. Tétel. A Fermat tétel

Ha prím, akkor

A tételt nem bizonyítjuk.

A tételre épülő prímszám ellenőrzési algoritmus egy egyszerű, de nem teljesen megbízható változatának a pszeudokódja:

Ha ez az algoritmus azt mondja, hogy a szám összetett, akkor az biztosan nem lesz prím. Ha azt mondja, hogy lehet, hogy prím, akkor nagy eséllyel valóban prímet vizsgált, ugyanis 10000-ig terjedően a számok között csak 22 olyan van, amely nem prím és a teszt esetlegesen prímnek minősíti. Ilyenek a Ötven bites számok esetén már csak a számok egy milliomod része lehet ilyen, 100 biteseknél pedig ez az arány 1:1013. Ezen hibák egy része kiszűrhető azzal, hogy a 2 helyett más alapot is beveszünk a moduláris hatványozásba, például a 3-at, stb. Sajnos azonban vannak olyan számok, amelyek mindegyik alap esetén prímnek maszkírozzák magukat ennél az algoritmusnál. Ezek az úgynevezett Carmichael számok. A Carmichael számok relatíve nagyon kevesen vannak. (Valójában végtelen sok ilyen szám van. Ilyenek: . Az első egy milliárd szám között csak 255 ilyen van.)

2.8. Példa. Döntsük el, hogy a 11 és a 12 prímek-e?

Ezen előkészületek után térjünk rá a fejezet céljára a nyilvános kulcsú titkosításra A titkosítás alapja az eredeti szöveg átalakítása, kódolása. A nyílvános kulcsok használata azt jelenti, hogy minden résztvevőnek van egy nyílvános, mindenki számára hozzáférhető kulcsa (, nyilvános, Public) és egy titkos, más által nem ismert kulcsa (, titkos, Secret). Legyen az üzenet. Legyen a két résztvevő és . küldi -nek az üzenetet titkosítva. Az elküldött titkosított szöveg , megkapja a üzenetet és a titkos kulcsával dekódolja A kulcsok egymás inverzei, és úgy vannak kialakítva, hogy a kulcs révén könnyű legyen titkosítani, de a kulcs ismeretében nagyon nehezen lehessen - praktikusan lehetetlen legyen - az kulcsot meghatározni. A digitális aláírás ilyenkor történhet úgy, hogy a küldő a titkosított szöveg mellé akár nyíltan odaírja a saját azonosítóját (aláírását), majd annak az titkosítottját. Ezután a alapján tudva, hogy kit nevez meg az aláírás, annak privát kulcsával dekódolja -et. . Ha , akkor nem történt átviteli hiba, vagy hamisítás, egyébként igen. Persze az -mel együtt is kódolható. Ez annak felel meg, mintha az első esetben nyílt levelezőlapon lenne az aláírásunk, a másodikban pedig mintha borítékba tettük volna.

Alább közöljük az RSA (Rivest – Shamir - Adleman) nyílvános kulcsú titkosítás algoritmusát. Az algoritmus feltételez két nagy prímszámot. (A gyakorlatban legalább 100-200 jegyűekre van szükség, hogy a titkosítás praktikusan feltörhetetlen legyen.) A kulcs felépítése , ahol a két prím szorzata, pedig egy kis páratlan szám. Az kulcs .

A szöveg titkosítása a alapján történik. Dekódolása pedig az alapján. A szöveg darabolásának bitméretét az szabja meg.

Az eljárás helyességét nem bizonyítjuk.

2.9. Példa. Számpélda RSA algoritmusra (nem életszerű, mivel a prímek kicsik)

Legyen a titkos választás:

A kibővített euklideszi algoritmust alkalmazzuk.

Láthatóan és multiplikatív inverze . Ez utóbbi helyett 280-at hozzáadva vesszük a 187-et. Ezek után akkor

Legyen az üzenetünk 100. Egy darabban titkosítható, mivel ez kisebb, mint 319. Titkosítsuk, majd fejtsük meg az üzenetet.

Titkosítás:

Tehát a titkosított érték:

Megfejtés:

Tehát a megfejtés: .