Tohle je snad common knowledge v oboru, ne? Ale dobrá, jako intro asi
https://safecurves.cr.yp.to/
Ono je to bohužel tak, že nemáme důkaz bezpečnosti pro nic, nejen ty křivky. Veškeré krypto stojí na tom, že v tom spousta schopných lidí hledala díru a zatím nic nenašla.
Od stále otevřeného P vs NP, přes chyby v implementacích, až po útoky postranními kanály je toho fakt hodně. A spousta z toho je minimálně prakticky nedokazatelná. Jestli bude nějaký prodejce krypta tvrdit, že má důkaz, tak pryč od něj :)
Ale to je nepochopení principu. Stejně jako třeba ve fyzice se nedokazuje (a nelze dokázat) neexistence jevů (určují se horní limity - nikdo střízlivý neřekne, že je proton stabilní, ale pouze to, že pokud je nestabilní, je poločas rozpadu alespoň 10^35 let).
V matematice nedokazujete axiomy, ale pouze to, že jejich určitá kombinace je bezesporná (a nebo dokonce ani to ne, viz Godelovy věty), ale hlavně že nějaký teorém je důsledek oněch axiomů.
Stejně tak v kryptografii pracujete s nějakými předpoklady - u RSA že neexistuje efektivní algoritmus pro rozklad čísla na prvočísla, u diskrétního logaritmu, že neexistuje efektivní algoritmu pro jeho výpočet, u diskrétního logaritmu na eliptické křivce k tomu navíc, že neexistuje efektivní algoritmus pro nalezení isomorfismu mezi operacemi na dané křivce a na Z/nZ (v podstatě eliptická křivka dělá to, že některé, na cyklickém tělese rychlé operace použité při řešení onoho problému, jsou na ní extrémně pomalé, a tak si můžeme dovolit použít mnohem menší čísla - z kilobitů se dostáváme na stovky bitů. Ve chvíli, kdybychom tohle dokázali zrychlit, tak šifra povolí na prosté brute force) popř pár dalších.
Teprve pak můžete tvrdit, že za daných předpokladů je algoritmus dnes bezpečný.
To co vidíte na oné stránce je pravý opak - laicky řečeno přišlo se na to, že za určitých okolností ony předpoklady neplatí (pro určitý typ křivky existují efektivní algoritmy...bla bla bla, máte to tam vysvětlené), a tak celá sranda kolem toho je na základě už známých útoků a z velké části na základě empirie vyloučit ty křivky, které buď jsou, nebo alespoň mohou být nebezpečné.
@Wasper: To je pravda, v kryptografii pracujete s nějakými předpoklady
, ale neměli bychom.
A rychlé operace použité při řešení onoho problému, jsou na ní extrémně pomalé, a tak si můžeme dovolit použít mnohem menší čísla
, to se děje, ale při aplikaci diskrétního logaritmu na velikosti klíče vůbec nezáleží.
> ale neměli bychom.
Úplně vždycky (nejen v krypto) pracujete s nějakými předpoklady. Není jiná možnost jak cokoliv udělat. Každý den předpokládáte spoustu věcí. Od tutových věcí, jako že se fyzikální zákony ze dne na den nezmění, až po to že se lidé kolem vás budou chovat +- rozumně.
Předpoklady v kryptu jsou jen pokračování téhle každodenní reality. Místo snění o "neměli bychom" se radši pořádně soustřeďte na to, co opravdu víte a co jenom automaticky předpokládáte.
@JSH: V matematice ale ne, mat.zákony se ze dne na den nezmění. 1+1 bude vždycky 2. To nemusíme předpokládat, můžeme jít hned na násobení, derivace a integrály. Ale u asymetrické kryptografie se tím, z nějakého důvodu, nikdo neřídí. Celý internet, veškerá komunikace, bankovní převody, platby kartou, a nakonec ještě kryptoměny stojí na jednom jediném předpokladu. Je jen otázkou času, až to praskne. Naštěstí to všichni vědí, a tak se na to připravují. Ne, nikdo se na to nepřipravuje.
Ten příklad s lidmi tady úplně nesedí.
Prosím pěkně, do matematiky opravdu nefušujte. Zrovna zavedení přirozených čísel je docela probádaná část matematiky, a zrovna nikdo apriori nepředpokládá, že 1+1=2.
Ale asi nemá cenu tady tady řešit, co ve skutečnosti takový matematik předpokládá (model ZFC), a jaké to má důsledky (třeba ono 1+1=2, kde 1=suc(0) a 2=suc(1) ), je toho plný internet, a třeba John Baez napsal moc hezkých článků (i) na tohle téma.
No v matematice přece předpokládáte že platí axiomy, ze kterých odvozujete všechno ostatní. Nemůžete z nich dokázat ani to, že nejsou ve sporu (pokud nemáte tak jednoduchý systém, že se k ničemu moc nehodí). Musí vám stačit, že hledáte dlouho a marně.
Jestli ty axiomy sedí na problém, který řešíte, už leží mimo samotnou matematiku. Můžete to ověřovat experimentálně, ale matematický důkaz nedostanete. Bez tohohle nedokazatelného kroku redukujete matematiku na intelektuální masturbaci odtrženou od reality.
.@johnny Opravdu? Takže když budu mít eliptickou křivku řádu 1001, tak bude stejně bezpečná jako klasické P256?
Nebo když sice bude vysokého řádu, ale délka klíče bude 8 bitů?
Edit: Nějaké předpoklady musíte udělat. Třeba takové, že neexistuje kosmická konspirace, že Váš mozek má kontinuitu (== že nějaký cizí proces nepřepsal větší, než malou část paměti v průběhu přemýšlení), pak co se týče matematiky (a specielně logiky), tak máme spoustu no-go teorémů, existence uncomputable funkcí apod.
Bohužel, jak něco obsahuje alespoň Peanovu aritmetiku, (která je velmi primitivní) tak jste na půdě nedokazatelnosti.
5. 10. 2023, 22:25 editováno autorem komentáře
> Tedy nebude bezpečná vůbec ani jedna.
Co si mám vlastně představit pod tím, že něco nebude vůbec bezpečné? Prolomí to chytřejší školák nebo žárlivá manželka? Nebo to znamená, že se nějací mafiáni/agenti k tomu tajemství můžou dostat prolomením šifry a nebudou to ze mě vytloukat v nějakém vlhkém a studeném sklepě?
U bezpečnosti vždycky jde o to, kdo se k tomu dostane, jaké prostředky na to bude potřebovat a jak dlouho mu to bude trvat. U krypta bohatě stačí aby nebylo nejslabší článek řetězce.
V OpenSSH si dnes muzete vybrat mezi EdDSA (dnes pouze ed25519) a ECDSA... a ano, kolem ECDSA (nistp256, nistp384, nistp521) jsou dlouhodobe jiste pochybnosti - i kdyz jde spise zatim jen o politicke uvahy (spolehlive prokazane to neni).
V OpenSSH jsou dnes k dispozici tři algoritmy: klasický RSA a dvoje eliptické křivky ECDSA a Ed25519. Druhá jmenovaná je nejnovější a řeší některé problémy předchozí varianty. Zejména závislost na dobrém generátoru náhodných čísel a problém s volbou křivky, který dramaticky mění bezpečnost algoritmu. Navíc varianta ECDSA schválená organizací NIST je dílem NSA a používají se tam podivné magické konstanty, jejichž původ nikdo nezná. Snowden před tím dost hlasitě varoval.
Ed25519 je otevřená, generuje klíče deterministicky, nepoužívá magické konstanty, nevrtala se v ní NSA a je rychlejší. Proto je obecně považována za bezpečnější a tedy preferovanou variantu.
Mne na https://safecurves.cr.yp.to/ vychadza, ze podmienky boli nastavene tak, aby ako bezpecne boli oznacene krivky vyvynute v Googlom.
Nejsem historik a moc jsem to nestudoval, tak co napíšu berte s rezervou, a paměť je trochu děravá k tomu - jestli si dobře pamatuju, tak djb přišel s 25519 jako alternativou v době, kdy zrovna (i jako dozvuky na Snowdena) vrcholila nedůvěra v cokoli, na co se NSA podívala, specificky v NIST křivky. A postupně se začala implementovat. Do toho přišel nijak nezdůvodněné vycouvání NSA z zavádění SuiteB (s NIST p521) s trapnou výmluvou stylu "počkejte si na posk-kvantum", které moc nevěřil nikdo.
Plus djb je v komunitě dost známý a uznávaný.
Takže nejspíš z historických důvodů.
5. 10. 2023, 18:31 editováno autorem komentáře
Na druhej stradne dnes sa uz NIST odporucaniami zaobera cely svet a beru sa defakto ako standard. Dokonca aj v Europskych odporucniach ETSI som P-256 nasiel ale ED25519 nie.
Viem, ze NSA kedysi zaviedla backdoor do nejakych sifrovacich algoritmov, ale tam dost richlo pochopili aku blbost spravili. Hlavne ked to co odporusaju pouzivaju oni sami (myslim tym NSA, a US Aramada)
Jo myslíte Dual_EC_DRBG? Tam to bylo pikantní o to, že o zneužitelnosti cvrlikali vrabčáci na střeše, NSA to hodně tlačila (včetně úplatků na zařazení do knihovny) a výhoda byla popsatelná Cimrmanovsky "algoritmus byl krajně podezřelý, ale zato extrémně pomalý".
S těmi doporučeními, on je to trochu problém v rozšíření. openssh je v pohodě, v tls už to je taky lepší, ale v DNSSEC to resolvne každé druhé DNSko.
Cely svet rozhodne ne :-) Rusaci maji prozmenu "sve" krivky od GOSTu. Tomu byste vy veril? ;-) A ze ETSI (urad) neco prebira... asi taky neni uplne dukaz, ze tam zadny problem neni. S prihlednuti k tomu, jak urednici obvykle pracuji ;-)
To mi ty vystupy od nezavislych univerzitnich matematiku/kryptologu, co zminuji vyhrady k ECDSA (ty podivne konstanty) a co predkladaji otevrenou variantu v podobe EdDSA prijdou duveryhodnejsi.