Miklós
-7 °C
2 °C

Megdőlt a faktorizálási rekord

2005.05.12. 14:23
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.

Nászút ajándékba!

Esküvőt tervez? Tervezzen velünk, nyerjen wellness nászutat!

Budapest Te Csodás!

Karácsonyi pompába öltözött utcák, színes adventi vásárok, gazdag kulturális élmények, ez mind Budapest.