Vlákno názorů k článku GPG: šifrování otevřeně a bezpečně od disorder - v navode sa vytvaraju 1024-bitovy DSA kluc, ktory uz...
-
Marian Kechlibar (neregistrovaný)
Na faktorizaci velkých čísel jsem se specializoval na MFF na doktorském studiu, takže do téhle oblasti jsem jakžtakž ponořen.
<i>Nedojde-li k výraznému posunu v oblasti algoritmů</i> (a od roku 1993, kdy bylo popsáno Number Field Sieve, v podstatě nedošlo), nemáte šanci někdy za 10 let crackovat 4096-bitové RSA moduly jen nárůstem výpočetního výkonu. Maximum, které bych reálně očekával, je 1024 bitů.
Nutno ovšem říci, že vám nikdo nezaručí, že se nějaký „dělový“ algoritmus neobjeví. Proto jsou předpovědi na 10 a více let obvykle vaření z vody.
Docela by mne zajímalo, odkud citujete toho Bruce Schneiera a jeho názor na délky klíčů. Pokud vím, Schneierův názor v tomto je, že lidé dělají z délky klíčů zbytečný fetiš a zanedbávají přitom podstatně praktičtější a realističtější ohrožení, jako je kvalitní keylogger.
-
disorder (neregistrovaný)
lenze z 1024-bitovych klucov sa prechadza uz teraz. preco si robit kluc o ktorom sa predpoklada dnes, ze dlho nevydrzi?
Applied Cryptography
Assume a dedicated cryptanalyst can get his hands on 10,000 mips-years, a
large corporation can get 107 mips-years, and that a large government can get
109 mips-years. Also assume that computing power will increase by a factor of
10 every five years. And finally, assume that advances in factoring
mathematics allow us to factor general numbers at the speeds of the special
number field sieve. (This isn't possible yet, but the breakthrough could occur
at any time.) Table 7.6 recommends different key lengths for security during
different years.
Table 7.6
Recommended Public-key Key Lengths (in bits)
Year vs. Individual vs. Corporation vs. Government
1995 768 1280 1536
2000 1024 1280 1536
2005 1280 1536 2048 -
Podívejte se pár příspěvků níže a počítejte:
Za 20 let se výpočetní kapacita možná zvětší 1000× – viz Moorův „zákon“. Dobrá, s rezervou počítejme 1000000×
Vládní instituce mají k dispozici výpočetní kapacitu, která je v nejlepším případě 10000000000× vyšší než obyčejné PC. A to nejspíš přeháním. Botnet ze všech stolních počítačů na světě by měl nanejvýš desetinu.
Pokud se nestane nic mimořádného, výpočetní kapacita vládních výpočetních center nebude za 20 let vyšší než 10000000000000000× násobek výpočetní kapacity obyčejného PC dnes.
Jenže zlomení 2048bitového klíče je 34996011596528190789960035633881941845650710894291398982812329702559247987190014771576210832368861184× složitější než zlomení 1024bitového klíče.
Za 20 let by tedy stále ještě bylo třeba 3499601159652819078996003563388194184565071089429139898281232970255924798719001477158 těch nejvýkonnějších vládních počítačů ke zlomení 2048bitové šifry.
Výpočet samozřejmě předpokládá, že nebude nalezeno slabé místo šifry.
-
Marian Kechlibar (neregistrovaný)
„teraz si predstav aky posun spravilo vyuzitie grafickych akceleratorov.“
Na to jsme si dělali ve firmě takovou malou studii … posun je lineární, čili dlouhodobě nepodstatný.
Nejlepší algoritmus pro faktorizaci velkých čísel, General Number Field Sieve, je subexponenciální složitosti (exponenciálně závisí na třetí odmocnině délky faktorizovaného čísla). Nic lepšího není na obecné RSA moduly známo.
Bohužel ne-matematici si neuvědomují, co to znamená: konkrétně, že prodloužení délky faktorizovaného čísla o 3 bity znamená nárůst komplexity algoritmu 2×.
Z hlediska laika je 2048 bitů „jenom“ 2× více než 1024 bitů… a že se v tom skrývá 2334 faktor složitosti, to jim nevysvětlíš.
Osobně dávám přednost tomuto příměru: milion má jen dvakrát víc nul než tisícovka, ale za jak dlouho ty dvě hodnoty vyděláš? Bohužel tento příměr funguje jen na lidi, co jsou ochotni myslet, což ne každý je.
