Gerador de números aleatórios

Uma breve história do aleatório em computadores

Computadores são máquinas determinísticas, o que torna "aleatório" uma coisa estranha de produzirem. A história dos geradores de números pseudoaleatórios (PRNG) em computadores começa com o método do quadrado do meio de John von Neumann, em 1946: elevar ao quadrado o número anterior, pegar os dígitos do meio como novo valor, repetir. O próprio von Neumann chamou de "um estado pecaminoso" usar geradores de números aleatórios sem entendê-los plenamente, porque o quadrado do meio tem modos de falha óbvios (cai a zero, períodos curtos). O gerador congruente linear de Lehmer (LCG, 1951), x_(n+1) = (a × x_n + c) mod m, foi a primeira família de PRNGs com propriedades estatísticas razoáveis; o rand() da biblioteca padrão de C ainda costuma usar uma variante LCG. O Mersenne Twister (Matsumoto e Nishimura, 1997-1998) nos deu um gerador com período de 2¹⁹⁹³⁷−1 (sim, um número de 6.000 dígitos) e excelentes propriedades estatísticas; tornou-se padrão em Python, R, MATLAB, PHP e muitas outras linguagens. A família xorshift de Marsaglia (2003) é bem mais rápida e pequena o bastante para caber em um registrador de hardware; o V8 moderno (a engine JavaScript do Chrome) usa uma variante xorshift128+ em Math.random(). PCG (Permuted Congruential Generator) de Melissa O'Neill (2014) é o estado da arte estatístico atual para PRNGs não criptográficos, combinando avanço de estado ao estilo LCG com permutação de saída para excelentes propriedades estatísticas a baixo custo.

PRNGs criptograficamente seguros (CSPRNGs) são outro animal. Propriedade definidora: mesmo que um atacante conheça toda saída que o gerador já produziu, não consegue prever a próxima saída com mais que vantagem desprezível. A syscall getrandom() do Linux (adicionada no kernel 3.17, outubro de 2014) e o /dev/urandom subjacente usam um gerador baseado em ChaCha20 alimentado por fontes de entropia de hardware (RDRAND, timing de interrupções, ruído de áudio). BCryptGenRandom do Windows usa uma construção AES-CTR-DRBG (NIST SP 800-90A) alimentada a partir de várias fontes de entropia. macOS / iOS usam um CSPRNG derivado do Fortuna. A diferença entre PRNG e CSPRNG importa enormemente: um PRNG serve para aleatoriedade de jogo, atribuição de buckets em testes A/B ou simulações; para qualquer coisa que um atacante possa tentar prever (tokens de sessão, geração de senhas, IDs de segurança), só um CSPRNG é seguro.

As duas APIs aleatórias do JavaScript

Math.random() é a API mais antiga e mais simples, devolve um número de ponto flutuante distribuído aproximadamente uniforme em [0, 1). A especificação ECMAScript deixa o algoritmo subjacente deliberadamente sem especificar ("approximately uniform distribution between 0 and 1, exclusive"), e as engines mudaram o que usam ao longo dos anos. V8 (Chrome) usou um Park-Miller LCG até 2015, depois trocou para xorshift128+ por melhores propriedades estatísticas. SpiderMonkey (Firefox) e JavaScriptCore (Safari) usam geradores não criptográficos rápidos similares. Math.random() é rápido e uniforme o bastante para mecânicas de jogo, simulações e qualquer aplicação onde imprevisibilidade não seja requisito de segurança. Não é criptograficamente seguro, o período é definido pela implementação, o estado pode ser recuperado a partir de poucas saídas, e a sequência não é segura para geração de senhas ou casos sensíveis a segurança. crypto.getRandomValues() é o CSPRNG da Web Crypto API. Preenche um array tipado com bytes aleatórios criptograficamente seguros tirados do CSPRNG do sistema operacional (a mesma fonte que o TLS usa para chaves de sessão). Disponível em todos os navegadores modernos desde aproximadamente 2014; o tamanho máximo de buffer em uma única chamada é de 65.536 bytes. A escolha certa para qualquer número aleatório que importe, geração de tokens, IDs de segurança, geração de senhas, qualquer coisa que um atacante possa tentar prever.

A armadilha do viés de módulo

Gerar um inteiro uniforme em uma faixa específica a partir de um CSPRNG é mais difícil do que parece. A abordagem ingênua, crypto.getRandomValues(new Uint8Array(1))[0] % 6 para um lançamento de dado, produz uma distribuição enviesada porque 256 não se divide igualmente por 6. Os valores 0-3 aparecem cada um 43 vezes na faixa 0-255; os valores 4-5 aparecem 42 vezes. O viés é pequeno em faixas pequenas, mas real e detectável em séries longas. A correção padrão é a amostragem por rejeição: gerar um byte aleatório, testar se cai no maior múltiplo da faixa que cabe (aqui, 252 = 42 × 6), usá-lo se sim, descartar e tentar de novo se não. A taxa de descarte é limitada por (faixa / próxima potência de 2), então para "1-6" você desperdiça cerca de 1,5 % dos bytes; para "1-1000000" contra um inteiro aleatório de 32 bits desperdiça cerca de 0,02 %. Toda biblioteca aleatória séria implementa amostragem por rejeição; o Math.floor(Math.random() * (max - min + 1)) + min baseado em Math.random() evita o viés porque a precisão de Math.random() é alta o bastante (53 bits de mantissa) para que o viés fique abaixo dos níveis humanamente detectáveis em qualquer faixa razoável. Este gerador usa saída CSPRNG com amostragem por rejeição, saída uniforme em qualquer faixa de inteiros que você pedir.

Casos de uso e que nível de aleatoriedade cada um precisa

• Sorteios de loteria e rifas. Para sorteios não monetários (trocas de mesa de escritório, atribuição de equipes em hackathon, plano de sala de aula), Math.random() serve. Para sorteios monetários ou qualquer coisa regulada, use um CSPRNG e, idealmente, publique a semente para que seja verificável.
• Mecânicas de jogo. Lançamentos de dados, embaralhamento de cartas, drops de loot, geração procedural. Math.random() é a escolha padrão, rápido, uniforme o bastante, imprevisível o bastante para que os jogadores não notem padrões. CSPRNGs ficam reservados para jogos de carta on-line em que o servidor precisa impedir trapaça.
• Atribuição de buckets para testes A/B. Faça hash do ID de usuário com um segredo estável para colocar cada usuário deterministicamente em um bucket; usar Math.random() faria com que o usuário caísse em buckets diferentes entre carregamentos de página, o que arruinaria o experimento. A atribuição baseada em hash é o padrão certo; a aleatoriedade só é usada para escolher a semente do experimento, uma vez.
• Amostragem aleatória para pesquisas. Tirar um subconjunto representativo de uma população. Math.random() serve; a pergunta estatística é se a sua amostra é grande o suficiente, não se a fonte aleatória é criptográfica.
• Geração de dados de teste. Faker, dados de mockup, fixtures sintéticas de banco. Math.random() com semente fixa (para reprodutibilidade) é a escolha certa.
• Chaves criptográficas, tokens de sessão, geração de senhas. Apenas CSPRNG, crypto.getRandomValues() no navegador, o módulo secrets em Python, crypto/rand em Go, nunca o aleatório padrão da linguagem. Um bug nessa camada compromete tudo o que depende dela; as consequências vão de "a sessão de qualquer um pode ser sequestrada" até "a chave de criptografia é recuperável".

RANDOM.ORG e a distinção do aleatório verdadeiro

RANDOM.ORG foi lançado em 1998 por Mads Haahr no Trinity College Dublin e segue como referência do "aleatório verdadeiro" on-line. Onde todo CSPRNG, em última instância, deriva seus bits de transformações algorítmicas de um estado alimentado por hardware (um processo determinístico, ainda que imprevisível para um atacante), o RANDOM.ORG mede o ruído atmosférico captado por receptores de rádio e converte esse ruído analógico diretamente em bits. Isso o torna um True Random Number Generator (TRNG) em vez de um Pseudo-Random Number Generator: os bits vêm de um processo físico genuinamente não determinístico, não de um algoritmo determinístico. RANDOM.ORG é usado por operadoras de loteria, pesquisadores acadêmicos conduzindo estudos duplo-cegos e jogos onde aleatoriedade verificável importa. O custo: um round-trip de rede por requisição, uma cota diária para o nível gratuito, e a questão filosófica de se você confia mais na fonte de entropia alegada pelo RANDOM.ORG do que no seu CSPRNG local. Para a maioria dos usos, o CSPRNG local basta; para casos em que uma terceira parte precisa verificar a aleatoriedade independentemente, o RANDOM.ORG fornece certificados assinados de aleatoriedade como serviço pago.

Amostragem sem reposição, o embaralhamento de Fisher-Yates

Quando você precisa de N números únicos em uma faixa, sortear 6 números entre 1 e 49 numa loteria, escolher 10 vencedores entre 1.000 inscritos, o ingênuo "gerar e descartar se duplicado" funciona para N pequeno, mas se degrada bruscamente quando N se aproxima do tamanho da faixa (a chance de tirar um número novo cai conforme o pool encolhe). O algoritmo padrão é o embaralhamento de Fisher-Yates, originário das tabelas estatísticas de Fisher e Yates de 1938 e formalizado em sua forma moderna em ciência da computação por Donald Knuth em 1969 (às vezes chamado de Knuth shuffle). O algoritmo é absurdamente simples: escreva os números 1 a N em um array; para i de N-1 até 1, troque o elemento i com um elemento aleatório entre 0 e i (inclusive); o array está uniformemente embaralhado. Pegue os primeiros K elementos para K números aleatórios únicos. Detalhe crucial: o índice aleatório deve estar em [0, i], inclusive, usar [0, i-1] introduz um viés sutil que a comunidade criptográfica levou anos para caracterizar (a variante de Sattolo, às vezes usada por engano no lugar do Fisher-Yates verdadeiro). Para faixas muito grandes em que alocar um array com todos os N valores é inviável (por exemplo, escolher 100 valores únicos entre 1 e 10⁹), a amostragem por reservatório (Vitter, 1985) lida com entradas em fluxo ou ilimitadas em uma única passagem com memória limitada.

Convenções de lançamentos de dados

Geradores de números aleatórios são dados disfarçados. O D6 (dado de seis lados) é o padrão universal nos jogos de tabuleiro, faixa 1-6. O D20 (dado de vinte lados) é o dado icônico de Dungeons & Dragons usado em testes de habilidade, jogadas de ataque e jogadas de salvamento, o sistema de modificadores de D&D faz com que uma única jogada de D20 mais um bônus de atributo decida a maioria das ações. O D100 (porcentagem, 1-100) é usado para jogadas percentuais em Chamado de Cthulhu, Warhammer Roleplay e muitos sistemas de chance crítica. A notação NdM significa "jogue N dados de M lados cada e some"; NdM+B adiciona um bônus. 3d6 joga três dados de seis lados e soma (faixa 3-18, a faixa clássica de pontuação de habilidade de D&D, com distribuição triangular centrada em 10-11). Para uma simulação justa, gerar um inteiro uniforme em [1, M] para cada dado e somar é exatamente equivalente a jogar dados físicos, a distribuição CSPRNG subjacente é mais uniforme do que qualquer dado físico que você consiga comprar. Cassinos e jogos regulamentados usam RNGs certificados que são testados contra baterias estatísticas (BigCrush do TestU01, NIST SP 800-22) para provar uniformidade aos reguladores; os mesmos padrões valem para RNGs de loteria.

Sementes e reprodutibilidade

Uma propriedade sutil mas importante dos PRNGs: dada uma semente, são determinísticos. Defina a semente para um valor conhecido e a sequência de números "aleatórios" é exatamente reproduzível. Isso é inestimável para testes (um teste unitário que usa dados aleatórios deveria fixar uma semente para que falhas sejam reproduzíveis) e para sorteios verificáveis (publicar a semente antes do sorteio, depois qualquer um pode verificar o resultado). O módulo random de Python tem random.seed(value) para isso; o Random de Java aceita uma semente no construtor. O Math.random() de JavaScript deliberadamente não expõe API de semente, as engines tratam a semente como estado interno, mas várias bibliotecas puramente JS (seedrandom, pcg-random) oferecem PRNGs com semente. CSPRNGs são diferentes por design: não expõem semente porque o sentido todo é a imprevisibilidade. Se você precisa de reprodutibilidade, use um PRNG com semente explícita; se precisa de segurança, use um CSPRNG e aceite que não vai conseguir reproduzir a sequência depois.

Privacidade: por que apenas no navegador, mesmo para números aleatórios

Números aleatórios em si raramente contêm informação sensível, então por que a arquitetura puramente de navegador importa? Duas razões. Primeiro, quando um número aleatório é usado como token de sessão, chave de idempotência, desafio de autenticação ou qualquer outro valor parecido a um segredo, gerá-lo num servidor de terceiros significa que esse servidor viu o valor antes de você usá-lo, uma exposição pequena, porém real. Segundo, geradores do lado do servidor que prometem "aleatoriedade criptográfica" não podem ser verificados pelo usuário; um servidor com bug ou malicioso poderia devolver valores não aleatórios ou enviesados que parecem aleatórios, e você não teria como detectar o viés sem amostragem massiva. Um gerador puramente de navegador faz a mesma chamada crypto.getRandomValues() que sua aplicação faria do lado do servidor; a entropia vem da mesma fonte do sistema operacional (Linux getrandom(), Windows BCryptGenRandom, macOS); nenhuma terceira parte vê a saída. Você pode verificar abrindo a aba Network das DevTools enquanto clica em Gerar, não há requisições saindo. Coloque a página off-line (modo avião) depois de carregar e o gerador continua funcionando.

Perguntas frequentes