Gerador de números aleatórios verdadeiros [fechado]

Question

Desculpe por esta não ser uma pergunta "real", mas algum tempo atrás, lembro-me de ter visto um post aqui sobre randomizar um randomizador aleatoriamente para gerar números verdadeiramente aleatórios, não apenas pseudo-aleatórios.Eu não vejo se eu procurar por isso.

Alguém sabe sobre esse artigo?

Answer 1

Eu acredito que isso estava ligado thedailywtf. com - ou seja.não é algo que você queira fazer.

Não é possível obter um número verdadeiramente aleatório a partir de números pseudoaleatórios, não importa quantas vezes você chame randomize().

Você pode obter números aleatórios "verdadeiros" de especial hardware.Você também pode coletar entropia dos movimentos do mouse e coisas assim.

Answer 2

Tenho que discordar de muitas das respostas a esta pergunta.

É possível coletar dados aleatórios em um computador.SSL, SSH e VPNs não seriam seguros se você não pudesse.

A maneira como o software gerador de números aleatórios funciona é que existe um piscina de dados aleatórios coletados de muitos lugares diferentes, como desvio de relógio, intervalos de interrupção, etc.

O truque para esses esquemas é estimar corretamente o entropia (o nome elegante para a aleatoriedade).Não importa se a fonte é tendenciosa, desde que você estime a entropia corretamente.

Para ilustrar isso, a chance de eu acertar a carta e neste comentário é muito maior do que o de z , então se eu usasse interrupções de chave como fonte de entropia, seria um viés - mas ainda há alguma aleatoriedade nessa entrada.Você não pode prever exatamente qual sequência de letras virá a seguir neste parágrafo.Você pode extrair entropia dessa incerteza e usá-la como parte de um byte aleatório.

Geradores aleatórios reais de boa qualidade, como Yarrow tem uma estimativa de entropia bastante sofisticada incorporada e só emitirá tantos bytes quanto puder dizer com segurança que possui em seu "conjunto de aleatoriedade".

Answer 3

No final da postagem, responderei à sua pergunta sobre por que você pode querer usar vários geradores de números aleatórios para "mais aleatoriedade".

Existem debates filosóficos sobre o que significa aleatoriedade.Aqui, quero dizer "indistinguível em todos os aspectos de uma distribuição iid uniforme (0,1) sobre as amostras extraídas". Estou ignorando totalmente as questões filosóficas sobre o que é aleatório.

O volume 2 de Knuth tem uma análise em que ele tenta criar um gerador de números aleatórios, como você sugere, e depois analisa por que ele falha e quais são os verdadeiros processos aleatórios.O Volume 2 examina os RNGs em detalhes.

Os outros recomendam o uso de processos físicos aleatórios para gerar números aleatórios.Porém, como podemos ver na interação Espo/vt, esses processos podem ter elementos periódicos sutis e outros elementos não aleatórios, em parte devido a fatores externos com comportamento determinístico.Em geral, é melhor nunca presumir a aleatoriedade, mas sempre testá-la, e geralmente você pode corrigir esses artefatos se estiver ciente deles.

É possível criar um fluxo “infinito” de bits que pareça completamente aleatório, de forma determinística.Infelizmente, tais abordagens crescem em memória com o número de bits solicitados (como seria necessário, para evitar a repetição de ciclos), portanto seu escopo é limitado.

Na prática, quase sempre é melhor usar um gerador de números pseudo-aleatórios com propriedades conhecidas.Os números principais a serem procurados são a dimensão do espaço de fase (que é aproximadamente compensada entre amostras que você ainda pode contar com distribuição uniforme) e a largura de bits (o número de bits em cada amostra que são uniformemente aleatórios entre si ) e o tamanho do ciclo (o número de amostras que você pode coletar antes que a distribuição comece a se repetir).

No entanto, como os números aleatórios de um determinado gerador estão deterministicamente em uma sequência conhecida, seu procedimento pode ser exposto por alguém pesquisando no gerador e encontrando uma sequência de alinhamento.Portanto, você provavelmente poderá evitar que sua distribuição seja imediatamente reconhecida como proveniente de um gerador de números aleatórios específico se mantiver dois geradores.A partir do primeiro, você amostra i e, em seguida, mapeia isso uniformemente de um para n, onde n é no máximo a dimensão da fase.Então, no segundo, você amostra i vezes e retorna o i-ésimo resultado.Isso reduzirá o tamanho do seu ciclo para (tamanho do ciclo original/n) no pior caso, mas para esse ciclo ainda gerará números aleatórios uniformes, e fará isso de uma forma que torne a busca pelo alinhamento exponencial em n.Também reduzirá o comprimento da fase independente.Não use este método a menos que você entenda o que o ciclo reduzido e os comprimentos de fase independentes significam para sua aplicação.

Answer 4

Um algoritmo para números verdadeiramente aleatórios não pode existir, pois o definição de números aleatórios é:

Tendo resultados imprevisíveis e, no caso ideal, todos os resultados igualmente prováveis;resultante dessa seleção;falta de correlação estatística.

Existem geradores de números pseudoaleatórios (PRNGs) melhores ou piores, ou seja,sequências de números completamente previsíveis que são difíceis de prever sem o conhecimento de uma informação, chamadas de semente.

Agora, PRNGs para os quais é extremamente difícil inferir a semente são criptograficamente seguro.Você pode querer procurá-los no Google, se é isso que você procura.

Outra maneira (se isso é verdadeiramente aleatório ou não, é uma questão filosófica) é usar fontes aleatórias de dados.Por exemplo, quantidades físicas imprevisíveis, como ruído ou medição de decaimento radioativo.

Estes ainda estão sujeitos a ataques porque podem ser medidos de forma independente, têm preconceitos e assim por diante.Então é realmente complicado.Isso é feito com hardware customizado, que geralmente é bastante caro.Eu não tenho ideia de quão bom /dev/random é, mas aposto que não é bom o suficiente para criptografia (a maioria dos programas de criptografia vem com seu próprio RNG e o Linux também procura um RNG de hardware na inicialização).

Answer 5

De acordo com a Wikipédia /dev/random, em sistemas operacionais do tipo Unix, é um arquivo especial que serve como um verdadeiro gerador de números aleatórios.

O driver /dev/random coleta ruído ambiental de várias fontes não determinísticas, incluindo, entre outras, temporizações entre teclados e temporizações entre interrupções que ocorrem no ambiente do sistema operacional.Os dados de ruído são amostrados e combinados com uma função de mixagem semelhante ao CRC em um ``pool de entropia'' em atualização contínua.Sequências de bits aleatórias são obtidas usando um hash MD5 do conteúdo deste pool.A função hash unidirecional destila os verdadeiros bits aleatórios dos dados do pool e oculta o estado do pool dos adversários.

A rotina /dev/random mantém uma estimativa da verdadeira aleatoriedade no pool e a diminui toda vez que strings aleatórias são solicitadas para uso.Quando a estimativa chega a zero, a rotina é bloqueada e aguarda a ocorrência de eventos não determinísticos para atualizar o pool.

O módulo do kernel /dev/random também fornece outra interface, /dev/urandom, que não espera a recarga do pool de entropia e retorna quantos bytes forem solicitados.Como resultado, /dev/urandom é consideravelmente mais rápido na geração em comparação com /dev/random, que é usado apenas quando se deseja aleatoriedade de alta qualidade.

Answer 6

John von Neumann disse certa vez algo no sentido de que "qualquer pessoa que tente gerar números aleatórios por meios algorítmicos está, obviamente, vivendo em pecado".

Nem mesmo /dev/random é aleatório, no sentido da palavra para um matemático ou físico.Nem mesmo a medição do decaimento de radioisótopos é aleatória.(A taxa de decaimento é.A medição não é.Os contadores Geiger têm um pequeno tempo de reinicialização após cada evento detectado, durante o qual não conseguem detectar novos eventos.Isso leva a preconceitos sutis.Existem maneiras de mitigar isso substancialmente, mas não de eliminá-lo completamente.)

Pare de procurar a verdadeira aleatoriedade.Um bom gerador de números pseudoaleatórios é realmente o que você procura.

Answer 7

Se você acredita em um universo determinístico, a verdadeira aleatoriedade não existe.:-) Por exemplo, alguém sugeriu que o decaimento radioativo é verdadeiramente aleatório, mas IMHO, só porque os cientistas ainda não descobriram o padrão, não significa que não exista um padrão a ser descoberto.Normalmente, quando você deseja números "aleatórios", o que você precisa são de números para criptografia que ninguém mais será capaz de adivinhar.

O mais próximo que você pode chegar do aleatório é medir algo natural que nenhum inimigo também seria capaz de medir.Normalmente você joga fora os bits mais significativos de sua medição, deixando os números com maior probabilidade de serem distribuídos uniformemente.Usuários radicais de números aleatórios obtêm hardware especial que mede eventos radioativos, mas você pode obter alguma aleatoriedade do ser humano usando o computador a partir de coisas como intervalos de pressionamento de teclas e movimentos do mouse, e se o computador não tiver usuários diretos, a partir de sensores de temperatura da CPU, e do tráfego de rede.Você também pode usar coisas como webcams e microfones conectados a placas de som, mas não sei se alguém faz isso.

Answer 8

Para resumir parte do que foi dito, nossa definição funcional do que é uma fonte segura de aleatoriedade é semelhante à nossa definição de criptograficamente segura:parece aleatório se pessoas inteligentes olharem para ele e não forem capazes de mostrar que não é completamente imprevisível.

Há não sistema para gerar números aleatórios que não poderiam ser previstos, assim como não existe cifra criptográfica que não possa ser quebrada.As soluções confiáveis ​​utilizadas para trabalhos importantes são apenas aquelas que até agora provaram ser difíceis de derrotar.Se alguém lhe disser o contrário, está lhe vendendo algo.

A inteligência raramente é recompensada na criptografia.Vá com soluções testadas e comprovadas.

Answer 9

Um computador geralmente tem muitas fontes físicas de ruído aleatório prontamente disponíveis:

• Microfone (espero que em um lugar barulhento)
• Vídeo compactado de uma webcam (apontado para algo variável, como uma lâmpada de lava ou uma rua)
• Sincronização do teclado e do mouse
• Conteúdo e tempo dos pacotes de rede (o mundo inteiro contribui)

E às vezes

• Hardware baseado em desvio de relógio
• Contadores Geiger e outros detectores de eventos raros
• Todos os tipos de sensores conectados a conversores A/D

O que é difícil é estimar a entropia destas fontes, que na maioria dos casos é baixa apesar das altas taxas de dados e muito variável;mas a entropia pode ser estimada com pressupostos conservadores, ou pelo menos não desperdiçada, para alimentar sistemas como o Yarrow ou o Fortuna.

Answer 10

Não é possível obter números aleatórios 'verdadeiros', um computador é uma construção lógica que não pode criar nada 'verdadeiramente' aleatório, apenas pseudo-aleatório.No entanto, existem algoritmos pseudo-aleatórios melhores e piores por aí.

Para obter um número "verdadeiramente" aleatório, você precisa de uma fonte física aleatória, algumas máquinas de jogos de azar têm isso embutido - muitas vezes é uma fonte radioativa, o decaimento radioativo (que, pelo que eu sei, é verdadeiramente aleatório) é usado para gerar os números.

Answer 11

Um dos melhores métodos para gerar um número aleatório é através Desvio do Relógio.Isso funciona principalmente com dois osciladores.

Uma analogia de como isso funciona é imaginar um carro de corrida em um circuito oval simples com uma linha while no início da volta e também uma linha while em um dos pneus.Quando o carro completa uma volta, será gerado um número baseado na diferença entre a posição da linha branca na estrada e no pneu.

Muito fácil de gerar e impossível de prever.