Az RSA egy nyilvános kulcsú kriptográfiai algoritmus, amelyet Ronald Rivest, Adi Shamir és Len Adleman fejlesztett ki. Ma az RSA messze a legelterjedtebb nyilvános kulcsú kriptográfiai algoritmus.

A kriptográfiai alapfogalmakról szeretne olvasni?

Az RSA kódolás - akár titkosítást, akár dekódolást, akár aláírás készítését vagy annak ellenőrzését értjük kódolás alatt - moduláris hatványozással történik. Ez azt jelenti, kódoláskor hatványozást végzünk, a kódoló bemenetét (pl. a titkosítandó vagy aláírandó üzenetet) felemeljük a kulcs által meghatározott hatványra, majd a kapott eredményt elosztjuk egy ún. modulussal és a kapott maradékkal számolunk tovább.

Amikor az Alajos nevű felhasználó RSA kulcspárt generál, a következő műveleteket végzi el:

1. Kiválaszt két nagy véletlen prímszámot. E két prímszám legyen p és q.
2. Összeszorozza őket, a kapott szorzat lesz a modulus, m = p * q.
3. Kiszámítja a Φ(m) = (p-1) * (q-1) értéket.
4. Kiválaszt egy olyan e egész számot, amely relatív prím Φ(m)-hez (azaz a legnagyobb közös osztójuk 1).
5. Kiszámít egy olyan dértéket, amelyre d * e = 1       (modulo Φ(m)) 

   azaz, ha e és d szorzatát elosztjuk Φ(m)-mel, akkor 1-et kapunk maradékul.

Az így kiszámított értékek közül:

• Alajos nyilvános kulcsa m és e.
• Alajos magánkulcsa d.

Ekkor bármilyen x < m egész számra igaz, hogy ( x^e ) ^d = x (modulo m). Erre az egyenlőségre épül az RSA kódolás és dekódolás.

Tegyük fel, hogy Bendegúz az x üzenetet szeretné titkosítva elküldeni Alajosnak. Ehhez megszerzi Alajos nyilvános kulcsát, azaz az m és e számokat. Bendegúz a következő módon határozza meg az y titkosított üzenetet:

y = x^e       (modulo m)

Alajos a következő módon állítja vissza az x nyílt üzenetet:

x = y^d       (modulo m)

Tegyük fel, hogy Alajos alá szeretné írni az x dokumentumot. Ekkor a következő módon számítja ki az s aláírást:

s = x^d       (modulo m)

Bendegúz megkapja az x dokumentumot és az s aláírást, és Alajos (m, e) nyilvános kulcsát. A következő egyenlőség ellenőrzésével döntheti el, hogy ezek összetartoznak-e:

s^e = x       (modulo m)

Az RSA algoritmus biztonsága a következőkre épül:

• Nem ismert hatékony algoritmus egy nagy egész szám prímtényezőinek meghatározására. (Ez az ún. IFP, azaz integer factorization problem.) Így a támadó m birtokában nem tudja kiszámítani p és q értékét.
• Nem ismert hatékony algoritmus egy szám moduláris i. gyökének meghatározására. Így a támadó e és y=x^e birtokában nem tudja kiszámítani x értékét.

Megjegyzés:

1. RSA esetén a kulcshosszat az m modulus méretével szokás megadni. Ha 2048 bites RSA-ról beszélünk, akkor m hossza 2048 bit, azaz p és q két 1024 bites prím. (Célszerű, ha p és q hasonló nagyságrendbe esik. Ha az egyikük nagyon kicsi, akkor az RSA könnyebben támadható.) Az e nyilvános kitevőt kicsinek szokás választani, míg dvalószínűleg 2048 bites lesz.

    

2. A p és q prímeket kiválasztása a következő módon történik: Generálunk egy kellően nagy véletlen számot, majd megnézzük, hogy prím-e. Az olyan méretű számok esetén, amelyekkel az RSA már biztonságos, hagyományos módon, pl. az Eratosztenészi szita segítségével nem reális megvizsgálni, hogy az adott szám prím-e. A gyakorlatban valószínűségi alapon működő prímteszteket (pl. a Miller-Rabin tesztet) szokás alkalmazni, de alkalmazható pl. a determinisztikus AKS prímtesztis.

    

3. A p és q értékekre a kulcsgenerálást követően elvileg nincsen szükség. Ugyanakkor, ezen értékek nem juthatnak a támadó kezébe, mert segítségükkel könnyen meghatározható a d magánkulcs. Sok implementáció rögtön a kulcsgenerálást követően megsemmisíti őket. Más implementációk megőrzik a p és q számokat, mert segítségükkel az RSA műveletek - a kínai maradéktételre alapuló, ún. RSA-CRT módszerek segítségével - gyorsabban végezhetőek el. (A p és q számokkal kizárólag a magánkulccsal végzett műveletek gyorsíthatóak, mert p és qnem hozható nyilvánosságra.)

    

4. Az RSA szimmetrikus, igaz rá, hogy (x^e)^d = (x^d)^e), így RSA esetén a dekódolás és az aláírás (valamint a titkosítás és az aláírás ellenőrzése) ugyanaz a művelet. A fenti szimmetriából az is következik, hogy ha az e értéket véletlenül választjuk, és titokban tartjuk, akkor e akár a magánkulcs szerepét is betöltheti. Ha ekkor d értékét hoznánk nyilvánosságra, akkor d lehetne a nyilvános kulcs. Ezek RSA-specifikus tulajdonságok, más nyilvános kulcsú kriptográfiai algoritmusok esetén jellemzően nem állnak fent.
5. Az e nyilvános kitevő kiválasztásakor egyetlen szempont, hogy az relatív prím legyen a Φ(m) számhoz. Mivel e értékét nyilvánosságra hozzuk, e általában nem véletlen szám, hanem sokszor rögzített érték. Az e-edik hatványra emelést általában az ismételt négyzetreemelés és szorzás (method of repeated squaring) algoritmussal számítjuk ki, és ennek sebességét az határozza meg, hogy e binárisan felírva hány 1-est tartalmaz. Korábban gyakori volt az e = 3 választás, mert 3 a legkisebb szóba jöhető e, és binárisan ábrázolva 11. Tekintve, hogy a nagyon kis e értékek ellen léteznek ismert támadások, ma az e = 65537 a gyakori választás. (A 65537 prím szám, és binárisan ábrázolva 10000000 00000001.)
6. Létezett olyan megközelítés, hogy egy rendszer összes felhasználója azonos modulust használjon, és különböző e értékeket válasszanak. (Ekkor egy központi szerver osztaná a d értékeket.) E megoldás nem szerencsés, léteznek támadások a közös e értékekre.