Haszowanie Pearsona
Haszowanie Pearsona to funkcja haszująca przeznaczona do szybkiego wykonywania na procesorach z rejestrami 8-bitowymi . Biorąc pod uwagę dane wejściowe składające się z dowolnej liczby bajtów, generuje na wyjściu pojedynczy bajt, który jest silnie zależny od każdego bajtu wejścia. Jego implementacja wymaga tylko kilku instrukcji oraz 256-bajtowej tablicy wyszukiwania zawierającej permutację wartości od 0 do 255.
Ta funkcja skrótu to CBC-MAC , która wykorzystuje 8-bitowy szyfr podstawieniowy zaimplementowany za pośrednictwem tabeli podstawieniowej . Szyfr 8-bitowy ma znikome bezpieczeństwo kryptograficzne, więc funkcja haszująca Pearsona nie jest silna kryptograficznie , ale jest przydatna do implementacji tablic mieszających lub jako kod sprawdzający integralność danych , do których celów oferuje następujące korzyści:
- Jest to niezwykle proste.
- Działa szybko na procesorach o ograniczonych zasobach.
- Nie ma prostej klasy wejść, dla których kolizje (identyczne wyjścia) są szczególnie prawdopodobne.
- Biorąc pod uwagę mały, uprzywilejowany zestaw danych wejściowych (np. słowa zarezerwowane dla kompilatora ), tablicę permutacji można dostosować tak, aby te dane wejściowe dawały różne wartości skrótu, tworząc tak zwaną idealną funkcję skrótu .
- Dwa łańcuchy wejściowe różniące się dokładnie o jeden znak nigdy się nie kolidują. Np. zastosowanie algorytmu do łańcuchów ABC i AEC nigdy nie da tej samej wartości.
Jedną z jego wad w porównaniu z innymi algorytmami haszującymi przeznaczonymi dla procesorów 8-bitowych jest sugerowana 256-bajtowa tablica wyszukiwania, która może być zbyt duża dla małego mikrokontrolera z rozmiarem pamięci programu rzędu setek bajtów. Obejściem tego problemu jest użycie prostej funkcji permutacji zamiast tabeli przechowywanej w pamięci programu. Jednak użycie zbyt prostej funkcji, takiej jak T[i] = 255-i , częściowo podważa użyteczność funkcji skrótu jako anagramów spowoduje uzyskanie tej samej wartości skrótu; Z drugiej strony użycie zbyt złożonej funkcji wpłynie negatywnie na szybkość. Użycie funkcji zamiast tabeli pozwala również na zwiększenie rozmiaru bloku. Takie funkcje naturalnie muszą być bijekcyjne , podobnie jak ich warianty tablicowe.
Algorytm można opisać za pomocą następującego pseudokodu , który oblicza skrót wiadomości C za pomocą tablicy permutacji T :
algorytm mieszania Pearsona to h := 0 dla każdego c w pętli C h := T[ h xor c ] koniec pętli return h
Zmienna mieszająca ( h ) może być inicjowana w różny sposób, np. do długości danych ( C ) modulo 256; ten konkretny wybór jest używany w poniższym przykładzie implementacji Pythona.
Przykładowe wdrożenia
Python , wyjście 8-bitowe
Parametr 'table' wymaga pseudolosowo przetasowanej listy z zakresu [0..255]. Można to łatwo wygenerować, używając wbudowanej zakresu Pythona i używając random.shuffle do permutacji:
0
z losowego importu shuffle example_table = list ( range ( , 256 )) shuffle ( example_table ) def hash8 ( wiadomość : str , tabela ) -> int : """Pearson hashing.""" hash = len ( wiadomość ) % 256 dla i W
wiadomość : hash = table [ hash ^ ord ( i )] zwraca hash
C# , 8-bitowy
0
public class PearsonHashing { public byte Hash ( string input ) { const byte [] T = { /* Permutacja 0-255 */ }; skrót bajtowy = ; bajt [] bajtów = Kodowanie . UTF8 . GetBytes ( dane wejściowe ); foreach ( var b w bajtach ) {
hash = T [( bajt ) ( hash ^ b )]; } zwróć skrót ; } }