- Kryptographisch geeigneter Zufallszahlengenerator
-
Ein kryptographisch sicherer Zufallszahlengenerator (auch kryptographisch geeigneter Zufallszahlengenerator, bzw. engl. cryptographically secure pseudo-random number generator (CSPRNG)) ist ein für die Kryptologie geeigneter Generator für Pseudozufallszahlen. Solche Zufallszahlen werden in vielen Bereichen der Kryptologie benötigt wie zum Beispiel:
- bei der Schlüsselgenerierung
- einmal genutzten Zahlen Nonces
- One-Time-Pads
- Salt
Die Qualitätsanforderungen für die Zufälligkeit solcher Zahlen sind sehr unterschiedlich. Für Nonces genügt es die Einmaligkeit der Zahl im Zufallsexperiment zu garantieren, für die Erstellung eines Hauptschlüssels oder sogar eines One-time pads sind die Anforderungen an die Zahl ungleich höher. So bleibt ein One-time pad in der Theorie nur unknackbar, wenn er aus natürlichen Zufallszahlen erstellt wurde.
Im Idealfall wird die Erstellung solcher Zufallszahlen durch andere zufällige Informationsquellen gespeist, was zum Beispiel ein hardwarebasierter Zufallsgenerator sein kann, aber auch nicht vorhersehbare Zustände in bestimmten Prozessen des Systems. Theoretisch ist es natürlich so, dass die Zufälligkeit einer aus solchen Intitaldaten generierten Zufallszahl nicht höher sein kann als die Ausgangswerte. Jedoch ist es manchmal notwendig, größere Mengen von Zufallszahlen zu generieren als aus diesen Quellen zu beziehen sind, in diesem Fall bedient man sich eines CSPRNG.
Grundsätzlich sind für einen CSPRNG dieselben Voraussetzungen wie für einen normalen Pseudozufallszahlengenerator vonnöten, nur dass für die Sicherheit noch einige zusätzliche Bedingungen erfüllt sein müssen. Die von ihm erzeugte Zahlenfolge sollte für einen Beobachter nicht von einer echten Zufallszahlenfolge unterscheidbar sein. Außerdem sollte für einen Beobachter sein interner Zustand geheim bleiben, d.h. der Generator stellt eine Black Box dar.
Inhaltsverzeichnis
Aufbau eines CSPRNG
Ein CSPRNG kann aus unterschiedlichen kryptografischen Primitiven aufgebaut werden: Stromverschlüsselung, Blockverschlüsselung, Hash-Funktionen oder auf der Grundlage mathematisch harter Probleme.
Beispiele
RC4 ist ein Stromchiffrieralgorithmus, das als CSPRNG gebraucht wird. Zu dieser Gruppe zählt auch ISAAC. [1]
ANSI X9.17
Dieser Pseudozufallszahlengenerator beruht auf Triple-DES, einem Blockverschlüsselungsverfahren.
FIPS 186-Generator
beruht auf der Hash-Funktion SHA-1.
Blum-Blum-Shub-Generator
Der BBS-Generator beruht auf der Annahme, dass Faktorisierung von Ganzzahlen ein schwieriges Problem ist, das nicht in polynomieller Zeit gelöst werden kann.
Tests auf Zufälligkeit
FIPS 140
In diesem Standard ist eine Test-Suite für CSPRNG aufgeführt. Dazu werden 20000 Ausgabebits verschiedenen statistischen Tests unterworfen:
- Monobit-Test
- Pokertest
- Run-Test
- Long Run Test (ein Run mit >34 Bits fällt durch)
Maurer's Universal Test
Die Idee hinter diesem Test ist, dass es nicht möglich sein sollte, eine Zufallszahlenfolge signifikant zu komprimieren.
Marsaglias Diehard Testsuite
Umfangreiche Testsuite, u.a.:
- Birthday Spacings Test (Geburtstagsabstände)
wählt zufällige Punkte auf einem Intervall. Diese sollten Poisson-verteilt sein. Das Prinzip des Tests ist verwandt dem Geburtstagsparadox.
- Overlapping Permutations (überlappende Permutationen)
untersucht jeweils fünf aufeinanderfolgende (Integer-)Zahlen auf Gleichverteilung. Diese können 5!=120 verschiedene Anordnungen haben, die gleichwahrscheinlich sind.
- Binary Rank Test (binärer Rangtest)
bildet aus den Bits der zu testenden Zahlenfolge zufällige Matrizen, berechnet deren Ränge. Darauf wird ein Chi-Quadrat-Test angewandt.
- Bitstream Test (Bitfolgen-Test)
betrachtet die zu testende Zahlenfolge als Bitfolgen aus jeweils 20-Bit "Worten", die sich überlappen. Es gibt 2^21 sich überlappende 20-Bit Worte und 2^20 mögliche 20-Bit Worte. Der Test zählt die fehlenden 20-Bit Worte. Diese sollten annähernd normalverteilt sein.
- Count-The-1's Test (Zähle die Einsen)
untersucht Bytefolgen. Er zählt die "1"-Bits in den Bytefolgen und vergleicht die erhaltenen Werte mit den statistisch zu erwartenden Werten.
- Parking Lot Test (Parkplatztest)
platziert zufällig Einheitskreise in ein 100x100 Quadrat. Die Anzahl der n=12000 "geparkten" Kreise sollte einer Normalverteilung folgen.
- Minimum Distance Test (Minimaler Abstand)
platziert n=8000 Punkte in ein 10000x10000 Punkte Quadrat. Dann wird der kleinste Abstand zwischen den Punktepaaren bestimmt. Der Quadrat dieser Abstände sollte exponentialverteilt sein.
- 3D Spheres Test (3D Kugel-Test)
platziert zufällig n=4000 Punkte in einen Würfel der Kantenlänge 1000. Danach wird um jeden Punkt eine Kugel mit dem Radius (Mittelpunkt, Punkt mit minimalem Abstand) gebildet. Das kleinste Kugelvolumen sollte einer Exponential-Verteilung folgen.
- Craps Test
wendet eine Teststatistik auf 200000 Craps-Spiele an
Standards
Viele Designs von CSPRNGs wurden standardisiert und sind dokumentiert in:
Einzelnachweise
Literatur
- Menezes, A.; Oorschot, P.; Vanstone, S.: Handbook of Applied Cryptography, Kapitel 5. Boca Raton. CRC Press, 1997.
Weblinks
- Referenz für CSPRNG (englisch)
- Testsuite
- Diehard Testsuite
Wikimedia Foundation.
