Az RSA titkosítási eljárás

RSA demo

A demo program használatának ismertetése (új ablak)

Gyakorlati megfontolások egy valódi RSA alkalmazás esetében

Mint láttuk, nyers erő alkalmazásával az eljárás segítségével titkosított üzenet gyakorlatilag megfejthetetlen. Léteznek azonban olyan módszerek, melyek az algoritmus gyenge pontjait, a kulcsgenerálás hibáit használják ki, s így mégis lehetőséget biztosítanak egy titkosított üzenet megfejtéséhez. Erre főleg akkor kerülhet sor, ha több felhasználós rendszerben egy központi számítógép végzi a kulcsok előállítását és kiosztását, és több felhasználó is ugyanazt az n értéket, vagy e számot kapja meg. További veszélyforrás, ha a prímeket, vagy az e számot túl kicsire választják, mert ez nagyon megkönnyíti a brute force támadást.

Összefoglalva, az alábbi feltételek szükségesek az eljárás biztonságához:

• p₁ és p₂ legyen nagy: legalább 512 bit
• p₁ és p₂ távolsága legyen azonos nagyságrendű p₁-gyel és p₂-vel, azaz a különbségük legyen legalább 511 bit; túl közeli prímek megkönnyítik a brute force támadást.
• p₁ és p₂ legyen véletlenül választott
• e és d ne legyen túl kicsi, ellenkező esetben a hatványozás könnyen megfejthető kódokat ad eredményül. Bizonyos programok a hatványozás felgyorsítása érdekében valamilyen e < 10 választással élnek. Ez azért veszélyes, mert ha x^e < n, akkor egyszerű e-edik gyök-vonással megfejthető az üzenet!
• Az e szám legyen véletlenszerűen választott; ellenkező esetben megkönnyítjük a támadó dolgát. Ha az e számot nem véletlenszerűen választjuk, hanem mindig ugyanazt az értéket használjuk (gyakori az e = 2¹⁶ + 1 = 65537 választás), akkor a támadó könnyebben meg tudja fejteni a titkos d kulcsot.
• Végül: ha szöveget akarunk titkosítani, az RSA demo programmal ellentétben soha ne karakterenként titkosítsunk, de még csak ne is karakter-blokkonként! A titkosítandó szöveg bináris kódjaiból, mint egységes bitfolyamból képezzünk közel 1024 bites blokkokat, és ezekre a blokkokra alkalmazzuk a titkosítást. Szemben más eljárásokkal (pl. DES), itt nincs előírva fix blokkméret, így célszerű változó blokkmérettel dolgozni.

Az RSA demo program képes szemléltetni nemcsak az RSA eljárást, hanem a módszer használata közben felmerülő hibákat is:

• Rövid prímek - a program alapvetően rövid prímeket generál, melyek szorzata gyorsan, könnyen faktorizálható. Lásd még: Determinisztikus prímteszt
• x > n - ha intervallumban kerestetünk prímeket, megadhatunk kis számokból álló, rövid intervallumot (például [3; 84]). Ekkor jó esély van rá, hogy a szorzat kisebb lesz, mint a karakter kódja, főleg, ha ékezetes karaktereket gépelünk be. Ekkor a titkosítás hibás kimenetet generál, és a megfejtett szöveg nem fog egyezni a titkosított szöveggel.
• p₁ vagy p₂ osztója x-nek - mivel lehetőség van rövid prímeket generálni, ezért megfigyelhetjük, milyen következményekkel jár, ha n és x nem relatív prímek: a karakter titkosított kódja maga a prím, amely x-nek és n-nek közös osztója.
• Végül: a karakterenkénti titkosítás minden azonos karakterre ugyanazt a kimenetet adja, ami az üzenet megfejthetőségét növeli.