Dlaczego XOR jest domyślnym sposobem łączenia skrótów?


145

Powiedzmy, że masz dwa skróty H(A)i H(B)chcesz je połączyć. Czytałem, że dobrym sposobem na połączenie dwóch skrótów jest do XORnich np XOR( H(A), H(B) ).

Najlepsze wyjaśnienie, jakie znalazłem, zostało pokrótce omówione tutaj w tych wytycznych dotyczących funkcji skrótu :

XORowanie dwóch liczb z mniej więcej losowym rozkładem daje w wyniku kolejną liczbę, która nadal ma mniej więcej losowy rozkład *, ale która teraz zależy od tych dwóch wartości.
...
* Na każdym bicie z dwóch liczb do połączenia wyprowadzane jest 0, jeśli dwa bity są równe, w przeciwnym razie 1. Innymi słowy, w 50% kombinacji zostanie wyprowadzone 1. Więc jeśli każdy z dwóch bitów wejściowych ma z grubsza 50-50 szans na 0 lub 1, to tak samo będzie z bitem wyjściowym.

Czy możesz wyjaśnić intuicję i / lub matematykę, dlaczego XOR powinien być domyślną operacją łączenia funkcji skrótu (zamiast OR lub AND itp.)?


20
Myślę, że właśnie to zrobiłeś;)
Massa

22
zwróć uwagę, że XOR może, ale nie musi, być „dobrym” sposobem „łączenia” skrótów, w zależności od tego, co chcesz w „kombinacji”. XOR jest przemienny: XOR (H (A), H (B)) jest równe XOR (H (B), H (A)). Oznacza to, że XOR nie jest właściwym sposobem tworzenia pewnego rodzaju skrótu uporządkowanej sekwencji wartości, ponieważ nie rejestruje kolejności.
Thomas Pornin

6
Oprócz problemu z zamówieniem (komentarz powyżej) jest problem z równymi wartościami. XOR (H (1), H (1)) = 0 (dla dowolnej funkcji H), XOR (H (2), H (2)) = 0 i tak dalej. Dla dowolnego N: XOR (H (N), H (N)) = 0. Równe wartości zdarzają się dość często w rzeczywistych aplikacjach, co oznacza, że ​​wynik XOR będzie wynosił 0 zbyt często, aby można go było uznać za dobry hash.
Andrei Galatyn

Czego używasz do uporządkowanej sekwencji wartości? Powiedzmy, że chciałbym utworzyć skrót znacznika czasu lub indeksu. (MSB mniej ważne niż LSB). Przepraszamy, jeśli ten wątek ma 1 rok.
Alexis

Odpowiedzi:


120

Zakładając jednolicie losowe (1-bitowe) dane wejściowe, rozkład prawdopodobieństwa wyjścia funkcji AND wynosi 75% 0i 25% 1. I odwrotnie, OR wynosi 25% 0i 75% 1.

Funkcja XOR wynosi 50% 0i 50% 1, dlatego dobrze jest łączyć jednolite rozkłady prawdopodobieństwa.

Można to zobaczyć, wypisując tabele prawdy:

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

 a | b | a OR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    1

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

Ćwiczenie: Ile funkcji logicznych ma dwa 1-bitowe wejścia ai bma taki jednolity rozkład wyjściowy? Dlaczego XOR jest najbardziej odpowiedni do celu określonego w pytaniu?


24
odpowiadając na ćwiczenie: z 16 możliwych różnych operacji a XXX b (0, a & b, a > b, a, a < b, b, a % b, a | b, !a & !b, a == b, !b, a >= b, !a, a <= b, !a | !b, 1)następujące mają rozkłady 50% -50% zera i 1, przy założeniu, że a i b mają rozkłady 50% -50% zera i jedynki: a, b, !a, !b, a % b, a == bczyli odwrotnie of XOR (EQUIV) mógł być również użyty ...
Massa

7
Greg, to niesamowita odpowiedź. Żarówka zapaliła się dla mnie, gdy zobaczyłem twoją oryginalną odpowiedź i spisałem własne tabele prawdy. Rozważyłem odpowiedź @ Massy na temat tego, jak istnieje 6 odpowiednich operacji do utrzymania dystrybucji. I chociaż a, b, !a, !bbędą miały taki sam rozkład, jak ich odpowiednie dane wejściowe, tracisz entropię drugiego wejścia. Oznacza to, że XOR jest najbardziej odpowiedni do łączenia skrótów, ponieważ chcemy uchwycić entropię zarówno z a, jak i b.
Nate Murray

1
Oto artykuł wyjaśniający, że bezpieczne łączenie skrótów, w których każda funkcja jest wywoływana tylko raz, nie jest możliwe bez wyprowadzenia mniejszej liczby bitów niż suma liczby bitów w każdej wartości skrótu. To sugeruje, że ta odpowiedź jest nieprawidłowa.
Tamás Szelei

3
@Massa Nigdy nie widziałem% używanego dla XOR lub nierównego.
Buge

7
Jak wskazuje Yakk , XOR może być niebezpieczny, ponieważ daje zero dla identycznych wartości. To oznacza, (a,a)i (b,b)oba produkty zera, co w wielu (większość?) Przypadkach znacznie zwiększa prawdopodobieństwo kolizji w strukturach danych opartych hash.
Drew Noakes

170

xorjest niebezpieczną funkcją domyślną do użycia podczas mieszania. Jest lepszy niż andi or, ale to niewiele mówi.

xorjest symetryczny, więc kolejność elementów zostaje utracona. Więc "bad"hash będzie łączyć to samo co "dab".

xor odwzorowuje parami identyczne wartości na zero i należy unikać mapowania „wspólnych” wartości na zero:

Jest więc (a,a)mapowane na 0, a (b,b)także na 0. Ponieważ takie pary są prawie zawsze bardziej powszechne, niż może to sugerować przypadkowość, kończy się z dużą liczbą kolizji na poziomie zerowym, niż powinieneś.

Z tymi dwoma problemami xorkończy się sumatorem mieszania, który wygląda na w połowie przyzwoicie, ale nie po dalszej kontroli.

Na nowoczesnym sprzęcie, dodawanie zwykle tak szybko, jak xor(trzeba przyznać, że prawdopodobnie zużywa więcej energii, aby to zrobić). Dodawanie tabeli prawdy jest podobne do tego xorna danym bicie, ale wysyła również trochę do następnego bitu, gdy obie wartości są równe 1. Oznacza to, że usuwa mniej informacji.

Więc hash(a) + hash(b)jest lepsze niż hash(a) xor hash(b)w przypadku a==b, gdy wynikiem jest hash(a)<<1zamiast 0.

To pozostaje symetryczne; więc "bad"i "dab"otrzymuję ten sam rezultat pozostaje problemem. Możemy złamać tę symetrię niewielkim kosztem:

hash(a)<<1 + hash(a) + hash(b)

aka hash(a)*3 + hash(b). ( hash(a)zaleca się jednorazowe obliczenie i przechowywanie, jeśli używasz rozwiązania zmianowego). Każda nieparzysta stała zamiast 3będzie bijektywnie odwzorowywać " k-bit" liczbę całkowitą bez znaku na siebie, ponieważ mapowanie na liczbach całkowitych bez znaku jest 2^kdla niektórych matematyczne modulo k, a każda nieparzysta stała jest względnie pierwsza 2^k.

Aby uzyskać jeszcze bardziej wyszukaną wersję, możemy sprawdzić boost::hash_combine, co jest efektywne:

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

tutaj dodajemy razem kilka przesuniętych wersji seedze stałą (która jest w zasadzie losowym 0s i 1s - w szczególności jest to odwrotność złotego podziału jako 32-bitowy ułamek z punktem stałym) z dodatkiem i xor. To łamie symetrię i wprowadza pewien „szum”, jeśli przychodzące wartości skrótu są słabe (tj. Wyobraź sobie, że każdy komponent hashuje do 0 - powyższe działa dobrze, generując rozmazanie 1i 0s po każdym połączeniu. Mój naiwny 3*hash(a)+hash(b)po prostu wyświetla 0in ta walizka).

(Dla tych, którzy nie znają języka C / C ++, a size_tjest liczbą całkowitą bez znaku, która jest wystarczająco duża, aby opisać rozmiar dowolnego obiektu w pamięci. W systemie 64-bitowym jest to zwykle 64-bitowa liczba całkowita bez znaku. W systemie 32-bitowym , 32-bitowa liczba całkowita bez znaku).


Dobra odpowiedź Yakk. Czy ten algorytm działa równie dobrze w systemach 32-bitowych i 64-bitowych? Dzięki.
Dave,

1
@dave dodaj więcej bitów do 0x9e3779b9.
Yakk - Adam Nevraumont

10
OK, żeby zakończyć ... tutaj jest 64-bitowa stała pełnej precyzji (obliczona z długimi liczbami podwójnymi i długimi liczbami bez znaku): 0x9e3779b97f4a7c16. Co ciekawe, nadal jest równy. Ponowne wykonanie tego samego obliczenia przy użyciu PI zamiast złotego współczynnika daje: 0x517cc1b727220a95, co jest nieparzyste, a nie parzyste, a zatem prawdopodobnie „więcej pierwsze” niż inna stała. Użyłem: std :: cout << std :: hex << (unsigned long long) ((1,0L / 3,14159265358979323846264338327950288419716939937510L) * (powl (2,0L, 64,0L))) << std :: endl; z cout.precision (numeric_limits <long double> :: max_digits10); Jeszcze raz dziękuję Yakk.
Dave

2
@Dave regułą odwrotnego złotego podziału dla tych przypadków jest pierwsza nieparzysta liczba równa lub większa niż obliczenie, które wykonujesz. Więc po prostu dodaj 1. Jest to ważna liczba, ponieważ sekwencja N * stosunek, mod maksymalny rozmiar (tutaj 2 ^ 64) umieszcza następną wartość w sekwencji dokładnie w tym stosunku w środku największej przerwy w liczby. Aby uzyskać więcej informacji, wyszukaj w Internecie hasło „Haszowanie Fibonacciego”.
Scott Carey,

1
@Dave właściwy numer to 0.9E3779B97F4A7C15F39 ... Zobacz link . Możesz cierpieć z powodu zasady okrągłej do parzystej (która jest dobra dla księgowych) lub po prostu, jeśli zaczniesz od dosłownej stałej sqrt (5), kiedy odejmiesz 1, usuniesz bit o najwyższym porządku, a kawałek musiał zostać utracony.
migle

29

Pomimo swoich poręcznych właściwości mieszania bitów, XOR nie jest dobrym sposobem łączenia hashów ze względu na swoją przemienność. Zastanów się, co by się stało, gdybyś zapisał permutacje {1, 2,…, 10} w tablicy z 10 krotkami.

Dużo lepszym wyborem jest to m * H(A) + H(B), gdzie m to duża liczba nieparzysta.

Kredyt: Powyższy sumator był wskazówką od Boba Jenkinsa.


2
Czasami przemienność jest dobrą rzeczą, ale xor jest kiepskim wyborem nawet wtedy, ponieważ wszystkie pary pasujących przedmiotów zostaną zhaszowane do zera. Suma arytmetyczna jest lepsza; hash pary pasujących elementów zachowa tylko 31 bitów użytecznych danych, a nie 32, ale jest to o wiele lepsze niż zachowanie zera. Inną opcją może być obliczenie sumy arytmetycznej jako a, longa następnie połączenie górnej części z dolną częścią.
supercat

1
m = 3jest właściwie dobrym wyborem i bardzo szybkim w wielu systemach. Zauważ, że dla każdego nieparzystego mmnożenia liczb całkowitych jest modulo 2^32lub 2^64i dlatego jest odwracalne, więc nie tracisz żadnych bitów.
Stefan Karpiński

Co się stanie, gdy wyjdziesz poza MaxInt?
uciążliwy

2
zamiast dowolnej liczby nieparzystej należy wybrać liczbę pierwszą
TermoTux

2
@Infinum, które nie jest konieczne przy łączeniu skrótów.
Marcelo Cantos

17

Xor może być "domyślnym" sposobem łączenia hashów, ale odpowiedź Grega Hewgilla pokazuje również, dlaczego ma swoje pułapki: xor dwóch identycznych wartości hash wynosi zero. W prawdziwym życiu identyczne skróty są częstsze, niż można by się spodziewać. Może się wtedy okazać, że w tych (nie tak rzadkich) przypadkach narożnych wynikowe połączone skróty są zawsze takie same (zero). Zderzenia z haszowaniem byłyby dużo, dużo częstsze niż się spodziewasz.

W wymyślonym przykładzie możesz łączyć zaszyfrowane hasła użytkowników z różnych zarządzanych witryn internetowych. Niestety, wielu użytkowników ponownie używa swoich haseł, a zaskakująca część powstałych skrótów wynosi zero!


Mam nadzieję, że wymyślony przykład nigdy się nie wydarzy, hasła powinny być solone.
user60561

8

Jest coś, co chciałbym wyraźnie wskazać innym osobom, które znajdą tę stronę. AND i OR ograniczają wydajność, jak BlueRaja - Danny Pflughoe próbuje wskazać, ale można to lepiej zdefiniować:

Najpierw chcę zdefiniować dwie proste funkcje, których użyję do wyjaśnienia tego: Min () i Max ().

Min (A, B) zwróci wartość, która jest mniejsza między A i B, na przykład: Min (1, 5) zwraca 1.

Max (A, B) zwróci większą wartość między A i B, na przykład: Max (1, 5) zwraca 5.

Jeśli otrzymasz: C = A AND B

Wtedy możesz stwierdzić, że C <= Min(A, B)wiemy o tym, ponieważ nie ma nic, co możesz ORAZ z 0 bitami A lub B, aby uzyskać jedynki. Zatem każdy bit zerowy pozostaje bitem zerowym, a każdy bit ma szansę stać się bitem zerowym (a tym samym mniejszą wartością).

Z: C = A OR B

Jest odwrotnie: w C >= Max(A, B)tym przypadku widzimy następstwo funkcji AND. Żaden bit, który jest już jedynką, nie może zostać zmieniony na zero, więc pozostaje jedynką, ale każdy bit zerowy ma szansę stać się jedynką, a tym samym większą liczbą.

Oznacza to, że stan wejścia nakłada ograniczenia na wyjście. Jeśli ORAZ coś z 90, wiesz, że wynik będzie równy lub mniejszy niż 90, niezależnie od tego, jaka jest inna wartość.

W przypadku XOR nie ma dorozumianych ograniczeń opartych na danych wejściowych. Istnieją specjalne przypadki, w których możesz stwierdzić, że jeśli XOR bajt z wartością 255, otrzymasz odwrotność, ale każdy możliwy bajt może zostać z tego wyprowadzony. Każdy bit ma szansę na zmianę stanu w zależności od tego samego bitu w innym operandzie.


6
Można powiedzieć, że ORjest bitowe max i ANDjest bitowe min .
Paŭlo Ebermann

Bardzo dobrze powiedziane Paulo Ebermann. Miło cię tu widzieć, a także Crypto.SE!
Corey Ogburn

Stworzyłem filtr, który zawiera wszystko, co otagowano kryptografię , a także zmiany na stare pytania. W ten sposób znalazłem tutaj twoją odpowiedź.
Paŭlo Ebermann

3

Jeśli masz XORlosowe wejście z polaryzowanym wejściem, wyjście jest losowe. To samo nie dotyczy ANDlub OR. Przykład:

00101001 XOR 00000000 = 00101001
00101001 I 00000000 = 00000000
00101001 LUB 11111111 = 11111111

Jak wspomina @Greg Hewgill, nawet jeśli oba wejścia są losowe, użycie ANDlub ORspowoduje odchylenie wyjścia.

Powodem, dla którego używamy XORczegoś bardziej złożonego, jest to, że nie ma potrzeby: XORdziała idealnie i jest niesamowicie głupio-szybkie.


1

Zakryj dwie lewe kolumny i spróbuj ustalić, jakie dane wejściowe wykorzystują tylko dane wyjściowe.

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

Kiedy zobaczyłeś 1-bit, powinieneś był się domyślić, że oba wejścia mają wartość 1.

Teraz zrób to samo dla XOR

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

XOR nie zdradza nic na temat danych wejściowych.


0

Kod źródłowy różnych wersji hashCode()w java.util.Arrays to świetne odniesienie do solidnych, ogólnych algorytmów haszujących. Są łatwo zrozumiałe i przetłumaczone na inne języki programowania.

Z grubsza rzecz biorąc, większość hashCode()implementacji z wieloma atrybutami jest zgodna z tym wzorcem:

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

Możesz przeszukać inne pytania i odpowiedzi StackOverflow, aby uzyskać więcej informacji o magii 31i dlaczego kod Java używa go tak często. Jest niedoskonały, ale ma bardzo dobre ogólne właściwości użytkowe.


2
Domyślny hash Java „pomnóż przez 31 i dodaj / akumuluj” jest obciążony kolizjami (np. stringKolizjami z string + "AA"IIRC) i dawno temu żałowali, że nie wprowadzili tego algorytmu do specyfikacji. To powiedziawszy, użycie większej liczby nieparzystej z większą liczbą ustawionych bitów i dodanie przesunięć lub obrotów rozwiązuje ten problem. „Mix” MurmurHash3 robi to.
Scott Carey,

0

XOR nie ignoruje niektórych danych wejściowych, czasem takich jak OR i AND .

Jeśli weźmiesz na przykład AND (X, Y) i wprowadzisz do wejścia X fałsz, to wejście Y nie ma znaczenia ... i prawdopodobnie chciałoby się, aby dane wejściowe miały znaczenie podczas łączenia hashów.

Zażycie XOR (X, Y), a następnie OBU wejść ZAWSZE sprawa. Nie byłoby wartości X, gdzie Y nie ma znaczenia. Jeśli zmieni się X lub Y, dane wyjściowe to odzwierciedlą.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.