Zufallszahlengenerator in Hardware?

[Plutos]

Heyhey,

sind die VIA C3 (und C7?) CPUs die einzigen, die echte (keine pseudo-) Zufallszahlen erzeugen können?

Was für Möglichkeiten gäbe es auf aktuellen PCs noch, ohne spezialisierte Hardware echte Zufallszahlen zu erzeugen (möglichst mit einem Output von 100Mbit/sec oder mehr)?

Edit: gibt es da mit Infineon TPM-Chips Möglichkeiten?

[da.phreak]

Beispielsweise so:

- schließe ein Radio an Deine Soundkarte an und stelle es auf einen unbenutzten Senderplatz ein. Das Atmosphärenrauschen ist zufällig, der aufgenommene Sound läßt sich entsprechend umrechnen. (siehe random.org (http://www.random.org/))
- Auch wurde schon mit Hilfe einer Webcam eine Lavalampe aufgenommen. Da der Zustand einer Lavalampe nicht vorhersagbar ist, lassen sich daraus Zufallszahlen generieren. Später hat man allerdings gemerkt, daß auch alleine das Rauschen der Kameraelektronik reicht

[Trap]

Was für Möglichkeiten gäbe es auf aktuellen PCs noch, ohne spezialisierte Hardware echte Zufallszahlen zu erzeugen (möglichst mit einem Output von 100Mbit/sec oder mehr)?
100 MBit/s ist ne Menge, da braucht man schon spezialisierte Hardware für.

Ein paar Intel Chipsätze haben auch einen Zufallszahlengenerator drin, aber die aktuellen wohl nicht mehr.

TPM-Module haben auch einen Zufallszahlengenerator drin.

[tatarus]

Ohne spezialisierte Hardware gibts keine Möglichkeit überhaupt wirkliche Zufallszahlen zu erzeugen. 100MBit/s als Bitfolge zufällig zu erzeugen ist mit normalen PCs nicht möglich. TPM Chips werden auch nur pseudo random Zahlen erzeugen und müssen dies auch nur für kurze Zahlenfolgen machen, um einen Schlüssel zu generieren.

Will man 100MBit/s+x als Zufallsfolge generieren (warum auch immer), dann benötigt man einen hochfrequentes Rauschen (im hohen GHz Bereich) und einen A/D Wandler, der das Rauschen immer nur 1Bit weise quantisiert und seriell ausgibt. Besser wäre natürlich ein FPGA mit integrierten Wandler, das den Bitsrom dann noch beliebig verändern kann.

[Trap]

TPM Chips werden auch nur pseudo random Zahlen erzeugen und müssen dies auch nur für kurze Zahlenfolgen machen, um einen Schlüssel zu generieren.
Das ist schon ein echter Zufallszahlengenerator, aber ich hab keine Ahnung wieviel Bit/s der erzeugen kann.

[Neomi]

Warum müssen es eigentlich "echte" Zufallszahlen sein? Der Mersenne Twister (die Generator-Referenz, wenn ich mich nicht irre) hat eine Periodenlänge von 2^19937-1 in der Standardkonfiguration, damit wirst du wohl niemals ein Muster erkennen können. Und 100 MBit/s sind locker drin.

[Plutos]

Warum müssen es eigentlich "echte" Zufallszahlen sein? Der Mersenne Twister (die Generator-Referenz, wenn ich mich nicht irre) hat eine Periodenlänge von 2^19937-1 in der Standardkonfiguration, damit wirst du wohl niemals ein Muster erkennen können. Und 100 MBit/s sind locker drin.

Es geht um verschiedene Tests mathematischer Modelle, und dazu brauche ich quasi "echte" Daten, also welche, die keinerlei analytisch erkennbares Muster aufweisen (da die Software darauf sehr empfindlich reagiert und unbrauchbare Ergebnisse produzieren könnte). Dieses Mersenne-Dingens werd' ich mir aber mal ansehen. Hohe Geschwindigkeit brauch' ich eigentlich nur, weil ich große Datenmengen brauche (sagen wir mal, größenordnungsmäßig 6- bis 10-stellige Zufallszahlen, und davon grob gesagt...mindestens eine Milliarde).

Ich werde mir auch mal anschauen, was mein TPM-Modul so kann. Dummerweise finde ich da von Infineon nicht wirklich viel Dokumentation.

[DaEmpty]

Warum müssen es eigentlich "echte" Zufallszahlen sein?
Das ist eine gute Frage. Normalerweise definiert man ja Zufallszahlen über ihre Eigenschaften. Quasi-Zufallswerte sollten eigentlich immer ausreichen.
Der Mersenne Twister (die Generator-Referenz, wenn ich mich nicht irre) hat eine Periodenlänge von 2^19937-1 in der Standardkonfiguration, damit wirst du wohl niemals ein Muster erkennen können. Und 100 MBit/s sind locker drin.
Referenz von der Periodenlänge her ja, aber Intel hat nicht umsonst dutzende Zufallsgeneratoren in ihrer Math Kernel Library. Der Mersenne Twister ist zwar auch als Basic Generator dabei, ist aber halt nicht immer die beste Wahl.

[Avalox]

Hier eine PCI Karte und ein USB Modul für Zufallszahlen.

http://www.idquantique.com/products/quantis.htm

[Plutos]

Hier eine PCI Karte und ein USB Modul für Zufallszahlen.

http://www.idquantique.com/products/quantis.htm

Sieht sehr interessant aus, leider würde das dazu führen, dass Teile der Software ohne diese Spezial-Hardware nicht mehr lauffähig wären.
Da momentan die einzige Vorraussetzung eine SSE2-fähige CPU ist (genauer gesagt, zwei davon), würde ich das gern möglichst lange beibehalten. Multi-Prozessor/-Core-System ist zwar schon eine etwas größere Einschränkung, aber übertreiben darf ich's mit den Hardware-Anforderungen noch nicht (TPM-Module wären hingegen in den fraglichen PCs verfügbar) ;).

[Frank]

Es geht um verschiedene Tests mathematischer Modelle, und dazu brauche ich quasi "echte" Daten, also welche, die keinerlei analytisch erkennbares Muster aufweisen (da die Software darauf sehr empfindlich reagiert und unbrauchbare Ergebnisse produzieren könnte).
Man kann problemlos Pseudozufallszahlen generieren, welche nicht als solche erkannt werden. Zu "meiner Zeit" war dafür der BBS Generator prädestiniert und erzeugte genauso wenig brechbare Ergebnisse wie RSA mit hinreichend großem Schlüssel.

[Mastermind@Glückskind]

Auch eine Zufallszahl kann zufällig ihrer Struktur nach alles andere als zufällig erscheinen!!!!!!!

[NiCoSt]

also....man könnte zufallszahlen noch etwas zufälliger machen, geht aber nur, wenn du ne Gausverteilung annimmst (was ja gelegentlich der fall ist). ein algorithmuss den ich mal benutzt habe:

Man Zeichnet einen Punkt auf die oberste Bildschrimzeile genau in die mitte. Dann Addiert man zur Zeilenkoordinate 1, sodass der Punkt weiter runter geht. Vorher wird jedoch eine Zufallszahl gebildet (kann ja jede programmiersprache, bei mir wars eine Zahl zwischen 0 und 1). ist die Zufallszahl im Raum 0 bis 0,5 wird für rechts entschieden, bei 0,5 geradeaus, bei 0,5 bis 1 links. Das wird immer wieder widerholt, bis der punkt am ende des Bildschrimes angekommen ist und eine chaotische Linie zurückgelegt hat. Der Endwert des Punktes wird mit dem Ausgangswert (also der Mitte) verglichen. Ist er rechts davon wird mit -1, genau da 0 und bei links mit 1 bewertet. es entsteht so eine recht zufällige abfolge die um 0 im Mittel schwankt.

[Spasstiger]

Warum reichen denn eigentlich Pseudozufallszahlen nicht aus?

Ich würde einfach die Zahlen mit einem 64-Bit-Generatorpolynom (x^64 + x^4 + x^3 + x + 1) erzeugen lassen und die auszuwählenden Binärstellen mit 32 Zahlen aus einem 6-Bit-Generatorpolyonom. Als Startwerte nimmt man einfach Werte vom Timer.

Dann erhält man 32-Bit-Pseudo-Zufallszahlen, die sehr gut gleichverteilt sind und sich auch nicht zyklisch wiederholen (zumindest nicht bei "nur" 1 Milliarde Zufallszahlen, die erzeugt werden sollen).

Das ganze sollte auch mit einem 32-Bit-Generatorpolynom und einem 5-Bit-Polynom zur Auswahl der Binärstellen schon ganz gut funktionieren.

[Plutos]

Man kann problemlos Pseudozufallszahlen generieren, welche nicht als solche erkannt werden. Zu "meiner Zeit" war dafür der BBS Generator prädestiniert und erzeugte genauso wenig brechbare Ergebnisse wie RSA mit hinreichend großem Schlüssel.

Wenn es so "problemlos" wäre, dann gäbe es dieses ganze Dilemma doch gar nicht, oder? Pseudozufallszahlen, die nicht als solche erkannt werden, würden sich ja per definitionem nicht von echten Zufallszahlen unterscheiden.
Seit ich weiß, was die Abkürzung "BBS" in diesem Zusammenhang bedeutet, kann ich den BBS-Generator leider nicht mehr Ernst nehmen ;). Nein, Quatsch, aber für einen Lachflash war das schon gut :smile:.

also....man könnte zufallszahlen noch etwas zufälliger machen, geht aber nur, wenn du ne Gausverteilung annimmst (was ja gelegentlich der fall ist). ein algorithmuss den ich mal benutzt habe:

Man Zeichnet einen Punkt auf die oberste Bildschrimzeile genau in die mitte. Dann Addiert man zur Zeilenkoordinate 1, sodass der Punkt weiter runter geht. Vorher wird jedoch eine Zufallszahl gebildet (kann ja jede programmiersprache, bei mir wars eine Zahl zwischen 0 und 1). ist die Zufallszahl im Raum 0 bis 0,5 wird für rechts entschieden, bei 0,5 geradeaus, bei 0,5 bis 1 links. Das wird immer wieder widerholt, bis der punkt am ende des Bildschrimes angekommen ist und eine chaotische Linie zurückgelegt hat. Der Endwert des Punktes wird mit dem Ausgangswert (also der Mitte) verglichen. Ist er rechts davon wird mit -1, genau da 0 und bei links mit 1 bewertet. es entsteht so eine recht zufällige abfolge die um 0 im Mittel schwankt.

Wobei der Zufall hier ja auch - dadurch, dass die Verschiebung eben durch eine Pseudozufallszahl festgelegt wird - durch den Zufallszahlengenerator der verwendeten Programmiersprache "begrenzt" wird. Software kann nunmal nur Pseudo-Zufall bieten ;).

Ich werde mir nun nichtsdestotrotz mal anschauen, wie weit ich mit Pseudo-Zufall komme. Das erfordert zwar ein bisschen mehr Denk-, aber wesentlich weniger Technik-Aufwand ;).

[Frank]

Seit ich weiß, was die Abkürzung "BBS" in diesem Zusammenhang bedeutet, kann ich den BBS-Generator leider nicht mehr Ernst nehmen ;). Gut ... dann nimmst Du also konsequenterweise auch RSA nicht ernst. Ist zwar mittlerweile oldfashioned aber unter normalen Bedingungen aktuell auch nicht in endlich vertretbarer Zeit brechbar.

[Neomi]

Gut ... dann nimmst Du also konsequenterweise auch RSA nicht ernst. Ist zwar mittlerweile oldfashioned aber unter normalen Bedingungen aktuell auch nicht in endlich vertretbarer Zeit brechbar.

Ich glaube, es ging ihm dabei nicht um die Funktionsweise, sondern alleine um den Namen (Blum Blum Shub).

[Shink]

Warum reichen denn eigentlich Pseudozufallszahlen nicht aus?

Weil Pseudozufallszahlen "per Definition" nicht zufällig sind?
Alle Generatoren haben so ihre Macken, sonst würde es nicht so viele davon geben.

Wenn die verwendeten Generatoren eine Eigenschaft haben, die sich schwer nachvollziehen lässt aber genau bei Unus Problem zu einem falschen Ergebnis führen wär das ja auch öde.

Außerdem benötigt man ja durchaus Performance für son Zeug.

[Monger]

Dann erhält man 32-Bit-Pseudo-Zufallszahlen, die sehr gut gleichverteilt sind und sich auch nicht zyklisch wiederholen (zumindest nicht bei "nur" 1 Milliarde Zufallszahlen, die erzeugt werden sollen).

Echte Zufallszahlen sind nicht gleichverteilt.


Aber im Prinzip stimme ich dir zu. Ich kann mir grad nicht vorstellen, wozu man denn unbedingt echte Zufallszahlen braucht.

[Spasstiger]

Echte Zufallszahlen sind nicht gleichverteilt.
Echte Zufallszahlen können auch gleichverteilt sein und umgangssprachlich geht man immer von Gleichverteilung aus (siehe z.B. Würfel). Unu hat sich dazu nicht näher geäußert.
Klar, wenn man Zufallszahlen aus einem Bauteilrauschen gewinnt, sind die Zahlen gaußverteilt.

[NiCoSt]

vielleicht solltest du mal sagen, was genau du für zufallszahlen brauchst.

brauchst du ne reihe 0,1 (also 010100000101010010101111010100) oder fließkommazahlen von 0 bis 1 oder ganzzahlige zahlen von 0 bis 100.... ??

[Coda]

Echte Zufallszahlen sind nicht gleichverteilt.
Ich weiß es jetzt nicht besser, aber warum ist das so? Intuitiv würde ich das annehmen.

brauchst du ne reihe 0,1 (also 010100000101010010101111010100) oder fließkommazahlen von 0 bis 1 oder ganzzahlige zahlen von 0 bis 100.... ??
Im Endeffekt macht das keinen Unterscheid weil alles aus ersterem generiert wird in der Praxis.

[#44]

Ich weiß es jetzt nicht besser, aber warum ist das so? Intuitiv würde ich das annehmen.

Eine (regemäßig auftretende) Gleichverteilung (bei z.B. 1Mio Zufallszahlen pro Durchlauf) setzt ja eine Abhängigkeit von den vorherigen Ergebnissen voraus. Ebendies ist ja bei einem absoluten Zufall auszuschließen. Die Verteilung ist Zufällig => Eine Gleichverteilung kann also auch nur zufällig auftreten...

[Coda]

Nö, eben nicht.
http://de.wikipedia.org/wiki/Gleichverteilung

"Der Begriff Gleichverteilung stammt aus der Wahrscheinlichkeitsrechnung und beschreibt eine Wahrscheinlichkeitsverteilung, wobei im diskreten Fall jeder mögliche Zustand mit der gleichen Wahrscheinlichkeit eintritt."

Da bei einem echten Zufallsgenerator 1 und 0 mit gleicher Wahrscheinlichkeit auftreten ist, ist die Ausgabe auch gleichverteilt.

[Plutos]

Gut ... dann nimmst Du also konsequenterweise auch RSA nicht ernst. Ist zwar mittlerweile oldfashioned aber unter normalen Bedingungen aktuell auch nicht in endlich vertretbarer Zeit brechbar.

Mir ging es wirklich nur um den lustig klingenden Namen ;) (ich weiß, ich bin kindisch).

vielleicht solltest du mal sagen, was genau du für zufallszahlen brauchst.

brauchst du ne reihe 0,1 (also 010100000101010010101111010100) oder fließkommazahlen von 0 bis 1 oder ganzzahlige zahlen von 0 bis 100.... ??

Das ist mir eigentlich völlig egal, wie schon gesagt kann man sich ja aus 1) alles herstellen.

Worum geht es denn jetzt? Es geht um eine Software, die (unter anderem) bestimmte Muster in (sehr großen) Zahlenmengen erkennt. Das klingt jetzt sehr allgemein, ist es letztendlich auch, es handelt sich nicht um eine konkrete Anwendung (Gesichts-Erkennung, Iris-Scan, Aktienkurs-Prognose oder was man daraus alles basteln könnte), sondern um wissenschaftliche Forschung auf diesem Gebiet.

Ich möchte nicht anmaßend klingend, aber da die Software diesbezüglich durchaus sehr intelligent arbeitet und - ausreichend große Datenmengen vorrausgesetzt - auch äußert komplexe Muster erkennt, habe ich einfach Bedenken, dass Pseudo-Zufallszahlen noch zu regelmäßig sind. Gerade bei den großen Datenmengen, die wir später damit analysieren wollen, halte ich es für zu wahrscheinlich, dass selbst in Pseudo-Zufallszahlen ein numerisch erkennbares Muster steckt.
Ganz trivial in diesem Zusammenhang wäre bspw. ein Pseudo-Zufallszahlengenerator, der keine einzige Zahl aus einem Intervall zweimal bringt, solange nicht jede Zahl aus diesem Intervall mindestens ein einziges mal "zufällig" erschienen ist. Iirc war das damals bei der Programmiersprache Basic z.B. der Fall.
Sicher hat man in gewissen Grenzen Spielraum, dennoch sollte die Software in der Lage sein, tatsächliche, wiederkehrende Muster von "echtem" Zufall zu unterscheiden. Es ist mir durchaus klar, dass das auch ein Problem der Statistik ist, um die Software u.a. auf ihre tatsächliche Leistungsfähigkeit hin zu testen, würde ich trotzdem sehr gerne mal mit echten Zufallszahlen "spielen".

Mögliche Anwendungen habe ich oben schon genannt, dabei geht es uns bei unserer Forschung in diesem Bereich momentan allerdings (noch) nicht.

[Coda]

Vielleicht hilft das ja weiter:

http://www.fourmilab.ch/random/

[Monger]

Ich weiß es jetzt nicht besser, aber warum ist das so? Intuitiv würde ich das annehmen.

Ich kann dir leider nur das sagen, was mein Mathe Dozent mal gesagt hat, der war nämlich Statistiker. Nach ihm ist es eher verdächtig, wenn sich Zahlen allzu regelmäßig streuen.

Simpelstes Beispiel: eine Explosion. Eigentlich sollte man ja annehmen, dass eine in alle Richtungen gleichmäßig gerichtete Kraft auch eine gleichmäßige Verteilung mit sich bringt. Das Gegenteil ist aber der Fall: die Explosion konzentriert sich in bestimmten Gebieten, in anderen Regionen bleibt sie dagegen fast völlig aus.

Das sieht man auch am Universum: nach aktuellem Kenntnisstand sind die drei Dimensionen nahezu perfekt symmetrisch in ihrer Ausdehnung. Eigentlich müsste sich die Masse einigermaßen regelmäßig im Universum verteilt haben, aber in Wahrheit ballt sie sich in einigen Regionen irrsinnig, während sie in anderen Regionen völlig abwesend ist.

Wenn du also bei 600 Würfelwürfen tatsächlich ziemlich genau 100mal jede Zahl bekommst, ist das schon verdächtig zu gleichmäßig für eine Gleichverteilung. Mein Dozent hat dann auch irgendwas davon erzählt wie man diese Störungen mathematisch erfasst, und dass die durchaus in einer Gleichverteilung auch erwartet werden, aber das kriege ich jetzt nicht mehr zusammen.

[Coda]

Ich kann dir leider nur das sagen, was mein Mathe Dozent mal gesagt hat, der war nämlich Statistiker. Nach ihm ist es eher verdächtig, wenn sich Zahlen allzu regelmäßig streuen.
Natürlich sind echte Zufallszahlen nicht gleichmäßig verteilt wenn man sagen wir 10000 diskrete Zahlen zwischen 1-10000 erzeugt.
Das ist aber nicht die Definition von Gleichverteilung. Gleichverteilung heißt so viel wie "wenn man unendlich viele Zahlen erzeugen würde, wäre es gleichmäßig verteilt".

Deine Beispiele sind übrigens nicht sehr gut. Die Materie im Universum war kurz nach dem Urknall wirklich ziemlich homogen. Das waren ultrakleine Schwankungen die nachher natürlich nach Mrd. von Jahren zu Ballungen geführt haben.

[Spasstiger]

Eine (regemäßig auftretende) Gleichverteilung (bei z.B. 1Mio Zufallszahlen pro Durchlauf) setzt ja eine Abhängigkeit von den vorherigen Ergebnissen voraus.
Wie kommst du darauf? Nimm einen Würfel, dieser liefert gleichverteilte Zufallswerte egal was vorher gewürfelt wurde.

[Asmodeus]

Wie kommst du darauf? Nimm einen Würfel, dieser liefert gleichverteilte Zufallswerte egal was vorher gewürfelt wurde.
Bei unendlich vielen Würfen ja. Bei z.b. nur 1000 Würfen liefert Dir ein echter Zufallszahlengenerator meistens keine Gleichverteilung, ein Quasi-Zufallszahlengenerator aber schon.

Gruß, Carsten.

[Coda]

Nein. Das ist wäre "gleichmäßig verteilt" != "Gleichverteilung".

Der Begriff Gleichverteilung stammt aus der Wahrscheinlichkeitsrechnung und beschreibt eine Wahrscheinlichkeitsverteilung, wobei im diskreten Fall jeder mögliche Zustand mit der gleichen Wahrscheinlichkeit eintritt. Im stetigen Fall betrifft es eine Verteilung mit konstanter Dichte. Der Grundgedanke einer Gleichverteilung ist, dass es keine Präferenz gibt.

[Spasstiger]

Bei z.b. nur 1000 Würfen liefert Dir ein echter Zufallszahlengenerator meistens keine Gleichverteilung, ein Quasi-Zufallszahlengenerator aber schon.
Wenn man z.B. 1200 mal würfelt, wird im Normalfall weder der reale Würfel noch der Pseudo-Zufallszahlengenerator eine gleichmäßige Verteilung, d.h. jeweils 200-mal die gleiche Augenzahl liefern (von Gleichverteilung im mathematischen Sinne sollte man bei einer endlichen Zahl von Zufallsexperimenten sowieso nicht sprechen).
Schon mit einem einzigen 32-Bit-Generatorpolynom wird man bei 1200 simulierten Würfen über tausende Runden hinweg eine andere Verteilung erhalten, wenn man den Startwert z.B. aus einem Timer gewinnt.

EDIT: Ich hab mal eben einen Pseudozufallszahlengenerator für das Werfen eines Würfels geschrieben als kleine Assembler-Programmierübung (für den 16-Bit-CISC, den wir an der Uni in VHDL entworfen haben). Das Programm verwendet zwei 16-Bit-Generatoren in Form linear rückgekoppelter Schieberegister, wovon eines zur Auswahl der Binärstellen aus dem anderen Generator dient. Die Startwerte habe ich beliebig gewählt und könnte man dem Timer entnehmen.
Bei 48000 Zufallszahlen sieht die Verteilung so aus:
1: 8053
2: 7957
3: 8122
4: 8069
5: 8095
6: 7960

Bei anderen Startwerten kommt folgende Verteilung raus:
1: 8089
2: 8057
3: 7757
4: 8014
5: 7954
6: 8129

Die Zahlen sind also jeweils nahe an den 8000 dran, die bei 48.000 Würfen zu erwarten wären, aber eben nicht genau gleich 8000.
Trotzdem handelt es sich um einen Pseudozufallszahlengenerator, welcher eine Gleichverteilung im mathematischen Sinne liefert.