RSA algoritmus

Üzenet titkosítása

Alice átadja nyilvános kulcsát ( n {\displaystyle n\,} & e {\displaystyle e\,} ) Bobnak, és titokban tartja magánkulcsát. Bob M üzenetet akar küldeni Alice-nek.

Először M-et egy m {\displaystyle m} számmá alakítja át, amely kisebb, mint n {\displaystyle n} , egy elfogadott reverzibilis protokoll, az úgynevezett kitöltési séma segítségével. Ezután kiszámítja a c {\displaystyle c\,} kódolt szöveget, amely megfelel:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

Ez gyorsan elvégezhető a négyzetre szorzásos exponenciálás módszerével. Bob ezután elküldi c-et c\displaystyle c\,} Alice-nak.

Üzenet dekódolása

Alice a következő eljárás során a d {\displaystyle d\,} magánkulcsának felhasználásával vissza tudja állítani m {\displaystyle m\,}   c {\displaystyle c\,} kódból:

m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}

Adott m {\displaystyle m\,} , vissza tudja állítani az eredeti különböző prímszámokat, a kínai maradéktételt alkalmazva erre a két kongruenciára a következőket kapjuk

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}}} .

Így,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Egy működő példa

Íme egy példa az RSA titkosításra és visszafejtésre. Az itt használt paraméterek mesterségesen kicsik, de az OpenSSL segítségével valódi kulcspárokat is létrehozhat és megvizsgálhat.

1. Válasszon két véletlenszerű prímszámot.
2.  : p = 61 {\displaystyle p=61} és q = 53 ; {\displaystyle q=53;} Számítsuk ki n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Számítsuk ki a totiens ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,}
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}
6. Válassza ki az e > 1 {\displaystyle e>1} 3120-nal koprimérikusan
7.  : e = 17 {\displaystyle e=17}
8. Válasszuk ki d {\displaystyle d\,} úgy, hogy d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}\equiv 1\,}
9.  : d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

A nyilvános kulcs ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Az m {\displaystyle m\,} kitöltött üzenethez a c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} titkosítási függvény a következő lesz:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,}

A titkos kulcs ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). A visszafejtési függvény m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} lesz:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,}

Például m = 123 titkosításához {\displaystyle m=123} , kiszámítjuk

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}}

A c = 855 visszafejtése {\displaystyle c=855} kiszámítjuk

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Mindkét számítás hatékonyan elvégezhető a moduláris exponenciálás négyzet- és többszörözési algoritmusával [en].

Az RSA egyenlet levezetése az Euler-tételből

Az RSA könnyen levezethető az Euler-tétel és az Euler-totiens függvény segítségével.

Kezdve Euler tételével,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

meg kell mutatnunk, hogy egy titkosított üzenet visszafejtése a megfelelő kulccsal visszaadja az eredeti üzenetet. Adott egy kitömött m üzenet, a c rejtjelezett szöveg kiszámítása a következő módon történik

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}

A visszafejtési algoritmusba behelyettesítve a következőt kapjuk

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}}

Meg akarjuk mutatni, hogy ez az érték is kongruens m-gyel. e és d értékét úgy választottuk meg, hogy kielégítő legyen,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

Vagyis létezik olyan egész szám k, hogy

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Most behelyettesítjük a titkosított, majd visszafejtett üzenetet,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}}

Alkalmazzuk Euler tételét, és elérjük az eredményt.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

Tömörítési sémák

A gyakorlatban az RSA-t valamilyen kitöltési sémával kell kombinálni, hogy az M értékei ne eredményezzenek bizonytalan titkosított szövegeket. A kitöltés nélkül használt RSA-nak lehetnek problémái:

• Az m = 0 vagy m = 1 értékek mindig 0, illetve 1 értékű titkosított szövegeket eredményeznek, az exponenciálás tulajdonságai miatt.
• Kis titkosítási exponensekkel (pl. e = 3) és kis m értékekkel történő titkosítás esetén az m e {\displaystyle m^{e}} (nem moduláris) eredménye szigorúan kisebb lehet, mint az n modulus. Ebben az esetben a rejtjelezett szövegek könnyen visszafejthetők a rejtjelezett szöveg et-gyökének a modulus figyelembevétele nélkül történő kivonásával.
• Az RSA titkosítás egy determinisztikus titkosítási algoritmus. Nincs véletlenszerű összetevője. Ezért egy támadó sikeresen indíthat a kriptorendszer ellen egy választott nyílt szövegű támadást. Szótárat készíthetnek úgy, hogy valószínűsíthető egyszerű szövegeket titkosítanak a nyilvános kulcs alatt, és az így kapott rejtjelszövegeket tárolják. A támadó ezután megfigyelheti a kommunikációs csatornát. Amint olyan rejtjelezett szövegeket lát, amelyek megegyeznek a szótárukban szereplő szövegekkel, a támadók ezt a szótárat felhasználhatják az üzenet tartalmának megismerésére.

A gyakorlatban az első két probléma rövid ASCII üzenetek küldésekor merülhet fel. Az ilyen üzenetekben az m egy vagy több ASCII-kódolt karakter(ek) összekapcsolása lehet. Az egyetlen ASCII NUL karakterből álló üzenet (amelynek számértéke 0) m = 0 kódolású lenne, ami 0 kódolt szöveget eredményez, függetlenül attól, hogy milyen e és N értékeket használunk. Hasonlóképpen, egyetlen ASCII SOH (amelynek numerikus értéke 1) mindig 1 titkosított szöveget eredményezne. Az olyan rendszerek esetében, amelyek hagyományosan kis e értékeket használnak, például 3-at, az összes, ezzel a sémával kódolt, egyetlen karakterből álló ASCII üzenet nem lenne biztonságos, mivel a legnagyobb m értéke 255 lenne, és 255³ kisebb, mint bármely ésszerű modulus. Az ilyen egyszerű szövegek visszanyerhetők a rejtjelezett szöveg kockagyökének egyszerű kivonásával.

E problémák elkerülése érdekében a gyakorlati RSA implementációk jellemzően valamilyen strukturált, véletlenszerű kitöltést ágyaznak be az m értékbe a titkosítás előtt. Ez a kitöltés biztosítja, hogy m nem esik a nem biztonságos valódi szövegek tartományába, és hogy egy adott üzenet a kitöltés után a nagyszámú lehetséges titkosítási szövegek egyikébe titkosítható. Ez utóbbi tulajdonság a szótáras támadás költségeit egy ésszerű támadó képességeit meghaladó mértékben növelheti.

Az olyan szabványokat, mint a PKCS, gondosan úgy tervezték, hogy az RSA titkosítás előtt biztonságosan kitömjék az üzeneteket. Mivel ezek a rendszerek az m nyílt szöveget bizonyos számú további bitekkel töltik fel, a kitöltetlen M üzenet méretének valamivel kisebbnek kell lennie. Az RSA kitöltési sémákat gondosan kell megtervezni, hogy megakadályozzák a kifinomult támadásokat. Ezt megkönnyítheti egy kiszámítható üzenetszerkezet. A PKCS-szabvány korai változatai ad-hoc konstrukciókat használtak, amelyekről később kiderült, hogy sebezhetőek egy gyakorlati adaptív, választott rejtjelezett szöveggel végrehajtott támadással szemben. A modern konstrukciók olyan biztonságos technikákat használnak, mint az optimális aszimmetrikus titkosítás kitöltése (Optimal Asymmetric Encryption Padding, OAEP), hogy az üzeneteket megvédjék, ugyanakkor megakadályozzák ezeket a támadásokat. A PKCS-szabvány rendelkezik olyan feldolgozási sémákkal is, amelyek az RSA-aláírások további biztonságát szolgálják, például a Probabilistic Signature Scheme for RSA (RSA-PSS).

Üzenetek aláírása

Tegyük fel, hogy Alice Bob nyilvános kulcsával küld neki egy titkosított üzenetet. Az üzenetben Alice-nek adhatja ki magát, de Bob nem tudja ellenőrizni, hogy az üzenet valóban Alice-től származik-e, mivel bárki használhatja Bob nyilvános kulcsát arra, hogy titkosított üzeneteket küldjön neki. Az üzenet eredetének ellenőrzésére tehát az RSA az üzenet aláírására is használható.

Tegyük fel, hogy Alice aláírt üzenetet kíván küldeni Bobnak. Készít egy hash-értéket az üzenetből, felemeli azt d mod n hatványára (akárcsak egy üzenet dekódolásakor), és "aláírásként" csatolja az üzenethez. Amikor Bob megkapja az aláírt üzenetet, az aláírást az e mod n hatványára emeli (akárcsak az üzenet titkosításakor), és az így kapott hash-értéket összehasonlítja az üzenet tényleges hash-értékével. Ha a kettő megegyezik, akkor tudja, hogy az üzenet szerzője birtokában volt Alice titkos kulcsának, és hogy az üzenetet azóta nem manipulálták.

Vegye figyelembe, hogy az olyan biztonságos kitöltési sémák, mint az RSA-PSS, ugyanolyan fontosak az üzenet aláírásának biztonságához, mint az üzenet titkosításához, és hogy ugyanazt a kulcsot soha nem szabad titkosításra és aláírásra is használni.