Ha egy magányos számítógépre bízták volna a feladatot 35 millió órányi számítási időt, azaz 4000 évet igényelt volna a megoldás. A tudósok viszont nem csatlakoztak a slow motion mozgalomhoz, a verseny pont annak bizonyítására szolgált, hogy ezt a gigantikus időmennyiséget lehetséges teljesíthető méretűvé csökkenteni. A világ minden tájáról, Franciaországból, Németországból, az Egyesült Államokból összekapcsolt gépek (Intel Xeon Gold 6130) együttes kapacitása már elegendőnek bizonyult a megoldáshoz. A titkosítási módszert, melyet a tudósok a később megoldandó probléma generálására használtak, RSA algoritmusnak hívják, megalkotói: Ron Rivest, Adi Shamir és Leonard Adelman után. Ebben az algoritmusban két résztvevő két prímszám összeszorzásával kreálja a titkosíráshoz használt majdnem elképzelhetetlenül nagy számot. Persze az RSA kódolás jóval bonyolultabb két szám szorzatánál, de a nyilvános és titkos kulcs generálásának alapját a prímszámok adják, melyekből végtelen mennyiség áll rendelkezésre.

Ugyan léteznek trükkök, amelyekkel visszafejthetőek a nagyobb összegek és könnyen eldönthetővé válik, hogy oszthatóak e például kilenccel vagy tizeneggyel, de ha a nagyobb prímszámokhoz érünk, már nincs ilyen segítségünk.

Meg tudjuk mondani például, milyen prímszámok szorzásából keletkezik a 667? Nincs trükk, amivel ki lehetne nyomozni, itt bizony számolni kell (a választ a cikk végén eláruljuk).

A prímszám alapú titkosírás különlegessége, hogy az eredmény mindig egyedülálló. Az ilyen, két prím szorzásával keletkező különleges számokat hívjuk félprímeknek. A félprímek nem oszthatóak semmilyen összetett számmal, csakis prímekkel, eggyel és önmagukkal. Az összetett számok esetében léteznek nyomok és jelek, amire támaszkodhatunk, ha fel akarjuk bontani őket, de a félprímekre ez nem vonatkozik. Éppen ezért volt nehéz dolguk a kutatóknak, mikor megkísérelték feltörni a 240 decimális jegy hosszúságú összeget. Az RSA kódolást azért tudják biztonságosan használni a számítógépes titkosításokhoz, mert már az alap összetevők generálása is hihetetlen hosszúságú számokat tud létrehozni.

Csak az, hogy eldöntsék, a generált szám prím e, külön, erre szolgáló tesztek, mint például a Miller-Rabin teszt alkalmazását igényli. Az, hogy kizárólag prímszámokkal kellett dolgozni, leegyszerűsítette ugyan a feladatot, de még így is rendkívül komplexnek bizonyult a faktorizációs folyamat.

Hatalmas összegekkel kellett dolgozni, hiszen, ha csak a tíz jegyű összegeket vesszük alapul, a kilencmilliárd számból még így is hozzávetőlegesen négymilliárd prímszám, így 360 millió potenciális jelöltet kellett kipróbálni. 

Az RSA kódok feltörésével régóta próbálkoznak, nem csak a hackerek, hanem a biztonsági szakértők is. Az M.I.T. munkatársai 1977-ben alkották meg az algoritmust, először 1997-ben sikerült feltörni, igaz, ekkor csak egy 48 bites kóddal próbálkoztak. A következő áttörés 2002-ben Tokióban történt, az ekkor használt kód már 64 bites volt. A fejlődés nem csak a programok szofisztikációjának köszönhető, Moore törvénye is szerepet játszik. Gordon Moore, az Intel társalapítója már 1965-ben megjósolta, hogy a számítógépes chipek tranzisztorainak száma minden tizennyolcadik hónapban megduplázódik. Ezzel természetesen a gépek számítási kapacitása és teljesítőképessége is exponenciálisan növekszik, ez pedig szükségessé teszi, hogy a régi, “buta” gépekre írt titkosítási módszereket is időről-időre felülvizsgálják és hatékonyabbá tegyék. De a kvantumszámítógépek semmissé tehetik nem csak Moore törvényét, hanem az eddig használt algoritmusok eredményességét is.

Peter Shor matematikus már 1994-ben, a Shor algoritmus megalkotásakor előre figyelmeztette a világot, hogy a kvantumszámítással elviekben végrehajtható lesz a RSA kódolás faktorizációja, melyre az akkori rendszer még nem volt képes.

Most pedig, hogy valóban nyakunkon van a kvantumvilág eljövetele, már nem érdemes várakozni és bízni az eddigi tapasztalatokban, valóban újabb titkosítási módszerekre lesz szükség, különben a tárolt, privát vagy éppen szupertitkos adatok is a hackerek prédájává válhatnak.

Egyelőre azonban a szépsége az RSA alapú kódolásnak, és az oka, hogy ilyen népszerű a biztonsági kódolás világában, az, hogy ami matematikailag ilyen nehézséget tud okozni, és még egyelőre 35 millió órányi számítási időt vesz igénybe a megoldása, elveheti a kedvét a hackereknek is. Emiatt a komplexitás miatt lehetséges az RSA titkosítás nyilvános megosztása, mivel csak az tudja felfejteni a kódot, akinek az osztópár egyik fele a kezében van. És még így is végig kell csinálnia a hosszadalmas osztási folyamatot. A francia tudósok a mostani kísérlettel felülírták az előző rekordot, mind időben, mind a titkosírás hosszában, a régi rekord felállításakor 232 számjegyű összeggel dolgoztak. De még ez, a 795 bit hosszúságú kriptográfiai megoldó kulccsal feltörhető szám is eltörpül a számítógépes titkosítási rendszereknél használatos, 2048 bites számokhoz képest. Emmanuel Thomé, a csapat vezetője elmondta, hogy ugyan nehéz a műveletet hétköznapi nyelven elmagyarázni, de a győzelemben több faktor is szerepet játszott, például a jobb memória használat, a gyorsabb algoritmusok, vagy a jól megválasztott paraméterek. “De azt is mondhattuk volna, hogy a győzelem a különféle fejlesztéseknek köszönhető.”

“A tanulság a gyakorlati alkalmazás számára, hogy fogadjuk meg a tanácsokat és használjunk legalább 2048 bites, Diffie-Hellman vagy DSA kulcsokat, amelyek biztonságot nyújtanak a fejlesztések ellen” - mondta Nadia Heninger, a kutatócsoport egyik amerikai tagja.

Az ilyen kísérletek másik haszna pedig, hogy bizonyítani tudjuk: ha a mai világban mindent a számítógépekre bízunk, az információinkat, tudásunkat, adataink védelmét, még akkor sincs elzárva előlünk a lehetőség, hogy időnként túl járjunk a gépek eszén, és magunk is megoldjuk a problémákat. Még ha erre gépeket is kell használnunk.

(A válasz pedig: 23 és 29)

(Forrás: Popular Mechanics, Fotó: Piqsels, Wikimedia Commons)