[PL]

Czym jest funkcja skrótu?

Funkcja skrótu jest algorytmem, przekształcającym dowolnie długi ciąg wejściowy, na ciąg wyjściowy o stałej długości. Przykładem tego, jak to jest zrobione, jest wykorzystanie rozbudowywania -- jeżeli mamy funkcję operującą na bloku danych, to możemy wywoływać ją wielokrotnie, zyskując możliwość obliczania skrótu dla dłuższego wejścia. Jedną z popularnych konstrukcji, jest konstrukcja Merkle–Damgårda, na której opiera się znaczna część funkcji skrótu. Przykładem innych rozwiązań jest konstrukcja gąbki funkcji SHA-3.

Jeżeli funkcja kompresji jest bezkolizyjna, również cały algorytm ma taką własność.

Wiadomość dzielona jest na mniejsze fragmenty ustalonej długości. Ostatni blok, najczęściej krótszy, wyrównywany jest przy pomocy specjalnego ciągu. Jednym z przykładów takiego ciągu może być 100000.....$L$, gdzie $L$ oznacza 64 bitową długość wiadomości przed wyrównaniem w formacie big-endian.

Następnie przy pomocy kolejnych bloków wiadomości i wyjścia z poprzedniej kompresji (funkcja H na rysunku), będącego aktualnym stanem funkcji skrótu, następuje jego modyfikacja. W przypadku pierwszego bloku, zamiast poprzedniego wyjścia, stosuje się stały wektor inicjujący (na rysunku oznaczony jako IV). Po ostatniej iteracji aktualny stan jest wyjściem całego algorytmu.

Różne funkcje mogą mieć różne zastosowanie docelowe -- funkcja służąca indeksowaniu najprawdopodobniej jest niewystarczająco bezpiecznym wyborem do celów uwierzytelniania. Jednoznaczne wymagania i obligatoryjne własności funkcji są uwarunkowywane jej zastosowaniem, jednak można wyróżnić kilka elementów ogólnie je charakteryzujących.

Czym jest kolizja funkcji skrótu?

Kolizja funkcji skrótu następuje wtedy, gdy dla dwóch różnych wejśc funkcji (np. haseł) jej wynik będzie taki sam. Może się tak wydarzyć dlatego, że możliwych wejść do funkcji jest nieskończenie wiele, a wyjść tylko ogarniczona ilość (chociaż bardzo duża).

Cechy funkcji skrótu

Jest nieodwracalna (jednokierunkowa)

Jednokierunkowość (albo nieodwracalność) oznacza, że wylcizenie skrótu z danego wejścia jest nieskomplikowane, ale posiadając tylko skrót obliczeniowo trudne jest znalezienie odopowiedniego wejścia.

Lawinowość funkcji skrótu

Jedną z cech jest także fakt dużych zmian w wyjściowym skrócie nawet w przypadku niewielkich modyfikacji wejścia. Nawet nieznacznie różniące się wiadomości powinny generować zupełnie inne skróty, bez żadnych wzajemnych zależności. Każdy bit wyjścia powinien zmieniać się z prawdopodobieństwem bliskim 0,5. W związku z tym, że haszowanie to proces mapowania nieskończonej ilości wiadomości na skończony zbiór skrótów, idealne funkcje skrótu nie istnieją. W praktyce wykorzystujemy algorytmy, które mają cechy dostatecznie zbliżone do tych idealnych.

Jest bezkolizyjna

Tak jest właśnie przypadku tej cechy – bezkolizyjności. Funkcją bezkolizyjną będziemy nazywać taką, dla której nie istnieje wielomianowy algorytm potrafiący znaleźć kolizję. To oczywiście nie oznacza, że taka nie istnieje. Po prostu jest to na tyle obliczeniowo skomplikowane, że możemy uznać to rozwiązanie za wystarczająco bezpieczne.

Funkcja skrótu cechuje się słabą bezkolizyjnością, jeżeli obliczeniowo trudne jest znalezienie kolizji dla znanej wiadomości. Silna bezkolizyjność to natomiast taka, w której skomplikowane obliczeniowo jest znalezienie nawet dowolnej pary wiadomości dającej ten sam skrót.