what length cryptography bit-manipulation hash probability xor

cryptography - what - sha1 max length



¿Por qué XOR es la forma predeterminada de combinar hashes? (9)

A pesar de sus prácticas propiedades de mezcla de bits, XOR no es una buena forma de combinar hashes debido a su conmutatividad. Considera lo que sucedería si almacenaras las permutaciones de {1, 2, ..., 10} en una tabla hash de 10 tuplas.

Una opción mucho mejor es m * H(A) + H(B) , donde m es un número impar grande.

Crédito: El combinador anterior fue un consejo de Bob Jenkins.

Supongamos que tiene dos hashes H(A) y H(B) y desea combinarlos. He leído que una buena forma de combinar dos hash es con XOR , por ejemplo, XOR( H(A), H(B) ) .

La mejor explicación que he encontrado se toca brevemente aquí en estas pautas de función hash :

XORing dos números con distribución aproximadamente aleatoria da como resultado otro número aún con distribución aproximadamente aleatoria *, pero que ahora depende de los dos valores.
...
* En cada bit de los dos números para combinar, se emite un 0 si los dos bits son iguales, sino un 1. En otras palabras, en el 50% de las combinaciones, se emitirá un 1. Entonces, si los dos bits de entrada tienen una probabilidad de 50 o 50 de ser 0 o 1, entonces también lo será el bit de salida.

¿Puede explicar la intuición y / o las matemáticas detrás de por qué XOR debería ser la operación predeterminada para combinar funciones hash (en lugar de OR o AND, etc.)?

Cubra las 2 columnas de la izquierda e intente determinar qué entradas están usando solo la salida.

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

Cuando viste un bit de 1, deberías haber calculado que ambas entradas eran 1.

Ahora haz lo mismo para XOR

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

XOR no revela nada sobre las entradas.

El código fuente de varias versiones de hashCode() en java.util.Arrays es una gran referencia para algoritmos de hash sólidos y de uso general. Se entienden fácilmente y se traducen a otros lenguajes de programación.

Hablando en términos generales, la mayoría de las implementaciones hashCode() multi-atributo siguen este patrón:

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; }

Puede buscar otras preguntas y respuestas de para obtener más información sobre la magia detrás de 31 y por qué el código Java lo usa con tanta frecuencia. Es imperfecto, pero tiene muy buenas características de rendimiento general.

Hay algo que quiero señalar explícitamente para otros que encuentran esta página. AND y OR restringen la salida como BlueRaja - Danny Pflughoe está tratando de señalar, pero se puede definir mejor:

Primero quiero definir dos funciones simples que usaré para explicar esto: Min () y Max ().

Min (A, B) devolverá el valor que es más pequeño entre A y B, por ejemplo: Min (1, 5) devuelve 1.

Max (A, B) devolverá el valor que es más grande entre A y B, por ejemplo: Max (1, 5) devuelve 5.

Si le dan: C = A AND B

Entonces puedes encontrar que C <= Min(A, B) Sabemos esto porque no hay nada que puedas Y con los 0 bits de A o B para hacerlos 1s. Entonces, cada bit cero se queda en cero y cada bit tiene la posibilidad de convertirse en un bit cero (y, por lo tanto, un valor menor).

Con: C = A OR B

Lo opuesto es cierto: C >= Max(A, B) Con esto, vemos el corolario de la función AND. Cualquier bit que ya sea uno no puede convertirse en cero, por lo que se mantiene como uno, pero cada bit cero tiene la posibilidad de convertirse en uno y, por lo tanto, en un número mayor.

Esto implica que el estado de la entrada aplica restricciones en la salida. Si AND y cualquier cosa con 90, sabe que la salida será igual o inferior a 90, independientemente de cuál sea el otro valor.

Para XOR, no hay restricción implícita basada en las entradas. Hay casos especiales en los que puede encontrar que si utiliza un byte XOR con 255, obtendrá el inverso, pero cualquier byte posible se puede generar a partir de ese. Cada bit tiene la posibilidad de cambiar de estado dependiendo del mismo bit en el otro operando.

Si XOR una entrada aleatoria con una entrada sesgada, la salida es aleatoria. Lo mismo no es cierto para AND o OR . Ejemplo:

00101001 XOR 00000000 = 00101001 00101001 AND 00000000 = 00000000 00101001 OR 11111111 = 11111111

Como señala @Greg Hewgill, incluso si ambas entradas son aleatorias, usar AND u OR dará como resultado una salida sesgada.

La razón por la que utilizamos XOR sobre algo más complejo es que, bueno, no es necesario: XOR funciona perfectamente, y es increíblemente estúpido-rápido.

Suponiendo entradas uniformemente aleatorias (1 bit), la distribución de probabilidad de salida de la función AND es del 75% 0 y del 25% 1 . Por el contrario, O es 25% 0 y 75% 1 .

La función XOR es 50% 0 y 50% 1 , por lo tanto, es bueno para combinar distribuciones de probabilidad uniformes.

Esto se puede ver al escribir tablas de verdad:

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

Ejercicio: ¿Cuántas funciones lógicas de dos entradas de 1 bit a y b tienen esta distribución de salida uniforme? ¿Por qué XOR es el más adecuado para el propósito indicado en su pregunta?

Xor puede ser la forma "predeterminada" de combinar hash, pero la respuesta de Greg Hewgill también muestra por qué tiene sus inconvenientes: el xor de dos valores hash idénticos es cero. En la vida real, existen hashes idénticos que son más comunes de lo que uno podría haber esperado. A continuación, puede encontrar que en estos casos de esquina (no tan infrecuentes), los hashes combinados resultantes son siempre los mismos (cero). Las colisiones hash serían mucho, mucho más frecuentes de lo que esperabas.

En un ejemplo artificial, puede que esté combinando contraseñas hash de usuarios de diferentes sitios web que administre. Desafortunadamente, una gran cantidad de usuarios reutiliza sus contraseñas, ¡y una sorprendente proporción de los hashes resultantes son cero!

xor es una función predeterminada peligrosa para usar cuando se usa hash. Es mejor que "y" y "o", pero eso no dice mucho.

xor es simétrico, por lo que el orden de los elementos se pierde. Entonces, "bad" combinará lo mismo que "dab" .

xor asigna valores idénticos a cero, y debe evitar mapear los valores "comunes" a cero:

Así que (a,a) se asigna a 0, y (b,b) también se mapea a 0. Como tales pares son más comunes de lo que la aleatoriedad puede implicar, terminas con muchas colisiones a cero de lo que deberías.

Con estos dos problemas, xor termina siendo un combinador de hash que parece medio decente en la superficie, pero no después de una inspección adicional.

En hardware moderno, agregando usualmente tan rápido como xor (es probable que use más potencia para llevarlo a cabo). La tabla de verdad de adición es similar a xor en el bit en cuestión, pero también envía un bit al siguiente bit cuando ambos valores son 1. Esto borra menos información.

Entonces hash(a) + hash(b) es mejor porque si a==b , el resultado es hash(a)<<1 lugar de 0.

Esto sigue siendo simétrico. Podemos romper esta simetría por un costo modesto:

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

también conocido como hash(a)*3 + hash(b) . (calcula el hash(a) una vez y se recomienda almacenarlo si usa la solución de turno). Cualquier constante impar en lugar de 3 mapeará size_t un size_t (o una constante sin signo de k bits), ya que el mapa de las constantes sin signo es el módulo matemático 2^k para algunos k , y cualquier constante impar es relativamente primo a 2^k .

Para una versión más elegante, podemos examinar boost::hash_combine , que es efectivamente:

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

aquí agregamos juntos algunas versiones modificadas de seed con una constante (que es básicamente aleatoria 0 sy 1 s - en particular es la inversa de la proporción áurea como una fracción de punto fijo de 32 bits) con alguna adición y un xor. Esto rompe la simetría e introduce algo de "ruido" si los valores hash entrantes son pobres (es decir, imagine que cada componente se hereda a 0 - lo anterior lo maneja bien, generando una mancha de 1 y 0 s después de cada combinación). 0 ).

Para aquellos que no están familiarizados con C / C ++, un size_t es un valor entero sin signo que es lo suficientemente grande como para describir el tamaño de cualquier objeto en la memoria. En un sistema de 64 bits, generalmente es un entero sin signo de 64 bits. En un sistema de 32 bits, un entero sin signo de 32 bits.