Почему XOR является стандартным способом объединения хэшей?

Скажем, у вас есть два хэша H(A) и H(B), и вы хотите объединить их. Я читал, что хороший способ объединить два хэша - это XOR их, например XOR( H(A), H(B) ).

Лучшее объяснение, которое я нашел, кратко затронуто здесь в следующих рекомендациях по хеш-функциям :

XOR, когда два числа с примерно случайным распределением приводят к другому числу, все еще с примерно случайным распределением * но который теперь зависит от двух значений.
...
* В каждом бите двух чисел для объединения выводится 0, если два бита равны, иначе - 1. Другими словами, в 50% от комбинации, 1 будет выведен. Таким образом, если каждый из двух входных битов имеет примерно 50-50 шанс быть равным 0 или 1, то и выходной бит тоже будет.

Можете ли вы объяснить интуицию и / или математику, объясняющую, почему XOR должна быть операцией по умолчанию для объединения хеш-функций (а не ИЛИ или И и т. Д.)?

135
задан Nate Murray 4 May 2011 в 20:07
поделиться