Paradoxo do Aniversário

O paradoxo do aniversário

Pegue um grupo de n pessoas. A chance de pelo menos duas delas dividirem aniversário sai de P(n) = 1 − 365! / ((365−n)! · 365^n). Em n = 23 você já passa de 50%: P ≈ 50,7%, ou seja, o encontro fica um pouco mais provável que o contrário. Suba para n = 70 e P ≈ 99,9%. Quase ninguém acredita de cara, porque a gente imagina um número perto de 365. O detalhe é que o que se compara são pares, não pessoas isoladas, e um grupo de 23 guarda C(23,2) = 253 deles. Daí a probabilidade subir quadraticamente com n.

Aplicações

Na criptografia, o birthday attack acha colisões numa função hash de k bits em cerca de 2^(k/2) tentativas, e não 2^k. O SHA-256 fica na barreira de 2^128 e segue inquebrável; já MD5 (2^64) e SHA-1 (2^80) são tidos como quebrados. A mesma conta aparece em outros lugares: detectar duplicatas numa base de dados, pensar se GUIDs/UUIDs vão continuar únicos, problemas de bolas-e-urnas, dimensionar uma hash table e amostragem estatística.

Perguntas frequentes

Por que P(23) ≈ 50% surpreende? A intuição se prende ao "meu aniversário" e à chance de 1 em 365 ligada a ele. Só que a pergunta trata de duas pessoas quaisquer da sala, e a quantidade de pares cresce com n², não com n.

Considera ano bissexto? Não. A fórmula padrão trata os 365 dias como equiprováveis. Com um 366º dia a curva se desloca de leve. As distribuições reais de nascimento também não são uniformes, mas em n=23 o efeito é pequeno.

O que é birthday attack? É um ataque de colisão em hashes. No lugar de quebrar uma pré-imagem específica, você procura dois inputs quaisquer que gerem o mesmo hash. Essa busca dá certo em torno de 2^(k/2) tentativas, o que corta a segurança efetiva pela metade.