it-swarm-eu.dev

Jak odhadnout čas potřebný k rozbití RSA šifrování?

Jak odhadnout čas potřebný k rozbití RSA šifrování? Mám na mysli čas potřebný k roztržení šifrování Rsa s délkou klíče 1024, 2048, 3072, 4096, 5120, 6144, 5120, 7168, 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360 a 16384?

67
Predator

Souhrn klíčových odhadů síly používaných různými vědci a organizacemi viz tento web .

Vaše „512 bitů ve 12μs“ je naprosto falešná. Uvidíme, odkud to pochází. 1999 byl rokem, kdy byla provedena první 512bitová obecná faktorizace, na výzvu zveřejněnou společností RSA (společnost) a nazvanou RSA-155 (protože číslo sestávalo ze 155 desetinných míst - v binárních číslech) , délka je 512 bitů). Tato faktorizace trvalo 6 měsíců. Na akce Eurocrypt uspořádané ve stejném roce (v květnu; v té době začalo 512bitové úsilí o faktorizaci, ale ještě nebylo dokončeno), Adi Shamir , od Weizmanna Institut, představil teoretické zařízení zvané ZÁBLESK , které, jak se zdá, může trochu pomoci ve snaze o faktorizaci. Měl by spočívat v obrovském počtu diod blikajících na pečlivě zvolených frekvencích v jakési černé zkumavce. Shamir přinesl vlastní zařízení, které z 10 metrů vypadalo jako kávovar. Požádal lidi, aby zhasli světlo, aby se účastník Eurocrypt mohl divit při čtyři červené diody blikající při inverzních hodnotách 2, 3, 5 a 7 sekund. Ooh! a Aah! oni šli, ačkoli skutečný stroj, by to byl postaven, by vyžadovalo několik milionů diod a frekvencí v 10 nebo 100 gigahertz. Myšlenka je tedy zábavná (přinejmenším pro výzkumníky v kryptologii, o nichž je známo, že mají zvláštní smysl pro humor), ale ještě nepřekročila krok teoretického náčrtu. Shamir je skvělý showman.

TWINKLE je však pouze „nápověda“. Nejznámější faktorizační algoritmus se nazývá General Number Field Sieve ; dva následující algoritmy jsou kvadratické síto a metoda eliptické křivky . 512bitové číslo je mimo dosah QS a ECM s dnešní technologií a a fortiori s technologií z roku 1999. GNFS je velmi složitý (matematicky vzato), zejména proto, že vyžaduje pečlivý výběr některých kritických parametrů ("výběr polynomu"). Proto musí být počáteční úsilí velmi inteligentních mozků (u velkých počítačů, ale mozky jsou zde nejdůležitější). Poté se GNFS skládá ze dvou částí, síto a lineární redukce. Síto může být vyrobeno paralelně na stovkách nebo tisících strojích, které musí být stále relativně velké (v RAM), ale je to možné. Lineární redukce zahrnuje výpočet věcí s maticí, která je příliš velká na to, aby se vešla do počítače (o několik řádů, i když předpokládáme, že uvedený počítač má terabajty rychlé RAM). Existují algoritmy, které udržují matici (což je poměrně řídké) v komprimovaném formátu a stále na tom mohou spočítat, ale je to těžké. Při 512bitové faktorizaci trvalo prosévání asi 80% celkového času, ale u větších čísel je úzkým hrdlem lineární redukce.

TWINKLE je pouze o urychlení prosévací části. O lineární redukci nic nedělá. Jinými slovy, urychluje část, která je snadná (relativně řečeno). Ani TWINKLE-zesílená prosévací polovina by nebyla nikde poblíž 12μs. Místo toho by to spíše pomohlo snížit čtyřměsíční úsilí o prosévání, řekněme, na tři týdny. Což je vědecky dobré, ale ne rekordér, zejména proto, že u větších velikostí dominuje lineární redukce. Zdá se, že číslo 12μs pochází ze záměny s ještě mytičtějším zvířetem Quantum Computer , což by mohlo snadno ovlivnit velká čísla, pokud by bylo možné vybudovat QC s 512 „qubits“. D-Wave nedávno ohlásil kvantový počítač se 128 qubity, ale ukázalo se, že se nejednalo o „skutečné“ qubity a že jsou pro faktorizaci nevhodné (stále mohou teoreticky provádět některé efektivní aproximace v optimalizačních problémech, což je skvělé ale v zásadě se nevztahuje na kryptografii, protože kryptografické algoritmy nelze přiblížit aproximacím - jsou navrženy tak, aby se jedna špatná bitka otřásla celou věcí). Nejlepší „skutečnou“ QC se zatím jeví prototyp společnosti IBM s, pokud si vzpomínám, má 5 qubits, což jí umožňuje stanovit, že 15 se rovná 3krát 5.

Aktuální záznam faktorizace RSA je pro 768-bitové celé číslo , oznámeno v prosinci 2009. Trvalo to čtyři roky a zapojili se nejchytřejší teoretici čísel, kteří v současné době žijí na Zemi, včetně Lenstra a Montgomeryho, kteří mají poněkud božského jako je stav v těchto kruzích. Nedávno jsem se dozvěděl, že se začal výběr parametrů pro 1024-bitovou faktorizaci čísel (to je část "brainy"); prosévání je technicky proveditelné (bude to drahé a bude vyžadovat roky výpočtu na mnoha univerzitních klastrech), ale prozatím nikdo neví, jak provést lineární redukční část pro 1024bitové celé číslo. Neočekávejte tedy 1024bitovou přestávku v dohledné době.

Právě teď může specializovaný amatér, který používá publikovaný kód (např. Msieve ), dosáhnout 512bitové faktorizace, pokud má přístup k výkonným počítačům (několik desítek velkých PC a alespoň jedno hodiny plné rychlé paměti RAM) ) a několik měsíců volného času; v zásadě „oddaný amatér“ znamená „znuděný student informatiky na bohaté univerzitě“. Cokoli nad 512 bitů je mimo dosah amatérky.

Shrnutí: ve vašem kódu, můžete vrátit "prakticky nekonečný" jako krakovací čas pro všechny délky klíčů. Typický uživatel nerozbije 1024bitový klíč RSA, nyní ani ne za deset let. Na Zemi je asi tucet lidí, kteří mohou s jakoukoli důvěryhodností tvrdit, že je myslitelné, s nízkou, ale nenulovou pravděpodobností, že možná budou schopny faktorovat jednu 1024- bit celé číslo v blíže neurčené době před rokem 2020.

(Je však velmi snadné implementovat implementaci RSA nebo jakékoli aplikace pomocí RSA tak, aby jakákoli důvěrná data, která drží, mohla být obnovena bez obtěžování klíčem RSA. Pokud používáte 1024bitové klíče RSA, můžete si být jisti, že když bude vaše aplikace napadena, nebude to prostřednictvím faktorizace pomocí klíče RSA.)

90
Thomas Pornin

Krátká odpověď : Nejjednodušší metodou by bylo použití věta prvočísla , ale uvědomte si, že je to aproximace. Odhadněte, jak dlouho by vám trvalo vyzkoušet každý z těchto prvočísel; doba za prvočíslo * počet prvočísel vám dává celkový čas. Tím získáte odhad pro hledání brutální síly.

Můžete také použít odhad doby běhu pro kvadratické síto nebo sítko pro obecné číslo pole . To vám poskytne odhady pro algoritmy factoringu, které skutečně používají lidé porušující čísla RSA.

Dlouhé pozadí :

Časová teorie čísel!

Nejprve se podívejme na velikost čísel, o kterých mluvíte. Při 2 ^ 3 = 8, což je 1 000 binárně, můžeme vidět, že se jedná o čtyřbitové číslo, minimální takové, jaké je možné. Takže 2 ^ 2 = 4 je 3-bitové číslo (100). Takže pro dané x je minimální možná hodnota, aby bylo zajištěno, že máme dost bitů, 2 ^ (x-1). 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328. To je velikost čísla máte co do činění se tady, to znamená, že velikost n, které mají být zapracovány.

Další velkou otázkou je, jak je n konstruováno? n=pq, Jak víte z definice RSA, takže hledáte dva prvočísla jako faktory tohoto čísla. Otázkou pak je, jak zjistíme, že číslo je prvořadé a můžeme je spočítat?

Podle definice je tedy číslo neredukovatelné, pokud pro libovolné číslo x menší než to, \gcd(p, x) = 1 s výjimkou x=1. V tom však můžeme zlepšit. Měli byste si poměrně rychle uvědomit, že u jakéhokoli čísla je buď prvotřídní, nebo ne. Pokud to není prvočíslo, pak gcd a alespoň jedno prvočíslo musí být větší než 1 (jinak by to bylo prvočíslo). Z toho usoudíme, že každé nepřiměřené celé číslo musí být dělitelné množinou prvočísel. Formální matematický důkaz není ve skutečnosti takovým skokem odtud.

Tomu se říká základní věta o aritemice a mírně zjednodušuje záležitosti. Takže teď, když pracujeme na tom, zda je číslo prvořadé, už nemusíme zkoušet každé číslo, pouze čísla, o kterých víme, že jsou prvořadá!

To je zjevně stále velmi pomalé, takže si udělejme další pozorování - vzhledem k tomu, že se faktory vyskytují ve dvojicích, spodní z těchto dvou čísel je nanejvýš druhou odmocninou čísla. Pokud jsme omezeni na N (množina přirozených čísel), představuje horní hranici na nejvyšší možné hodnotě, kterou musíme zkontrolovat. Takže teď, pro libovolné číslo N, musíme hledat každé celé číslo začínající od 2 a směřující k sqrt (N) pro každé číslo, které v tomto seznamu určíme jako nejlepší. Pak můžeme, pokud najdeme prvočíslo, odvodit, zda to ovlivňuje samotný N. Nebudu odhadovat dobu běhu toho, protože nepochybně řeknu špatnou věc, ale bude to trvat dlouho.

Nyní vidíte sílu RSA. Vyberte si velmi velkou připravku a skončíte dlouhou cestou. Za současného stavu musíme začít od 2, což je jasně hrozné.

Testování primality si klade za cíl zlepšit to pomocí různých technik. Naivní metoda je ta, kterou jsme právě probrali. Myslím, že podrobná diskuse o těchto technikách je pro Math pravděpodobně vhodnější, takže to shrnu: všechny runtimes jsou nesmyslné a použití tohoto jako způsobu, jak spočítat prvočísla, by bylo hrozné.

Takže nemůžeme spolehlivě spočítat počet prvočísel, než je počet, aniž bychom brali navždy, protože je to skutečně analogické celočíselné faktorizaci. A co funkce, která nějak počítá, připravuje se jiným způsobem?

Zadejte \pi(n) = \frac{n}{\log(n) - 1.08366}, jeden pokus o Prime Number Theorem aproximace počtu prvočísel. Je to však přesně tak; cílem takové funkce je přesně spočítat počet prvočísel, ale v současné době vám dává pouze odhad. Pro vaše účely by to mohlo být považováno za dost dobré.

Je to však stále ještě aproximace. Podívejte se na zbytek článku. Mimo jiné jsou další odhady závislé na hypotéze Riemanna.

Dobře, co tedy celočíselná faktorizace ? Druhá nejlepší dosavadní metoda se nazývá Kvadratické síto a nejlepší se nazývá síto obecného pole . Obě tyto metody se dotýkají docela pokročilých matematik; za předpokladu, že to myslíš vážně s faktoringovými prvočíslami, které bych si o nich mohl přečíst. Určitě byste měli být schopni použít odhady pro obojí jako vylepšení používání věty prvočísel, protože pokud se chystáte činit velké prvočísla, budete je chtít používat a ne hledání brutální síly.

Ale chci vědět o kvantu?

Dobře, dost fér. Celočíselnou faktorizaci na kvantovém počítači lze provést v směšně krátkém množství času za předpokladu, že budeme schopni implementovat Shorův algoritmus . Měl bych zdůraznit, že to vyžaduje kvantový počítač. Pokud vím, vývoj kvantových počítačů v měřítku, které mohou rozbít RSA, je v současné době daleko. Viz vývoj kvantových výpočtů .

V každém případě by Shorův algoritmus byl exponenciálně rychlejší. Na této stránce je uveden odhad doby běhu, kterou můžete do svých odhadů zahrnout.

25
user2213

Další možností je vytvořit velkou databázi možných klíčů a použít ji jako vyhledávací tabulku. Očividně nepotřebujete VŠECHNY prvočísla, jen pár vás provede velkým procentem internetového provozu.

Zdroj: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

0
Evgeny