Qual a diferença entre números pseudo-aleatórios e verdadeiramente aleatórios e por que isso importa?

Eu nunca consegui isso. Basta dizer que você escreve um pequeno programa em qualquer idioma que lança alguns dados (apenas usando dados como exemplo). Após 600.000 lançamentos, cada número teria sido rolado cerca de 100.000 vezes, o que eu esperaria.

Por que existem sites dedicados à 'verdadeira aleatoriedade'? Certamente, dada a observação acima, as chances de obter qualquer número são quase exatamente 1 sobre quantos números ele pode escolher.

Eu tentei em Python : aqui está o resultado de 60 milhões de rolos. A variação mais alta é igual a 0,15. Isso não é tão aleatório quanto possível?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

Vamos jogar poker no computador, apenas você, eu e um servidor em que ambos confiamos. O servidor usa um gerador de números pseudo-aleatórios que é inicializado com uma semente de 32 bits antes de jogar. Portanto, existem cerca de quatro bilhões de decks possíveis.

Recebo cinco cartas na minha mão - aparentemente não estamos jogando Texas Hold 'Em. Suponha que as cartas sejam distribuídas uma para mim, uma para você, uma para mim, uma para você e assim por diante. Então, eu tenho as primeiras, terceira, quinta, sétima e nona cartas do baralho.

Anteriormente, executei o gerador de números pseudo-aleatórios quatro bilhões de vezes, uma vez com cada semente, e escrevi o primeiro cartão gerado para cada um em um banco de dados. Suponha que minha primeira carta seja a dama de espadas. Isso mostra apenas uma como a primeira carta em uma em cada 52 desses decks possíveis, então reduzimos os decks possíveis de quatro bilhões para cerca de 80 milhões.

Suponha que minha segunda carta seja a de três corações. Agora eu corro meu RNG 80 milhões mais vezes usando as 80 milhões de sementes que produzem a rainha de espadas como o primeiro número. Isso leva alguns segundos. Eu escrevo todos os baralhos que produzem os três corações como a terceira carta - a segunda carta na minha mão. Novamente, isso representa apenas cerca de 2% dos decks, então agora estamos com 2 milhões de decks.

Suponha que a terceira carta na minha mão seja a 7 dos clubes. Eu tenho um banco de dados de 2 milhões de sementes que distribuem meus dois cartões; Eu corro meu RNG mais 2 milhões de vezes para encontrar os 2% desses decks que produzem os 7 dos clubes como a terceira carta, e estamos com apenas 40 mil decks.

Você vê como isso acontece. Eu corro meu RNG 40000 mais vezes para encontrar todas as sementes que produzem minha quarta carta e isso nos leva a 800 decks, e depois corro 800 mais vezes para obter as ~ 20 sementes que produzem minha quinta carta, e agora apenas gere esses vinte baralhos de cartas e eu sei que você tem uma das vinte mãos possíveis. Além disso, tenho uma ideia muito boa do que vou desenhar a seguir.

Agora você vê por que a verdadeira aleatoriedade é importante? Da maneira como a descreve, você acha que a distribuição é importante, mas a distribuição não é o que torna um processo aleatório. Imprevisibilidade é o que torna um processo aleatório.

ATUALIZAR

Com base nos comentários (agora excluídos devido à sua natureza pouco construtiva), pelo menos 0,3% das pessoas que leram isso estão confusas quanto ao meu argumento. Quando as pessoas argumentam contra pontos que eu não fiz, ou pior, argumentam por pontos que eu assumi na suposição de que não os fiz, então eu sei que preciso explicar de maneira mais clara e cuidadosa.

Parece haver uma confusão particular em torno da distribuição de palavras, por isso quero chamar os usos com cuidado.

As perguntas em questão são:

• Como os números pseudo-aleatórios e números verdadeiramente aleatórios diferem?
• Por que a diferença é importante?
• As diferenças têm algo a ver com a distribuição da saída do PRNG?

Vamos começar considerando a maneira perfeita de gerar um baralho aleatório com o qual jogar poker. Depois, veremos como outras técnicas para gerar decks são diferentes e se é possível tirar proveito dessa diferença.

Vamos começar supondo que temos uma caixa mágica rotulada TRNG. Como entrada, damos a ele um número inteiro n maior ou igual a um e, como saída, nos fornece um número verdadeiramente aleatório entre um e n, inclusive. A saída da caixa é totalmente imprevisível (quando é fornecido um número diferente de um) e qualquer número entre um e n é tão provável quanto outro; isto é, a distribuição é uniforme . (Existem outras verificações estatísticas mais avançadas da aleatoriedade que poderíamos executar; estou ignorando esse ponto, pois não é pertinente ao meu argumento. O TRNG é perfeitamente estatisticamente aleatório por suposição.)

Começamos com um baralho de cartas não embaralhadas. Pedimos à caixa um número entre um e 52 - ou seja TRNG(52),. Qualquer que seja o número que devolvemos, contamos muitas cartas do nosso baralho classificado e as removemos. Torna-se a primeira carta no baralho embaralhado. Em seguida, solicitamos TRNG(51)e fazemos o mesmo para selecionar o segundo cartão, e assim por diante.

Outra maneira de ver é: são 52! = 52 x 51 x 50 ... x 2 x 1 decks possíveis, que são aproximadamente 2 ²²⁶ . Nós escolhemos um deles verdadeiramente ao acaso.

Agora nós negociamos as cartas. Quando olho para minhas cartas, não tenho idéia de quais cartas você tem. (Além do fato óbvio de que você não possui nenhuma das cartas que tenho.) Elas podem ser quaisquer cartas, com igual probabilidade.

Então deixe-me explicar isso claramente. Temos distribuição uniforme de cada saída individual de TRNG(n); cada um escolhe um número entre 1 e n com probabilidade 1 / n. Além disso, o resultado desse processo é que escolhemos um dos 52! decks possíveis com uma probabilidade de 1/52 !, portanto, a distribuição no conjunto de decks possíveis também é uniforme.

Tudo certo.

Agora vamos supor que temos uma caixa menos mágica, rotulada PRNG. Antes de poder usá-lo, ele deve ser semeado com um número não assinado de 32 bits.

LADO: Por que 32 ? Não foi possível semear com um número de 64, 256 ou 10000 bits? Certo. Mas (1) na prática, a maioria dos PRNGs disponíveis no mercado é semeada com um número de 32 bits e (2) se você possui 10000 bits de aleatoriedade para fazer a semente, por que está usando um PRNG? Você já tem uma fonte de 10000 bits de aleatoriedade!

De qualquer forma, voltando ao modo como o PRNG funciona: depois de semeado, você pode usá-lo da mesma maneira que usa TRNG. Ou seja, você passa um número, n, e retorna um número entre 1 e n, inclusive. Além disso, a distribuição dessa produção é mais ou menos uniforme . Ou seja, quando pedimos PRNGum número entre 1 e 6, obtemos 1, 2, 3, 4, 5 ou 6 aproximadamente um sexto das vezes, independentemente da semente.

Quero enfatizar esse ponto várias vezes, porque parece ser o que está confundindo certos comentaristas. A distribuição do PRNG é uniforme de pelo menos duas maneiras. Primeiro, suponha que escolhemos qualquer semente em particular. Esperamos que a sequência PRNG(6), PRNG(6), PRNG(6)...um milhão de vezes produza uma distribuição uniforme de números entre 1 e 6. E segundo, se escolhermos um milhão de sementes diferentes e chamarmos PRNG(6) uma vez para cada semente, novamente esperaremos uma distribuição uniforme de números de 1 a 6. 6. A uniformidade do PRNG em qualquer uma dessas operações não é relevante para o ataque que estou descrevendo .

Diz-se que esse processo é pseudo-aleatório porque o comportamento da caixa é realmente totalmente determinístico; ele escolhe entre um dos 2 ³² comportamentos possíveis com base na semente. Ou seja, uma vez semeada, PRNG(6), PRNG(6), PRNG(6), ... produz uma sequência de números com uma distribuição uniforme, mas essa sequência é inteiramente determinada pela semente. Para uma determinada sequência de chamadas, digamos, PRNG (52), PRNG (51) ... e assim por diante, existem apenas 2 ³² sequências possíveis. A semente escolhe essencialmente qual deles obteremos.

Para gerar um baralho, o servidor agora gera uma semente. (Como? Voltaremos a esse ponto.) Em seguida, eles chamam PRNG(52), PRNG(51)e assim por diante para gerar o convés, semelhante ao anterior.

Este sistema é suscetível ao ataque que descrevi. Para atacar o servidor, primeiro, antecipadamente, semeamos nossa própria cópia da caixa com 0 e pedimos PRNG(52)e anotamos isso. Em seguida, reintroduzimos 1, pedimos PRNG(52)e escrevemos isso até 2 ³² -1.

Agora, o servidor de poker que está usando o PRNG para gerar decks deve gerar uma semente de alguma forma. Não importa como eles fazem isso. Eles poderiam ligar TRNG(2^32)para obter uma semente verdadeiramente aleatória. Ou eles poderiam tomar o tempo atual como uma semente, o que dificilmente é aleatório; Eu sei que horas são tanto quanto você. O ponto do meu ataque é que isso não importa, porque eu tenho meu banco de dados . Quando vejo meu primeiro cartão, posso eliminar 98% das sementes possíveis. Quando vejo minha segunda carta, posso eliminar 98% a mais, e assim por diante, até que finalmente chegue a um punhado de sementes possíveis e saiba com alta probabilidade o que está em sua mão.

Agora, novamente, quero enfatizar que a suposição aqui é que, se ligássemos PRNG(6)um milhão de vezes, obteríamos cada número aproximadamente um sexto das vezes . Essa distribuição é (mais ou menos) uniforme , e se a uniformidade dessa distribuição é tudo o que importa , tudo bem. O ponto principal da pergunta era : existem outras coisas além dessa distribuição com a PRNG(6)qual nos preocupamos? e a resposta é sim . Também nos preocupamos com a imprevisibilidade .

Outra maneira de analisar o problema é que, embora a distribuição de um milhão de chamadas PRNG(6)seja boa, porque o PRNG está escolhendo entre apenas ³² comportamentos possíveis, ele não pode gerar todos os baralhos possíveis. Só pode gerar 2 ³² dos 2 ²²⁶ decks possíveis; uma pequena fração. Portanto, a distribuição no conjunto de todos os decks é muito ruim. Mas, novamente, o ataque fundamental aqui se baseia em sermos capazes de prever com sucesso o comportamento passado e futuro de PRNGuma pequena amostra de sua produção.

Deixe-me dizer isso uma terceira ou quatro vezes para garantir que isso aconteça. Existem três distribuições aqui. Primeiro, a distribuição do processo que produz a semente aleatória de 32 bits. Isso pode ser perfeitamente aleatório, imprevisível e uniforme, e o ataque ainda funcionará . Segundo, a distribuição de um milhão de chamadas para PRNG(6). Isso pode ser perfeitamente uniforme e o ataque ainda funcionará. Terceiro, a distribuição dos decks escolhidos pelo processo pseudo-aleatório que descrevi. Essa distribuição é extremamente ruim; apenas uma pequena fração dos decks possíveis da IRL pode ser escolhida. O ataque depende da previsibilidade do comportamento do PRNG com base no conhecimento parcial de sua saída .

À parte: Esse ataque exige que o invasor saiba ou seja capaz de adivinhar qual é o algoritmo exato usado pelo PRNG. Se isso é realista ou não, é uma questão em aberto. No entanto, ao projetar um sistema de segurança, você deve projetá-lo para ser seguro contra ataques, mesmo que o invasor conheça todos os algoritmos do programa . Em outras palavras: a parte de um sistema de segurança que deve permanecer em segredo para que o sistema seja seguro é chamada de "chave". Se o seu sistema depende, para sua segurança, dos algoritmos usados ​​como secretos, sua chave contém esses algoritmos . Essa é uma posição extremamente fraca para se estar!

Se movendo.

Agora vamos supor que tenhamos uma terceira caixa mágica rotulada CPRNG. É uma versão com força de criptografia PRNG. É preciso uma semente de 256 bits em vez de uma semente de 32 bits. Ele compartilha com PRNGa propriedade que a semente escolhe entre um dos 2 ²⁵⁶ comportamentos possíveis. E, como nossas outras máquinas, possui a propriedade de que um grande número de chamadas CPRNG(n)produz uma distribuição uniforme de resultados entre 1 e n: cada uma acontece 1 / n do tempo. Podemos executar nosso ataque contra isso?

Nosso ataque original exige que armazenemos 2 ³² mapeamentos de sementes para PRNG(52). Mas 2 ²⁵⁶ é um número muito maior; é completamente inviável executar CPRNG(52)isso muitas vezes e armazenar os resultados.

Mas suponha que exista outra maneira de extrair o valor CPRNG(52)e deduzir um fato sobre a semente. Até agora, fomos muito burros, forçando brutalmente todas as combinações possíveis. Podemos olhar dentro da caixa mágica, descobrir como ela funciona e deduzir fatos sobre a semente com base na produção?

Não. Os detalhes são muito complicados para explicar, mas os CPRNGs são projetados de maneira inteligente, de modo que é inviável deduzir qualquer fato útil sobre a semente da primeira saída de CPRNG(52)ou de qualquer subconjunto da saída, não importa o tamanho .

OK, então agora vamos supor que o servidor esteja usando CPRNGpara gerar decks. Ele precisa de uma semente de 256 bits. Como ele escolhe essa semente? Se escolher qualquer valor que um invasor possa prever , de repente o ataque se tornará viável novamente . Se pudermos determinar que das 2 ²⁵⁶ sementes possíveis, apenas quatro bilhões delas provavelmente serão escolhidas pelo servidor, então estaremos de volta aos negócios . Podemos montar esse ataque novamente, prestando atenção apenas no pequeno número de sementes que podem ser geradas.

Portanto, o servidor deve trabalhar para garantir que o número de 256 bits seja distribuído uniformemente - ou seja, cada semente possível é escolhida com probabilidade de 1/2 ²⁵⁶ . Basicamente, o servidor deve estar chamando TRNG(2^256)-1para gerar a semente CPRNG.

E se eu puder invadir o servidor e examiná-lo para ver qual semente foi escolhida? Nesse caso, o atacante conhece o passado e o futuro completos do CPRNG . O autor do servidor precisa se proteger contra esse ataque! (É claro que se eu conseguir montar esse ataque com êxito, provavelmente também posso transferir o dinheiro diretamente para minha conta bancária, então talvez isso não seja tão interessante. O ponto é: a semente deve ser um segredo difícil de adivinhar, e um um número verdadeiramente aleatório de 256 bits é bastante difícil de adivinhar.)

Voltando ao meu argumento anterior sobre defesa em profundidade: a semente de 256 bits é a chave desse sistema de segurança. A idéia de um CPRNG é que o sistema esteja seguro enquanto a chave estiver segura ; mesmo que todos os outros fatos sobre o algoritmo sejam conhecidos, desde que você mantenha a chave em segredo, as cartas do oponente são imprevisíveis.

OK, então a semente deve ser secreta e distribuída uniformemente, porque, se não for, podemos montar um ataque. Assumimos que a distribuição dos resultados de CPRNG(n)é uniforme. E a distribuição sobre o conjunto de todos os decks possíveis?

Você pode dizer: existem 2 ²⁵⁶ sequências possíveis produzidas pelo CPRNG, mas existem apenas 2 ²²⁶ decks possíveis. Portanto, existem mais sequências possíveis do que os decks, então estamos bem; agora todos os baralhos de IRL possíveis (com alta probabilidade) são possíveis neste sistema. E esse é um bom argumento, exceto ...

2 ²²⁶ é apenas uma aproximação de 52 !. Divida isso. 2 ^256/52 ! não pode ser um número inteiro porque, por um lado, 52! é divisível por 3, mas não há potência de dois! Como esse número não é todo agora, temos a situação em que todos os decks são possíveis , mas alguns são mais prováveis ​​que outros .

Se isso não estiver claro, considere a situação com números menores. Suponha que tenhamos três cartões, A, B e C. Suponha que usemos um PRNG com uma semente de 8 bits, portanto, existem 256 sementes possíveis. Existem 256 saídas possíveis PRNG(3)dependendo da semente; não há como ter um terço deles como A, um terço deles com B e um terço com C porque 256 não é igualmente divisível por 3. Deve haver um pequeno viés em relação a um deles.

Da mesma forma, 52 não se divide uniformemente em 2 ²⁵⁶ , então deve haver algum viés em relação a algumas cartas, como a primeira carta escolhida e uma diferença em relação a outras.

Em nosso sistema original com uma semente de 32 bits, houve um grande viés e a grande maioria dos decks possíveis nunca foi produzida. Neste sistema, todos os decks podem ser produzidos, mas a distribuição dos decks ainda é falha . Alguns decks são um pouco mais prováveis ​​que outros.

Agora, a pergunta é: nós temos um ataque baseado nessa falha? e a resposta está na prática, provavelmente não . CPRNGs são projetados de modo que se a semente é verdadeiramente aleatório , em seguida, é computacionalmente inviável para dizer a diferença entre CPRNGe TRNG.

OK, então vamos resumir.

Como os números pseudo-aleatórios e números verdadeiramente aleatórios diferem?

Eles diferem no nível de previsibilidade que exibem.

• Números verdadeiramente aleatórios não são previsíveis.
• Todos os números pseudo-aleatórios são previsíveis se a semente puder ser determinada ou adivinhada.

Por que a diferença é importante?

Porque existem aplicativos em que a segurança do sistema depende de imprevisibilidade .

• Se um TRNG for usado para escolher cada cartão, o sistema estará indisponível.
• Se um CPRNG for usado para escolher cada cartão, o sistema estará seguro se a semente for imprevisível e desconhecida.
• Se um PRNG comum com um pequeno espaço de semente é usado, o sistema não é seguro, independentemente de a semente ser imprevisível ou desconhecida; um espaço de semente pequeno o suficiente é suscetível a ataques de força bruta do tipo que descrevi.

A diferença tem algo a ver com a distribuição da saída do PRNG?

A uniformidade de distribuição ou a falta dela para chamadas individuais para RNG(n)não é relevante para os ataques que eu descrevi.

Como vimos, tanto um PRNGe CPRNGproduzir distribuições pobres da probabilidade de escolher qualquer plataforma individual de todos os possíveis decks. O PRNGé consideravelmente pior, mas ambos têm problemas.

Mais uma pergunta:

Se o TRNG é muito melhor que o CPRNG, que por sua vez é muito melhor que o PRNG, por que alguém usa o CPRNG ou o PRNG?

Duas razões.

Primeiro: despesa. TRNG é caro . Gerar números verdadeiramente aleatórios é difícil. Os CPRNGs fornecem bons resultados para muitas chamadas arbitrariamente, com apenas uma chamada para o TRNG para a semente. O lado ruim é, obviamente, que você deve manter essa semente em segredo .

Segundo: às vezes queremos previsibilidade e tudo o que importa é uma boa distribuição. Se você estiver gerando dados "aleatórios" como entradas do programa para uma suíte de testes e aparecer um erro, seria bom que a execução da suíte de testes produza o bug novamente!

Espero que agora seja muito mais claro.

Por fim, se você gostou disso, poderá ler mais sobre o assunto aleatoriedade e permutações:

• Suponha que eu tenha distribuído dados aleatórios uniformemente. Como faço para transformá-lo em uma determinada distribuição não uniforme?
• Por que alguns GUIDs são gerados aleatoriamente? Todos os seus bits são aleatórios? (Não.) Posso confiar em um GUID como fonte de verdadeira aleatoriedade? (Não!)
• Como posso gerar grandes números aleatórios usando a notação fatorádica?
  • Como posso transformar isso em uma permutação aleatória?
• Como podemos montar o ataque descrito aqui contra a permutação aleatória?
• Quanto viés é introduzido usando a técnica restante para implementar RNG(n)?

Como Eric Lippert diz, não é apenas distribuição. Existem outras maneiras de medir a aleatoriedade.

Um dos primeiros geradores de números aleatórios possui uma sequência no bit menos significativo - alternava 0 e 1. Portanto, o LSB era 100% previsível. Mas você precisa se preocupar com mais do que isso. Cada bit deve ser imprevisível.

Aqui está uma boa maneira de pensar sobre o problema. Digamos que você esteja gerando 64 bits de aleatoriedade. Para cada resultado, pegue os primeiros 32 bits (A) e os últimos 32 bits (B) e faça um índice em uma matriz x [A, B]. Agora execute o teste um milhão de vezes e, para cada resultado, aumente a matriz com esse número, ou seja, X [A, B] ++;

Agora desenhe um diagrama 2D, onde quanto maior o número, mais brilhante o pixel nesse local.

Se for verdadeiramente aleatório, a cor deve ser um cinza uniforme. Mas você pode obter padrões. Tomemos, por exemplo, este diagrama da "aleatoriedade" no número de sequência TCP do sistema Windows NT:

ou mesmo este do Windows 98:

E aqui está a aleatoriedade da implementação do roteador Cisco (IOS).

Esses diagramas são cortesia do artigo de Michał Zalewski . Nesse caso em particular, se alguém pode prever qual será o número de sequência TCP de um sistema, pode representar esse sistema ao fazer uma conexão com outro sistema - o que permitiria o seqüestro de conexões, interceptação de comunicação etc. E mesmo se Não é possível prever o próximo número 100% das vezes. Se pudermos criar uma nova conexão sob nosso controle , podemos aumentar a chance de sucesso. E quando os computadores podem gerar 100.000 conexões em poucos segundos, as chances de um ataque bem-sucedido variam de astronômicas a possíveis ou até prováveis.

Embora números pseudo-aleatórios gerados por computadores sejam aceitáveis ​​para a maioria dos casos de uso encontrados por usuários de computador, há cenários que requerem números aleatórios completamente imprevisíveis.

Em aplicativos sensíveis à segurança, como criptografia, um gerador de números pseudo-aleatórios (PRNG) pode produzir valores que, embora de aparência aleatória, são de fato previsíveis por um invasor. Alguém tentando invadir um sistema de criptografia poderá adivinhar as chaves de criptografia se um PRNG foi usado e o invasor tiver informações sobre o estado do PRNG. Portanto, para tais aplicações, é necessário um gerador de números aleatórios que produza valores verdadeiramente inimagináveis. Observe que alguns PRNGs foram projetados para serem criptograficamente seguros e são utilizáveis ​​para esses aplicativos sensíveis à segurança.

Mais informações sobre ataques RNG podem ser encontradas neste artigo da Wikipedia .

Eu tentei em Python: aqui está o resultado de 60 milhões de rolos. A variação mais alta é igual a 0,15. Isso não é tão aleatório quanto possível?

Na verdade, é tão "bom" que é ruim ... Todas as respostas existentes se concentram na previsibilidade, dada uma pequena sequência de valores iniciais. Quero levantar outra questão:

    sua distribuição tem um desvio padrão muito menor do que os testes aleatórios

Verdadeira aleatoriedade apenas não vem muito que perto de uma média "quase exatamente 1 sobre a forma como sempre muitos números que podem escolher entre" que você está usando como uma indicação de qualidade.

Se você examinar esta pergunta do Stack Exchange sobre distribuições de probabilidade para vários lançamentos de dados , verá uma fórmula para o desvio padrão de N lançamentos de dados (assumindo resultados genuinamente aleatórios):

 sqrt(N * 35.0 / 12.0).

Usando essa fórmula, o desvio padrão para:

• 1 milhão de rolos é 1708
• 60 milhões de rolos é 13229

Se olharmos para seus resultados:

• 1 milhão de rolos: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) é 804
• 60 milhões de rolos: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) é 3827

Você não pode esperar que o desvio padrão de uma amostra finita corresponda exatamente à fórmula, mas deve chegar bem perto. No entanto, em 1 milhão de rolos, você tem menos da metade do valor padrão do stddev e, em 60 milhões, você tem menos de um terço - está piorando, e isso não é coincidência ...

Os pseudo-RNGs tendem a se mover através de uma sequência de números distintos, começando com a semente e não revisitando o número original por um período específico. Por exemplo, implementações da antiga rand()função de biblioteca C geralmente têm um período de 2 ^ 32 e visitam todos os números entre 0 e 2 ^ 32-1 exatamente uma vez antes de repetir a semente. Então, se você simulou 2 ^ 32 dados rola o pré-módulo (%) incluiriam cada número de 0 a 2 ^ 32, as contagens para cada resultado 1-6 seriam 715827883 ou 715827882 (2 ^ 32 não é um múltiplo de 6) e, portanto, o desvio padrão apenas trivialmente acima de 0. na fórmula acima, o desvio padrão correto para rolos de 2 ^ 32 é 111924. De qualquer forma, à medida que o número de rolos pseudo-aleatórios aumenta, você converge para o desvio padrão de 0. Pode-se esperar que o problema seja significativo quando o número de rolos é uma fração significativa do período, mas alguns pseudo-RNGs podem exibir problemas piores - ou mesmo com menos amostras - do que outros.

Portanto, mesmo que você não se importe com vulnerabilidades criptográficas, em alguns aplicativos, você pode se importar em ter distribuições que não apresentam resultados excessivamente artificialmente. Alguns tipos de simulação estão tentando descobrir especificamente as conseqüências dos resultados desiguais que ocorrem naturalmente com grandes amostras de resultados aleatórios individualmente, mas estão sub-representados em alguns resultados do pRNG. Se você está tentando simular como uma grande população reage a algum evento, esse problema pode alterar radicalmente seus resultados, levando a conclusões imprecisas.

Para dar um exemplo concreto: digamos que um matemático diga a um programador de máquinas de pôquer que, depois de 60 milhões de simulações - costumava piscar centenas de pequenas "luzes" pela tela, se houver 10.013.229 ou mais seis, que o matemático espera ser 1 stddev longe da média, deve haver um pequeno pagamento. De acordo com a regra 68-95-99.7 (Wikipedia), isso deve ocorrer cerca de 16% das vezes (~ 68% caem dentro de um desvio padrão / somente metade fora está acima). Com o seu gerador de números aleatórios, isso é cerca de 3,5 desvios padrão acima da média: menos de 0,025% de chance - quase nenhum cliente obtém esse benefício. Veja a tabela Desvios mais altos na página mencionada, especificamente:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

Acabei de escrever este gerador de números aleatórios para gerar dados

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Você usa assim

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

etc etc Você gostaria de usar este gerador para um programa que rodava um jogo de dados? Lembre-se, sua distribuição é exatamente o que você esperaria de um gerador "verdadeiramente aleatório"!

Geradores de números pseudo-aleatórios fazem essencialmente a mesma coisa - eles geram números previsíveis com a distribuição correta. Eles são ruins pelo mesmo motivo que o gerador simplista de números aleatórios acima é ruim - eles não são adequados para situações em que você precisa de uma imprevisibilidade genuína, não apenas da distribuição correta.

A geração de números aleatórios que seu computador pode executar é adequada para a maioria das necessidades, e é improvável que você encontre um tempo em que precise de um número verdadeiramente aleatório.

A verdadeira geração de números aleatórios tem seus propósitos. Em segurança de computadores, jogos de azar, grandes amostragens estatísticas, etc.

Se você está interessado nas aplicações de números aleatórios, consulte o artigo da Wikipedia .

Os números aleatórios gerados por funções típicas na maioria das linguagens de programação não são números puramente aleatórios. Eles são números pseudo-aleatórios. Como não são números puramente aleatórios, eles podem ser adivinhados com informações suficientes sobre números gerados anteriormente. Portanto, isso será um desastre para a segurança na criptografia .

Por exemplo, a seguinte função geradora de número aleatório usada em glibcnão gera um número puramente aleatório. O número pseudo-aleatório gerado por isso pode ser adivinhado. É um erro grave por questões de segurança. Há uma história disso se tornando desastroso. Isso não deve ser usado em criptografia.

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

Esse tipo de gerador de números pseudo-aleatórios nunca deve ser usado em locais sensíveis à segurança, embora seja estatisticamente significativo.

Um dos famosos ataques à chave pseudo-aleatória é o ataque ao 802.11b WEP . O WEP possui chave de longo prazo de 104 bits, concatenada com IV (contador) de 24 bits para criar a chave de 128 bits, que por sua vez é aplicada ao algoritmo RC4 para gerar chave pseudo-aleatória.

( RC4( IV + Key ) ) XOR (message)

As chaves estavam intimamente relacionadas umas com as outras. Aqui, apenas o IV aumentou 1 em cada etapa e todos os outros permaneceram iguais. Como isso não era puramente aleatório, era desastroso e facilmente decomposto. A chave pode ser recuperada analisando cerca de 40000 quadros, que é questão de minutos. Se o WEP usasse IV de 24 bits puramente aleatório, poderia ser seguro até cerca de 2 ^ 24 (quase 16,8 milhões) quadros.

Portanto, deve-se usar o gerador de números aleatórios puros em questões sensíveis à segurança sempre que possível.

A diferença é que os números gerados por pseudoaleatórios são previsíveis (repetidos) após algum tempo em que os números aleatórios verdadeiros não são. O comprimento necessário para repetir depende do comprimento da semente que é usada para sua geração.

Aqui está um vídeo muito legal sobre esse tópico: http://www.youtube.com/watch?v=itaMNuWLzJo

Suponha que um número pseudo-aleatório possa ser adivinhado por qualquer pessoa antes de ser gerado.

Para aplicações triviais, uma pseudo-aleatoriedade é boa, como no seu exemplo, você obterá aproximadamente a porcentagem correta (aproximadamente 1/6 do conjunto total de resultados) com alguma variação menor (que você veria se lançasse um dado 600k vezes);

No entanto, quando se trata de coisas como segurança de computadores; É necessária uma aleatoriedade verdadeira.

Por exemplo, o algoritmo RSA começa com o computador escolhendo dois números aleatórios (P e Q) e, em seguida, executando várias etapas nesses números para gerar os números especiais conhecidos como chaves públicas e privadas. (A parte importante de uma chave privada é que ela é privada e ninguém mais sabe disso!)

Se um invasor souber quais são os dois números 'aleatórios' que seu computador escolherá, eles poderão executar as mesmas etapas para calcular sua chave privada (aquela que ninguém mais deveria saber!)

Com sua chave privada, um invasor pode fazer coisas como: a) Converse com seu banco fingindo ser você; b) ouça seu tráfego de Internet "seguro" e decodifique-o; c) disfarce entre você e outras partes da Internet.

É aí que a verdadeira aleatoriedade (ou seja, não poder ser adivinhada / calculada) é necessária.

O primeiro número aleatório que eu já usei tinha a excelente propriedade de que, entre dois números aleatórios consecutivos, o segundo fosse maior com uma probabilidade de 0,6. Não 0,5. E o terceiro era maior que o segundo, com probabilidade de 0,6, e assim por diante. Você pode imaginar como isso causa estragos com uma simulação.

Algumas pessoas não acreditariam que isso fosse possível com os números aleatórios sendo igualmente distribuídos, mas obviamente é possível se você observar a sequência (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) onde o segundo de dois números é maior com probabilidade 0.6.

Por outro lado, para simulações, pode ser importante poder reproduzir números aleatórios. Digamos que você faça uma simulação de tráfego e queira descobrir como algumas ações que você pode executar poderiam melhorar o tráfego. Nesse caso, você deseja recriar exatamente os mesmos dados de tráfego (como pessoas tentando entrar em uma cidade) com ações diferentes que você tentou melhorar.

A resposta curta é que geralmente as pessoas exigem "verdadeira aleatoriedade" por um motivo ruim, a saber, que não têm entendimento de criptografia.

Primitivas criptográficas, como cifras de fluxo e CSPRNGs, são usadas para produzir fluxos enormes de bits imprevisíveis, depois de terem sido alimentados com alguns bits imprevisíveis.

O leitor cuidadoso agora terá percebido que há um problema de inicialização aqui: precisamos reunir alguns bits de entropia para iniciar tudo. Em seguida, pode alimentá-los com um CSPRNG que, por sua vez, fornecerá alegremente todos os bits imprevisíveis que precisamos. portanto é necessário um RNG de hardware para propagar um CSPRNG . Este é o único caso em que a entropia é necessária na verdade.

(Acho que isso deveria ter sido publicado em Segurança ou Criptografia.)

Edit: No final, é preciso selecionar um gerador de números aleatórios que seja bom o suficiente para a tarefa prevista e, no que diz respeito à geração de números aleatórios, o hardware não necessariamente equivale a bom. Assim como os PRNGs ruins, as fontes aleatórias de hardware geralmente apresentam vieses.

Editar: algumas pessoas aqui assumem um modelo de ameaça no qual um invasor pode ler o estado interno de um CSPRNG e daí chegar à conclusão de que os CSPRNGs não são uma solução segura. Este é um exemplo de modelagem de encadeamento ruim. Se um invasor possui o seu sistema, o jogo termina, puro e simples. Não faz diferença se você usa um TRNG ou um CSPRNG neste momento.

Edit: Então, para resumir tudo isso ... A entropia é necessária para propagar um CSPRNG. Uma vez feito isso, um CSPRNG fornecerá todos os bits imprevisíveis que precisamos para aplicativos de segurança muito mais rapidamente do que (geralmente) coletamos entropia. Se a imprevisibilidade não for necessária, como na simulação, o Mersenne Twister fornecerá números com boas propriedades estatísticas a uma taxa muito mais alta.

Edit: Qualquer pessoa disposta a entender o problema da geração segura de números aleatórios deve ler o seguinte: http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf

Nem todos os PRNGs são adequados para todos os usos. Por exemplo, Java.util.SecureRandom usa o hash SHA1, que tem um tamanho de saída de 160 bits. Isso significa que existem 2 ¹⁶⁰ fluxos possíveis de números aleatórios que podem vir dele. Simples assim. Você não pode obter mais de 2 ¹⁶⁰ valores do estado interno. Portanto, você não pode obter mais de 2 ¹⁶⁰ fluxos únicos de números aleatórios de uma única semente, não importa de onde sua semente veio. Acredita-se que o Windows CryptGenRandom use um estado de 40 bytes, possui 2 ³²⁰ fluxos possíveis de números aleatórios.

O número de maneiras de embaralhar um baralho de 52 cartas padrão é 52 !, o que é aproximadamente 2 ²²⁶ . Portanto, independentemente da propagação, você não pode usar Java.util.SecureRandom para embaralhar um baralho de cartas. Existem aproximadamente 2 ⁶⁶ possíveis embaralhamento que ele não pode produzir. Claro, não sabemos quais são eles ...

Portanto, se eu tivesse uma fonte de, digamos, 256 bits de aleatoriedade verdadeira (por exemplo, de um cartão Quantis RNG), eu poderia semear um PRNG como CryptGenRandom () com essa semente e então usar o PRNG para embaralhar um baralho de cartões. Se eu replantar com verdadeira aleatoriedade cada shuffle, tudo ficará bem: imprevisível e estatisticamente aleatório. Se eu fizesse o mesmo com o Java.util.SecureRandom, haveria embaralhamento que não poderia ser produzido, porque ele não pode ser propagado com 256 bits de entropia e seu estado interno não pode representar todos os embaralhamento possíveis.

Observe que os resultados java.util.SecureRandom seriam imprevisíveis e estatisticamente aleatórios. Nenhum teste estatístico jamais identificaria um problema! Mas a saída do RNG não é grande o suficiente para cobrir todo o domínio de todas as saídas possíveis necessárias para simular um baralho de cartas.

E lembre-se, se você adicionar os curingas, são 54! que você precisa cobrir, o que requer cerca de ^2.238 possibilidades.

Os números pseudo-aleatórios são gerados usando uma função matemática e um valor inicial (chamado semente ), enquanto os números aleatórios não são. A previsibilidade deles os torna incrivelmente úteis para replays de jogos, pois você só precisa salvar a semente e a entrada do jogador - a IA responderá exatamente da mesma maneira "aleatória" todas as vezes.

A diferença entre o número aleatório "verdadeiro" e o número pseudo-aleatório é a previsibilidade. Esta resposta já foi fornecida.

No entanto, a previsibilidade não é necessariamente uma coisa ruim, como a maioria dos exemplos está mostrando. Aqui está um exemplo prático de um dos raros casos em que a previsibilidade é boa: O Sistema de Posicionamento Global.

Cada satélite usa um código PRN distinto (os códigos Gold ) adequado para a correlação automática ou correlação cruzada necessária para a medição do tempo de propagação do sinal. Para esses códigos Gold, a correlação entre si é particularmente fraca, possibilitando uma identificação inequívoca do satélite, mas permitindo o cálculo da distância pela correlação entre a sequência emitida e o receptor.

Para uma verificação rápida da aleatoriedade, você pega pontos com coordenadas aleatórias em [0; 1) e depois os coloca no cubo k-dimensional. Em seguida, você faz o procedimento para dividir este cubo em subcubos - cada volume do subcubo (ou subsfera) deve ser medido corretamente por esse procedimento com flutuações de acordo com o teorema bem conhecido.

A qualidade da aleatoriedade é importante onde você encontra ...

1. fins de segurança. Quando você gera um número para usar como parâmetro para sua geração de chaves, e é bem previsível - o inimigo descobrirá isso com 100% de probabilidade e tornará o campo de pesquisa muito menor.

2. fins científicos. Na ciência, você deve não apenas ter média média em boas condições, mas também as correlações entre vários números aleatórios devem ser eliminadas. Portanto, se você pegar (a_i - a) (a_ {i + 1} -a) e encontrar sua distribuição, deve corresponder às estatísticas.

A correlação de pares é denominada "aleatoriedade fraca". Se você deseja uma aleatoriedade real, deve ter uma correlação de ordem alta com mais de duas variações.

Hoje, apenas os geradores de mecânica quântica fornecem verdadeira aleatoriedade.

Por que a verdadeira aleatoriedade é importante?

Existem basicamente duas razões principais pelas quais a verdadeira aleatoriedade é necessária:

1. Se você estiver usando o RNG para criptografia (incluindo coisas como apostas em dinheiro real e executando uma loteria), um PRNG fará com que você cifra muito mais fraco do que a análise matemática (que assume um TRNG) que você acredita. O PRNG na verdade não será aleatório, mas possui um padrão - os adversários podem explorar o padrão para decifrar uma cifra que deveria ter sido quebrada.
2. Se você estiver usando o RNG para simular entradas "aleatórias", por exemplo, para teste ou simulação de bugs, um PRNG tornará sua abordagem fraca. Quando você não descobre bugs, sempre haverá essa dúvida incômoda: Existe um erro que não é perceptível no padrão do meu PRNG, mas teria aparecido se eu apenas usasse um TRNG? As descobertas da minha simulação descrevem com precisão a realidade ou o fenômeno que descobri é simplesmente um artefato do padrão do PRNG?

Fora dessas áreas, isso realmente não importa. Advertência: Se o seu PRNG é muito, muito ruim, ainda pode ser inadequado - você não quer fazer um jogo de Craps no qual os dados sempre surgem, seus jogadores não vão gostar.

Como o PRNG do Python não é bom o suficiente?

É muito improvável que você seja capaz de detectar as armadilhas de um PRNG real usando uma metodologia tão simples. A análise estatística dos RNGs é um campo da ciência por si só, e alguns testes muito sofisticados estão disponíveis para comparar a "aleatoriedade" de um algoritmo. Estes são muito mais avançados do que sua simples tentativa.

Todo desenvolvedor de software que cria bibliotecas do mundo real, como os desenvolvedores do Python, usa esses testes estatísticos como parâmetro para verificar se a implementação do PRNG é boa o suficiente. Portanto, exceto em casos de supervisão real do desenvolvedor, é muito improvável que você consiga detectar facilmente um padrão em um PRNG do mundo real. Isso não significa que não há padrão - um PRNG possui um padrão por definição.

Basicamente, você não pode provar que uma fonte é aleatória pela análise matemática da saída; você precisa, por exemplo, de um modelo físico que diga que a fonte é aleatória (como no decaimento radioativo).

Você pode simplesmente executar testes em lote para encontrar correlação estatística nos dados de saída; nesse caso, os dados são comprovadamente não aleatórios (mas também uma fonte aleatória pode ter saídas não aleatórias ou não será verdadeiramente aleatória se não puder fornecer dados específicos). resultado). Caso contrário, se os testes forem aprovados, você poderá dizer que os dados são pseudo-aleatórios.

Passar apenas em alguns testes de aleatoriedade significa que você possui um bom PRNG (gerador de número pseudo-aleatório), que pode ser útil para aplicativos em que a segurança não está envolvida.

Se estiver envolvida segurança (por exemplo, criptografia, geração de um salt de chaves, geração aleatória de números para jogos de azar ...), não basta ter um bom PRNG, ele precisa ter qualidades adicionais, como a saída da função não ser facilmente calculada a partir das saídas anteriores, a função precisa ter um custo computacional desejável (limitado o suficiente para ser utilizável, mas alto o suficiente para derrotar tentativas de força bruta), o hardware que executa a função - ou o dispositivo, no estranho caso de hoje em dia, é um dispositivo analógico - não deve ser facilmente adulterado, etc.

Ter um bom PRNG pode ser útil em jogos para criar padrões novos e imprevisíveis e em criptografia - muito complicado para explicar em um único post, apenas pense como um papel básico que saída do procedimento de criptografia deve ser pseudo-aleatória, não mostrando padrões que poderiam relacionar dados criptografados anteriores com os seguintes dados criptografados, ou relacionar dados de texto sem formatação a dados criptografados, ou relacionar dois textos cifrados diferentes um ao outro (para que suposições possam ser feitas nos textos sem formatação) ...

História curta:

Gera uma semente aleatória usando o microssegundo atual do sistema.

Esse truque é bastante antigo e ainda funciona.

Excluindo o fator força bruta, onde eu posso determinar todas as combinações "apostando" em todos os números possíveis e esse não é o objetivo desta pergunta, especialmente quando a maioria dos números aleatórios é arredondada antes de seu uso.

Digamos um exemplo, eu posso determinar a semente usada usando apenas 10 valores. Então, conhecendo a semente, posso adivinhar o próximo valor.

Se eu usasse a semente = 1, poderia obter a próxima sequência:

1, 2, 3, 4, 5, 6, 7, 8, 9 ... (e deduzo que a semente usou o id 1 e o próximo valor 10)

Mas, o que acontecerá se alterar o envio de todos os valores "enésimos" ?. Alterar a semente pelos microssegundos atuais é um truque barato (isto é, não requer muitos ciclos de CPU).

Então a seqüência agora é: (semente = 1) 1, 2, 3, 4, 5, (semente = 2), 7, 9, 11, 13 ... (15?)

Nesse caso:

a) Não posso deduzir qual semente foi usada.

b) Ergo, não consigo adivinhar o próximo valor.

c) O único palpite que posso fazer é deduzir que a próxima semente pode ser um número importante.

De qualquer forma, os algoritmos mais modernos de gerador aleatório já usam esse truque sob o capô.

O fato é que, não precisamos de um computador quântico para criar um número aleatório "verdadeiro", a imprecisão do cristal de quartzo do nosso computador atua como um gerador aleatório, também a eficiência aleatória de nossa CPU também é variável sem considerar que a CPU geralmente executa várias tarefas ao mesmo tempo.