Funkcje skrótu: koncepcja i podstawy

W różnych gałęziach technologii informacyjnej wykorzystywane są funkcje mieszania. Z jednej strony zaprojektowano znaczne uproszczenie wymiany danych między użytkownikami i przetwarzanie plików używanych do różnych celów, z drugiej strony, w celu optymalizacji algorytmów zapewniających kontrolę dostępu do odpowiednich zasobów. Funkcja haszowania jest jednym z kluczowych narzędzi do zapewniania ochrony hasłem danych, a także organizowania wymiany dokumentów podpisanych cyfrowym podpisem. Istnieje wiele standardów, dzięki którym pliki mogą być buforowane. Wiele z nich zostało opracowanych przez rosyjskich specjalistów. W jakich wersjach mogą być reprezentowane funkcje mieszające? Jakie są główne mechanizmy ich praktycznego zastosowania?

Co to jest?

Najpierw zapoznaj się z pojęciem funkcji skrótu. Termin ten jest powszechnie rozumiany jako algorytm do przekształcania pewnej ilości informacji w krótszą sekwencję symboli za pomocą metod matematycznych. Praktyczne znaczenie funkcji hash można prześledzić w różnych obszarach. Dzięki temu można ich używać podczas sprawdzania integralności plików i programów. Ponadto kryptograficzne funkcje mieszające są używane w algorytmach szyfrowania.

Charakterystyka

Rozważ kluczowe cechy badanych algorytmów. Wśród nich:

• obecność wewnętrznych algorytmów przekształcania danych o pierwotnej długości w krótszą sekwencję znaków;
• otwartość na weryfikację kryptograficzną;
• obecność algorytmów niezawodnie szyfrujących oryginalne dane;
• adaptacja do odszyfrowywania, gdy zaangażowane są małe moce obliczeniowe.

Wśród innych najważniejszych właściwości funkcji mieszającej:

• umiejętność przetwarzania początkowych macierzy danych o dowolnej długości;
• generowanie bloków hash o stałej długości;
• równomiernie rozprowadzaj wartości funkcji na wyjściu.

Rozważane algorytmy sugerują również wrażliwość na dane wejściowe na poziomie 1 bit. Oznacza to, że nawet jeśli, warunkowo mówiąc, przynajmniej jedna zmiana liter w dokumencie źródłowym, funkcja mieszania będzie wyglądać inaczej.

Wymagania mieszania

Istnieje szereg wymagań dotyczących funkcji skrótu przeznaczonych do praktycznego wykorzystania w określonym obszarze. Po pierwsze, odpowiedni algorytm powinien być wrażliwy na zmiany w wewnętrznej strukturze zaszyfrowanych dokumentów. Oznacza to, że w funkcji mieszania należy rozpoznać, jeśli mówimy o pliku tekstowym, permutacjach akapitowych, dzieleniu wyrazów. Z jednej strony treść dokumentu się nie zmienia, z drugiej - jego struktura jest dostosowywana, a proces ten powinien być rozpoznawany podczas mieszania. Po drugie, rozważany algorytm musi przekonwertować dane tak, aby operacja odwrotna (przekształcenie skrótu w oryginalny dokument) była praktycznie niemożliwa. Po trzecie, funkcja mieszająca powinna obejmować użycie takich algorytmów, które praktycznie wykluczają prawdopodobieństwo utworzenia tej samej sekwencji znaków w postaci skrótu, innymi słowy - pojawienie się tak zwanych kolizji. Rozpatrzymy ich istotę nieco później.

Oznaczone wymagania, do których funkcja hash musi być zgodna, mogą być spełnione głównie poprzez zastosowanie złożonych podejść matematycznych.

Struktura

Przeanalizujmy, jaka może być struktura rozpatrywanych funkcji. Jak zauważyliśmy powyżej, wśród głównych wymagań rozważanych algorytmów jest zapewnienie jednokierunkowości szyfrowania. Osoba, która ma do dyspozycji tylko skrót, nie powinna być w stanie uzyskać na jego podstawie dokumentu źródłowego.

W której strukturze można użyć funkcji mieszania dla takich celów? Przykładem jego kompilacji może być: H (hash, czyli hash) = f (T (tekst), H1), gdzie H1 jest algorytmem przetwarzania tekstu T. Ta funkcja miesza T w taki sposób, że bez znajomości H1, otwórz go jako w pełni funkcjonalny plik będzie prawie niemożliwy.

Korzystanie z funkcji skrótu w praktyce: pobieranie plików

Bardziej szczegółowo przyjrzymy się możliwościom zastosowania funkcji skrótu w praktyce. Wykorzystanie odpowiednich algorytmów może być używane podczas pisania skryptów do pobierania plików z serwerów internetowych.

W większości przypadków określona jest suma kontrolna dla każdego pliku - jest to wartość mieszania. Powinien być taki sam dla obiektu znajdującego się na serwerze i pobrany na komputer użytkownika. Jeśli tak nie jest, plik może się nie otworzyć lub może się nie uruchomić poprawnie.

Funkcja skrótu i ​​EDS

Korzystanie z funkcji haszowania jest powszechne podczas organizowania wymiany dokumentów zawierających podpis cyfrowy. W takim przypadku podpisany plik zostanie zaszyfrowany, aby odbiorca mógł zweryfikować jego prawdziwość. Chociaż formalnie funkcja hash nie jest zawarta w strukturze klucza elektronicznego, może być zapisana w pamięci flash sprzętu, z którym podpisywane są dokumenty, na przykład eToken.

Podpis elektroniczny jest szyfrowany za pomocą kluczy publicznych i prywatnych. Oznacza to, że wiadomość zaszyfrowana za pomocą klucza prywatnego jest dołączona do pliku źródłowego, a EDS jest weryfikowana przy użyciu klucza publicznego. Jeśli funkcja mieszania obu dokumentów jest taka sama, plik przechowywany przez odbiorcę jest uznawany za autentyczny, a podpis nadawcy jest uznawany za poprawny.

Hashing, jak zauważyliśmy powyżej, nie jest bezpośrednio składnikiem EDS, jednak umożliwia bardzo efektywną optymalizację algorytmów aktywacji podpisów elektronicznych. Zatem tylko hash może być zaszyfrowany, a nie sam dokument. W rezultacie szybkość plików przetwarzania znacznie wzrasta, a jednocześnie możliwe staje się zapewnienie skuteczniejszych mechanizmów ochrony EDS, ponieważ nacisk w operacjach obliczeniowych w tym przypadku będzie umieszczony nie na przetwarzaniu oryginalnych danych, ale na zapewnieniu siły kryptograficznej podpisu. Funkcja skrótu umożliwia również podpisywanie różnych typy danych a nie tylko tekst.

Sprawdzanie hasła

Innym możliwym obszarem zastosowania hashowania jest organizacja algorytmów weryfikacji haseł, które ograniczają dostęp do określonych zasobów plików. W jaki sposób niektóre rodzaje funkcji skrótu mogą być zaangażowane w rozwiązywanie takich problemów? Bardzo proste.

Faktem jest, że na większości serwerów, do których dostęp jest ograniczony, hasła są przechowywane w postaci wartości zakodowanych. Jest to całkiem logiczne - gdyby hasła zostały przedstawione w oryginalnej formie, hakerzy, którzy uzyskaliby do nich dostęp, mogliby z łatwością odczytać tajne dane. Z kolei na podstawie skrótu do obliczenia hasła nie jest łatwo.

W jaki sposób sprawdzany jest dostęp użytkownika przy użyciu rozważanych algorytmów? Hasło wprowadzone przez użytkownika jest sprawdzane względem tego, co jest przechowywane w funkcji mieszającej, która jest przechowywana na serwerze. Jeśli wartości bloków tekstu są takie same, użytkownik uzyskuje niezbędny dostęp do zasobów.

Najprostsza funkcja skrótu może być używana jako narzędzie do sprawdzania haseł. Jednak w praktyce specjaliści IT najczęściej używają złożonych wielostopniowych algorytmów kryptograficznych. Z reguły są one uzupełniane przez stosowanie norm transfer danych za pośrednictwem bezpiecznego kanału - aby hakerzy nie mogli wykryć ani obliczyć hasła przesłanego z komputera użytkownika na serwer - przed sprawdzeniem za pomocą zakotwiczonych bloków tekstu.

Hash Collisions

W teorii funkcji skrótu takie zjawisko jest dostarczane jako kolizja. Jaka jest jego istota? Kolizja hash to sytuacja, w której dwa różne pliki mają ten sam kod skrótu. Jest to możliwe, jeśli długość docelowej sekwencji znaków jest mała. W tym przypadku prawdopodobieństwo dopasowania hash będzie wyższe.

Aby uniknąć kolizji, zaleca się w szczególności użycie podwójnego algorytmu zwanego "hashiem funkcji mieszania". Obejmuje tworzenie otwartego i zamkniętego kodu. Wielu programistów rozwiązujących ważne problemy zaleca, aby nie używać funkcji mieszania w przypadkach, gdy nie jest to konieczne i zawsze testować odpowiednie algorytmy w celu uzyskania najlepszej kompatybilności z określonymi kluczami.

Historia wyglądu

Założyciele teorii funkcji skrótu można uznać za badaczy Cartera, Wegmana, Simonsona, Bierbrauera. W pierwszych wersjach odpowiednie algorytmy były używane jako zestaw narzędzi do tworzenia unikalnych obrazów sekwencji znaków o dowolnej długości, z późniejszym celem ich identyfikacji i sprawdzenia autentyczności. Z kolei mieszanie, zgodnie z określonymi kryteriami, powinno mieć długość 30-512 bitów. Jako szczególnie przydatną cechę odpowiednich funkcji, uznano, że jest przydatna do wykorzystania jako zasobu do szybkiego wyszukiwania plików lub ich sortowania.

Popularne standardy Hash

Rozważamy teraz popularne standardy, w których funkcje skrótu mogą być reprezentowane. Wśród nich - CRC. Ten algorytm jest cyklem, zwanym także sumą kontrolną. Standard ten charakteryzuje się prostotą i zarazem uniwersalnością - dzięki niemu można uzyskać najszerszy zakres danych. CRC jest jednym z najczęstszych algorytmów niekryptograficznych.

Z kolei podczas szyfrowania powszechnie stosowane są standardy MD4 i MD5. Innym popularnym algorytmem kryptograficznym jest SHA-1. W szczególności cechuje go rozmiar skrótu 160 bitów, który jest większy niż MD5 - ten standard obsługuje 128 bitów. Istnieją rosyjskie standardy dotyczące używania funkcji skrótu, - GOST R 34.11-94, a także zastąpienie go GOST R 34.11-2012. Można zauważyć, że wartość mieszania zapewniona przez algorytmy przyjęte w Federacji Rosyjskiej wynosi 256 bitów.

Omawiane standardy mogą być klasyfikowane z różnych powodów. Na przykład są tacy, którzy używają blokowych i specjalistycznych algorytmów. Prostocie obliczeń opartych na standardach pierwszego typu często towarzyszy ich niska prędkość. Dlatego jako alternatywa dla algorytmów blokowych mogą być zaangażowane te, które obejmują mniejszą liczbę operacji obliczeniowych. Zwyczajowo przypisuje się wysokie standardy, w szczególności wspomniane powyżej MD4, MD5, a także SHA. Rozważ szczegółowo szczegóły specjalnych algorytmów haszowania na przykładzie SHA.

Funkcje algorytmu SHA

Korzystanie z funkcji mieszania opartych na standardzie SHA jest najczęściej przeprowadzane w obszarze opracowywania narzędzi do cyfrowego podpisywania dokumentów DSA. Jak zauważyliśmy powyżej, algorytm SHA obsługuje 160-bitowy skrót (dostarczający tak zwanego "skrótu" sekwencji znaków). Początkowo uznany standard dzieli tablicę danych na bloki 512 bitów. Jeśli to konieczne, jeśli długość ostatniego bloku nie osiąga określonej cyfry, struktura plików jest uzupełniona 1 i konieczną liczbą zer. Również na końcu odpowiedniego bloku mieści się kod ustalający długość wiadomości. Rozważany algorytm obejmuje 80 funkcji logicznych, za pomocą których przetwarzane są 3 słowa, reprezentowane w 32 bitach. Również w standardowym SHA zapewnione jest użycie 4 stałych.

Porównanie algorytmów skrótu

Przyjrzyjmy się, jak korelują właściwości funkcji mieszania związanych z różnymi standardami, na przykład porównując cechy rosyjskiego standardu GOST R 34.11-94 i amerykańskiego SHA, które omówiliśmy powyżej. Przede wszystkim należy zauważyć, że algorytm opracowany w Federacji Rosyjskiej obejmuje wdrożenie 4 operacji szyfrowania na 1 cykl. Odpowiada to 128 rundom. Z kolei na 1 rundę, po aktywowaniu SHA, zakłada się, że oblicza się około 20 poleceń, a całkowita liczba rund wynosi 80. W ten sposób użycie SHA pozwala na przetworzenie 512 bitów danych źródłowych podczas 1 cyklu. W tym samym czasie rosyjski standard jest w stanie wykonywać operacje na cykl 256 bitów danych.

Specyfika najnowszego rosyjskiego algorytmu

Powyżej, odnotowaliśmy, że standard GOST R 34.11-94 został zastąpiony przez nowszy - GOST R 34.11-2012 "Stribog". Szczegółowo badamy jego szczegóły.

Dzięki temu standardowi można zaimplementować kryptograficzne funkcje mieszające, tak jak w przypadku omówionych powyżej algorytmów. Można zauważyć, że najnowszy rosyjski standard obsługuje blok danych wejściowych w ilości 512 bitów. Główne zalety GOST R 34.11-2012:

• wysoki poziom bezpieczeństwa związany z pękaniem szyfru;
• niezawodność, poparta wykorzystaniem sprawdzonych struktur;
• operatywne obliczanie funkcji skrótu, brak przekształceń w algorytmie, które komplikują konstrukcję funkcji i spowalniają obliczenia.

Znane zalety nowego rosyjskiego standardu szyfrowania kryptograficznego pozwalają na jego wykorzystanie przy organizacji przepływu dokumentów, który spełnia najbardziej rygorystyczne kryteria określone w przepisach prawnych.

Specyfika kryptograficznych funkcji skrótu

Rozważmy bardziej szczegółowo, w jaki sposób typy algorytmów, które badamy, mogą być wykorzystywane w dziedzinie kryptografii. Kluczowym wymaganiem dla odpowiednich funkcji jest odporność na kolizje, o której wspomnieliśmy powyżej. Oznacza to, że powielone wartości funkcji mieszania nie powinny być tworzone, jeśli wartości te są już obecne w strukturze sąsiedniego algorytmu. Inne kryteria wymienione powyżej powinny również spełniać funkcje kryptograficzne. Oczywiste jest, że zawsze istnieje teoretyczna możliwość odzyskania pliku źródłowego na podstawie skrótu, zwłaszcza jeśli istnieje potężne narzędzie komputerowe w dostępie. Jednak scenariusz ten powinien zostać zminimalizowany dzięki solidnym algorytmom szyfrowania. A zatem obliczenie funkcji skrótu będzie bardzo trudne, jeśli jej moc obliczeniowa odpowiada formule 2 ^ {n / 2}.

Innym ważnym kryterium algorytmu kryptograficznego jest zmiana wartości mieszania w przypadku korekty początkowego zestawu danych. Powyżej zauważyliśmy, że standardy szyfrowania powinny mieć czułość 1-bitową. Ta właściwość jest kluczowym czynnikiem zapewniającym niezawodną ochronę dostępu do plików za pomocą hasła.

Systemy iteracyjne

Sprawdzamy teraz, jak można budować algorytmy kryptograficznego mieszania. Wśród najbardziej powszechnych schematów rozwiązywania tego problemu jest zastosowanie iteracyjnego modelu sekwencyjnego. Opiera się on na wykorzystaniu tak zwanej funkcji kompresji, w której liczba bitów wejściowych jest znacznie większa niż liczba zapisana na wyjściu.

Oczywiście funkcja kompresji musi spełniać niezbędne kryteria wytrzymałości kryptograficznej. W schemacie interaktywnym pierwsza operacja przetwarzania wejściowego strumienia danych jest podzielona na bloki, których rozmiar jest obliczany w bitach. Odpowiedni algorytm obejmuje także zmienne czasowe o zadanej liczbie bitów. Pierwsza wartość używa dobrze znanej liczby, a kolejne bloki danych są łączone z wartością danej funkcji na wyjściu. Wartość skrótu staje się bitem wyjściowym ostatniej iteracji, która uwzględnia cały strumień wejściowy, w tym pierwszą wartość. Dostarczany jest tak zwany "efekt lawinowy" mieszania.

Główną trudnością charakteryzującą mieszanie zaimplementowane jako schemat iteracyjny jest to, że czasami trudno jest budować funkcje haszujące, jeśli strumień wejściowy nie jest identyczny z rozmiarem bloku, w którym dzielona jest początkowa tablica danych. Ale w tym przypadku standard mieszania może być sformułowany w algorytmy, dzięki którym oryginalny strumień może zostać rozszerzony w taki czy inny sposób.

W niektórych przypadkach tak zwane algorytmy wieloprzebiegowe mogą być zaangażowane w przetwarzanie danych w ramach schematu iteracyjnego. Sugerują one powstawanie jeszcze bardziej intensywnego "efektu lawinowego". Taki scenariusz zakłada tworzenie powtarzających się tablic danych, a dopiero potem następuje ekspansja.

Zablokuj algorytm

Funkcja kompresji może być również oparta na algorytmie blokowym, za pomocą którego wykonywane jest szyfrowanie. Tak więc, w celu zwiększenia poziomu bezpieczeństwa, można użyć bloków danych, które mają być mieszane w bieżącej iteracji, jako klucz, oraz wyniku operacji uzyskanych podczas wykonywania funkcji kompresji przed - jako dane wejściowe. W rezultacie ostatnia iteracja zapewni wyjście algorytmu. Zabezpieczenia hasłowe będą korelować z solidnością zaangażowanego algorytmu.

Jednak, jak zauważyliśmy powyżej, biorąc pod uwagę różne typy funkcji haszujących, algorytmom blokującym często towarzyszy potrzeba użycia dużych mocy obliczeniowych. Jeśli są niedostępne, szybkość przetwarzania plików może nie być wystarczająca do rozwiązania praktycznych problemów związanych z używaniem funkcji skrótu. W tym samym czasie wymagana odporność na kryptoopory może zostać zrealizowana przy niewielkiej liczbie operacji ze źródłowymi strumieniami danych, w szczególności algorytmy, które rozważaliśmy, są przystosowane do rozwiązywania takich problemów - MD5, SHA, rosyjskie standardy szyfrowania kryptograficznego.