True Random

  • Schrift vergrößern
  • Standard-Schriftgröße
  • Schriftgröße verkleinern

Startseite Deutsch

 

Einleitung                                                                                             zwei Würfel

Echte physikalische Zufallszahlengeneratoren produzieren Zufallszahlen aus echt zufälligen Prozessen wie dem Fallen eines Spielwürfels oder dem Rauschen eines Widerstandes oder Oszillators. Die echte, also nicht vorgetäuschte, Zufälligkeit dieser Zahlen, ist die Grundlage vieler kryptografischer Verfahren beispielsweise zum Erzeugen von PINs, TANs und kryptographischen Schlüsseln. Sie eignet sich aber auch für andere Anwendungen wie stochastische Resonanz, genetische Algorithmen, Monte-Carlo-Simulationen, Surrogatdaten-Methode, Erzeugen von Lotto-Zahlen und viele weitere.

Häufig problematisch, sowohl bei echten wie unechten Zufallszahlengeneratoren, sind statistische Auffälligkeiten, die teilweise durch die Entropie (mittlere Zufälligkeit einer einzelnen Zufallszahl) charakterisiert werden können. Die Entropie der Informationstheorie sagt aber nur sehr wenig über Zufallszahlen aus, weil sie nur die einzelnen Wahrscheinlichkeiten der Zufallszahlen berücksichtigt; bedingte Wahrscheinlichkeiten und anderes bleibt unberücksichtigt. Zudem ist die Entropie nicht invariant gegenüber einer Basistransformation und so kann die bitweise Entropie einen ganz anderen Wert haben als die byteweise Entropie. Dies ist der Grund, weshalb es viele verschiedene Entropie-Tests gibt und es genau genommen nicht eine sondern viele informationstheoretische Entropien gibt.

Die statistischen Auffälligkeiten können drastische Konsequenzen haben. Zitat aus einem Lehrbuch:

"If all scientific paper whose results are in doubt because of bad rand()s were to disappear from library shelves, there would be a gap on each shelf about as big as your fist."

Numerical Recipes (in C), Chapter 7.1


Ein weiteres Problem ist die Bestimmung des Grads der Nicht-Berechenbarkeit/Nicht-Vorhersagbarkeit der Zufallszahlen, also deren echte Zufälligkeit, auch wirkliche Zufälligkeit oder der Grad der Nichtdeterminiertheit genannt.
Da ein physikalischer Zufallszahlengenerator ein stochastischer Automat mit endlichem Gedächtnis ist, kann dessen echte Zufälligkeit mit der Theorie der Markow-Ketten berechnet werden. Die echte Zufälligkeit, genauer die mittlere Zufälligkeit einer Zufallszahl von einem stochastischen Automaten, heisst in dieser Theorie Entropiebelag. Im Gegensatz zur Entropie werden hier bedingte Wahrscheinlichkeiten berücksichtigt und der Wert is unabhängig von Basistransformationen.
Nach der Theorie hat ein stochastischer Automat mit einer Gedächtnislänge von m genau n^m (n hoch m) innere Zustände, wobei n die Anzahl der möglichen Zufallszahlen ist. Die Gedächtnislänge m bedeutet, dass eine Zufallszahl allgemein von den m vorher produzierten abhängt.
Ein Beispiel: (2^(16))^(1000) = 3,02E4816 bei einem 16-Bit Zufallszahlengenerator mit einer Gedächtnisslänge von m=1000. Durch diese riesige Anzahl an Zuständen und eine noch grössere Anzahl an Zustandsübergangs-Wahrscheinlichkeiten ist der Entropie-Belag im Allgemeinen aber nur theoretisch berechenbar. Zudem müssen vor der Berechnung der Entropie erstmal die benötigten Pameter ermittelt werden, also sowohl die ergodischen Wahrscheinlichkeiten der Zustände als auch alle Übergangswahrscheinlichkeiten. Hinzu kommen natürlich die üblichen Voraussetzungen, also Unabhängigkeit von äusseren Einflüssen wie Temperatur, Druck usw. bei allen zulässigen Betriebs-Parametern. Durch die Bellsche Ungleichung braucht man sich um verborgene lokale Paramter hierbei nicht zu kümmern.
Der aufgrund der riesigen Anzahl an Zuständen und Zustandsübergangswahrscheinlichkeiten praktisch nicht zu bewältigende Rechenaufwand ist der einzige Grund, weshalb physikalische Zufallszahlengenertoren getestet werden, denn theoretisch können deren Eigenschaften komplett berechnet werden.
Dass der Entropiebelag praktisch nicht berechnet werden kann, ist auch der Grund weshalb echte Zufallszahlen häufig rein deterministisch nachbearbeitet werden. Eine rein deterministische Nachbearbeitung wie ein exklusiv-verodern mit Pseudozufallszahlen (so genannter XOR-Modus) ändert zwar nichts am Entropie-Belag, erhöht aber (meistens) die Entropie. Für kryptografische Anwendungen sind solche Nachbearbeitungen daher sinnlos und sollten immer vermieden werden, da sie Schwächen der Hardware nur verbergen, aber nicht ausgleichen können. Hierdurch können sie den Anwender in falscher Sicherheit wiegen, da sie die Zufallszahlen zufälliger erscheinen lassen, als sie es wirklich sind.

Da der Entropiebelag praktisch nicht bestimmt werden kann, sind in der Praxis nur Tests möglich wie ein Entropie-Test oder die Diehard-Tests und vereinfachende Angaben wie eine Entropie.
Es gibt aber Spezialfälle, in denen eine Entropie und der Entropie-Belag auch real berechenbar sind. Ein Beispiel sind Pseudo-Zufallszahlengeneratoren, denn sie haben N innere Zustände und alle Zustandsübergangswahrscheinlichkeiten sind entweder 0 oder 1. Hierdurch ist der Term p*ld(p) in der Definitions-Formel des Entropiebelags und damit auch der gesamte Entropie-Belag immer exakt gleich null.
Wie man an der einfachen Definitions-Formel für die Entropie sieht, ist die Entropie ebenfalls null dann, und nur genau dann, wenn als Zufallszahlen solche gewählt werden, die (von der Breite her) einem ganzzahligen Vielfachen der Periodenlänge P des Generators entsprechen. Hierfür muss die Periodenlänge des Pseudozufallszahlengenerators endlich sein, denn ansonsten, also bei unendlicher Periodenlänge, wäre die Entropie immer, also auch bei nichtdeterministischen Zufallszahlengeneratoren exakt gleich null.
Bei Pseudozufallszahlengenratoren mit unendlicher Periodenlänge, beispielsweise eine algorithmische Zufalls-Sequenz wie die Nachkommastellen einer normalen Zahl wie der Champernowne-Konstanten, sind die Entropien daher (nahezu) eins, weil sozusagen jede neue berechnete Nachkommastelle eine Überraschung ist (da sie vor der Berechnung unbekannt ist), während der Entropiebelag auch dort null ist, weil ja jede Nachkommastelle feststeht, unabhängig davon ob sie jemand berechnet oder nicht.

Anschaulich bedeutet der Wert 0 des Entropie-Belags, das Pseudozufallszahlengeneratoren keine echte Zufälligkeit (Nichtdeterminiertheit) haben, auch wenn sie unendlich viel Information (bzw. Desinformation) enthalten.

In der Praxis sieht man aber häufig, dass zwischen Pseudozufall, also scheinbarem Zufall und echtem Zufall (Nichtdeterminiertheit) nicht unterschieden wird und daher mit Entropie das bezeichnet wird, was genau genommen der Entropiebelag ist. Dadruch wird beim Zufall nicht zwischen Schein und Sein unterschieden.

Generell ist es so, dass die physikalischen Zustände eines Zufallszahlengenerators nicht genau den Markow-Zuständen entsprechen, aber die physikalischen Zustände können mit Markow-Zuständen approximiert werden und mit dem Grenzübergang m gegen unendlich geht dies beliebig genau. Dadurch ist jeder Zufallszahlengenerator ein Markow-Prozess und mit der Theorie der Markow-Ketten beschreibbar.

Die Nicht-Berechenbarkeit ist das Kriterium der informationstheoretischen Sicherheit der Zufallszahlen und wichtig, beispielsweise um zu verhindern, dass jemand eine TAN-Liste berechnen oder mit hoher Wahrscheinlichkeit erraten kann, selbst wenn dieser Jemand alle vorherigen TAN-Listen kennt (z. B. aus dem Altpapier-Container).
Hierzu ein weiteres Zitat:

"There is a DEFINITE NEED FOR DATA WITH ENTROPY NOT BASED ON ALGORITHMS. As to whether we need *true* random numbers, that's a subject for debate. Typically we get data that's as good as we need it to be from a hardware generator by running the initial data (which may have some kind of pattern or bias) through an algorithm which sort of mixes it. But it is very usefull to have this entropy come from a hardware device, because it affords an EXTRA LEVEL OF SECURITY; pseudorandom numbers can be compromised if the algorithm is known and the seed is discovered, but THERE IS NO SUCH EQUIVALENT FOR RANDOM NUMBERS GENERATED BY A HARDWARE DEVICE."

Moses Liskov (faq-editor@rsa.com), http://www.rsa.com/ , year 2000


Zur Lösung dieser beiden Probleme, also zum Produzieren von Zufallszahlen ohne statistische Auffälligkeiten und mit viel Entropie sowie Entropiebelag, wurden die unten beschriebenen Zufallszahlengeneratoren entwickelt.
Es gibt zwar schon lange quasi kostenlose echte Zufallszahlengeneratoren, beispielsweise /dev/random (der physikalische Standards-Zufallszahlengenerator unter Linux und anderen Unix-Derivaten), die ebenfalls Zufallszahlen hoher Qualität produzieren, aber nur eine Geschwindigkeit von ungefähr 2 Byte pro Sekunde haben und damit millionenfach langsamer sind als die unten beschriebenen Generatoren.

Als Tests wurden neben FIPS-, AIS-, NIST- und speziellen Tests, u. A. mit einem Hardware-Spektrum-Analysator, überwiegend die Diehard-Tests verwendet, weil sie meist viel härter und vielseitiger sind als die anderen Tests.


 

1. Generation (Nachbearbeitung der Zufallszahlen erforderlich)

Die Generatoren der ersten Generation erzeugen Zufallszahlen ganz einfach durch digitales Rauschen. Hierzu werden Hazards von digitalen Schaltungen genommen und ausgegeben. Zum Abschirmen äusserer Störeinflüsse werden geschlossene Hochfrequenz-dichte Eisen-Gehäuse verwendet. Die Qualität dieser Zufallzahlen reicht ohne Nachbearbeitungen wie Bit-Vertauschungen, Invertierungen usw. meist nicht aus um alle statistischen Tests zu bestehen. Diese Nachbearbeitung wird daher von den Treibern vorgenommen, so wie beispielsweise bei /dev/random, das der physikalische Standard-Zufallszahlengenerator unter Linux und anderen Unix-Derivaten ist.


rp1: schneller echter Zufallszahlengenerator für den Parallelport rp1 ist ein echter Zufallszahlengenerator für den Parallelport, der echte physikalische 5-Bit-Zufallszahlen produziert und auf Hazards basiert.
Er ist geeignet für Hot Swap und mit weniger als 0,1 Watt Verbrauch sehr stromsparend. Das Gerät wird vom Parallelport versorgt und hat deshalb weder Kabel noch Batterien.

  • Geschwindigkeit: 2 MByte/s (der Parallelport kann nur rd. 1 MByte/s auslesen)
  • Abmessungen: 6 x 5 x 1,5 cm
  • Gewicht: 55 g


Die mit dem zugehörigen Treiber generierten Zufallsbitdateien enthalten keine signifikanten Korrelationen und bestehen auch die 15 Diehard-Tests.

 

Referenzkunden: iPei



rw1: schneller echter Zufallszahlengenerator (16Bit) der ersten Generation rw1 ist eine ISA-Karte und echter Zufallszahlengenerator, der physikalische 16-Bit-Zufallszahlen produziert und auf Hazards basiert.

  • Geschwindigkeit: 16,67 MByte/s (der ISA-Bus nur ca. 2 MByte/s auslesen)
  • Abmessungen (inkl. Slot-Blech): 18 x 12 x 2 cm
  • Gewicht: 200 g


Die mit dem zugehörigen Treiber generierten Zufallsbitdateien enthalten keine signifikanten Korrelationen und bestehen auch die 15 Diehard-Tests.
Diese Karte ist geeignet für Hot Swap.


 

2. Generation ( perfekte Zufallszahlengeneratoren )

Die Zufallszahlengeneratoren der zweiten Generation sind entwickelt worden aus denen der ersten Generation und dem zentralen Grenzwertsatz. Eine ausführliche Beschreibung, die im Wesentlichen ein Kapitel aus meiner Doktorarbeit ist, gibt es hier.
Kurz gesagt kann mit dem zentralen Grenzwertsatz gezeigt werden, dass durch die Modulo-Addition von ausreichend vielen echten Zufallszahlen die Gedächtnis-Länge m des Markow-Prozesses des Zufallszahlengenerators effektiv auf eins reduziert wird und die Übergangswarscheinlichkeiten zwischen den inneren Zuständen des Markow-Prozesses des Zufallszahlengenerators angeglichen werden. Dies bedeutet, dass sowohl die Entropien als auch der Entropie-Belag den theoretischen Maximal-Wert von 1 Bit je Bit annehmen. Hierfür ist nur nachzuweisen, dass ausreichend viele primäre Zufallszahlen verwendet werden, also dass die Lindebergsche Bedingung erfüllt ist.

Der Haupvorteil dieser Technick ist, dass pro Taktzyklus eine echte Zufallszahl produziert wird, die nicht nachbearbeitet werden muss, weil die Zufallszahlenfolgen sowohl theoretisch als auch praktisch auch unbearbeitet alle Tests wie z. B. die 15 Diehard-Tests bestehen. Zudem ist keine Abschirmung nötig und die langsamsten Generatoren hier sind gut acht Millionen mal schneller als /dev/random, das der physikalische Standard-Zufallszahlengenerator unter Linux und anderen Unix-Derivaten ist.

Diese mathematisch beweisbar korrekte Technik ist patentiert (deutsches Patent Nr. 199 26 640) und macht diese Zufallszahlengeneratoren weltweit einzigartig.
Um deutlich zu zeigen, dass die Treiber die Zufallszahlen NICHT bearbeiten ist die Software vollständig open-source. Da keine Nachbearbeitung nötig ist, können die Generatoren auch völlig ohne Software verwendet werden. Aus diesem Grund haben einige Generatoren (rw2) einen Mono- und zwei Stereo-Ausgänge mit den Zufallsbits, die beispielsweise als perfekt weisses Rauschen für Audio-Messungen oder zum Schalten eines Lasers für Kreuzkorrelations-Messungen verwendet werden können.

Dass diese Generatoren auch in der Klimakammer bei -10...+60°C alle Zufallszahlen-Tests bestehen und auch für sichherheitskritische kryptografische Anwendungen geeignet sind, konnten Firmen wie Kryptografics bestätigen.

Diese Generatoren sind optimiert für a) autonomen Betrieb, b) harte Echtzeit und c) sehr hohe Qualität bei hohen Geschwindigkeiten.
Dadurch können diese Generatoren auch für Rauschradar, Tarnkappenradar, als Störsender und als Zufalls-Taktgenerator (mit diskret exponentialverteilter Periodendauer) verwendet werden.


rw2: schneller echter Zufallszahlengenerator (16Bit) der zweiten Generation rw2 ist eine ISA-Karte und echter Zufallszahlengenerator, der physikalische 16-Bit-Zufallszahlen produziert und auf dem zentralen Grenzwertsatz basiert.
Die Karte produziert echte Zufallszahlen mit mehr als 16 MByte/s und gibt sie auch als digitales Rauschen (Folge zufälliger und unabhängiger Bits, weisses Rauschen mit der Grenzfrequenz Taktfrequenz/4) mit der Taktfrequenz (0..8,33 MHz) auch über eine BNC-Buchse aus.
Diese Karte besitzt neben einem Stereo-Ausgang (mit 2*0..4,17 MHz) drei Kontroll-LEDs (Versorgungsspannung, Takt, BNC-Ausgang) und kann auch ohne ISA-Bus betrieben werden, denn sie benötigt neben 5V Versorgungsspannung nur einen Takt.

  • Geschwindigkeit (ohne Übertakten): 16,67 MByte/s (der ISA-Bus nur ca. 2 MByte/s auslesen)
  • Abmessungen (inkl. Slot-Blech): 18 x 12 x 2 cm
  • Stromversorgung: 5V/0,75A
  • Gewicht: 250 g


Diese Karte ist geeignet für Hot Swap.

 

Referenzkunden: Kryptographics




rw3: schneller echter Zufallszahlengenerator (32Bit) der zweiten Generation rw3 ist eine PCI-Karte und echter Zufallszahlengenerator, der physikalische 16-Bit-Zufallszahlen produziert und auf dem zentralen Grenzwertsatz basiert.
Sie ist einer der schnellsten echte Zufallszahlengeneratoren der Welt, bei dem eine Nachbearbeitung der Zufallszahlen nicht nötig ist.
Diese Karte ist geeignet für Hot Swap und basiert auf der PROTO-3, zu der es reichlich Dokumentation und Software gibt.

  • Geschwindigkeit: 80 MByte/s (der PCI-Bus kann nur ca. 5 MByte/s auslesen)
  • Abmessungen (inkl. Slot-Blech): 23 x 12 x 2 cm
  • Gewicht: 330 g
Referenzkunden: Telekom




rw4: schneller echter Zufallszahlengenerator (32Bit) der zweiten Generation rw4 ist eine PCI-Karte und echter Zufallszahlengenerator, der physikalische 32-Bit-Zufallszahlen produziert und auf dem zentralen Grenzwertsatz basiert.
Sie ist der derzeit weltweit schnellste echte Zufallszahlengenerator, bei dem eine Nachbearbeitung der Zufallszahlen nicht nötig ist.
Diese Karte ist geeignet für Hot Swap und basiert auf der PCI-Proto Lab/PLX, zu der es reichlich Dokumentation und Software gibt.

  • Geschwindigkeit: 160 MByte/s (interne Datenrate, der PCI-Bus kann ohne DMA nur ca. 10 MByte/s auslesen)
  • Abmessungen (inkl. Slot-Blech): 32 x 12 x 2 cm
  • Gewicht: 450 g

 

Referenzkunden: Kryptographics




rw3usb: schneller echter Zufallszahlengenerator der zweiten Generation rw3usb: schneller echter Zufallszahlengenerator der zweiten Generation RW3USB ist ein echter Zufallszahlengenerator für den USB-Bus.
Die Grund-Version hat einen USB-Anschluss sowohl zur Stromversorgung als auch zum Datenaustausch. Die Premium-Versionen haben auch einen Parallelport-Anschluss, einen Stereo-Ausgang oder eine batteriegepufferte Echtzeituhr.
Der Parallelport-Anschluss ist zur Datenübertragung in harter Echtzeit, für Latenzzeiten unter 10 Mikrosekunden. Die über die Stereo-Buchse mit rund 200 kHz ausgegebenen beiden Zufallsbitströme können direkt verwendet werden als zweikanaliges weisses Rauschen oder Zufalls-Takte mit diskret exponentialverteilter Periodendauer.

  • Geschwindigkeit: 1,5 MBit/s
  • Abmessungen (ohne Kabel): 8 x 5,5 x 2,5 cm
  • Stromversorgung: Über den USB-Bus (5V/0,3A)
  • Gewicht (ohne Kabel): 150 g

Weitere Features:
Moderner Mikrocontroller (MSP430) mit updatefähiger Firmware und internem Temperatursensor.
Moderner FTDI USB-Controller.
128 MB frei verfügbarer Flash-Speicher (optional auch mehr).
Ausführlich dokumentierte Schnittstellen.
Viel Open Source-Software, für MS-Win, Linux und auch für harte Echtzeit (RTAI).
Die Datenübertragung über USB ist mit einer Prüfsumme abgesichert; diejenige über den Parallelport ist mit einem Paritätsbit abgesichert.
Selbsttest der Hardware und ausführlicher Selbsttest des Zufallszahlengenerators nach FIPS und AIS.
Erfüllt die Anforderungen nach CE, FIPS 140-1, FIS 140-2, AIS 31, usw..
Robustes und stabiles sowie HF-dichtes Eisen-Gehäuse.
Verschiedene Modi, beispielsweise interruptfreier Modus für geringste Latenzzeit im harten Echtzeit-Betrieb.

 



Links

Ein zugehöriger uni ulm intern - Artikel vom November 1999 hier.

Ein Artikel zur ersten Generation meiner Zufallszahlengeneratoren hier.

Wenn der Zufallszahlengenerator /dev/random nicht schnell genug ist und die obigen Generatoren zu schnell sind (oder zu teuer, oder ...) kann man auch den freien ALSA sound card related Entropy Gathering Daemon (EGD) randomsound verwenden um /dev/random um ca. den Faktor 100 schneller zu machen: http://packages.debian.org/de/sid/admin/randomsound
http://v2.www.rpmseek.com/rpm-pl/randomsound.html?hl=de&cx=857:R:0.
Dafür reicht schon der onboard-Sound oder eine kleine USB-Soundkarte für 4 Euro.
Eine ähnliche Alternative ist der EGD RandD.
Eine weitere Alternative sind die rng-tools ( http://www.kernel.org/doc/Documentation/hw_random.txt).

c't-RandCam & Co - Programme zur Erzeugung von Zufallszahlen.

Dieharder: A (new) Random Number Test Suite.

TestU01 - Empirical Testing of Random Number Generators.

NIST Test Suite

FIPS 140 Standard

AIS 20 und AIS 31 zur Evaluation von deterministischen (AIS 20) und nichtdeterministischen (AIS 31) Zufallszahlengeneratoren:

L'Ecuyer's Test Suite (auch Psudozufallszahlengeneratoren)

A method for recycling physical random numbers, von Art Owen

Public-domain-Zufallsbitdateien, Freeware (z. B. ein Programm zur Erzeugung von echt zufälligen und exakt gleichverteilten Lottozahlen) und weitere Informationen hier.

Informations-Theorie unter anderem zur Entropie, zum Entropiebelag usw.: Buch "Grundlagen der Information", Akademie Verlag, Berlin, 1991, Kapitel 1.2.5..

Über mich (Homepage)