Probabilidade de colisão quando hash é metade do tamanho dos dados?

Question

Se eu tivesse uma senha de 100 bits e fizesse um hash com uma função hash que retornasse uma chave de 50 bits, agora eu a forcei até obter uma string que produza um hash correspondente. Existe agora uma chance de 50% de a string que eu produzi com força bruta não é a senha original, mas uma string que produz uma colisão?

    

Answer 1

Não. É muito, muito menos que isso. Se assumirmos que a função hash é perfeita, existem 2 ^ 50 senhas que produzem o mesmo hash de 50 bits.

Use números simples para torná-lo mais claro. Digamos que você tenha 10 ^ 4 widgets (10.000) e coloque-os em 10 ^ 2 caixas (100). Quantos widgets estão na caixa média? Bem, são 10.000 / 100 ou 100. Portanto, se você estiver procurando por um determinado widget e souber apenas sua caixa, haverá uma chance em 100 de que um widget selecionado aleatoriamente dessa caixa seja o correto.

Fazer as contas com seus números dá uma chance de 1 em 2 ^ 50.