Francia tudósok feltörték az eddigi kísérletekben használt leghosszabb kriptográfiai kulcsot
2019 / 12 / 10 / Bobák Zsófia
Francia tudósok feltörték az eddigi kísérletekben használt leghosszabb kriptográfiai kulcsot
Ez az algoritmus ugyan sokkal gyengébb és rövidebb, mint amit a biztonsági titkosításoknál alkalmaznak, de az eredmény még így is hatalmas előrelépésnek számít. Bár, egyben arra is rávilágít, hogy az RSA kódok igenis feltörhetőek és még csak nincs is hozzá szükség kvantumszámítógépekre.

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)


Kövesd a Rakétát a Facebookon is!
Kövess, üzenj, kommentelj a Rakéta Facebook oldalán!
Ismerd meg a ROADSTER magazint!
AUTÓK - DESIGN - GASZTRO - KULT - UTAZÁS - TECH // Ha szereted a minőséget az életed minden területén, páratlan élmény lesz!
Ezek is érdekelhetnek
HELLO, EZ ITT A
RAKÉTA
Kövess minket a Facebookon!
A jövő legizgalmasabb cikkeit találod nálunk!

Hírlevél feliratkozás

Ne maradj le a jövőről! Iratkozz fel a hírlevelünkre, és minden héten elküldjük neked a legfrissebb és legérdekesebb híreket a technológia és a tudomány világából.