[linux] ako zakodovat heslo?

[Marcel Telka]

On Mon, Feb 25, 2002 at 03:20:55PM +0100, Jozef Novikmec wrote:
>  > > Neviem ci som odbornik na kryptografiu, skor nie ako ano :-), ale v
> > > odbornej terminologii sa takejto moznosti hovori kolizia. Znamena ze dva
>  > > rozne vstupy daju ten isty vystup z hashovacej funkcie. Kedze v teorii
>  > > sa vravi ze hashovacia funkcia je jednoznacna, funkcia ktora ma kolizie
>  > > jednoznacna nie je, takato funkcia by sa nemala volat hashovacou:-).
>  > 
>  > Myslim, ze tu sa trochu mylis. Hashovacia funkcia vo vseobecnosti je na to,
>  > aby mapovala vstup (z velkej mnoziny) na vystup (z mensej, resp. malej mnoziny).
>  > Pri takomto mapovani vzdy moze dojst k tomu, ze sa vygeneruju rovnake vystupy.
> 
>  Ano to som nepoprel ze k takejto moznosti moze dojst, ale prave v tom je
>  problem ze ak sa to stane casto, tak takato hashovacia funkcia nie je
>  dostatocne kvalitna na pouzivanie.

Suhlas. Ja som vsak reagoval na toto:

Kedze v teorii sa vravi ze hashovacia funkcia je jednoznacna, funkcia ktora
ma kolizie jednoznacna nie je, takato funkcia by sa nemala volat hashovacou:-).

A toto bohuzial nie je pravda. Mozno si to naozaj myslel tak, ako si to teraz
vysvetlil, ale povodna veta bohuzial nebola pravdiva (alebo aspon nebola presna).


>  
>  Takze si zoberme mnozinu vsetkych 128 bitovych slov. Ak mame funkciu
>  ktora tuto mnozinu transformuje na mnozinu 128 bitovych slov pricom
>  y(i)=hash(x(i)) , pre vsetky x(i) musi byt ine y(i), takejto funkcii sa
>  hovori jednoznacna. Napr. y=x^2 jednoznacna nie je lebo 2^2-4 ale aj
>  -2^2=4.
>  
>  Ak je vystup hashovacej funkcie 128 bitovy, tak existuje 2^128 moznych
>  128 bitovych slov. Ak si zoberieme ze vstupov existuje nekonecne vela,
>  musi zakonite dojst ku kolizii. Otazka je ze ako casto a podla toho sa
>  hodnoti kvalita hashovacej funkcie.

Spravne. Idealna hashovacia funkcia je uplne rovnomerna.

>  
>  > 
>  > BTW, hashovanie sa po slovensky spravne vola "transformacia kluca"
>  > (zdroj: N. Wirth: Algoritmy a struktury udajov, alfa 1989, str. 360)
>  > 
>  
>  Pridam este jeden termin. Mna v skole ucili ze hashovacia funkcia sa po
>  slovensky povie jednocestna funkcia.

Hm. Myslim, ze hashovacia funkcia je len specialny pripad jednocestnej funkcie.
Samozrejme zavisi od toho, ako si hashovaciu funkciu zadefinujeme :-).
Napr. funkcia f(x) = 0 alebo f(x) = x' (derivacia) su typicke "jednocestne"
funkcie avsak tazko by sme ich mohli nazvat hashovacimi.

>  
>  Z toho vyplyva aj jej dalsia vlastnost a to ze y(i)=hash(x(i)) ale k
>  funkcii hash neexistuje inverzna funkcia teda neplati

Myslim, ze neexistencia inverznej funkcie nie je nutna podmienka pre
hashovaciu funkciu. Napr. o funkcii f(x) = x sa tiez (v istom priblizeni)
da povedat ako o hashovacej funkcii, avsak existuje k nej inverzna funkcia.

>  x(i)=hash^(-1)(y(i)). Keby som hlbsie popatral v pamati tak by som
>  pridal aj podmienky ktore musi funkcia splnat aby mala inverznu
>  funkciu:-), ved to nebolo az tak davno :-))).

:-) Ja si to tiez uz nepamatam, ale intuitivne by som povedal, ze (transformacna)
funkcia ma inverznu funkciu vtedy, ak pre dva rozne vstupy generuje dva rozny vystupy
a pre rovnake vstupy generuje rovnake vystupy a toto plati pre vsetky mozne vstupy.



Ahoj.

-- 
+-------------------------------------------+
| Marcel Telka   e-mail:   marcel na telka.sk  |
|                homepage: http://telka.sk/ |
|                jabber:   marcel na jabber.sk |
+-------------------------------------------+