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

38

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)”?

terminology hashing

— gracedlamb
źródło

8

Wikipedia zawiera szczegółowe artykuły na temat tablic mieszających i funkcji kryptograficznych . Czego szukasz, czego tam nie ma?

— David Richerby,

1

Wymieniłeś już wiele zastosowań terminu „skrót”, a jest ich więcej. Więc jak dokładnie oczekujesz odpowiedzi na „co to właściwie jest?”

— Raphael

4

„Hashe” w tym sensie jest skrótem od „Hash tabel”, np. Tabel używających skrótów do organizowania kluczy. To trochę jak nazywanie benzyny „gazem” - nie oczekujesz, że „gaz” będzie gazowy lub że gaz będzie miał właściwości podobne do benzyny, prawda? Dzieje się tak przez cały czas - w szczególności skracanie jest bardzo częstym źródłem nakładania się słów.

— Luaan,

1

„Nie ma definicji tego słowa - nikt nie wie, co to jest skrót”. - The Devil's Dictionary

— jpmc26 06.04.16

Co do różnych ciągów myślenia, czym jest funkcja skrótu: funkcja skrótu to po prostu jakaś funkcja z wieloma właściwościami, ale nie jest to tak zdefiniowane, że jest istotne, to są właściwości, które chcemy, aby miały - które wywodzimy z tego, jak chcemy korzystać z funkcji - to istotne. Ponieważ chcemy go używać do szybkiego uzyskiwania dostępu do danych, chcemy, aby był wydajnie obliczalny. Ponieważ nie mamy dostępnej nieskończonej przestrzeni, chcemy, aby kododomena była skończona. Ponieważ chcemy uniknąć kolizji tak dobrze, jak to możliwe, chcemy, aby funkcja skrótu równomiernie rozkładała skróty.

— G. Bach,

44

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$

Powinno być łatwe do obliczenia i
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:

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.
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.
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.
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.

— usul
źródło

1

Dobre wyjaśnienie, ale nie zgadzam się z „bardzo mało prawdopodobnym”. Zobacz: programmers.stackexchange.com/questions/49550/... : zderzenie zrobić wystąpić, a czasem zaskakująco często.

— Olivier Dulac,

8

Należy również zauważyć, że w kontekście cyptografii termin „skrót” bardzo silnie implikuje operację „jednokierunkową”, której w praktyce nie można łatwo odwrócić. Gdy można to łatwo odwrócić, nazywa się to „szyfrowaniem”. Dlatego ludzie w Security.SE powiedzą ci, aby zawsze haszować hasła swoich klientów, nigdy ich nie szyfrować.

— Ixrec,

4

Hash, który nie „rozprzestrzenia się”, jest nadal hashem, być może niezbyt dobrym dla twojej aplikacji.

— Stop Harming Monica,

1

Jasne, to są wszystkie dobre punkty.

— usul

10

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.

— Pharap
źródło

2

Nie jestem pewien, czy naprawdę jest niewłaściwe nazywanie tabeli skrótu lub funkcji skrótu „hashem” (nie wydaje się gorsze niż na przykład użycie słowa „Waszyngton” w znaczeniu „Stany Zjednoczone”, jak w „ Waszyngton ostrożnie przyjął oświadczenie Chin ”). Ale zgadzam się, że jest to mylące i dobrze, że wyrażasz to jasno w swojej odpowiedzi.

— David Richerby,

1

@DavidRicherby Formalnie powiedziałbym, że „hash” pracy jest niezdefiniowany. „Funkcja skrótu”, „wartość skrótu”, „tablica skrótu” i „mieszanie łańcucha” wszystkie mają dokładne definicje matematyczne, ale „skrót” jest niejednoznaczny. Podobnie wiem, co rozumiesz przez „Waszyngton”, ale twoje zdanie ma sens, jeśli interpretuję „Waszyngton” jako „George Washington” lub „Denzel Washington”, a nie „Miasto Waszyngton”, co jest wysoce nieformalnym sposobem odnieść się do rządu federalnego. Podsumowując: uważaj, aby nie pomylić „wiedząc, co masz na myśli” w przypadku ścisłej definicji formalnej.

— Mike Ounsworth,

@DavidRicherby To nie jest tak naprawdę analogiczna analogia. Nieprawidłowość jest dyskusyjna, ale nieformalność nie.

— Pharap

2

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.

— Przestań krzywdzić Monikę
źródło

I nadal mam zastrzeżenia do twojego pierwszego zdania, ponieważ podczas mieszania 32-znakowych haseł za pomocą SHA-512, przestrzeń wejściowa jest w rzeczywistości mniejsza niż przestrzeń wyjściowa. Podczas łączenia funkcji skrótu razem domena i zakres są takie same; wielkość przestrzeni wejściowej jest nieistotna. Odpowiedź Pharapa ma poprawną definicję: „Funkcja skrótu to dowolna funkcja o wyjściu o stałej długości”. To jest wszystko, czego potrzebujesz, wynikają z tego wszystkie inne warunki, o których mówisz.

— Mike Ounsworth,

@MikeOunsworth, ale domeną SHA-512 są ciągi binarne o dowolnej długości. Podejrzewam, że mógłbym ukraść sformułowania Pharaps, ale starałem się wyraźnie określić warunki dla korzyści PO. Nie jestem pewien, czy „o stałej długości” jest konieczne, ani jednoznacznie zdefiniowane.

— Stop Harming Monica,

@OrangeDog Ok, ale mogę owinąć SHA-512 wewnątrz funkcji o nazwie, MikesHash()która przyjmuje ciągi o długości 12 i przekazuje je do SHA-512 i zwraca dane wyjściowe. Jestem prawie pewien, że MikesHash()nadal spełnia definicję funkcji skrótu. (W praktyce masz rację, używane przez nas funkcje skrótu akceptują dane wejściowe o dowolnej długości, ale nie sądzę, aby coś nie spełniało funkcji skrótu, jeśli tak nie jest.)

— Mike

@ MikeOunsworth na równi mogę owinąć tak, że dane wyjściowe są obcięte lub wypełnione, jeśli msb jest jeden. Wyjście nie ma już ustalonej długości, ale czy nadal jest funkcją skrótu?

— Przestań krzywdzić Monikę

@OrangeDog Powiedziałbym, że nie. Cały czas chodziło mi o to, że funkcja skrótu musi być odwzorowana na wyjście o stałym rozmiarze, ale wielkość wejściowa jest nieistotna. Dotarliśmy bardzo daleko od tematu. Twoja odpowiedź ma w sobie coś dobrego, bądź ostrożny z formalną definicją ;-)

— Mike Ounsworth,

0

Ś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.

— Jesse MacDougall
źródło

3

Jest to tylko jedno użycie skrótu. Istnieje wiele innych zastosowań.

— Yuval Filmus

Witamy na stronie! Wykorzystanie skrótów kryptograficznych jako sum kontrolnych jest już objęte zaakceptowaną odpowiedzią, więc twoja odpowiedź nie dodaje nic nowego, a zajmuje dużo miejsca na ekranie.

— David Richerby,

-1

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

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.

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”.

— nponeccop
źródło