Vorrichtung und Verfahren zum Erzeugen einer Zufallsbitfolge

Die vorliegende Erfindung betrifft Vorrichtungen und Verfahren zum Erzeugen von Zufallsbits und Zufallsbitfolgen. Dies dient beispielsweise zur Implementierung eines Zufallszahlengenerators .

Zufallszahlen, welche in digitaler Form als Zufallsbitfolgen auftreten, werden häufig in sicherheitsrelevanten Anwendungen benötigt. Es ist beispielsweise bei asymmetrischen Authenti- fikationsverfahren notwendig, Zufallszahlen zu erzeugen und zu verwenden. Insbesondere bei RFID-Tags mit Sicherheitsfunk- tionalität sind entsprechende Zufallszahlen mit besonders niedrigem Hardwareaufwand zu generieren. Wünschenswert ist es dabei, lediglich digitale Logikschaltungen, welche aufwandsgünstig implementiert werden können, einzusetzen.

In der Vergangenheit wurden Zufallszahlengeneratoren z.B. unter Verwendung analoger Rauschquellen, deren Signale digitalisiert werden, verwendet. Hybride Analog/Digital-Schaltungen sind jedoch nur aufwändig zu implementieren.

Um echte zufällige Bitfolgen zu erzeugen, ist in der Regel eine physikalische Zufallsquelle erforderlich, die in der Regel schwierig in Computersystemen einzusetzen ist. Bei Hardware-Zufallszahlen-Generatoren wird ein physikalischer Pro- zess als Zufallsquelle verwendet. Dann muss allerdings das physikalische System über Sensoren erfasst und vermessen werden, wobei aus den gemessenen Daten anschließend die Zufallsdaten extrahiert werden können. Als Beispiele für zufallsbestimmte physikalische Prozesse seien radioaktiver Zerfall, Rauschen von Halbleitern, freischwingende Oszillatoren oder Quantenzustände von Photonen genannt. Obgleich eine gute Ran- dominisierung von Zufallsdaten damit erzielt wird, sind die notwendigen Messvorrichtungen außergewöhnlich aufwendig, so dass eine Anwendung in Massenartikeln, beispielsweise für ein einfaches Verschlüsseln von Daten auf RFID-Tags, nicht ökonomisch ist. Bei rein elektrisch arbeitenden Zufallszahlen- Generatoren ergibt sich zudem häufig das Problem, dass die korrekte Arbeitsweise davon abhängt, dass analoge Elektronik- Schaltungen auf vordefinierte Arbeitspunkte exakt eingestellt werden müssen. Daher ergeben sich Probleme bei Fertigungsstreuungen und Veränderungen der Betriebsbedingungen wie Temperatur oder anderen äußeren Einflüssen. Es ist somit nachteilig, da rein analoge Schaltkreise empfindlich gegen- über Störungen und Manipulationen sind.

So genannte Pseudo-Zufauszahlen können algorithmisch erzeugt werden. Dabei sollen die algorithmisch erzeugten Zufallsbits oder Zufallszahlen, obwohl sie eigentlich nicht zufällig sind, von echten Zufallsbits möglichst nicht zu unterscheiden sein. Bei Pseudo-Zufallsbits wird eine Mikroprozessoreinrichtung CPU (= Central Processing Unit) mit einem entsprechenden Programm betrieben, das aus einem Speicher einen so genannten Seedwert (= Samen) benötigt. Aus dem aktuellen Wert des Seeds berechnet die CPU Zufallsbits und neue Werte des Seeds, die wiederum abgespeichert werden und den alten Wert überschreiben. Um nicht dieselben Zufallsbit- oder Zahlenfolgen auf verschiedenen Geräten zu erhalten, werden die verschiedenen Geräte in einem Personalisierungsschritt auf einen individu- eilen Startwert gesetzt.

Obwohl Pseudo-Zufauszahlen für manche Anwendungen ausreichend zufällige Daten liefern, können sie physikalische Zufallszahlen nicht vollständig ersetzen. Denn zumindest für die Bestimmung eines initialen Seed-Wertes wird echter Zufall benötigt. Von dem initialen Seed-Wert ausgehend, sind die Pseudo-Zufauszahlen jedoch deterministisch. Die statistische Qualität von erzeugten Pseudo-Zufallsdaten hängt dabei stark vom verwendeten Algorithmus und der Länge des Seed-Wertes ab. Es finden beispielsweise in Standard-C-Bibliotheken Verfahren Verwendung, die Fibonacci-Generatoren verwenden. Auch rückgekoppelte Schieberegister werden teilweise für die Erzeugung von Pseudo-Zufauszahlen verwendet. Die vorgenannten Maßnah- men eigenen sich nicht für kryptographische Anwendungen. Ein Angreifer könnte zu leicht die Zufallszahlenfolge voraussagen .

Aufwändigere Verfahren verwenden kryptographisch starke Hash- Funktionen oder Verschlüsselungsverfahren, um aus einem aktuellen Seed-Wert Zufallsdaten und neue Seed-Werte zu berechnen. Um eine ausreichende Qualität bei der Erzeugung von Zufallszahlen zu erzielen, sind daher besonders leistungsfähige Ressourcen benötigende CPUs notwendig.

In der Vergangenheit wurde auch vorgeschlagen, rein digitale Zufallszahlen-Generatoren, die digitale elektrische Komponenten in integrierten Schaltkreisen aufweisen, zu schaffen. Beispielsweise wurde vorgeschlagen, die Verwendung von Jitter in Ringoszillatoren zur Zufallszahlenerzeugung zu verwenden. Digitale Ringoszillatoren werden üblicher Weise aus einer ungeraden Anzahl von Invertern, die zyklisch angeordnet bzw. miteinander rückgekoppelt sind, ausgebildet. Die Schwankungen der Periodenlängen werden dabei als Jitter bezeichnet. Allerdings ist der Jitter in der Regel klein gegenüber der Periodenlänge, so dass sich die Zufälligkeit desselben nur langsam über die Zeit akkumuliert. Um Zufallszahlen schneller zu erzeugen, sind Fibonacci- oder Gallois-Ringoszillator-Varianten vorgeschlagen worden, mittels denen schneller Zufallszahlenfolgen erzeugt werden können.

Zwar können die digital implementierten Zufallszahlen- Generatoren günstig hergestellt werden, beispielsweise als FPGAs oder in ASICs (Application specific integrated circuits = anwendungszugeschnittene integrierte Schaltkreise) , allerdings stören Fertigungsschwankungen der entsprechenden Bauteile den Prozess der Zufallszahlenerzeugung. Um statistische Defekte in den Zufallsdaten, die beispielsweise von physika- lischen Rauschquellen erzeugt werden, zu kompensieren, werden auch algorithmische Nachbearbeitungen vollzogen. Dabei werden die Messdaten komprimiert, um eine Erhöhung der Entropie zu erreichen. Um Schwankungen in der Häufigkeitsverteilung aus- zugleichen, können auch kryptographisch starke Hash- Funktionen Verwendung finden.

Insgesamt ergibt sich aus den bekannten Verfahren und Genera- toren zur Zufallsbiterzeugung bzw. die entsprechenden Hardware mäßigen Implementierungen, eine Reihe von Nachteilen, die den Einsatz in Massenprodukten in der Regel ausschließen.

Es ist daher eine Aufgabe der vorliegenden Erfindung, eine verbesserte Vorrichtung und ein Verfahren zum Erzeugen von Zufallsbits zu schaffen.

Diese Aufgabe wird durch eine Vorrichtung mit den Merkmalen des Patentanspruchs 1 und durch ein Verfahren nach Patentan- spruch 14 gelöst.

Demgemäß weist eine Vorrichtung zum Erzeugen einer Zufallsbitfolge einen mehrere invertierende digitale Einrichtung umfassenden Ringoszillator auf, an dem ein Oszillatorsignal abgreifbar ist. Es ist ein Zwischenspeicherelement zum Speichern von Pegeln des Oszillatorsignals vorgesehen, und mindestens zwei steuerbare Schalteinrichtungen sind in einem Signalpfad des Ringoszillators vorgesehen, um vorzugsweise gleichzeitig mindestens zwei Oberwellen bzw. Flanken einer Oberwelle des Ringoszillators anzuregen.

Das Zwischenspeicherelement überwacht und speichert die schwankenden Pegel des Oszillatorsignals. Da die gleichzeitig erzeugten Oberwellenflanken gegeneinander phasenverschoben sind, laufen dieselben potenziell unter statistischen Schwankungen zusammen. Die sich ergebenden Signalformen sind nicht vorhersagbar und dienen als Basis der Zufallsbiterzeugung.

Bei einem Verfahren zum Erzeugen einer Zufallsbitfolge sind die Schritte vorgesehen:

Bereitstellen eines Ringoszillators, welcher digitale Schaltelemente umfasst; Anregen von mindestens zwei Flanken einer oder mehrerer Oberwelle des Ringoszillators als Oszillatorsignal, welches zwischen zwei vorgegebenen logischen Pegeln schwankt;

Abgreifen des Oszillatorsignals; und

Ermitteln eines Zufallsbits in Abhängigkeit einer Anzahl von Pegeldurchgängen des Oszillatorsignals in einem vorgegebenen Zeitraum.

Beispielsweise kann ausgehend von einem statischen Zustand mit geeignet gewählten Anfangsbedingungen, welche durch die steuerbaren Schalteinrichtungen festgelegt werden können, ein metastabiler Schwingungszustand des Ringoszillators in Form einer Oberwelle eingestellt werden. Die Phasenlage der beiden Flanken der Oberwelle unterliegt statistischen Schwankungen. In der Regel fallen nach einem gewissen Zeitraum die beiden Flanken der Oberwelle zusammen. Hat der Ringoszillator eine gerade Anzahl von Invertern, wird er stehen bleiben. Sofern eine ungerade Anzahl von Invertern vorgesehen ist, fällt der Ringoszillator in seine Grundfrequenz und schwingt stabil weiter .

Als Zufallsbit kann beispielsweise eine Anzahl von steigenden oder fallenden Oszillatorsignalflanken innerhalb des vorgegebenen Zeitraumes verwendet werden. Insbesondere das Zwischenspeicherelement, welches zum Beispiel als Flip-Flop ausgestaltet sein kann, eignet sich zum Zählen von Signalflanken. Wird ferner diese ermittelte oder gespeicherte Anzahl einer Modulo-Operation unterzogen, ergibt sich ein zufälliges Bit.

Beispielsweise eine Steuereinrichtung kann an dem Zwischenspeicherelement mehrere Zufallsbits nacheinander ermitteln, welche dann eine Zufallsbitfolge oder eine binäre Zufallszahl liefert . In der Vorrichtung können die steuerbaren Schalteinrichtungen zum Beispiel als UND-Gatter ausgeführt werden. UND-Gatter lassen sich leicht standardisiert implementieren und dienen, je nach logischem Pegel eines Eingangssignals, als geschlos- sener Schalter oder blockieren den Signalpfad innerhalb des Ringoszillators .

Auf analoge Weise kann die steuerbare Schalteinrichtung als ODER-Gatter ausgeführt sein, wobei dann ein logischer L-Pegel zum Anschwingen der Schaltung führt.

Als eine Ausführungsform ist ferner eine Steuereinrichtung vorgesehen, welcher derart ein Startsignal für die steuerbaren Schalteinrichtungen und das Zwischenspeicherelement er- zeugt, dass jede steuerbare Schalteinrichtung jeweils eine Oberwellenflanke des Oszillatorsignals erzeugt und das Zwischenspeicherelement zurückgesetzt wird. Dadurch wird ermöglicht, dass von einem statischen Zustand aus ein metastabiler Schwingungszustand erreicht wird.

Ferner kann die Steuereinrichtung an einem Ausgang des Zwischenspeicherelements einen logischen Pegel eines Zufallsbit abgreifen, wobei das Startsignal zum Erzeugen mehrerer Zufallsbits erzeugt wird, und die mehreren Zufallsbits als Zu- fallsbitfolge von der Steuereinrichtung ausgegeben werden. Die Vorgehensweise hat zum Beispiel den Vorteil, dass keine weitere Regelschaltung erforderlich ist, um einen metastabilen Zustand des Ringoszillators aufzufinden oder aufrecht zu erhalten. Vielmehr ergibt sich durch die Erzeugung von Ober- wellen dieser metastabile Zustand, welcher als Basis für die Zufallsbiterzeugung dient.

In einer Ausführungsform ist zwischen den steuerbaren Schalteinrichtungen jeweils eine gleiche Anzahl von invertierenden digitalen Einrichtungen vorgesehen. Diese symmetrische Anordnung hat den Vorteil, dass Störeinflüsse symmetrisiert vorliegen und die statistische Zufälligkeit verbessert wird. In noch weiteren Ausführungsformen der Vorrichtung zum Erzeugen einer Zufallsbitfolge ist ein weiteres Zwischenspeicherelement derart an den Ringoszillator gekoppelt, dass parasitäre elektrische Einflüsse der Zwischenspeicherelemente sym- metrisch in Bezug auf die invertierenden digitalen Einrichtungen vorliegen. Die kapazitive Last der beispielsweise als logische Gatter ausgeführten invertierenden Einrichtungen oder Schalteinrichtungen, ist damit weitestgehend symmetrisch, so dass die jeweilige Oberwelle besonders lange erhal- ten wird und die statistisch zufällige Phasenbeziehung zwischen beiden Oberwellen günstiger ist. Das zweite Zwischenspeicherelement, beispielsweise als Flip-Flop ausgeführt, dient zum Beispiel nur der Symmetrisierung des Oszillatorteils der Schaltung, wobei dessen Ausgang nicht verwendet wird.

Die invertierenden digitalen Einrichtungen und die steuerbaren Schalteinrichtungen können als zwei logische Gatter, wie z.B. NAND-Gatter integriert werden. Ein NAND-Gatter kombi- niert einerseits eine invertierende Funktion des durchlaufenden Signals und andererseits eine Schaltfunktion, je nach Kombination der logischen Eingangssignale. Die Vorrichtung zur Erzeugung von Zufallsbits lässt sich daher besonders kompakt ausführen.

Statt der NAND-Gatters können auch NOR-Gatter verwendet werden, wobei dann der Übergang zum logische Wert H das Schwingen der Schaltung startet.

Es ist ferner denkbar, dass zwischen einem Eingang eines logischen Gatters, insbesondere eines NAND-Gatters (bzw. des NOR-Gatters) und einem Ausgang des jeweils anderen NAND- Gatters (bzw. NOR-Gatters) eine Verzögerungseinrichtung geschaltet ist. Die Verzögerungszeit durch die Verzögerungsein- richtung, beispielsweise eine Kette von Treiberschaltungen, sollte dabei länger sein als die Schaltzeit der NAND-Gatter (bzw. NOR-Gatter). Ansonsten würden die beiden Oberwellen praktisch direkt aufeinander fallen. In einer Weiterbildung ist die Vorrichtung als FPGA (= Field Programmable Gate Array bzw. im Feld programmierbare Gate- Anordnung) ausgeführt. Durch die vollständig digital imple- mentierte Vorrichtung ist eine entsprechende Programmierung besonders einfach. Ferner eignen sich die Vorrichtung und das Verfahren zur Implementierung in einem ASIC.

Die vorgeschlagene Vorrichtung und das Verfahren haben den Vorteil, dass sie schaltungstechnisch besonders einfach zu implementieren sind. Es wird nur eine geringe Anzahl von e- lektronischen digitalen Bauelementen benötigt. Damit eignet sich insbesondere ein Einsatz entsprechender Zufallszahlen- Generatoren im Massengeschäft.

Weitere vorteilhafte Ausgestaltungen der Erfindung sind Gegenstand der Unteransprüche sowie der im Folgenden beschriebenen Ausführungsbeispiele der Erfindung. Im Weiteren wird die Erfindung anhand von Ausführungsbeispielen unter Bezug- nähme auf die folgenden Figuren näher erläutert. Es zeigt dabei :

Figur 1 : ein Schaltbild einer ersten Ausführungsform einer Vorrichtung zur Erzeugung von Zufallsbitfolgen;

Figuren 2-5 mögliche Signalformen von Oszillatorsignalen und Zufallsbitsignalen;

Figur 6: ein Ersatzschaltbild für einen Ringoszillator, welcher in Ausführungsformen von Vorrichtungen zur Erzeugung von Zufallsbits eingesetzt werden kann;

Figur 7 : ein Schaltbild einer zweiten Ausführungsform einer Vorrichtung zur Erzeugung von Zufallsbitfolgen; Figuren 8, 9: mögliche Signalformen von Oszillatorsignalen; und

Figur 10: ein Schaltbild einer dritten Ausführungsform einer Vorrichtung zur Erzeugung von Zufallsbitfolgen .

In den Figuren sind gleiche oder funktionsgleiche Elemente mit denselben Bezugszeichen versehen worden, sofern nichts Anderes angegeben ist.

Figur 1 zeigt einen Zufallsbit-Generator als Vorrichtung zum Erzeugen von Zufallsbitfolgen. Der Zufallsbit-Generator 1 um- fasst einen Ringoszillator, der aus seriell verschalteten In- vertern 2-11 aufgebaut ist. Dabei ist ein oberer Zweig aus fünf Invertern 2-6 und ein unterer Zweig aus fünf Invertern 7-11 dargestellt. Die beiden Zweige sind zyklisch miteinander verschaltet, wobei als steuerbare Schalteinrichtungen jeweils ein AND- bzw. UND-Gatter 12, 13 verwendet ist. Die UND-Gatter haben jeweils zwei Eingänge 18, 19, 21, 22 und einen Ausgang 20, 23.

Jeweils ein Eingang 21, 19 der UND-Gatter 12, 13 ist über eine geeignete Leitung an eine Steuereinrichtung 50 gekoppelt, welche ein Steuersignal ST erzeugt. Der Signalpfad des Ringoszillators umfasst damit die Inverter 2-11 und die beiden UND-Gatter 12, 13. Am Signalpfad ist ein entsprechendes Oszillatorsignal OS abgreifbar.

Zum Erfassen und Speichern des Oszillatorsignals OS ist ein Zwischenspeicherelement 14, welches als Flip-Flop ausgeführt ist, gekoppelt. Das Flip-Flop 14 hat einen Takteingang 15, einen Rücksetzeingang 16 und einen Datenausgang 17. Der Rücksetzeingang 16 ist an den Steuerausgang 51 der Steuereinrich- tung 50 gekoppelt und empfängt wie die Eingänge 21 und 19 der UND-Gatter 12, 13 das Startsignal ST. Das Oszillatorsignal OS ist an den Takteingang 15 des Flip-Flops 14 geführt. An dem Datenausgang 17 des Flip-Flops 14 lässt sich ein Zufallsbit ZB abgreifen, welches an einen Eingang 52 der Steuereinrichtung 50 geführt ist.

Die Steuereinrichtung 50 erzeugt das Startsignal ST derart, dass ausgehend von den UND-Gattern 12, 13, im Signalpfad jeweils eine Flanke einer Oberwelle entsteht. Dabei durchläuft eine erste Oberwellenflanke vom Ausgang 23 des UND-Gatters 12 durch die Inverter 2-6, und eine zweite Oberwelle läuft von dem Ausgang 20 des zweiten UND-Gatters 13 durch die Inverter 7-11. Zunächst kann das Startsignal ST zum Beispiel auf logischen L-Pegel oder 0-Pegel gesetzt werden. Dann ist am Ausgang 23, 20 der UND-Gatter 12, 13 immer ein logischer L-Pegel bzw. eine 0. Eine Schwingung des Ringoszillators ergibt sich damit nicht. Wird das Startsignal ST auf logischen H-Pegel oder 1 gesetzt, arbeiten die UND-Gatter 12, 13 als geschlossene Schalter. D.h., Eingang 22 ist logisch mit dem Ausgang 23 des UND-Gatters 12 verbunden und der Eingang 18 ist logisch mit dem Ausgang 20 des UND-Gatters 13 verbunden. Gleichzeitig erfolgt ein Rücksetzen des Flip-Flops 14.

Es ergeben sich nun zwei Oberwellenflanken im Signalpfad des Ringoszillators. Beim Start liegt am Eingang des ersten In- verters 2 eine logische 1 vor. Durch die Invertierungen der Folgeinverter 3-6 ergibt sich dann am Eingang 18 des UND- Gatters 13 eine logische 0. Gleichzeitig wird eine Oberwellenflanke, ausgehend von einer logischen 1, am Ausgang 20 des UND-Gatters 13 bzw. Eingang des Inverters 7 durch die untere Inverterkette getrieben. Dies führt zu einer logischen 0 am Ausgang des Inverters 11. Somit liegen die beiden Oberwellen- flanken phasenverschoben vor. Das Oszillatorsignal umfasst daher miteinander überlagerte Flanken eines Oberwellensignals .

Durch die Überlagerung der beiden Flanken der Oberwelle ist kein stabiles logisches Signal durch das Oszillatorsignal OS gegeben. Am Takteingang 15 des Flip-Flops 14 schwankt daher ein unregelmäßiges oszillierendes logisches Signal. Das Oszillatorsignal kann in diesem metastabilen Schwingungszustand als analoges Signal mit Zufallseigenschaften aufgefasst werden .

Eine topologisch und funktional äquivalente Anordnung kann auch erreicht werden, indem in einem aus Invertern aufgebauten Ringoszillator, zwei Inverter durch NAND-Gatter ersetzt werden. Diese sollten vorzugsweise an gegenüberliegenden Positionen des Rings vorgesehen werden, um gegenüber Störeinflüssen symmetrische Signaleigenschaften zu erreichen. Es ist auch denkbar, um mehr als zwei Oberwellen zu erzeugen, mehrere steuerbare Schalter, die durch geeignete Zuführung eines Startsignals Oberwellenflanken erzeugen, vorzusehen.

Zur näheren Erläuterung der Funktionsweise der Ausführungs- form eines Zufallszahlen-Generators in der Figur 1, sind in den Figuren 2-5 Signalformen des Oszillatorsignals OS und des Zufallsbitsignals ZB über die Zeit t aufgetragen. In der Figur 2 ist beispielsweise das Oszillatorsignal am Takteingang 15 des Flip-Flops 14 über die Zeit aufgetragen. Logischer L- Pegel entspricht bei den folgenden Darstellungen von Signalkurven einem Pegel von 0 V und ein H-Pegel, also einer logischen 1, etwa 3,3 V.

Man erkennt, dass sobald das Startsignal ST auf logisch 1 ge- setzt wird, am Ausgang des Inverters 6 das Oszillatorsignal unregelmäßig zu schwingen beginnt. Man kann erkennen, dass zwei Oberwellenflanken OWl und OW2 gegeneinander verschoben und mit unterschiedlicher Amplitude im zeitlichen Verlauf vorliegen. Ab etwa 300 ns sind die beiden Flanken OWl und OW2 der Oberwelle zusammen gelaufen und schwingen stabil aus. Der Ringoszillator bleibt somit stehen.

Grundsätzlich hat ein Ringoszillator mit einer geraden Anzahl von Invertern, wie er in der Figur 1 dargestellt ist, einen Fixpunkt und bleibt nach einem gewissen Zeitraum stehen. Der Signalverlauf bis zu dem Stehenbleiben des Ringoszillators dient als Zufallsbasis für die Erzeugung des Zufallsbits. Denn das Flip-Flop 14 zählt als Taktteiler die Anzahl der Schwingungen Modulo 2. D.h. der am Datenausgang 17 vorliegende Pegel entspricht zufällig der Anzahl der sich im Signalverlauf der Figur 2 ergebenden steigenden oder fallenden Signalflanken. Ein weiteres zufälliges Element ergibt sich durch die stark schwankenden Amplituden, so dass beispielsweise im Bereich zwischen 200 und 300 ns kein wohldefinierter logischer Pegel am Eingang 15 des Zwischenspeichers bzw. Flip- Flops 14 vorliegt.

Die Figur 3 zeigt den Oszillatorsignalverlauf über die Zeit ein weiteres Mal. Die Kurve der Figur 3 entspricht einem anderen Start als dem der Figur 2. Man erkennt, dass wiederum zwei Oberwellenflanken OWl, OW2 vorliegen, die aufeinander zulaufen und nach etwa 300 ns den Oszillator in einen stabi- len Zustand führen. Allerdings unterscheiden sich die Signalverläufe der Figur 2 und der Figur 3 zufällig voneinander.

Die Figuren 4 und 5 zeigen den zeitlichen Verlauf des Zufallsbitsignals ZB am Ausgang 17 des Flip-Flops 14. Durch die zufällige Oszillatorsignalform am Takteingang 15 des Flip- Flops 14, ergeben sich sowohl logische H- als auch logische L-Pegel am Ausgang 17 des Flip-Flops 14. Die Signalform in der Figur 4 für das Zufallsbit ZB ergibt sich in zufälliger Abhängigkeit von dem Oszillatorsignal OS am Takteingang 15.

Nach einem vorgegebenen Zeitraum, beispielsweise 400 ns, wenn der Ringoszillator seinen stabilen Zustand erreicht hat, kann ein zufälliges Bit, welches im Fall der Figur 4 einen logischen H-Pegel aufweist, erfasst werden. Dies erfolgt bei- spielsweise durch die Steuereinrichtung 15, die über ihren

Eingang 52 an den Ausgang 17 des Flip-Flops 14 gekoppelt ist.

Die Figur 5 zeigt einen ähnlichen Signalverlauf. Allerdings ist der logische Pegel des sich ergebenden Zufallsbits nach 400 ns ein logischer L-Pegel der in etwa 0 V beträgt. Man kann nun beispielsweise einen Zeitraum vorgeben, in dem in der Regel der Ringoszillator, nach dem durch das Startsignal zwei Oberwellenflanken erzeugt wurden, einen stabilen Zustand erreicht. Die sich zwischenzeitlich zufällig ergebenden Signalverläufe bzw. Signalflanken dienen dem Bestimmen eines Zufallsbits. Die Güte der Zufälligkeit des erzeugten Zufallsbits ZB hängt im Wesentlichen von dem nicht determinierbaren, zeitversetzten Verlauf der erzeugten Oberwelle ab. Die beiden Oberwellenflanken durchlaufen die Ringoszillatoranordnung phasenverschoben. Dabei spielen einerseits die Schalteigenschaften, insbesondere Schaltzeiten der beiden UND-Gatter 12, 13 eine Rolle, wie auch die Verzögerungseigenschaften der In- verter 2-11.

In der Figur 6 ist daher ein Ersatzschaltbild für einen entsprechenden Ringoszillator hergestellt. In einer einfachen Ausführungsform eines Ringoszillators 100, der sich zum Ein- satz in einem Zufallsbit-Generator eignet, sind jeweils ein

Inverter 6, 11 und eine Verzögerungsstrecke 26, 27 hintereinander geschaltet. Diese beiden Verzögerungs- und Inverter- strecken werden zyklisch durch zwei Schalter 24, 25 verschaltet. Die beiden Schalter lassen sich durch ein Startsignal ST öffnen oder schließen. Dies erfolgt im Wesentlichen gleichzeitig .

Sind die beiden steuerbaren Schalter 24, 25 geöffnet, ergibt sich keinerlei Oszillation. Vielmehr liegen stabile logische Pegel am Eingang und Ausgang eines jeweiligen Inverters 6, 11 vor. Werden die Schalter jedoch geschlossen, durchläuft beispielsweise eine Signalflanke, ausgehend vom Ausgang des Inverters 6 (ein wohldefinierter H- oder L-Pegel die Verzögerungsstrecke 27 und wird durch den zweiten Inverter 11 inver- tiert. Das somit invertierte Oberwellensignal durchläuft dann erneut eine Verzögerungsstrecke 26 und wird wiederum vom Inverter 6 invertiert. Somit umlaufen zwei Oberwellenflanken im Signalpfad als Oszillatorsignal OS. Vorzugsweise sind dabei die Schaltzeiten der steuerbaren Schalter 24, 25 geringer als die Signalverzögerung durch die Verzögerungsstrecken 26, 27.

Durch Abgriff des Oszillatorsignals OS und ein Zählen der sich ergebenden Signalflanken durch die beiden überlagerten Oberwellenflanken, wird dann, wie beispielsweise hinsichtlich der Figur 1 erläutert wurde, ein Zufallsbit ermittelt. Durch mehrfaches Anstoßen der Oberwellen und Rücksetzen des entsprechenden Zwischenspeicherelementes, wie einem Flip-Flop, wird dann eine Zufallsbitfolge erzeugt.

Die Figur 7 zeigt einen Zufallsbit-Generator als Vorrichtung zum Erzeugen von Zufallsbits, bei dem invertierende Elemente in NAND-Gattern integriert sind. Der Zufallsbit-Generator 101 weist eine Kette von Treiberschaltungen 36-40 auf, die prinzipiell eine Verzögerungsstrecke darstellen. Eine zweite entsprechende Verzögerungsstrecke ist aus fünf weiteren Treibern 41-45 aufgebaut. Es ergibt sich ein oberer Zweig und ein unterer Zweig, die miteinander über ein NAND-Gatter 28 bzw. 29 verbunden sind. Die NAND-Gatter 28, 29 weisen jeweils zwei

Signaleingänge 30-33 und einen invertierenden Ausgang 34, 35 auf. Im Vergleich zur Figur 6 entsprechen die NAND-Gatter 28, 29 einer Kombination der steuerbaren Schalter 24, 25 mit jeweils einem Inverter 6, 11.

An erste Eingänge 30, 33 der NAND-Gatter 28, 29 ist ein Startsignal ST geführt. Zwischen den Ausgang 34 des ersten NAND-Gatters 28 und dem zweiten Eingang 32 des zweiten NAND- Gatters 29 ist die obere Verzögerungsstrecke aus Treibern 36- 40 geschaltet. Zwischen den Ausgang 35 des zweiten NAND- Gatters 29 und dem zweiten Eingang 31 des ersten NAND-Gatters 28 ist der untere Zweig aus den fünf Treibern 41-45 gekoppelt. Am Ausgang des Treibers 40 wird das Oszillatorsignal OS abgegriffen und an einen Takteingang 15 eines Flip-Flops 14 geführt. Ein Rücksetzeingang 16 des Flip-Flops 14 ist ebenfalls mit dem Startsignal ST verbunden, und der Datenausgang 17 des Flip-Flops liefert ein Zufallsbit ZB. Die Funktionsweise ist ähnlich hinsichtlich der in Figur 1 beschriebenen Schaltung. Sobald das Startsignal auf 1 gesetzt wird, wird das Flip-Flop 14 zurückgesetzt und am Ausgang 34 bzw. 35 der NAND-Gatter starten miteinander phasenverschobene Oberwellenflanken des sich ergebenden Ringoszillators, der im Signalpfad die NAND-Gatter 28, 29 und die Treiberschaltungen 36-45 hat. Selbst mit diesen wenigen digitalen Elementen lassen sich Zufallsbits hoher Güte erzeugen.

In der Figur 8 ist eine beispielhafte Signalform des Oszilla- torsignals OS am Eingang des Flip-Flops 14 für den Zufallsbit-Generator 101 dargestellt. Man erkennt, dass nach etwa 450 ns der Ringoszillator einen stabilen L-Pegel am Ausgang des Treibers 40 bzw. Eingang 32 des NAND-Gatters 29 hat. Dies ist der stabile Zustand für den Ringoszillator.

In der Figur 9 ist ein ähnlicher Signalverlauf für das Oszillatorsignal nach einem weiteren Start über die Zeit dargestellt. Bei dem in der Figur 9 dargestellten „Run" fallen die beiden erzeugten Oberwellen bereits früher aufeinander bzw. laufen zusammen, so dass nach bereits etwa 370 ns der stabile Zustand des Oszillators erreicht wird. Durch Zählen der sich ergebenden Signalflanken, beispielsweise in dem vorgegebenen Zeitraum zwischen 0 und 450 ns, wird dann ein Zufallsbit ZB abgeleitet, welches am Ausgang 17 des Flip-Flops 14 abgreif- bar ist.

Ferner ist in der Figur 10 eine weitere Variante eines Zufallsbit-Generators dargestellt. Der Zufallsbit-Generator 102 weist im Wesentlichen dieselben Elemente, wie in der Figur 1 dargestellt ist, auf, wobei jedoch am oberen und am unteren Zweig nur jeweils drei Inverter 2-4 und 5-7 nacheinander geschaltet sind. Auf Elemente, die in der Figur 1 bereits erläutert wurden, wird hier nicht eingegangen. Der Zufallsbit- Generator 102 weist neben einem ersten Zwischenspeicherele- ment 14 bzw. einem Flip-Flop ein zweites Flip-Flop 46 auf, welches vorzugsweise eine identische Struktur wie das erste Flip-Flops 14 hat. Der Takteingang 47 des zweiten Flip-Flops 46 ist an den Ausgang des letzten Inverters 7 in der unteren Inverterkette gekoppelt bzw. an den Eingang des ersten UND- Gatters 12. Der Takteingang 15 des ersten Flip-Flops 14 ist an den letzten Inverter 4 der oberen Inverterkette und an den Eingang des zweiten UND-Gatters 13 geführt. Das zweite Flip- Flop 46 hat ebenfalls einen Rücksetzeingang 48 an den, wie auch an den Rücksetzeingang 16 des ersten Flip-Flops 14 das Startsignal ST geführt ist.

Das zweite Flip-Flop 46 dient dabei der Symmetrisierung des Oszillatorteils der Schaltung. Der Datenausgang 49 wird nicht verwendet. Durch die erzielte symmetrische Situation bleibt eine erzeugte Oberwelle durch das erste oder zweite UND- Gatter 12, 13 besonders lange erhalten. Somit ergibt sich eine größere Anzahl von potenziell durch das Flip-Flop 14 er- fassbare Signalflanken, die zu dem Zufallsbitwert ZB führen.

Die vorgestellten Zufallsbit-Generatoren haben insbesondere den Vorteil, dass nur eine geringe Anzahl von digitalen e- lektronischen Komponenten notwendig ist, die leicht in den integrierten Schaltkreisen implementiert werden können. Ferner kann die vorgeschlagene Vorgehensweise einfach in einer gebräuchlichen Hardware-Beschreibungssprache wie VHDL beschrieben werden. Dadurch können logische Standard- Komponenten aus Zellbibliotheken zu IC-Anwendungen leicht verwendet werden. Dadurch sind die entsprechenden Komponenten auch synthetisierbar und als FPGA-Anwendungen verwendbar. Da die Zufallszahlen-Generatoren völlig digital arbeiten, sind keine analogen Schaltungskomponenten oder entsprechende Fertigungsprozesse bei der Herstellung entsprechender integrier- ter Schaltungen notwendig.

Da die Oberwellen dieselben digitalen Bauelemente des jeweiligen Ringoszillators nacheinander durchlaufen, wirken sich Änderungen durch die Umweltbedingungen oder elektrische Ei- genschaften der Elektronik in gleicher Weise auf die Signalflanken aus. Die Schwingungsvorgänge sind daher besonders robust gegenüber externen Einflüssen, hinsichtlich Fertigungsstreuungen und Alterungsvorgängen. Somit eignet sich insbesondere ein Einsatz in der Massenproduktion, beispielsweise auf RFIDs.

Obwohl die vorliegende Erfindung anhand einiger Ausführungsbeispiele erläutert wurde, ist sie nicht darauf beschränkt, sondern vielfältig modifizierbar. Insbesondere können andere als vorgestellte Anzahlen von Invertern in den Oszillatoren vorgesehen werden. Auch ist es möglich, mehr als zwei Oberwellenflanken durch geeignete steuerbare Schalter in einem Signalpfad eines Ringoszillators zu erzeugen. Dadurch ergibt sich eine weitere Randomisierung des Oszillatorsignals in dem Einschwingvorgang. Ferner ist es möglich mehrere Oberwellen unterschiedlicher Ordnung zu erzeugen und viele Oberwellen flanken als randomisierende Elemente zu verwenden. Neben den dargestellten Flip-Flops als Zwischenspeicherelemente, können auch weitere digitale Speicherformen Anwendung finden.