Autor Zpráva
had
Profil *
ahoj lidičky,

provozuju na větším webu soukromé vzkazy a rád bych nějaký rozumný (malý) scriptík php, který by mi bezpečně vyrobil hash ze zprávy tak, aby bylo z něho zpětně možné dostat z něj zase text.
k dispozici mám text, id uživatele, který odesílá a id toho, kdo to přijmá.

měl jsem celkem pěkný způsob, ale ukázalo se, že zkracuje zprávy na cca 150 znaků +-.

poradíte? díky :)
Nox
Profil
vyrobil hash ze zprávy tak, aby bylo z něho zpětně možné dostat z něj zase text.
Není možné dostat z hashe jednoznačně původní heslo, jelikož hashů je konečný počet a možných zdrojů nekonečný, tzn. jeden hash má nekonečně mnoho vzorů

Je ale samozřejmě možné šifrovat a v tomto rozhodně radím nevynalézat kolo, zvlášť když to kolo bylo vymýšleno chytrýma lidma
a již nějakou dobu vylepšováno
http://cz.php.net/manual/en/book.mcrypt.php
had
Profil *
asi jsem to blbě řekl... nechci hash... chci prostě jen vyrobit zašifrovaný řetězec, ze kterého zase zpátky půjde dostat text...

"...jeden hash má nekonečně mnoho vzorů???" - to se ale rovná kolizi, ne??? aby šifra splňovala svůj účel, musí být pro každý řetězec minimálně 1 hash, který je neopakovatelný, nebo se pletu? hashů je ideálně stejný počet, jako možných kombinací původních textů k šifrování...
hash = řetězec, ze kterého nelze dostat původní text
Nox
Profil
Možná se pletu, ale kdyžtak mě řekněte v čem se mýlím...

Neopakovatelný hash délky např. 40 znaků by byl možný jen pokud by vzor mohl mít jen 40 znaků, pak by obě množiny měly stejný počet, ale jakmile bys do toho zahrnul i řetězce o délce třeba 41, tak už máš víc vzorů než možných hashů a tudíž nemůže mít každý vzor jednoznačný hash

"Kolize jsou nežádoucí, ale v principu se jim nelze vyhnout, protože počet možných různých vstupních zpráv je nekonečný a počet různých otisků je omezený (limitovaný, konečný, menší)"
Wikipedie

Především -> hashování není šifrování, prostě jen můžeš porovnat, zda mají 2 řetězce stejný hash
Teoreticky lze hashováním a porovnáváním dokonce dostat původní řetězec z hashe, ale je to opravdu jen na haluz, že to bude zrovna ten a ne jiný vzor

chci prostě jen vyrobit zašifrovaný řetězec, ze kterého zase zpátky půjde dostat text
tomu se říká "zašifrovaný řetězec" :)

hash = řetězec, ze kterého nelze dostat původní text
http://cs.wikipedia.org/wiki/Hash
had
Profil *
S těma délkama hashů to stále nechápu...mozková kapacita prostě už nestačí :)
já jsem si myslel, že pro každé slovo musí být různý hash, pakliže ne, nastává kolize (dvě slova mají stejný hash).
ale dosáhl jsem výsledku tématu, díky za pomoc :)
imploder
Profil
had
S těma délkama hashů to stále nechápu...mozková kapacita prostě už nestačí :)
Není to tak složité, jde o jednoduchou kombinatoriku.

Představ si že máš řetězec o jednom znaku. Každý znak (předpokládejme, že znak=bajt) může mít 256 různých hodnot. Tedy náš jednoznakový řetězec má taky 256 možných hodnot. Pak přidáme další znak, tedy máme řetězec o 2 znacích. Ke každé hodnotě prvního znaku je 256 různých hodnot druhého znaku. Tedy dvouznakový řetězec může mít 256 krát 256 možných hodnot. Když přidáme třetí znak, má opět 256krát tolik možných hodnot, co řetězec dvouznakový. A tak pořád dál. Prostě:

Počet možných hodnot řetězce o délce n znaků je 256 na n-tou.

Kratší má vždy kombinací míň, delší víc. Stejně dlouhé řetězce mají vždycky stejný počet možných hodnot.

Ke každému řetězci musí existovat odpovídající kód, na který se převede. Aby bylo možné každý kód převést zpátky na původní řetězec, musí ke každému kódu náležet právě 1 původní řetězec. Na to musí být možných kódů aspoň tolik, jako možných původních řetězců. A proto nejde zakódovat všechny možné řetězce o určité délce do řetězce kratšího.

Kódů musí být k dispozici stejně nebo víc než řetězců. Vysvětluju to nějak rozvláčně, ale prostě je to taková celkem jednoduchá úvaha, že se do toho místa na kódy všechny ty řetězce "vejdou", jenom když není kratší.
Nox
Profil
imploder
256 je trochu moc :)

had
Prostě hash má konstantní délku... aby bylo nějaké přiřazení unikátní, tak musí být aspoň tolik cílových prvků kolik původních

...když máš 3 modré kuličky (řetězce) a 2 červené (hashe) a přitom musíš každou modrou přiřadit nějaké červené (každý řetězec lze
zahashovat), tak nemáš jinou možnost než dát 2 kuličky k jedné červené
Původních řetězců je nekonečně mnoho (s délkou 1 (možná 0) až nekonečně), hashů je konečně mnoho (tipuju 36 na n-tou, kde n je délka hashe)

Ano, pak nastává kolize, resp. je nekonečně mnoho kolizí, to už je život a daň za rychlost hashovacích algoritmů

Trochu naši teorii nabourává:
http://en.wikipedia.org/wiki/Perfect_hash_function
a přiznám se, že moc nechápu, jak je to možné
nightfish
Profil
hashů je konečně mnoho (tipuju 36 na n-tou, kde n je délka hashe)
samozřejmě záleží na délce hashe...
md5 produkuje 128bitový výstup (možných kombinací je tedy 2^128)
sha1 produkuje 160bitový výstup (2^160 kombinací)

Ano, pak nastává kolize, resp. je nekonečně mnoho kolizí, to už je život a daň za rychlost hashovacích algoritmů
ano, u hashovacích funkcí kolize existují, nicméně právě kvalita hashovacího algoritmu se posuzuje podle toho, jak obtížné je kolizi najít
obvykle se požaduje, aby hašovací funkce splňovala tyto vlastnosti:
- je jednoduché vypočítat hash F(x) pro vstupní hodnotu x
- pro dané y je výpočetně nezvládnutelné nalézt takové x, aby platilo F(x) = y (first preimage resistance)
- pro dané x je výpočetně nezvládnutelné nalézt takové x' <> x, aby platilo F(x') = F(x) (second preimage resistance)
- je výpočetně nezvládnutelné nalézt taková x, x' (x <> x'), aby platilo F(x') = F(x) (collision resistance)

samozřejmě všechny tyto případy lze řešit útokem hrubou silou (otestovat všechny možnosti, díky narozeninovému paradoxu jich teoreticky stačí otestovat půlku) - výpočetní nezvládnutelnost spočívá v tom, že za současného stavu techniky to nejde v rozumném čase

pro zájemce o studium hašovacích funkcí lze doporučit http://crypto-world.info/klima/2005/cryptofest_2005.htm

Trochu naši teorii nabourává:
http://en.wikipedia.org/wiki/Perfect_hash_function
a přiznám se, že moc nechápu, jak je to možné

perfect hashing spoléhá na to, že máte omezenou množinu všech vstupů - každému vstupu pak hašovací funkcí přiřadíte právě jeden výstup (používá se například při implementaci vyhledávání v hašovací tabulce) - s kryptografickou hašovací funkcí to nemá moc společného
had
Profil *
wow! teda kluci, tady se to rozjelo... :)

jj, díky implodere, pochopil jsem :)

napadá mě takhle jeden dotaz:
jak je potom možné, že se s výkonem dnešních počítačů nevytvoří kompletní databáze předpočítaných hashů pro md5 nebo sha1? když bych si vzal, že 2^160 ~= 1,46 * 10e47...to není mnoho, pakliže by se to rozdělilo na několik počítačů a každý by pracoval na jednom kousku... vznikla by kompletní tabulka předpočítaných hashů a další varianty textu by byly kolize, ptž by se funkce opakovala, myslím si to správně???
nightfish
Profil
had
on je asi trochu problém tolik dat někam uložit...
běžně dostupné disky mají kapacitu 10^12 bajtů (1 TB)... tzn. pořád bys takových disků potřeboval 10^35...
imploder
Profil
Nox
256 je trochu moc :)
Myslel jsem obecnou hashovací funkci, neuvažoval jsem omezení jako třeba že hash md5 má vždycky tvar [a-z0-9]{16} zatímco původní řetězec může obsahovat jakékoliv znaky a může být jakkoliv dlouhý. Počet možných hodnot každého bajtu je 256 v obou řetězcích. Hash md5 díky tomu omezení člověk bez problémů přečte, jiná hashovací funkce žádné omezení znaků v hashi mít nemusí.

had
jak je potom možné, že se s výkonem dnešních počítačů nevytvoří kompletní databáze předpočítaných hashů pro md5 nebo sha1? když bych si vzal, že 2^160 ~= 1,46 * 10e47...to není mnoho, pakliže by se to rozdělilo na několik počítačů a každý by pracoval na jednom kousku... vznikla by kompletní tabulka předpočítaných hashů a další varianty textu by byly kolize, ptž by se funkce opakovala, myslím si to správně???
Vychází mi 2^160 ~= 1,46 * 10^48.

Kdybys vzal všechny počítače na světě - kterých je slušně výkonných max. tak 10^9 - tak každý z nich by musel vygenerovat 1,46 * 10^39 hashů. Pokud jich dejme tomu za sekundu vytvoří 10 000, tak mu splnění úkolu zabere 10^35 s, tj. 7.61035008 × 1028 let. To není málo.

Určitý problém by taky asi představovalo vyhledávání v takovém obřím objemu dat. Nejspíš by se indexovalo hashem, aby se dalo ke každému řetězci podle hashe přímo přistoupit (tedy hash = adresa řetězce). Pokud není možné nějak plánovaně rozvrhnout řetězce, aby se hashovaly tak, aby jejich hashe šly po sobě, pak vždycky po zahashování (dokud se neprovede, neví se, co z toho vyjde) by se musely vkládat záznamy na příslušná místa a nešly by přitom za sebou. To by byl u většího počtu počítačů problém, protože místo zápisu na disk (i ten je dost pomalý) by se musely data tahat přes síť. Možná by to šlo nějak chytře zefektivnit, ale jednoduchý problém to určitě není.
had
Profil *
uf...aha. 1028 jo??? hm...tak jsem se asi trošku seknul... :)
nightfish
Profil
imploder
že hash md5 má vždycky tvar [a-z0-9]{16}
md5 v php vrací buď hexa řetězec o délce 32 znaků ([a-z0-9]{32})
a nebo "binární" řetězec o délce 16 znaků (bajtů) (podle hodnoty druhého nepovinného parametru)
tak či onak je výstup vždy 128bitový

Vaše odpověď

Odkud se sem odkazuje


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: