Problém faktorizácie v asymetrickej kryptografie alebo naozaj sa ron mýlil?

Bc. Ján Kotrády

Abstrakt

Faktorizovanie verejného modulu kryptografického systému RSA sa pred niekoľkými rokmi ukazovalo ako neriešiteľný problém, avšak v roku 2012 Lenstra a kol. poukázali na určité možnosti faktorizácie verejných modulov algoritmom najväčšieho spoločného deliteľa, spôsobené chybou v generátoroch náhodných čísel. Aj niekoľko rokov po objavení tohto problému je možnosť faktorizácie verejných modulov algoritmom najväčšieho spoločného deliteľa stále aktuálna a problém ako taký nie je v širšom zmysle stále vyriešený. Z pomerne malej množiny verejných modulov, ide o približne 1,2 milióna, sme boli schopní faktorizovať 65 verejných modulov o dĺžke minimálne 1024 bitov, čo predstavuje stále reálne riziko bezpečnosti informačných systémoch. Podarilo sa nám pritom faktorizovať niekoľko verejných modulov z protokolu SSH, dokonca aj z protokolu SSL a ukazuje sa, že PGP servery obsahujú pomerne vysoké množstvo chybne generovaných modulov z hľadiska dĺžky prvočísel. V práci sa venujeme spôsobu získavania dát, efektívnemu algoritmu výpočtu najväčšieho spoločného deliteľa, ale hlavne výsledkom výskumu faktorizácie, ktorý bol realizovaný na vzorke približne 1,2 milióna verejných modulusov. Ďalej sme skúmali vzťahy medzi jednotlivými faktorizovanými verejnými modulmi a pritom sme poukázali na vzťah medzi faktorizovanými verejnými modulmi a zariadeniami, ktoré tento chybný modul obsahujú, ako aj na ich spoločné vlastnosti a špecifikácie. Zisťovali sme taktiež aj vzťah medzi vlastníctvom zariadení, respektíve vlastníctvo IP adries týchto zariadení, ktoré boli faktorizované a faktorizovanými verejnými modulmi, pričom sme dospeli k záveru, ktorý nám len potvrdzuje doterajšie dohady ohľadne problému faktorizácie algoritmom najväčšieho spoločného deliteľa. Zároveň sme sa snažili zodpovedať na otázku, či sa naozaj Ron Riverst so svojím kryptografickým systémom RSA mýlil. Naším výskumom sme poukázali na fakt, že problém faktorizácie algoritmom najväčšieho spoločného deliteľa v kryptografickom systéme RSA je stále veľkým bezpečnostným rizikom informačných systémov.