Jaká prvočísla jsou bezpečná?

[Whox]

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..

[Reklama]

[Tuxik]

Třeba 2^57885161-1 je celkem bezpečný 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.

[aaaaaa]

http://www.jupiterbroadcasting.com/89226/national-security-breaking-agency-techsnap-236/
Tu o tom trochu mluví, doporučuji poslechnout.

[Jenda]

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

[karel2]

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.

[Reklama]

[JardaA]

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.

[Ivan]

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.

[Milan Straka]

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.

[frk]

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í"...

[Pavel Vojáček]

Dokonce je dokázáno třeba i to, že existuje nekonečně mnoho dvojic prvočísel p, p+2.

Není dokázáno.

[ox]

Není dokázáno.

Ten důkaz se nepovedl.
http://crypto-world.info/news/index.php?prispevek=137&sekce=c

[fedorac]

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

[cmyk]

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í...

[Whox]

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...

[JS]

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.