A digitális világ hatalmas része az RSA titkosítására támaszkodik a magánélet és a biztonság érdekében. Egy nemrégiben készült matematikai cikk, amely „tönkreteszi az RSA kriptorendszert”, szívdobogtatást adott a kriptográfusoknak. Igazuk van aggódni?
Mi az RSA titkosítás?
A Rivest-Shamir-Adleman (RSA) titkosítási rendszer megoldotta az adatok titkosításának problémáját, hogy azokat csak a címzett tudja visszafejteni. 1977-ben a társ-alkotók –Ron Rivest, Adi Shamir, és Leonard Adleman– javasolta elegáns megoldás a titkosítási kulcsok újszerű használatán alapul. Egyszerűen fogalmazva: a titkosítási kulcsok nagyon nagy értékek, amelyeket a matematikai folyamatokban használnak, és amelyeket az adatok titkosításához alkalmaznak. Az áttörést, amelyet az RSA a kriptográfia világába hozott, a használata volt magán és nyilvános kulcsok.
Azt is meg kell említenünk Clifford kakasok, az Egyesült Királyság vezető matematikusa Kormányzati kommunikációs központ (GCHQ), aki 1973-ban a nyilvános és a magánkulcs titkosítását / visszafejtését alkalmazta a rejtjelezéshez. Az információkat titkosították és titokban maradtak. Csak 1997-ben oldották fel a titkosítást. A nagy elmék nyilvánvalóan hasonlóan gondolkodnak.
A nyilvános kulcs / privát kulcs szekvencia a kívánt címzett nyilvános kulcsának megszerzése, és a titkosítással együtt a titkos kulccsal történő felhasználása. Ezután a címzett visszafejtheti az adatokat a magánkulcsával és az Ön nyilvános kulcsával. A nyilvános kulcsokat biztonságosan nyilvánosságra lehet hozni, a magánkulcsokat pedig biztonságosan titokban tartják. Mivel a címzettnek nem kell embernek lennie, bármely rendszer, szolgáltatás vagy eszköz, amely nyilvános kulcsát tanúsított, hitelesített módon ismertté teszi, használhatja az RSA titkosítást. Ez lehetővé teszi a rendszerek közötti kommunikáció titkosítását.
A nyilvános kulcs tanúsítvány a nyilvános kulcs tulajdonosának személyazonosságának igazolására szolgál. Két általános példa a nyilvános kulcsú tanúsítványokra Biztonságos Socket Layer és Szállítási réteg tanúsítványok (SSL / TLS). A nyilvános kulcsok továbbíthatók a kommunikálni akaró emberek között, vagy lekérhetők olyan kulcsszerverekről, mint a OpenPGP kulcsszerver.
Biztonságos héj (SSH), OpenPGP, S / MIME, és az SSL / TSL mind RSA titkosítást használ, és minden böngésző használja. Néhány kriptovaluta használja. Gyakorlatilag az egész elektronikus kereskedelem világa ilyen vagy olyan módon függ az RSA-tól. Mindent alaposan meg kell vizsgálni, ami veszélyezteti az RSA kriptorendszer integritását.
ÖSSZEFÜGGŐ: Az OpenPGP titkosítás használata a Thunderbird e-mailjeihez
Az RSA kriptográfiát fenyegető veszélyek
A titkosítási algoritmusok központi eleme az visszafordíthatatlanság. Az adatokon végrehajtott matematikai transzformációknak minden gyakorlati célból visszafordíthatatlannak kell lenniük.
Az RSA séma nagyon nagy számokat használ, amelyek két nagy prímszám szorzásának szorzata. Két prímszám felvétele és összeszorozása triviális és számítási szempontból olcsó. A művelet végrehajtásához nem kell sok feldolgozási erő vagy idő. Ám ha átadják a kapott terméket, és előzetes ismeretek nélkül megpróbálják – faktorálás útján – kideríteni, melyik két prímszámot használták, az az számítási szempontból drága.
A faktoring nagyon gyorsan megnehezül, mivel a számok egyre nagyobbak lesznek. Ilyen tiltó időbe telik – egyes becslések futnak billió év– az ilyen típusú titkosítás feltörése. Ez biztonságos ál-irreverzibilitást biztosít. Ez nem igazán visszafordíthatatlan, de annyi időbe telik, míg valóban visszafordíthatatlan lehet.
Megjelenése kvantumszámítás fenyegetést jelent az ilyen típusú titkosításra. A kvantumszámítógépek azt ígérik, hogy rendkívül rövid idő alatt képesek elvégezni a két prímszám meghatározásához szükséges egész számot. Azt jósolják, hogy egy kvantum számítógép, amelynek származéka fut Shor algoritmusa elfogadhatóan rövid időn belül képes lenne megtalálni a prímszámokat – talán akár órákon belül is.
Várható hogy 25 évig tartson vagy annál több, mielőtt létezik egy erre képes kvantum számítógép. Ez jó lehet néhány most titkosított információ esetében – az információk hasznossága ekkorra már lejárhatott. De néhányat, amit most titkosítanak, 25 (vagy akár több) év múlva is védeni kell és titokban kell tartani. Például néhány kormányzati és biztonsági kommunikáció akkor is érzékeny lesz.
Az RSA végrehajtásának hibái a múltban problémákat okoztak. Az elméleti RSA-t működőképes szoftver-implementációvá kell alakítani, mielőtt hasznos lehet – és az összetett szoftver gyakran tartalmaz hibákat. Az RSA kriptoszisztémában használt algoritmusok módosultak és helyettesítettek, mivel hibákat találtak a megvalósításokban. A régi verziókat elavulták és felváltották az új verziók.
Állítások szerint a hátsó ajtókat az RSA algoritmusaiba vezették be a nemzetbiztonsági ügynökségek kényszere vagy együttműködésük miatt. Ezeket a vádakat soha nem bizonyították be, de olyan hibákat, amelyek hatékonyan szolgáltatták a hátsó ajtókat megtalálták és ezt követően megszólították.
Mi az új veszély?
Egyetemi tanár Claus Peter Schnorr nyugdíjas matematikus és kriptográfus. A Matematika és Számítástudományi Tanszék professzora volt Johann Wolfgang Goethe Egyetem Frankfurt am Mainban.
Schnorr (előnyomtatás azt jelenti, hogy késői fejlesztés alatt áll, de még nincsenek szakértői vélemények) javasolja a új módszer a primer egész számok faktorálásához a mai számítástechnikai platformokon nagy sebességgel. A cikk címe: „SVP algoritmusok Fast Factoring Integers”. Az SVP a legrövidebb vektor probléma. Az absztrakt a „Ez elpusztítja az RSA kriptorendszert” provokatív mondattal zárul.
Azáltal, hogy egy nagyon bonyolult munkát egyszerű állításba sűrít, ez a tényező nagyságrenddel történő javulást jelent a faktoring sebességében. A sebességnövekedést Schnorr néhány korábbi munkájának finomításával lehetne elérni. Nyilvánvaló, hogy a faktoring egész számának forradalmi csökkenése jelentős hatással lenne az RSA kriptoszisztémára. Vagyis, ha az elméleti cikk tényszerűen helyes, és ha egy gyakorlati megvalósítás ki tudja igazolni a hipotézist.
A cikk az úgynevezett matematikai struktúrák felhasználásával népszerűsíti a faktoring módszert rácsok. Schnorr professzor széles körben elismert szakértő ezen a területen és annak alkalmazásában a kriptográfiában. A lap azt állítja, hogy az új technika drámai módon gyorsabb, mint a Általános számmező szita (GNFS) algoritmus, amelyet a leggyorsabb áramlási technikának tekintenek a nagy számok faktorálásához.
A fenyegetés elemzése
Schorr írása elméleti jellegű. Nincsenek időzítések vagy eredmények a megvalósításokból. Az elméleti sebességnövekedés a GNFS-hez képest papíron lenyűgözően hangzik, de vajon az elmélet és a matematika ellenáll-e azoknak az ellenőrzésnek, akik valóban értenek ehhez az érdemi kommentáláshoz szükséges szinten?
Dr. Léo Ducas kutatója a titkosítási csoport a Centrum Wiskunde és Informatika (CWI). A CWI a holland matematika és informatika nemzeti kutatóintézete. Ducas Ph.D. címet szerzett. 2013-ban a „Rácsalapú aláírások: támadások, elemzés és optimalizálás” témában. Pályafutása során rácsokkal dolgozott. Ő is kriptográfus, így kiválóan képes átnézni Schnorr dolgozatát.
Még jobb a céljainkhoz, Dr. Léo Ducas programozó. Ha szeretne kanyarodni a Cryptrisnél, az övé aszimmetrikus kriptográfiai játék, tessék. Tudományos forráskódja szétszórt GitHub. Egy része benne ül saját adattára, míg sokkal több más, többszerzős projektek tárházaiban lakik, amelyeken dolgozott.
Felülvizsgálta és elemezte Schnorr cikkét. Létrehozta Schnorr algoritmusainak megvalósítását a SageMath forgatókönyv. Ő nevezte el SchnorrGate. Ducas rámutat a titkosítás StackExchange. Ez egy olyan hibát vizsgál meg a papír egyik képletében, amely nyomtatott formában nagyon pontatlan eredményeket produkál. Ezzel a képlettel korrigálva Schnorr faktoring-módszere működik, de sokkal lassabban, mint ahogyan azt előre megjósolja.
Ducas SageMath tesztjeiből származó megállapításai ezt megerősítik. Illusztrálják, hogy Schnorr faktoring algoritmusai működnek, de sokkal lassabban, mint a ma már elérhető legjobb módszerek.
Mindannyian újra lélegezhetünk
Az RSA még egy napot titkosít. De mi lett volna, ha a lap állításai igaznak bizonyulnak? Nos, a káosz, kezdetben, majd egy új kriptorendszer elfogadása.
Talán a Elliptikus görbe rejtjelezés (ECC) megérkezett volna.
