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.
Citace od: karel2 kdy 21. 10. 2015, 07:13:53
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.
Citace od: JardaA kdy 21. 10. 2015, 07:27:27
Citace od: karel2 kdy 21. 10. 2015, 07:13:53
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.
Citace od: Ivan kdy 21. 10. 2015, 10:06:51
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.
Citace od: Ivan kdy 21. 10. 2015, 10:06:51
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.
Citace od: Ivan kdy 21. 10. 2015, 10:06:51
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.
Citace od: Ivan kdy 21. 10. 2015, 10:06:51
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.
Citace od: Ivan kdy 21. 10. 2015, 10:06:51
... 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í"...
Citace od: frk kdy 21. 10. 2015, 11:33:22
Dokonce je dokázáno třeba i to, že existuje nekonečně mnoho dvojic prvočísel p, p+2.
Není dokázáno.
Citace od: Pavel Vojáček kdy 21. 10. 2015, 14:33:13
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
Citace od: Jenda kdy 21. 10. 2015, 01:21:17
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í...
Citace od: cmyk kdy 22. 10. 2015, 12:42:04
Citace od: Jenda kdy 21. 10. 2015, 01:21:17
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...
Citace od: Ivan kdy 21. 10. 2015, 10:06:51
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)
Citace od: cmyk kdy 22. 10. 2015, 12:42:04
Citace od: Jenda kdy 21. 10. 2015, 01:21:17
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í.
Citace od: ox kdy 21. 10. 2015, 17:39:45
Citace od: Pavel Vojáček kdy 21. 10. 2015, 14:33:13
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
Citace od: JS kdy 22. 10. 2015, 21:00:12
Citace od: Ivan kdy 21. 10. 2015, 10:06:51
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.
Citace od: Ivan kdy 23. 10. 2015, 10:01:46
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)
Citace od: JSH kdy 23. 10. 2015, 11:43:50
Citace od: Ivan kdy 23. 10. 2015, 10:01:46
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.