Jak udělat soubor s konkrétním kontrolním součtem

Pavouk106

  • *****
  • 2 395
    • Zobrazit profil
    • Můj blog
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #30 kdy: 05. 01. 2012, 17:04:32 »
Prostě a jednoduše bez matematiky a dalších podrobností

Teoreticky to jde
Prakticky to taky jde

Když se budeš hodně snažit a podaří se Ti zachovat velikost souboru a jeho hash i po změně, máš doma na polici Nobelovku. Gratuluju!


DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #31 kdy: 05. 01. 2012, 17:08:14 »
Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Ta kolize imho nemusí existovat. Řekněme, že H1 bude mít obor funkce v lichých číslech a H2 v sudých číslech. Tam opravdu nemůže nastat situace kdy H1(x)=H2(x)

Pavouk106

  • *****
  • 2 395
    • Zobrazit profil
    • Můj blog
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #32 kdy: 05. 01. 2012, 17:08:56 »
Ještě dodatek:

Pokud chceš někomu podstrčit urpavenej soubor a chceš aby s nim pracoval, tak to udělej asi takhle - pošli mu to (nějak předej, ...), až (pokud) udělá hash a dá Ti vědět, že je jinej než má být (podle webu, jinýho dodavatele, ...), řekni mu, že u Tebe doma je ten hash taky jinej (a nadiktuj mu te samej, co to udělá jemu) a že Ti to dělá přesně to, co se od toho očekává (= funguje to = data jou naoko v pořádku). Lepší možnost, jak dneska obejít hash, prostě není.

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #33 kdy: 05. 01. 2012, 17:11:58 »
Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Ta kolize imho nemusí existovat. Řekněme, že H1 bude mít obor funkce v lichých číslech a H2 v sudých číslech. Tam opravdu nemůže nastat situace kdy H1(x)=H2(x)

eh, zapomeňte na to, napsal jsem blbost.

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #34 kdy: 05. 01. 2012, 17:15:47 »
Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Chci vidět důkaz :-)


DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #35 kdy: 05. 01. 2012, 17:32:16 »
Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Chci vidět důkaz :-)

Já mám protidůkaz: mějme množinu hashovacích funkcí Hn(x), kde Hn(x)=n-tý bit vstupu x. Pak jistě platí, že Hn(x)!=Hn(y) pro všechna n z intervalu 1..len(x). Prostě ty funkce to zkontrolují bit po bitu. QED. (formální důkaz nechám na někoho jiného)

Policajt

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #36 kdy: 05. 01. 2012, 17:33:44 »
Chci vidět důkaz :-)
..hash ma danou delku, rekneme 1 znak. znak muze nabyvat rekneme 5 hodnot. staci vzit 6 ruznych souboru a mas kolizi

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #37 kdy: 05. 01. 2012, 17:35:40 »
Chci vidět důkaz :-)
..hash ma danou delku, rekneme 1 znak. znak muze nabyvat rekneme 5 hodnot. staci vzit 6 ruznych souboru a mas kolizi

Pro jednu funkci. Ne pro n funkcí.

Karel

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #38 kdy: 05. 01. 2012, 18:39:24 »
Chci vidět důkaz :-)
..hash ma danou delku, rekneme 1 znak. znak muze nabyvat rekneme 5 hodnot. staci vzit 6 ruznych souboru a mas kolizi

Pro jednu funkci. Ne pro n funkcí.

Takže mám funkci 1, kde hash může nabývat 5 různých hodnot. Funkci 2, kde hash může nabývat 7 různých hodnot, a funkci 3, kde hash může nabývat 11 různých hodnot. Spojením těchto 3 funkcí vzniká nejvýše 5*7*11 = 385 různých kombinací výsledků. Tak vemte 386 souborů a máte kolizi. Ono spojování N funkcí jen prodlužuje to, co by se dalo nazvat výsledným hashem. A dokud tento výsledek je menší než vstup, pak vždy existuje kolize.

Karel

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #39 kdy: 05. 01. 2012, 18:45:53 »
Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Chci vidět důkaz :-)

Já mám protidůkaz: mějme množinu hashovacích funkcí Hn(x), kde Hn(x)=n-tý bit vstupu x. Pak jistě platí, že Hn(x)!=Hn(y) pro všechna n z intervalu 1..len(x). Prostě ty funkce to zkontrolují bit po bitu. QED. (formální důkaz nechám na někoho jiného)

Takže váš výsledný hash je stejně dlouhý jako vstupní soubor (čímž porušujete předpoklad, že hash je menší než vstupní data). Pak je metoda opravdu neprůstřelná. Jenže, proč se tedy obtěžovat hashem, když se stejně jedná o porovnání 1:1?

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #40 kdy: 05. 01. 2012, 20:52:29 »
Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Chci vidět důkaz :-)

Já mám protidůkaz: mějme množinu hashovacích funkcí Hn(x), kde Hn(x)=n-tý bit vstupu x. Pak jistě platí, že Hn(x)!=Hn(y) pro všechna n z intervalu 1..len(x). Prostě ty funkce to zkontrolují bit po bitu. QED. (formální důkaz nechám na někoho jiného)

Takže váš výsledný hash je stejně dlouhý jako vstupní soubor (čímž porušujete předpoklad, že hash je menší než vstupní data). Pak je metoda opravdu neprůstřelná. Jenže, proč se tedy obtěžovat hashem, když se stejně jedná o porovnání 1:1?
Někteří lidi tady tvrdili, že při libovolné kombinaci různých hashovacích funkcí je možné najít takovou kolizi, že nebude možné ty soubory rozlišit. Já jsem na jednoduchém příkladu n jednobitových hashovacích funkcí dokázal, že to není pravda. Ano, funkčně je to porovnání bit po bitu. Ale k vyvrácení tvrzení to stačí.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #41 kdy: 05. 01. 2012, 20:55:50 »
Este raz napisem to co nie je mozne vyvratit.
Kedze hash na to aby mal pre nas zmysel MUSI byt radovo mensi ako vstupne subory (128KiB vs. TiB, etc), musia nutne existovat kolizie. Presne ako bolo spomenute hore.

Pokial chceme kolizie 100% vylucit, mozeme predsa rovno porovnavat zdrojovy subor bit po bite!

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #42 kdy: 05. 01. 2012, 20:56:34 »
Dodatok: A je uplne jedno ci pouzijes jednu alebo x hashovacich funkcii!

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #43 kdy: 05. 01. 2012, 21:26:35 »
Dodatok: A je uplne jedno ci pouzijes jednu alebo x hashovacich funkcii!

Ne, když použiju n jednobitových hashovacích funkcí, tak nemůže dojít ke kolizi, protože tato operace je ekvivalentní srovnání dvou souborů bit po bitu.

JS

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #44 kdy: 05. 01. 2012, 21:36:12 »
Dodatok: A je uplne jedno ci pouzijes jednu alebo x hashovacich funkcii!

Neni. To co jste prave udelal bylo vytknuti existencniho kvantifikatoru (existuje kolize) pred obecny (pro vsechny hashovaci funkce), a to se nema delat. :-)

Apropos, nalezani kolizi bude snadne, pokud P=NP.