Czym dokładnie (i dokładnie) jest „skrót”?

Słyszałem, że słowo „hash” jest używane w różnych kontekstach (w całym świecie komputerów) o różnych znaczeniach. Na przykład w książce Learn Python the Hard Way w rozdziale o słownikach jest powiedziane: „Python nazywa je„ dyktandami ”.„ Inne języki nazywają je „hashe”. ”

Innym powszechnym użyciem tego słowa jest szyfrowanie. Słyszałem także (i czytałem) osoby używające słowa „hash” jako specyficznej funkcji w programowaniu wysokiego poziomu.

Co to właściwie jest?

Czy ktokolwiek (z czasem i posiadający wiedzę) może uprzejmie wyjaśnić drobiazgowe „haszysz (lub hasze)”?

Artykuł w Wikipedii na temat funkcji skrótu jest bardzo dobry, ale przedstawię tutaj swoje zdanie.

Co to jest skrót?

„Hash” jest naprawdę szerokim terminem o różnych formalnych znaczeniach w różnych kontekstach. Nie ma jednej idealnej odpowiedzi na twoje pytanie. Wyjaśnię ogólną podstawową koncepcję i wymienię niektóre z najczęstszych zastosowań tego terminu.

„Hash” to funkcja określana jako funkcja hash, która przyjmuje jako obiekty wejściowe i wyprowadza ciąg lub liczbę. Obiekty wejściowe są zwykle elementami podstawowych typów danych, takich jak ciągi, liczby całkowite lub większe złożone z innych obiektów, takich jak struktury zdefiniowane przez użytkownika. Dane wyjściowe to zazwyczaj liczba lub ciąg znaków. Rzeczownik „skrót” często odnosi się do tego wyniku. Czasownik „skrót” często oznacza „zastosuj funkcję skrótu”. Główne właściwości, które powinna mieć funkcja skrótu to:$h$

1. Powinno być łatwe do obliczenia i
2. Wyniki powinny być stosunkowo małe.

Przykład:

Powiedzmy, że chcemy mieszać liczby w zakresie od 0 do 999,999,999 do liczby między 0 a 99. Jedną prostą funkcją skrótu może być .$h(x) = x \mod 100$

Wspólne dodatkowe właściwości:

W zależności od przypadku użycia możemy chcieć, aby funkcja skrótu spełniała dodatkowe właściwości. Oto kilka typowych dodatkowych właściwości:

1. Jednorodność : Często chcemy, aby skróty obiektów były wyraźne. Ponadto możemy chcieć, aby skróty były „rozłożone”. Jeśli chcę podzielić niektóre obiekty na 100 segmentów (więc wynikiem mojej funkcji skrótu jest liczba od 0 do 99), zazwyczaj mam nadzieję, że około 1/100 obiektów wyląduje w segmencie 0, około 1/100 wyląduje w wiadro 1 i tak dalej.

2. Kryptograficzna odporność na kolizje : czasami jest to brane jeszcze dalej, na przykład w kryptografii mogę chcieć funkcji skrótu takiej, że przeciwnikowi trudno jest znaleźć dwa różne dane wejściowe odwzorowane na to samo wyjście.

3. Kompresja : często chcę przesyłać dowolnie duże dane wejściowe do wyjścia o stałej wielkości lub stałej liczby segmentów.

4. Determinizm : Mogę chcieć funkcji skrótu, której dane wyjściowe nie zmieniają się między uruchomieniami, tzn. Dane wyjściowe funkcji skrótu na tym samym obiekcie zawsze pozostaną takie same. Może się to wydawać sprzeczne z powyższą jednolitością, ale jednym z rozwiązań jest jednokrotne wybranie funkcji skrótu, a nie zmiana jej między kolejnymi uruchomieniami.

Niektóre aplikacje

Jedną z powszechnych aplikacji są struktury danych, takie jak tablica skrótów, które są sposobem na implementację słowników. Tutaj przydzielasz trochę pamięci, powiedzmy 100 „segmentów”; następnie, gdy zostaniesz poproszony o zapisanie pary (klucz, wartość) w słowniku, umieścisz klucz w numerze 0-99 i zapiszesz parę w odpowiednim segmencie w pamięci. Następnie, gdy zostaniesz poproszony o wyszukanie klucza, umieścisz klucz w numerze 0-99 za pomocą tej samej funkcji skrótu i ​​sprawdzisz wiadro, aby sprawdzić, czy ten klucz tam jest. Jeśli tak, zwracasz jego wartość.

Pamiętaj, że możesz także implementować słowniki na inne sposoby, na przykład za pomocą drzewa wyszukiwania binarnego (jeśli twoje obiekty są porównywalne).

Inną praktyczną aplikacją są sumy kontrolne, które są sposobem na sprawdzenie, czy dwa pliki są takie same (na przykład plik nie był uszkodzony od poprzedniej wersji). Ponieważ jest mało prawdopodobne, aby funkcje skrótu odwzorowały dwa dane wejściowe na to samo wyjście, obliczasz i przechowujesz skrót pierwszego pliku, zwykle reprezentowany jako ciąg. Ten skrót jest bardzo mały, może tylko kilkadziesiąt znaków ASCII. Następnie, gdy zdobędziesz drugi plik, zaszyfrujesz go i sprawdzisz, czy dane wyjściowe są takie same. Jeśli tak, prawie na pewno jest to dokładnie ten sam plik bajt po bajcie.

Inną aplikacją jest kryptografia, w której te skróty powinny być trudne do „odwrócenia” - to znaczy, biorąc pod uwagę dane wyjściowe i funkcję skrótu, obliczenie danych wejściowych, które doprowadziły do ​​tego wyniku, powinno być trudne obliczeniowo. Jednym z zastosowań jest hasło: zamiast przechowywać samo hasło, przechowujesz kryptograficzny skrót hasła (być może z innymi składnikami). Następnie, gdy użytkownik wprowadzi hasło, obliczasz jego skrót i sprawdzasz, czy pasuje do poprawnego skrótu; jeśli tak, to mówisz, że hasło jest prawidłowe. (Teraz nawet ktoś, kto może sprawdzić i dowiedzieć się, jaki hash zapisany jest na serwerze, nie ma tak łatwego czasu udając, że jest użytkownikiem.) Ta aplikacja może być przypadkiem, gdy dane wyjściowe są tak samo długie lub dłuższe niż dane wejściowe, ponieważ dane wejściowe są tak krótkie.

Funkcja skrótu to funkcja, która pobiera dane wejściowe i generuje wartość o stałym rozmiarze. Na przykład możesz mieć funkcję skrótu, stringHashktóra akceptuje stringdowolną długość i tworzy 32-bitową liczbę całkowitą.

Zazwyczaj słuszne jest stwierdzenie, że wynikiem działania funkcji skrótu jest skrót (znany również jako wartość skrótu lub suma skrótu). Czasami jednak ludzie określają samą funkcję jako skrót . Jest to technicznie niepoprawne, ale zwykle pomijane, ponieważ ogólnie rozumie się (w kontekście), że osoba miała na myśli funkcję skrótu .

Typowym zastosowaniem funkcji skrótu jest implementacja tabeli skrótu . Tabela skrótów to struktura danych, która łączy wartości z innymi wartościami, zwykle nazywanymi kluczami. Robi to za pomocą funkcji skrótu na klawiszu, aby wygenerować wartość skrótu o stałej wielkości, której może użyć do szybkiego wyszukiwania przechowywanych danych. Nie będę szczegółowo omawiał, w jaki sposób to robi, ale kluczowym faktem jest to, że nazywa się to tablicą skrótu, ponieważ opiera się na funkcji skrótu do generowania wartości skrótu ( skrótów ).

Tutaj pojawia się pewne zamieszanie, ponieważ niektórzy ludzie (znowu, nieco niepoprawnie) nazywają tablicę skrótów jako skrót. Jak stwierdzono w innych odpowiedziach, czasami implementacja tabeli skrótów w danym języku odnosi się do tablicy skrótów jako skrótu (zwłaszcza Perl to robi, chociaż spodziewam się, że inne języki też to robią). Inne języki wybierają odniesienie do implementacji tabeli skrótów jako słownika. Python jest jednym z tych języków, ale ze względu na ich zakorzenienie wielu użytkowników Pythona skraca termin słownik do „dict”.

Tak więc, chociaż prawidłowe użycie terminu hash odnosi się do wartości skrótu generowanej przez funkcję skrótu , ludzie czasami używają tego terminu nieformalnie w odniesieniu do funkcji skrótu i tabel skrótu , co powoduje zamieszanie.

Funkcja skrótu to zasadniczo każda funkcja, w której obraz jest mniejszy niż domena . Wynik takiej funkcji f(x)można nazwać „skrótem x”.

W informatyce zwykle spotykamy dwie aplikacje funkcji skrótu.

Pierwszy dotyczy struktur danych, takich jak tabele skrótów , w których chcemy zamapować domenę kluczową (np. 32-bitowe liczby całkowite lub łańcuchy o dowolnej długości) na indeks tablicy (np. Liczby całkowite od 0 do 100). Celem jest maksymalizacja wydajności struktury danych; właściwości funkcji skrótu, które są zwykle pożądane, to prostota i jednolity rozkład wyjściowy.

Perl nazywa wbudowany typ tablicy asocjacyjnej „skrótem” , który wydaje się być przyczyną tego zamieszania. Nie znam innych języków, które to robią. Luźno struktura danych może być postrzegana jako sama funkcja skrótu (gdzie domeną jest bieżący zestaw kluczy), ale jest również implementowana jako tabela skrótów.

Drugi dotyczy kryptografii : uwierzytelniania wiadomości, weryfikacji hasła / podpisu itp. Domeną są zazwyczaj dowolne ciągi bajtów. W tym przypadku zwracamy uwagę na bezpieczeństwo - które czasami oznacza celowo niską wydajność - gdzie użytecznymi właściwościami są odporność na kolizje i odporność na zdjęcia.

Świetne pytanie, Basil Ajith,

Oto moja perspektywa tego, czym jest skrót dla czegoś, nad czym dzisiaj pracuję.

*

Użyj sumy kontrolnej, aby sprawdzić, czy plik tarball jest zgodny ze stroną pobierania

*

Zakłada czapkę audytora, to znaczy szatę czarodzieja

hash to wartość / ciąg / cokolwiek / etykieta. Upewnij się, że jest taki sam na twoim komputerze jak źródło pobierania.

Spróbuję po prostu dodać krótkie podsumowanie tego, co mówią inni.

Funkcja skrótu

Istnieje specjalny rodzaj funkcji zwanych funkcjami skrótu.

„SHA256 to dobrze znana funkcja skrótu, która jest kryptograficznie bezpieczna”

Trzy główne aplikacje to * tabele skrótów, * sumy kontrolne (kontrole integralności danych, np. Na dyskach twardych lub protokołach ADSL), * i kryptografia (różne formy uwierzytelniania kryptograficznego, w tym między innymi podpisy cyfrowe i bezpieczne przechowywanie haseł).

Stół Hash

Tabela skrótów to struktura danych do szybkiego wyszukiwania. Używa funkcji skrótu wewnętrznie, stąd nazwa.

„Bazy danych używają wewnętrznych tabel mieszania i drzew wyszukiwania, aby przyspieszyć wykonywanie żądań wyszukiwania”

Haszysz

1. słownikowy typ danych abstrakcyjnych

„Hash” to oficjalna nazwa wbudowanych słowników w Perlu. Są to tabele skrótów wewnętrznie, stąd nazwa. „Ten podprogram przyjmuje jako pierwszy argument skrót.” Te dni można wykorzystać dla dowolnej tablicy asocjacyjnej, niekoniecznie tabeli skrótów.

2. wynik zastosowania funkcji skrótu do niektórych danych wejściowych

„Udostępniane są skróty MD5 obrazów .iso w celu sprawdzenia ich integralności po pobraniu”.