Ihre Aufgabe ist es, einen Hardware-Zufallszahlengenerator mit der Hardware zu improvisieren, die Sie haben.
Herausforderung
Schreiben Sie ein Programm mit folgenden Eigenschaften:
- Es wird entweder
0
oder1
(und sonst nichts) gedruckt . - Die Ausgabe hängt von einem physischen Prozess ab und nicht nur vom internen Zustand des Computers.
- Es gibt keine Beziehung zwischen den Ausgaben nachfolgender Läufe (im Abstand von einer Minute).
- Die Leistung ist mit keinem realistischen Aufwand vorhersehbar.
- Die Wahrscheinlichkeit der Ausgabe
0
liegt zwischen 0,2 und 0,8. - Es läuft mit einer relativ hohen Wahrscheinlichkeit in weniger als einer Minute.
Sie müssen erklären, warum Ihr Programm diese Eigenschaften hat, wenn dies nicht offensichtlich ist.
Erläuterungen und Einschränkungen
Das Folgende mag wie eine Menge Einschränkungen für einen Beliebtheitswettbewerb erscheinen, aber letztendlich ist es alles, um sicherzustellen, dass das Programm im Geist der Frage bleibt, etwas funktioniert und um Lösungen zu vermeiden, die beliebt sind, weil sie ein totaler Overkill sind, aber ultimativ eher langweilig.
- Die Systemzeit zählt nicht als physischer Prozess.
- Sie können jede beliebige Consumer-Hardware verwenden, von 8-Zoll-Floopy-Disk-Laufwerken über einen USB-Raketenwerfer bis hin zu Kopfhörern - es sei denn, diese ist für die Zufallsgenerierung vorgesehen. Ein Hardware-Teil ist für den Endverbraucher geeignet, wenn es in Massenproduktion hergestellt wird und weniger als 1000 US-Dollar kostet. Sie können also keine Radioteleskope, das CERN, MRTs oder Ihren selbstgebauten Partikeldetektor verwenden.
- Sie können nur die grundlegendsten Annahmen zum Status und zur Ausrichtung der Hardware treffen, z. B. Einschalten (sofern diese über einen Netzschalter verfügt) und ordnungsgemäße Installation und Funktionsweise. Beispielsweise können Sie davon ausgehen, dass ein CD-Laufwerk im Allgemeinen in der Lage ist, eine CD zu lesen und nicht zu blockieren, aber Sie können nicht davon ausgehen, dass es offen oder geschlossen ist oder eine CD enthält. In einem anderen Beispiel können Sie nicht davon ausgehen, dass zwei Hardware-Teile aufeinander abgestimmt sind, um eine besondere Interaktion zu ermöglichen, sondern dass sie sich im selben Raum befinden.
- Sie können die Hardware in einem beliebigen Zustand belassen, es sei denn, Sie beschädigen sie.
- Sie können und müssen davon ausgehen, dass sich die Hardware in einer natürlichen Umgebung befindet, mehr jedoch nicht. Sie können beispielsweise davon ausgehen, dass sich die Hardware weder in einem Tank mit flüssigem Helium noch in einem extrem schall- und lichtdichten Raum oder im Weltraum befindet. Es kann jedoch nicht davon ausgegangen werden, dass Schall- und Lichtquellen vorhanden sind, außer solchen, die nur mit radikalen Anstrengungen vermieden werden können.
- Ihr Programm muss auf einem Standard-Desktop-Computer mit einem nicht-esoterischen Betriebssystem Ihrer Wahl ausgeführt werden. Sie können jede Software verwenden, die nicht speziell für die Generierung von Zufallszahlen entwickelt wurde.
- Sie können keinen Internetzugang annehmen.
- Sie können nicht davon ausgehen, dass Menschen anwesend oder abwesend sind, aber Sie können davon ausgehen, dass niemand absichtlich in Ihr Programm eingreift, z. B. indem Sie einen Lüfter manuell stoppen oder ein Programm ausführen, das nichts anderes tut, als das Mikrofon so oft wie möglich auszuschalten.
- Sie können nur die grundlegendsten Annahmen über die Softwareeinstellungen treffen. Beispielsweise können Sie davon ausgehen, dass Treiber installiert und aktiviert sind, Sie müssen jedoch darauf vorbereitet sein, dass der Ton stummgeschaltet wird.
- Sie können die Softwareeinstellungen in einem beliebigen Zustand belassen.
Bonus
Eine besondere Belohnung wurde für eine besonders kurze Lösung vergeben. Dies war eher durch die Anzahl der Anweisungen und ähnlich als durch die Zeichen. Die Gewinner waren (gebunden nach meinen Kriterien):
- Diese Antwort von Franki.
- Diese Antwort von Tejas Kale.
Ich konnte nur eine Antwort vergeben und die Antwort von Tejas Kale wurde durch Los gewonnen.
quelle
Antworten:
Schale
Liest ein einzelnes Sample aus dem Mikrofon-Stream und druckt das niedrigstwertige Bit, das vom Rauschen dominiert werden sollte.
EDIT: Geändert, um die Stummschaltung des Mikrofons aufzuheben ... und alles andere auch!
quelle
cat /dev/urandom > /dev/dsp
, nur für den Fall, dass sich der Computer in einem schalldichten Raum befindet.Bash
Erfasst die Entropie von der Antwortzeit eines einzelnen Pings an localhost.
Beachten Sie, dass die Antwortzeit genau dreimal in der Ausgabe von
ping -qc1
:Alle anderen Zahlen und konstant und - was noch wichtiger ist - unabhängig von der Reaktionszeit.
sed 's/[^1-9]/+/g'
Wandelt jede Null und jede Ziffer in Pluszeichen um und gibtecho $[...0&1]
die Parität der resultierenden Summe aus.quelle
CYGWIN_NT-6.2-WOW64 work 1.7.28(0.271/5/3) 2014-02-09 21:06 i686 Cygwin
-ping
hat weder-q
noch-c
hier.ping
bestätigt. Ich bin überrascht.JavaScript + HTML5 DeviceMotion
JSFiddle hier .
Verwendet die HTML5 DeviceMotion-API auf unterstützten Geräten (hauptsächlich Mobilgeräten). Es verwandelt das resultierende
acceleration
Objekt in JSON, hackt es und nimmt den Rest von Modulo 2.Der größte Teil des Codes ist die Hash-Funktion (verdammt noch mal JavaScript und das völlige Fehlen einer Standardbibliothek). Es könnte wahrscheinlich kürzer sein, aber ich bin ein Trottel für eine gute Hash-Funktion.
quelle
Python + Webcam
Mit Code schamlos gestohlen hier , nimmt eine shapshot Ihre Webcam verwenden, Hashes , die Daten und druckt das niedrigstwertige Bit.
quelle
Perl
Überprüft die Antwortzeit Ihrer Festplatte, indem drei Vorgänge zeitlich festgelegt werden:
Schließlich wird die benötigte Zeit als Float gepackt und das 11. höchstwertige Bit verwendet (das zweithöchste Bit der Mantisse).
quelle
Bash
sensors
druckt die aktuellen Systemtemperaturen zusammen mit der Lüftergeschwindigkeit.sed 's/[^1-9]/+/g'
Wandelt jede Null und jede Ziffer in Pluszeichen um und das Echo gibt$[...0&1]
die Parität der resultierenden Summe aus.Regex- und Paritätsberechnung entlehnt der Antwort von Dennis.
quelle
Bash
Benutzt alles, nur für den Fall ...
Kommt drauf an
/sys
oder/proc
)/proc/<pid>/s*
hängen verschiedene Werte in (z. B. sched / schedstat) von der Geschwindigkeit der Hardware ab, die erforderlich ist, um diese Prozesse zum Leben zu erwecken.Die Laufzeit auf meinem System beträgt ~ 10s, kann aber stark variieren. Führen Sie dies insbesondere nicht als root aus, oder ändern Sie es zumindest zum Ausschließen
/proc/kcore
(es sei denn, Sie sind bereit, viel Zeit für das Einschließen der darin enthaltenen Entropie zu verwenden, was wahrscheinlich wirklich alles einschließen würde).quelle
Shell + Wi-Fi
Versetzt die WLAN-Karte in den Überwachungsmodus, speichert empfangene Pakete im Wert von 30 Sekunden (einschließlich nicht lesbarer verschlüsselter Daten aus benachbarten Netzwerken), nimmt den sha512-Hash der Paketdaten und gibt 1 zurück, wenn der erste Buchstabe des Hashs 0-7 ist . Angenommen, Ihre Wi-Fi-Karte ist
wlan0
und Sie haben derzeit keinmon0
Gerät.Wenn sich keine Wi-Fi-Geräte in der Nähe befinden, ist die Ausgabe vorhersehbar, da sie jedes Mal dieselbe ist.
quelle
Moderne 8086-kompatible Prozessoren von Intel enthalten ein leicht zugängliches Peripheriegerät, das eine ordnungsgemäße Zufälligkeit erzeugt. Das Ansteuern dieses Peripheriegeräts erfolgt unter Verwendung des
rdrand
Befehls, der entweder ein zufälliges Bitmuster erzeugt oder das Übertragsflag setzt, wenn das Peripheriegerät nicht verfügbar ist oder keine Entropie mehr aufweist.Das folgende Kurzprogramm für 80386 Linux prüft anhand der
cpuid
Anweisung , ob das Peripheriegerät verfügbar ist und versucht, eine Zufallszahl zu generieren. Wenn entweder das Peripheriegerät oder eine Zufallszahl nicht verfügbar ist, wird das Programm mit dem Status beendet1
. Konnte eine Zufallszahl generiert werden, wird entweder a1
oder a0
ausgedruckt und das Programm mit dem Exit-Status beendet0
.Speichern unter
rand.s
und zusammenbauen mitHier ist die gesamte Versammlung:
Und ein Dump der resultierenden 77 Bytes Maschinencode:
quelle
rdrand
ist kein Zufallszahlengenerator. Es ist ein Peripheriegerät, das von der NSA entwickelt wurde, um sich mit der Kryptographie der Menschen zu beschäftigen.Bash
Ziel ist die unnötig teure Methode zum Sammeln von Zufallszahlen. Wie lange es dauert, Emacs millionenfach zu spawnen, und verwenden Sie dann Dennis 'Trick, um die Zeit in einen einzelnen Booleschen Wert umzuwandeln (auf meinem Computer dauert es ungefähr 7 Sekunden).
quelle
Arduino Mega1280
edit: aktualisierte Version, die robust ist, wenn etwas in die Pins gesteckt ist. Die Idee beruht auf der Tatsache, dass der ATMega1280 einen separaten internen Oszillator für den Watchdog-Oszillator verwendet. Ich richte einfach einen Watchdog-Interrupt ein, der ein Flag setzt, einen Zähler basierend auf der Systemuhr (auf dem Arduino ist dies ein externer 16-MHz-Quarz) und erlaube, dass Taktjitter / -varianz die Arbeit machen.
quelle
Javascript
http://jsfiddle.net/prankol57/9a6s0gmv/
Nimmt Videoeingang.
Sie können den Screenshot sehen, mit dem die Zufallszahl berechnet wurde.
quelle
Shell unter Linux
Messen Sie die Lesegeschwindigkeit einer Festplatte und die Zugriffszeit eines häufig aktualisierten Verzeichnisses auf dieser Disc, dessen Layout nicht vorhersehbar ist.
erfordert:
Dieser Ansatz hat den Vorteil, dass keine Daten auf dem System geändert werden und kein Perl über dem von primo erforderlich ist.
quelle
Schale
Getestet unter Linux, aber vielleicht hat Ihr U * IX / proc / stat auch?
Dies startet nur einen zusätzlichen Vorgang, liest nur eine zusätzliche Datei (nicht einmal auf der Disc) und ist 37 Zeichen kurz. Es ist auch ziemlich schnell.
Man kann denken, dass dies von allen Kernel- und Userland-Prozesszuständen bestimmt wird, aber das ist nicht der Fall, da / proc / stat auch die E / A-Wartezeit, die Zeit für die Wartung von Hardware-Interrupts, die Zeit für Leerlaufaufgaben und einige andere umfasst hängen vom externen Hardwareeingang ab.
quelle
Matlab
Die Mikrofonlösung:
Nimmt 10 Sekunden Ton auf, ermittelt die Anzahl der negativen Samples in der Aufnahme und gibt 0 aus, wenn diese Anzahl gerade ist, und 1, wenn sie ungerade ist. Also 0 mit 50% Wahrscheinlichkeit. Der Ansatz bedeutet, dass selbst geringe Mengen an Rauschen, die bei einer stillen Aufnahme unvermeidbar sind, ausreichen, um eine zufällige Ausgabe zu generieren. Der folgende etwas längere Code beschleunigt den Zahlengenerator, indem eine kürzere Aufzeichnung verwendet wird, die mit einer höheren Bitrate kompensiert wird, die mehr Rauschen erzeugt.
In einem Test unter ruhigen Bedingungen stelle ich fest, dass in 100 Läufen des letzteren Codes der Code 51 Mal null ausgibt. 100 Läufe unter lauten Bedingungen wurden 40-mal null produziert.
Edit: Danke an Emil für den Hinweis auf einen Fehler im Originalcode :-)
quelle
Bash
(Danke, Dennis.)
quelle
w
Zeigt eine Liste der angemeldeten Benutzer an, die leer sein können. Die Systemlast basiert auf der Länge der CPU-Warteschlange.w
mittop
.Nimmt das niedrigstwertige Bit des Beschleunigungsmessers des Computers (benötigt das
hdaps
Linux-Modul):Dies misst im Wesentlichen das Rauschen des Sensors.
quelle
SmileBASIC
Verwendet den Bewegungssensor des 3DS. Die Z-Achse des Beschleunigungsmessers liegt normalerweise bei -1 (aufgrund der Schwerkraft), und aufgrund von zufälligem Rauschen kann sie manchmal darüber oder darunter liegen.
Hier ist eine, die das Mikrofon verwendet:
quelle
Bash
Ich nahm Sohams eigenen Vorschlag an (unter Verwendung von
top
):Bearbeiten: Es funktioniert genauso wie bei Soham. Alle nicht numerischen Zeichen in der Ausgabe von top werden in '+' umgewandelt, und die Parität der resultierenden Zeichenfolge wird ausgewertet.
Das 'b'-Flag nach oben führt es im Batch-Modus aus, sodass alle Prozesse gemeldet werden, nicht nur der erste Bildschirm und' n1 'sagt, dass nur 1 Iteration von oben ausgeführt werden soll.
quelle