Echte physikalische Zufallszahlengeneratoren
English Version
Echte physikalische Zufallszahlengeneratoren |
Klick here for an English Version |
SSL-URL dieser Seite |
|---|
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ächtnislä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 Parameter 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 umverborgene Parameter
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 M>0 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 die Nachkommastellen der Zahl Pi, sind die
Entropien daher (nahezu) eins, während der Entropiebelag auch
dort null ist.
Anschaulich bedeutet dies, dass die Nachkommastallen der Zahl Pi
immer eine (scheinbare) Zufälligkeit haben und dadurch insgesamt
unendlich viel Information (bzw. Desinformation) enthalten
während Pseudozufallszahlengeneratoren endlicher Periode bei
einer geeignet gewählten Zufallszahlenbreite immer nur die eine
gleiche Zufallszahl ausgeben und damit keinerlei Zufälligkeit
haben.
Anschaulich bedeutet der Wert des Entropie-Belags, dass
Pseudozufallszahlengeneratoren keine echte Zufälligkeit
(Nichtdeterminiertheit) haben, auch wenn sie unendlich viel
Information (bzw. Desinformation) enthalten.
In der Praxis sieht man es 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 Standard-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.
| Referenzkunden: | iPei |
|---|
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.
| Referenzkunden: |
|
|---|
| Referenzkunden: |
|
|---|
| Referenzkunden: |
|
|---|
Ein zugehöriger uni ulm intern - Artikel vom November 1999 hier.
Ein Artikel zur ersten Generation meiner Zufallszahlengeneratoren hier.
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)
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..
Weitere Infos von und Bestellungen an: |
 |
|---|
EU VAT-ID: DE245929143
