¿Cómo calcular las probabilidades de una colisión en algoritmos hash?

Question

Digamos que tengo un algoritmo hash, y es agradable y suave (las probabilidades de que surja un valor hash son las mismas que cualquier otro valor).

Ahora digo que sé que las probabilidades de elegir 2 hashes y que haya una colisión son (por los argumentos) 50000: 1.

Ahora digo que recojo 100 hashes. ¿Cómo calculo las probabilidades de una colisión dentro de ese conjunto de 100 valores, dadas las probabilidades de una colisión en un conjunto de 2?

¿Cuál es la solución general a esto, por lo que puedo llegar a una serie de intentos de hash después de los cuales las probabilidades caen por debajo de un umbral aceptable? P.ej. Puedo decir cosas como "Un lote de creaciones de valor hash 49999 tiene una alta probabilidad de colisión".

Answer 1

Esto es generalization of the Birthday problem.

Answer 2

Esto se llama the Birthday problem. Para resolverlo, piense en cambio en las probabilidades de que haya no colisiones (llámelo p _nc).

• p _nc (1) = 1
• p _nc (2) = 1 - p _c (2)
• p _nc (3) = P _nc (2) * p _nc (2) * p _nc (2)

Answer 3

Eso me suena mucho al Birthday Paradox.

Debería poder simplemente sustituir el conjunto de posibles cumpleaños (365) con los posibles hash (50000) y ejecutar los mismos cálculos que allí se presentan.

Si modifica la secuencia de comandos de Python presenta en el artículo de sus valores:

def bp(n, d): 
    v = 1.0 
    for i in range(n): 

     v = v * (1 - float(i)/d) 
    return 1 - v 

print bp(2, 50000) 

Se termina con las probabilidades de colisión en dos números de 0,00002. Alrededor de 265 muestras, tiene alrededor de un 50% de posibilidades de tener una colisión.

Answer 4

En primer lugar calcular la probabilidad de que no hay una colisión:

hashes_picked = 100 
single_collision_odds = 50000 

# safe_combinations is number of ways to pick hashes that don't overlap 
safe_combinations = factorial(single_collision_odds)/factorial(single_collision_odds - hashes_picked) 

# all_combinations is total number of ways to pick hashes 
all_combinations = single_collision_odds ** hashes_picked 

collision_chance = (all_combinations - safe_combinations)/all_combinations 

Answer 5

y en JS

function calculate(n,k) 
{ 

    var result =1; 
    for (var i=0; i<k; i++){ 
     result=result*n/(n-i) 
    } 
    result=(1-1/result)*100; 
    return result; 
}