Geração de número aleatório - Random number generation

Os dados são um exemplo de gerador de números aleatórios de hardware mecânico. Quando um dado cúbico é lançado, um número aleatório de 1 a 6 é obtido.

A geração de números aleatórios é um processo pelo qual, muitas vezes por meio de um gerador de números aleatórios ( RNG ), é gerada uma sequência de números ou símbolos que não podem ser razoavelmente previstos melhor do que por acaso . Isso significa que a sequência de resultado particular conterá alguns padrões detectáveis ​​em retrospectiva, mas imprevisíveis em previsão. Os verdadeiros geradores de números aleatórios podem ser geradores de números aleatórios de hardware (HRNGS) que geram números aleatórios, em que cada geração é uma função do valor atual do atributo de um ambiente físico que está constantemente mudando de uma maneira que é praticamente impossível de modelar. Isso estaria em contraste com as chamadas "gerações de números aleatórios" feitas por geradores de números pseudo-aleatórios (PRNGs) que geram números que apenas parecem aleatórios, mas são de fato pré-determinados - essas gerações podem ser reproduzidas simplesmente sabendo o estado do PRNG .

Várias aplicações de aleatoriedade levaram ao desenvolvimento de vários métodos diferentes para gerar dados aleatórios . Alguns deles existem desde os tempos antigos, entre cujas fileiras estão bem conhecidos exemplos "clássicos", incluindo o lançamento de dados , lançamento de moedas , o embaralhamento de cartas de jogar , o uso de hastes de mil-folhas (para adivinhação ) no I Ching , bem como inúmeras outras técnicas. Devido à natureza mecânica dessas técnicas, gerar grandes quantidades de números suficientemente aleatórios (importante nas estatísticas) exigia muito trabalho e tempo. Assim, os resultados às vezes eram coletados e distribuídos como tabelas de números aleatórios .

Existem vários métodos computacionais para geração de números pseudo-aleatórios. Todos ficam aquém do objetivo da verdadeira aleatoriedade, embora possam atender, com sucesso variável, alguns dos testes estatísticos de aleatoriedade destinados a medir o quão imprevisíveis são seus resultados (isto é, em que grau seus padrões são discerníveis). Isso geralmente os torna inutilizáveis ​​para aplicativos como criptografia . No entanto, geradores de números pseudo-aleatórios (CSPRNGS) cuidadosamente projetados e criptograficamente seguros também existem, com recursos especiais projetados especificamente para uso em criptografia.

Aplicações práticas e usos

Os geradores de números aleatórios têm aplicações em jogos de azar , amostragem estatística , simulação de computador , criptografia , design completamente aleatório e outras áreas onde a produção de um resultado imprevisível é desejável. Geralmente, em aplicativos que têm a imprevisibilidade como o recurso principal, como em aplicativos de segurança, geradores de hardware são geralmente preferidos em vez de algoritmos pseudo-aleatórios, quando viável.

Os geradores de números pseudo-aleatórios são muito úteis no desenvolvimento de simulações do método Monte Carlo , pois a depuração é facilitada pela capacidade de executar a mesma sequência de números aleatórios novamente começando da mesma semente aleatória . Eles também são usados ​​em criptografia - desde que a semente seja secreta. O remetente e o destinatário podem gerar o mesmo conjunto de números automaticamente para usar como chaves.

A geração de números pseudo-aleatórios é uma tarefa importante e comum na programação de computadores. Embora a criptografia e certos algoritmos numéricos exijam um grau muito alto de aleatoriedade aparente , muitas outras operações precisam apenas de uma quantidade modesta de imprevisibilidade. Alguns exemplos simples podem ser apresentar a um usuário uma "citação aleatória do dia" ou determinar de que maneira um adversário controlado por computador pode se mover em um jogo de computador. Formas mais fracas de aleatoriedade são usadas em algoritmos hash e na criação de algoritmos de busca e classificação amortizados .

Algumas aplicações que parecem à primeira vista adequadas para a aleatorização não são, de facto, tão simples. Por exemplo, um sistema que seleciona "aleatoriamente" faixas de música para um sistema de música de fundo deve aparecer apenas aleatoriamente, e pode até ter maneiras de controlar a seleção de música: um sistema verdadeiramente aleatório não teria nenhuma restrição para o mesmo item aparecer dois ou três vezes em sucessão.

Números "verdadeiros" vs. pseudo-aleatórios

Existem dois métodos principais usados ​​para gerar números aleatórios. O primeiro método mede algum fenômeno físico que se espera que seja aleatório e então compensa possíveis vieses no processo de medição. Fontes de exemplo incluem medição de ruído atmosférico , ruído térmico e outros fenômenos eletromagnéticos e quânticos externos. Por exemplo, a radiação cósmica de fundo ou decadência radioativa medida em escalas de tempo curtas representam fontes de entropia natural .

A velocidade na qual a entropia pode ser obtida de fontes naturais depende dos fenômenos físicos subjacentes que estão sendo medidos. Assim, as fontes de entropia "verdadeira" de ocorrência natural são consideradas bloqueadoras  - elas são limitadas por taxa até que entropia suficiente seja coletada para atender à demanda. Em alguns sistemas semelhantes ao Unix, incluindo a maioria das distribuições Linux , o arquivo do pseudo dispositivo / dev / random será bloqueado até que entropia suficiente seja coletada do ambiente. Devido a esse comportamento de bloqueio, grandes leituras em massa de / dev / random , como preencher uma unidade de disco rígido com bits aleatórios, podem frequentemente ser lentas em sistemas que usam esse tipo de fonte de entropia.

O segundo método usa algoritmos computacionais que podem produzir longas sequências de resultados aparentemente aleatórios, que são na verdade completamente determinados por um valor inicial mais curto, conhecido como valor de semente ou chave . Como resultado, toda a sequência aparentemente aleatória pode ser reproduzida se o valor da semente for conhecido. Este tipo de gerador de números aleatórios é freqüentemente chamado de gerador de números pseudo - aleatórios . Este tipo de gerador normalmente não depende de fontes de entropia que ocorrem naturalmente, embora possa ser semeado periodicamente por fontes naturais. Este tipo de gerador não é bloqueador, portanto, eles não são limitados em taxa por um evento externo, tornando grandes leituras em massa uma possibilidade.

Alguns sistemas adotam uma abordagem híbrida, fornecendo aleatoriedade colhida de fontes naturais quando disponível, e recorrendo a geradores de números pseudo-aleatórios (CSPRNGs) criptograficamente seguros com base em software periodicamente recriados . O fallback ocorre quando a taxa de leitura de aleatoriedade desejada excede a capacidade da abordagem de colheita natural para acompanhar a demanda. Essa abordagem evita o comportamento de bloqueio de taxa limitada de geradores de números aleatórios com base em métodos mais lentos e puramente ambientais.

Embora um gerador de números pseudo-aleatórios baseado unicamente na lógica determinística nunca possa ser considerado uma fonte de número aleatório "verdadeiro" no sentido mais puro da palavra, na prática eles são geralmente suficientes até mesmo para aplicativos críticos de segurança exigentes. De fato, geradores de números pseudo-aleatórios cuidadosamente projetados e implementados podem ser certificados para fins criptográficos de segurança crítica, como é o caso com o algoritmo Yarrow e fortuna . O primeiro é a base da fonte / dev / random de entropia no FreeBSD , AIX , OS X , NetBSD e outros. O OpenBSD usa um algoritmo de número pseudo-aleatório conhecido como arc4random .

Métodos de geração

Métodos físicos

Os primeiros métodos para gerar números aleatórios, como dados, lançamento de moedas e roleta, ainda são usados ​​hoje, principalmente em jogos e apostas, pois tendem a ser muito lentos para a maioria das aplicações em estatística e criptografia.

Um gerador de número aleatório físico pode ser baseado em um fenômeno físico atômico ou subatômico essencialmente aleatório, cuja imprevisibilidade pode ser atribuída às leis da mecânica quântica . As fontes de entropia incluem decaimento radioativo , ruído térmico , ruído de disparo , ruído de avalanche em diodos Zener , desvio do relógio , o tempo dos movimentos reais de uma cabeça de leitura / gravação de disco rígido e ruído de rádio . No entanto, os fenômenos físicos e as ferramentas usadas para medi-los geralmente apresentam assimetrias e vieses sistemáticos que tornam seus resultados não uniformemente aleatórios. Um extrator de aleatoriedade , como uma função hash criptográfica , pode ser usado para abordar uma distribuição uniforme de bits de uma fonte não uniformemente aleatória, embora em uma taxa de bits inferior.

O aparecimento de fontes de entropia fotônica de banda larga, como caos óptico e ruído de emissão espontânea amplificado , auxiliam muito no desenvolvimento do gerador físico de números aleatórios. Entre eles, o caos óptico tem um alto potencial para produzir fisicamente números aleatórios de alta velocidade devido à sua alta largura de banda e grande amplitude. Um protótipo de um gerador de bits aleatórios físicos de alta velocidade em tempo real baseado em um laser caótico foi construído em 2013.

Várias maneiras criativas de coletar essa informação entrópica foram inventadas. Uma técnica é executar uma função hash em um quadro de um fluxo de vídeo de uma fonte imprevisível. Lavarand usou essa técnica com imagens de várias lâmpadas de lava . HotBits mede decaimento radioativo com tubos Geiger-Muller , enquanto Random.org usa variações na amplitude do ruído atmosférico gravado com um rádio normal.

Demonstração de um gerador de números aleatórios simples com base em onde e quando um botão é clicado

Outra fonte de entropia comum é o comportamento dos usuários humanos do sistema. Embora as pessoas não sejam consideradas bons geradores de aleatoriedade quando solicitadas, elas geram um comportamento aleatório muito bem no contexto de jogos de estratégia mista . Alguns softwares de computador relacionados à segurança requerem que o usuário faça uma longa série de movimentos do mouse ou entradas de teclado para criar entropia suficiente necessária para gerar chaves aleatórias ou para inicializar geradores de números pseudo-aleatórios.

Métodos computacionais

A maioria dos números aleatórios gerados por computador usa PRNGs, que são algoritmos que podem criar automaticamente longas séries de números com boas propriedades aleatórias, mas, eventualmente, a sequência se repete (ou o uso da memória aumenta sem limites). Esses números aleatórios são bons em muitas situações, mas não são tão aleatórios quanto os números gerados a partir do ruído atmosférico eletromagnético usado como fonte de entropia. A série de valores gerados por tais algoritmos é geralmente determinada por um número fixo denominado semente. Um dos PRNG mais comuns é o gerador congruencial linear , que usa a recorrência

para gerar números, onde a , b e m são inteiros grandes e é o próximo em X como uma série de números pseudo-aleatórios. O número máximo de números que a fórmula pode produzir é um a menos que o módulo , m -1. A relação de recorrência pode ser estendida a matrizes para ter períodos muito mais longos e melhores propriedades estatísticas. Para evitar certas propriedades não aleatórias de um único gerador congruencial linear, vários desses geradores de números aleatórios com valores ligeiramente diferentes do coeficiente multiplicador, a , podem ser usados ​​em paralelo, com um gerador de número aleatório "mestre" que seleciona entre os vários geradores diferentes.

Um método simples de caneta e papel para gerar números aleatórios é o chamado método do quadrado do meio sugerido por John von Neumann . Embora simples de implementar, seu resultado é de baixa qualidade. Tem um período muito curto e deficiências graves, como a sequência de saída quase sempre convergindo para zero. Uma inovação recente é combinar o quadrado do meio com uma sequência de Weyl . Este método produz resultados de alta qualidade por um longo período.

A maioria das linguagens de programação de computador inclui funções ou rotinas de biblioteca que fornecem geradores de números aleatórios. Eles geralmente são projetados para fornecer um byte ou palavra aleatória, ou um número de ponto flutuante uniformemente distribuído entre 0 e 1.

A qualidade, ou seja, a aleatoriedade de tais funções de biblioteca varia amplamente, desde uma saída completamente previsível até criptograficamente segura. O gerador de números aleatórios padrão em muitas linguagens, incluindo Python, Ruby, R, IDL e PHP é baseado no algoritmo Mersenne Twister e não é suficiente para fins de criptografia, como está explicitamente declarado na documentação da linguagem. Essas funções de biblioteca geralmente têm propriedades estatísticas pobres e algumas repetirão padrões após apenas dezenas de milhares de tentativas. Eles geralmente são inicializados usando o relógio de tempo real de um computador como semente, já que esse relógio geralmente mede em milissegundos, muito além da precisão da pessoa . Essas funções podem fornecer aleatoriedade suficiente para certas tarefas (por exemplo, videogames), mas são inadequadas onde a aleatoriedade de alta qualidade é necessária, como em aplicativos de criptografia, estatísticas ou análise numérica.

Fontes de números aleatórios de qualidade muito mais alta estão disponíveis na maioria dos sistemas operacionais; por exemplo, / dev / random em vários tipos de BSD, Linux, Mac OS X, IRIX e Solaris ou CryptGenRandom para Microsoft Windows. A maioria das linguagens de programação, incluindo aquelas mencionadas acima, fornecem um meio de acessar essas fontes de qualidade superior.

Por humanos

A geração de números aleatórios também pode ser realizada por humanos, na forma de coletar várias entradas de usuários finais e usá-los como uma fonte de randomização. No entanto, a maioria dos estudos conclui que os seres humanos apresentam algum grau de não aleatoriedade ao tentar produzir uma sequência aleatória de, por exemplo, dígitos ou letras. Eles podem alternar muito entre as escolhas quando comparados a um bom gerador aleatório; portanto, essa abordagem não é amplamente utilizada.

Pós-processamento e verificações estatísticas

Mesmo com uma fonte de números aleatórios plausíveis (talvez de um gerador de hardware baseado na mecânica quântica), a obtenção de números completamente imparciais é cuidadosa. Além disso, o comportamento desses geradores geralmente muda com a temperatura, a tensão da fonte de alimentação, a idade do dispositivo ou outras interferências externas. E um bug de software em uma rotina de números pseudoaleatórios, ou um bug de hardware no hardware em que é executado, pode ser igualmente difícil de detectar.

Os números aleatórios gerados às vezes são submetidos a testes estatísticos antes do uso para garantir que a fonte subjacente ainda está funcionando e, em seguida, são pós-processados ​​para melhorar suas propriedades estatísticas. Um exemplo seria o gerador de número aleatório de hardware TRNG9803, que usa uma medição de entropia como um teste de hardware e, em seguida, pós-processa a sequência aleatória com uma cifra de fluxo de registro de deslocamento. Geralmente é difícil usar testes estatísticos para validar os números aleatórios gerados. Wang e Nicol propuseram uma técnica de teste estatístico com base na distância que é usada para identificar os pontos fracos de vários geradores aleatórios. Li e Wang propuseram um método de teste de números aleatórios baseado em fontes de entropia caótica de laser usando propriedades de movimento browniano.

Outras considerações

Remodelando a distribuição

Distribuições uniformes

A maioria dos geradores de números aleatórios funciona nativamente com inteiros ou bits individuais, portanto, uma etapa extra é necessária para chegar à distribuição uniforme "canônica" entre 0 e 1. A implementação não é tão trivial quanto dividir o inteiro por seu valor máximo possível. Especificamente:

  1. O inteiro usado na transformação deve fornecer bits suficientes para a precisão pretendida.
  2. A própria natureza da matemática de ponto flutuante significa que existe mais precisão quanto mais próximo o número estiver de zero. Essa precisão extra geralmente não é usada devido ao grande número de bits necessários.
  3. O erro de arredondamento na divisão pode influenciar o resultado. Na pior das hipóteses, um limite supostamente excluído pode ser traçado de acordo com as expectativas baseadas na matemática de números reais.

O algoritmo mainstream, usado por OpenJDK, Rust e Numpy, é descrito em uma proposta para STL do C ++ . Ele não usa a precisão extra e sofre viés apenas no último bit devido ao arredondamento para o par. Outras preocupações numéricas são justificadas ao mudar essa distribuição uniforme "canônica" para um intervalo diferente. Um método proposto para a linguagem de programação Swift afirma usar a precisão total em todos os lugares.

Inteiros uniformemente distribuídos são comumente usados ​​em algoritmos como o embaralhamento de Fisher-Yates . Novamente, uma implementação ingênua pode induzir um viés de módulo no resultado, portanto, algoritmos mais envolvidos devem ser usados. Um método que quase nunca realiza a divisão foi descrito em 2018 por Daniel Lemire, com o atual estado da arte sendo o 2021 "algoritmo ideal" inspirado na codificação aritmética por Stephen Canon da Apple Inc.

A maioria dos 0 a 1 RNGs inclui 0, mas exclui 1, enquanto outros incluem ou excluem ambos.

Outras distribuições

Dada uma fonte de números aleatórios uniformes, existem alguns métodos para criar uma nova fonte aleatória que corresponde a uma função de densidade de probabilidade . Um método, denominado método de inversão , envolve a integração de até uma área maior ou igual ao número aleatório (que deve ser gerado entre 0 e 1 para distribuições adequadas). Um segundo método, denominado método de aceitação-rejeição , envolve escolher um valor xey e testar se a função de x é maior do que o valor y. Se for, o valor x é aceito. Caso contrário, o valor x é rejeitado e o algoritmo tenta novamente.

Como um exemplo para amostragem de rejeição, para gerar um par de números aleatórios normalmente distribuídos padrão estatisticamente independentes ( x , y ), pode-se primeiro gerar as coordenadas polares ( r , θ ), onde r 2 ~ χ 2 2 e θ ~ UNIFORME ( 0,2π) (ver transformada de Box-Muller ).

Branqueamento

As saídas de vários RNGs independentes podem ser combinadas (por exemplo, usando uma operação XOR bit a bit ) para fornecer um RNG combinado pelo menos tão bom quanto o melhor RNG usado. Isso é conhecido como clareamento de software .

Os geradores de números aleatórios computacionais e de hardware às vezes são combinados para refletir os benefícios de ambos os tipos. Os geradores de números aleatórios computacionais podem gerar números pseudo-aleatórios muito mais rápido do que os geradores físicos, enquanto os geradores físicos podem gerar "verdadeira aleatoriedade".

Sequências de baixa discrepância como alternativa

Alguns cálculos que usam um gerador de números aleatórios podem ser resumidos como o cálculo de um valor total ou médio, como o cálculo de integrais pelo método de Monte Carlo . Para tais problemas, pode ser possível encontrar uma solução mais precisa pelo uso das chamadas sequências de baixa discrepância , também chamadas de números quase aleatórios . Essas sequências têm um padrão definido que preenche as lacunas de maneira uniforme, qualitativamente falando; uma sequência verdadeiramente aleatória pode, e geralmente deixa, lacunas maiores.

Atividades e demonstrações

Os seguintes sites disponibilizam amostras de números aleatórios:

  • As páginas de recursos SOCR contêm várias atividades interativas práticas e demonstrações de geração de números aleatórios usando miniaplicativos Java.
  • O Quantum Optics Group na ANU gera números aleatórios provenientes do vácuo quântico. Amostras de números aleatórios estão disponíveis na página de pesquisa do gerador de números aleatórios quânticos.
  • A Random.org disponibiliza números aleatórios provenientes da aleatoriedade do ruído atmosférico.
  • O Quantum Random Bit Generator Service do Ruđer Bošković Institute coleta a aleatoriedade do processo quântico de emissão fotônica em semicondutores. Eles fornecem uma variedade de maneiras de buscar os dados, incluindo bibliotecas para várias linguagens de programação.
  • O Grupo da Universidade de Tecnologia de Taiyuan gera números aleatórios provenientes de um laser caótico. Amostras de números aleatórios estão disponíveis em seu Serviço de Gerador de Números Aleatórios Físicos.

Backdoors

Uma vez que grande parte da criptografia depende de um gerador de número aleatório criptograficamente seguro para geração de chaves e nonce criptográfico , se um gerador de número aleatório puder ser previsível, ele pode ser usado como backdoor por um invasor para quebrar a criptografia.

Foi relatado que a NSA inseriu uma porta dos fundos no gerador de números pseudo-aleatórios criptograficamente seguro e certificado pelo NIST Dual EC DRBG . Se, por exemplo, uma conexão SSL for criada usando este gerador de número aleatório, de acordo com Matthew Green, isso permitiria à NSA determinar o estado do gerador de número aleatório e, assim, eventualmente, ser capaz de ler todos os dados enviados pela conexão SSL. Embora fosse aparente que Dual_EC_DRBG era um gerador de números pseudoaleatórios muito pobre e possivelmente backdoored muito antes de o backdoor da NSA ser confirmado em 2013, ele tinha visto um uso significativo na prática até 2013, por exemplo, pela proeminente empresa de segurança RSA Security . Subseqüentemente, houve acusações de que a RSA Security inseriu intencionalmente uma porta dos fundos da NSA em seus produtos, possivelmente como parte do programa Bullrun . A RSA negou intencionalmente a inserção de uma porta dos fundos em seus produtos.

Também foi teorizado que os RNGs de hardware poderiam ser modificados secretamente para ter menos entropia do que o declarado, o que tornaria a criptografia usando o RNG de hardware suscetível a ataques. Um desses métodos, que foi publicado, funciona modificando a máscara contaminante do chip, que seria indetectável pela engenharia reversa óptica. Por exemplo, para geração de números aleatórios no Linux, é visto como inaceitável usar o hardware RDRAND da Intel RNG sem misturar a saída RDRAND com outras fontes de entropia para neutralizar quaisquer backdoors no RNG de hardware, especialmente após a revelação do programa NSA Bullrun .

Em 2010, um sorteio da loteria dos EUA foi manipulado pelo diretor de segurança da informação da Multi-State Lottery Association (MUSL), que instalou secretamente malware backdoor no computador RNG seguro da MUSL durante a manutenção de rotina. Durante os hacks, o homem ganhou uma quantia total de $ 16.500.000 ao prever os números corretamente algumas vezes no ano.

A randomização do layout do espaço de endereço (ASLR), uma mitigação contra o rowhammer e ataques relacionados ao hardware físico dos chips de memória foi considerada inadequada no início de 2017 pela VUSec. O algoritmo de número aleatório, se baseado em um registrador de deslocamento implementado em hardware, é previsível em valores suficientemente grandes de p e pode sofrer engenharia reversa com poder de processamento suficiente ( Brute Force Hack ). Isso também significa indiretamente que o malware que usa esse método pode ser executado em GPUs e CPUs, se codificado para isso, até mesmo usando GPU para quebrar o ASLR na própria CPU.

Veja também

Referências

Leitura adicional

links externos