Potrzebuję zbudować funkcję skrótu, która przekształca dwie wartości 32bitowe w jedną w ten sposób, że działanie jej jest przemienne.
i ponadto:
gdzie są realizacją zmiennej losowej o rozkładzie jednostajnym na zbiorze
Potrzebuję zbudować funkcję skrótu, która przekształca dwie wartości 32bitowe w jedną w ten sposób, że działanie jej jest przemienne.
i ponadto:
gdzie są realizacją zmiennej losowej o rozkładzie jednostajnym na zbiorze
To musi być jakaś bezpieczna fukcja skrótu? (Tzn coś „kryptograficznego”?)
Bo jak nie, to chyba zwykły XOR spełnia warunki....
coobba napisał(a)
To musi być jakaś bezpieczna fukcja skrótu? (Tzn coś „kryptograficznego”?)
Nie musi być kryptograficznie bezpieczna,... Mam zamiar ją urzywać do umieszczania krawędzi grafu nieskierowanego w tablicy hashującej.
coobba napisał(a)
Bo jak nie, to chyba zwykły XOR spełnia warunki....
Ale XOR chyba sie nie nadaje, gdyż wtedy:
A tego bym ie chciał, gdyż w tym wypadku wszystkie pętle mają taki sam skrót :|
wg. tego co podales, zbudowac taka funkcje jest bardzo prosto..
niech:
g(a,b): dowolne przeksztalcenie 32bit+32bit -> 32bit
w takim razie:
h(a,b) := g( min(a,b), max(a,b) )
spelnia 32bit+32bit -> 32bit oraz h(a,b) = h(b,a)
a g moze byc doslownie czymkolwiek co ma 'dobry' rozrzut.. ale kolizji i tak nigdy nie ominiesz, ostatecznie moc zbioru wejscia jest 264 a wyjscia 232, tak wiec przy idelanym rozkladzie, na kazda jedna wartosc hasha, bedziesz mial 1 kolizje planowana (h(ab)=h(ba)) oraz ... dodatkowe 2^32-1 nieplanowanych..
Ten pomysł z i jest genialny :)
A z tego, że będę miał kolizji - jestem w pełni świadomy :] ...jedyne to mi zależało by nie były tak oczywiste.
Witam, czy ktos moglby podrzucic tu stronke gdzie mozna znalezc przedstawiony algorytm funkcji skrotu whirlpool? Bylbym bardzo wdzieczny. Pozdrawiam