Beschreibung

Die vorliegende Erfindung betrifft einen selbsttestbaren echten Zufallszahlengenerator basierend auf einer Kombination von individualisierten Matrixfeld-Oszillatoren bestehend aus sich gegenseitig beeinflussenden XOR-Mini-Oszillatoren.

Stand der Technik

In vielen Bereichen werden Zufallszahlen verwendet. Dazu zählen Bereiche wie Kryptographie, Monte-Carlo-Berechnung und Simulation, Glücksspiele usw.. Ein besonders wichtiger Bereich ist die Kryptographie. Hier werden Zufallszahlen u.a. für Schlüssel für symmetrische und asymmetrische Kryptographieverfahren, kryptographische Abfrage-Antwort-Protokolle,

Initialisierungsvektoren oder Zufallsstopfbits benötigt. Ein praktisches Anwendungsgebiet in diesem Bereich sind beispielsweise Chipkarten.

Zufallszahlen können durch Zufallszahlengeneratoren erzeugt werden. Es gibt im Wesentlichen zwei Hauptarten von Zufallszahlengeneratoren (random number generators - RNGs): deterministische (pseudozufällige) RNGs (DRNG oder PRNG) und nichtdeterm inistische Zufallsgeneratoren (echt zufällig, Hardware) basierend auf einem physikalischen Prozess (physical true RNG - TRNG oder PTRNG). Die letzteren können kurz als echte oder physikalische Zufallszahlengeneratoren bezeichnet werden. Die

Hauptanforderung an sie ist, dass sie unvorhersehbare und unkontrollierbare Zufallszahlen generieren. Obwohl sehr viele Konstruktionen von physikalischen Zufallszahlengeneratoren existieren und obwohl auch die Forschung auf diesem Gebiet weiter geht, lässt sich der augenblickliche Stand der Technik gemäß der wissenschaftlichen Veröffentlichung „Mario Stipcevic und etin Kaya Kog, True Random Number Generators, Open Problems in Mathematics and Computational Science, Springer International Publishing, Switzerland, S. 275-316, 2014“, welche den hierzu nächstgelegenen Stand der Technik offenbart, in diesem Bereich grob in die vier folgende Familien unterteilen:

- auf Rauschen basierende Zufallszahlengeneratoren (noise based RNGs)

- Zufallszahlengeneratoren basierend auf einem frei laufenden Oszillator (free running oscillator RNGs)

- Chaos-Zufallszahlengeneratoren (chaos RNGs)

- Quanten-Zufallszahlengeneratoren (quantum RNGs)

Zurzeit gibt es keine Standardisierung in diesem Bereich. Allerdings herrscht in der Industrie aktuell die Verwendung von physikalischen Zufallszahlengeneratoren basierend auf einem frei laufenden Oszillator (free running oscillator - FRO) vor, deren Zufälligkeit bzw. Entropie sich von elektronischem Rauschen in logischen Schaltungen ableiten lässt und die sich nicht als strikt gleichmäßig zufällig erwiesen haben. Diese Art von Zufallszahlengeneratoren bietet allerdings grundsätzlich eine leichtere technische Realisierbarkeit. Eine neuere Entwicklung in diesem Bereich sind Zufallszahlengeneratoren basierend auf einer Kombination eines linearen Rückkopplungsschieberegisters (linear feedback shift register - LFSR) und eines frei laufenden Oszillators (FRO). Sie werden Fibonacci-Ringoszillator (Finbonacci ring oscillator - FIRO) und Galois-Ringoszillator (Galois ring oscillator - GARO) genannt.

Weiterer diesbezüglicher Stand der Technik ergibt sich aus dem folgenden wissenschaftlichen Veröffentlichungen: V. Fischer, Random Number Generators for Cryptography - Design and Evaluation, Summer School on Design and Security of Cryptographic Algorithms and Devices, Sibenik, Croatia, June 2014;

M. Dichtl, Fibonacci Ring Oscillators as True Random Number Generators - A Security Risk, IACR Cryptology ePrint Archive, 270, 2015;

W. Killmann and W. Schindler, AIS20/AIS31 - A Proposal for: Functionality Classes for Random Number Generators, Version 2.0, 2011 ;

A. Rukhin et al. , A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST Special Publication 800-22, US Department of Commerce, National Institute of Standards and Technology, Gaithersburg, MD, April 2010;

M. Dichtl, J.D. Golic, High-Speed True Random Number Generation with Logic Gates Only, Cryptographic Hardware and Embedded Systems - CHES 2007, Lecture Notes in Computer Science, vol 4727, Springer, Berlin, Heidelberg, pp 45-62, 2007;

J. Baiasch et al., Design and testing methodologies for true random number generators towards industry certification, 2018 IEEE 23rd European Test Symposium (ETS), Bremen, pp. 1-10, 2018;

M. Sönmez Turan et al., Recommendation for the Entropy Sources Used for Random Bit Generation, NIST Special Publication 800-90B, Department of Commerce, National Institute of Standards and Technology, Gaithersburg, MD, January 2018; A Schubert and W. Anheier, On Random Pattern Testability of Cryptographic VLSI Cores, Journal of Electronic Testing: Theory and Applications, Vol. 16, No. 3, Kluwer Academic Publishers, Netherlands, pp. 185-192, 2000;

A. Schubert, Modellierung, Optimierung und Selbsttest von kryptographischen virtuellen Komponenten, Dissertation Universität Bremen, Fortschritt-Berichte VDI Reihe 10, Nr. 690, VDI Verlag GmbH, Düsseldorf, 2002.

Zusammenfassend kann man über FRO-Zufallszahlengeneratoren sagen, dass sie niedrige Kosten und Aufwand versprechen, aber eine Lösung mit niedriger Entropie darstellen. Sie bieten weder eine sehr gute noch eine beweisbare Zufälligkeit. Außerdem besteht die Gefahr der Kopplung von FROs mit dem Systemtakt oder anderen Logikschaltungen auf dem Chip einschließlich in der Nähe liegender FROs. Die Implementierungsdetails von FROs müssen häufig an den spezifischen Typ, die Generation oder die Technologie eines FPGAs oder ASICs angepasst werden. Trotz ihres interessanten und innovativen Prinzips stellen Fibonacci-Ringoszillatoren und Galois-Ringoszillatoren nur eine Teillösung der Probleme von FROs dar. Das Problem der Nicht-Portierbarkeit und der Anforderung eines genügend großen Rauschens für ein vernünftiges zufälliges Verhalten, weit weg von einem pseudozufälligen Verhalten, bleiben bestehen. Ein weiteres beobachtetes Problem dieser neuen Art von Ringoszillatoren ist die Gefahr eines ungewollten Stillstandes oder des Auftretens von periodischen statt chaotischen Oszillationen. Allgemein ist die Verbreitung echter Zufallszahlengeneratoren noch eher begrenzt. Das liegt wohl auch daran, dass der Preis von guten echten kommerziellen Zufallszahlengeneratoren mit hohen Bitraten wie beispielsweise echten Quanten-Zufallszahlengeneratoren recht hoch ist.

Ausgehend von dem beschriebenen Stand der Technik ist es Aufgabe der vorliegenden Erfindung, einen Zufallszahlengenerator zu schaffen, der ein robustes, zuverlässiges, maximal echt zufälliges Verhalten garantiert und ausschließlich unter Verwendung bekannter digitaler Schaltungen aufgebaut ist. Damit lässt sich erfindungsgemäß erstmals eine kryptographische Schaltung zur Ausführung symmetrischer und/oder asymmetrischer Kryptographieverfahren schaffen, die vollständig, einschließlich eines echten Zufallszahlengenerators mit robuster, zuverlässiger, annähernd maximal echter Zufälligkeit (Entropie), auf einer einzigen integrierten digitalen Schaltung aufgebaut ist.

Erfindungsgemäß wird diese Aufgabe dadurch gelöst, dass der Zufallszahlengenerator eine Matrix aus einzelnen Oszillator-Schaltungen umfasst, die eine gerade Anzahl Eingänge aufweisen, die jeweils mit einem Ausgang einer benachbarten Oszillator-Schaltung verbunden sind, wobei jeweils zwei der Eingänge mit einem ersten Exklusiv-Oder-Gatter verbunden sind, und die Ausgänge der ersten Exklusiv-Oder-Gatter mit Eingängen eines weiteren Exklusiv-Oder-Gatters verbunden sind, dessen Ausgangssignal ein Ausgangssignal der einzelnen Oszillator-Schaltung bildet, und mit Eingängen der jeweils benachbarten Oszillator-Schaltungen verbunden ist, wobei die Oszillator-Schaltungen an den Rändern der Matrix entsprechend mit Oszillator-Schaltungen an den gegenüberliegenden Rändern der Matrix verbunden sind, und das Ausgangssignal einer der Oszillator-Schaltungen den Signal-Ausgang der Matrix bildet.

Mit dieser Schaltungsanordnung lässt sich erstmals mittels eines neuartigen Zusammenschlusses bekannter digitaler Einzelschaltungen ein analoges Ausgangssignal mit echt zufälligem Signalverlauf erzeugen, das eine robuste und zuverlässige Extraktion von annähernd maximal echter Zufälligkeit (Entropie) durch Abtastung ermöglicht. Es ist nicht mehr nötig, wie bei bisherigen echten Zufallszahlengeneratoren mit hoher Qualität, dieses echt zufällige analoge Ausgangssignal mittels analoger Schaltungen und/oder anderen physikalischen Hilfsmittel, wie beispielsweise radioaktiven Zerfällen zu bilden. Der Grundgedanke besteht darin, mit sogenannten Matrixfeld-Oszillatoren möglichst nah an der Idee eines auf Oszillatoren basierenden Zufallszahlengenerators zu bleiben, aber a) den echt zufälligen Einfluss (echte Entropie) von unvorhersehbaren, intrinsischen Veränderungen (Instabilitäten) von Verzögerungszeiten von Schaltungselementen durch elektronisches Rauschen auf die Signalausbreitung und damit auf die Zustände in einer komplexen asynchronen Schaltung entscheidend zu erhöhen bzw. zu verstärken und so den pseudozufälligen Einfluss signifikant zu reduzieren und b) die positiven Eigenschaften von XOR-Logikbausteinen in Form von sogenannten Mini-Oszillatoren möglichst optimal zu nutzen und c) die Sicherheit und Robustheit gegen unerwünschte Manipulationen (Attacken) durch die gewählte komplexe Schaltungsstruktur deutlich zu erhöhen. Die Ausgangssignale der XOR-Mini-Oszillatoren an den Rändern der Matrixfeld-Oszillatoren werden nicht direkt als Eingangssignale zurückgeführt, sondern sie dienen als Eingangssignale für die XOR-Mini- Oszillatoren an den gegenüberliegenden Rändern des jeweiligen Matrixfeld- Oszillators. Diese Maßnahme dient dazu, die statistischen Eigenschaften des Zufallszahlengenerators zu verbessern. Dabei sollen die Matrixfeld- Oszillatoren nicht zu groß werden, um eine Kombination von mehreren Matrixfeld-Oszillatoren zu ermöglichen.

Weitere bevorzugte Ausführungsformen der vorliegenden Erfindung ergeben sich aus den Unteransprüchen:

Hierbei ist es bevorzugt, dass das Ausgangssignal der einzelnen Oszillator- Schaltung noch über einen Signaleingang eines Multiplexers geführt ist, dessen Steuereingang mit einem ersten binären Steuersignal und dessen anderer Signaleingang mit einem weiteren binären Steuersignal verbunden ist, und dessen Ausgangssignal das Ausgangssignal der einzelnen Oszillator-Schaltung bildet, wobei das erste binäre Steuersignal zum Aktivieren und Deaktivieren der Matrix aus Oszillator-Schaltungen dient, und das weitere binäre Steuersignal zum sicheren Anlaufen der einzelnen Oszillator-Schaltungen dient.

Auf diese Weise kann der erfindungsgemäße Zufallszahlengenerator gezielt ein- und ausgeschaltet werden und gleichzeitig kann ein sicheres Anschwingen der einzelnen Oszillator-Schaltungen herbeigeführt werden.

Es ist weiter bevorzugt, das Ausgangssignal mindestens einer der einzelnen Oszillator-Schaltungen über einen Inverter zu führen. Dies verbessert sowohl die Zufälligkeit des Ausgangssignals als auch die Sicherheit des Anschwingens der verbundenen Oszillator-Schaltungen.

Weiter ist es bevorzugt, dass die Matrix zweidimensional, vorzugsweise quadratisch ist, und vorzugsweise 6 x 6 einzelne Oszillator-Schaltungen umfasst.

Die vorliegende Erfindung würde zwar auch mit einer eindimensionalen Matrix funktionieren, dann ist ein sicheres Anschwingen der Oszillatoren aber nicht mehr garantiert und das zufällige Verhalten könnte durch Einwirkungen von außen manipuliert werden. Eine mehr als zweidimensionale Ausführung der Matrix führt zu extrem kompliziertem Schaltungsaufbau, ohne dass noch ein erheblicher Gewinn an Manipulationsfestigkeit und Zufälligkeit des Schaltungsverhaltens erzielt werden könnte.

Weiter ist es bevorzugt, dass eine weitere der Oszillator-Schaltungen der Matrix mit einem speziellen weiteren binären Steuersignal an ihrem Multiplexer verbunden ist, welches so eingerichtet ist, dass es für eine kurze Zeitspanne direkt vor der Aktivierung der Matrix über das erste binäre Steuersignal aktiviert wird, und damit zum sicheren Anlaufen der Oszillator- Schaltungen der Matrix dient. Auf diese Weise kann ein sicheres Anschwingen der Oszillatoren der Matrix sichergestellt werden. Weiter ist es bevorzugt, dass lediglich eine weitere Oszillator-Schaltung in der Matrix mit einem Inverter versehen ist.

Es hat sich nämlich gezeigt, dass das Vorsehen eines Inverters in der gesamten Matrix das Anschwingen aller Oszillatoren verbessert. Weitere Inverter vorzusehen bringt keinen größeren Zugewinn mehr, erhöht aber den Schaltungsaufwand.

Weiter ist es erfindungsgemäß bevorzugt, das Ausgangssignal der Matrix mit einem D-Kippglied (erste Metastabiltäts-FF-Stufe) zu verbinden, dessen Ausgangssignal das abgetastete - ggf. metastabile - Ausgangssignal der Matrix darstellt. Zusammen mit der zweiten Metastabiltäts-FF-Stufe kann auf diese Weise am einfachsten das gewünschte digitale Ausgangssignal der Matrix bereitgestellt werden, da die Matrix selbst, wie oben beschrieben, trotz ihrer Zusammensetzung ausschließlich aus Digitalschaltungen ein analoges Ausgangssignal liefert.

Eine Verletzung der Setup- and Hold- Zeiten der ersten D-Kippglied-Stufe durch das analoge Ausgangssignal der Matrix führt zu einen nicht digitalen (metastabilen) "Zwischensignal" nach der ersten D-Kippglied-Stufe, siehe https://de.wikipedia.org/wiki/Metastabilität_(digitale_Scha ltung). Erst nach der zweiten D-Kippglied-Stufe erhält man ein rein digitales und synchronisiertes Ausgangssignal.

Weiter ist es bevorzugt, wenn der erfindungsgemäße Zufallszahlengenerator mehrere Matrizen aus einzelnen Oszillator-Schaltungen umfasst, deren abgetastete Ausgangssignale alle jeweils mit einem Eingang eines Exklusiv- Oder-Gatters verbunden sind, dessen Ausgang die Zufallssequenz liefert.

Die XOR-Kombination von mehreren individualisierten Matrixfeld-Oszillatoren gleichzeitig mit der Digitalisierung (und Synchronisierung) hat den Vorteil, dass ggf. auch der Ausfall eines Matrixfeld-Oszillators abgefangen wird. Außerdem wird der Zufallszahlengenerator durch die XOR-Kombination unabhängiger Matrixfeld-Oszillatoren zufälliger und robuster, da die Entropie am Ausgang der XOR-Kombination größer als die einzelnen Entropien an den Ausgängen der Matrixfeld-Oszillatoren (vor der XOR-Kombination) ist.

Weiter ist es bevorzugt, wenn der Ausgang des Exklusiv-Oder-Gatters mit einem Eingang der zweiten D-Kippglied-Stufe (zweite Metastabilitäts-FF- Stufe) verbunden ist, dessen Ausgang die digitalisierte und synchronisierte Zufallssequenz liefert.

Weiter ist es bevorzugt, wenn die einzelnen, durch das Exklusiv-Oder-Gatter verbundenen Matrizen dadurch individualisiert sind, dass in jeder der Matrizen die relativen Positionen der Oszillator-Schaltungen mit dem Inverter, dem Signal-Ausgang und dem speziellen weiteren binären Steuersignal (Ort der Anregung) zueinander anders sind.

Die Individualisierung der Matrixfeld-Oszillatoren durch Wahl des Ortes der Anregung, des Inverters und des Ausgangs machen die Matrixfeld- Oszillatoren unabhängig voneinander. Damit können die statistischen Eigenschaften des Zufallszahlengenerators weiter verbessert werden und die Gefahr der Kopplung von Matrixfeld-Oszillatoren vermieden werden. Der Einsatz eines zusätzlichen Inverters im Matrixfeld dient der Vermeidung der Gefahr eines ungewollten Stillstandes bzw. einer periodischen Oszillation eines Matrixfeld-Oszillators.

Weiter ist es bevorzugt, das Ausgangssignal einer Oszillator-Schaltung einer Matrix mit einem Dateneingang eines ersten D-Kippglieds zu verbinden, dessen Ausgang mit einem Dateneingang eines zweiten D-Kippglieds verbunden ist, dessen Ausgang mit einem Dateneingang eines dritten D- Kippglieds verbunden ist, dessen Ausgang ebenso wie der Ausgang des zweiten D-Kippglieds jeweils mit einem Eingang eines Exklusiv-Oder-Gatters verbunden ist, dessen Ausgang anzeigt, ob die Oszillator-Schaltung schwingt. Auf diese Weise wird erfindungsgemäß ein Kontrollsignal über das korrekte Schwingen der jeweiligen Matrizen aus Oszillator-Schaltungen bereitgestellt.

Dabei ist es weiter bevorzugt, dass die Ausgänge der Exklusiv-Oder-Gatter verschiedener Oszillator-Schaltungen einer Matrix jeweils mit einem Eingang eines Oder-Gatters verbunden sind, dessen Ausgang mit dem Rücksetz- Eingang eines Zählers verbunden ist, der mit einem Systemtakt hochzählt, und dessen Überlauf ein Signal liefert, dass die Matrix nicht ordnungsgemäß oszilliert.

Auf diese Weise wird sichergestellt, dass lediglich echte Stillstände der Oszillatoren der Matrizen ein Störungssignal liefern. Schließlich bedeutet ein analoges zufälliges Ausgangssignal auch, dass das Signal über einen längeren Zeitraum konstant null oder eins sein kann, da diese Signalfolge zwar unwahrscheinlich aber nicht ausgeschlossen ist.

Zur Überwachung des gesamten erfindungsgemäßen Zufallszahlengenerators ist es bevorzugt, die Überlauf-Signale der Zähler der zu dem Zufallszahlengenerator verbundenen Matrizen jeweils mit einem Eingang eines Und-Gatters zu verbinden, dessen Ausgangssignal einen Totalausfall des Zufallszahlengenerators anzeigt. Dieser Totalausfall-Test hat die Aufgabe, einen Totalausfall des Zufallszahlengenerators schnell anzuzeigen, und ist an den speziellen erfindungsgemäßen Aufbau des Zufallszahlengenerators angepasst.

Eine Nachbearbeitung (post-processing) nach der Digitalisierung ist erfindungsgemäß nicht erforderlich, um statistische Tests zu bestehen. Vorzugsweise wird eine Wartezeit (Anlaufzeit) direkt nach dem Start des Zufallszahlengenerators vor Ausgabe der ersten Zufallswerte eingeführt. Während dieser Zeit werden die anfallenden Daten verworfen. Mit dieser Maßnahme wird der noch vorhandene pseudozufällige Einfluss auf den Zufallszahlengenerator entscheidend reduziert. Eingebaute Oszillationsprüfungen (built-in oscillation health tests) ermöglichen eine sichere Aussage über die Zustände der Matrixfeld-Oszillatoren. Die Auswertung aller Oszillationsprüfungen führt zu einem einfachen, effektiven und schnellen Test zur Erkennung eines Totalausfalls der Rauschquelle (total failure test (TOT) of the noise source). Desweiteren kann der Zufallszahlengenerator durch ein entsprechendes Eingangssignal gezielt in einen Ruhezustand gebracht werden.

Die vorliegende Erfindung weist die folgenden Vorteile auf:

- Kombination von individualisierten Matrixfeld-Oszillatoren, die unabhängig voneinander sind, zu einem statistisch starken, robusten, echten Zufallszahlengenerator

- bessere echte Zufallseigenschaften als andere bekannte vergleichbare Ansätze

- keine zusätzliche (komplexe) Nachbearbeitung (post-processing) nach der Digitalisierung notwendig zur Erreichung der geforderten statistischen Eigenschaften

- hervorragende Ergebnisse bei statistischen Tests (AIS-31 -Testsuite, NIST statistische Testsuite/NIST 800-22, TestUOl statistischer Test von der Universität Montreal und Tests gemäß NIST SP800-90B) der Original- Zufallssequenz (raw random sequence) nach der Digitalisierung (alle Tests werden bestanden)

- kostengünstiger und technologieunabhängiger Ansatz ohne analoge Komponenten, da sehr einfache Implementierbarkeit und Portierbarkeit des Zufallszahlengenerators bei alleiniger Verwendung von normaler digitaler Logik (geeignet für alle FPGAs und ASICs) mit begrenzten Ressourcen und keine Notwendigkeit von speziellen manuellen Interventionen (stattdessen automatische Synthese) höhere Sicherheit durch die Implementierung des ganzen Zufallszahlengenerators in einen einzigen Chip und ggf. zusätzliche Integration eines kryptographischen Systems in demselben Chip, da Realisierung des Zufallszahlengenerators unter alleiniger Verwendung von normaler digitaler Logik (geeignet für alle FPGAs und ASICs) bei begrenzten Ressourcen

- sehr hohe konstante Bitrate (mindestens 30 Mbit/s) im Vergleich mit vergleichbaren Zufallszahlengeneratoren (digitale Logik, Aufwand, Kosten) möglich

- Vermeidung der Gefahr eines Stillstandes des Zufallszahlengenerators (stall) bzw. von periodischen Oszillationen durch Einsatz mindestens eines zusätzlichen Inverters in jedem der Matrixfeld-Oszillatoren entscheidende Reduzierung des noch vorhandenen kleinen pseudozufälligen Einflusses auf die Ausgangssequenz nach der Digitalisierung durch eine Wartezeit (Verwerfen der anfallenden Daten während der Wartezeit) direkt nach Start vor Ausgabe des ersten Zufallswerts

- weitgehende Temperaturunabhängigkeit des Zufallsprozesses

- keine Gefahr der Kopplung von Matrixfeld-Oszillatoren im Vergleich zu FROs u.a. aufgrund der Individualisierung und der komplexen Struktur (Gatter-Rückkopplungspfade) der Matrixfeld-Oszillatoren (wesentlich komplexer als FROs) - große Sicherheit und Robustheit des Zufallszahlengenerators (bisher sind keine Attacken und/oder Schwächen bekannt), da deutlich kleinere Gefahr der Manipulation von Matrixfeld-Oszillatoren beispielsweise im Rahmen von aktiven Seitenkanalattacken im Vergleich zu FROs u.a. aufgrund der Individualisierung und der komplexen Struktur (Gatter-Rückkopplungspfade) der Matrixfeld-Oszillatoren (wesentlich komplexer als FROs)

- einfacher, effektiver und schneller Totalausfall-Test basierend auf eingebauten Oszillationsprüfungen der Matrixfeld-Oszillatoren.

Die vorliegende Erfindung kann im Bedarfsfälle folgendermaßen weiterentwickelt werden:

A. Kombination mit kryptographischer Nachbearbeitung (cryptographic post- processing) mit deterministischen RNG (DRNG) gemäß AIS20/31.

B. eingebettete On-Iine-Tests (initiale, regelmäßige und auf Anfrage) beispielsweise gemäß AIS20/31 und/oder NIST zusätzlich zu den schon vorhandenen Tests.

C. Erstellen eines stochastischen Modells gemäß AIS20/31

D. Veränderung der Größe der Matrixfeld-Oszillatoren E. Veränderung der Dimension der Matrixfeld-Oszillatoren

F. veränderter Einsatz von Invertern in den Matrixfeld-Oszillatoren

G. Veränderung der Anzahl der zu kombinierenden Matrixfeld-Oszillatoren H. Veränderung der Wartezeit (Anlaufzeit) nach Start des Zufallszahlengenerators vor Ausgabe des ersten Zufallswertes bei Verwerfen der vorherigen Werte I. Einführung einer Neustart-Betriebsart für Hochsicherheitsanwendungen

J. Puffern von Zufallszahlen vor Ausgabe

K. Eventuelle (Verwendung nur in bestimmten Fällen bei 1 sehr seltenen Anwendungen des Ausführungsbeispiels mit extremen Anforderungen an die statistischen Eigenschaften oder bei 2. für sehr gute statistischen Eigenschaften nicht ausreichender Konfiguration des Zufallszahlengenerators (beispielsweise kleinere Anzahl von Matrixfeld- Oszillatoren oder kleinere Anzahl von XOR-Mini-Oszillatoren in den Matrixfeld-Oszillatoren als beim Ausführungsbeispiel) zusätzliche Nachbearbeitung (postprocessing) wie beispielsweise mit dem Von- Neumann-Verfahren

Diese Weiterentwicklungen können zusätzlich die folgenden Vorteile ermöglichen: zu A.: Gewährleistung der Unvorhersehbarkeit von generierten Zahlen in Vorwärts und/oder Rückwärtsrichtung bei permanenten und temporären Ausfall der Rauschquelle (entropy source) zu B.: umfassende On-Iine-Test-Strategie (u.a. auch On-Iine-Test der statistischen Eigenschaften) zu C.: Entropie-Abschätzung, Erfüllen der Anforderungen von AIS20/31 zu D, E, F, G, H: Anpassung an veränderte technische Gegebenheiten, d.h. z.B. an neue FPGA- oder ASIC-Technologiegenerationen, oder an neue Erkenntnisse hinsichtlich Schwächen bzw. Attacken zu I: Online-Test der echten Zufälligkeitseigenschaften zu J: Ergebnisse von Tests abwarten und ggf. mangelhafte Daten verwerfen. zu K.: Einsatz der Nachverarbeitung zur weiteren Verbesserung der statistischen Eigenschaften der vom Zufallszahlengenerator erzeugten Zufallsdaten (in den allermeisten Anwendungsfällen dieses Zufallszahlengenerators und insbesondere im Fall des Ausführungsbeispiels ist diese Nachbearbeitung nicht notwendig und nicht vorteilhaft bzw. wünschenswert u.a. wegen der Reduzierung der Datenbitrate).

Folgende Abwandlungen der vorliegenden Erfindung sind möglich:

- Veränderung der Größe der zweidimensionalen, quadratischem Matrixfeld- Oszillatoren, d.h. andere Anzahl von XOR-Mini-Oszillatoren

- Veränderung der Formen der Matrixfeld-Oszillatoren (kein Quadrat)

- Veränderung der Verdrahtung der XOR-Mini-Oszillatoren, insbesondere an den Rändern der Matrixfeld-Oszillatoren

- Veränderung der Dimension der Matrixfeld-Oszillatoren (eindimensionale oder mehrdimensionale (dreidimensionale, vierdimensionale, ...) Struktur durch entsprechende Veränderung der Anzahl der Eingänge der XOR-Mini- Oszillatoren und der zweidimensionalen Verdrahtung der XOR-Mini- Oszillatoren) - Veränderung der Logik-Struktur in den XOR-Mini-Oszillatoren (z.B. XOR- Gatter mit 4 Eingängen)

- veränderter Einsatz von Invertern in den Matrixfeld-Oszillatoren

- Veränderung der Anzahl der Matrixfeld-Oszillatoren

- Veränderung der Individualisierung der Matrixfeld-Oszillatoren

Veränderung der Wartezeit (Anlaufzeit) nach Start des Zufallszahlengenerators vor Ausgabe des ersten Zufallswertes bei Verwerfen der vorherigen Werte

- veränderter Totalausfall-Test bzw. andere Oszillationsprüfungen (z.B. andere Anzahl von Takten ohne Flanke der jeweils 6 Testsignale als Schwelle für die Meldung einer Nicht-Oszillation).

Es existiert ein VHDL-Modell eines Ausführungsbeispiels des erfindungsgemäßen Zufallszahlengenerators. Basierend auf diesem VHDL- Modell ist auf einem SmartFusion-Evaluationsboard mit dem SmartFusion - FPGA A2F200M3F-FGG484 von Microsemi (Microchip Technology) ein Prototyp des Ausführungsbeispiels des Zufallszahlengenerators implementiert. Es gibt weitere Implementierungen des Prototyps auf einem IGLOO-Nano-Starter-Kit-Board ebenfalls von Microsemi, auf einem Cmod- S6-Board von Digilent mit dem Xilinx Spartan 6 LX4 FPGA (Spartan 6 XC6SLX4-2CPG1 96 FPGA) und auf einem Cmod-S7-Board von Digilent mit dem Xilinx Spartan 7 FPGA (Spartan 7 XC7S25-1CSGA225C FPGA).

Im Folgenden wird die Erfindung anhand eines in den Zeichnungen dargestellten Ausführungsbeispiels näher beschrieben und erklärt.

Es zeigen: Fig. 1 einen erfindungsgemäßen XOR-Mini-Oszillator ohne Darstellung der Rückkopplung über Nachbar-Mini-Oszillatoren; Fig. 2 die erfindungsgemäße Verbindung zweier benachbarter XOR- Mini-Oszillatoren der Fig. 1 ;

Fig. 3 den Aufbau eines erfindungsgemäßen Matrixfeld-Oszillators aus einer zweidimensionalen Matrix von XOR-Mini-Oszillatoren mit einer beispielhaften Individualisierung ohne Darstellung der Verbindungsleitungen an den Rändern;

Fig. 4 den Matrixfeld-Oszillator der Fig. 3 mit Darstellung der Verbindungsleitungen an den Rändern (zum Zweck der Übersichtlichkeit sind hier die Signalbezeichnungen bei den einzelnen Oszillatoren weggelassen);

Fig. 5 die Nummerierung der Elemente der Matrix eines Matrixfeld- Oszillators;

Fig. 6 die Gesamtschaltung eines erfindungsgemäßen Zufallszahlengenerators aus den einzelnen vorbeschriebenen Elementen mit digitalisierter Rauschquelle (ohne Totalausfall-Test und Oszillationsprüfungen);

Fig. 7 die erfindungsgemäß vorgeschlagene Schaltung für die Flankenerkennung zum Zweck der Oszillationsprüfung;

Fig. 8 die Schaltung für die erfindungsgemäße Oszillationsprüfung; Fig. 9 die erfindungsgemäße Schaltung für den Totalausfall-Test; Fig. 10 das Ausgangssignal eines erfindungsgemäßen Matrixfeld- Oszillators im Zeit- (oberer Teil der Abbildung) und im Frequenzbereich (unterer Teil der Abbildung) falls der Matrixfeld- Oszillator deaktiviert ist;

Fig. 11 das gleiche Ausgangssignal für den Fall der Aktivierung des Matrixfeld-Oszillators;

Fig.12 drei Kurven des Verlaufs der differenziellen Ausgangsspannung eines erfindungsgemäßen Matrixfeld-Oszillators nach drei verschiedenen Neustarts;

Fig.13 die Standardabweichung der differenziellen Ausgangsspannung des Matrixfeld-Oszillators nach 1000 verschiedenen Neustarts;

Fig.14 das arithmetische Mittel der differenziellen Ausgangsspannung des Matrixfeld-Oszillators nach 1000 verschiedenen Neustarts;

Fig.15 die Häufigkeitsverteilung von Byte-Werten bei einer vom Zufallszahlengenerator erzeugten Datenmenge, die bei 100.000 Neustarts mit jeweils 125-Byte- bzw. 1.000-Bit-Datenblöcken entstanden ist, ohne Wartezeit nach jedem Neustart;

Fig.16 die gleiche Häufigkeitsverteilung, wenn die Daten erst nach einer Wartezeit von 45 Mikrosekunden nach jedem Neustart aufgezeichnet werden.

Ein wesentlicher Teil der Erfindung sind sogenannte XOR-Mini-Oszillatoren, die zu sogenannten Matrixfeld-Oszillatoren oder Matrizen M zusammengeschaltet werden. Die Fig. 1 zeigt den Aufbau eines XOR-Mini- Oszillators 100. Der hier dargestellte Oszillator 100 ist zur Verwendung in einer zweidimensionalen Matrix M vorgesehen. Er verfügt daher über vier Eingänge, an die die vier Ausgangssignale der jeweils in der Matrix M benachbarten Oszillatoren angeschlossen sind: t (top): hier ist der Ausgang des in der Matrix oberhalb gelegenen Oszillators angeschlossen b (bottom): hier ist der Ausgang des in der Matrix unterhalb gelegenen Oszillators angeschlossen

I (left): hier ist der Ausgang des in der Matrix links gelegenen Oszillators angeschlossen und r (right): hier ist der Ausgang des in der Matrix rechts von dem Oszillator 100 gelegenen Oszillators angeschlossen.

Jeweils zwei der Eingänge sind auf ein Exklusiv-Oder-Gatter geführt:

Die Eingänge t und b sind mit dem Exklusiv-Oder-Gatter 102 verbunden, die Eingänge I und r sind mit dem Exklusiv-Oder-Gatter 104 verbunden. Die Ausgänge der beiden Gatter 102, 104 sind wiederum mit den beiden Eingängen eines weiteren nachgeschalteten Exklusiv-Oder-Gatters 106 verbunden. Dessen Ausgang ist mit einem Eingang eines Multiplexeres 108 verbunden. Der Multiplexer 108 verfügt über zwei Eingänge, die mittels des Signals s[1] umgeschaltet werden können. Damit kann der Oszillator ein- und ausgeschaltet werden, indem zum Einschalten das Signal s[1] so belegt wird, dass der Multiplexer 108 den Eingang durchschaltet, an dem das Exklusiv- Oder-Gatter 106 angeschlossen ist. Im ausgeschalteten Zustand wird der Eingang durchgeschaltet, an dem das Signal s[0] liegt. Dieses Signal ist üblicherweise auf 0 gesetzt, lediglich bei einem speziellen Oszillator in der Matrix M, dem Oszillator „Start“, der als Ort der Anregung für die Oszillatoren der Matrix M dient, wird dieses Signal zum sicheren Anlaufen des Oszillators während des Einschaltvorgangs kurzfristig auf 1 gesetzt, bevor dann der Multiplexer 108 auf den Eingang umgeschaltet wird, der mit dem Ausgang des Exklusiv-Oder-Gatters 106 verbunden ist.

Im normalen Fall stellt der Ausgang des Multiplexes 108 das Ausgangssignal des Oszillators 100 dar. Lediglich bei einem speziellen Oszillator in der Matrix ist noch ein Inverter 110 zwischen den Ausgang des Multiplexes 108 und den endgültigen Ausgang o (out) geschaltet.

Zur Gewährleistung der statistischen Eigenschaften und der Portierbarkeit des Zufallszahlengenerators soll die Logik-Struktur dieser Schaltung strikt eingehalten werden. Der gestrichelte Inverter 110 ist optional, d.h. er ist als der Teil der Individualisierung eines Matrixfeld-Oszillators M am Ausgang nur eines XOR-Mini-Oszillators 100 eines Matrixfeld-Oszillators M implementiert. Er dient der Vermeidung der Gefahr eines ungewollten Stillstandes oder von periodischen Oszillationen eines Matrixfeld-Oszillators M.

Die Grundüberlegungen für die Wahl dieser Grundstruktur werden im Folgenden erläutert. Das Oszillator-Verhalten bei der Zusammenschaltung von mehreren XOR-Mini-Oszillatoren 100 wird durch folgende Betrachtungen deutlich. Dabei werden zwei XOR-Mini-Oszillatoren 100 miteinander verbunden. Die Fig. 2 zeigt zwei benachbarte XOR-Mini-Oszillatoren 100. Bei s[1:0] = 10 stellt der Pfad, der mit den Buchstaben A bis F gekennzeichnet ist, einen Rückkopplungspfad dar. Dieser Rückkopplungspfad bildet bei bestimmten Werten der Eingänge eine Inverter-Funktionalität, die ähnlich einem rückgekoppelten Inverter zu einem Oszillator-Verhalten führt. Die Tabelle 1 zeigt, für welche Wertekombinationen der Eingänge der Rückkopplungspfad eine Inverter-Funktionalität aufweist. Hierbei ist zu beachten, dass bei der Hälfte aller möglichen Wertekombinationen (32 von 64) eine Inverter-Funktionalität des Rückkopplungspfades und damit ein Oszillator-Verhalten auftritt. Außerdem ist zu beachten, dass bei dem Ausführungsbeispiel nicht nur zwei sondern 36 XOR-Mini-Oszillatoren 100 zu einem sogenannten Matrixfeld-Oszillator M zusammengeschaltet werden. Sie werden so miteinander verbunden, dass jeder XOR-Mini-Oszillator 100 vier Nachbar-XOR-Mini-Oszillatoren 100 hat. D.h. jeder XOR-Mini-Oszillator 100 hat grundsätzlich vier Möglichkeiten einen Rückkopplungspfad zu bilden und Oszillator-Signale zu erzeugen.

Tabelle 1 : Wertekombinationen der Eingänge zweier benachbarter XOR-Mini- Oszillatoren 100 mit einer Inverter-Funktionalität im Rückkopplungspfad

Eine weitere interessante Grundüberlegung sind die grundsätzlichen Eigenschaften der XOR-Operation y = x @z hinsichtlich gewichteter und ungewichteter Zufallssequenzen. Falls beide Eingangsvariablen x und z statistisch unabhängig sind und die Wahrscheinlichkeiten P (x=l), P (z=l) und P (y=l), als P _x , P _z und P _y bezeichnet werden, dann ist die Ausgangswahrscheinlichkeit P _y der XOR-Operation:

P _y = (l - P _x ) P _z + P _x (l - P _z ) (1)

Die Gleichung (1 ) kann wie folgt umgeformt werden:

Der absolute Betrag der Differenz zwischen der Signalwahrscheinlichkeit und der idealen Wahrscheinlichkeit von 0,5 ist ein Maß für die Ähnlichkeit einer binären Variablen mit einer idealen binären zufälligen Variablen: 1

Da 0 < 2 — a

2 < 1 für 0 < a < 1 und a y 0,5 ist, kann die folgende

Ungleichung hergeleitet werden. für 0 < P _x , P _z < 1 und P _x , P _z 0,5. (4)

In diesem Fall hat eine Folge am Ausgang der XOR-Operation eine größere Ähnlichkeit zu einer nicht gewichteten (pseudo-)zufälligen Folge als die beiden Eingangsfolgen. In diesem Kontext hat die XOR-Operation also die Eigenschaft, den Grad von Zufälligkeit zu erhöhen. Eine Schaltung von einer Vielzahl von verknüpften XOR-Gattern verstärkt diese beschriebenen Eigenschaften. Im Sonderfall P _x = 0,5 gilt gemäß Gleichung:

Dieser Sonderfall impliziert für die XOR-Operation, dass bei einer (pseudo-) zufälligen Eingangsgröße mit der Signalwahrscheinlichkeit 0,5 die Ausgangsgröße ebenfalls (pseudo-)zufällig mit der Signalwahrscheinlichkeit 0,5 und unabhängig von der zweiten Eingangsgröße ist. Falls beide Eingangsgrößen x und z (pseudo-)zufällig mit P _x = P _z = 0,5 und statistisch voneinander unabhängig sind, ist die Ausgangsgröße ebenfalls (pseudo-) zufällig mit P _y = 0,5 und sowohl von dem einen als auch den anderen Eingang statistisch unabhängig.

Die in diesen zwei Grundüberlegungen beschriebenen Funktionalitäten und Eigenschaften treten In der Realität nicht in Reinform auf. In der asynchronen Schaltung der Matrixfeld-Oszillatoren M vermischen sie sich, es bilden sich Undefinierte Zwischenzustände (Metastabilität) und es tritt analoges Verhalten, u.a. chaotische Oszillationen an den Ausgängen der Matrixfeld- Oszillatoren M, auf. Dieses analoge Verhalten hat sowohl pseudo- als auch echt zufällige Eigenschaften. Der echt zufällige Anteil am Verhalten wird wesentlich von den unvorhersehbaren Veränderungen von Verzögerungszeiten der Schaltungselemente verursacht und bestimmt, die vom elektronischen Rauschen beeinflusst werden. Um diesen echt zufälligen Einfluss gegenüber dem pseudozufälligen Einfluss nachhaltig zu erhöhen, werden erfindungsgemäß die Anzahl der Verbindungen und damit auch der Rückkopplungen (Oszillator-Verhalten) möglichst effizient vergrößert. Durch die komplexen Rückkopplungsstrukturen breiten sich kleine zufällige Variationen schnell über den ganzen Matrixfeld-Oszillator M aus und das macht die Extraktion von Zufälligkeit durch Abtastung einfacher.

Der Einfluss des echt zufälligen elektronischen Rauschens wird durch die gewählte Schaltungsstruktur erheblich verstärkt. Dies ist die dritte Grundüberlegung. Alle drei Grundüberlegungen führen zu der Schaltung der Matrixfeld-Oszillatoren M bestehend aus einem Feld von sich gegenseitig beeinflussenden XOR-Mini-Oszillatoren 100. Ein Matrixfeld-Oszillator M (asynchrone Schaltung) in dem in Fig. 3 dargestellten Ausführungsbeispiel besteht aus einem zweidimensionalen 6 x 6-Feld von XOR-Mini-Oszillatoren 100, deren Ausgangssignal jeweils den Nachbar-Mini-Oszillatoren 100 in allen vier Richtungen als Eingangssignal dient.

Das Ausgangssignal o eines jeden XOR-Mini-Oszillators 100 wird an die entsprechenden Eingänge der vier Nachbar-Mini-Oszillatoren 100 angelegt. Die Ausgangssignale der XOR-Mini-Oszillatoren 100 an den Rändern der Matrixfeld-Oszillatoren M werden nicht direkt als Eingangssignale zurückgeführt, sondern sie dienen als Eingangssignale für die XOR-Mini- Oszillatoren 100 an den gegenüberliegenden Rändern des jeweiligen Matrixfeld-Oszillators M (siehe Fig. 4). Fig. 5 zeigt die Nummerierung der Elemente in einem Matrixfeld-Oszillator in Form (Zeile, Spalte).

Tabelle 2: beispielhafte Individualisierung der Matrixfeld-Oszillatoren

Zur Gewährleistung der Individualität und der Unabhängigkeit der Matrixfeld- Oszillatoren M muss bei der Wahl des Ortes der Anregung (Start), des zusätzlichen Inverters (Inv) und des Ausgangs (Out) darauf geachtet werden, dass sie sich in einem einzelnen Matrixfeld-Oszillator M und als Ser- Kombination in allen Matrixfeld-Oszillatoren M des Zufallszahlengenerators unterscheiden. Es soll also nie der gleiche Oszillator als Ort der Anregung (Start), als Oszillator mit zusätzlichem Inverter (Inv) oder als Ausgangs- Oszillator (Out) dienen. Vielmehr sollen diese Aufgaben durch jeweils separate Oszillatoren wahrgenommen werden. Die Individualisierung der Matrixfeld-Oszillatoren M in dem Ausführungsbeispiel zeigt Tabelle 2. Der rein asynchrone Matrixfeld-Oszillator M ist deaktiviert, wenn die Steuereingänge der XOR-Mini-Oszillatoren 100 alle s[1 :0] = 00 sind. In diesem Fall sind alle Ausgänge o der XOR-Mini-Oszillatoren 100 andauernd gleich logisch null (0). Die einzige Ausnahme bildet der XOR-Mini-Oszillator Inv mit dem zusätzlichen Inverter 110 am Ausgang. Hier ist der Ausgang konstant logisch eins (1). Der Matrixfeld-Oszillator M wird aktiviert, indem die Steuereingänge der XOR-Mini-Oszillatoren 100 alle s[1:0] = 10 gesetzt werden. Die einzige Ausnahme bildet der XOR-Mini-Oszillator Start. Hier wird der Steuereingang kurzzeitig s[1 :0] = 01 gesetzt, um den Matrixfeld-Oszillator M mit einem Ausgangswert von logisch eins (1) direkt anzuregen. Nach der erfolgten Anregung wird auch dieser Steuereingang auf s[1:0] = 10 gesetzt. Eine indirekte Anregung findet auch durch den XOR-Mini-Oszillator Inv mit dem zusätzlichen Inverter 110 statt. Der Ausgang des XOR-Mini-Oszillators Out stellt gleichzeitig den Ausgang des Matrixfeld-Oszillators M dar.

Die Steuersignale der einzelnen XOR-Mini-Oszillatoren 100 werden durch die beiden Eingangssignale enable und Start bestimmt (siehe Tabelle 3). Diese beiden Eingangssignale nehmen bei der Aktivierung des Matrixfeld- Oszillators M ausgehend von logisch null (0) gleichzeitig den Wert logisch eins (1) an. Während das enable-Eingangssignal diesen Wert für die Dauer der Aktivierung des Matrixfeld-Oszillators M beibehält, geht das start- Eingangssignal relativ kurz danach wieder auf den Ausgangswert logisch null (0) zurück. Durch das Setzen des Eingangssignals enable auf 0 werden die Matrixfeld-Oszillatoren M deaktiviert (Ruhezustand).

Tabelle 3: Steuersignale der XOR-Mini-Oszillatoren 100

In dem Ausführungsbeispiel werden an sechs Stellen im Matrixfeld-Oszillator M die Ausgangssignale als Testsignale ausgegeben. Sie dienen als

Grundlage für die Oszillationsprüfung des jeweiligen Matrixfeld-Oszillators M. Zwei der sechs Testsignale entsprechen den Ausgangssignalen der XOR- Mini-Oszillatoren Out und Start und sind somit abhängig von der Individualisierung des jeweiligen Matrixfeld-Oszillators M. Die vier weiteren Testsignale tasten an festen Orten der Matrixfeld-Oszillatoren M die

Ausgangssignale ab (siehe folgende Tabelle).

Tabelle 4: Testsignale in den Matrixfeld-Oszillatoren M

Der Zufallszahlengenerator in dem Ausführungsbeispiel enthält als Rauschquelle 9 asynchrone Matrixfeld-Oszillatoren M. Die analogen Ausgangssignale der 9 Matrixfeld-Oszillatoren M werden in der in Fig. 6 dargestellten Schaltung digitalisiert und zum Takt der nachfolgenden synchronen Schaltung synchronisiert. Die beiden Eingangssignale

Systemtakt (clk) und asynchrones Active-Low-Reset (res_a_n) werden an die entsprechenden Eingänge der D-Flip-Flops 200 angelegt.

Beim Übergang von der asynchronen zu der synchronen Schaltung sind im Digitalisierer 20 zwei sogenannte Metastabilitäts-Flip-Flop-Stufen asynchrones Active-Low-Reset; R _s : synchrones Active-High-Reset) für die Digitalisierung erforderlich. Im Rahmen dieser Digitalisierungsschaltung 20 werden die generierten analogen Ausgangssignale (sogenannte raw random Signals) der 9 Matrixfeld-Oszillatoren M bei einem aktivierten Enable-Signal durch die erste Metastabilitäts-Flip-Flop-Stufe (9 D-Flip-Flops 200) abgetastet, mit der XOR-Kombination 210 zusammengeführt und nach der zweiten Metastabilitäts-Flip-Flop-Stufe (1 D-Flip-Flop 220) als ein digitales Signal bzw. als Orginal-Zufallssequenz (sogenannte raw random sequence) ausgegeben. Die XOR-Kombination 210 komprimiert die abgetasteten Ausgangssignale von 9 unabhängigen Matrixfeld-Oszillatoren M zu einem Signal. Dies führt dazu, dass die echte Entropie am Ausgang der XOR- Kombination 210 größer als die einzelnen echten Entropien an den Ausgängen der Matrixfeld-Oszillatoren M (vor der XOR-Kombination) ist. Die komplexen hochfrequenten Ausgangssignale (chaotische Oszillationen) der Matrixfeld-Oszillatoren M können häufige Metastabilitätseffekte in der ersten Metastabilitäts-Flip-Flop-Stufe hervorrufen und zu metastabilen Signalen nach dieser ersten Stufe führen. Erst nach der zweiten Metastabilitäts-Flip- Flop-Stufe wird eine rein digitale Zufallssequenz mit einem sehr geringen Bias kontinuierlich ausgegeben. Hier werden mehrere Kopien derselben physikalischen Rauschquelle (hier Matrixfeld-Oszillatoren), deren Abtastbits XOR-kombiniert werden, als eine einzige Rauschquelle betrachtet.

Eine zusätzliche Nachbearbeitung (post-processing) der Ausgangssequenz nach der Digitalisierung ist aufgrund der ausgezeichneten statistischen Eigenschaften der Sequenz nicht erforderlich. Allerdings soll direkt nach der Aktivierung der 9 Matrixfeld-Oszillatoren M und des Digitalisierers 20 eine bestimmte Zeit (45 ps in diesem Ausführungsbeispiel) vor Ausgabe der ersten Zufallsbits durch den Zufallszahlengenerator gewartet und die während der Wartezeit (Anlaufzeit) anfallenden Zufallsbits verworfen werden, um den noch gering vorhandenen pseudozufälligen Einfluss auf die Ausgangssequenz auf ein unbedeutendes Maß zu minimieren. Dazu ist die erfindungsgemäße Schaltung vorzugsweise noch um ein Modul 230 zur Realisierung der Wartezeit (Anlaufzeit) von 45 ps ergänzt. Das Modul 230 zur Realisierung der Wartezeit (Anlaufzeit) von 45 ps ist oberhalb des Digitalisierers in Fig. 6 angeordnet. Es basiert auf einem entsprechenden Zähler und zeigt nach Ablauf der Wartezeit (45 ps) nach Start des Zufallszahlengenerators (Voraussetzung: enable ist 1 und das asynchrone Active-Low-Reset wird nicht aktiviert) mit dem Ausgangssignal out_valid = 1 an, dass die Anlaufzeit vorüber ist und die Bits der Orginal-Zufallssequenz am Ausgang out gültig sind. Vorher ist out_valid = 0, d.h. die Bits der Ausgangsequenz am Ausgang out sollten verworfen werden.

Neben der bereits beschriebenen Aktivierung der Rauschquelle durch die beiden Eingangssignale enable und Start, lässt sich auch der Digitalisierer 20 durch das Setzen des Eingangssignals enable auf 1 aktivieren (Bedingung: keine Aktivierung des asynchronen Active-Low-Resets) und durch das Setzen des Eingangssignals enable auf 0 deaktivieren (Ruhezustand).

Im Folgenden werden die Schaltungen Oszillationsprüfung 30 und Totalausfall-Test 40 beschrieben. Als Vorbemerkung ist hier festzuhalten, dass ein fehlerhaftes Verhalten der Matrixfeld-Oszillatoren M in Form des Erzeugens einer periodischen Testsequenz wie z.B. 10101 ...01 weder bekannt noch plausibel ist, da periodische Oszillationen u.a. durch den Einsatz des zusätzlichen Inverters 110 in jedem der Matrixfeld-Oszillatoren M verhindert werden. Im Folgenden wird daher dieser Fall nicht weiter berücksichtigt.

Die Teilschaltung Flankenerkennung 300 (clk: Systemtakt; res_a_n, R^: asynchrones Active-Low-Reset; R _s : synchrones Active-High-Reset) in Fig. 7 detektiert Änderungen eines digitalisierten Testsignals.

Zu diesem Zweck wird jedes der 6 Testsignale eines Matrixfeld-Oszillators M (zur Auswahl dieser Testsignale siehe Tabelle 4) jeweils einem ersten D-Flip- Flop 310 zur Abtastung zugeführt. Der Ausgang dieses D-Flip-Flops 310 wird dem Eingang eines weiteren D-Flip-Flops 320 zugeführt. Diese beiden D- Flip-Flops 310 und 320 dienen als Metastabilitäts-Flip-Flops zur Digitalisierung und zur Synchronisierung des jeweiligen Testsignals. Der Ausgang des D-Flip-Flops 320 wird einerseits dem D-Eingang eines weiteren D-Flip-Flops 330 zugeführt, welches der zur Flankenerkennung erforderlichen Zeitverzögerung dient, und zur Erkennung der Flanke wird der Eingang des D-Flip-Flops 330 (dies entspricht dem Ausgang des D-Flip- Flops 320) einerseits und der Ausgang des D-Flip-Flops 330 jeweils dem Eingang eines Exklusiv-Oder-Gatters 340 zugeführt. Dessen Ausgangssignal „edge“ zeigt jeweils das Vorhandensein einer Flanke in dem digitalisierten Ausgangssignaltest an. Diese Ausgangssignale „edge“ dienen sodann als Eingangssignale für die Oszillationsprüfung 30.

Fig. 8 zeigt die Schaltung Oszillationsprüfung 30(clk: Systemtakt; res_a_n: asynchrones Active-Low-Reset; res_s: synchrones Active-High-Reset). Hier werten 6 Instanzen der Schaltung Flankenerkennung 300 die jeweils 6 Testsignale eines Matrixfeld-Oszillators M aus. Wenn 100 Takte lang keines der jeweils 6 digitalisierten Testsignale eine Flanke aufweist, zeigt dies das Ausgangssignal des Zählers bzw. der Schaltung Oszillationsprüfung 30 mit noedge = 1 an. Dies ein sehr deutliches Zeichen, dass der entsprechende Matrixfeld-Oszillator M nicht mehr oszilliert. Mit noedge = 0 wird angezeigt, dass der Matrixfeld-Oszillator M oszilliert (built-in oscillation health test).

Demgemäß umfasst die in Fig. 8 dargestellte Schaltung Oszillationsprüfung 30 6 Flankenerkennungsschaltungen 300 (0 bis 5), deren jeweilige Ausgangssignale „edge“ einem Oder-Gatter 32 zugeführt sind. Der Ausgang dieses Oder-Gatters 32 wird dem Rücksetz-Eingang res_s eines Zählers 34 zugeführt. Der Zähler wird mit dem Systemtakt hochgezählt, d.h. der Systemtakt liegt auf dem Zähleingang des Zählers. Wenn der Zähler überläuft, d.h. während so vieler Systemtakte, wie der Zähler zählen kann, keine Flanke entstanden ist, geht der Zähler Überlauf auf logisch 1 und wird als Signal „noedge“, also Oszillationsstörung des entsprechenden Matrixfeld- Oszillators M angezeigt. Der Zähler kann beispielsweise bei einem Dezimalzähler 100 Takte weit zählen, bis er überläuft, bei einem binären Zähler empfiehlt sich eine Zweierpotenz, beispielsweise 128. Die Überlauf- Signale des Zählers 34 „noedge“ werden dann zur Gesamtüberwachung des erfindungsgemäßen Zufallszahlengenerators einer Schaltung Totalausfall- Test 40 zugeführt.

Die Schaltung Totalausfall-Test 40 in Fig. 9 (clk: Systemtakt; res_a_n: asynchrones Active-Low-Reset) gibt das Signal tot = 1 aus, d.h. ein Totalausfall liegt vor, wenn die Oszillationsprüfungen 30 aller 9 Matrixfeld- Oszillatoren M keine Oszillation (noedge = 1) anzeigen. Die

Oszillationsprüfung 30 und der Totalausfall-Test werden kontinuierlich betrieben (Bedingung: enable = 1 und keine Aktivierung des asynchronen Active-Low-Resets). Sie sind so ausgelegt, dass ein Totallausfall auf der einen Seite relativ schnell angezeigt wird und ein falscher Alarm auf der anderen Seite extrem unwahrscheinlich ist.

Demgemäß werden alle Ausgänge „noedge“ der 9 Oszillationsprüfungsschaltungen 0 bis 8 einem Und-Gatter 42 zugeführt. Dessen Ausgang ergibt das Signal „tot“ für den Totalausfall des erfindungsgemäßen Zufallszahlengenerators.

Es folgt nun die Beschreibung des experimentellen Nachweises, dass der erfindungsgemäße Zufallszahlengenerator nicht nur funktioniert, sondern auch echt zufällige und nicht pseudozufällige Bitfolgen hoher Entropie liefert.

Im Folgenden werden die Eigenschaften eines erfindungsgemäßen echten Zufallszahlengenerators basierend auf einer Kombination von individualisierten Matrixfeld-Oszillatoren M bestehend aus sich gegenseitig beeinflussenden XOR-Mini-Oszillatoren 100 im Rahmen des beschriebenen Ausführungsbeispiels (9 individualisierte Matrixfeld-Oszillatoren M (Rauschquelle) jeweils bestehend aus einem zweidimensionalen 6 x 6-Feld von XOR-Mini-Oszillatoren 100 inkl. einem entsprechenden Digitalisierer 20 und Totalausfall-Test 40) untersucht. Dies geschieht an Hand einer Implementierung des Ausführungsbeispiels des Zufallszahlengenerators auf einem SmartFusion-Evaluationsboard mit dem SmartFusion-FPGA A2F200M3FFGG484 von Microsemi basierend auf einem VHDL-Modell. Hierbei ist zu beachten, dass die SmartFusion-FPGA-Technologie auf der ProASIC3-FPGA-Flash-Architektur beruht. Bei der Untersuchung wird nur das reine FPGA (FPGA fabric) ohne den im SOC FPGA ebenfalls vorhandenen Prozessor benutzt. Das wichtigste Ziel dieser Untersuchung ist es, zu ermitteln, in wie weit die vom Zufallszahlengenerator erzeugte Zufälligkeit echt ist. Dazu wird im Abschnitt 1.1 das Verhalten eines einzelnen Matrixfeld-Oszillators 100 und im Abschnitt 1.2 das Verhalten des gesamten Zufallszahlengenerators untersucht. In den Anhängen A, B und C sind zusätzlich Kurz-Analysen von Implementierungen des oben beschriebenen Ausführungsbeispiels des erfindungsgemäßen Zufallszahlengenerators auf einem IGLOO-FPGA (Microsemi), einem Spartan-6-FPGA (Xilinx) und einem Spartan-7-FPGA (Xilinx) dargestellt. Mit Anhang D folgt eine Kurz-Analyse einer „Frequency Injection Attack“. Im Anhang E sind einige Merkmale (Ressourcen- und Leistungsverbrauch) von Implementierungen des Ausführungsbeispiels des erfindungsgemäßen Zufallszahlengenerators aufgeführt. Schließlich zeigt der Anhang F die Ergebnisse eines Langzeit-Oszillationstests der vier Implementierungen des Ausführungsbeispiels des erfindungsgemäßen Zufallszahlengenerators.

1.1 Untersuchung eines Matrixfeld -Oszillators M

Um einen ersten Eindruck von dem Verhalten der in dem Zufallszahlengenerator enthaltenen Matrixfeld-Oszillatoren M zu bekommen, wird als erstes beispielhaft das Ausgangssignal (Standardausgang) des Matrixfeld-Oszillators 0 des erfindungsgemäßen Zufallszahlengenerators in der Zeit- und Frequenzdomäne (Spektrum) mit einem Oszilloskop aufgezeichnet. Die Fig. 10 bzw. 11 zeigt das Ausgangsignal des Matrixfeld- Oszillators 0 im Zeit- (oberer Teil der Abbildung) und im Frequenzbereich (unterer Teil der Abbildung) falls der Matrixfeld-Oszillator 0 deaktiviert (Fig. 10) bzw. aktiviert (Fig. 11) ist.

Beim Vergleich der beiden spektralen Darstellungen in den Fig. 10 und 11 erkennt man, dass der Abstand zwischen dem Rauschen des deaktivierten und des aktivierten Matrixfeld-Oszillators 0 ca. 20 dB beträgt. Das offensichtliche Vorliegen von Rauschen beim aktivierten Matrixfeld-Oszillator M hilft bei der Frage leider nicht weiter, wie groß der Anteil der echten Zufälligkeit am Rauschen ist. lm Folgenden wird ein Neustart-Ansatz verfolgt, um den Umfang der von einem Oszillator erzeugten echten Zufälligkeit zu evaluieren und analysieren. Auf diesem Weg ist es praktisch möglich, zwischen echter Zufälligkeit und Pseudozufälligkeit zu unterscheiden.

Dieser Ansatz basiert auf der Wiederholung der Experimente ausgehend von identischen Startbedingungen, d.h. man startet den Oszillator ausgehend von den gleichen Anfangszuständen aller logischen Gatter neu. Pseudozufälligkeit ist deterministisch und zeigt so identisches Verhalten bei jeder Wiederholung des Experimentes. Andererseits verhält sich echte Zufälligkeit bei jeder Wiederholung trotz identischer Startbedingungen unterschiedlich. In einem unwesentlichen Ausmaß kann echte Zufälligkeit auch in den Startbedingungen enthalten sein, die ideal nicht identisch sind.

Die Neustart-Messungen wurden mittels der bereits oben genannten FPGA- Technologie vorgenommen. Bei jedem Experiment dient der inaktive Zustand (Ausgang gleich 0) als Anfangszustand des Matrixfeld-Oszillators 0, so dass die Anfangsbedingungen im Wesentlichen identisch sind. Anstatt eines Standardausgangs wurden für den Ausgang des Matrixfeld-Oszillators 0 LVDS-Ausgänge gewählt und entsprechende Ausgangsspannungen differentiell gemessen, um die Genauigkeit der Messung zu erhöhen. In Fig. 12 sind drei von insgesamt 1000 gemessenen Kurven der differentiellen Ausgangsspannung des Matrixfeld-Oszillators 0 nach verschiedenen Neustarts dargestellt.

Man erkennt deutlich, dass sich die Verläufe der drei Kurven voneinander unterscheiden. Während sie am Anfang noch identisch oder zumindest ähnlich sind, unterscheiden sie sich im Verlauf der Darstellung der Fig. 12 immer mehr. Die Menge an Zufälligkeit in den aufgezeichneten Kurven, die relevant für die Extraktion der Entropie durch Abtastung ist, kann durch die Standardabweichung der Ausgangsspannung als eine Funktion der Zeit gemessen werden. D.h. falls die Standardabweichung relativ groß ist, dann ist die Extraktion eines Bits von echter Zufälligkeit durch Abtastung relativ leicht und zuverlässig. Ist die Standardabweichung auf der anderen Seite relativ klein, dann ist das extrahierte zufällige Bit stark gewichtet und dieser Bias wird stark von der Implementierung abhängig sein. So wurden entsprechend die Standardabweichung und das arithmetische Mittel der differentiellen Ausgangsspannung des Matrixfeld-Oszillators 0 als Funktionen der Zeit (Zeitdauer 140 ns) für die 1000 Kurven berechnet. Die Ergebnisse sind in den Fig. 13 und 14 dargestellt.

Die Ergebnisse des experimentellen Neustart-Ansatzes zeigen, dass der Matrixfeld-Oszillator 0 echte Zufälligkeit generiert. Man sieht in Fig. 13 und

14, dass nach ungefähr 25 ns der arithmetische Mittelwert und die

Standardabweichung relativ stabile Werte erreichen. Der relativ stabile Wert für die Standardabweichung ist ungefähr doppelt so groß wie die entsprechenden Werte des Fibonacci- und des Galois-Ring-Oszillators. Die Struktur des Matrixfeld-Oszillators M ermöglicht also eine robustere und zuverlässigere Entropie-Extraktion durch Abtastung als vergleichbare Oszillatoren. Aufgrund der grundsätzlich gleichen Struktur sind gleiche bzw. ähnliche Ergebnisse für die anderen Matrixfeld-Oszillatoren M zu erwarten.

1.2 Untersuchung des gesamten Zufallszahlengenerators

1.2.1 Herkömmliche statistische Tests

Für die weitere Analyse findet die Datenausgabe des Zufallszahlengenerators über eine SPI-Schnittstelle statt, da sie die angestrebte, relativ hohe Datenrate von 30 Mbit/s ermöglicht. Das FT2232H- Mini-Modul von FTDI wird dazu eingesetzt. Es stellt diese SPI-Schnittstelle zur Verfügung. Die Implementierung des Zufallszahlengenerators wird an diese Schnittstelle angepasst. Die SPI-Schnittstelle ermöglicht das Lesen von Datenblöcken bis zu einer Größe von 65536 Bytes bei einer Datenrate von bis zu 30 Mbit/s. Die Daten werden vom FT2232H-Mini-Modul zu einem Rechner über USB übertragen. Obwohl der Zufallszahlengenerator natürlich zur kontinuierlichen Datenausgabe fähig ist, können aufgrund der verwendeten SPI-Schnittstelle Daten nur blockweise ausgegeben werden. Als erster Schritt bei der Untersuchung werden die grundsätzlichen statistischen Eigenschaften des Zufallszahlengenerators mit gängigen statistischen Tests (AIS31 statistische Testsuite, NIST statistische Testsuite/NIST 800-22 und TestUOl statistischer Test von der Universität Montreal) überprüft. Die statistischen Tests werden auf Daten angewendet, die bei einer sequentiellen Datenaufnahme mit 200 62.500-Byte-bzw.

500.000-Bit-Datenblöcken (Datenrate 30 Mbit/s) entstehen. Es handelt sich dabei um Original-Zufallssequenzen nach der Digitalisierung (raw random sequence). Die dabei vom Zufallszahlengenerator bei Raumtemperatur erzeugte Gesamtdatenmenge hat eine Größe von 100.000.000 Bits (ca. 11 ,9 MB). Die Ergebnisse der statistischen Tests sind in der Tabelle 5 dargestellt.

Tabelle 5: Ergebnisse der statistischen Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten bei einer sequentiellen Datenaufnahme mit 200 62.500- Byte- bzw. 500.000-Bit-Datenblöcken (Datenrate 30 Mbit/s)

Die Tabelle 5 zeigt, dass der Zufallszahlengenerator alle durchgeführten statistischen Tests besteht. Die zweite Spalte der Tabelle 5 enthält das Ergebnis des Entropie-Tests über ein Byte. Hierbei ist zu beachten, dass die AIS31 -Testsuite mit Shannon-Entropieschätzung arbeitet. Der Wert für die Shannon-Entropie pro Byte in der zweiten Spalte von Tabelle 5 ist größer als der Maximalwert von 8 Bit. Dies liegt an Rundungsfehlern in der Berechnung durch das AIS31 -Analysewerkzeug. Der Entropie-Wert in der besagten Spalte ist größer als 7,976 Bit Shannon-Entropie pro Byte. D.h. die Shannon- Entropie pro Bit ist in diesem Fall größer als 0,997 Bit. Somit werden die entsprechenden Anforderungen von AIS20/31 erfüllt.

AIS20/31 fordert, dass die AIS31 statistische Testsuite bei allen relevanten Umweltbedingungen bestanden wird. Daher wird der Zufallszahlengenerator Temperaturtests in einem bestimmten Temperaturbereich unterzogen. Es wird hier wieder die sequentielle Datenaufnahme bei grundsätzlich unveränderten Testbedingungen (außer Temperatur) durchgeführt. Das heißt, bei jeder der unterschiedlichen Temperaturen (von -25 °C bis +55 °C in Schritten von 5 °C) werden 200 62.500-Byte- bzw. 500.000-Bit- Datenblöcke empfangen. Dies ergibt wieder jeweils eine Gesamtdatenmenge von jeweils 100.000.000 Bits (ca. 11 ,9 MB). Jede dieser Gesamtdatenmengen wird mit der AIS31 statistischen Testsuite getestet. Die Ergebnisse sind in der Tabelle 6 dargestellt. Tabelle 6: Ergebnisse der Tests mit der AIS31 statistischen Testsuite von durch den Zufallszahlengenerator bei verschiedenen Temperaturen erzeugten Daten bei sequentieller Datenaufnahme mit 200 62.500- Byte- bzw. 500.000-Bit-Datenblöcken (Datenrate 30 Mbit/s)

Die Ergebnisse der Untersuchungen in Tabelle 6 ergeben wieder, dass die Entropie-Werte stets größer als 7,99 Bit Shannon-Entropie pro Byte bzw. 0,99875 Bit Shannon-Entropie pro Bit sind und somit die Anforderungen von AIS20/31 erfüllen. In mehreren Fällen sind die Werte für die Shannon- Entropie pro Byte in der zweiten Spalte von Tabelle 6 größer als der Maximalwert von 8 Bit. Wie schon vorher erwähnt, liegt dies an Rundungsfehlern in der Berechnung durch das AIS31 -Analysewerkzeug. Die dritte Spalte der Tabelle 6 zeigt, dass alle Tests der AIS31 -Testsuite bei allen Temperaturen im untersuchten Temperaturbereich bestanden werden. Dies gilt sogar für die niedrigen Temperaturen. Hierbei ist zu betonen, dass es sich bei den untersuchten Daten um Original-Zufallssequenzen nach der Digitalisierung (raw random sequences) handelt.

1.2.2 Statistische Tests im Rahmen von experimentellen Neustart- Untersuchungen

Trotz der Ergebnisse von Abschnitt 1.1 kann nicht ausgeschlossen werden, dass noch vorhandene Pseudozufälligkeit die Entropie-Extraktion durch Abtastung negativ beeinflusst. Eine weitere Untersuchungsmethode ist notwendig, um eine Aufklärung darüber zu erhalten, ob die vom gesamten Zufallszahlengenerator erzeugte Zufälligkeit nach der Digitalisierung noch signifikantem pseudozufälligen Einfluss unterliegt. Der Ansatz für diese neue Analysemethode auf der Ebene des Gesamt-Zufallszahlengenerators leitet sich vom experimentellen Neustart-Ansatz auf der Ebene eines Matrixfeld- Oszillators M aus Abschnitt 1.1 ab. Anstatt die analogen Signale vor der Digitalisierung (raw random Signals) werden die Original-Zufallssequenzen nach der Digitalisierung (raw random sequence) bei Neustarts für unterschiedlich lange Zeitabschnitte aufgezeichnet und mit herkömmlichen statistischen Tests analysiert. Die Analyse erfolgt, indem die verschiedenen Datensequenzen in Form von Datenblöcken zu einer Gesamtdatenmenge zusammengesetzt werden, die dann mit gängigen statistischen Tests (AIS31 statistische Testsuite, NIST statistische Testsuite/NIST 800-22 und TestUOl statistischer Test von der Universität Montreal) geprüft werden. Die Grundidee dabei ist, dass auch bei einer durch Neustarts erzeugten Datenmenge die statistischen Tests bestanden werden müssen. Denn bei Vorliegen einer echten Zufallsgenerierung durch den Zufallszahlengenerator müssen die statistischen Eigenschaften der Datenmenge unabhängig davon sein, ob sie durch eine sequentielle Datenaufnahme oder durch Datenblöcke bei einer Reihe von Neustarts entsteht. Andererseits werden die durch eventuell noch vorhandene Pseudozufälligkeiten verursachten Unzulänglichkeiten wie Bias und statistische Abhängigkeiten durch die sehr anspruchsvollen und komplexen statistischen Tests bei diesem Ansatz erkannt. Treten mehrere Fehler in den Tests auf, ist die Wahrscheinlichkeit groß, dass die Pseudozufälligkeit signifikanten Einfluss auf die Original- Zufallssequenzen nach der Digitalisierung hat. Im fehlerfreien Fall ist der Einfluss der Pseudozufälligkeit vernachlässigbar gering. Dieses Verfahren hat den Vorteil, zum einen kleinere Datenblöcke über kürzere Zeitintervalle, aber auch größere Datenblöcke über längere Zeitintervalle untersuchen zu können.

Dieser neue Ansatz verspricht einen einfachen aber umfassenden Überblick, ob der Zufallszahlengenerator echte Zufälligkeit ohne signifikanten Einfluss von Pseudozufälligkeit bei der gegebenen Datenrate erzeugt oder nicht. Zur Demonstration der effektiven Wirkungsweise wird diese neue Methode bei dem Zufallszahlengenerator zweimal angewendet, beim ersten Mal ohne und beim zweiten Mal mit einer Wartezeit direkt nach dem Neustart, in der die Zufallsbits verworfen werden. Erst nach der Wartezeit werden die Zufallsbits nicht mehr unterdrückt, sondern ausgegeben. Zuerst wird die neue Testmethode beim Zufallszahlengenerator ohne Wartezeit nach jedem Neustart angewendet. Es werden hierbei 100.000 Neustarts mit jeweils 125-Byte-bzw. 1.000-Bit-Datenblöcken (Original- Zufallssequenzen direkt nach der Digitalisierung (raw random sequence)) mit einer Datenrate von jeweils 30 Mbit/s bei Raumtemperatur durchgeführt. Einen ersten Eindruck von den Eigenschaften der entsprechenden Gesamtdatenmenge gibt die Häufigkeitsverteilung von Byte-Werten. Sie wird in Fig. 15 dargestellt.

Die ungleichmäßige Häufigkeitsverteilung der Byte-Werte in Fig. 15 ist offensichtlich. Die relativen Häufigkeiten bis einschließlich dem schwarzen Strich L (Byte-Wert 0x3 F) betragen im Wesentlichen jeweils 0,40% und danach jeweils 0,38% bzw. 0,39%. Da sich die Datenmenge aus 100.000 1000-Bit-Datenblöcken nach 100.000 Neustarts zusammensetzt, deutet dies auf einen noch vorhandenen pseudozufälligen Einfluss auf den Zufallszahlengenerator hin. Dieser pseudozufällige Einfluss zeigt sich auch bei der weiteren statistischen Analyse der obigen Datenmenge. Während bei der AIS31 statistischen Testsuite überraschenderweise alle Tests mit dieser Datenmenge noch bestanden werden, trifft das für die beiden anderen angewendeten statistischen Tests nicht zu.

- NIST Statistical test suite/NIST 800-22 (sts-2.1.2): nicht bestanden (nicht bestandene Tests wie folgt)

Frequency

CumulativeSums

Runs

NonOverlappingTemplate

- TestUOl statistischer Test, Unversität Montreal (TestUOl 1.2.3):

Alphabit-Batterie: nicht bestanden (nicht bestandene Tests wie folgt) MultinomialBitsOver (L = 2)

MultinomialBitsOver (L = 4) MultinomialBitsOver (L = 8)

Hamminglndep (L = 16)

Hamminglndep (L = 32)

RandomWalkl H (L = 64) RandomWalkl M (L = 64)

RandomWalkl J (L = 64)

RandomWalkl H (L = 320)

RandomWalkl M (L = 320)

RandomWalkl J (L = 320) RandomWalkl R (L = 320)

Rabbit-Batterie: nicht bestanden (nicht bestandene Tests wie folgt)

Fourier3

PeriodslnStrings HammingWeight

Hamminglndep (L = 16)

Hamminglndep (L = 32)

Hamminglndep (L = 64)

AutoCor Run of bits

Run of bits RandomWalkl H RandomWalkl M RandomWalkl J RandomWalkl H (L = 1024)

RandomWalkl M (L = 1024)

RandomWalkl J (L = 1024)

RandomWalkl H (L = 10016)

RandomWalkl M (L = 10016) RandomWalkl J (L = 10016)

Eine Lösung dieses Problems erhält man, wenn man sich die Erkenntnisse aus Abschnitt 1.1 vergegenwärtigt. Je länger man wartet, desto echt zufälliger ist der Zustand der Matrixfeld-Oszillatoren M. So wird bei der zweiten Durchführung die neue Testmethode (Neustart-Methode mit direkt nach der Digitalisierung gesammelten Daten) unter gleichen Bedingungen wie beim ersten Experiment auf einen Zufallszahlengenerator angewendet, der eine Wartezeit von 45 ps direkt nach jedem Neustart aufweist. Erst nach der Wartezeit werden Zufallsdaten ausgegeben. Nun liegt eine geänderte Häufigkeitsverteilung der Byte-Werte der Gesamtdatenmenge, wie Fig. 16 zeigt, vor. Die Häufigkeitsverteilung der Byte-Werte ist nun wesentlich gleichmäßiger. Es gibt jetzt keine auffällige Stufe mehr bei dem Byte-Wert 0x3 F (schwarzer Strich L). Die relativen Häufigkeiten betragen im Wesentlichen jeweils 0,39%. Der pseudozufällige Einfluss auf den Zufallszahlengenerator wurde durch die Einführung der Wartezeit offensichtlich entscheidend reduziert. Das Verschwinden eines signifikanten pseudozufälligen Einflusses, d.h. der Zufallszahlengenerator erzeugt nur noch reine echte Zufälligkeit, zeigt auch die statistische Analyse weiterer Neustart-Versuche mit unterschiedlicher Datenblockgröße und Anzahl von Neustarts bei Raumtemperatur, bei einer Datenrate von 30 Mbit/s und ebenfalls gleichen Gesamtdatenmenge von jeweils 100.000.000 Bits (ca. 11,9 MB).

Tabelle 7: Ergebnisse der statistischen Tests von durch den Zufallszahlengenerator bei verschiedenen Neustart-Bedingungen bei Raumtemperatur erzeugten Daten bei einer Wartezeit von 45 ps nach jedem Neustart Die Ergebnisse dieser Untersuchungen zeigt die Tabelle 7. Die zweite Spalte der Tabelle 7 enthält die Ergebnisse des Entropie-Tests über ein Byte. Teilweise sind die Werte für die Shannon-Entropie pro Byte größer als der Maximalwert von 8 Bit aufgrund von Rundungsfehlern. Die Entropie-Werte in der besagten Spalte sind alle größer als 7,976 Bit Shannon-Entropie pro Byte. D.h. die Shannon-Entropie pro Bit ist in allen Fällen größer als 0,997 Bit. Somit werden die entsprechenden Anforderungen von AIS20/31 erfüllt. Die Ergebnisse dieser umfangreichen Neustart-Tests zeigen, dass trotz der gleichen Anfangsbedingungen bei den Neustarts dieser Zufallszahlengenerator Daten liefert, die die genannten statistischen Tests erfüllen. Dies gilt sogar für Daten, die aus relativ kleinen Datenblöcken (1000 Bit Sequenzen) zusammengesetzt sind und bei einer sehr großen Anzahl von Neustarts (100.000) generiert wurden. Dies ist ein klarer Nachweis, dass reine echte Zufälligkeit von dem Zufallszahlengenerator generiert wird. Die einzige Bedingung dafür ist, dass eine Wartezeit (Anlaufzeit) von 45 ps direkt nach jedem Neustart vor Ausgabe des ersten Zufallswertes bei Verwerfen der vorherigen Daten eingehalten wird. Diese Anlaufzeit wird bei allen Untersuchungen in diesem Dokument, die den Gesamt- Zufallszahlengenerator betreffen, berücksichtigt. Die einzigen Ausnahmen bilden die Untersuchungen am Anfang dieses Abschnitts 1.2.2, die explizit ohne Wartezeit nach jedem Neustart durchgeführt wurden.

1.2.3 Tests gemäß NIST SP800-90B

Eine abschließende Prüfung der Eigenschaften des Zufallszahlengenerators ermöglichen die Min-Entropie-Tests und Neustart-Tests (restart tests) des relativ neuen Standards NIST SP800-90B. Die Min-Entropie-Tests bestehen aus zwei Pfaden: HD (independent and identically distributed) und Nicht-I ID. Aufgrund der bisherigen Untersuchungsergebnisse wird im Folgenden der IID-Pfad beschritten. D.h. es wird davon ausgegangen, dass die Entropie- Quelle unabhängig identisch verteilte Zufallszahlen generiert. Zuerst wird die initiale Min-Entropie-Schätzung (H ₀ hginai) it dem Min-Entropie-Test ermittelt, dann werden die Neustart-Tests durchgeführt. Die ersten 10 ⁶ Bits der Original-Zufallssequenzen nach der Digitalisierung (raw random sequence) nach einer Wartezeit von 45 ps nach Start entsprechend der bereits beschriebenen sequentiellen Datenaufnahme (siehe Abschnitt 1.2.1) dienen als Datenmenge für den Min-Entropie-Test. Zur Generierung der Datenmenge für die Neustart-Tests werden 1000 Neustarts bei Raumtemperatur durchgeführt. Es werden jeweils 1000 Bits der Original- Zufallssequenzen nach der Digitalisierung (raw random sequence) nach einer Wartezeit von 45 ps nach jedem Neustart aufgezeichnet. Das ergibt ebenfalls eine Datenmenge von 10 ⁶ Bits, auf die die Neustart-Tests angewendet werden. Die Ergebnisse der Tests gemäß NIST SP800-90B sind in der Tabelle 8 dargestellt. Sie zeigen, dass sich die anfängliche IID- Annahme durch die Tests bestätigt. So werden auch die Neustart-Tests für diese Annahme bestanden. Der ermittelte Wert für die Min-Entropie pro Bit ist mit 0,993767 Bit sogar nach den Neustart-Tests unverändert sehr hoch. Dieser Wert ist sehr nah an dem maximal möglichen Wert von 1 Bit, der bei Vorliegen einer ideal gleichmäßigen Wahrscheinlichkeitsverteilung auftritt. An dieser Stelle ist zu bemerken, dass NIST SP800-90B für das erfolgreiche Bestehen des Testverfahrens keinen spezifizierten Minimalwert für die geschätzte Min-Entropie fordert, wenn die Neustart-Tests bestanden werden. Tabelle 8: Ergebnisse der NIST SP800-90B Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten (Daten rate 30 Mbit/s)

Entsprechend den Untersuchungen mit der AIS31 statistische Testsuite im Abschnitt 1.2.1 wird auch hier im Rahmen der NIST SP800-90B Tests der Zufallszahlengenerator Temperaturtests in einem bestimmten Temperaturbereich unterzogen. Es wird hier wieder die Datenaufnahme bei grundsätzlich unveränderten Testbedingungen (außer Temperatur) durchgeführt. Das heißt, bei jeder der unterschiedlichen Temperaturen (von -25 °C bis +55 °C in Schritten von 5 °C) werden die vorher beschriebenen

NIST SP800-90B Tests durchgeführt. Die Ergebnisse sind in der Tabelle 9 dargestellt.

Die Ergebnisse der Untersuchungen in der Tabelle 9 ergeben wieder, dass die IID-Annahme durch alle Tests bestätigt wird. Außerdem werden auch alle Neustart-Tests für diese Annahme bestanden. Tabelle 9: Ergebnisse der NIST SP800-90B Tests von durch den Zufallszahlengenerator bei verschiedenen Temperaturen erzeugten Daten (Daten rate 30 Mbit/s)

Die Min-Entropie pro Bit nach den Neustart-Tests ist bei allen Temperaturen immer größer als 0,99 Bit und damit sehr hoch. Dies gilt sogar für die niedrigen Temperaturen. Hierbei ist wieder zu betonen, dass es sich bei den untersuchten Daten um Original-Zufallssequenzen nach der Digitalisierung (raw random sequences) handelt. Aus all diesen Ergebnissen lässt sich folgern, dass im gesamten untersuchten Temperaturbereich der erfindungsgemäße Zufallszahlengenerator als echte Entropie-Quelle von sehr hoher Qualität hier seine Bestätigung findet.

1.3. Zusammenfassung

Die Untersuchungsergebnisse sowohl auf der Ebene des Matrixfeld- Oszillators M als auch auf der Ebene des gesamten Zufallszahlengenerators zeigen, dass echte Zufälligkeit erzeugt wird. Es konnte mittels der umfassenden Neustart-Experimente gezeigt werden, dass durch die Einführung der Wartezeit (Anlaufzeit) nach jedem Neustart vor Ausgabe des ersten Zufallswertes bei Verwerfen der vorherigen Daten der pseudozufällige Einfluss auf ein unbedeutendes Maß reduziert werden kann. Weiterhin konnte nachgewiesen werden, dass der Matrixfeld-Oszillator M eine deutlich robustere und zuverlässigere Entropie-Extraktion durch Abtastung als vergleichbare Oszillatoren wie beispielsweise Fibonacci- und Galois-Ring- Oszillatoren ermöglicht. Zu betonen ist, dass alle Neustart-Experimente auf der Ebene des gesamten Zufallszahlengenerators auf Original- Zufallssequenzen direkt nach der Digitalisierung (raw random sequences) beruhen. Das heißt eine komplexe zusätzliche Nachbearbeitung (post- processing) der Daten nach der Digitalisierung ist nicht notwendig. Weiter ist zu beachten, dass diese Neustart-Untersuchungen bei einer relativ hohen Bitrate von 30 Mbit/s durchgeführt wurden. Diese Tests führen dazu, dass die Notwendigkeit von anderen aufwendigeren Wegen zum Beweis der von diesem Zufallszahlengenerator generierten echten Zufälligkeit bedeutend kleiner wird. Das heißt, die Analyse ermöglicht einen klaren Nachweis der echten Zufälligkeit, ohne dass der schwierige, aufwendige, risikobehaftete und ggf. bestreitbare Beweisansatz des stochastischen Modells (siehe AIS20/31) beschritten wird. Zusammenfassend lässt sich feststellen, dass der erfindungsgemäße Zufallszahlengenerator eine echte Entropie-Quelle von sehr hoher Qualität im gesamten untersuchten Temperaturbereich darstellt.

Anhang A. Kurz-Analyse basierend auf einem IGLOO-FPGA von

Microsemi IGLOO nano Starter kit board (AGLN-NANO-KIT) mit dem IGLOO-FPGA AGLN250V2-VQG100 von Microsemi

Tabelle 10: Ergebnisse der statistischen Tests von durch den Zufallszahlengenerator bei

Raumtemperatur erzeugten Daten bei einer sequentiellen Datenaufnahme mit 200 62.500- Byte- bzw. 500.000-Bit-Datenblöcken (Datenrate 30 Mbit/s)

Tabelle 11: Ergebnisse der NIST SP800-90B Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten (Datenrate 30 Mbit/s)

Anhang B. Kurz-Analyse basierend auf einem Spartan -6-FPGA von Xilinx

Cmod S6 board von Digilent mit dem Xifinx Spartan 6 LX4 FPGA (Spartan 6 XC6SLX4-2CPG196 FPGA)

Tabelle 12: Ergebnisse der statistischen Tests von durch den Zufallszahlengenerator bei

Raumtemperatur erzeugten Daten bei einer sequentiellen Datenaufnahme mit 200 62.500- Byte- bzw. 500.000-Bit-Datenblöcken (Datenrate 30 Mbit/s)

Tabelle 13: Ergebnisse der NIST SP800-90B Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten (Datenrate 30 Mbit/s

Anhang C. Kurz-Analyse basierend auf einem Spartan-7-FPGA von Xilinx Cmod S7 Board von Digilent mit dem Xilinx Spartan 7 FPGA (Spartan 7 XC7S25-1 CSGA225C FPGA)

Teil I - Zufallszahlengenerator: 15 Mbit/s, IF (SPI): 15 Mbit/s Tabelle 14: Ergebnisse der statistischen Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten bei einer sequentiellen Datenaufnahme mit 200 62.500- Byte- bzw. 500.000-Bit-Datenblöcken

Tabelle 15: Ergebnisse der NIST SP800-90B Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten

Teil ff - Zufallszahlengenerator: 30 Mbit/s, IF (SRI): 15 Mbit/s

Tabelle 16: Ergebnisse der statistischen Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten bei einer sequentiellen Datenaufnahme mit 200 62.500- Byte- bzw. 500.000-Bit-Datenblöcken

Tabelle 17: Ergebnisse der NIST SP800-90B Tests von durch den Zufallszahlengenerator bei Raumtemperatur erzeugten Daten

Bemerkung: Die Beschränkung der Datenrate des Interfaces (Serial Peripheral Interface - SRI) auf 15 Mbit/s ist in der Beschaltung des Xilinx Spartan 7 FPGA auf dem Cmod S7 Board begründet (Schaltgeschwindigkeit der digitalen I/Os: maximal 25 MHz).

Anhang D. Kurz-Analyse einer „Frequency Injection Attack“ basierend auf einem IGLOO-FPGA von Microsemi IGLOO nano Starter kit board (AGLN-NANO-KIT) mit dem IGLOO-FPGA AGLN250V2-VQG100 von Microsemi Auf Basis der Kenntnis der Veröffentlichung T. Markettos and S. W. Moore, The Frequency Injection Attack on Ring-Oscillator- Based True Random Number Generators, Cryptographic Hardware and Embedded Systems - CHES 2009, Lecture Notes in Computer Science, vol. 5747, Springer, Berlin, Heidelberg, pp 317-331 , 2009 wurde bei dieser Kurz-Analyse für verschiedene Frequenzen untersucht, ob die Einspeisung einer sinusförmigen Störspannung auf die Betriebsspannung eines IGLOO-FPGAs mit der Implementierung des in Abschnitt 1 beschriebenen Ausführungsbeispiels des Zufallszahlengenerators einen negativen Einfluss auf die (echten) Zufallseigenschaften der vom Generator erzeugten Daten hat. Die in den Tabellen 18 und 19 dargestellten Ergebnisse zeigen, dass das für die untersuchten Frequenzen nicht der Fall ist.

Tabelle 18: Ergebnisse der Tests mit der AIS31 statistischen Testsuite von durch den Zufallszahlengenerator bei verschiedenen Frequenzen eines Störsignals erzeugten Daten bei sequentieller Datenaufnahme mit 200 62.500-Byte- bzw. 500.000-Bit- Datenblöcken (Datenrate 30 Mbit/s)

Tabelle 19: Ergebnisse der NIST SP800-90B Tests von durch den Zufallszahlengenerator bei verschiedenen Frequenzen eines Störsignals erzeugten Daten (Datenrate 30 Mbit/s)

Anhang E. Merkmale der Implementierung des Ausführungsbeispiels (siehe Abschnitt 1) des Zufallszahlengenerators Ressourcenverbrauch

I. Beispielimplementierung SmartFusion-FPGA A2F200M3F-FGG484 auf dem SmartFusion-Evaluationsboard von Microsemi: Anzahl benötigter FPGA-Kernzellen (Core Cells): 2108

II. Beispielimplementierung Xilinx Spartan 7 FPGA (Spartan 7 XC7S25- 1CSGA225C FPGA) auf dem Cmod S7 Board von Digilent Anzahl benötigter FPGA-LUTs: 1218

Anzahl benötigter FPGA-Register (Flip-Flops): 277 Leistunqsverbrauch:

Beispielimplementierung IGLOO-FPGA AGLN250V2-VQG100 auf dem IGLOO nano Starter kit board (AGLN-NANO-KIT) von Microsemi: Leistungsverbrauch des FPGAs (Core) bei einem deaktivierten

Zufallszahlengenerator (1 ,2 V Core-Spannung):

P _off = 3,768 mW Leistungsverbrauch des FPGAs (Core) bei einem aktivierten

Zufallszahlengenerator (1 ,2 V Core-Spannung):

P _on = 64,2 mW

Anhang F. Langzeit-Osziilationstest der Implementierungen des Ausführungsbeispiels (siehe Abschnitt 1) des Zufaliszahlengenerators

Alle 4 Implementierungen des Ausführungsbeispiels (siehe Abschnitt 1) des erfindungsgemäßen Zufallszahlengenerators wurden einem Langzeit- Oszillationstest unterzogen. Dabei wird geprüft, ob während der Dauer eines Monats bei kontinuierlichem Betrieb des Zufallszahlengenerators ein oder mehrere der 9 Matrixfeld-Oszillatoren temporär oder permanent stehenbleiben bzw. nicht mehr oszillieren (100 Takte lang keine Oszillation der jeweils 6 digitalisierten Testsignale). Wenn alle 9 Matrixfeld-Oszillatoren stehenbleiben, liegt ein Totalausfall vor. Die Ergebnisse zeigt die Tabelle 20.

Tabelle 20: Ergebnisse des Langzeit-Oszillationstest für 4 Implementierungen des Ausführungsbeispiels des Zufallszahlengenerators