Algoritmy pro faktorizaci RSA modulů sdílejících prvočíslo

20.2.2012 23:56 | Přečteno: 2420× | programování | | poslední úprava: 21.2.2012 01:28

Po publikaci Lenstra et al. o RSA modulech sdílejích prvočíslo se dlouho diskutovalo jak to skutečně udělali, protože jejich paper o tom taktně mlčí. Ukážu několik algoritmů a časové odhady.

Benchmark GCD, počty klíčů podle velikosti modulů

Na notebooku (Core i5-2520M) s obyčeným pythoním gmpy (wrapper GMP) dostávám 170794 GCD za sekundu na 1024-4096 bit RSA modulech. Lenstra testoval 4.7 miliona 1024-bit modulů a 6.4 modulů celkově. V mé denně updatované databázi se nachází 1424938 unikátních RSA modulů, které se dělí podle velikosti modulu následovně (pár ostatních s jinými velikosti vynechávám):

 rsa_bits |  count
----------+--------
     4096 |  22367
     1024 | 491356
     2048 | 908103

Triviální algoritmus

Nejjednodušší je prostě udělat GCD každého modulu s každým jiným, což dává složitost O(N²). Rychlost operace GCD se schová do nějaké konstanty, protože velikost modulů je shora omezena. Pro uvedený notebook by to znamenalo 4.1 let na otestování na 4.7M modulů nebo 7.6 let pro otestování 6.4M modulů.

Trochu lepší algoritmus - zgrupujeme klíče podle velikosti modulu

Místo testování každého modulu s každým, budeme testovat jenom ty se stejným modulem, protože moduly s různě velkými moduly téměř jistě nebudou sdílet prvočíslo. Kvůli kvadratické složitosti to dost pomůže proti "triviálnímu" algoritmu. Třeba pro otestování všech klíčů z mé DB by časy byly:

 rsa_bits |  čas
----------+--------
     4096 | 50 min
     1024 | 17 dní
     2048 | 56 dní

Probabilistický algoritmus

Místo testovaní všech klíčů se můžeme spokojit třeba s nalezením jenom P=50% z nich. Tím by šlo algoritmus ještě více urychlit. Podle výsledků Lenstru je 0.2% klíčů sdílejích prvočísla. Oříšek je zde v tom, že existuje 1995 skupin, které navíc nejsou uniformně rozloženy. Když si trocha zjednodušíme předpoklady, šlo by se dopočítat k očekávanému počtu testů.

Např. jaký je očekáváný počet GCD testů, pokud budeme předpokládat že slabé klíče jsou uniformně rozloženy v těch 1995 skupinách? Kolik by to bylo, kdybychom předpokládali existenci jenom jedné skupiny? Kdyby se to někomu chtělo spočítat, ocenil bych to, teď si mi to už počítat nechce . Ten případ s jednou skupinou by měl být celkem snadno spočítatelný.

Algebraické triky

Možná existují další algebraické triky jak ještě víc omezit počet modulů k testování. Při kvadratické náročnosti vzhledem k počtu modulů by to mohlo ještě značně urychlit. Možná když budu mít chvíli času, tak si osvěžím z Koblitze jestli to lze algebraicky znásilnit ještě víc. Ale neodmítnu jestli se někdo podělí o nápad

Update: vítězný algebraický trik který dává lineární složitost

Vychází z algoritmu, který publikoval Dan Bernstein v Journal of Algorithms. Je založen na triku jak naráz spočítat GCD modulu N₁ se všema ostatníma:

gcd(N₁,N₂…N_m) = gcd(N₁, (N₁*N₂*…*N_m mod N₁²)/N₁)

Závěrem

Z odhadů je vidět, že i s takto jednoduchými algoritmy to lze na nějakém mírně lepším clusteru nebo FPGA "vydrtit" v celkem rozumném čase. Používat GPU na GCD jsem taky nezkoušel. S lineárním algoritmem to dá běžné PC za pár hodin.

       

Komentáře

[rastos]

To čo by bolo veľmi zaujímavé, je informácia o tom, ako vytiahnuť modul z mojich kľúčov - teda z PGP/GPG kľúčov a SSL certifikátov - a malý program, ktorý by povedal z koľkými kľúčmi z publikovanej DB kľúčov zdieľam RSA modul.

Ale inak vďaka za ten blogpost.

[limit_false]

Lze udělat blacklist klíčů podobně jako u těch slabých debianích klíčů. Problém je v tom, že takto nelze otestovat všechny klíče. Možnosti jsou pak dvě:

1. veřejná služba, kde uživatel pošle veřejný RSA klíč, který musí být podepsán privátním (aby to nešlo jednoduše použít jako orákulum)
2. homomorfní šifrování, což je pěkný koncept, ale velmi nepraktický z hlediska nároků na místo a výkon

Extrakce modulu: viz "openssl rsa" a "openssl pkcs8" příkazy.

[Josef Kufner]

Podepisovat veřejný klíč privátním ze stejného páru není moc dobrý nápad.

[Filip Jirsák]

Proč ne? Dělá se to třeba v každé žádosti o certifikát.

[limit_false]

Tam zavisi od milionu veci. Treba nutnost paddingu a hashovat jako prvni pozadavek. Jinak i tak kvuli blbe implementaci pri malem verejnem exponentu (napr. 3) lze z 3 podpisu ziskat klic. Tusim se to vola message extension attack (nekde mam i paper). Zduraznuji, ze je to chyba implementace, ne algoritmu (mam v planu to v par softech hledat, protoze tohle chyba kterou je velmi lehke udelat).

Zbytek je jenom delsi "rant" okolo soucasne situace:

Jako vubec kazdy crypto protokol musi prohlednout mnoho lidi, i kdyby ho navrhoval sam Schneier. Viz fiasko s WEP. Kdyby prasklo nejake jine RFC jehoz jsem autorem kvuli podobne blbosti, zacnu hackovat IETF servery a mazat sve jmeno z daneho RFC

Ted se vlastne z ruznych diskusi dozvidam, ze "best practices", co nedavno platili, uz neplati. Na nekterych vecech se ani veterani kryptografie nedokazou dohodnout. Budu o tom psat clanek pro root.cz, mozna tak do mesice by se mohl objevit.

"Crypto-shitstorm" strhnuvsi se v ruznych listech je dusledek tech generatoru. Nekdy mi z toho jde hlava kolem a nekdy jsem zas rad ze vim treba vic nez 1/3 lidi v ruznych otazkach (v porovani jaka lama jsem byl pred 10 lety). Jinak kolem generatoru budeme toho videt vice. Uz jsem videl implementace /dev/random, ktere jsou deterministicke by design. Horsi je, ze kdyz se programatora zeptam, kde je tam v tech 5 radcich chyba, maloktery programator se chyta.

Holt crypto je tezke a implementace crypta jeste tezsi. Je tam asi 10 "obecnich vet" a pocet specialnich pripadu lze mozna shora omezit Grahamovym cislem.

Taky by me zajimalo, jestli se nekdo nekdy dopatra pravdy o tomhle generatoru: Dual EC DRBG. Je dokazano, ze existuje sada bodu na te elipticke krivce a kdo je zna, muze vypocitat stav generatoru (plus "podivny bug" se statistickou distribuci bitu). Bohuzel nalezeni ekvivalentni (EC)DLP, takze mozna se nikdy nedovime. Ten generator se pouziva ve Windows (vyborna analyza RNG/PRNG). Po blamazi s NSAKEY to muze znamenat cokoli.

Chtel jsem tim rict, ze velmi pravdepodobne existuji utocnici typu NSA znajici backdoory v random generatorech a buhvicem a schopni primo napadnout, tresnu, 10-20% kompu otevrenych do netu primo s relativne nizkymi naklady (a zbytek pak odtud). Se znalosti vnitrnosti generatoru jako ten s tim entropy bugem se na dejme tomu 3-5% dostane bezny "crypto-smrtelnik". (Abychom nevypadal jako paranoik sam, zminil to i jeden z tech veteranu a ti si skutecne davaji pozor aby nezneli paranoidne, i kdyz z definice prace paranoidni byt musi ).

Jsem jenom zvedav, co se stane az nadpolovicni cast kryptologu nastvou s neustalym pretlacenim zrud jako COICA/SOPA/PIPA/ACTA/PCIP, protoze uz ted jsou kvuli tomu dost nastvani. "Taky mensi Armageddon" neni vyloucen: "Cracking SCADA...done. Corollary: life deleted."

[rastos]

Mhm. Ty tuším budeš zaujímavý človek. Budem si ťa musieť viacej všímať Prezradíš mi, čo máš vyštudované?

[limit_false]

MFF UK. Ale u crypto platí, že co bylo před rokem "best practice", už může být považováno za nedoporučené, nebo dokonce nebezpečné. Tudíž je nutné neustále sledovat nové publikace.

[polymorf]

Ok, takze zistite ze Jozef Novak z Podebrad a Parn Gupta z Kathmandu na routeri zdielaju rovnaky privatny kluc. Co s tym?

[rastos]

Keďže Jozef Novák z Poděbrad je podozrivý z podporovania terorizmu sťahovaním nelegálnych empétrojek, je nutné navštíviť Parna Guptu z Kathmandu, a získať jeho kľúč výmenou za tabuľku čokolády, čím sa umožní úplná kontrola nad sieťovou prevádzkou Jozefa Nováka z Poděbrad.

Nie. Robím si srandu. V skutočnosti je to tak, že okrem toho, že sa dozvieš, že zdieľajú rovnaký kľúč, tak sa aj dozvieš aj aký ten privátny kľúč je. A do Kathmandu nemusíš. Skrátka je to spôsob "faktorizácie", ktorá sa nerobí hrubou silou, ale hľadaním, či obeť náhodou používa kľúč, z nejakej malej množiny.

[Ivan]

Jozef Novak poziva pro svuj priv klic N1 dve prvocisla. N1 := ( p * q ). Gupta pouziva privatni klic N2 := ( p * r ). Tzn. shodou okolnosti si oba hodili nahodnym generatorem a padlo jim stejne "nahodne" prvocislo "p". Takze pouzijes eukliduv algoritmus a zjistis nejvetsiho spolecneho delitele(N1, N2) a tim je prave "p". Tim se ti podarilo faktorizovat oba privatni klice.

[Marcel Šebek]

Ten algebraický trik se mi moc nezdá, nebude tam náhodou GCD ukrytý v tom modulárním násobení?

[limit_false]

Ten algoritmus od DJB je skutečně šílený. Pro ilustraci zmíním, že byl navrhnut v 1995, správnost a složitost algoritmu byla dokázána až v 2004. BTW není "úplně lineární", ale "téměř lineární", složitost O(n^1+o(1)) vzhledem k počtu n bitů všech modulů). Některé části je jednodušší "vydrtit" nežli je kódit.

[JS]

A je nekde nejaky popis?

[limit_false]

http://cr.yp.to/lineartime/dcba-20040404.pdf

Doporucuji moc nejist pred prvnim ctenim, zveda se z toho algoritmu dost zaludek

[Bystroushaak]

>o< - ASCII bonbon za kvalitní blogpost :)

[Řepa]

Škoda té angločeštiny, kazí to estetický požitek z čtení.

Ale jinak zajímavé téma.

[limit_false]

Are you fucking kidding me?

Bavíme se zde o mozko-ničící složitosti a algebře, to už můžete jít rovnout vyfuckovat Bernsteina za jeho Noetherian coids a jiné "jazykové" úchylnosti (které jsou úchylné i v angličtině).

A není to "angločeština", je to spíš "latin-*".

[Řepa]

Hádat se nechci. Jen jsem uvedl svůj názor čtenáře.

Jinak NSD se snad povinně učí na středních školách a většina ostatních věcí stejně byla uvedena jen jako fakt („že lineární algoritmus existuje atp.“), takže čtenář ani nemá co se snažit pochopit.

[limit_false]

OK sorry za prehnanou reakci. Je to tim, ze v posledne dobe je pod kazdym clankem nejaky grammar nazi. Pod temer kazdym clankem i na lupa.cz, root.cz, mne se objevuji... Kdyz uz neco podobneho ("prilis mnoho anglickych terminu") vytykali veteranovi jako Jiri Peterka, tak jsem cumel a zacal penit.

Ja tak proste mluvim a fakt me nikdo nedonuti psat jinak (nakonec, je to blog). Proste vybiram efektivnejsi slova (Thaicinu a Nepalstinu treba moc casto nevyuziju, ale EN/DE/LAT/GR pravidelne).

Jinak NSD se snad povinně učí na středních školách a většina ostatních věcí stejně byla uvedena jen jako fakt („že lineární algoritmus existuje atp.“), takže čtenář ani nemá co se snažit pochopit.

Ano, kdyz to dostanou takto naservirovano (vsechno jiz pochopeno je jednoduche). NSD se sice uci, ale zvlastni je, ze kazdemu z cca 10-15 lidi jsem to musel vysvetlovat osobne jak to funguje, i kdyz je to trivialni (proste si nedocvakly ty dva-tri fakty). Proto jsem psal ten clanek.

Tvrzeni "ctenar ani nema co pochopit" je asi jako dostat reseni na instanci NP-uplneho problemu a reknout "vzdyt to je jednoduche" kvuli tomu ze reseni je zverejneno a nerict nic o narocnosti nalezani reseni.

BTW zpusobu pro GCD je spousta. Tim Euklidovym byste daleko nedosel. Samotny Bernstein je v zasade "mega-GCD-na-steroidech". Ale to nema cenu vysvetlovat, viz paper: http://cr.yp.to/lineartime/dcba-20040404.pdf Preji vesele a stastne grcani pri cteni.

Taky nebudu vykladat jake triky jsem skutecne pouzil, nebo nedejboze davat sem kod pro script kiddies (napr. kazdemu algebraikovi musi prijit ta dlouha GCD rovnice podivna, jsou tam zbytecne veci navic). Tudiz evidentne algebraik nejste.

Stejne ste IMHO jenom stoural. Hadat se nechci, jenom jsem uvedl nazor autora (vidite ted, jaka je to dementni argumentace?) Omluva prijde az od vas uvidim implementaci toho Bernsteinova algoritmu. Pak taky muzete napsat stokrat lepsi clanek o te implementaci.

There's no royal road to crypto.

[jas]

Nechce sa vam vyskusat O(n*log n) algoritmus zalozeny na tom, ze gcd(a,b,c,d) = gcd(gcd(a,b), gcd(c,d)) ? S ohladom na jednoduchost by v realite mohol dosahovat celkom dobre vysledky. Obvzlast ak sa berie do uvahy postupne zjednodusovanie vypoctu gcd vo vrstvach log n.

Implementacia v pythone asi nejak takto (pripadne pridat nejake optimalizacie ako lepsiu kniznicu pre gcd (ak je) a pod.):

from fractions import gcd

def wgcd(d, u):
  if u - d == 1:
    return a[d]
  elif u - d == 2:
    return gcd(a[d], a[d+1])
  else:
    return gcd(wgcd(d, d + (u - d)/2), wgcd(d + (u - d)/2, u))

a = [17*(x*2) for x in range(150000)]
print(wgcd(0, len(a)))

[jas]

Hm, ked tak rozmyslam, tak ta zlozitost sa pravdepodobne zmesti aj do O(n).

[limit_false]

Ta rovnice gcd(a,b,c,d) = gcd(gcd(a,b), gcd(c,d)) je sice pravdivá, ale řeší jiný problém. My potřebujeme gcd(a, b*c*d), gcd(b, a*c*d), gcd(c, a*b*d)...:

pro každé i=1..n: gcd(N_i, N₁ * N₂ * ... * N_i-1 * N_i+1 * ... * N_n).

Lze to podobním stromem urychlit taky, ale je to jenom jedna z částí (pořád je to daleko od "téměř-linearity").

[jas]

Konecne ta gcd rovnica z blogu zacina davat zmysel. Akosi som za gcd(N1,N2…Nm) povazoval gcd(N1,N2,N3 .. Nm) a nie gcd N1 s produktom N2 .. Nm. Vdaka za objasnenie.