Szerző: Bizó Dániel

2010. január 11. 12:02

Megtört a 768 bites RSA titkosítás

Kutatóknak sikerült prím összetevőire bontani egy 768 bites számot, a már nem élő RSA Challenge folytatásaként. Ez azt jelenti, hogy a magasabb szintű biztonságot megkövetelő alkalmazásokhoz többé nem tekinthető elegendőnek a 768 bites RSA titkosítás.

Kétezer év processzoridő

A nemzetközi, amerikai, francia, japán, német és svájci kutatókból álló csapat által közzétett tanulmány szerint 2009 december 12-én sikerült prímtényezőkre bontaniuk egy 768 bites, azaz 232 számjegyből álló RSA-768 számot, amelyet a már visszavont RSA Factoring Challenge kezdeményezés által közzétett listáról vettek.

Az RSA Laboratories 1991-ben indította el a programot, hogy folyamatosan tesztelje a kulcsokra alapuló titkosítási algoritmusok erősségét. Az eddigi legerősebb visszafejtett kulcs 663 bites volt, ezt 2005 tavaszára sikerült prímekre bontani, míg egy 640 bitessel 2005 őszére végeztek. A sikeres faktorizáció azt jelenti, hogy az így titkosított adatok visszafejtése megfelelő erőforrások birtokában bizonyítottan lehetséges záros határidőn belül - igaz, a szükséges erőfeszítések láthatóan még mindig hatalmasak, a számítási kapacitások exponenciális növekedésével azonban néhány éven belül rutinfeladattá változhat.

A kutatók, akik publikációjukban hangsúlyozzák a feladat egy nagyságrenddel nagyobb nehézségét az általános faktorizációs rekordokhoz képest, az RSA-768 kulcsot egy úgynevezett számtest-szita (number field sieve) faktorizációs algoritmussal megdolgozva fejtették vissza két prímszámra, ahogyan az a korábbi törések esetében is történt. A probléma nagyságát jól érzékelteti, hogy a munka első fázisa, a megfelelő polinom kiválasztása fél évet vett igénybe 80 processzor bevetésével.

Ezt követően indult meg a szitálás (egy polinom kis prímekre bontható értékeinek azonosítása) amely nagyjából két éven át tartott gépek százain - becslés szerint egy 2,2 gigahertzes Opteron processzor 2 gigabájt memóriával 1500 évet bíbelődne el ezzel a lépéssel. A kutatók szándékosan túlzott szitálást alkalmaztak, hogy minimalizálják a mátrix méretét, aminek eredményeként 192 796 550 sort és oszlopot kaptak.

Az így felépített mátrix mérete 105 gigabájt lett, ezt követően, a harmadik és utolsó lépésként, lineáris algebrával, Wiedemann algoritmussal feldolgozták három hónap alatt, a végső eredményt pedig ezt követően négy és fél nap alatt sikerült elérni. A teljes feladat 2000 év gépidőt vett igénybe. A számításban x86-os akadémiai fürtök vettek részt világszerte, köztük egy 56 darab, két hatmagos Opteron gépből (672 darab 2,2 gigahertzes mag) álló és Infinibandet használó a lausanne-i politechnikumban, és egy 92 darab kétutas Xeon L5420 node -ból felépülő (736 mag 2,5 gigahertzen), Myrinet összeköttetéssel.

Újra és újra emelni kell a szintet

A publikáció megjegyzi, hogy a kutatás során szerzett adatok alapján már horizonton van az 1024 bites RSA faktorizációja is, és emiatt a körültekintő biztonsági politika legkésőbb három-négy éven belül már ezeket az RSA titkosításokat is kivonja a forgalomból, és magasabb szintű RSA kulcsokra (vagy más algoritmusra) vált. A kutatók prezentálták, hogy módszerük skálázható, vagyis a feladat tetszőleges számú gépre hatékonyan szétdarabolható, különösen a szitálás, amely minimális emberi közreműködést igényel.

A kifejezetten nagy értékű adatokra azonban már ezt sem javasolt használni, legalábbis az Egyesült Államok Kereskedelmi Minisztériumának számítógépbiztonsági hivatala és a nemzetbiztonsági hivatal kormányzati ajánlása szerint 2010-től az RSA-1024 sem tekinthető biztonságosnak, és legalább 2048 bites RSA-kulcsokat kell alkalmazni, de  \"bizalmas\" valamint \"szigorúan bizalmas\" területeken egyáltalán nem használható.

Fontos megjegyezni, hogy a különféle matematikai elveken működő algoritmusok erőssége nem vethető közvetlen össze az adott kriptográfia terminológiájában használatos bithosszal. Ez azt jelenti, hogy az egész számok faktorizációjára építő RSA és DSA titkosítási megoldások sokkal hosszabb kulcsokkal kell rendelkezzenek adott szintű védelemhez, mint például a véges testekre épülő AES-nek. Az AES-128 erősségét matematikailag az RSA-3072 hozza, az AES-256 pedig az RSA-15360 és SHA-384 titkosítással egyenértékű - az AES-256 és az SHA-384 vagy erősebb kulcsok jelenleg megfelelnek a legszigorúbb kormányzati követelményeknek.

Nagyon széles az a skála, amin az állásinterjú visszajelzések tartalmi minősége mozog: túl rövid, túl hosszú, semmitmondó, értelmetlen vagy semmi. A friss heti kraftie hírlevélben ezt jártuk körül. Ha tetszett a cikk, iratkozz fel, és minden héten elküldjük emailben a legfrissebbet!

a címlapról