"Richtige" Zufallszahlen erzeugen

[heinz]

Hallo Zusammen,

ich bin mal wieder auf der Suche nach einer etwas ungewoehnlichen Sache...

Ich Suche nach einer Moeglichkeit eine "echte" Zufallszahl am Computer zu erzeugen.
Da scheint es einige Moeglichkeiten zu geben.
Besonders interessiert mich die Moeglichkeit, die Soundkarte dafuer zu nutzen. (Scheint mir im Moment am einfachsten umzusetzen zu sein...)
Die Theorie ist einfach:
Man nimmt z.B. das Rauschen auf, welches vom Mikrofoneingang kommt wenn kein Mikrofon angesteckt ist.

Nach ein paar versuchen in der Art:

Code: Alles auswählen

arecord -t raw -d5 -r 48000 -f S32_BE zufall.raw

-t Typ
-d Sekunden
-r Rate (Hertz)
-f Signed 32Bit _ BigEndian

habe ich allerdings festgestellt, dass nicht alle Werte in der Datei gleichverteilt sind.

Bei obigem Code sieht die Verteilung bei mir z.B. so aus:
Dateigroesse = 960000 Byte

Code: Alles auswählen

   Zeichen    | Vorkommen (Gerundet)
--------------+--------------------
     #FF      |   11.8%
     #00      |   11.8%
     #01      |    1.3%
     #FE      |    1.2%
Alle anderen  |    0.3%

Jetzt meine eigentliche Frage:

Kennt jemand von Euch eine Seite im Netz, wo diese Art der Erzeugung von Zufallszahlen genauer beschrieben wird?
Ich habe jetzt schon etwas laenger im Netz danach gesucht aber finde fast nur Seiten wo zwar steht, dass man es so machen kann aber keine genauere Beschreibung wie...

Falls keinem eine solche Seite bekannt ist, hat Er oder Sie vlt. eine Idee, wie ich gleichverteilte Werte durch die Aufnahme bekomme...

Schonmal Danke, fuers drueber nachdenken.

Gruss,
heinz

[eggy]

Was spricht gegen den Zufall vom Kernel? Der wird je nach Implementation auch aus unterschiedlichen Buckets gefüllt, der Code war lesbar gut dokumentiert, was da passiert kannst Du also selbst nachlesen.

[heinz]

Was spricht gegen den Zufall vom Kernel?

Eigentlich nichts...
Ich befasse mich nur z.Z. ein wenig mit dem Zufall und wollte die Moeglichkeit einer Erzeugung von Zufallszahlen mit der Soundkarte (Rauschen) einfach mal ausprobieren und testen.
Ich bin ein neugieriger Mensch und fuer solche wie mich ist Linux eine riesige Fundgrube aus Tools mit denen man "verruckte" Ideen einfach mal so ausprobieren kann...
Sorry, wenn ich Euch damit auf die Nerven falle...

Ich habe in der Zwischenzeit weiter im Netz gesucht und schon einige Diskussionen darueber gelesen.
Ich moechte hier auf keinen Fall eine weitere Diskussion darueber anfachen, was die beste Methode ist um eine Zufallszahl zu erzeugen. (Das Netz ist voll davon...)

Aber es gibt halt den "Pseudozufall" (vom Rechner erzeugt und unter Umstaenden vorhersehbar) und den "echten Zufall" (aus natuerlichen Vorgaengen und nicht vorhersehbar) und "der Echte" interessiert mich z.Z.

Habe jetzt auch schon ein paar mal gelesen, dass es besser sein soll, den Line-In-Anschluss zu benutzen und einen Radio daran anzuschliessen, der keinen Sender empfaengt.
Wobei mir der qualitative Unterschied noch nicht ganz klar ist...

Gruss,
heinz

[smutbert]

Du hat bis jetzt nur etwas von 0x00 bis 0xff geschrieben, was ja 8 Bit sind. Wenn der Analog-Digital-Konverter tatsächlich 32 Bit schafft, wäre es vielleicht naheliegender tatsächlich mit 32 Bit aufzunehmen und davon dann zB etwa nur die niederwertigsten 8 auszuwerten. Die werden auch bei Line-In verlässlich vom thermischen Rauschen bestimmt und du brauchst kein Radio.

Der Mikrofoneingang ist zwar oft als Rauschgenerator verschrien, aber wenn der irgendetwas komisches macht, ist es vielleicht schwieriger mit den Werten, die dort herauskommen etwas anzufangen.

Das Vorgehen wird glaube ich – ich habe nur die ersten Zeilen überflogen – auch hier vorgeschlagen:
https://www.volkerschatz.com/science/audiorng.html

Es gibt auch schon fertige Software
- Audio Entropy Daemon: https://www.vanheusden.com/aed/
- im Paket entropybroker gibt es verschiedene Programme für Zufallsquellen, ich glaube da ist auch etwas für Audio dabei

[heinz]

wäre es vielleicht naheliegender tatsächlich mit 32 Bit aufzunehmen und davon dann zB etwa nur die niederwertigsten 8 auszuwerten.

Danke fuer den Hinweis!
Die erzeugte Datei war schon mit 32 Bit aufgenommen aber das selbst "zusammengezimmerte" Programm zum Anzeigen, wertet im Moment nur 8 Bit Werte aus.
Von den 32 Bit nur die niederwertigsten 8 Bit zu verwenden ist aber eine sehr gute Idee.

Du schreibst auch:

...Die werden auch bei Line-In verlässlich vom thermischen Rauschen bestimmt...

Gibt es grosse Unterschiede zwischen Mic. und Line-In?
Klar, das wird auch von der Soundkarte abhaengen. Aber gibt es Hardwareunterschiede zwischen beiden, die das erzeugen von Zufallszahlen beeinflussen koennen?

Und vielen Dank fuer die informativen Links.

Kanntest Du die Seiten schon? Falls nicht, mit welchen Suchbegriffen hast Du sie gefunden?

Gruss,
heinz

[shoening]

Hi,

ich würde es mal mit randomsound probieren. Das sorgt bei den Kernel Zufallszahlen für Entropie über das Rauschen der Soundkarte.

Viele Grüße
Stefan

[heinz]

ich würde es mal mit Debianrandomsound probieren.

Auch Dir Danke fuer den Tipp!
Werde mal den Sourcecode genauer anschauen...

Gruss,
heinz

[hikaru]

Wenn du wissen willst wie arecord aus dem Rauschsignal Bits erzeugt, dann wäre es naheliegend, den Quellcode zu studieren.

Völlig unabhängig davon, könnte deine Grundannahme falsch sein, dass nämlich arecord aufgrund eines "Bugs" ungleich verteilte Werte aus einem gleichverteilten Rauschpegel liefert. Es könnte ebenso sein, dass dein Mikrofoneingang aufgrund äußerer Einflüsse schon gar kein gleichverteiltes Rauschen liefert. Vielleicht hast du einfach nur Taubendreck in deiner Mikrofonbuchse.

[smutbert]

[...]
Gibt es grosse Unterschiede zwischen Mic. und Line-In?
Klar, das wird auch von der Soundkarte abhaengen. Aber gibt es Hardwareunterschiede zwischen beiden, die das erzeugen von Zufallszahlen beeinflussen koennen?

Ich traue dem Mikrofoneingang nicht, weil ich mir da nie sicher wäre, dass das Signal nicht digital verstärkt wird und das möglicherweise noch dazu in Abhängigkeit vom Pegel (Auto-Gain oä).

Verglichem mit dem Mikrofoneingang ist Line-In denke ich einfach überschaubarer und das halte ich bei diesem Anwendungsfall für sehr gut.

Kanntest Du die Seiten schon? Falls nicht, mit welchen Suchbegriffen hast Du sie gefunden?

Nein, ich hatte nur dunkel in Erinnerung, dass ich schon einmal über einen Dämon gestolpert bin der die Soundkarte zur Gewinnung von Zufallszahlen nutzt.

Gesucht habe ich einerseits mit

Code: Alles auswählen

apt search audio random

was mich zu entropybroker geführt hat und sonst waren meine Suchbegriffe glaube ich so etwa „random number generator soundcard linux“.

[wanne]

habe ich allerdings festgestellt, dass nicht alle Werte in der Datei gleichverteilt sind.

Selbstverständlich nicht. Und das wird dir bei "echtem" Zufall auch niemals passieren. Deswegen ist der unbrauchbar für sicherheitsrelevante Teile. Echte Hardware Zufallsgeneratoren nutzen deswegen Hardware von denen man die Verteilung sehr gut kennt. (Kernzerfälle sind z.B. fast perfekt exonentiell.) dann haust du die Umkehrfunktion drüber (also im Fall der Zerfälle den passenden Logarithmus.) und bekommst was halbwegs gleichverteiltes. Normale PC-Hardware ist dazu ungeeignet weil du unendlich viele Einflüsse hast die sich überlagern und die Verteilung nicht mehr abzuschätzen ist. (Und nein. Man kann das nicht mit Statistik gerade biegen. Die Folge 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 mach für jedes Einzelteil gesehen gleichverteilt aussehen sie ist es aber eben nicht, weil die Einzelteile nicht unabhängig sind. Gerade bei Audio wirst du massiv immer Resonanzen und CO haben, die du nie alle finden wirst.)
Die Lösung für solche Probleme sind Mischforemen aus cryptografischen-PRNGs und und echtem Zufall wie /dev/random das macht. Sie bieten dir die Vorteile aus beiden Welten: Unvorhersehbarkeit und zwar in alle Richtungen. (Du kannst von der Zufallszahl nicht auf den Zustand schließen und selbst wenn dir ein Zustand bekannt ist kannst du keine Vorgänger und nur eine Maximalanzahl von Nachfolger vorhersehen.)
Passende Algorithmen sind leider alles andere als Trivial. Es gibt gute Gründe warum die Implementierung von /dev/urandom doch ein paar mehr Zeilen hat. Verzichtet man allerdings auf Unvorhersehbarkeit von Zustand auf Zufallszahlen sondern will nur Unvorhersehbarkeit zwischen den einzelnen Zufallszahlen wird es deutlich einfacher. Dann kannst du dich auf allgemein anerkannte Kryptografische Algorithmen verlassen. Z.B. sowas

Code: Alles auswählen

aes-256-ofb(sha3-265(große Menge na Hardwarerandom*))

In Bash:

Code: Alles auswählen

openssl enc -aes-256-ofb -kfile zufall.raw -nosalt -md sha3-256 -in /dev/zero | head -c 1200

* Große Menge heißt, dass du mehr als 256Bit Streuentropie haben willst. Das Problem ist, dass das ein Wert ist der nur schwer feststellbar ist. Bei deinem Device würde ich auf ca. 1Bit auf 100Byte tippen. Ein guter Kompressionsalgorithmus auf die passende Datei kann dir eine obere Schranken geben. Du willst ja aber eigentlich eine untere Schranke. Und die ist nicht feststellbar. /dev/urandom löst das Problem in dem es halt allen hardware-Random den es bekommen kann nimmt. Das ist dann auf jeden Fall das beste Ergebnis, dass man bekommen kann. /dev/random lässt den Hersteller des Treibers für die Hardware die Abschätzung machen wie zufällig (=> Wieviel Streuentropie) das Gerät liefert. Beide drücken sich also sozusagen um das Problem diese Abschätzung zu machen.

[TuxPeter]

Hi,
ich habe den Thread nur überflogen, möchte aber doch eine Beobachtung beisteuern: Wenn man das Leeraufrauschen, im ungünstigsten Fall noch bei offenen Eingängen, eines Gerätes mal durch eine Spektrumsanalyse schickt, wird man einen Haufen niederenergetischer Spektrallinien finden - alles Anti-Rauschen! Das Gleiche gilt für Radios u. andere Quellen.

Andrerseits besteht ein ziemlich gut thermisch rauschender Generator aus einem einfachen Transistor (BE-Strecke "verpolt") und einem Widerstand, evtl. noch einem Auskoppel-Kondensator. Es wäre also nicht besonders aufwendig, es damit zu versuchen.

Ps.: Irgendein Elektronik-Fuzzi hat mir mal erzählt, dass diese komischen flackernden LEDs, die man heute gerne als Kerzen-Ersatz benutzt (imo eine besondere Umweltsauerei) im Prinzip einen Rauschgenerator enthalten - keine Ahnung, ob der gleich digital oder die Quelle analog rauscht.

[eggy]

Sorry, wenn ich Euch damit auf die Nerven falle...

Keine Sorge, tust Du nicht. Aber der Wink mit dem Kernelcode war schon so gemeint, dass es sinnvoll ist, das zu lesen.
Die benutzen nämlich unterschiedliche Eingaben aus einigen Hardwarequellen und bauen daraus den Zufall zusammen. Also genau das, was Du vorhast, nur, dass die eben mehrere Quellen hernehmen, in Eimer füllen und deren Inhalte umrühren und zusammenwürfeln. Wenn ich das richtig in Erinnerung hab, standen da auch ausreichend viele Kommentare dabei, so dass man das selbst ohne große C Kenntnisse noch relativ gut verständlich findet.

Aber es gibt halt den "Pseudozufall" (vom Rechner erzeugt und unter Umstaenden vorhersehbar) und den "echten Zufall" (aus natuerlichen Vorgaengen und nicht vorhersehbar) und "der Echte" interessiert mich z.Z.

Das das Du da machen willst, ist, wenn man es mal ganz genau nimmt, auch nur Pseudozufall. Denn Deine Soundkarte wird nen gewissen Bias haben, bestimmte Töne garnicht wahrzunehmen. Perfekten Zufall erzeugen ist SEHR SEHR SEHR schwer, ich würde fast so weit gehen wollen zu sagen "unmöglich", Restbias bleibt immer.

Habe jetzt auch schon ein paar mal gelesen, dass es besser sein soll, den Line-In-Anschluss zu benutzen und einen Radio daran anzuschliessen, der keinen Sender empfaengt.
Wobei mir der qualitative Unterschied noch nicht ganz klar ist...

Das Stichwort ist "White Noise" https://de.wikipedia.org/wiki/Weißes_Rauschen

Bemüh Dich mal in die Unibib, da stehen in der Infomatikabteilung wahrscheinich ne Menge Bücher über Kryptografie, in etwa jedem dritten davon solltest Du Referenzen auf gute Paper finden.

Nen guter Startpunt ist auch
https://blog.cryptographyengineering.co ... lustrated/

Schneier schreibt in Applied Cryptography auch nen paar Sätze zu dem Thema, u.a.:

Donald Knuth quotes John von Neumann as saying: “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin” [863].

Und definiert folgend einen Sequenzgenerator als Pseudozufällig, nennt dazu die zu erfüllenden Eigenschaften und definiert ihn als real random

if it has this additional third property:
3. It cannot be reliably reproduced. If you run the sequence generator twice with the exact same input (at least as exact as humanly possible), you will get two completely unrelated random sequences.

Nun hat man in der Computerei aber folgendes Problem: Die meisten Definitionen von "Algorithmus" verlangen Determiniertheit. Und das steht in krassem Widerspruch dazu.

Schau dir mal was, was er an den Zitatstellen im Anhang verlinkt, da sollte ausreichend gutes Material dabei sein. Das Buch ist zwar schon älter, aber grundlegend hat sich daran nichts geändert.

[eggy]

Ps.: Irgendein Elektronik-Fuzzi hat mir mal erzählt, dass diese komischen flackernden LEDs, die man heute gerne als Kerzen-Ersatz benutzt (imo eine besondere Umweltsauerei) im Prinzip einen Rauschgenerator enthalten - keine Ahnung, ob der gleich digital oder die Quelle analog rauscht.

Und wenn man die lange genug laufen lässt, sieht man, dass die sich wiederholen. Wir hatten dazu mal nen Experiment in ner Cryptovorlesung, Helligkeitswerte übern abgeschotteten Lichtsensor eingelesen und dann auf die Werte geschaut, ob sich da was wiederholt. War interessant und sehr deutlich gar nicht zufällig.

[wanne]

Nun hat man in der Computerei aber folgendes Problem: Die meisten Definitionen von "Algorithmus" verlangen Determiniertheit. Und das steht in krassem Widerspruch dazu.

Gut das Computer Programme und keine Algorithmen ausführen.
Einfachstes Beispiel:

Code: Alles auswählen

while true; do echo hi; done

Ist nach Knuth kein Algorithmus. Mein Rechner kommt gut damit zurecht.

Andrerseits besteht ein ziemlich gut thermisch rauschender Generator aus einem einfachen Transistor (BE-Strecke "verpolt") und einem Widerstand, evtl. noch einem Auskoppel-Kondensator. Es wäre also nicht besonders aufwendig, es damit zu versuchen.

Ja. Über all wo du Quantenmechanische Effekte nutzt hast du sehr guten Zufall und vor allem "echten" und nicht nur unverstandene sich überlagernde Effekte wie bei analogen Quellen. Die Variante mit Kondensator ist wie man das auf entropiearmen Geräten unter Linux macht. Man schmeißt timer Interrupts an und misst die Zeit, die sie wirklich brauchen. Die Verteilung ist eben auch nicht bei weitem nicht gleichverteilt. Sondern hat verm. Poisson-Verteilt mit Peak über der Soll-Zeit. Nimmst du genug Werte kannst du dann so ein Konstrukt, wie ich es vorgeschlagen habe gleichverteilten Zufall erzeugen.

[eggy]

Nun hat man in der Computerei aber folgendes Problem: Die meisten Definitionen von "Algorithmus" verlangen Determiniertheit. Und das steht in krassem Widerspruch dazu.

Gut das Computer Programme und keine Algorithmen ausführen.
Einfachstes Beispiel:

Code: Alles auswählen

while true; do echo hi; done

Ist nach Knuth kein Algorithmus. Mein Rechner kommt gut damit zurecht.

Das ist nicht nur nach Knuth kein Algorithmus. Ein weiterer Punkt anerkannter Algorithmusdefinitionen ist die Finitheit. Dein Konstrukt kommt aus dem While-Teil nicht wieder raus. Ergo nix Algorithmus.

[cronoik]

OT:

Ein weiterer Punkt anerkannter Algorithmusdefinitionen ist die Finitheit. Dein Konstrukt kommt aus dem While-Teil nicht wieder raus. Ergo nix Algorithmus.

Das ist aber die Terminierung. Die Finitheit ist eine Eigenschaft die sich auf die Laenge der Beschreibung des bezieht. Ist diese nicht endlich, liegt keine Finitheit vor.

[eggy]

Ups. erstes Semester ... ist nen paar Tage her