Az elmúlt hét a kriptográfia szempontjából mindenképpen érdekes volt. Március 3-án Claus Peter Schnorr német kriptográfus és matematikus közzétett egy tanulmányt, amelynek címe „Factoring Integers by CVP and SVP Algorithms”. A nagy számok hatékony prímtényezőkre bontása hitelesítésszolgáltatói szempontból nem sok jót sugall, ráadásul a tanulmány kivonatában szerepelt az alábbi mondat: „This destroys the RSA cryptosystem”, azaz a tanulmány megállapításainak alkalmazásával a szerző állítása szerint a gyakorlatban is törhető az RSA algoritmus. Ez egy nagyon kemény állítás, és nem kevesebbet jelent, mint hogy ASAP lecserélendő/frissítendő minden RSA kulcsot használandó rendszer, azaz – jelenleg még – a kriptográfiai rendszerek nagy része. Még szerencse, hogy van mire. Azért mielőtt az ember belekezd egy ilyen attrakcióba, érdemes nagyon alaposan megvizsgálni, hogy valóban ilyen forró-e a helyzet.

Először is nézzük az ismert tényeket. Jelenleg is léteznek támadási metódusok gyenge vagy speciális paraméterekkel rendelkező RSA megtörésére, úgymint a Håstad támadás, vagy Coppersmith támadása. Kiemelendő, hogy ezek kizárólag megfelelő padding és algoritmus-paraméterek hiányában működnek (pl. amikor az e, vagyis a nyilvános exponens értéke 3). Ha valaki a megfelelően alkalmazott RSA-t szeretné törni, ahhoz viszont a nagy számok prímtényezőkre bontására kell kialakítania egy hatékony algoritmust, erre pedig jelenleg nincsen ismert módszer. A tanulmány állítása szerint azonban pont ez a helyzet változna meg!

PKI szakértőként az első kérdés, ami felmerült bennem, hogy mégis, nagyságrendileg mekkora számok felbontását mutatja be a cikk. Az absztrakt szerint „These new algorithms factor integers N≈2⁴⁰⁰ and N≈2⁸⁰⁰ using 7·10¹⁰ and 4.3·10¹² arithmetic operations, much faster then the quadratic sieve QS and the number field sieve NFS”, azaz körülbelül 800 bites számról van szó. Napjainkban a legelterjedtebb RSA kulcsméretek a 2048 és 4096 bit, azaz egy 800 bites szám igen távol áll a jelenleg széles körben alkalmazott paraméterektől. A másik kérdés, amely eszembe jutott, hogy amennyiben az itt leírtak átültethetők a gyakorlatba is, a szerző miért nem szemléltette ezt a faktorizálási versenyek rendelkezésre álló példáinak valamelyikének megoldásával.

Szerencsénkre azóta több szakértő is rámutatott a tanulmány állításainak hibáira; ezek közül az egyik legkritikusabb az R_n,f mátrix determinánsának Nⁿ⁺¹(n(n+1))/2 N-ként történő hozzárendelése volt , a helyes Nⁿ⁺¹ n! ln N helyett. Ez, ahogy többen is utaltak rá, nagy pontatlanságokhoz vezethet a számszerű becslések tekintetében.

Mások a gyakorlati megvalósítást igyekeztek górcső alá venni. Leo Ducas, a rácsalapú kriptográfia egyik kiemelkedő szakértője Sage implementációt készített a leírtakból, amelynek GitHub repozitóriuma a következő linken elérhető, így az elmélet ténylegesen tesztelhető is:

https://github.com/lducas/SchnorrGate

Ducas példaként a következő teszteket emelte ki (ahol b a prímtényezőkre bontandó számok bitmérete, n az elemek számának faktorbázisa, t pedig a próbálkozások száma):

Running b=10, n=47, t=1000, we obtained 353 Factoring Relation found out of 1000 trials.
Running b=20, n=47, t=1000, we obtained 65 Factoring Relation found out of 1000 trials.
Running b=40, n=47, t=1000, we obtained 0 Factoring Relation found out of 1000 trials.

Ez alapján Ducas azt a következtetést vonta le, hogy a megközelítésnek lehet értelme, ám egyebek mellett a megfelelő sikerhányadhoz sokkal nagyobb rácsdimenzió alkalmazása szükséges, mint amit Schnorr tanulmányában leírt. Csapatunk is lefuttatott néhány tesztet a script segítségével, és az szintén hasonló eredményekkel tért vissza.

Összegezve tehát, az eddigi vizsgálódások és elemzések egyelőre inkább cáfolni mint megerősíteni látszanak a Schnorr tanulmányában szereplő igen erős állítást. Ezt támasztja alá az nem elhanyagolható tény is, hogy a szerző március 4-én kiadott egy újabb verziót a cikkből, amelyben már nem szerepel az RSA törhetőségéről szóló megállapítás. Mindezek alapján nagy valószínűséggel kimondhatjuk, hogy egyelőre nem törhető a megfelelő paraméterekkel rendelkező RSA.

Nem szabad azonban elbíznunk magunkat. Az, hogy az RSA-t a megalkotása óta eltelt ~45 év alatt még nem sikerült megtörni, egyáltalán nem jelenti azt, hogy törhetetlen. A kitartó kriptográfusok évtizedek óta próbálkoznak, a számítógépek kapacitása folyamatosan nő (amely révén egy korábban nem hatékony törő algoritmus is kivárható időn belül eredményt érhetnek el), és a kvantumszámítógépek is megjelentek már a látóhatár szélén. Készen kell állnunk arra, hogy szükség esetén váltsunk, és ezért is nagyon érdemes tisztában lennünk az alternatív lehetőségekkel, például az elliptikus görbe alapú (ECC) megoldásokkal, vagy a post-quantum algoritmusokkal.