Qual é a semente menor e mais simples para um gerador de números aleatórios?

40

Um pequeno microcontrolador (Atmel de 8 bits) controla várias luzes para apresentar um show de luzes com muitas sequências de luzes aleatórias sofisticadas.

Um pseudo-RNG adequado faz seu trabalho bem, mas estou procurando uma boa semente para ele. Uma semente será necessária porque se alguém ligar vários dispositivos ao mesmo tempo, não parecerá bom se todos gerarem as mesmas seqüências de efeitos até que se afastem lentamente devido às pequenas diferenças em suas fontes de relógio individuais.

Um método muito bom para propagar um pseudo-RNG, que eu costumava usar, é possível no caso de um dispositivo que deve ser iniciado pressionando um botão ou pressionando um botão. Assim que o µc for ligado, um timer muito rápido poderá ser iniciado, e o valor desse timer semeará o RNG assim que o botão for pressionado pela primeira vez.

O problema é que, nesse cenário, não há botões. O programa deve iniciar assim que o dispositivo for ligado.

O local no PCB é extremamente limitado (nada mais do que algumas das menores peças SMD podem caber), então estou procurando a solução menor e mais simples possível. Portanto, descartarei soluções sofisticadas, como o verdadeiro hardware RNG, receptores de rádio etc.

Tudo o que tenho é um contador de timer de 16 bits na CPU e um alfinete de porta não utilizado que tenha acesso a um ADC.

Minha solução atual é usar apenas um resistor (o mais impreciso possível) para fornecer aproximadamente metade da tensão de alimentação ao pino do ADC e propagar o RNG com o primeiro valor de conversão do AD. No entanto, hoje em dia a maioria dos resistores de 10% tem uma imprecisão bem abaixo de 1% (seria divertido imaginar o rosto de um fornecedor quando eu lhes digo que queremos os resistores SMD da pior qualidade que eles encontrarem), então há uma chance muito alta de várias unidades começando com a mesma semente.

Uma alternativa melhor seria fazer várias conversões e criar um valor a partir dos bits menos significativos dessas medidas. No entanto, eu usei o ADC desse tipo µc antes e sei que é muito preciso. A execução do ADC na velocidade mais rápida possível pode ajudar aqui.

Alguém tem uma sugestão melhor? Não é necessário que a semente seja perfeitamente distribuída uniformemente, mas quanto mais uniforme for a distribuição, melhor. Uma semente de 16 bits com uma distribuição perfeitamente uniforme seria um sonho bom demais para ser verdade, mas acho que uma distribuição decente na metade de 5 ou 6 bits pode ser suficiente.

vsz
fonte
12
"seria divertido imaginar o rosto de um fornecedor quando digo que queremos os resistores SMD da pior qualidade que eles puderem encontrar" - seria ainda mais engraçado deixar o valor desse resistor indefinido no diagrama de circuito e dizer ao pessoas em produção que esta peça deve ser soldada manualmente após o PCB sair da máquina de colocação, de uma lixeira onde misturamos todos os valores de resistores que temos. - Porque não é um RNG que estou procurando, mas uma semente . Portanto, se ele gera o mesmo valor quase sempre que não é tão ruim, é mais importante ser diferente entre os dispositivos.
vsz
8
Por que não gravar um valor aleatório no armazenamento EEPROM durante a programação de produção? Dessa forma, você pode usar o RNG mais sofisticado que desejar, pois ele estará apenas no (s) programador (es) de produção e não nos dispositivos finais. (Crédito para @immibis: o seu 'software arquivo ligeiramente diferente' me deu a idéia.)
Calrion
2
Portanto, apenas para ser 100% claro, o problema é que eles podem começar na mesma sequência, não que eles se afastem com o tempo, correto?
wedstrom 3/09/15
2
A escolha do seu RNG é importante: algumas precisam de sementes de boa qualidade, outras não. Por exemplo, para o Xorshift, qualquer semente que não seja 0 funcionará e funcionará igualmente bem. Mesmo uma pequena diferença na semente inicial resultará em uma posição inicial muito diferente no ciclo do RNG.
precisa saber é o seguinte
3
Você pode combinar todas as respostas da ADC com estatísticas e tempo para obter ainda mais aleatoriedade. Por exemplo, meça quantos ticks de processador são necessários até você tirar N amostras onde os 3 LSBs inferiores são 101 e M amostras onde os 3 LSBs inferiores são 110. Expanda esse conceito conforme desejado.
wjl 5/09/15

Respostas:

24

Coloque um resistor e um capacitor paralelos entre o pino A / D e o terra. Torne o resistor razoavelmente alto, de preferência bem acima do requisito de impedância do sinal de entrada para o A / D. Faça o tempo de RC constante, talvez em torno de 10 µs. Por exemplo, 100 kΩ e 100 pF parecem uma boa combinação.

Para obter um valor com alguma aleatoriedade, mova o pino alto por um tempo, depois ajuste-o para alta impedância e faça uma leitura A / D alguns µs depois. Particularmente, se você abusar adequadamente do tempo de aquisição do A / D, a tensão que ele verá dependerá dos valores de R e C, da corrente de fuga do pino, de outros ruídos próximos e da temperatura.

Pegue o bit baixo ou o baixo dois bits e repita conforme necessário para obter qualquer número de bits aleatórios.

Para um padrão mais aleatório, execute este procedimento ocasionalmente e injete o bit baixo do resultado A / D no gerador de números aleatórios que você já está usando.

Olin Lathrop
fonte
Isso parece bom. Verifique a impedância de entrada no ADC - a série Atmega8 possui uma impedância de entrada analógica de 100Meg, o que torna o valor do resistor de Olin um pouco baixo.
stefandz 02/09
3
@stef: A impedância de entrada e a impedância de sinal necessária para a conversão correta são duas coisas diferentes. Sim, a impedância de entrada é muito alta devido ao fato de ser CMOS. No entanto, existe um limite máximo de impedância no sinal para permitir que ele carregue a amostra e mantenha a tampa dentro do tempo especificado e para superar qualquer vazamento que o pino possa ter.
Olin Lathrop
2
desculpe, pela sua resposta, pensei que você estava referenciando a impedância de entrada em oposição à especificação de impedância da fonte. 10k é a impedância de fonte máxima especificada do Atmega8, portanto, sua resposta é imediata. Para referência, a tampa S / H interna é de 14pF, caso alguém esteja interessado.
stefandz
2
@stef: editei a resposta para deixar isso mais claro.
Olin Lathrop
Você perdeu a fase Lunar e os feriados. Também acene com a mão uma adição útil, especialmente se estiver baixa C e não estiver bem protegida.
Russell McMahon
23

Algumas opções possíveis:

  1. Pré-programe um endereço serial exclusivo para cada dispositivo. Se você tiver um algoritmo RNG bom o suficiente, mesmo uma lista seqüencial de endereços seriais produzirá resultados totalmente diferentes.

  2. Dependendo do seu MCU / configuração, você pode ter duas fontes de relógio diferentes disponíveis para o relógio do sistema e a entrada do watchdog timer / timer. Se um / ambos tiverem variação significativa, você poderá usá-lo para gerar uma semente adequadamente diferente. Aqui está um exemplo que escrevi que usa um timer interno de vigilância do Arduino e um relógio externo do sistema XTAL .

  3. Use um transistor BJT e construa um amplificador altamente dependente de beta. Isso pode ser lido de um ADC para a semente.

  4. Capacitores / indutores são normalmente especificados para uma tolerância muito pior do que os resistores. Você pode construir algum tipo de circuito de filtro (RC, RL, LC) com estes e medir a saída com o ADC.

helloworld922
fonte
5
Eu voto na opção 1, é uma solução de contagem de zero partes que resultará em que as seqüências nunca terão que corresponder. O número de série e o gerador RND podem dizer 16 bits, fazendo com que qualquer dispositivo tenha uma chance insignificante de imitar o padrão de outro.
KalleMP 02/09
1
Eu também gosto da solução. Se você usar um algoritmo de hash simples, deverá ficar bem, mesmo se tiver números de série sequenciais.
magu_ 02/09/2015
6
A coisa agradável sobre a opção 1 é que alguns dispositivos vêm com built-in números de série (geralmente de rede / relacionado RF micros) para que você não precisa mesmo de uma etapa separada para queimar os números de série
slebetman
3
Mesmo um RNG de lixo como um LCG irá "produzir muito diferentes resultados para uma lista seqüencial de endereços de série" . Também votei em 1.
BlueRaja - Danny Pflughoeft
3
Se você tiver uma fonte de tempo, usá-la como base para alternar a semente ajudaria a compensar as coisas entre as execuções. Combine isso com um endereço / número de série ou o endereço MAC, se o seu dispositivo tiver um e você também corrigirá a correspondência entre dispositivos. Eu já vi algum software que armazena persistentemente alguns ou todos os números aleatórios gerados para uso como semente, mesmo após uma reinicialização. Se seus dispositivos tiverem tempos de operação diferentes, eles deverão se afastar.
TafT
8

Memória não inicializada

Você pode tentar usar a memória não inicializada no micro controlador. O truque é encontrar os bits que têm os chinelos mais "equilibrados" e são realmente aleatórios. O procedimento é ler toda a memória, redefinir e repetir algumas vezes para medir quais bits são verdadeiramente aleatórios. Então você usa este mapa para ler bits aleatórios suficientes para propagar seu PRNG ou LFSR!

Este método deve dar-lhe sementes aleatórias, mesmo com hardware idêntico, mais detalhes (e links) estão disponíveis em este hack-a-dia artigo

Eu gosto desse método porque ele não requer nenhum circuito ou pinos adicionais; seu AVR já possui ram, você só precisa encontrar os bits instáveis ​​(aleatórios). Além disso, o procedimento de mapeamento pode ser automatizado; você pode aplicar o mesmo código e procedimento a cada dispositivo e obter resultados verdadeiramente aleatórios!

esoterik
fonte
1
Você realmente não precisa descobrir quais bits são aleatórios. Todos os bytes com XOR fornecerão um resultado aleatório, mesmo que apenas 8 bits sejam aleatórios. E, como mostra a figura, os valores reais podem não ser aleatórios no sentido temporal, eles são únicos o suficiente - o que é exatamente o que precisamos aqui.
MSalters
1
Se você puder encontrar um PRNG que permita "misturar" a entropia, isso poderá ser ainda melhor do que a opção XOR-then-seed. Itere através da memória não inicializada e misture os bytes no PRNG. Por exemplo, veja minha biblioteca C simples - função de mixagem .
Craig McQueen
Isso não fornecerá aleatoriedade de qualidade de criptografia.
@CamilStaps, é claro que não.
Navin
1
Isso não vai funcionar. A memória não inicializada é um comportamento indefinido se eu tiver um sistema operacional e não tiver controle sobre qual parte da memória será atribuída ao meu programa e o que havia antes. Em um microcontrolador sem sistema operacional, esse não é o caso. Especialmente com o AVR, porque toda a RAM será zero se houver tempo suficiente para que os capacitores sejam esvaziados pelo consumo atual de queda de energia.
vsz 5/09/15
7

O que eu fiz para um MP3 player com capacidade aleatória é usar apenas uma semente sequencial diferente a cada ligação. Comecei em 1 e guardei isso na EEPROM, de modo que, no próximo ciclo de energia, usei 2 etc. Isso ocorreu em um ATMEGA168. Como helloworld922 observou, mesmo uma simples semente seqüencial irá gerar sequências pseudo-aleatórias completamente diferentes.

Eu usei um dos geradores de sequência aleatória linear congruente, isso fornece uma distribuição uniforme.

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

Obviamente, se você deseja que várias unidades tenham sequências diferentes, mesmo que elas tenham o mesmo número de ciclos de energia, você precisa de algo para iniciar aleatoriamente.

Isso pode ser feito por qualquer um dos métodos propostos pelos outros pôsteres - Um método em que posso pensar poderia usar o cruzamento de zero CA que entra no processador, se você o tiver (para controle de fase da lâmpada, por exemplo)? Isso pode ser usado para amostrar o cronômetro no primeiro cruzamento após a inicialização e, em seguida, usado como semente.

Existem botões na unidade para selecionar o modo etc? Nesse caso, você pode testar o contador na primeira vez em que o botão é pressionado após a programação da MCU, você pode gerar uma semente aleatória inicialmente e armazená-la na EEPROM. Toda energização após esse ponto usaria a semente armazenada.

Kevin White
fonte
5

Um ADC é uma fonte muito boa de aleatoriedade.

Você não precisa confiar nas tolerâncias do resistor. Qualquer resistor irá gerar ruído térmico e o mesmo efeito físico introduzirá ruído no ADC ao executar todas as etapas de amostragem e conversão. (A folha de dados informará sobre a quantidade de ruído e quais configurações são as piores / as melhores.)

Você não deve deixar o pino ADC flutuando; isso pode deixar a tensão flutuar muito longe e corre o risco de saturar a entrada.
(Muitos MCUs permitem que você use algo como metade da tensão de alimentação como uma entrada ADC, para calibração. Isso economiza o resistor externo e ainda gera ruído. Novamente, consulte a folha de dados para a pior / melhor configuração.)

Você não precisa confiar em uma única medição ADC; você pode combinar várias medidas com uma função simples de hash ou soma de verificação (o CRC seria suficiente). Se você precisar começar a usar o RNG imediatamente, poderá combinar posteriormente o resultado do ADC com a semente atual do RNG.

CL.
fonte
2
Não tenho certeza se o ruído Johnson é adequado para esta aplicação; No STP, um resistor de 10Meg com uma largura 40uVde banda de 10kHz possui ruído Johnson. Você precisaria de um ADC> 14 bits ou um circuito amplificador para medir isso razoavelmente.
precisa saber é o seguinte
STP não é realmente relevante. A temperatura pode ser intencionalmente aumentada, mas um aumento de 60 graus sobre STP é apenas 10% de ruído extra.
MSalters
1
Uma abordagem semelhante seria usar o ruído do tiro em um diodo. pt.wikipedia.org/wiki/Noise_generator#Shot_noise_generators
teambob
2

Você pode salvar a semente de uma sessão para outra? Em caso afirmativo, é possível ativar todas as unidades por algum período aleatório após a criação? Dessa forma, todas as unidades serão enviadas com sementes predefinidas que provavelmente não serão as mesmas.

Outro pensamento: como você vincula várias unidades para que elas sejam ativadas simultaneamente? Se estiverem em série, adicione algum tipo de capacitor para que o (n + 1 )ésimo dispositivo inicie alguns ciclos de relógio após o enésimo dispositivo. Idealmente, os capacitores descarregariam muito rapidamente no desligamento do dispositivo; portanto, a cada inicialização / reinicialização, há um intervalo maior entre as seqüências.

Se eles estiverem em paralelo, você ainda poderá aleatoriamente um pouco o tempo de inicialização. Presumo que exista algum tipo de filtragem de energia usando capacitores. Nesse caso, fabricar os dispositivos com circuitos de filtragem ligeiramente diferentes faria com que cada dispositivo iniciasse em um momento ligeiramente diferente, causando divergência após várias reinicializações.

Uma variação disso é adicionar variação aos sinais do relógio, se possível. Uma diferença de 0,1% na velocidade do relógio pode ter pouco impacto no show de luzes, enquanto altera a taxa em que você percorre a tabela PRNG rapidamente.

MichaelS
fonte
1
talvez conecte um grande vazamento ao pino analógico e faça algumas leituras de "canos principais" para semear o RNG.
Jasen
1
@ Jasen, todas as unidades conectadas ao mesmo cabo de extensão verão o mesmo zumbido da rede elétrica.
Ian Ringrose
2

Se você estiver executando na fonte de relógio "calibrada" interna. Você não pode salvar uma semente depois de algum tempo, preferencialmente na EEPROM. O relógio mudará e será diferente de unidade para unidade. Para salvar um novo valor após algum tempo novamente (talvez a cada 10 minutos ou mais, ou após um tempo curto o suficiente para ocorrer dentro do prazo normal do dispositivo. Quanto mais tempo o dispositivo estiver ligado, maior será a probabilidade de salvar um valor "diferente" na EEPROM.

Dê um salto de vez em quando (de vez em quando) e faça nova propagação enquanto o dispositivo estiver ligado (salve esse novo valor na EEPROM).

Mats
fonte
2

Que tal estender sua idéia original de conversão do AD com base em um resistor variável, adicionando um LDR ou termistor? (O primeiro precisaria "olhar" para fora, não sei se isso é viável; mas a variação da luz pode ser maior que a variação da temperatura entre os dispositivos iniciados aproximadamente na mesma hora e no mesmo local. ..)

Hagen von Eitzen
fonte
1
Os termistores vêm com outra propriedade útil. Várias séries da maioria dos fabricantes apresentam uma tremenda variação e imprecisão. Isso irá "melhorar" ainda mais o resultado.
Ariser
1

2 soluções em potencial, ambas assumindo que você precisa de uma semente única por unidade.

  1. Se você piscar suas unidades uma por uma na fábrica, o arquivo hexadecimal poderá ser modificado programaticamente por algum script intermediário no programador. Se for controlado por PC, você pode substituir uma inicialização variável pela data e hora. Garantido para ser único para cada unidade!

  2. Os dispositivos Dallas 1 wire usam apenas um pino e cada um vem com um número de série exclusivo de 64 bits. Você pode usar isso como a semente.

Loganf
fonte
1
Eu gosto de 2, mas infelizmente todas as peças do DS são bastante caras.
Ariser 03/09/2015
Não use o timestamp de produção para aleatoriedade de qualidade criptográfica, é previsível.
2
@CamilStaps para a aplicação do OP, cripto-qualidade não é necessária
Hagen von Eitzen
1
@HagenvonEitzen verdade, mas outros podem chegar a essa pergunta procurando aleatoriedade de criptografia-Q, por isso vale a pena mencionar.
4
@CamilStaps Suspiro , parece que você desistiu da humanidade :) É realmente muito exigente esperar de alguém que queira usar uma resposta do electronicsSE para fins criptográficos que eles sejam pelo menos cuidadosos o suficiente para ler a pergunta que devem responder? ? "16bit" ou sementes "5 o5 6 bits" não são cripto-Q mesmo gerado por um bando de Schrödinger gatos :)
Hagen von Eitzen
1

Você pode deixar um pino ADC flutuante para alimentar o gerador de números aleatórios (RNG) com ruído capturado. Deve ser o suficiente para gerar uma semente ou até usá-la como o gerador RNG.

Não se esqueça de usar o tempo mínimo de conversão possível.

A outra solução poderia ser um gerador de ruído aplicado ao pino ADC.

jnk0le
fonte
2
Vou fazer algumas medições, mas se bem me lembro, um alfinete flutuante do ADC lê 0ou aproxima 0. Vou verificar novamente para ver se é esse o caso.
vsz
1
Estou interessado, ele lê 0quando está flutuando?
Bence Kaulics
2
O problema é que isso pode funcionar em uma placa de desenvolvimento e falhar no produto final.
vsz 5/09/15