Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Whox 20. 10. 2015, 21:01:37
-
Zdravím, nedávno tady byla ve článku zmíněna bezpečnostní chyba, která zneužívala využívání malého množství prvočísel. Program na generování prvočísel si dokáže napsat asi každý na tomhle serveru, ale chtěl bych vědět, jak velké musí být prvočísla, aby byly dostatečně bezpečné, případně kolik jich musí být k dispozici. Napadá někoho, kde bych to zjistit?
Díky za odpovědi..
-
Třeba 2^57885161-1 je celkem bezpečný :D Ale ono nejde tak o to, který jsou bezpečný, ale který jsou nebezpečný. Problémem je především používání relativně malé množiny předpočítaných prvočísel.
-
http://www.jupiterbroadcasting.com/89226/national-security-breaking-agency-techsnap-236/ (http://www.jupiterbroadcasting.com/89226/national-security-breaking-agency-techsnap-236/)
Tu o tom trochu mluví, doporučuji poslechnout.
-
Podíval bych se do zdrojáku openssl (nebo nějakého čitelnějšího forku). Generuje se to pomocí
openssl dhparam -out dhparams-4096.pem 4096
-
Tak prvočísel je dost, problém je náročnost jejich nalezení. Proto se používá jen pár, navíc některé ty knihovny jsou poněkud staré a ty prvočísla tam jsou predpočtená z dob kdy jejich hledání by byl na nemalou chvíly. A nevím jak vám, ale čekat i dnes pár dní na vygenerování klíčů se asi nikomu nechce. Navíc se spoléhalo, že ikdyž se použijí ty samá prvočísla tak v algoritmu jsou používána náhodná čísla.
Problém bezpečnosti šifrování na pc bych viděl v tom, že matematicky to vše hezky sedí, ale implementačně prostě té náhody mnoho není. Zvláště u všech možných embeded zařízení, zvláště routry kdy se často k inicializaci generátoru náhodných čísel používal čas od startu, kupodivu ty samá zařízení startují obdobně rychle asi každý tuší k čemu to vede.
-
Tak prvočísel je dost, problém je náročnost jejich nalezení.
Prvočísel je nekonečně mnoho, ale to hledání je opravdu oříšek.
-
Tak prvočísel je dost, problém je náročnost jejich nalezení.
Prvočísel je nekonečně mnoho, ale to hledání je opravdu oříšek.
Je dokazano, ze mezi po sobe jdoucimi mocninami dvojky je alespon jedno. Z toho vyplyva, ze je jich nekonecne mnoho.
Jaka je jejich skutecna hustota to je vec druha. Overit, ze je neco prvocislo je vlastne stejne narocne jako faktorizace sama.
Proto se pouzivaji randomizovane algorigmy (napr. zalozene na fermatove vete). Ty ale mohou vracet i spatne vysledky, pravdepodobnost uspechu zavisi na mnozsvi invetovaneho procesoroveho casu.
-
Je dokazano, ze mezi po sobe jdoucimi mocninami dvojky je alespon jedno. Z toho vyplyva, ze je jich nekonecne mnoho.
Dokonce je dokázáno, že pro každé n > 1 existuje prvočíslo větší než n a menší než 2n, viz Bertrandův postulát.
Jaka je jejich skutecna hustota to je vec druha. Overit, ze je neco prvocislo je vlastne stejne narocne jako faktorizace sama.
Tak to opravdu není stejné. Celý princip RSA je založený na tom, že zatímco test prvočíselnosti je vcelku triviální (jde provést v čase polynomiálním s délkou zápisu čísla), tak faktorizace je těžká. Skutečná obtížnost faktorizace není známá, takže se teoreticky může ukázat, že faktorizace je tak lehká jako test prvočíselnosti, ale pokud by to tak bylo, okamžitě dojde k prolomení RSA.
Proto se pouzivaji randomizovane algorigmy (napr. zalozene na fermatove vete). Ty ale mohou vracet i spatne vysledky, pravdepodobnost uspechu zavisi na mnozsvi invetovaneho procesoroveho casu.
Ve skutečnosti existují deterministické algoritmy testující prvočíselnost fungující v asymptoticky polynomiálním čase (viz např. Lenstra and Pomerance, http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf), byť jejich konstanty jsou vysoké a jsou pomalejší než algoritmy randomizované. Skutečně bezpečná implementace generátorů prvočísel by tedy měla opakovaně použít randomizovaný algoritmus k nalezení čísla, které je s vysokou pravděpodobností prvočíslo (třeba 1 ku milionu) a na něm pak spustit deterministický algoritmus, který sice trvá déle, ale skoro určitě uspěje a nebude ho třeba opakovat.
-
Dokonce je dokázáno, že pro každé n > 1 existuje prvočíslo větší než n a menší než 2n, viz Bertrandův postulát.
Dokonce je dokázáno třeba i to, že existuje nekonečně mnoho dvojic prvočísel p, p+2.
... Celý princip RSA je založený na tom, že zatímco test prvočíselnosti je vcelku triviální (jde provést v čase polynomiálním s délkou zápisu čísla), tak faktorizace je těžká....
Tak bezpečnost RSA nestojí zdaleka jen na obtížnosti faktorizace, ale ještě třeba na obtížnosti "diskrétního odlogaritmování"...
-
Dokonce je dokázáno třeba i to, že existuje nekonečně mnoho dvojic prvočísel p, p+2.
Není dokázáno.
-
Není dokázáno.
Ten důkaz se nepovedl.
http://crypto-world.info/news/index.php?prispevek=137&sekce=c
-
p,p+k kde k je 2 asi opravdu ne,ale jsou dukazy, kteryma to k pomalu snizujou ... nejmin jsem videl tusim k okolo 300 - bylo to neco v souvislosti s kryptomenou Riecoin
-
Podíval bych se do zdrojáku openssl (nebo nějakého čitelnějšího forku). Generuje se to pomocí
openssl dhparam -out dhparams-4096.pem 4096
Jestli tomu dobře rozumím, tak to není problém s entropií (/dev/random je vcelku uspokojivé), ale že možná openssl při generování toho dhparams-4096.pem používá nedostatečný počet předgenerovaných prvočísel? Najít ve zdrojáku jak to je by bylo uklidňující...
-
Podíval bych se do zdrojáku openssl (nebo nějakého čitelnějšího forku). Generuje se to pomocí
openssl dhparam -out dhparams-4096.pem 4096
Jestli tomu dobře rozumím, tak to není problém s entropií (/dev/random je vcelku uspokojivé), ale že možná openssl při generování toho dhparams-4096.pem používá nedostatečný počet předgenerovaných prvočísel? Najít ve zdrojáku jak to je by bylo uklidňující...
Právě proto jsem si říkal, že by bylo dobré vědět, jak nejen tam nějaké čísla přidat. Vygenerovat nějaké prvočísla není až tak velký problém, pokud člověk má dost času, navíc existují stránky, kde si jich člověk může spoustu stáhnout, pokud takovým stránkám bude věřit. Ale než se do něčeho takového člověk pustí, musí tomu rozumět...
-
Jaka je jejich skutecna hustota to je vec druha.
Pridam se k tem ostatnim vyvracecum omylu a dodam, ze hustota prvocisel je asymptoticky n/ln(n). Takze jich je celkem dost.
-
Jseš si jistý, že omyly vyvracíš a nezavádíš? hint: 1/ln(n)
-
Podíval bych se do zdrojáku openssl (nebo nějakého čitelnějšího forku). Generuje se to pomocí
openssl dhparam -out dhparams-4096.pem 4096
Jestli tomu dobře rozumím, tak to není problém s entropií (/dev/random je vcelku uspokojivé), ale že možná openssl při generování toho dhparams-4096.pem používá nedostatečný počet předgenerovaných prvočísel? Najít ve zdrojáku jak to je by bylo uklidňující...
Jak jsi přišel na to, že je tam vůbec _nějaký_ problém? Celá ta aféra kolem weak DH je kolem toho, že spousta lidí používá kilové DH (pro nějž lze předpočítat tabulku umožňující efektivní crackování, ale to předpočítání je velmi drahé), a navíc skoro všichni používají stejná, takže to stačí spočítat jednou a pak už se láme zadarmo.
Kdyby se buď používala dvou či čtyřkilová, tak by tabulku předpočítat nešlo, a kdyby se používala kilová, ale u každého jiná, tak by NSA nejspíš neutrácela tolik peněz za každého Frantu Vonáska.
Problém je v tom, že a) DH někdo kdysi nahardcodoval a kilo mu přišlo dost, b) generování vlastního 4kb DH trvá na horších počítačích klidně hodinu.
Já jsem si jich jednou přes noc spoustu napočítal a teď když potřebuju někam nové, tak prostě hrábnu a vytáhnu a nemusím čekat na počítání.
-
Není dokázáno.
Ten důkaz se nepovedl.
http://crypto-world.info/news/index.php?prispevek=137&sekce=c
Tady je novější populární článek, ale přes nadějný titulek zřejmě opravdu ještě není plně dokázáno.
http://www.nature.com/news/first-proof-that-infinitely-many-prime-numbers-come-in-pairs-1.12989
-
Jaka je jejich skutecna hustota to je vec druha.
Pridam se k tem ostatnim vyvracecum omylu a dodam, ze hustota prvocisel je asymptoticky n/ln(n). Takze jich je celkem dost.
Ja mel namysli spis takovy veci jako je "koberec z prvocisel". Kdyz si vizualizujete privocisla v 2 rozmernem prostoru, tak je vytvari zajimave obrazce a na prvni pohled to vypada, ze ve vyskytu prvocisel je nejaky skryty system.
-
Ja mel namysli spis takovy veci jako je "koberec z prvocisel". Kdyz si vizualizujete privocisla v 2 rozmernem prostoru, tak je vytvari zajimave obrazce a na prvni pohled to vypada, ze ve vyskytu prvocisel je nejaky skryty system.
Na tenhle dojem bohatě stačí, že jsou tam nerovnoměrnosti a že je to symetrické. Všimni si že ty zajímavé tvary se vyskytují kolem os symetrie. No a na nerovnoměrnosti stačí když je to opravdu náhodné.
-
asi zalezi na poctu bitu ... nicmene tady je neco pro ty mensi ...
https://en.wikipedia.org/wiki/Ulam_spiral (https://en.wikipedia.org/wiki/Ulam_spiral)
-
Ja mel namysli spis takovy veci jako je "koberec z prvocisel". Kdyz si vizualizujete privocisla v 2 rozmernem prostoru, tak je vytvari zajimave obrazce a na prvni pohled to vypada, ze ve vyskytu prvocisel je nejaky skryty system.
Na tenhle dojem bohatě stačí, že jsou tam nerovnoměrnosti a že je to symetrické. Všimni si že ty zajímavé tvary se vyskytují kolem os symetrie. No a na nerovnoměrnosti stačí když je to opravdu náhodné.
Prosím zanechte OT.