Az amerikai RSA kriptográfiai vállalat széfjében lapuló két prímszámot azok szorzatából több hónapi munkával fejtették vissza német és holland kutatók. A felbontott szám 200 jegyû, vagyis ezzel megdöntötték japán kollégáik egy héttel ezelõtt bejelentett faktorizálási rekordját.
Jens Franke és Thorsten Kleinjung matematikusok a bonni egyetemen amszterdami kollégáikkal együttmûködve új világcsúcsot értek el a nagy számok prímtényezõkre bontásában. Megtalálták a RSA200 néven emlegetett, 200 jegyû óriásszám két prímfaktorát.
A számítási mûveletet a két fõiskola számítógépeire bízták, ezen kívül besegítettek a német informatikai biztonsági hivatal (BSI) nagygépei is. A bonni egyetemen ez a feladat három hónapig lekötötte az egy gigabites hálóra kapcsolt, 80 darab 2,2 GHz-es számítógépbõl álló clustert, írta a Technology Review.
Fûben, fában a prímszám
Az amerikai RSA Security kriptográfiai vállalat által 2001-ben kiírt faktorizálási versenyben az általuk kiötlött RSA200 prímtényezõinek meghatározása volt az egyik feladat. A nemzetközi kiírás több puszta szórakoztató fejtörésnél. A hagyományos, nyilvános kulcsú titkosítási és elektronikus aláírási eljárások azon a tényen alapulnak, hogy a nagy számoknak igen nehéz megtalálni a prímtényezõit.
Aki az interneten titkosított oldalon keresztül vásárol, online banki mûveletet végez, vagy aktiválja az autója indításgátlóját, mind erre az eljárásra hagyatkozik. Az új faktorizálási rekord ugyan nem teszi kérdésessé az említett eljárások biztonságát, az RSA szakértõi jelenleg mégis már a 300 jegyû számok használatát javasolják.
Elõztek a japánok
Az RSA200 megbontásával Jens Franke csapata visszaszerezte a faktorizálási rekordot, amelyet egy héttel korábban elvesztett. Május 2-án jelentette be ugyanis a japán Kazumaro Aoki, hogy munkatársaival az NTT távközlési konszern clusterét és a német kutatóknál bevált számítási eljárást használva megtalálták a 176 jegyû C176 (11281+1) prímtényezõit.
A korábbi csúcsot Franke, Kleinjung és kollégáik 2003 decembere óta tartották, amikor megdöntötték a két helyiértékkel rövidebb RSA576-ot. Ezt követõen sem ültek sokáig a babérjaikon, nekiláttak megszervezni az RSA200 felbontását.
Sokáig tartana
A nagy számok visszafejtésénél a kutatók azt a számelméleti algoritmust, a számteszt szitát (Number Field Sieve, NFS) használják, amelyet J.M. Pollard ötlött ki több mint 15 évvel ezelõtt.
Ez az eljárás rendszerezi és ezzel felgyorsítja a szükséges számítási mûveleteket. A faktorizálás ennek ellenére favágó munka, nem pedig célzott keresés. Az RSA200 esetében egyetlen 1 GHz-es pc kereken 121 év alatt készült volna el a feladattal.