Probabilidade de colisões SHA1

Dado um conjunto de 100 strings diferentes de comprimento igual, como você pode quantificar a probabilidade de que uma colisão de digestão SHA1 para as strings seja improvável …?

    texto alternativo

    Os valores de hash de 160 bits gerados pelo SHA-1 são grandes o suficiente para garantir que a impressão digital de cada bloco seja única? Assumindo valores hash randoms com uma distribuição uniforme, uma coleção de n blocos de dados diferentes e uma function hash que gera b bits, a probabilidade p de que haverá uma ou mais colisões é limitada pelo número de pares de blocos multiplicado pela probabilidade de que um determinado par colidirá.

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

    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 na probabilidade de uma colisão de 2 itens em um espaço de 10. O primeiro item é único, com probabilidade de 100%. O segundo é único com probabilidade 9/10. Portanto, a probabilidade de ambos serem únicos é 100% * 90% e a probabilidade de uma colisão é:

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

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

    Dê uma olhada na tabela desta página na Wikipedia ; basta interpolar entre as linhas para 128 bits e 256 bits.

    Isso é problema de aniversário – o artigo fornece boas aproximações que tornam bastante fácil estimar a probabilidade. A probabilidade real será muito, muito, muito baixa – veja esta pergunta para um exemplo.