Druhá odpověď skutečně není správná, ale řešení je opravdu jednoduché. Rozeberu první IMO jednodušší případ, otázku jen trochu upravím, aby odpověď byla jednoznačnější.
Kolik nejméně náhodně narozených osob musí být na vaší párty, aby s alespoň 90% pravděpodobností nastalo, že někdo v místnosti má narozeniny jako vy?
Nechť se narozeninové party účastní n lidí (včetně oslavence). Jaká je pravděpodobnost p', že se nikdo nenarodil ve stejný den jako oslavenec? p' = (364/365)^(n-1). Pravděpodobnost p jevu opačného, tedy že na party bude alespoň jeden další člověk, který se narodil ve stejný den jako oslavenec, bude p = 1 - p'. Nyní už jen vyjádříme n a vezmeme jeho horní celou část.
n = [1 + log (1 - p) / log (364 / 365)],
což pro p = 0,9 dává n = 841
Paradox je zajímavý i tím, že u něj rychleji konverguje pravděpodobnost k 1. I v našem porovnání (vzrůst pravděpodobnosti z 0,5 na 0,9) vzrostl počet osob u paradoxu jen o 78%, zatímco u běžné úlohy o 231%.
Zamýšlel jsem to spíše jako "zážitek paradoxu" a ne test z počtů. Pochopitelně kdo chce... Snazší je počítat druhou část otázky, která je dost podobná otázce "kolikrát musím typicky házet kostkou, aby mi během sekvence házení s 90% pravděpodobností padla právě jednou šestka".
V rámci tohoto článku se pojmem míní to, že neexistuje teoretický postup s jehož pomocí, a v jakékoliv kombinaci se současnými existujícími nebo sestrojitelnými technickými zařízeními (HW, SW, cluster, grid apod., kvantový počítač /ty jsou zatím jen slaboučké/...), by bylo možné v reálném čase nalézt to, co se v každé uvedené definici hledá. Pojem tedy není omezen na čistou matematiku, ale "schůdnost" zde zahrnuje i kritérium praxe. Ergo náročnost existujících postupů musí být takového řádu, že vám nepomůže ani masivní paralelizace výpočtu pomocí mnoha pospojovaných počítačů.
Chyby implementace algoritmu nebo možnost průniků do zařízení (které algoritmus vykonává) jsou zcela jinou záležitostí, která ovšem též souvisí s praxí. Je pravda, že většina bezpečnostních incidentů zařízení (přesněji modulů) spadá do této kategorie. Takové případy zde na začátku označuji trochu slangově jako "díry implementace", tento a navazující text (zítra?) o nich nepojednávají.
Z navazujícího textu by "nároky praxe" měly být již zřejmější, zatím aspoň takto.
btw: co furt máte s těma kvantovejma počítačema ? Pokud vim tak jediné co zvládly je faktorial 17tky. To je reálné po několika hodinách maximálně desítkách (možná nemam odhad a jsou to desítky minut) vyplincnout z hlavy :-), tak jaké kvanotvé počítače to je ještě hooooodně v plenkách.
Mozna mate na mysli pripad, kdy kvantovy pocitac zvladnul faktorizaci cisla 15, coz zvladne bezne zdatny clovek za par sekund. Ale zde jde spis o princip, ze lze dnes narocne operace delat s teoreticky uplne jinou slozitosti, jen neni uplne zvladnuta technologie. Takovych, co rikali ze "neco nejde" a "neco je v plenkach" uz bylo hodne a historie jim nakonec vetsinou za pravdu neda. Pred deseti lety stal mobil desitky tisic a vazil pul kila (prehanim) o pet let pozdeji ho mel temer kazdy za par babek. To same se muze stat s kvantovymi pocitaci a byl bych opatrny rikat, ze neco nejde. Z hlediska sifrovani bych radsi premyslel jak udelat sifru, ktera na takovym pocitaci nepujde rozbit za par sekund.
no nevim, co je normální člověk ale faktorizvat 15 za pár sekund ...no nevím nevím.
Jistě, že věda postuju rychle. A řikání o nečem, že je to v plenkách se nevyplácí. Zase nadruhou stranu u toho faktoriálu nekončej možnosti kvanotovejch počítaču ale končí technologickej postup, kterým se pokoušej vědci sestavovat kvanotové počítače. Takže máš možná máš pravdu a neměl bych to říkat, až se objeví novej postup výroby bude to třeba neskutečně rychlý vývoj :-)
Faktorizace je rozklad cisla na soucin prvocisel, coz je tady 15=5*3, jen je treba spojit hodne qbitu umerne velikosti toho cisla. Tady jich bylo potreba par, u cisel pouzivanych v sifrovani jich budou asi stovky a to se zatim neumi.
Jasny ze tezko rict, jestli zrovna tohle se zvladne, ale jak je znam, tak na neco prijdou! :-) Ale co, treba z toho fakt nikdy nic nebude.
Mozna Vase schopnost pocitat 17! odpovida Vasi inteligenci - nevim, jak Vy, ale tohle lze snad za (maximalne) par minut i z hlavy, nerknu-li s tuzkou a papirem. Kvantove pocitace jsou eralnou hrozbou prave proto, ze uz dnes vime a mame algoritmy s linearni (tedy nejlepsi moznou ze soucasneho pohledu) casovou slozitosti, ktere dnesni pohled na asymetrickou kryptografii rozbiji naprosto uplne na padrt... A pokud si myslite, ze ten, komu se to povede bude jako prvni informovat halasne verejnost, bude patricne placan po zadech, tak jste na velkem omylu. A vubec, jste si jist, ze takovato zarizeni UZ nejsou a jen se o tom nesmi vedet? Vite co vsecho skryva NSA? Vite, jake zakulisni podivne okolnosti doprovazeji DES od zacatku...? Nemusim byt tak velky magor, abych si myslel, ze je to do puntiku fikce nebo na druhou stranu zcela pravdive...
Pletes si kvantovou kryptografii a kvantovy pocitac, to jsou dve ruzne veci. Kvantova kryptografie se uz experimentalne nasazuje na mnoha mistech, dokonce jsem slysel o jednom projektu, ktery si dal za ukol pospojovat nektere banky v CR kvantovym kryptografickym kanalem... ale ztroskotalo to na prepojovacich optickych prvcich.
kvantovy pocitac je provadeni operaci pomoci quibitu, kvantova kryptografie je zpusob posilani jednotlivych fotonu s urcitym kvantovym "nabojem", u kterych zavisi na tom, "jak" se prijmou... je to trochu slozitejsi, doporuucju wiki :).
"Informatikům" (rozumějte diletantům se zkušenostma s patláním čehosi v n+1 jazycích) vašeho typu by naopak neškodilo znát základy teorie, nemusel byste se pak zesměšňovat. Tipuju správně, že učíte nějaké nebohé studenty na jedné pražské VŠ?
"...8 počítačů..." - podstatné výsledky kryptoanalýzy se obvykle týkají asymptotické složitosti. "proskočí jejich šifrovací vrstvu" - pletete si algoritmus a jeho a implementaci. "A proto se každou chvíli objeví větší či menší mezera v uznávaných algoritmech." - opravdu, zjevně nechápete rozdíl mezi algoritmem a jeho implementací. "Právě to, že se lidé, kteří uměli programovat, naučili kryptologickou teorii, vedlo přece dosud ke všem prolomením." - blábol.
Chcete-li jinak, jako u každého matemnatického tvrzení musíte vždy mít nějaké předpoklady.
Předpoklady vaší teorie tedy jsou jaké? - Nejspíš, že algorimus nesmí být nijak implementován (aby teorie přesně platila).
Já jsem se už kdysi ptal v jedné diskusi, jak kryptologové řeší problém spywaru. Tak jako ho řešíte?
Kryptologové "řeší" spyware tak, že bezpečnostně kritické funkce soustředí do takových modulů, do nichž se spyware nemůže dostat.
Bezpečnost implementací pak není čistě jen "kryptologická" záležitost byť kryptoanalytici mívají velké slovo v tom, kudy na implementace útočit. Některé zásady bezpečných implementací:
- Omezení složitosti zařízení
- Dohled nad návrhem, výrobou, dodáním
- Odolnost proti, nebo aspoň detekce, narušení
- Odolnost proti známým druhům průniků
- Certifikace zařízení/modulů podle určitých metodologií zahrnující výše uvedené atd.
Kvůli tomu byste např. měl mít klíče a vytváření e-podpisu implementováno na čipové kartě (popř. tokenu).
Obecně se jedná o tematiku "Záruk bezpečnosti". Na obecné platformě jako jsou pécéčka se jakákoliv formální bezpečnost dosahuje poměrně obtížně, pragmatické postupy proti spyware asi znáte...
Neptáte se na kryptografii, ale na bezpečnost. Kryptografie není všelék na bezpečnost!
Předpoklady? Z teoretického hlediska můžu třeba chtí tajný prostor, kam útočník útočník nevidí, a kde schovávám klíče, a další tajný prostor, kde probíhá algoritmus, jeho stav útočník opět nevidí, a neunikají z něj žádné jiné informace než odpověď z definované množiny v konstantním čase.
Samozřejmě je otázka, jak takovou věc realizovat v praxi. To je zajímavé, ale nechápu, proč by jí měl řešit především kryptolog. Odpověď může zasahovat od bezpečnosti a programování přes elektrotechniku až po ostrahu objektů.
Například se dají předpoklady plnit tak, že se postaví barák, před barák člověk s pistolí, dovnitř se zavře skupina šifrantů s kalkulačkama. Taková bezpečnost se dá nalomit třeba tak, že útočník zastřelí chlapa s pistolí a z šifrantů vytáhne klíče mučením. Nebo nějaké informace uniknou od šifranta k jeho přítelkzni v posteli. Nějaký voják vám asi bude schpný spočíat, kolik by stála ostraha informací v ceně kolika milonů proti jakým útočníkům...
Nebo můžu postavit šifrovací čip, hlídat narušení jeho pouzdra, budu se muset starat o elmag emise, spotřebu energie, a tak dále a tak dále... Útočník může zkoušet čip rozbít, nebo přečíst paměť pomocí velmi citlivých magnetometrů, nebo cokoli jiného. Jaké útoky a obrany kolik stojí vám může vysvětlit elktrotechnika fyzik.
Nebo můžete mít OS s nějakým bezpečnostním modelem...
Jestli se ptáte po spywaru - v prostředí, kde může "šifrující" program a jeho paměť a veškeré vstupy a výstupy číst a měnit útočník (resp. jeho programy) vám kryptografie téměř nic nenabídne, nic nevyřeší. Otázka je, jaké hodnoty se chrání v prostředí, kde běžně běží spyware.
Odpověď tedy zní, kryptologie předpokládá, že nikdo se k ničemu nedostane.
Ale to je implementačně téměř nesplnitelné. A také je každý prvek implementovaného algoritmu různě rizikový. A to by, podle mě, měla být záležitost kryptologů, aby řekli, kde předpokládají jakou úroveň zabezpečení. Protože pro špionážní služby je současná kryptologoie požehnáním, lidé mylně věřím, že mají vše zabezpečeno, a oni mají již vše připraveno v digitálním tvaru.
U algoritmu jehoz casoprostorova ci vycislitelna slozitost lze libovolnym znamym zpusobem (i jen teoreticky - viz narozeninovy paradox) vyznamne zkratit je naprosto irelevantni konkretni implementace nebo technicke prostredky. A o redukci jste mozna uz zaslechl...
mám 3 MD5 hashe a potřebuji k tomu najít hesla, která jsem zapomněl. Jedno jsem našel na http://passcracking.com/Good_values_list.asp, ale další tam nejsou. Neznáte kde je nějaká kompletní databáze?
No ja jsem byl na přednášce pama Klímy(předpokládám, že neni třeba představovat) o MD5 a tam byly Kolize prvního a druhého řádu, přesně prohozeny.
Prvi řád : nalezení druhého vzoru, dva na n/2
Druhý řád: nalezení obrazu, dva na n
Pokud se podíváte na originální anglické termíny nebo věcnou podstatu, zjistíte, že žádný rozpor není. Jde o to jak přeložit pojmy "image resistance", "2nd image resistance" a "collision resistance", které jsem pro jistotu referenčně uvedl. Já používám své překlady, které vychází z Menezese. Také jsou vhodnější pro výklad, protože vlastnosti/obrázky je vhodné řadit jak v článku jsou a pak je nelogické, když se kolize II.řádu probírají dříve než kolize I. řádu. Pokud probíráte hašovací funkce v širším rámci, nebo pro jiné publikum, tak mohou být priority výkladu jiné.
V češtině jsou slova vzor/obraz určená pro podmnožiny definičního oboru/oboru hodnot, které sobě zobrazením odpovídají. U funkcí jsou užívané výrazy argument/hodnota (týkají se jediného prvku množiny o což u hašovacích funkcí jde). Proto myslím Klíma zavedl úplně jinou terminologii přes kolize I. a II. řádu (nevylučuji, že se též používají někde v anglické literatuře), které mají stoupající hierarchii z hlediska vzrůstající schopnosti útočníka nalézat kolize. Mnou uváděná terminologie je naopak převzata z terminologie Menezese včetně "síly" odolnosti proti kolizím, která je brána z pohledu schopnosti hašovací funkce útokům odolávat.
"Silně kolizně odolná" hašovací funkce odolává i snadnějšímu "nalezení kolizí I. řádu". Proto se to zdá prohozené (pohled kryptograf vs. kryptoanalytik).
Ideální by byl nějaký veřejný matematický slovník, v němž by se to ujednotilo. Před psaním tohoto článku jsem kvůli termínům trochu prohledával český web, ale nic použitelného a autoritativního jsem nenašel. Potíž, je že v oblasti je navíc zvyk používat i nematematické pojmy z programování (vstup, výstup)...
Výpočtově neschůdné je obvykle jen to řešení, které si dovedou matematici představit ve svém světě.
Takže třeba 8 spojených počítačů si nepředstaví - protože to Turing před 50 lety nepopsal, rovněž tak si nepředstaví, že by někdo proskočil jejich "šifrovací vrstvu" a podíval se na obsah nějakých pomocných proměnných - protože opět neuvažují situaci, co udělá jejich slavný program, pokud (úmyslně) přeteče buffer.
A proto se každou chvíli objeví větší či menší mezera v uznávaných algoritmech.
Já řešení vidím v tom, aby se kryptologové naučili nejprve programovat. (Ale ne pouze v jednom jazyce pod jedním operačním systémem!) Právě to, že se lidé, kteří uměli programovat, naučili kryptologickou teorii, vedlo přece dosud ke všem prolomením.