Probabilidad de colisiones SHA1

Question

Dado un conjunto de 100 secuencias diferentes de la misma longitud, ¿cómo se puede cuantificar la probabilidad de que un SHA1 de colisión para las cuerdas es poco probable ...?

Answer 1

  

se generan los valores hash de 160 bits   por SHA-1 lo suficientemente grande como para asegurar la   huella digital de cada bloque es único?   Suponiendo que los valores hash aleatorias con una   distribución uniforme, una colección de   n diferentes bloques de datos y un hash   función que genera bits b, el   probabilidad p de que habrá una   o más colisiones está limitada por la   número de pares de bloques multiplica   por la probabilidad de que un par dado   colisionará.

(fuente: http: / /bitcache.org/faq/hash-collision-probabilities )

Answer 2

Bueno, la probabilidad de una colisión sería:

1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)

Piense en la probabilidad de una colisión de 2 objetos en un espacio de 10. El primer elemento es único, con una probabilidad del 100%. El segundo es único con una probabilidad de 9/10. Por lo tanto la probabilidad de ser único es 100% * 90%, y la probabilidad de una colisión es:

1 - (100% * 90%), or 1 - ((10 - 0) / 10) * ((10 - 1) / 10), or 1 - ((10 - 1) / 10)

Es bastante improbable. Usted tendría que tener muchos más cadenas para que sea una posibilidad remota.

Tome un vistazo a la tabla de la esta página en Wikipedia ; simplemente interpolar entre las filas para 128 bits y 256 bits.

Answer 3

Eso es cumpleaños Problema - el artículo proporciona buenas aproximaciones que hacen que sea muy fácil de estimar el probabilidad. probabilidad real va a ser muy muy muy bajo - ver esta pregunta para un ejemplo.