Dotaz: Kontrolní kód s max 14 znaky

[Proki]

Dobrý den, v jedné aplikaci potřebuji vytvářet kontrolní kódy různě dlouhých XML dokumentů, které se přenášejí mezi systémy. Podmínkou je, že tento kód může mít maximálně 14 alfanumerických znaků a bylo by vhodné, aby například dvě chyby v dokumentu nevygenerovali platný opět kontrolní součet. Tento kontrolní součet slouží jen pro detekci chyb při přenosu, nemusí být tedy generován žádným šifrovacím algoritmem. Děkuji za každou radu, co bych mohl použít, případně za každé nakopnutí správným směrem. Celý den hledám různé algoritmy, ale všechny mnou nalezené generují kódy delší jak 15 znaků. Zkrácení delšího kódu si dovolit nemohu.

Odpovědi

[VjEtNaM]

Asi idealni pro kontrolu detekce chyby přenosu se mi zdá CRC-32.
Délka kontolního hashe pro CRC-32 je 8 znaků hex např "04C11DB7".
Možnost kolize dvou kontrolních součtů je 1:2^32.
Ve spoustě prog. jazyků již bývá implementován jako funkce.
Více info zde -> Wiki-CRC

[Semo]

Nechapem, preco by si nemohol z nejakeho dlhsieho kodu brat len podmnozinu 14 znakov.

[VjEtNaM]

Určitě mohl ale, hashovaci algoritmy nejsou nadarmo navrženy tak aby co nejméně docházelo ke kolizím.
Tím že se vezme pouze podmnožina části znaků múže dojít k nepředpokládanému zvýšení pravděpodobnosti kolizí.

[me vakérav]

Aby co nejméně docházelo ke kolizím je potřeba hodnoty hashe rozprostřít rovnoměrně do prostoru. To znamená, že i jednotlivé části hashe jsou co nejvíce rozprostřeny (= všechny hodnoty stejně náhodně zastoupeny).

Takže pokud by část hashe vedla ke zvýšení pravděpodobnosti kolize (většímu než daným samotným zkrácením prostoru), jedná se o špatný hash.

Správná odpověď na tazatelovu otázku je vzít některý standardní hash a použít z něj třeba prvních 14 znaků. To je IMHO zcela korektní operace. (Anebo: Udělat hash, to převést na binární podobu (tj. dvouznaky 0-9a-f převést na bajty, čímž se zkrátí o polovinu), to base64ovat a z výsledku vzít prvních 14 znaků.)

[Sten]

Souhlasím. Jmenuje se to lavinový efekt (změna jednoho bitu kompletně změní celý hash). Hlavní důvod nicméně není předcházení kolizím, ale ochrana před prolomením pomocí statistické analýzy.

[VjEtNaM]

Díky za link rád jsem se poučil.

[Sten]

14 alfanumerických znaků? To je 62¹⁴ kombinací (pokud se rozlišují velká a malá písmena), což je cca 1,2 × 10²⁵. To můžete klidně použít nějakou 64-bitovou heš (třeba CRC-64) a vhodně to namapovat na písmena a čísla.

[l4m4]

14 alnum znaků obsáhne cca 83 bitů informace. Takže lepší je vzít delší hash a uříznout, jak radí jiní.

[Sten]

Možná by tedy bylo lepší použít Skein nebo Fletcher, kde si můžete nastavit délku, jakou potřebujete. CRC umí taky libovolnou délku, ale je tam problém s výběrem vhodných mocnin.

[Heron]

CRC je kontrolní součet a ne hash. Obojí má jiné použití a nelze to zaměnovat.

[pepe_]

Příloha:

• crc32 (794 bytů)

crc32 urcite staci ...

[l4m4]

Proč určitě stačí? Proč v perlu, když o perlu tazatel nic nepíše? Proč, když už v perlu, používat složitě Archive::Zip namísto standardního Digest?

[Sten]

Hašovací funkce nejsou jenom kryptografické, CRC je zrovna nekryptografická hašovací funkce

[Heron]

To je pravda.

Jen jsem chtěl upozornit na skutečnost, že CRC má zcela jiné použití a návrh, než taková rodina funkcí SHA a nemělo by se to zaměňovat. CRC jsou navržené jako kontrolní součty a SHA je navržená jako kryptograficky bezpečná. Což je vidět už jen z délky výstupu. Kryprograficky silné funkce jsou ty o délce 160b a více.

[Proki]

Zkusil jsem implementovat algoritmus, kdy vstup hashuju pomocí funkce MD5 a pak jej převedu do vyšší číselné soustavy tak, aby výstup měl maximálně 14 znaků (za využití dalších písmen abecedy neomezující se pouze na 0-9, a-f jako je tomu u šestnáctkové soustavy). Dal by se tento postup v reálu aplikovat nebo je to naprosto chybná cesta a CRC-32 by bylo pro kontrolu chyb vhodnější?

[me vakérav]

Jo, viz poslední věta v závorce tady. Ale standardní base64 se mi zdá jednodušší než implementovat něco svého.

Nicméně pro kontrolu chyb stačí skoro cokoli, klidně to CRC32.

[l4m4]

Base62 ovšem obsahuje dva nealanumetické znaky (+ a /). Tudíž je-li ten požadavek striktní, je nutno použít Base62.

[Tarmaq]

a k paddingu je vyuzivan znak =