Chance de uma colisão hash
-
26-12-2019 - |
Pergunta
Desculpas se esta for uma pergunta duplicada;A maioria dos que eu encontrei sobre a minha cabeça, então eu posso ter perdido a resposta.
Para um dado hash, digamos MD5 (128 bits), qual é a chance de uma colisão hash com 10 ^ 12 deles?
Minha matemática não é ótima, eu inventei esta equação (acho que está correta), mas não tem idéia de como resolvê-lo:
Collision_chance= 1 - (1 - (1/2 ^ 128)) ^ (10 ^ 12)
Eu estou supondo que está em algum lugar em torno de 10 ^ -26, isso soa certo?
obrigado
Editar: Acho que minha estimativa está muito errada.Ver aniversário paradoxo
Solução
O que a sua fórmula diz para ter 2 ^ 128 + 1 valores?Eu acredito que não diz que a probabilidade de colisão é 1, então não pode estar certa.Na verdade, eu sei que não é - a fórmula correta é bastante grande e desajeitada, mas há boas aproximações usando a exponencial de uma fração.Assim não tyiset fórmulas, então não vou tentar escrever as fórmulas aqui.
A melhor palavra chave para buscar é provavelmente " Ataque de aniversário ".
Outras dicas
Por que uma colisão hash seria um problema?Os hashes nunca são projetados para gerar vaues exclusivos, apenas para facilitar uma rápida primeira comparação.
Se você está tendo problemas com colisões hash, você está usando errado.