Probabilidade de colisões SHA1

Question

Dado um conjunto de 100 diferentes cadeias de comprimento igual, como você pode quantificar a probabilidade de que um SHA1 colisão para as cordas é improvável ...?

Answer 1

Os valores de hash de 160 bits gerados por SHA-1 suficientemente grande para assegurar o impressão digital de cada bloco é único? Assumindo que os valores de hash aleatórios com um distribuição uniforme, um conjunto de n diferentes blocos de dados e um hash função que gera b bits, o probabilidade p que haverá um ou mais colisões é delimitada pela número de pares de blocos multiplicado pela probabilidade de que um dado par irá colidir.

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

Answer 2

Bem, a probabilidade de uma colisão seria:

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

Pense a probabilidade de uma colisão de 2 itens em um espaço de 10. O primeiro item é o único com probabilidade de 100%. O segundo é o único com probabilidade 9/10. Assim, a probabilidade de ambos ser único é 100% * 90%, ea probabilidade de uma colisão é:

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

É muito improvável. Você teria que ter muitas mais cordas para que seja uma possibilidade remota.

Veja a tabela na desta página no Wikipedia ; apenas interpolate entre as fileiras de 128 bits e 256 bits.

Answer 3

É aniversário Problema - o artigo fornece agradáveis ??aproximações que o tornam bastante fácil de estimar o probabilidade. probabilidade real será muito muito muito baixo - veja esta questão para um exemplo.