www.wikidata.de-de.nina.az

Kryptographisch sicherer Zufallszahlengenerator Ein kryptographisch sicherer Zufallszahlengenerator auch kryptographisch

Kryptographisch sicherer Zufallszahlengenerator

Ein kryptographisch sicherer Zufallszahlengenerator (auch kryptographisch geeigneter Zufallszahlengenerator, bzw. englisch 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:

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.

Grundsätzlich sind für einen CSPRNG dieselben Voraussetzungen wie für einen normalen Pseudozufallszahlengenerator vonnöten, allerdings müssen für die Sicherheit noch einige zusätzliche Bedingungen erfüllt sein. Zum einen darf die von ihm erzeugte Zahlenfolge nicht von einer echten Zufallszahlenfolge unterscheidbar sein. Zum anderen darf es nicht möglich sein, anhand der Ausgabe des Generators auf seinen internen Zustand zu schließen, auch wenn die genaue Funktionsweise bekannt ist.

Das BSI spezifiziert Anforderungen an Zufallszahlengeneratoren zur Verwendung in Projekten der Bundesregierung in der technischen Richtlinie BSI TR-03116 und teilt diese in Funktionsklassen ein. Im Wesentlichen werden dort physikalische echte (Klassen PTG.2, PTG.3) und nicht-physikalische echte Zufallszahlengeneratoren (Klasse NTG.1) von deterministischen bzw. pseudo Zufallszahlengeneratoren (Klassen DRG.2, DRG.3) unterschieden. Jene in den Klassen PTG.3 und NTG.1 verarbeiten die gewonnene Entropie wiederum mit einem deterministischen Zufallszahlengenerator der Klasse DRG.3 und sind somit als hybride Zufallszahlengeneratoren anzusehen. Die ehemaligen Klassen PTG.1 und DRG.1 finden seit 2022 keine Beachtung mehr.

Nichtdeterministische CSRNG Bearbeiten

Im Idealfall wird die Erstellung von Zufallszahlen durch eine nicht deterministische Entropiequelle gespeist. Das kann zum Beispiel ein hardwarebasierter Zufallsgenerator sein oder auch ein hybrider Generator. Für kryptologische Anwendungen sollten nicht-deterministische Generatoren verwendet werden, denn nur bei diesen kann garantiert werden, dass sie nicht reproduzierbar oder vorhersagbar sind.

Eine Herausforderung bei virtualisierten Umgebungen ist die Verfügbarkeit von Entropiequellen, mit denen Zufallszahlen von ausreichender Qualität für kryptographische Anwendungen bereitgestellt werden können. Prinzipiell ist in virtualisierten Umgebungen eine Entropieversorgung mit denselben Methoden wie auf physischen Maschinen möglich, allerdings gibt es Qualitätsunterschiede je nach verwendeter Entropiequelle. Ein mögliches Problem ist die Qualität der Zufallszahlen kurz nach dem Systemstart.

Deterministische CS(P)RNG Bearbeiten

In der Regel ist der Einsatz eines nichtdeterministischen Generators nicht möglich oder zu ineffizient. Dessen Datenstrom wäre auch nicht wiederholbar, was je nach Anwendung erforderlich sein kann. Darum nutzt man häufig einen deterministischen, kryptologisch sicheren Pseudozufallszahlengenerator. Ein solcher basiert entweder auf einem kryptographischen Primitiv wie einer Block- oder Stromverschlüsselung oder einer sicheren Hash-Funktion, oder auf mathematisch schwierigen, also nach aktuellem Kenntnisstand nicht in realistischer Zeit lösbaren Problemen.

Auf kryptographischen Primitiven basierende Generatoren Bearbeiten

Ein kryptographisches Primitiv, also eine Verschlüsselungs- oder Hashfunktion, wird entweder im Counter- oder im Output-Feedback-Modus betrieben. Hierbei darf es nicht möglich sein, den Anfangszustand des Generators herauszufinden. Den internen Zustand des Generators zu ermitteln, ist dann gleichbedeutend damit, das zugrundeliegende Primitiv selbst zu brechen.

Der hierbei generierte Datenstrom ist kryptologisch sicher und pseudozufällig (soweit es auch das verwendete Primitiv garantiert). Generatoren, die auf bewährten Funktionen, wie z. B. AES oder SHA-1 basieren, bestehen alle gängigen statistischen Tests auf Zufälligkeit.

Auf zahlentheoretischen Problemen basierende Generatoren Bearbeiten

Die Sicherheit des Blum-Blum-Shub-Generators beruht auf der Annahme, dass die Primfaktorzerlegung von natürlichen Zahlen ein schwieriges Problem ist, das nicht in Polynomialzeit gelöst werden kann.

Tests auf Zufälligkeit Bearbeiten

FIPS 140 Bearbeiten

In diesem US-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)

Maurers Universaltest Bearbeiten

Die Idee hinter diesem Test ist, dass es nicht möglich sein sollte, eine Zufallszahlenfolge signifikant zu komprimieren.

Diehard-Tests Bearbeiten

Umfangreiche Testsuite, u. a.:

Standards Bearbeiten

Viele Designs von CSPRNGs wurden standardisiert und sind dokumentiert in:

  • FIPS 186-2 (veraltet)
  • ANSI X9.17-1985 Appendix C
  • ANSI X9.31-1998 Appendix A.2.4
  • ANSI X9.62-1998 Annex A.4

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, Boca Raton FL u. a. 1997, ISBN 0-8493-8523-7 (CRC Press Series on Discrete Mathematics and its Applications), Kapitel 5.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Matthias Peter, Werner Schindler: A proposal for: Functionality classes for random number generators. Version 2.35 Bundesamt für Sicherheit in der Informationstechnik (BSI), 2022. (online)
  2. Zufallszahlenerzeugung in virtualisierten Umgebungen. Abgerufen am 19. Juni 2023.
  3. NIST 800-20 (PDF; 3,1 MB)
  4. Pierre L’Ecuyer, Richard Simard: TestU01 Paper
  5. National Institute of Standards and Technology (Hrsg.): Digital Signature Standard (DSS) (= Federal Information Processing Standards. Nr. 186-2). 2000, Appendix 3. Random Number Generation for the DSA ( (Memento vom 18. Mai 2009 im Internet Archive) [PDF]). (Memento vom 18. Mai 2009 im Internet Archive)
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein kryptographisch sicherer Zufallszahlengenerator auch kryptographisch geeigneter Zufallszahlengenerator bzw englisch cryptographically secure pseudo random number generator CSPRNG ist ein fur die Kryptologie geeigneter Generator fur Pseudozufallszahlen Solche Zufallszahlen werden in vielen Bereichen der Kryptologie benotigt wie zum Beispiel bei der Schlusselgenerierung einmal genutzten Nonces zufallige Bytefolgen Stromverschlusselung SaltDie Qualitatsanforderungen fur die Zufalligkeit solcher Zahlen sind sehr unterschiedlich Fur Nonces genugt es die Einmaligkeit der Zahl im Zufallsexperiment zu garantieren fur die Erstellung eines Hauptschlussels oder sogar eines One Time Pads sind die Anforderungen an die Zahl ungleich hoher So bleibt ein One Time Pad in der Theorie nur unknackbar wenn er aus naturlichen Zufallszahlen erstellt wurde Grundsatzlich sind fur einen CSPRNG dieselben Voraussetzungen wie fur einen normalen Pseudozufallszahlengenerator vonnoten allerdings mussen fur die Sicherheit noch einige zusatzliche Bedingungen erfullt sein Zum einen darf die von ihm erzeugte Zahlenfolge nicht von einer echten Zufallszahlenfolge unterscheidbar sein Zum anderen darf es nicht moglich sein anhand der Ausgabe des Generators auf seinen internen Zustand zu schliessen auch wenn die genaue Funktionsweise bekannt ist Das BSI spezifiziert Anforderungen an Zufallszahlengeneratoren zur Verwendung in Projekten der Bundesregierung in der technischen Richtlinie BSI TR 03116 und teilt diese in Funktionsklassen ein 1 Im Wesentlichen werden dort physikalische echte Klassen PTG 2 PTG 3 und nicht physikalische echte Zufallszahlengeneratoren Klasse NTG 1 von deterministischen bzw pseudo Zufallszahlengeneratoren Klassen DRG 2 DRG 3 unterschieden Jene in den Klassen PTG 3 und NTG 1 verarbeiten die gewonnene Entropie wiederum mit einem deterministischen Zufallszahlengenerator der Klasse DRG 3 und sind somit als hybride Zufallszahlengeneratoren anzusehen Die ehemaligen Klassen PTG 1 und DRG 1 finden seit 2022 keine Beachtung mehr Inhaltsverzeichnis 1 Nichtdeterministische CSRNG 2 Deterministische CS P RNG 2 1 Auf kryptographischen Primitiven basierende Generatoren 2 2 Auf zahlentheoretischen Problemen basierende Generatoren 3 Tests auf Zufalligkeit 3 1 FIPS 140 3 2 Maurers Universaltest 3 3 Diehard Tests 4 Standards 5 Siehe auch 6 Literatur 7 Weblinks 8 EinzelnachweiseNichtdeterministische CSRNG BearbeitenIm Idealfall wird die Erstellung von Zufallszahlen durch eine nicht deterministische Entropiequelle gespeist Das kann zum Beispiel ein hardwarebasierter Zufallsgenerator sein oder auch ein hybrider Generator Fur kryptologische Anwendungen sollten nicht deterministische Generatoren verwendet werden denn nur bei diesen kann garantiert werden dass sie nicht reproduzierbar oder vorhersagbar sind Eine Herausforderung bei virtualisierten Umgebungen ist die Verfugbarkeit von Entropiequellen mit denen Zufallszahlen von ausreichender Qualitat fur kryptographische Anwendungen bereitgestellt werden konnen Prinzipiell ist in virtualisierten Umgebungen eine Entropieversorgung mit denselben Methoden wie auf physischen Maschinen moglich allerdings gibt es Qualitatsunterschiede je nach verwendeter Entropiequelle Ein mogliches Problem ist die Qualitat der Zufallszahlen kurz nach dem Systemstart 2 Siehe auch Physikalischer ZufallszahlengeneratorDeterministische CS P RNG BearbeitenIn der Regel ist der Einsatz eines nichtdeterministischen Generators nicht moglich oder zu ineffizient Dessen Datenstrom ware auch nicht wiederholbar was je nach Anwendung erforderlich sein kann Darum nutzt man haufig einen deterministischen kryptologisch sicheren Pseudozufallszahlengenerator Ein solcher basiert entweder auf einem kryptographischen Primitiv wie einer Block oder Stromverschlusselung oder einer sicheren Hash Funktion oder auf mathematisch schwierigen also nach aktuellem Kenntnisstand nicht in realistischer Zeit losbaren Problemen Auf kryptographischen Primitiven basierende Generatoren Bearbeiten Ein kryptographisches Primitiv also eine Verschlusselungs oder Hashfunktion wird entweder im Counter oder im Output Feedback Modus betrieben Hierbei darf es nicht moglich sein den Anfangszustand des Generators herauszufinden Den internen Zustand des Generators zu ermitteln ist dann gleichbedeutend damit das zugrundeliegende Primitiv selbst zu brechen 3 Der hierbei generierte Datenstrom ist kryptologisch sicher und pseudozufallig soweit es auch das verwendete Primitiv garantiert Generatoren die auf bewahrten Funktionen wie z B AES oder SHA 1 basieren bestehen alle gangigen statistischen Tests auf Zufalligkeit 4 Auf zahlentheoretischen Problemen basierende Generatoren Bearbeiten Die Sicherheit des Blum Blum Shub Generators beruht auf der Annahme dass die Primfaktorzerlegung von naturlichen Zahlen ein schwieriges Problem ist das nicht in Polynomialzeit gelost werden kann Tests auf Zufalligkeit BearbeitenFIPS 140 Bearbeiten In diesem US Standard ist eine Test Suite fur CSPRNG aufgefuhrt Dazu werden 20000 Ausgabebits verschiedenen statistischen Tests unterworfen Monobit Test Pokertest Run Test Long Run Test ein Run mit gt 34 Bits fallt durch Maurers Universaltest Bearbeiten Die Idee hinter diesem Test ist dass es nicht moglich sein sollte eine Zufallszahlenfolge signifikant zu komprimieren Diehard Tests Bearbeiten Umfangreiche Testsuite u a Birthday Spacings Test Geburtstagsabstande wahlt zufallige Punkte auf einem Intervall Diese sollten Poisson verteilt sein Das Prinzip des Tests ist verwandt mit dem Geburtstagsparadox Overlapping Permutations uberlappende Permutationen untersucht jeweils funf aufeinanderfolgende Integer Zahlen auf Gleichverteilung Diese konnen 5 120 verschiedene Anordnungen haben die gleich wahrscheinlich sind Binary Rank Test binarer Rangtest bildet aus den Bits der zu testenden Zahlenfolge zufallige Matrizen berechnet deren Range 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 uberlappen Es gibt 221 sich uberlappende 20 Bit Worte und 220 mogliche 20 Bit Worte Der Test zahlt die fehlenden 20 Bit Worte Diese sollten annahernd normalverteilt sein Count The 1s Test Zahle die Einsen untersucht Bytefolgen Er zahlt die 1 Bits in den Bytefolgen und vergleicht die erhaltenen Werte mit den statistisch zu erwartenden Werten Parking Lot Test Parkplatztest platziert zufallig Einheitskreise in ein 100 100 Quadrat Ein Kreis gilt als erfolgreich geparkt wenn es keine Uberlappung mit einem bereits erfolgreich geparkten Kreis gibt Die Anzahl der erfolgreich geparkten Kreise nach n 12000 Versuchen sollte annahernd normalverteilt sein Minimum Distance Test Minimaler Abstand platziert n 8000 Punkte in ein 10000 10000 Punkte Quadrat Dann wird der kleinste Abstand zwischen den Punktepaaren bestimmt Das Quadrat dieser Abstande sollte exponentialverteilt sein 3D Spheres Test 3D Kugel Test platziert n 4000 Punkte in einen Wurfel der Kantenlange 1000 Danach wird um jeden Punkt eine Kugel gebildet Der Radius dieser Kugeln ist der Abstand zwischen dem Mittelpunkt und dem jeweils nachstgelegenen Punkt Die sich so ergebenden Kugelvolumen sollten einer Exponentialverteilung folgen Runs Test entnimmt n Kugeln aus einer Urne mit zwei verschiedenen Kugelsorten Gleichfarbige nacheinanderfolgend gezogene Kugeln werden zu einem Zug Run zusammengefasst Die Anzahl der ubriggebliebenen Zuge soll der einer echten Zufallsziehung zur gegebenen Lange n entsprechen Craps Test wendet eine Teststatistik auf 200000 Craps Spiele an Standards BearbeitenViele Designs von CSPRNGs wurden standardisiert und sind dokumentiert in FIPS 186 2 veraltet 5 ANSI X9 17 1985 Appendix C ANSI X9 31 1998 Appendix A 2 4 ANSI X9 62 1998 Annex A 4Siehe auch BearbeitenListe von ZufallszahlengeneratorenLiteratur BearbeitenAlfred J Menezes Paul C van Oorschot Scott A Vanstone Handbook of Applied Cryptography CRC Press Boca Raton FL u a 1997 ISBN 0 8493 8523 7 CRC Press Series on Discrete Mathematics and its Applications Kapitel 5 Weblinks BearbeitenRandom Number Generation NIST Computer Security Division englisch Referenz fur CSPRNG Testsuite Diehard Testsuite Zufallszahlengenerator zur Erzeugung von One Time Pads englisch Einzelnachweise Bearbeiten Matthias Peter Werner Schindler A proposal for Functionality classes for random number generators Version 2 35 Bundesamt fur Sicherheit in der Informationstechnik BSI 2022 online Zufallszahlenerzeugung in virtualisierten Umgebungen Abgerufen am 19 Juni 2023 NIST 800 20 PDF 3 1 MB Pierre L Ecuyer Richard Simard TestU01 Paper National Institute of Standards and Technology Hrsg Digital Signature Standard DSS Federal Information Processing Standards Nr 186 2 2000 Appendix 3 Random Number Generation for the DSA csrc nist gov Memento vom 18 Mai 2009 im Internet Archive PDF Digital Signature Standard DSS Memento vom 18 Mai 2009 im Internet Archive Abgerufen von https de wikipedia org w index php title Kryptographisch sicherer Zufallszahlengenerator amp oldid 235672384