Crypto-IT

Funkcja jednokierunkowa to funkcja, którą łatwo obliczyć, ale za to dużo trudniej obliczyć wartość jej funkcji odwrotnej. Znając wartość x można łatwo obliczyć f(x). Z drugiej strony znając wartość f(x) bardzo trudno jest wyznaczyć oryginalną wartość x.

W sensie ściśle matematycznym nie jest udowodnione, że funkcje jednokierunkowe rzeczywiście istnieją. W praktyce jednak, wykorzystuje się funkcje, które zachowują się tak, jak powinny zachowywać się idealne funkcje jednokierunkowe.

Funkcje jednokierunkowe są kluczowymi elementami wielu narzędzi przydatnych w kryptografii. Są wykorzystywane w generatorach pseudolosowych, uwierzytelnianiu wiadomości i w podpisach elektronicznych.

Jednokierunkowa funkcja zapadkowa to specjalny typ funkcji jednokierunkowej, która posiada swego rodzaju "tylne drzwi" (zapadnię). Podobnie jak w przypadku wszystkich funkcji jednokierunkowych, łatwo jest obliczyć wynik w jednym kierunku, natomiast trudno obliczać w kierunku przeciwnym. Różnica polega na tym, że jeśli posiada się pewne dodatkowe sekretne informacje, to bez większych problemów można obliczyć taką funkcję w kierunku przeciwnym.

Przykładem jednokierunkowych funkcji zapadkowych może być rozkład bardzo dużych liczb na czynniki pierwsze. Jest to zadanie obecnie praktycznie niewykonalne. Z drugiej strony, znając jedną z poszukiwanych liczb, zadanie rozkładu na czynniki pierwsze staje się bardzo proste.

Jednokierunkowe funkcje skrótu (istnieje wiele innych określeń funkcji tego typu) przekształcają ciągi wejściowe o różnej długości w ciągi wyjściowe o stałej (zwykle mniejszej) długości. Ciąg wyjściowy jest nazywany często wartością skrótu (ang. hash value). Jednokierunkowe funkcje skrótu są często wykorzystywane do oznaczania porcji danych, czyli do przypisywania im pewnych unikalnych, charakterystycznych wartości.

Jednokierunkowe funkcje skrótu spełniają wszystkie warunki, jakie muszą posiadać funkcje jednokierunkowe. Łatwo jest obliczyć skrót na podstawie ciągu wejściowego, natomiast dysponując tylko skrótem nie da się przewidzieć jakie były oryginalne dane wejściowe.

Funkcja skrótu powinna być bezkonfliktowa (ang. collision-free), czyli bardzo trudno powinno być wskazać dwa różne ciągi wejściowe, które dają w wyniku taki sam skrót.

Algorytmy funkcji skrótu są często jawne. Zapewniają bezpieczeństwo dzięki swoim właściwościom, posiadanym z definicji jako funkcje jednokierunkowe. Zwykle zmiana dowolnego bitu w ciągu wejściowym, powoduje zmianę około połowy bitów wartości skrótu. Dane generowane przez funkcje skrótu powinny być pseudolosowe (nie powinno być możliwe odróżnienie ich od zwykłych danych losowych).

Jednokierunkowe funkcje skrótu używane są w celu ochrony przed celowymi lub przypadkowymi modyfikacjami danych. Dla danego zbioru danych można wyliczyć za ich pomocą sumę kontrolną, która będzie mogła być załączona do wiadomości i sprawdzona przez jej odbiorców. Weryfikacja odbywa się poprzez wyliczenie przez odbiorców sumy kontrolnej dla otrzymanych danych i porównanie jej z wartością otrzymaną). Funkcje skrótu wykorzystywane są na przykład w algorytmie uwierzytelniania wiadomości HMAC.

Ponadto, funkcje skrótu są wykorzystywane do efektywnego przechowywania danych w tak zwanych tablicach haszujących. Dostęp do danych odbywa się poprzez odszukiwanie właściwych wartości skrótu, przechowywanych w pamięci komputera.

Mając daną funkcję skrótu operującą na niewielkim bloku danych, można rozszerzyć ją i skonstruować funkcję operującą na większej, dowolnie dużej ilości danych wejściowych. W ten sposób staje się możliwe obliczenie wartości skrótu dla wiadomości o dowolnej długości. Można w tym celu wykorzystać tak zwaną konstrukcję Merkle-Damgard.

Poniższy schemat prezentuje sposób połączenia bloków funkcji skrótu (h: T x X -> T, gdzie T to zbiór wszystkich możliwych wartości skrótu), z których każda operuje na jednym bloku danych, w łańcuch, który umożliwia wyliczenie wartości skrótu dla całej wiadomości (H: X^L -> T).

Do pierwszej funkcji h przekazywany jest wcześniej ustalony wektor inicjujący IV. Natomiast ostatni blok wiadomości, powinien zostać dopełniony do pełnej długości za pomocą wcześniej ustalonych bitów. Popularną metodą wyrównywania długości ostatniego bloku jest dopisanie za ostatnim bitem wiadomości dodatkowego bitu równego 1, a następnie dopełnienie bloku bitami zerowymi. Pozwala to precyzyjnie określić koniec właściwych bitów wiadomości.

Można wykazać, że jeśli funkcja h jest bezkonfliktowa, to utworzona na jej bazie funkcja H jest również bezkonfliktowa (ponieważ kolizja w funkcji H powodowałaby automatycznie kolizję w funkcji h).

Istnieje kilka popularnych sposobów utworzenia jednokierunkowej funkcji skrótu, operującej na danych wejściowych dowolnej długości, przy użyciu algorytmów szyfrów blokowych.

Funkcja skrótu Davies-Meyer (oznaczona jako h) wykorzystuje algorytm szyfrujący E operujący na kolejnych blokach wiadomości:
    h(H, m) = E(m, H) XOR H

Budowa funkcji Davies-Meyer jest przedstawione poniżej:

Można wykazać, że jeżeli E jest bezpiecznym algorytmem szyfru blokowego, to ewentualny napastnik musiałby wykonać w przybliżeniu O(2^n/2) operacji szyfrowania, aby znaleźć kolizję (czyli wiadomość, dla której wyliczona wartość skrótu jest taka sama, jak wartość, której on poszukuje).

Innym rodzajem funkcji skrótu opartej na algorytmie szyfru blokowego są funkcje Miyaguchi-Preneel. Istnieje 12 odmian tych funkcji, przykładowo:
    h(H, m) = E(m, H) XOR H XOR m
lub:
    h(H, m) = E(H XOR m, m) XOR m