Como funcionam os geradores de números aleatórios: PRNGs, CSPRNGs e verdadeira aleatoriedade

Números aleatórios fornecem brindes, jogos, simulações, senhas e criptografia. A parte surpreendente é que a maioria dos números aleatórios não é nada aleatória. Eles são produzidos por um processo determinístico que parece imprevisível visto de fora.

Principais conclusões

• Um gerador de números pseudo-aleatórios (PRNG) transforma uma semente em uma sequência longa e repetível.
• Um PRNG criptograficamente seguro (CSPRNG) é projetado para que os resultados passados ​​não possam praticamente revelar os futuros.
• A verdadeira aleatoriedade vem de fontes físicas de entropia, não apenas de um algoritmo.
• Os navegadores expõem um CSPRNG através de crypto.getRandomValues(), que é a escolha certa para sorteios justos diários.
• A imparcialidade também depende de como os valores são mapeados para um intervalo: a aritmética de módulo tendenciosa pode favorecer discretamente alguns resultados.

Por que a aleatoriedade é mais difícil do que parece

Um computador segue instruções. Se você executar o mesmo programa duas vezes com as mesmas entradas, normalmente obterá a mesma saída. Um gerador de números aleatórios deve quebrar essa expectativa sem quebrar a máquina.

O software geralmente resolve o problema em duas camadas. Primeiro, ele coleta uma pequena quantidade de dados imprevisíveis, chamados de entropia, de fontes como instabilidade de tempo, eventos de teclado ou ruído de hardware. Em segundo lugar, utiliza essa entropia como semente para um algoritmo que produz um longo fluxo de números. O fluxo parece aleatório, mas é totalmente determinado pela semente e pelo algoritmo.

Esse design é útil. Torna números aleatórios reproduzíveis para simulações e testes. Isso também significa que um gerador mal semeado pode repetir a mesma sequência em máquinas diferentes, e é por isso que a qualidade da semente é importante.

O que um gerador de números pseudo-aleatórios faz

Um PRNG mantém um estado interno. Cada vez que você pede um número, ele transforma o estado e retorna parte do resultado. A transformação geralmente é rápida e determinística. Dado o mesmo estado inicial, a mesma sequência aparece novamente.

A maioria dos PRNGs eventualmente repetem seu estado. O número de valores antes da repetição é chamado de período. Um longo período é útil, mas não torna automaticamente um gerador seguro. Um invasor que consegue observar resultados suficientes pode reconstruir o estado interno e prever valores futuros.

PRNG versus CSPRNG

Um PRNG de uso geral é otimizado para velocidade e qualidade estatística. Um CSPRNG é projetado para resistir à previsão. Ele usa primitivas criptográficas e é construído de forma que o aprendizado de uma saída não revele a próxima.

Math.random() do JavaScript não é adequado para trabalhos sensíveis à segurança. É rápido e conveniente, mas os motores não garantem qualidade criptográfica. Os navegadores fornecem crypto.getRandomValues() para aleatoriedade relevante para a segurança. Ele preenche um array digitado com bytes aleatórios usando a fonte criptográfica da plataforma.

Para senhas, tokens, sorteios justos com prêmio e qualquer coisa que um invasor queira prever, use um CSPRNG. Para uma animação decorativa ou uma simulação aproximada, um PRNG normal pode ser suficiente.

De onde vem a verdadeira aleatoriedade

Nenhum algoritmo de software pode criar informações do nada. A verdadeira aleatoriedade entra no sistema através de processos físicos: decaimento radioativo, ruído térmico ou o tempo preciso da entrada do usuário. Os sistemas operacionais coletam esses sinais em um pool de entropia e os utilizam para gerar geradores criptográficos.

Os sistemas operacionais e navegadores modernos combinam entropia continuamente. Você não precisa agitar o mouse para fazer um empate justo, mas o sistema precisa de uma fonte saudável de entropia durante a inicialização e após longos períodos sem atividade. Esta é uma das razões pelas quais os geradores criptográficos são cuidadosamente projetados, em vez de improvisados.

Como funcionam os geradores deste site

As ferramentas deste site usam crypto.getRandomValues() em seu navegador. Os resultados são gerados localmente e não são carregados.

Para intervalos inteiros, o navegador retorna um valor não assinado de 32 bits. Uma abordagem ingênua usa o resto após a divisão, mas isso pode introduzir um pequeno viés quando o intervalo não se divide uniformemente em todo o espaço de 32 bits. Os geradores usam amostragem de rejeição: valores fora da região imparcial são descartados e redesenhados. O resultado é uma distribuição uniforme em todo o intervalo solicitado.

Os embaralhamentos usam o algoritmo Fisher-Yates com índices aleatórios seguros. Ao contrário de uma classificação casual com um comparador aleatório, Fisher-Yates produz cada permutação com igual probabilidade quando os índices aleatórios são uniformes.

O que é aleatório o suficiente para o seu caso de uso?

Use a pseudo-aleatoriedade comum para animações, arte de jogos ou simulações aproximadas onde a previsibilidade não tem custo. Use um CSPRNG para:

• Senhas e códigos de recuperação.
• Brindes, sorteios e audições com prêmio real.
• Atribuição aleatória de pessoas a equipes ou grupos.
• Tokens, identificadores de sessão e qualquer coisa relacionada à segurança.
• Qualquer empate que você precise defender publicamente.

Para chaves criptográficas de longo prazo, use um sistema de gerenciamento de chaves dedicado em vez de um site. A aleatoriedade do navegador é forte, mas o ciclo de vida, o armazenamento e o controle de acesso das chaves são tão importantes quanto os bits iniciais.

Uma simples verificação de justiça

Você pode testar um gerador informalmente executando vários sorteios e observando a distribuição. Com um dado de seis lados, cada face deve aparecer aproximadamente um sexto das vezes. As tiragens curtas variam e as listras são normais. O que importa é se o processo é imparcial em muitos ensaios e se é reproduzível o suficiente para ser auditado.

Para sorteios públicos, registre as entradas, as configurações e o resultado. O registro faz mais pela confiança do que qualquer alegação de aleatoriedade.

Resultado final

Aleatoriedade é uma cadeia de decisões de engenharia: coleta de entropia, escolha de algoritmo, mapeamento imparcial e uso transparente. Um bom gerador não precisa ser misterioso. Precisa ser imprevisível onde for importante, documentado onde for usado e honesto sobre seus limites.