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

664

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
Peter
fonte
1
Dê uma olhada no artigo da wikipedia sobre números aleatórios gerados por hardware. Veja também - stats.stackexchange.com/questions/32794/…
steadfish
21
O que você quer dizer com "lança alguns dados"? Possui um braço de robô e uma câmera acoplados?
starblue
3
Embora eu concorde com a essência geral do seu tom, que muitas vezes nos preocupamos demais com isso, mas ele foi explorado na vida real: en.wikipedia.org/wiki/Ronald_Dale_Harris
Grady Player
3
Veja este artigo sobre um jogo de pôquer on-line sem a verdadeira aleatoriedade, por que é importante.
Varaquilex
1
Se você mantiver um contador de 0-5 e rolar os dados adequadamente, 666 gorilhões de vezes, obterá uma distribuição igual.
jcora

Respostas:

1383

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 226 . 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 32 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 32 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 32 -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 32 comportamentos possíveis, ele não pode gerar todos os baralhos possíveis. Só pode gerar 2 32 dos 2 226 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 256 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 32 mapeamentos de sementes para PRNG(52). Mas 2 256 é 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 256 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 256 . 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 256 sequências possíveis produzidas pelo CPRNG, mas existem apenas 2 226 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 226 é 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 256 , 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:

Eric Lippert
fonte
20
Ok, meninos e meninas. Isso é o suficiente para comentar por enquanto. Se você quiser discutir mais sobre isso, vá até uma sala de bate-papo, kthnxbye!
Ivo Flipse
1
@ Eric Mas a semente não é redefinida antes de cada novo sorteio de deck, é? Portanto, enquanto você está certo de que há apenas relativamente poucas trajetórias das quais estamos amostrando, você não sabe exatamente de onde na trajetória está no momento e as trajetórias se cruzam.
AS
Um bom (mas denso) tratamento de questões relacionadas está no Knoc TAOCP vol 2, seção 3.5 “O que é uma sequência aleatória?” (P. 149), começando com definições esclarecedoras de sequências equidistribuídas, distribuídas em k e ∞. Sequências pseudo-aleatórias são discutidas em 3.5.F (p. 170). Veja também os critérios de pseudo-aleatoriedade da teoria da complexidade e do BSI alemão .
ShreevatsaR
160

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:

Windows NT

ou 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 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.

Bruce Barnett
fonte
30
Isso é tão brilhante que traz lágrimas aos meus olhos. Deve haver um aplicativo que os crie para todos os sistemas operacionais (móveis / desktop / servidor) e plataformas (JVM / Javascript / etc).
HDave
5
A função rand () do Windows é muito boa! Produz uma nuvem que não possui padrões aparentes. Veja minha implementação para experimentá-lo (e outros algoritmos): github.com/Zalastax/visualize_random
Zalastax 17/02/02
93

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 .

bwDraco
fonte
9
Existem PRNGs criptográficos e são amplamente utilizados. Eles podem, a partir de uma semente de tamanho modesto, gerar um fluxo praticamente ilimitado de números aleatórios. É computacionalmente inviável distinguir esse fluxo de números aleatórios verdadeiros, portanto, nenhuma informação adicional pode ser obtida de qualquer parte desse fluxo e, para qualquer finalidade prática, os números são tão bons quanto os números aleatórios verdadeiros.
Aaaaaaaaaaaa
Eu acho que a maneira mais fácil de explicar isso é que algoritmos de gerador de números aleatoriamente 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 poderá ser aleatório.
Keltari
6
@Keltari Está faltando o elemento entropia ... A maioria dos RNGs (pelo menos criptográficos) coleta informações de fontes externas (por exemplo, movimento do mouse) e as usa como parte da condição inicial - assim, a transformação de Apara Bé programada, mas o estado inicial de A(deveria) não pode ser adivinhado. O Linux /dev/randommanterá uma aproximação da quantidade de entropia disponível e deixará de fornecer números se cair muito baixo.
Básico
Por curiosidade - por que as lâmpadas de lava são consideradas "verdadeiramente aleatórias"? Entendo que ele exibe um comportamento bastante imprevisível, mas alguém com uma compreensão suficientemente firme da dinâmica dos 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, elas não são aleatórias, mas altamente previsíveis.
theGreenCabbage
1
@theGreenCabbage: Eu suspeito que as lâmpadas de lava sejam caóticas. Dado um modelo de computador suficientemente bom e dígitos de precisão suficientes, você pode (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 rapidamente divergem de comportamento. (E este comentário ignora atratores caóticos.)
DMM
76

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                |
Tony D
fonte
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
50

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.

Chris Taylor
fonte
2
"Geradores de números pseudo-aleatórios ... geram números previsíveis com a distribuição correta" - Só porque o PRNG não garante que ele tenha uma distribuição perfeita (de fato, os comerciais em geral não, exatamente pelo razões descritas nestas respostas). Embora possam ser previsíveis com informações suficientes (o algo usado, a semente inicial, os valores de saída, p / e), eles ainda têm variação.
Brian S
3
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
2
@BrianS Na verdade, um PRNG que falhou nos testes de distribuição ao longo do tempo seria previsível por definição. Assim, ao longo de um N grande, se você se afastar um pouco dos N / 2 heads em N coin flips, poderá começar a apostar nas heads e poderá ganhar mais do que perde. Da mesma forma, se você obtivesse uma distribuição perfeita de cara x coroa, mas as cabeças sempre viessem em pares, teria novamente uma receita para vencer. Testes de distribuição são como você sabe que um PRNG é bom.
Jon Kiparsky
1
Você esqueceu nonlocal next:-).
7274 Kos
5
Exemplo ainda melhor: acredita-se que Pi seja normal , o que significa que qualquer sequência de dígitos de qualquer comprimento dado em qualquer base não aparece mais frequentemente do que qualquer outra sequência desse comprimento naquela base. Um algoritmo que, quando solicitado por n bits aleatórios, pega os próximos n bits de pi e os retorna (a "semente" é o bit em que você inicia)) deve, a longo prazo, produzir uma distribuição perfeitamente uniforme. Mas você ainda não o desejaria para o seu gerador - alguém que conhece o último monte de bits que você gerou pode encontrar a primeira vez que essa sequência ocorre, assumir que sua semente está lá e provavelmente estar correta.
cpast
26

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 .

Alex McKenzie
fonte
12
O grande problema é quando você precisa de números aleatórios que um invasor não pode prever por motivos de segurança.
David Schwartz
16
Você certamente encontrará um tempo em que precisa de um número verdadeiramente aleatório. É o suficiente para abrir uma página web que começa com https://...
Jan Hudec
3
@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 a randomização do layout do espaço de endereço . É por isso que coisas assim acontecem.
Reid
5
@JanHudec Eu estava falando especificamente no sentido de que você precisaria usar um gerador de números aleatórios on-line. Números aleatórios verdadeiros são usados ​​com frequência, mas poucas pessoas realmente precisam gerá-los.
Alex McKenzie
2
As máquinas caça-níqueis também usam um PRNG, não um TRNG. O gerador funciona o tempo todo e um número é escolhido no momento exato em que o botão de rotação é pressionado. A soma do PRNG e o tempo de pressão do botão verdadeiramente aleatório equivale a um TRNG.
Roger Dahl
26

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.

Prabhu
fonte
3
Eu culparia o material WEP por um protocolo mal projetado usando uma cifra fraca. Com cifras de fluxo modernas, você pode usar um contador como IV.
CodesInChaos
2
O principal problema com o WEP foi repetir a chave em 2 ^ 24 (quase 16 milhões) quadros. Foi ainda pior com as chaves relacionadas, que tornaram possível decifrar o código em cerca de 40000 quadros. O ponto principal aqui é que a chave não é aleatória. Está intimamente relacionado, e é fácil de quebrar.
Prabhu
1
A pseudo-aleatoriedade é ruim na criptografia apenas 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 semeado com a expansão de 128 bits da chave XORed no texto simples da mensagem.
11114 Matt
12

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

Fatal705
fonte
Previsibilidade! = Repetindo. Mersenne Twister é um bom exemplo disso. Na maioria das implementações após o 624 Int32, é possível prever todo o próximo número, mas a sequência do Mersenne Twister é muito maior que essa (2 ^ 19937 - 1).
HoLyVieR
Não entendo por que essa resposta não é empurrada para cima da pilha, pois me parece que essa é a resposta precisa e concisa à pergunta, pelo menos parcialmente. Os números pseudo-aleatórios podem ser facilmente previstos após alguns sorteios, o número de sorteios variando com a "qualidade" do algoritmo pseudo-aleatório. A seleção de um algoritmo "bom" está considerando os aspectos: 1. todo valor é desenhado em igual frequência (distribuição); 2. leva um "longo tempo" para reiniciar a sequência no início e começar a desenhar novamente os mesmos números no mesma ordem.
minutos a
msgstr "números aleatórios verdadeiros não são [previsíveis]". 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 Estou escrevendo este comentário muito exato. Direito?
minutos a
Hipoteticamente, porém, considerando o vasto grau de entropia envolvido nas ações reais de corpos reais, o poder de computação necessário seria ridiculamente enorme. Pense nos continentes cobertos por computadores. Além disso, devido à dependência do estado anterior, o estado de todo corpo no universo, em todo momento, precisaria ser armazenado, o que, por definição, exigiria mais espaço do que o disponível no universo, completamente preenchido com aparatos de memória
TheEnvironmentalist
@TheEnvironmentalist - Ah! "Continentes cobertos de computadores" ... não é disso que se trata o "Guia do Mochileiro das Galáxias"? ;-)
ysap 15/02
10

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.

DoubleFission
fonte
10

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.

gnasher729
fonte
8

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

Erwan Legrand
fonte
2
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 depende de números aleatórios e, por qualquer motivo, fosse crítico que os números fossem o mais aleatórios possível, eu certamente tiraria vantagem de um RNG de hardware para ter certeza de que quaisquer propriedades observadas não são devidas às peculiaridades do RNG.
Kef Schecter
3
@KefSchecter Seus PRNGs de hardware ouvidos geralmente têm saída tendenciosa e / ou correlacionada. Eles precisam de uma etapa de pós-processamento para transformá-la 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 do fluxo. Como um bônus extra, é reproduzível, o que é valioso na ciência.
CodesInChaos
OK, é justo. Mas o mesmo não se aplicaria igualmente a aplicativos de criptografia? Até a resposta que Gievn diz aqui precisa de um RNG de hardware para propagar o CSPRNG.
Kef Schecter
2
@KefSchecter Sim, aplicativos de criptografia precisam de números aleatórios verdadeiros para propagar o CSPRNG. Mas, para todo o resto, podemos usar esse CSPRNG.
CodesInChaos
@ KefSchecter: aplicativos criptográficos exigem que o fluxo não seja reproduzível pelo mundo em geral. Por outro lado, em aplicações científicas, ser útil para mostrar que os números "aleatórios" que se está usando não foram simplesmente escolhidos para mostrar sua análise de maneira adequada. Por exemplo, se alguém anuncia, depois de anunciar seus métodos, que irá gerar dados de uma certa maneira, usando os números da loteria estadual do dia seguinte, os leitores podem estar um pouco confiantes de que não falsificaram os resultados, mesmo que o sorteio da semana tenha apenas algumas dezenas bits de entropia.
supercat
7

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 160 fluxos possíveis de números aleatórios que podem vir dele. Simples assim. Você não pode obter mais de 2 160 valores do estado interno. Portanto, você não pode obter mais de 2 160 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 320 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 226 . Portanto, independentemente da propagação, você não pode usar Java.util.SecureRandom para embaralhar um baralho de cartas. Existem aproximadamente 2 66 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.

Paco Hope
fonte
2
Por que você se importa que alguns shuffles não possam acontecer? Essa restrição não tem efeito observável.
CodesInChaos
2
Estou meio chocado com a pergunta. Para empresas de jogos altamente regulamentadas, esse viés provaria matematicamente que suas chances de ganhar o jogo de cartas são diferentes no computador do que em um baralho de cartas. Não importa se as chances são melhores ou piores. Eles são DIFERENTES. O computador não é moralmente equivalente a um baralho real. Além disso, não podemos caracterizar a diferença. A empresa de jogos que enfrenta fortes multas regulatórias se importaria muito.
Paco Hope
1
Mas é detectável. Detecto-o usando um processo conhecido: revisão do código-fonte e conhecimento do domínio do problema. É isso que é notável. NÃO posso usar análise estatística automatizada. É tão detectável quanto alguém usando java.util.Random ou o Mersenne Twister. A análise estatística não é o único mecanismo de detecção válido para incompatibilidade no domínio RNG / problema. Falhas que passam nesse detector não são, por definição, sucessos.
Paco Hope
1
Eu nunca discordei dessa afirmação. O que eu disse é que a análise estatística não é prova infalível de que o RNG / PRNG está correto. Este é um exemplo de um falso negativo. Deve estar incorreto, mas o teste de saída estatística será aprovado. Se eu usar SHA1 (1), SHA1 (2), SHA1 (3) ... SHA1 (n) como meu "RNG" que também passará em testes estatísticos. Também está errado. A definição de correto se estende além da definição de "passa nos testes estatísticos". Passar nos testes estatísticos é necessário, mas não suficiente.
Paco Hope
4
@CodesInChaos: O argumento "não conhecemos um ataque que possa tirar proveito do fato de que a grande maioria dos possíveis embaralhamento de IRL nunca será produzida" não implica que esse ataque seja impossível, apenas que não não sabe o que é ou como se defender. A atitude correta nesse caso é eliminar a possibilidade de ataque, eliminando a condição: faça um RNG de qualidade suficiente para que ele possa gerar todos os baralhos possíveis.
Eric Lippert
6

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.

BonzaiThePenguin
fonte
6

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.

radouxju
fonte
2

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.

sanaris
fonte
1

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.

Superbest
fonte
0

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) ...

Dice9
fonte
-5

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.

magallanes
fonte
2
Essa é uma péssima idéia e é uma fonte de vulnerabilidade para coisas que precisam de uma sequência realmente imprevisível. Se você tomar microssegundos, terá apenas 10 ^ 6 possibilidades de sementes, o que é bastante baixo.
HoLyVieR
@HoLyVieR: certamente é uma má idéia se você se preocupa com segurança, mas não tão ruim quanto você pensa: você usaria microssegundos desde o início do sistema (ou época do unix ....) o que aumenta significativamente a faixa de valores possíveis.
Mikera
1
@mikera Não é melhor, o tempo em que a solicitação foi processada é previsível. É um vetor de vulnerabilidade para um bom número de funcionalidades de redefinição de senha. Esses scripts geraram um token "aleatório" com sua técnica e o invasor pôde encontrar o token gerado, já que encontrar o horário em que foi executado é bastante trivial ... é o mesmo horário em que a solicitação de redefinição de senha foi enviada + - 150ms.
21814 HoLyVieR
Claro, essa situação é muito ruim. Mas a situação em que o estado foi propagado na inicialização do sistema e o invasor não tem uma boa maneira de adivinhar o tempo de inicialização não é tão ruim assim. Você pode facilmente escolher 10 ^ 12 microssegundos possíveis, o que pode inviabilizar alguns tipos de ataque. Para ser claro: todas essas soluções são muito ruins do ponto de vista de criptografia, mas as constantes são importantes .
Mikera
Para servidores on-line, as informações de disponibilidade do sistema às vezes são oferecidas publicamente. Ou você pode obtê-lo em uma página de status "Incidentes. Servidor novamente.". Ou você pode executar ping, esperar um grande tempo de inatividade e observar que pode ser uma reinicialização da máquina (o que daria algumas centenas de milhões de tempo para verificar, o que é bastante baixo).
Dereckson