Vlákno názorů k článku Hash kódy bez tajností, nejen LinkedIn a ti další od Ondřej Bouda - Vtip je v tom, že když hledám někoho,...

Vtip je v tom, že když hledám někoho, kdo má narozeniny ve stejný den jako já, tak mám jasně dané datum. Pravděpodobnost, že někdo narodil v konkrétně daném dni, je 1:365.

V tom druhém případě ale nemám datum fixnuté, a proto je pravděpodobnost úspěchu mnohem vyšší. Je to stejný rozdíl, jako když budete snažit hodit kostkou dvakrát za sebou šestku (fixní výsledek) versus hodit dvakrát za sebou "stejné číslo".

Ty situace má smysl rozlišovat např. proto, že hash se často používá k ověření pravosti dokumentů (elektronický podpis). Když mi někdo pošle podepsaný dokument a já ho potom chci pozměnit/zfalšovat, jsem v té "fixní" situaci: jedna verze dokumentu (a její hash) je pevně daná.

Na druhou stranu, když dokument vytvářím a chci někoho podvést, jsem v té příznivější situaci: snažím se vytvořit dva dokumenty, které se obsahem budou lišit (v můj prospěch) a přitom budou mít stejný otisk (jiného otisku dosáhnou změnou nevýznamotvorných prvků: vkládáním mezer, změnou formátování apod.). Příklad: vytvářím smlouvu o půjčce, od dlužníka si nechám elektronicky podepsat verzi s úrokem 5%, ale současně si vygeneruju verzi s úrokem 20% a obrovským penále (se stejným hashem - a tu pak předložím soudu). Oproti "fixní" variantě mám výhodu v tom, že můžu podle potřeby měnit obsah *obou* verzí.

Takže v té první (fixní) situaci vygeneruju 200 různě změněných dokumentů, ale šance, že se trefím do potřebného hashe, je velmi malá.

V té druhé situaci vygeneruju 100 verzí od každého ze znění (tedy taky celkem 200 dokumentů) a přitom šance, že dva z těch dokumentů budou mít stejný otisk, je řádově vyšší...

Je to tak, pavděpodobnost že vyhrajete ve sportce je malá, ale pravděpodobnost že někdo vyhraje ve sportce je docela velká.

Ten na konci zmíněný narozeninový paradox je zajímavý, to jsem vůbec netušil. Opravdu to tak funguje?

Ano. V Crypto Class se to v rámci jednoho cvičení demonstruje na úloze, najít kolize pro 50bitový hash - naivně hrubou silou by to bylo pro jednotlivého uživatele poměrně obtížné, pomocí narozeninového paradoxu to je práce na maximálně 10 sekund...

Ovšem, pravděpodobnostně. Pamatujte, mám jen 50% pravděpodobnost. Ale když nenajdu po těch 10 sekundách, tak pokus stopnu a spustím úplně nový, který potrvá zase 10 sekund a zase bude mít 50% pravděpodobnost. Pravděpodobnost, že ani po minutě nebudu mít kolizi, už je dost malá, a po hodině zanedbatelná.

Jisteze to funguje, ale statisticky! Stejne tak je mozne, ze na pracovisti bude 365 lidi a kazdy bude mit narozeniny v jiny den (pravdepodobnost vyskytu tohoto jevu ovsem bude velmi mala).