![]() |
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:
- Kiválaszt két nagy véletlen prímszámot. E két prímszám legyen p és q.
- Összeszorozza őket, a kapott szorzat lesz a modulus, m = p * q.
- Kiszámítja a Φ(m) = (p-1) * (q-1) értéket.
- 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).
- 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 ( xe ) 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:
Alajos a következő módon állítja vissza az x nyílt üzenetet:
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:
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:
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=xe birtokában nem tudja kiszámítani x értékét.
- 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 d valószínűleg 2048 bites lesz.
- A p és q prímek 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ímteszt is.
- 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 q nem hozható nyilvánosságra.)
- Az RSA szimmetrikus, igaz rá, hogy (xe)d = (xd)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.
- 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.)
- 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.