Mária
-7 °C
3 °C

Kétszázezer dollár két prímszámért

2001.07.26. 08:19
Az RSA idén ismét meghirdette 635 ezer dolláros összdíjazású faktorálási versenyét, melynek célja a számelméleti kutatások népszerűsítése. A nagy számok faktorálása során szerzett tapasztalatok ugyanis alapvető fontosságúak lehetnek az új kriptográfiai módszerek kidolgozásában és a régiek tökéletesítésében.
A verseny célja az RSA által megadott számok felírása prímszámok szorzataként, a 665 például megadható az 5, a 7 és a 19 szorzataként. A szám nagyságával arányosan nő a faktorálás nehézsége: a százjegyű számok a jelenlegi technológiával könnyen faktorálhatók, a kétszázjegyűnél nagyobb számok azonban komoly kihívást jelentenek.

Két prímszám kétszázezer dollárért

RSA-576, a 174 jegyű szám
18819881292060796383869723 94616504398071635633794173 82700763356422988859715234 66548531906060650474304531 73880113033967161996923212 05734031879550656996221305 168759307650257059
Az RSA direkt nehéz számokat választott, melyeket két nagy prímszám összeszorzásával képeztek, hasonlóan az RSA titkosításnál használt kulcspár tagjaihoz. A faktorálandó számok közül a legkisebb 174 jegyű, vagyis 576 bit hosszúságú, a legnagyobb 617 jegyű, vagyis 2048 bites. Az előbbi faktorálásáért tízezer dollár jár a megfejtőnek, az utóbbiért pedig 200 ezer.

Többszázezer számítógép dolgozik együtt

Mielőtt azonban valaki nekiáll otthon számolgatni, esetleg programot írni a prímszámok levadászására, érdemes megnézni az RSA számítókapacitási becslését. Míg egy 430 bites számot egyetlen géppel és akármennyi memóriával ki lehet vesézni, egy 760 bites szám megfejtéséhez már 215 ezer, legalább 500 megahertzes Pentium szükséges, összesen 4 GB memóriával. Így aztán az ehhez hasonló kihívások főleg tudományos elhivatottságú, és nem pénzéhes személyek érdeklődését vonzza, akik az interneten egyesítik gépeik számítókapacitását.

Évtizedekig vár megfejtőre a díj

Az eddig megfejtett legnagyobb szám 155 jegyű, vagyis 512 bites, ezt 1999 augusztusában fejtette meg egy kutatócsoport öt hónap alatt. Ez lényegesen több, mint az a kilenc hét, amely egy 140 jegyű szám faktorálásához kellett az előző verseny során. Az RSA arra számít, hogy az 576 bites feladványt legkésőbb jövőre megfejtik, a 2048 bites kihívás azonban még évtizedeken át frusztrálja a kódtörőket.