Was ist der kleinste und einfachste Keim für einen Zufallsgenerator?

40

Ein kleiner Mikrocontroller (8-Bit-Atmel) steuert eine Reihe von Lichtern, um eine Lichtshow mit vielen ausgefallenen zufälligen Lichtsequenzen zu präsentieren.

Ein geeignetes Pseudo-RNG macht seine Arbeit gut, aber ich suche einen guten Samen dafür. Ein Startwert ist erforderlich, da es nicht gut aussieht, wenn jemand mehrere solcher Geräte gleichzeitig einschaltet, wenn alle dieselben Effektsequenzen erzeugen, bis sie aufgrund der winzigen Unterschiede in ihren einzelnen Taktquellen langsam auseinander driften.

Eine sehr gute Methode, um ein Pseudo-RNG zu setzen, das ich oft verwendet habe, ist bei einem Gerät möglich, das per Knopfdruck oder durch Drücken eines Schalters gestartet werden muss. Sobald der µc eingeschaltet ist, kann ein sehr schneller Timer gestartet werden, und der Wert dieses Timers setzt den RNG, sobald die Taste zum ersten Mal gedrückt wird.

Das Problem ist, dass in diesem Szenario keine Schaltflächen vorhanden sind. Das Programm muss gestartet werden, sobald das Gerät eingeschaltet wird.

Der Platz auf der Leiterplatte ist extrem begrenzt (es passen möglicherweise nicht mehr als ein paar der kleinsten SMD-Teile), daher suche ich nach der kleinsten und einfachsten möglichen Lösung. Daher schließe ich ausgefallene Lösungen wie echte RNG-Hardware, Funkempfänger usw. aus.

Alles, was ich habe, ist ein 16-Bit-Timer-Zähler in der CPU und ein unbenutzter Portpin, der Zugriff auf einen ADC hat.

Meine derzeitige Lösung besteht darin, nur einen Widerstand (so ungenau wie möglich) zu verwenden, um ungefähr die Hälfte der Versorgungsspannung für den ADC-Pin bereitzustellen, und den RNG mit dem ersten AD-Umwandlungswert zu setzen. Heutzutage haben die meisten 10% -Widerstände jedoch eine Ungenauigkeit von weit unter 1% (es wäre lustig, sich das Gesicht eines Lieferanten vorzustellen, wenn ich ihnen sage, dass wir die schlechtesten SMD-Widerstände suchen, die sie finden können), daher besteht eine sehr hohe Wahrscheinlichkeit für mehrere Einheiten, die mit demselben Samen beginnen.

Eine bessere Alternative wäre, mehrere Konvertierungen durchzuführen und einen Wert aus den niedrigstwertigen Bits dieser Messungen zu erstellen. Ich habe jedoch zuvor den ADC dieses µc-Typs verwendet und weiß, dass er sehr genau ist. Hier kann es hilfreich sein, den ADC mit der schnellstmöglichen Geschwindigkeit zu betreiben.

Hat jemand einen besseren Vorschlag? Es ist nicht erforderlich, dass das Saatgut perfekt gleichmäßig verteilt ist, aber je gleichmäßiger die Verteilung ist, desto besser. Ein 16-Bit-Startwert mit einer vollkommen gleichmäßigen Verteilung wäre ein Traum, der zu schön ist, um wahr zu sein, aber ich denke, eine halbwegs anständige Verteilung über 5 oder 6 Bits könnte ausreichen.

vsz
quelle
12
"Es würde Spaß machen, sich das Gesicht eines Lieferanten vorzustellen, wenn ich ihm sage, wir wollen die schlechtesten SMD - Widerstände, die er finden kann." Leute in der Produktion, die dieses eine Teil manuell löten müssen, nachdem die Platine aus dem Bestückungsautomaten kommt, aus einem Behälter, in dem wir jeden Widerstandswert, den wir haben, zusammengemischt haben. - Weil ich kein RNG suche, sondern einen Samen . Wenn es also fast jedes Mal den gleichen Wert erzeugt, wenn es nicht so schlimm ist, ist es wichtiger, dass Sie sich von Gerät zu Gerät unterscheiden.
vsz
8
Warum nicht während der Produktionsprogrammierung einen zufälligen Wert in den EEPROM-Speicher schreiben? Auf diese Weise können Sie das ausgefallenste RNG verwenden, das Ihnen gefällt, da es sich nur um Produktionsprogrammierer und nicht um Endgeräte handelt. (Dank an @immibis: Ihre "etwas andere Software-Datei" brachte mich auf die Idee.)
Calrion
2
Um% 100 klar zu sein, besteht das Problem darin, dass sie mit der gleichen Sequenz beginnen und nicht mit der Zeit auseinander driften, richtig?
Mittwoch
2
Die Wahl Ihres RNG ist von Bedeutung: Einige benötigen qualitativ hochwertiges Saatgut, andere nicht. Für Xorshift funktioniert beispielsweise jeder Startwert anders als 0 und genauso gut. Sogar ein kleiner Unterschied in der Anfangssaat führt zu einer sehr unterschiedlichen Startposition im Zyklus des RNG.
curiousdannii
3
Sie können alle ADC-Antworten mit Statistiken und Timing kombinieren, um noch mehr Zufälligkeit zu erzielen. Messen Sie beispielsweise, wie viele Prozessorticks erforderlich sind, bis Sie N Samples mit den unteren 3 LSBs von 101 und M Samples mit den unteren 3 LSBs von 110 nehmen. Erweitern Sie dieses Konzept nach Bedarf.
WJL

Antworten:

24

Legen Sie einen Parallelwiderstand und einen Kondensator zwischen den A / D-Pin und Masse. Stellen Sie den Widerstand ziemlich hoch ein, vorzugsweise weit über der Impedanzanforderung für das Eingangssignal für den A / D. Stellen Sie die RC-Zeitkonstante auf etwa 10 µs ein. Zum Beispiel klingt 100 kΩ und 100 pF wie eine gute Kombination.

Um einen Wert mit einer gewissen Zufälligkeit zu erhalten, fahren Sie den Stift eine Weile hoch, stellen Sie ihn dann auf hohe Impedanz und führen Sie einige µs später eine A / D-Messung durch. Insbesondere wenn Sie die A / D-Erfassungszeit richtig ausnutzen, hängt die Spannung, die angezeigt wird, von den R- und C-Werten, dem Pin-Leckstrom, anderen Nebengeräuschen und der Temperatur ab.

Ergreifen Sie das niedrige Bit oder die niedrigen zwei Bits und wiederholen Sie diese Schritte nach Bedarf, um eine beliebige Anzahl von Zufallsbits zu erhalten.

Für ein zufälligeres Muster führen Sie diesen Vorgang gelegentlich durch und injizieren Sie das niedrige Bit des A / D-Ergebnisses in den Zufallszahlengenerator, den Sie bereits verwenden.

Olin Lathrop
quelle
Das klingt gut. Stellen Sie sicher, dass Sie die Eingangsimpedanz am ADC überprüfen - die Atmega8-Serie hat eine analoge Eingangsimpedanz von 100Meg, wodurch der Widerstandswert von Olin etwas niedrig ist.
stefandz
3
@stef: Die Eingangsimpedanz und die für die korrekte Konvertierung erforderliche Signalimpedanz sind zwei verschiedene Dinge. Ja, die Eingangsimpedanz ist sehr hoch, da es sich um CMOS handelt. Es gibt jedoch eine maximale Impedanzgrenze für das Signal, damit es die Probe- und Haltekappe innerhalb der angegebenen Zeit aufladen und eventuelle Leckagen am Stift beseitigen kann.
Olin Lathrop
2
Tut mir leid, aufgrund Ihrer Antwort dachte ich, dass Sie die Eingangsimpedanz im Gegensatz zur Quellimpedanzspezifikation referenzierten. 10k ist die spezifizierte maximale Quellenimpedanz des Atmega8, Ihre Antwort ist also genau richtig. Als Referenz ist die S / H-Kappe im Inneren 14pF, falls jemand interessiert war.
stefandz
2
@stef: Ich habe die Antwort bearbeitet, um dies klarer zu machen.
Olin Lathrop
Sie haben die Mondphase und die Feiertage verpasst. Hand winken auch eine nützliche Ergänzung, besonders wenn niedrige C und nicht gut abgeschirmt.
Russell McMahon
23

Einige mögliche Optionen:

  1. Programmieren Sie eine eindeutige Serienadresse für jedes Gerät vor. Wenn Sie über einen ausreichend guten RNG-Algorithmus verfügen, führt auch eine fortlaufende Liste serieller Adressen zu völlig unterschiedlichen Ergebnissen.

  2. Abhängig von Ihrer MCU / Ihrem Setup stehen möglicherweise zwei unterschiedliche Taktquellen für die Systemuhr und den Watchdog-Timer / Timer-Zähler-Eingang zur Verfügung. Wenn eine / beide signifikante Abweichungen aufweisen, können Sie diese verwenden, um einen entsprechend anderen Samen zu erzeugen. Hier ist ein Beispiel, das ich geschrieben habe und das einen internen Watchdog-Timer von Arduino und eine externe XTAL-Systemuhr verwendet .

  3. Verwenden Sie einen BJT-Transistor und bauen Sie einen in hohem Maße Beta-abhängigen Verstärker. Dies kann von einem ADC für den Startwert gelesen werden.

  4. Kondensatoren / Induktivitäten weisen normalerweise eine viel schlechtere Toleranz als Widerstände auf. Sie könnten damit eine Art Filterschaltung (RC, RL, LC) aufbauen und den Ausgang mit dem ADC messen.

helloworld922
quelle
5
Ich stimme für Option 1, es ist eine Zero-Part-Count-Lösung, die dazu führt, dass die Sequenzen niemals übereinstimmen müssen. Die Seriennummer und der RND-Generator können 16 Bit anzeigen, sodass Geräte kaum die Möglichkeit haben, das Muster eines anderen zu imitieren.
KalleMP
1
Ich mag auch die Lösung. Wenn Sie einen einfachen Hashing-Algorithmus verwenden, sollten Sie auch dann in Ordnung sein, wenn Sie fortlaufende Seriennummern haben.
magu_
6
Eine nette Sache bei Option 1 ist, dass einige Geräte mit eingebauten Seriennummern (normalerweise mit Netzwerk- / HF-bezogenen Mikros) ausgestattet sind, sodass Sie nicht einmal einen separaten Schritt zum Brennen der Seriennummern benötigen
slebetman
3
Sogar ein Müll-RNG wie ein LCG wird "wild unterschiedliche Ergebnisse für eine sequentielle Liste von Serienadressen erzeugen" . Ich stimme auch für 1.
BlueRaja - Danny Pflughoeft
3
Wenn Sie eine Zeitquelle haben, können Sie diese als Basis für das Einschalten des Seeds verwenden, um Probleme zwischen den Läufen auszugleichen. Kombinieren Sie dies mit einer Seriennummer oder der MAC-Adresse, falls Ihr Gerät eine hat, und Sie werden auch die Übereinstimmung zwischen den Geräten korrigieren. Ich habe eine Software gesehen, die einige oder alle Zufallszahlen, die zur Verwendung als Startwert generiert wurden, auch nach einem Neustart dauerhaft speichert. Wenn Ihre Geräte unterschiedliche Betriebszeiten haben, sollten sie auseinander driften.
TafT
8

Nicht initialisierter Speicher

Sie können versuchen, den nicht initialisierten Speicher des Mikrocontrollers zu verwenden. Der Trick besteht darin, die Bits zu finden, die die "ausgeglichensten" Flip-Flops aufweisen und tatsächlich zufällig sind. Das Verfahren besteht darin, den gesamten Speicher auszulesen, zurückzusetzen und einige Male zu wiederholen, um zu messen, welche Bits wirklich zufällig sind. Dann verwenden Sie diese Karte, um genügend zufällige Bits auszulesen, um Ihr PRNG oder LFSR zu setzen!

Diese Methode sollte Ihnen auch bei identischer Hardware zufällige Startwerte liefern. Weitere Details (und Links) finden Sie in diesem Artikel

Diese Methode gefällt mir, weil keine zusätzlichen Schaltkreise oder Pins erforderlich sind. Ihr AVR hat bereits RAM, Sie müssen nur die instabilen (zufälligen) Bits finden. Auch das Mapping-Verfahren könnte automatisiert werden; Sie können auf jedes Gerät denselben Code und dieselbe Prozedur anwenden und wirklich zufällige Ergebnisse erzielen!

esoterik
quelle
1
Sie müssen nicht wirklich herausfinden, welche Bits zufällig sind. Durch XOR-Verknüpfung aller Bytes erhalten Sie ein zufälliges Ergebnis, auch wenn nur 8 Bits zufällig sind. Und wie das Bild zeigt, sind die tatsächlichen Werte zeitlich nicht zufällig, sondern eindeutig genug - und genau das brauchen wir hier.
MSalters
1
Wenn Sie ein PRNG finden, mit dem Sie Entropie "einmischen" können, ist dies möglicherweise sogar besser als die Option "XOR-then-seed". Durchlaufen Sie den nicht initialisierten Speicher und mischen Sie die Bytes in den PRNG. Siehe z. B. meine einfachere zufällige C-Bibliothek - Mischfunktion .
Craig McQueen
Dies gibt Ihnen keine Zufälligkeit in Kryptoqualität.
@CamilStaps wird es natürlich nicht.
Navin,
1
Das wird nicht funktionieren. Nicht initialisierter Speicher ist undefiniertes Verhalten, wenn ich ein Betriebssystem habe und nicht steuern kann, welcher Teil des Speichers meinem Programm zugewiesen wird und was zuvor vorhanden war. Auf einem Mikrocontroller ohne Betriebssystem ist dies nicht der Fall. Besonders bei AVR, da dort der gesamte RAM Null ist, wenn genügend Zeit verstrichen ist, um die Kondensatoren durch den Stromverbrauch im Brownout zu entleeren.
vsz
7

Was ich für einen MP3-Player mit Zufallsfunktion getan habe, ist, bei jedem Einschalten einfach einen anderen sequentiellen Startwert zu verwenden. Ich habe bei 1 begonnen und dies im EEPROM gespeichert, so dass ich beim nächsten Ein- und Ausschalten 2 usw. verwendete. Dies war auf einem ATMEGA168. Wie helloworld922 feststellte, wird selbst ein einfacher sequentieller Startwert völlig unterschiedliche Pseudozufallssequenzen erzeugen.

Ich habe einen der linear kongruenten Zufallsgeneratoren verwendet, dies ergibt eine gleichmäßige Verteilung.

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

Natürlich, wenn Sie möchten, dass mehrere Geräte unterschiedliche Sequenzen haben, obwohl sie möglicherweise die gleiche Anzahl von Einschaltzyklen hatten, müssen Sie etwas nach dem Zufallsprinzip starten.

Dies könnte mit einer der Methoden geschehen, die auf den anderen Postern vorgeschlagen wurden. Eine Methode, die ich mir vorstellen kann, könnte den Wechselstrom-Nulldurchgang verwenden, der in den Prozessor fließt, wenn Sie ihn haben (zum Beispiel zur Steuerung der Lampenphase). Dies könnte verwendet werden, um den Timer bei der ersten Kreuzung nach dem Einschalten abzutasten und dann als Startwert zu verwenden.

Befinden sich am Gerät Tasten zur Auswahl des Modus usw.? Wenn dies der Fall ist, können Sie den Zähler beim ersten Drücken der Taste nach dem Programmieren der MCU abtasten. Sie können zunächst einen zufälligen Startwert generieren und im EEPROM speichern. Bei jedem Einschalten nach diesem Zeitpunkt wird der gespeicherte Startwert verwendet.

Kevin White
quelle
5

Ein ADC ist eine sehr gute Quelle für Zufälligkeiten.

Sie müssen sich nicht auf Widerstandstoleranzen verlassen. Jeder Widerstand erzeugt thermisches Rauschen und der gleiche physikalische Effekt führt bei allen Abtast- und Umwandlungsschritten Rauschen in den ADC ein. (Das Datenblatt gibt Auskunft über die Lautstärke und die schlechtesten / besten Konfigurationseinstellungen.)

Sie sollten den ADC-Pin nicht schweben lassen. Dies kann dazu führen, dass die Spannung zu weit schwimmt und der Eingang möglicherweise gesättigt wird.
(Bei vielen MCUs können Sie ungefähr die Hälfte der Versorgungsspannung als ADC-Eingang für die Kalibrierung verwenden. Dadurch wird der externe Widerstand geschont und es treten weiterhin Störungen auf. Die schlechteste / beste Konfiguration finden Sie im Datenblatt.)

Sie müssen sich nicht auf eine einzige ADC-Messung verlassen. Sie können mehrere Messungen mit einer einfachen Hash- oder Prüfsummenfunktion kombinieren (CRC würde ausreichen). Wenn Sie den RNG sofort verwenden müssen, können Sie das ADC-Ergebnis später mit dem aktuellen RNG-Startwert kombinieren.

CL.
quelle
2
Ich bin nicht sicher, ob Johnson Noise für diese Anwendung geeignet ist. Bei STP hat ein 10Meg-Widerstand über eine 10-kHz-Bandbreite 40uVJohnson-Rauschen. Sie benötigen einen> 14-Bit-ADC oder eine Verstärkerschaltung, um dies angemessen zu messen.
helloworld922
STP ist nicht wirklich relevant. Insbesondere die Temperatur könnte absichtlich erhöht werden, aber zusätzliche 60 Grad über STP bedeuten nur 10% zusätzliches Rauschen.
MSalters
1
Ein ähnlicher Ansatz wäre die Verwendung des Schussrauschens in einer Diode. en.wikipedia.org/wiki/Noise_generator#Shot_noise_generators
Teambob
2

Können Sie den Samen von Sitzung zu Sitzung speichern? Wenn ja, ist es möglich, jedes Gerät nach der Erstellung für einen zufälligen Zeitraum einzuschalten? Auf diese Weise werden alle Einheiten mit voreingestellten Samen geliefert, die wahrscheinlich nicht gleich sind.

Ein anderer Gedanke: Wie können Sie mehrere Geräte miteinander verbinden, damit sie gleichzeitig eingeschaltet werden? Wenn sie in Reihe geschaltet sind, fügen Sie eine Art Kondensator hinzu, damit das (n + 1) -te Gerät einige Taktzyklen nach dem n-ten Gerät startet. Im Idealfall entladen sich Kondensatoren beim Herunterfahren des Geräts sehr schnell, sodass bei jedem Start / Neustart eine größere Lücke zwischen den Sequenzen entsteht.

Wenn sie parallel sind, können Sie die Startzeit noch ein wenig zufällig einstellen. Ich gehe davon aus, dass es eine Art Leistungsfilterung mit Kondensatoren gibt. In diesem Fall würde die Herstellung der Geräte mit geringfügig unterschiedlichen Filterkreisläufen dazu führen, dass jedes Gerät zu einem geringfügig unterschiedlichen Zeitpunkt startet und nach mehreren Neustarts eine Divergenz auftritt.

Eine Variation hiervon besteht darin, Ihren Taktsignalen nach Möglichkeit eine Varianz hinzuzufügen. Ein Unterschied von 0,1% in der Taktrate hat möglicherweise nur geringe Auswirkungen auf die Lichtshow, während Sie die Geschwindigkeit, mit der Sie die PRNG-Tabelle durchlaufen, relativ schnell ändern.

MichaelS
quelle
1
Schließen Sie möglicherweise einen großen Ausguss an den analogen Pin an und messen Sie das "Netzbrummen", um den RNG zu bestimmen.
Jasen,
1
@Jasen, alle Geräte, die an dasselbe Verlängerungskabel angeschlossen sind, haben dasselbe Netzbrummen.
Ian Ringrose
2

Wenn Sie mit einer internen "kalibrierten" Taktquelle arbeiten. Könnten Sie einen Startwert nach einiger Zeit nicht speichern, vorzugsweise in das EEPROM. Die Uhr driftet und unterscheidet sich von Gerät zu Gerät. Zum erneuten Speichern eines neuen Werts nach einiger Zeit (etwa alle 10 Minuten oder nach einer Zeit, die kurz genug ist, um innerhalb der normalen Einschaltdauer des Geräts zu liegen. Je länger das Gerät eingeschaltet ist, desto wahrscheinlicher ist die Speicherung ein "anderer" Wert in das EEPROM.

Machen Sie auch ab und zu einen Sprung (nicht zu oft) und wiederholen Sie die Zeit, während das Gerät eingeschaltet ist (speichern Sie diesen neuen Wert im EEPROM).

Mats
quelle
2

Wie wäre es, wenn Sie Ihre ursprüngliche Idee der AD-Wandlung basierend auf einem variierenden Widerstand durch Hinzufügen eines LDR oder Thermistors erweitern würden? (Der erste müsste in der Lage sein, nach draußen zu "schauen", ich weiß nicht, ob das machbar ist; aber die Variation des Lichts kann höher sein als die Variation der Temperatur zwischen Geräten, die ungefähr zur selben Zeit an ungefähr derselben Stelle gestartet wurden. ..)

Hagen von Eitzen
quelle
1
Thermistoren haben eine weitere nützliche Eigenschaft. Einige Serien der meisten Hersteller weisen eine enorme Varianz und Ungenauigkeit auf. Dies wird das Ergebnis weiter "verbessern".
Ariser
1

2 mögliche Lösungen, vorausgesetzt, Sie benötigen einen eindeutigen Startwert pro Einheit.

  1. Wenn Sie Ihre Einheiten ab Werk einzeln flashen, kann die Hex-Datei durch ein Zwischenskript im Programmierer programmgesteuert geändert werden. Wenn es PC-gesteuert ist, können Sie eine variable Initialisierung mit Datum und Uhrzeit überschreiben. Garantiert einzigartig für jede Einheit!

  2. Dallas 1-Draht-Geräte verwenden nur einen Pin und haben jeweils eine eindeutige 64-Bit-Seriennummer. Sie können dies als Samen verwenden.

Loganf
quelle
1
Ich mag 2, aber leider sind die DS-Teile alle ziemlich teuer.
Ariser
Verwenden Sie den Produktionszeitstempel nicht für Zufälligkeiten in Kryptoqualität, es ist vorhersehbar.
2
@CamilStaps Für die Anwendung des OP ist keine Kryptoqualität erforderlich
Hagen von Eitzen
1
@HagenvonEitzen stimmt, aber andere mögen auf diese Frage kommen und nach Crypto-Q-Zufälligkeit suchen, daher ist es erwähnenswert.
4
@CamilStaps Seufz , es scheint , dass Sie auf die Menschheit aufgegeben haben :) Ist es wirklich zu anspruchsvoll von jemandem zu erwarten , die eine Antwort von electronicsSE für kryptographische Zwecke verwenden möchte , dass sie zumindest vorsichtig genug sein , um die Frage zu lesen , sie zu beantworten soll , ? "16bit" - oder "5 o5 6 bit" -Samen sind keine Krypto-Q, selbst wenn sie von einer Gruppe von Schrödinger-Katzen generiert werden :)
Hagen von Eitzen
1

Sie können einen potentialfreien ADC-Pin belassen, um den Zufallszahlengenerator (RNG) mit erfasstem Rauschen zu versorgen. Es sollte ausreichen, einen Startwert zu generieren oder ihn sogar als RNG-Generator zu verwenden.

Vergessen Sie nicht, die minimal mögliche Konvertierungszeit zu verwenden.

Die andere Lösung könnte ein Rauschgenerator sein, der in den ADC-Pin eingesetzt wird.

jnk0le
quelle
2
Ich werde einige Messungen durchführen, aber wenn ich mich richtig erinnere, liest ein schwebender ADC-Pin 0oder nähert sich 0. Ich werde es noch einmal überprüfen, um festzustellen, ob dies der Fall ist.
vsz
1
Ich bin interessiert, liest es 0beim schweben?
Bence Kaulics
2
Das Problem ist, dass dies möglicherweise auf einer Entwicklungsplatine funktioniert und im Endprodukt fehlschlägt.
vsz