Questão Como os números pseudo-aleatórios e verdadeiramente aleatórios são diferentes e por que isso importa?


Eu nunca entendi isso. Apenas diga que você escreve um pequeno programa em qualquer idioma que jogue alguns dados (apenas usando dados como exemplo). Depois de 600.000 rolos, cada número teria sido lançado em torno de 100.000 vezes, o que é 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 maior variação é como 0,15. Não é tão aleatório quanto vai ser?

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

651


origem


Dê uma olhada no artigo da wikipedia sobre números aleatórios gerados por hardware Veja também isso - stats.stackexchange.com/questions/32794/… - steadyfish
O que você quer dizer com "joga alguns dados"? Tem um braço robótico e câmera acoplada? - starblue
Enquanto eu concordo com a essência geral do seu tom, muitas vezes nos preocupamos muito com isso, mas isso tem sido explorado na vida real: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
Vejo esta artigo sobre um jogo de poker online que não possui uma verdadeira aleatoriedade do porquê. - Varaquilex
Se você apenas mantiver um contador de 0-5 e lançar um dado de acordo, 666 gorillion times, você obteria uma distribuição igual também. - jcora


Respostas:


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

Eu 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 a primeira, terceira, quinta, sétima e nona cartas no baralho.

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

Suponha que minha segunda carta seja a três de copas. Agora eu corro meu RNG 80 milhões mais vezes usando os 80 milhões de sementes que produzem a rainha de espadas como o primeiro número. Isso me 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. Isso é novamente apenas cerca de 2% dos decks, então agora estamos abaixo de 2 milhões de decks.

Suponha que a terceira carta na minha mão seja o 7 de paus. Eu tenho um banco de dados de 2 milhões de sementes que distribuem minhas duas cartas; Eu corro meu RNG mais 2 milhões de vezes para encontrar os 2% daqueles baralhos que produzem o 7 de paus como a terceira carta, e estamos reduzidos a apenas 40.000 baralhos.

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

Agora você vê porque a aleatoriedade verdadeira é importante? Do jeito que você descreve, você acha que distribuição é importante, mas a distribuição não é o que torna um processo aleatório. Imprevisibilidade é o que faz um processo aleatório.

ATUALIZAR

Com base na (agora excluída devido à sua natureza não construtiva) comentários, pelo menos 0,3% das pessoas que leram isto estão confusas quanto ao meu ponto. Quando as pessoas discutem contra pontos que eu não fiz, ou pior, argumentam para pontos que eu fez fazer no suposição de que eu não as fiz, então sei que preciso explicar com mais clareza e cuidado.

Parece haver uma confusão particular em torno da palavra distribuição então eu quero chamar os usos com cuidado.

As perguntas em questão são:

  • Como 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 o perfeito maneira de gerar um baralho aleatório de cartas para jogar poker. Então, veremos como outras técnicas para gerar decks são diferentes e se é possível aproveitar essa diferença.

Vamos começar supondo que temos uma caixa mágica rotulada TRNG. Como sua entrada nós damos um inteiro n maior ou igual a um, e como sua saída nos dá um número verdadeiramente aleatório entre um e n, inclusive. A saída da caixa é totalmente imprevisível (quando dado um número diferente de um) e qualquer número entre um e n é tão provável quanto outro; quer dizer que o distribuição é uniforme. (Existem outras verificações estatísticas mais avançadas de aleatoriedade que poderíamos realizar; 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 sem cartas. Pedimos à caixa um número entre um e 52 - isto é, TRNG(52). Seja qual for o número que ele devolve, nós contamos que muitas cartas do nosso baralho classificadas e removemos aquela carta. Ele se torna a primeira carta no baralho embaralhado. Então nós pedimos TRNG(51) e faça 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 é aproximadamente 2226. Nós escolhemos um deles de forma verdadeiramente aleatória.

Agora nós negociamos as cartas. Quando eu olho minhas cartas eu tenho nenhuma ideia que cartas você tem. (Além do fato óbvio de que você não tem nenhuma das cartas que eu tenho). Eles poderiam ser qualquer carta, com igual probabilidade.

Então deixe-me ter certeza de que eu explico isso claramente. Nós 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 !, então a distribuição sobre o conjunto de possíveis baralhos é Além disso uniforme.

Tudo bem.

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

A PARTE, DE LADO: Porquê 32? Não poderia ser semeado com um número de 64 ou 256 ou 10000 bits? Certo. Mas (1) na prática, a maioria dos PRNGs prontos para uso são semeados com um número de 32 bits, e (2) se você tem 10000 bits de aleatoriedade para fazer a semente, então por que você está usando um PRNG? Você já tem uma fonte de 10000 bits de aleatoriedade!

De qualquer forma, de volta para como o PRNG funciona: depois de ser semeado, você pode usá-lo da mesma maneira que você 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 saída é mais ou menos uniforme. Isto é, quando perguntamos PRNG para um número entre 1 e 6, obtemos 1, 2, 3, 4, 5 ou 6, aproximadamente, um sexto do tempo, independentemente da semente.

Eu quero enfatizar este ponto várias vezes porque parece ser o que está confundindo certos comentaristas. A distribuição do PRNG é uniforme pelo menos de 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 produziria uma distribuição uniforme de números entre 1 e 6. E segundo, se escolhêssemos um milhão de sementes diferentes e PRNG(6)  uma vez para cada semente, novamente esperamos uma distribuição uniforme de números de 1 a 6. A uniformidade do PRNG em qualquer uma dessas operações não é relevante para o ataque que estou descrevendo.

Este processo é dito ser pseudo-aleatório porque o comportamento da caixa é totalmente determinista; escolhe de um de dois32 possíveis comportamentos baseados na semente. Ou seja, uma vez que é semeado, PRNG(6), PRNG(6), PRNG(6), ...  produz um seqüência de números com uma distribuição uniforme, mas essa sequência é inteiramente determinado pela semente. Para uma determinada sequência de chamadas, por exemplo, PRNG (52), PRNG (51) ... e assim por diante, existem apenas 232 seqüências possíveis. A semente essencialmente escolhe qual delas obtemos.

Para gerar um deck, o servidor agora gera uma semente. (Como? Nós vamos voltar a esse ponto.) Então eles chamam PRNG(52), PRNG(51) e assim por diante, para gerar o baralho, semelhante ao anterior.

Este sistema é suscetível ao ataque que descrevi. Para atacar o servidor nós antecipadamente semeamos nossa própria cópia da caixa com 0 e pedimos PRNG(52) e escreva isso. Então nós re-semente com 1, pedir PRNG(52), e escreva isso, até o máximo de 232-1.

Agora, o servidor de poker que está usando o PRNG para gerar decks tem que 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 meu segundo cartão, posso eliminar 98% a mais, e assim por diante, até que, finalmente, posso chegar a um punhado de sementes possíveis e saber, 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 nós obteríamos cada número aproximadamente um sexto do tempo. Essa distribuição é (mais ou menos) uniformee se a uniformidade dessa distribuição é tudo o que você se preocupa, isso é bom. O ponto da questão era Existem outras coisas que a distribuição de PRNG(6) que nos importamos? e a resposta é sim. Nos preocupamos com imprevisibilidade também.

Outra maneira de olhar para o problema é que, embora a distribuição de um milhão de chamadas para PRNG(6) pode estar bem porque o PRNG está escolhendo entre apenas 232 Comportamentos possíveis, não pode gerar todos os baralhos possíveis.  Só pode gerar 232 dos 2226 possíveis baralhos; uma pequena fração. Então a distribuição sobre o conjunto de todos os decks é muito ruim. Mas, novamente, o ataque fundamental aqui é baseado em nós sermos capazes de prever o comportamento passado e futuro de PRNG de uma pequena amostra de sua saída.

Deixe-me dizer isso uma terceira ou quarta vez para garantir que isso afunda. Há 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á. Em segundo lugar, 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 de baralhos escolhidos pelo processo pseudo-aleatório que descrevi. Essa distribuição é extremamente pobre; apenas uma pequena fração dos decks IRL possíveis pode ser escolhida. O ataque depende do previsibilidade do comportamento do PRNG com base no conhecimento parcial de sua saída.

TANTO: Este ataque requer que o atacante saiba ou consiga adivinhar qual é o algoritmo exato usado pelo PRNG. Se isso é realista ou não, é uma questão em aberto. Contudo, Ao projetar um sistema de segurança, você deve projetá-lo para estar protegido contra ataques, mesmo que o invasor saiba todos os algoritmos do programa.. Dito de outra forma: a parte de um sistema de segurança que deve permanecer secreta para que o sistema seja seguro é chamada de "chave". Se o seu sistema depende da segurança dos algoritmos que você usa como segredo, então sua chave contém esses algoritmos. Isso é um extremamente posição fraca para estar em!

Se movendo.

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

Nosso ataque original nos obriga a armazenar 232 mapeamentos de sementes para PRNG(52). Mas 2256 é um número muito maior; é completamente inviável correr CPRNG(52)que muitas vezes e armazenar os resultados.

Mas suponha que haja algum de outros maneira de levar o valor de CPRNG(52) e daí deduzir um fato sobre a semente? Nós fomos muito burros até agora, apenas forçando 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 saída?

Não. Os detalhes são complicados demais para explicar, mas os CPRNGs são inteligentemente projetados para que seja impossí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 quão grande.

OK, agora vamos supor que o servidor esteja usando CPRNG para gerar decks. Precisa de uma semente de 256 bits. Como escolhe essa semente? Se escolher qualquer valor que um invasor possa prever então de repente o ataque se torna viável novamente. Se pudermos determinar que dos 2256 possíveis sementes, apenas quatro bilhões delas provavelmente serão escolhidas pelo servidor, Estamos de volta ao negócio. Podemos montar este ataque novamente, prestando atenção apenas ao 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 - isto é, cada semente possível é escolhida com probabilidade de 1/2256. Basicamente, o servidor deve estar chamando TRNG(2^256)-1 para gerar a semente para CPRNG.

E se eu conseguir hackear o servidor e olhar para ele para ver qual semente foi escolhida? Nesse caso, o atacante sabe 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 sucesso, provavelmente também posso transferir o dinheiro para minha conta bancária diretamente, então talvez não seja interessante. O ponto é: a semente tem que ser um segredo difícil de adivinhar, e um número de 256 bits verdadeiramente aleatório é muito difícil de adivinhar.)

Voltando ao meu ponto anterior sobre a defesa em profundidade: a semente de 256 bits é a chave para este sistema de segurança. A ideia de um CPRNG é que o sistema é seguro contanto que a chave esteja segura; mesmo que todos os outros fatos sobre o algoritmo sejam conhecidos, contanto que você consiga manter a chave secreta, as cartas do oponente são imprevisíveis.

OK, então a semente deve ser tanto secreta quanto uniformemente distribuída, porque se não for, podemos montar um ataque. Temos por suposição que a distribuição de produtos de CPRNG(n) é uniforme. E quanto à distribuição sobre o conjunto de todos os baralhos possíveis?

Você pode dizer: existem 2256 seqüências possíveis de saída pelo CPRNG, mas existem apenas 2226 possíveis baralhos. Portanto, existem mais seqüências possíveis do que decks, então estamos bem; cada baralho IRL possível é agora (com alta probabilidade) possível neste sistema. E esse é um bom argumento, exceto ...

2226 é apenas um aproximaçãode 52 !. Divida isso. 2256/ 52! não pode ser um número inteiro porque, por um lado, 52! é divisível por 3 mas nenhum poder de dois é! Como este não é um número inteiro agora, temos a situação em que todos os decks são possível, mas alguns baralhos 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 cartas, A, B e C. Suponha que usemos um PRNG com uma semente de 8 bits, então existem 256 sementes possíveis. Existem 256 saídas possíveis de PRNG(3) dependendo da semente; não há como um terço deles ser A, um terço deles ser B e um terço deles ser C, porque 256 não é divisível por 3. Tem que haver um pequeno viés em relação a um deles.

Da mesma forma, 52 não divide uniformemente em 2256, então deve haver algum preconceito em relação a algumas cartas como a primeira carta escolhida e um viés longe dos outros.

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 de decks ainda é falha. Alguns decks são muito levemente mais provável do que outros.

Agora a questão é: temos um ataque baseado nessa falha? e a resposta é na prática, provavelmente não. CPRNGs são projetados para que se a semente é verdadeiramente aleatória então é computacionalmente inviável dizer a diferença entre CPRNG e TRNG.

OK, então vamos resumir.

Como 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 aplicações onde a segurança do sistema depende imprevisibilidade.

  • Se um TRNG for usado para escolher cada cartão, o sistema será inatacá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 ordinário com um pequeno espaço de semente é usado, então 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 produção do PRNG?

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

Como vimos, ambos PRNG e CPRNG produzir pobres distribuições da probabilidade de escolher qualquer baralho individual de todos os baralhos possíveis. 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 CPRNG ou PRNG?

Duas razões.

Primeiro: despesa. O TRNG é caro. Gerar números verdadeiramente aleatórios é difícil. CPRNGs dão bons resultados para arbitrariamente muitas chamadas com apenas 1 ligue para o TRNG para a semente. O lado negativo é claro que você tem que manter essa semente em segredo.

Segundo: às vezes nós quer previsibilidade e tudo o que nos interessa é boa distribuição. Se você está gerando dados "aleatórios" como entradas do programa para um conjunto de testes, e isso mostra um bug, então seria bom que a execução do conjunto de testes produzisse novamente o bug novamente!

Espero que agora seja muito mais claro.

Finalmente, se você gostou disso, então você pode desfrutar de algumas leituras adicionais sobre o assunto de aleatoriedade e permutações:


1371



Ok meninos e meninas Isso é o suficiente comentar por agora. Se você quiser discutir isso mais, vá pegar uma sala de chat, kthnxbye! - Ivo Flipse♦
@Eric Mas a semente não é reiniciada antes de cada novo deck ser sorteado, é? Então, enquanto você está certo de que existem apenas relativamente poucos trajetórias estamos provando, você não sabe exatamente onde na trajetória você está no momento e trajetórias se cruzam. - A.S.
Alguém realmente fez algo parecido com isso - EJoshuaS
Um tratamento bom (mas denso) de questões relacionadas está no TAOCP de Knuth vol 2, seção 3.5 “O que é uma sequência aleatória?” (P. 149), começando com as definições iluminadoras de sequências distribuídas equidistribuídas, distribuídas em k e distribuídas em ∞. Seqüências pseudo-aleatórias são discutidas em 3.5.F (p. 170). Veja também os critérios de pseudo-aleatoriedade Teoria da complexidade e BSI alemão. - ShreevatsaR


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 tem uma seqüência no bit menos significativo - ele alternou entre 0 e 1. Portanto, o LSB foi 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 realize o teste um milhão de vezes e, para cada resultado, incremente o array nesse número, ou seja, X [A, B] ++;

Agora desenhe um diagrama 2D, em que quanto maior o número, mais brilhante será 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 seqüência do TCP do sistema Windows NT:

Windows NT 

ou até mesmo este do Windows 98:

Windows 98 

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

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


155



Isso é tão brilhante que traz lágrimas aos meus olhos. Deve haver um aplicativo que os crie para cada sistema operacional (móvel / desktop / servidor) e plataforma (JVM / Javascript / etc). - HDave
A função Windows Rand () é muito boa! Produz uma nuvem que não tem nenhum padrão aparente. Veja minha implementação para tentar (e outros algoritmos): github.com/Zalastax/visualize_random - Zalastax


Embora números pseudo-aleatórios gerados por computadores sejam aceitáveis ​​para a maioria dos casos de uso encontrados pelos usuários de computador, há cenários que exigem completamente números aleatórios 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 que tentar decifrar um sistema de criptografia pode 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 produz valores que são verdadeiramente indiscutíveis. Observe que alguns PRNGs são projetados para serem criptograficamente seguros e são utilizáveis ​​para tais aplicativos sensíveis à segurança.

Mais informações sobre ataques de RNG podem ser encontradas em este artigo da Wikipedia.


91



PRNGs criptográficos existem e são amplamente utilizados. Eles podem, a partir de sementes modestas, gerar um fluxo praticamente ilimitado de números aleatórios. É computacionalmente inviável distinguir tal fluxo de números aleatórios verdadeiros, assim nenhuma informação adicional pode ser obtida de qualquer porção de tal fluxo, e para qualquer propósito prático os números são tão bons quanto números aleatórios verdadeiros. - aaaaaaaaaaaa
Acho que a maneira mais fácil de explicar isso é que os algoritmos de geração de números aleatórios precisam ser programados. Isso significa que há um conjunto de instruções que estão sendo seguidas. Se houver um conjunto de instruções, não pode ser aleatório. - Keltari
@Keltari Você está perdendo o elemento de entropia ... A maioria dos RNGs (pelo menos os criptográficos) reúnem a entrada de fontes externas (por exemplo, movimento do mouse) e usam isso como parte da condição inicial - assim, a transformação de A para B está programado, mas o estado inicial de A (deveria) ser imprudente. Linux's /dev/random manterá uma aproximação de quanto a entropia está disponível e deixará de dar números se cair muito baixo. - Basic
Por curiosidade - por que as lâmpadas de lava são consideradas "verdadeiramente aleatórias"? Eu entendo que exibe um comportamento bastante imprevisível, mas alguém com uma compreensão firme o suficiente sobre a dinâmica de fluidos e como esses fluidos interagem no ambiente gravitacional da Terra pode certamente produzir resultados "previsíveis", não? Claro, as lâmpadas de lava são imprevisíveis, mas para mim, não são aleatórias, mas altamente previsíveis. - theGreenCabbage
@theGreenCabbage: Eu suspeito que as lâmpadas de lava são caóticas. Dado um modelo de computador suficientemente bom e dígitos de precisão suficientes, você poderia (em princípio) prever o comportamento por um tempo. Mas, como o sistema é caótico, duas lâmpadas de lava com a menor mudança nas condições iniciais divergem rapidamente no comportamento. (E esse comentário ignora atratores caóticos). - dmm


Eu tentei em Python: Aqui está o resultado de 60 milhões de rolos. A maior variação é como 0,15. Não é tão aleatório quanto vai ser?

Na verdade, é então "bom" é ruim... Todas as respostas existentes se concentram em previsibilidade dada uma pequena seqüência de valores iniciais. Eu quero levantar outra questão:

seu distribuição tem desvio padrão muito menor do que rolos aleatórios deve

Verdadeira aleatoriedade simplesmente não chega aquele perto de calcular a média "quase exatamente 1 sobre quantos números ele pode escolher" que você está usando como uma indicação de qualidade.

Se você olhar essa pergunta do Stack Exchange sobre distribuições de probabilidade para vários lançamentos de dados, você verá uma fórmula para o desvio padrão das jogadas 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 jogadas você tem menos da metade do stddev, e em 60 milhões você está abaixo de um terço - está ficando pior, 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 biblioteca C rand() A função comumente tem um período de 2 ^ 32, e eles visitam cada número 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 (%) os resultados 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 o desvio padrão, portanto, apenas trivialmente acima de 0. Usando Na fórmula acima, o desvio padrão correto para 2 ^ 32 rolos é 111924. De qualquer forma, à medida que seu número de rolos pseudo-aleatórios aumenta você converge para 0 desvio padrão. A questão pode ser significativa quando o número de rolos é uma fração significativa do período, mas alguns pseudo-RNGs podem apresentar problemas piores - ou problemas mesmo com menos amostras - do que outros.

Assim, mesmo que você não se importe com vulnerabilidades criptográficas, em alguns aplicativos você pode se preocupar em ter distribuições que não tenham resultados excessivamente altos e artificialmente. Alguns tipos de simulação estão especificamente tentando descobrir as conseqüências da desigual resultados que ocorrem naturalmente com grandes amostras de resultados aleatórios individuais, mas estão sub-representados em alguns resultados do pRNG. Se você está tentando simular como uma enorme população reage a algum evento, essa questão pode radicalmente altere seus resultados levando a conclusões extremamente imprecisas.


Para dar um exemplo concreto: Digamos que um matemático diga a um programador de máquina de pôquer que depois de 60 milhões de testes simulados - usado para cintilar centenas de pequenas "luzes" ao redor da 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. Por o Regra 68–95–99.7 (Wikipedia) isso deve acontecer 16% do tempo (~ 68% caem dentro de um desvio padrão / apenas metade fora estão acima). Com o seu gerador de números aleatórios, isso é de cerca de 3,5 desvios padrão acima da média: 0,025% chance - quase nenhum cliente obtém esse benefício. Veja a tabela Desvios Mais Elevados na página que acabamos de mencionar, 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                |

75



Você está comparando maçãs e laranjas aqui. Os dois desvios padrão não têm absolutamente nada a ver um com o outro. - Jbeuh


Eu acabei de escrever este gerador de números aleatórios para gerar jogadas de 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ê ficaria feliz em 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 pela mesma razão que o gerador de números aleatórios simplista acima é ruim - eles não são adequados para situações em que você precisa de imprevisibilidade genuína, não apenas a distribuição correta.


50



"Geradores de números pseudo-aleatórios ... geram números previsíveis com a distribuição correta" - Só porque é um PRNG não garante que tenha uma distribuição perfeita (na verdade, os comerciais em geral não o fazem, exatamente razões descritas nestas respostas). Enquanto eles podem ser previsíveis, dada a informação suficiente (o algoritmo usado, a semente inicial, os valores de saída, w / e), eles ainda têm variância. - Brian S
Além do ponto, eu sei, mas get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on é muito elegante para não mencionar :) - Janus Troelsen
@BrianS Na verdade, um PRNG que falhava nos testes de distribuição ao longo do tempo seria previsível por definição. Então, ao longo de um N grande, se você chegar a um pouco de N / 2 em N coin flips, você pode começar a apostar em heads, e você pode ganhar mais do que perder. Da mesma forma, se você tem uma distribuição perfeita de cara x coroa, mas cara sempre vem em pares, então você teria novamente uma receita para ganhar. Os testes de distribuição são como você sabe que um PRNG é bom. - Jon Kiparsky
Você esqueceu nonlocal next :-). - Kos
Exemplo ainda melhor: Pi é acreditado para ser normal, o que significa que qualquer seqüência de dígitos de qualquer comprimento determinado em qualquer base não aparece com mais freqüência do que qualquer outra seqüência daquele comprimento naquela base. Um algoritmo que, quando solicitado n bits aleatórios, leva o próximo n pedaços de pi e os retorna (a "semente" é o bit que você inicia), deve, no longo prazo, produzir uma distribuição perfeitamente uniforme. Mas você ainda não iria querer isso para o seu gerador - alguém que conhece o último grupo de bits que você gerou pode encontrar a primeira vez que a sequência ocorre, suponha que sua semente esteja lá e provavelmente esteja correta. - cpast


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 momento em que precise de um número realmente aleatório.

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

Se você estiver interessado nas aplicações de números aleatórios, verifique Artigo da Wikipédia.


26



O grande problema é quando você precisa de números aleatórios que um atacante não pode prever por razões de segurança. - David Schwartz
Você tem certeza que pode se deparar com um momento em que você precisa de um número verdadeiramente aleatório. É o suficiente para abrir uma página da web que começa com https://... - Jan Hudec
@JanHudec: Bem, no uso diário, você precisará de números aleatórios seguros no momento em que abrir qualquer programa, bem antes de digitar em uma barra de endereços: consulte randomização de layout de espaço de endereço. É por isso coisas assim acontece. - Reid
@JanHudec Eu estava falando especificamente no sentido de que você precisaria usar um gerador de números aleatórios on-line. Os números aleatórios verdadeiros são usados ​​com frequência, mas muito poucas pessoas realmente precisam gerá-los. - Alex McKenzie
Slot machines também usam um PRNG, não um TRNG. O gerador funciona o tempo todo e um número é escolhido na hora exata em que o botão giratório é pressionado. A soma do PRNG e o tempo de pressionamento de botão verdadeiramente aleatório equivale a um TRNG. - Roger Dahl


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. Então isso vai ser um desastre para segurança em criptografia.

Por exemplo, a seguinte função geradora de números aleatórios usada em glibc não gera um número puramente aleatório. O número pseudo-aleatório gerado por isso pode ser adivinhado. É um erro por questões de segurança. Há uma história de isso se tornar 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 estatisticamente significativo.

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

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

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

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


26



Eu culpo as coisas WEP em um protocolo mal projetado usando uma cifra fraca. Com as modernas cifras de fluxo, você pode usar um contador como IV. - CodesInChaos
O principal problema com o WEP foi repetir a chave em quadros de 2 ^ 24 (quase 16 milhões). Foi ainda pior com as chaves relacionadas que tornaram possível quebrar o código em cerca de 40000 quadros. O ponto principal aqui é que a chave não é aleatória. Está intimamente relacionado, de modo que é tão fácil de quebrar. - Prabhu
Pseudo-aleatoriedade é ruim em criptografia somente ao gerar chaves criptográficas. Está perfeitamente bem além disso. De fato, o RC4 é pouco mais que um gerador de números pseudo-aleatórios semeados com a expansão de 128 bits da chave XORed no texto simples da mensagem. - Matt


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

Aqui está um bom vídeo sobre esse assunto: http://www.youtube.com/watch?v=itaMNuWLzJo 


12



Previsibilidade! = Repetindo. Mersenne Twister é um bom exemplo disso. Na maioria das implementações após o 624 Int32 você pode prever todo o próximo número, mas a sequência do Mersenne Twister é muito mais longa que aquela (2 ^ 19937 - 1). - HoLyVieR
Eu não entendo porque esta resposta não é empurrada para a pilha, pois isso me parece que esta é a resposta precisa e concisa para a pergunta, pelo menos parcialmente. Pseudo-números aleatórios podem ser facilmente previstos após alguns sorteios, variando o número de empates com o algoritmo pseudo-aleatório "qualidade". Selecionando um algoritmo "bom" está olhando para aspectos: 1. todo valor é desenhado em igual frequência (distribuição), 2. leva um "longo tempo" para reiniciar a sequência no começo e começar a desenhar novamente os mesmos números no mesma ordem. - mins
"números aleatórios verdadeiros não são [previsíveis]". Pois hoje isso é verdade. Agora, se acreditamos na teoria do Big Bang, e temos muito poder para calcular o estado do Universo a qualquer momento após o BB, com base na física, então ... somos capazes de prever o futuro, incluindo o fato de que Eu estou escrevendo este comentário muito exato. Certo? - mins
Isso é hipoteticamente verdade, entretanto, considerando o vasto grau de entropia envolvido nas ações reais dos corpos reais, o poder computacional necessário seria ridiculamente grande. Pense em continentes cobertos de computadores. Além disso, devido à dependência do estado anterior, o estado de cada corpo no universo em cada ponto do tempo precisaria ser armazenado, o que, por definição, exigiria mais espaço do que o disponível no universo, completamente preenchido com aparato de memória. - TheEnvironmentalist
@TheEnvironmentalist - Ah! "Continentes cobertos de computadores" ... não é isso que "O Guia do Mochileiro das Galáxias"? ;-) - ysap


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 de resultados total) com alguma pequena variação (que você veria se fosse lançar um dado 600k vezes);

No entanto, quando se trata de coisas como segurança de computadores; Verdadeira aleatoriedade é necessária.

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

Se um invasor puder saber 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 deve saber!)

Com a sua chave privada, um atacante pode fazer coisas como: a) Fale com seu banco fingindo ser você, b) Escute seu tráfego de internet "seguro" e decodifique-o, c) Divirta-se entre você e outras pessoas na Internet.

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


10





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

Algumas pessoas não acreditariam em mim, isso era 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 dos 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 podem melhorar o tráfego. Nesse caso, você poderá recriar os mesmos dados de tráfego (como pessoas tentando entrar em uma cidade) com ações diferentes que tentou melhorar o tráfego.


10





A resposta curta é que geralmente as pessoas exigem "aleatoriedade verdadeira" por uma razão ruim, a saber, que elas não entendem de criptografia.

Primitivas criptográficas, como cifras de fluxo e CSPRNGs são usados ​​para produzir grandes fluxos de bits imprevisíveis, uma vez que tenham sido alimentados com alguns bits imprevisíveis.

O leitor atento agora percebeu que há um problema de bootstrapping aqui: precisamos juntar alguns bits de entropia para iniciar tudo. Então, pode alimentá-los com um CSPRNG que, por sua vez, fornecerá alegremente todos os bits imprevisíveis de que precisamos. portanto um RNG de hardware é necessário para semear um CSPRNG. Este é o único caso em que a entropia é necessária na verdade.

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

Edit: No final, deve-se 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 têm vieses.

Edit: Algumas pessoas aqui assumem um modelo de ameaça em que um invasor pode ler o estado interno de um CSPRNG e de lá chegar à conclusão de que os CSPRNGs não são uma solução segura. Este é um exemplo de modelagem de thread pobre. Se um atacante é dono do seu sistema, o jogo acabou, claro e simples. Não faz diferença se você usa um TRNG ou um CSPRNG neste momento.

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

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


8



Não é necessariamente uma questão de segurança. Eu acho que existem razões para usar números verdadeiramente aleatórios que não envolvem segurança. Se eu estivesse fazendo alguma pesquisa científica que dependesse de números aleatórios e fosse por alguma razão crítica que os números fossem tão aleatórios quanto possível, eu certamente aproveitaria um RNG de hardware para ter certeza de que as propriedades observadas não são devidas. às peculiaridades do RNG. - Kef Schecter
@ KefSchecter Os seus PRNGs de hardware ouvidos geralmente têm resultados tendenciosos e / ou correlacionados. Eles precisam de um passo de pós-processamento para transformá-lo em saída independente uniforme. Não há razão para acreditar que essa etapa de pós-processamento seja mais confiável do que uma cifra de fluxo moderna. Eu certamente confiaria mais na cifra de fluxo. Como um bônus extra, é reproduzível, o que é valioso na ciência. - CodesInChaos
OK, é justo. Mas o mesmo não se aplica igualmente às aplicações de criptografia? Até mesmo a resposta gievn aqui diz que você precisa de um RNG de hardware para semear o CSPRNG. - Kef Schecter
@ KefSchecter Sim, os aplicativos de criptografia precisam de números aleatórios reais para propagar o CSPRNG. Mas para tudo o mais, podemos usar esse CSPRNG. - CodesInChaos
@ KefSchecter: Aplicativos criptográficos exigem que o fluxo não seja reproduzível pelo mundo em geral. Em contraste, em aplicações científicas, ser capaz de mostrar que os números "aleatórios" que alguém está usando não foram simplesmente escolhidos para mostrar a análise de uma boa luz é útil. Por exemplo, se alguém anuncia, depois de anunciar seus métodos, que os dados de certa forma serão gerados usando os números das loterias estaduais do dia seguinte, os leitores podem estar confiantes de que não se falsificaram os resultados, mesmo que o desenho da semana tenha apenas algumas dúzias. pedaços de entropia. - supercat