Kryptografia
Jednokierunkowe
funkcje skrótu
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. 3203083
Wykład X
e-mail: robert.borowiec@ita.pwr.wroc.pl
www: lstwww.ita.pwr.wroc.pl/~RB/
15-minut
Funkcja jednokierunkowa
Funkcja jednokierunkowa f(x) jest to funkcja, dla
której łatwo policzyć y=f(x) dla znanego argumentu x.
Jednak znając wartość funkcji y, trudno jest wyznaczyć
argument x=f-1(y).
x
f(x)
*'
X
Y
,' ?!
f -1(x)
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 2/9
Jednokierunkowa funkcja skrótu
Jednokierunkowa funkcja skrótu jest to funkcja
jednokierunkowa, która w wyniku daje wartość o
konkretnej ustalonej długości.
Właściwości funkcji skrótu:
dla zadanej wiadomości M funkcja umożliwia łatwe
x
wyznaczenie f(M);
dla zadanej wartości y trudno jest wyznaczyć
wiadomość M=f -1(y);
dla zadanej wiadomości M trudno jest wyznaczyć
inną wiadomość M dla której funkcja f wytwarza taki
sam skrót f(M)= f(M );
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 3/9
Kryptoanaliza funkcji skrótu
Funkcja skrótu powinna spełniać trzy warunki:
Niemożliwe jest odtworzenie wiadomości M (wartości
argumentu funkcji) znajÄ…c wynik funkcji;
Musi być trudno obliczeniowo znalezć wiadomość M , która
w wyniku da tą sama wartość skrótu jak wiadomość M;
x
Musi być trudno obliczeniowo znalezć takie dwie losowe
wiadomości M i M dające po skróceniu samą wartość
(atak metoda dnia urodzin). Żaden atak nie powinien być
bardziej efektywny niż metoda brutalna;
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 4/9
Kryptoanaliza funkcji skrótu
Paradoks dnia urodzin:
Ile osób musi liczyć grupa , aby była znaczna
szansa na to aby, ktoś z tej grupy miał urodziny
określonego dnia.
x
Odpowiedz 183 osoby
Ile osób musi liczyć grupa, aby była znaczna
szansa na to, aby znalazły się w niej dwie osoby
o tej samej dacie urodzin.
Odpowiedz 23 osoby, co daje 253 możliwe pary
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 5/9
Kryptoanaliza funkcji skrótu
Przy funkcji skrótu, która skraca wiadomość M do
słowa o długości h bitów znalezienie wiadomości M ,
która skraca się do takiej samej wartości jak
wiadomość M wymaga wykonania sprawdzenia 2h
losowo wybranych wiadomości.
x
Znalezienie dwóch dowolnych wiadomości M i M
skracających się do tej samej wartości o długości h
bitów wymaga sprawdzenia 2h/2 losowo wybranych
wiadomości.
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 6/9
Znane funkcje skrótu
Snerfu
N-hash
MD2
MD4
x
MD5
Ripe-MD
HAVAL
SHA
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 7/9
Funkcja SHA
SHA ( ang. Secure Hash Algorithm) jest
standardem w Stanach Zjednoczonych
Cechy SHA:
wytwarza skrót o długości 160 bitów;
x
przeznaczony jest do skracania wiadomości o
długości mniejszej niż 264 bitów, ale większej od
0.
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 8/9
KONIEC
Dziękuję za uwagę
Kryptografia, Wykład X
© Robert Borowiec 2003-10-13
Strona 9/9
Wyszukiwarka
Podobne podstrony:
W14 Kodowanie i Kryptografia kody cykliczne?le 6gW15 Kodowanie i Kryptografia kody splotowe?leW8 Kodowanie i Kryptografia Algorytmy niesymetryczne 1gW12 Kodowanie i Kryptografia Rozdzielanie tajemnicy 1gW3 Kodowanie i Kryptografia Algebra 2 2gW13 Kodowanie i Kryptografia kody liniowe?le 6g9 Kryptoanaliza funkcji skrotu 14W1 Kodowanie i Kryptografia Systemy cyfrowe 1gW6 Kodowanie i Kryptografia Kody klasyczne kryptoanaliza 1gW11 Kodowanie i Kryptografia Protokoy kryptograficzne 2gW2 Kodowanie i Kryptografia Algebra 1 2gW9 Kodowanie i Kryptografia Podpisy cyfrowe 1gW7 Kodowanie i Kryptografia Szyfry symetryczne 2gW4 Kodowanie i Kryptografia Wprowadzenie do kryptografii 2gW5 Kodowanie i Kryptografia Szyfry klasyczne 2gW10 wskazniki na tablice wielowymiarowe i funkcjeBMW e39 e46 funkcje kodowaniaKodowanie modułów BMW NCS Przydatne funkcjeGeneza i funkcjonowanie mitu arkadyjskiegowięcej podobnych podstron