Beschreibung

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 immer häufiger anzutreffenden RFID-Tags 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.

Ein Zufallszahlengenerator, der praktisch ausschließlich digitale Logikschaltungen aufweist, ist in der

WO 2006/015624 Al beschrieben. In dieser internationalen Patentanmeldung wird vorgeschlagen, zufällige Phasenschwankungen von aus digitalen Gattern aufgebauten Ringoszillatoren zu verwenden. Gemäß der WO 2006/015624 Al eignen sich jedoch lediglich sehr spezielle Ringoszillatoren, nämlich Fibonacci- oder Galois-Ringoszillatoren mit besonderen Eigenschaften zum Einsatz in einen Zufallszahlengenerator. Bei einem derart aufgebauten Schaltkreis wird davon ausgegangen, dass die Ringoszillatoren keine Fixpunkte aufweisen dürfen. Diese Bedingung kann insbesondere für Fibonacci- oder Galois- Oszillatorschaltkreise durch mathematische Gleichungen dargestellt werden, die gemäß der WO 2006/015624 Al erfüllt sein

müssen. Bei einer entsprechenden Implementierung ist daher zunächst zu prüfen, ob ein Ringoszillator Fixpunkte aufweist. Nachteilig ist damit die Auswahl von in Frage kommenden Oszillatorschaltkreisen sehr eingeschränkt.

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

Diese Aufgabe wird durch eine Vorrichtung mit den Merkmalen des Patentanspruchs 1 gelöst.

Demgemäß weist eine Vorrichtung zum Erzeugen einer Zufallsbitfolge einen digitalen Ringoszillatorschaltkreis mit logi- sehen Bauelementen auf. Der Ringoszillatorschaltkreis hat einen Eingangsknoten und einen Ausgangsknoten und ist derart ausgestaltet, dass bei einem Zustandswechsels eines an dem Eingangsknoten gekoppelten logischen Startsignals eine Oszillation einsetzt. Die Oszillation kann einen Fixpunkt errei- chen. Dabei ist an dem Ausgangsknoten des Ringoszillatorschaltkreises ein Zufallssignal mit einem zufälligen Pegelverlauf abgreifbar.

Unter einem Fixpunkt wird im Folgenden verstanden, dass die logischen Bauelemente des Ringoszillatorschaltkreises einen stabilen logischen Zustand einnehmen. Dieser muss nicht zwingend während des Betriebs der Vorrichtung zum Erzeugen einer Zufallszahlenfolge eingenommen werden. Der Ringoszillatorschaltkreis ist jedoch derart ausgestaltet, dass ein stabiler Fixpunkt grundsätzlich existiert. Das Vorliegen eines entsprechenden Fixpunktes kann zum Beispiel mathematisch bestimmt werden. Vorzugsweise handelt es sich um wohldefinierte logische Zustände der Bauelemente und nicht metastabile Zustände, wobei zwar keine Oszillation des Ringoszillators auf- tritt, die jeweiligen internen Potenziale jedoch auf einem

Pegel verharren, der zwischen den den logischen Pegeln zugeordneten Potenzialen liegt.

Durch thermische oder quantenmechanische Vorgänge innerhalb der zur Implementierung des Oszillators verwendeten Halbleiterbauelemente entstehen zum Beispiel Phasenschwankungen oder Jitter, welche zufällige interne Signal- oder Potenzialver- laufe hervorrufen. Die logischen Bauelemente, beispielsweise eine ungerade Anzahl von Inverterschaltungen, können z. B. zum Ausbilden eines Ringoszillators kaskadenförmig zu einem Ring gekoppelt sein, wobei durch die ungerade Anzahl der Inverterschaltungen eine Oszillation möglich wird. In der Regel hängt die Oszillationsfrequenz von der Anzahl der verwendeten Inverter- oder Logikschaltungen ab. Durch unterschiedlich auftretende Verzögerungen bei der Signalverarbeitung durch die einzelnen logischen Bauelemente stellt sich in der Regel keine konstante Phase sondern ein Jitter ein.

Bei der vorliegenden Erfindung wird davon ausgegangen, dass das Erreichen eines Fixpunktes des Ringoszillatorschaltkreises unschädlich für den zumindest in der Anfangszeit der Oszillation auftretenden zufälligen Jitters ist. Jeder Ringos- zillatorschaltkreis weist in seinem Signalverlauf nach dessen Aktivierung bzw. Starten zufällige zeitliche Pegelverläufe auf. Diese werden berücksichtigt, um z. B. den logischen Pegel eines Zufallsbits zu bestimmen.

Die Vorrichtung zum Erzeugen einer Zufallsbitfolge hat insbesondere den Vorteil, dass sie einfach zu implementieren ist und Berechnungen, wie sie beispielsweise beim Stand der Technik zum Ausschließen eines Fixpunktes notwendig sind, nicht durchgeführt werden müssen. Als Ringoszillatorschaltkreise kommt damit eine größere Klasse von Oszillatoren in Frage.

Dabei können selbstverständlich auch Galois- oder Fibonacci- Ringoszillatoren eingesetzt werden. Ferner haben Ringoszillatoren mit Fixpunkten den Vorteil, dass bei Erreichen des Fixpunktes, was bei der vorgeschlagenen Vorrichtung zum Erzeugen einer Zufallsbitfolge für die Güte der Zufälligkeit unschädlich ist, der Energieverbrauch stark zurückgeht. Dies trifft insbesondere bei einer Implementierung der entsprechenden Schaltungsanordnungen in CMOS-Technologie zu.

Durch die besonders aufwandsgünstige Implementierung, die vorzugsweise ausschließlich digitale Bauelemente aufweist, ist eine Realisierung in der Art einer FPGA-Schaltung beson- ders günstig. Unter einem FPGA versteht man programmierbare integrierte Schaltkreise in der Digitaltechnik. FPGAs können durch eine Konfiguration interner Strukturen, die logische Gatter bilden können, "im Feld" programmiert werden (FPGA = Field Programable Gate Array) . Selbstverständlich kann die entsprechende Vorrichtung zum Erzeugen von Zufallszahlen auch als anwendungsspezifische integrierte Schaltung (ASIC = Application Specific Integrated Circuit) ausgeführt werden, zum Beispiel in CMOS.

In einer Ausführungsform der Vorrichtung ist ein an den Ausgangsknoten gekoppeltes Zwischenspeicherelement vorgesehen, welches in Abhängigkeit von dem Zufallssignal einen logischen Pegel speichert.

Es ist z. B. möglich, ein Zwischenspeicherelement als Flip- Flop auszubilden, welches beim Durchlaufen eines vorbestimmbaren logischen Schwellwertes seinen internen abgespeicherten Zustand wechselt. Bekannte Flip-Flops wechseln zum Beispiel den intern abgespeicherten logischen Zustand bei jeder stei- genden oder fallenden Signalflanke des eingekoppelten Zufallssignals. Das heißt, sofern das Zufallssignal zwischen zwei logischen Pegeln unregelmäßig schwankt, liefert das Zwischenspeicherelement einen Zufallsbitwert, der von der nicht bestimmbaren Anzahl von beispielsweise steigenden oder fal- lenden Flanken des Zufallssignals abhängt. Beispielsweise kann das Zwischenspeicherelement einen dem Zufallssignal entsprechenden logischen Pegel speichern.

Es ist dabei denkbar, dass das Zwischenspeicherelement, wie beispielsweise ein Flip-Flop, in Abhängigkeit von einem Abtastsignal einen dem Zufallssignal entsprechenden logischen Pegel speichert. Ein Abtastsignal, beispielsweise ein externes Taktsignal, führt dazu, dass zu bestimmten Zeitpunkten

der Pegel des Zufallssignals von dem Zwischenspeicherelement erfasst wird und entweder als Zufallsbit verwendet wird oder auch ein Invertieren des gespeicherten logischen Pegels im Zwischenspeicherelement hervorruft .

Durch regelmäßiges Abtasten, beispielsweise mit einem D-Flip- Flop, des Zufallssignals, insbesondere in einem Zeitraum bevor der Ringoszillator potenziell einen stabilen Fixpunkt erreicht, ist der zufällige Pegelverlauf des Zufallssignals ausreichend, um eine zufällige Verteilung der erfassten Zufallsbits zu erzielen.

Die Abtastsignalerzeugungseinrichtung ist vorzugsweise derart ausgestaltet, dass das Abtastsignal innerhalb eines vorgege- benen Zeitraums mehrere Zustandswechsel aufweist. Der vorgegebene Zeitraum entspricht zum Beispiel einem durchschnittlicher Oszillationszeitraum. Der Fixpunkt tritt üblicherweise nach einem vorhergehenden Oszillationszeitraum auf. Es kann zum Beispiel die Verteilung dieser Oszillationszeiträume ei- nes Ringoszillators durch Messungen bestimmt werden. Der vorgegebene Zeitraum ist vorzugsweise so gewählt, dass ein sub- stanzieller Anteil der Schwingungen innerhalb des Zeitraums auftritt .

Eine Abtastsignalerzeugungseinrichtung erzeugt gemäß einer

Ausführungsform mehrere Zustandswechsel für ein Abtastsignal, sodass innerhalb der durchschnittlichen Oszillationszeit das Zufallssignal an dem Ausgangsknoten mehrfach erfasst wird. Vorzugsweise wird der Ringoszillatorschaltkreis derart einge- stellt, dass dieser nicht von einem Fixpunkt aus aktiviert wird und somit während der durchschnittlichen Oszillationszeit zeitlich nicht vorhersehbare, also randomisierte, Pegelverläufe zeigt. Zufallsbits können damit durch periodisches Sampeln oder Abtasten des Zufallssignals bestimmt werden.

Ein entsprechendes Startsignal zum Neustarten des Ringoszillators kann z. B. von einer Rechtecksignalerzeugungseinrich- tung geliefert werden, welche ein Startsignal mit wechselnden

logischen Pegeln erzeugt. Insofern wird der eingesetzte Ringoszillatorschaltkreis regelmäßig neu gestartet, sodass die Gefahr des Einschwingens in einen Fixpunkt reduziert wird.

In einer bevorzugten Ausführungsform der Vorrichtung ist eine Steuerungseinrichtung vorgesehen, welche z. B. gemäß einer Programmierung ein Abgreifen eines Zufallsbitwertes an dem Ausgangsknoten oder Zwischenspeicherelement und/oder die Erzeugung des Startsignals veranlasst. Es ist damit eine Reali- sierung einer Ansteuerungsschaltung denkbar, die die Erzeugung eines einzelnen Zufallsbit immer von einem selben Startzustand des Ringoszillators beginnen lässt. Bei einem Rücksetzen oder Neustart bzw. Wiederaktivieren des Ringoszillators von diesem Startzustand und die Erzeugung eines weiteren Zufallsbit kann vorzugsweise eine Wartezeit legen, damit der Ringoszillatorschaltkreis relaxieren oder abklingen kann.

Die Erzeugung einer Zufallsbitfolge kann insbesondere durch Invertieren eines an den Ausgangsknoten angeschlossenen Flip- Flops bei jedem 0-1-Durchgang des Zufallssignals erfolgen, wobei die Zufallsbits auch durch periodisches Sampeln oder Abtasten des zwischengespeicherten logischen Pegels dieses Flip-Flops bestimmbar ist. Auch wenn der entsprechende Ringoszillator vor dem Abtasten des entsprechenden Zufallsbitwer- tes an dem Flip-Flop in einem Fixpunkt verbleibt, ist dies nicht schädlich für die Zufälligkeit des zwischengespeicherten logischen Pegels bzw. Zufallsbitwertes. Die Zufälligkeit wird dabei z. B. durch die vorher berücksichtigten 0-1- Durchgänge ausreichend berücksichtigt. Ebenso sind andere Merkmale, wie zum Beispiel 1-0-Durchgänge, des Zufallssignals verwendbar .

In einer Weiterbildung der Erfindung ist ein Zufallszahlengenerator mit einer vorbeschriebenen Vorrichtung zum Erzeugen einer Zufallsbitfolge vorgeschlagen. Dabei werden mehrere abgegriffene Pegelwerte des Zufallssignals oder von einem Zwischenspeicherelement gespeicherte logische Pegel als Bitwerte einer Zufallszahl erfasst.

Die Erfindung betrifft ferner ein Verfahren zum Erzeugen einer Zufallsbitfolge gemäß Patentanspruch 17.

Dabei werden Zufallsbitwerte in Abhängigkeit von einem Pegelverlauf eines an einem digitalen Ringoszillatorschaltkreis abgegriffenen Zufallssignals bestimmt. Der digitale Ringoszillatorschaltkreis weist dabei logische Bauelemente auf, welche derart verschaltet sind, dass durch Aktivieren des Ringoszillatorschaltkreises eine Oszillation erfolgt. Diese kann grundsätzlich aufgrund der Implementierung des Ringoszillators einen Fixpunkt erreichen, in dem die logischen Bauelemente einen stabilen logischen Zustand einnehmen.

Das entsprechende Verfahren kann z. B. durch geeignete Programmierung programmierbarer digitaler Logikschaltungen, wie beispielsweise FPGAs implementiert werden. Ein Aktivieren des Ringoszillatorschaltkreises kann zum Beispiel durch Einschalten oder Ankoppeln einer geeigneten Versorgungsspannung an die entsprechende Schaltungsanordnung erfolgen. Ferner ist ein Aktivieren entsprechend einer jeweiligen Implementierung der Ringoszillatorschaltung durch Ankoppeln eines geeigneten Steuer- oder Startsignals möglich. Unter Aktivieren ist ein Vorgang zu verstehen, der in einer Oszillation des Ringoszil- latorschaltkreises, vorzugsweise ausgehend von einem vorgegebenen Startzustand der eingesetzten Logikgatter, resultiert.

In einer Variante der Verfahrens werden dabei die folgenden Verfahrensschritte durchgeführt: Aktivieren eines digitalen Ringoszillatorschaltkreises, der einen Fixpunkt aufweist, und Abgreifen eines oder mehrerer Pegelwerte eines von dem Ringoszillatorschaltkreis erzeugten oszillierenden Zufallssignals .

Dabei kann der Ringoszillatorschaltkreis zum Erzeugen mehrerer Zufallsbitwerte mehrfach aktiviert werden. Insofern werden Situationen, in denen der Ringoszillator bereits seinen Fixpunkt erreicht zwar für die Zufallsbitfolgenerzeugung be-

rücksichtigt, jedoch wird durch den (regelmäßigen) Neustart des Schaltkreises der Einfluss auf die Zufälligkeit reduziert .

Wie bereits hinsichtlich der Vorrichtung zum Erzeugen einer Zufallsbitfolge erläutert wurde, kann das Zufallssignal mehrfach abgetastet werden und in Abhängigkeit von einem jeweiligen Pegelwert des Zufallssignals ein logischer Pegel eines Zufallsbits verändert werden. Dies kann beispielsweise durch ein Zwischenspeicherelement wie zuvor beschrieben wurde erzielt werden.

In einer weiteren Variante des Verfahrens wird zunächst eine durchschnittliche Oszillationszeit des Ringoszillatorschalt- kreises, z. B. experimentell, bestimmt. Anhand dieser durchschnittlichen Oszillationszeit, in der wahrscheinlich kein Fixpunkt des Oszillators eintritt, kann dann der Pegel des Zufallssignals mehrfach erfasst werden. Insofern wird mittels dem Verfahren zuverlässig eine Zufallsbitfolge erfasst obwohl gegenüber der weit verbreiteten Annahme, fixpunktbehaftete

Oszillatoren seien für die Zufallszahlengenerierung unbrauchbar, ein eben solcher verwendet wird.

Weitere vorteilhafte Ausgestaltungen der Erfindung sind Ge- genstand der Unteransprüche sowie der im Folgenden beschriebenen Ausführungsbeispiele.

Im Folgenden wird die Erfindung unter Bezugnahme auf die beigelegten Figuren und anhand einiger Ausführungsbeispiele nä- her erläutert. Es zeigt dabei:

Fig. 1 ein Ausführungsbeispiel eines Zufallszahlengenerators;

Fig. 2 eine erste Ausführungsform eines Ringoszillatorschaltkreises;

Fig. 3 eine zweite Ausführungsform eines Ringoszillatorschaltkreises;

Fig. 4 eine kumulative Verteilung von minimalen Oszillati- onszeiten eines Ringoszillatorschaltkreises;

Fig. 5 beispielhafte Zufallssignalpegelverläufe eines Ringoszillatorschaltkreises; und

Fig. 6 ein prinzipielles Ablaufdiagramm für ein Verfahren zum Erzeugen von Zufallsbitfolgen.

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

In der Fig. 1 ist beispielhaft ein Zufallszahlengenerator 1 dargestellt. Der Zufallszahlengenerator 1 weist einen Ringoszillatorschaltkreis 2 mit einem Eingangsknoten 3 und einem Ausgangsknoten 4 auf. Ausführungsbeispiele für Ringoszillatoren sind z. B. in den folgenden Fig. 2 und 3 näher erläutert,

Beispielsweise kann ein Ringoszillator durch kaskadierte Ver- schaltung mehrerer Inverter realisiert werden. Inverter oder auch andere logische Bauelemente dienen dabei als Verzögerungselemente, wobei nicht vorhersagbare Schwankungen der einzelnen Verzögerungszeiten nicht vorhersagbare Oszillationsvariationen, sogenannte Jitter, hervorrufen. Die Verzögerungsschwankungen beruhen in der Regel auf verschiedenen in- ternen und externen Rauschfaktoren, wie beispielsweise die Hardwareimplementierung der Bauelemente und Strom-, Span- nungs- und/oder Temperaturschwankungen. Sofern, wie es bei Inverter oder logischen Gattern der Fall ist, die Verzögerungszeit extrem kurz ist, liefern diese nichtvorhersagbaren Fluktuationen zufällige Pegelverläufe des prinzipiell oszillierenden Signals, welches an dem Ausgangsknoten 4 als Zufallssignal OS abgreifbar ist.

Der Ringoszillatorschaltkreis 2 lässt sich durch ein geeignetes Startsignal ST, welches dem Eingangsknoten 3 eingekoppelt ist, aktivieren bzw. starten. Es wird dabei angenommen, dass der Ringoszillatorschaltkreis 2 einen Fixpunkt aufweist, d. h. stabile Zustände existieren, in denen die logischen Bauelemente logische Zustände aufweisen, die sich zeitlich nicht mehr ändern. Bis zum Erreichen eines derartigen Fixpunktes erfolgt jedoch eine praktisch zufällige Veränderung der entsprechenden abgreifbaren Pegel.

Das Zufallssignal OS ist einem Zwischenspeicherelement 7, z. B. einer Flip-Flop-Einrichtung, zugeführt. Die Flip-Flop- Einrichtung 7, beispielsweise ein D-Flip-Flop, nimmt an einem Dateneingang das Zufallssignal an und liefert an einem Daten- ausgang einen zwischengespeicherten logischen Pegel als Zufallsbit ZB. Da das Zufallssignal OS zeitlich fluktuiert und zufällig schwankt, ist z. B. denkbar, dass durch Einkoppeln eines Abtastsignals, beispielsweise in der Form eines Taktsignals CLK, an einen Takteingang des Flip-Flop 7, der zum Abtastzeitpunkt also z. B. beim Vorliegen einer steigenden oder fallenden Taktflanke, gegenwärtige Wert des Zufallssignals OS erfasst bzw. zwischenspeichert wird.

Ein entsprechendes Abtast- oder Taktsignal CLK wird in der beispielhaften Darstellung der Fig. 1 durch eine Steuereinrichtung 5 geliefert. Die Steuereinrichtung 5 erzeugt ebenfalls geeignete Steuersignale CTl, um einen Rechtecksignalgenerator 6, der das Startsignal ST an den Eingangsknoten 3 des Ringoszillators 2 liefert, zu steuern.

Es sind verschiedene Ausführungsbetriebsmodi des Zufallszahlengenerators 1 denkbar. Zum Beispiel kann, wie zuvor beschrieben wurde, zu jedem Abtastzeitpunkt das Zufallssignal OS durch das Zwischenspeicherelement 7 erfasst werden und als ein Zufallsbit ZB ausgegeben werden. Dies wird beispielsweise in ein Schieberegister 8 eingeführt. Nach einer vorgegebenen Anzahl von Abtastzeitpunkten liegt damit eine Zufallsbitfolge in dem Schieberegister 8 vor. Alternativ kann, auch wenn es

in der Fig. 1 nicht explizit dargestellt ist, auch das Schieberegister durch das Taktsignal CLK angesteuert werden. An einem Ausgang 10 des Zufallszahlengenerators 1 ist dann eine binär kodierte Zufallszahl ZZ abgreifbar.

Alternativ kann das Zwischenspeicherelement oder Flip-Flop 7 auch derart ausgestaltet sein, dass bei jedem 0-1- oder auch 1-0-Durchgang des Zufallssignals OS der intern gespeicherte Wert des Zufallsbits ZB im Zwischenspeicherelement 7 geändert wird. Damit wird als zusätzliches zufälliges Element die Anzahl der Schwankungen oder Oszillationen des Zufallssignals OS zur Erzeugung eines Zufallsbits verwendet. In Abhängigkeit von dem Abtast- oder Taktsignal CLK wird dann der zufällig erzeugte Pegelzustand im Zwischenspeicherelement als Zufalls- bit ZB ausgegeben.

Es ist weiterhin denkbar, vor jeder Zufallsbiterzeugung den Ringoszillatorschaltkreis 2 zurückzusetzen bzw. erneut zu starten, um die Gefahr des Erreichens eines Fixpunktes zu re- duzieren. Vorzugsweise wird bei dem Rücksetzen oder Initialisieren des Ringoszillatorschaltkreises vorgegeben, dass der Startzustand, also die logischen Pegel aller logischen und digitalen Bauelemente, welche in dem Ringoszillatorschaltkreis 2 verwendet werden, nicht dem eines Fixpunktzustandes entsprechen.

Im Folgenden sind beispielhafte prinzipiell Fixpunkte aufweisende Ringoszillatorschaltkreise, welche sich zum Einsatz in einer Vorrichtung zur Erzeugung von Zufallsbitfolgen eignen, näher erläutert.

In der Fig. 2 ist ein Ringoszillatorschaltkreis 2 dargestellt. Dabei ist eine Verzögerungsstrecke aus sieben Inver- tern 11 - 17 aufgebaut, dem ein NAND-Gatter vorgeschaltet ist. Die Inverter sind dabei in der Schaltung als NAND-Gatter angegeben. Das NAND-Gatter 9 erhält als Eingangsgrößen ein Startsignal ST und ein Rückkopplungssignal Rl. Das Ausgangssignal des NAND-Gatters 9 ist dabei an einen Ausgangsknoten 4

des Ringoszillatorschaltkreises 2 und als Eingangsgröße einem XOR-Gatter 20 zugeführt, welches ausgangsseitig das Rückkopplungssignal Rl liefert.

Ferner ist das Ausgangssignal des letzten Inverters 17 einem Eingang eines XOR-Gatters 18 zugeführt, wobei ferner ein Rückkopplungssignal R2, welches dem Ausgangssignal des vierten Inverters 14 entspricht, zugeführt ist. Einem weiteren XOR-Gatter 19 sind das Ausgangssignal des ersten Inverters 11 sowie das Ausgangssignal des XOR-Gatters 18 zugeführt. Das das Rückkopplungssignal Rl bildende XOR-Gatter 20 erhält e- benfalls das Ausgangssignal des weiteren XOR-Gatters 19. Insgesamt ergibt sich ein Ringoszillatorschaltkreis, welcher nur elf logische Gatter aufweist und besonders einfach z. B. in RFID-Chips oder -Tags implementierbar ist.

Eine alternative Ausführungsform eines Ringoszillatorschaltkreises ist in der Fig. 3 dargestellt. Dabei ist im Wesentlichen dieselbe Topologie wie in der Fig. 2 verwendet, wobei jedoch die Inverter 11 - 17 durch NAND-Gatter 21 - 27 ersetzt sind. Die den XOR-Gattern 18 - 20 der Fig. 2 entsprechenden XOR-Gatter sind mit den Bezugszeichen 28 - 30 in der Fig. 3 versehen .

Ein logischer Pegel 0 oder Low an dem Eingangsknoten 3, beispielsweise in Form eines entsprechenden Startsignals ST, führt zu einem deterministischen Zustand sowohl der Ringoszillatorschaltung 2 gemäß der Fig. 2 als auch gemäß der Fig. 3. Bei ST=O schwingt die Oszillatorschaltung nicht. Tritt ein Wechsel von 0 auf 1, also eine steigende logische Flanke, des Startsignals ST auf, beginnt die jeweilige Oszillatorschaltung bzw. der jeweilige Ringoszillator 2 eine Oszillation.

Diese Oszillation dauert solange an, bis ein stabiler Zustand der jeweiligen Schaltungsanordnung erreicht wird. Dies kann z. B. ein Fixpunkt sein, bei dem die Zustandsbelegung der einzelnen logischen Gatter stabil ist und sich ein erneutes Schwingen nur durch ein erneutes Starten oder Rücksetzen der

einzelnen logischen Pegel der Gatter erzwingen lässt. In der Fig. 3 sind beispielhaft an den Ausgängen der jeweiligen Logikgattern 9, 21 - 30 die logische Zustände in einem Fixpunkt H = I, L = O dargestellt. In der Regel stellt sich der Fix- punkt, abgesehen in der Situation, in der bereits beim Start des Ringoszillators 2 der Fixpunkt vorliegt, nach einer Phase mit zufälligen Oszillationen bzw. mit einem zufälligen Pegelverlauf an dem Ausgangsanschluss 4 ein. Es kann z. B. der entsprechende Ringoszillatorschaltkreis 2 zunächst auf seine Fixpunkteigenschaft experimentell untersucht werden.

In der Fig. 4 ist für eine Implementierung mit dem Ringoszillator, wie er in der Fig. 3 dargestellt ist, eine kumulative Verteilung für Zeiten, nach denen der Ringoszillator einen Fixpunkt erreicht, aufgetragen. Die in der Fig. 4 dargestellte Statistik stützt sich auf 1.000 Neustarts des Ringoszillators 2, wie er in der Fig. 3 dargestellt ist, wobei auf der Y-Achse die Zeiten nach denen der Fixpunkt erreicht wurde, also ein stabiler logischer H-Pegel am Ausgangsknoten 4 abge- griffen wird, aufgetragen. Die Fig. 4 zeigt die kumulative

Verteilung der entsprechenden Zeiten bis zum Erreichen eines Fixpunktes vom Neustart des Ringoszillators bei 1.000 Versuchen. Die vertikale Achse ist dabei logarithmisch aufgetragen .

Es ergibt sich für den in der Fig. 3 dargestellten Ringoszillator ein Median von 2.277 ns und ein Mittelwert (MOT) für die Zeiten zum Erreichen des Fixpunktes nach 3.686 ns . Bei der experimentellen Bestimmung dieser Zeiten bis zum Errei- chen des Fixpunktes ergibt sich nur bei 16 von 1.000 Neustarts eine Zeit von weniger als 100 ns nach dem Neustart. Es ist somit trotz des Vorliegens eines Fixpunktes für die in dem Zufallsgenerator verwendeten Ringoszillatoren praktisch ausgeschlossen, dass lediglich dieser Fixpunkt bzw. ein ent- sprechender logischer Pegel als Zufallsbit erfasst wird. Insbesondere die Berücksichtigung des Pegelverlaufes bis zum Erreichen des Fixpunktes, der zufällig ist, liefert zuverlässige zufällige Bitwerte.

In Fig. 5 sind beispielhaft die Pegelverläufe des Zufallsignals OS, welches am Ausgangsknoten 4 des in der Fig. 3 dargestellten Ringoszillators abgreifbar ist, dargestellt. Auf der X-Achse ist die Zeit in Nanosekunden dargestellt und auf der Y-Achse beispielhafte Pegelverläufe OSl - OS7, welche auf einen jeweiligen logischen Pegelwert V ₀ normiert sind, dargestellt. Dabei sind die verschiedenen Pegelverläufe OSl - 0S7 auf der Y-Achse gegeneinander verschoben dargestellt.

Zum Zeitpunkt t=0 ist der Ringoszillator 2 aktiviert bzw. gestartet worden. Dies erfolgt durch Umschalten des Startsignals ST von logischem L- auf logischen H-Pegel. Die dargestellten Kurven OSl - 0S7 können beispielsweise mit einem Os- zilloskop an einem Ausgangsknoten 4 abgegriffen werden.

Beispielsweise zeigt die Kurve OSl des Pegelverlaufes das Erreichen des Fixpunktes, also einen stabilen H-Pegel am Ausgangsknoten 4 bereits nach etwa 50 ns . Die übrigen beispiel- haft ausgewählten Pegelverläufe 0S2 - 0S7 hingegen zeigen zufällige Oszillationen in diesem Zeitbereich. Sofern beispielsweise durch entsprechende experimentelle Daten festgestellt wird, dass zumindest innerhalb einer minimalen Oszillationszeit tosz ' i die in der Fig. 5 z. B. mit etwa 42 ns an- gegeben werden kann, der Fixpunkt nicht erreicht wird, ist es ausreichend zur Bestimmung eines Zufallsbits den innerhalb dieser Zeit t _O sz ' vorliegenden Pegelverlauf zu berücksichtigen. Dies kann z. B. dadurch erfolgen, dass der Ausgangsknoten 4 der Ringoszillatorschaltung nach Ablauf einer vorgege- benen Zeit nach dem Neustart direkt abgetastet wird. Ferner kann dies, wie in der Fig. 1 schematisch dargestellt ist, ü- ber ein Flip-Flop geschehen. Es lassen sich auch andere Zeiträume verwenden, wie zum Beispiel eine mittlere Oszillationszeit MOT oder der Median der Verteilung der Figur 4. Ein sub- stanzieller Anteil der Oszillationen bevor ein Fixpunkt ereicht wird sollte jedoch bei der Zufallsbiterzeugung berücksichtig werden.

Sofern bei direkten Sampeln oder Abtasten immer der Fixpunkt erreicht wird, eignen sich der Ringoszillator sowie die Abtastzeitpunkte nicht zur Erzeugung von Zufallsbits. Falls jedoch der Fixpunkt häufig jedoch nicht immer vor dem Abtasten erreicht wird, erzeugt der Zufallsgenerator bzw. der Ringoszillatorschaltkreis statistisch unabhängige Zufallsbits. Diese Zufallsbits können eine Schiefe aufweisen, d. h. die Wahrscheinlichkeit 0 oder 1 abzugreifen liegt nicht bei 50 %. Durch geeignete algorithmische Nachbearbeitung kann eine der- artige Schiefe jedoch für das Erreichen des Fixpunktes kompensiert werden. Es sind zum Beispiel Verfahren bzw. Algorithmen bekannt, die auch ohne Kenntnis der konkreten statistischen Eigenschaften der Zustandsverteilung eine Schiefe kompensieren .

Wird ein Flip-Flop zum Erfassen oder Abtasten des zufälligen Pegelverlaufs, beispielsweise der Signale OSl - 0S7 verwendet, ist eine Implementierung möglich, bei der bei z. B. jeder aufsteigenden Flanke des Signals OSl - 0S7 ein Zustands- Wechsel im zwischengespeicherten Zustand des Flip-Flops auftritt. Es spielt dann keine Rolle ob beim Auslesen des Zwischenspeicherelementes bzw. Flip-Flops bereits ein Fixpunkt erreicht ist oder nicht.

Es ist auch denkbar, dass bei vorgegebenen Zeitpunkten bzw. Abtastzeitpunkten, die durch ein Taktsignal vorgegeben sein können, ein Zustandswechsel des vom Flip-Flop gespeicherten logischen Pegels in Abhängigkeit von dem jeweiligen vorliegenden Pegel des Zufallssignals erfolgt. Dabei sollte eine Berücksichtigung der Pegel des Zufallssignals z. B. durch Abtasten mehrfach innerhalb des bestimmbaren mittleren Oszillationszeitraums MOT erfolgen.

Um die Eigenschaften der Zufälligkeit bzw. Verbesserung der Schiefe zu erzielen, ist es möglich den Ringoszillator in regelmäßigen Abständen zurückzusetzen und einen vorgegebenen Zeitraum relaxieren zu lassen. Dies ist in der Fig. 5 beispielsweise durch die 20 ns dauernde negative Vorlaufzeit bis

zum Start des Ringoszillators angedeutet. Sofern der Ringoszillator selbst wenn er einen Fixpunkt aufweist regelmäßig neu gestartet wird, sind statistische Abhängigkeiten der in Abhängigkeit von dem Zufallssignal erzeugten Zufallsbits un- möglich. Es ist lediglich eine Schiefe d. h. eine Abweichung der Häufigkeit der 1-Bits vom Idealwert von der Wahrscheinlichkeit ^ möglich. Untersuchungen der Anmelderin ergeben jedoch, dass z. B. bei einer Implementierung des Ringoszillators gemäß der Fig. 3 in einem Zufallszahlengenerator eine Wahrscheinlichkeit von 0,4951 für den Bitwert 1 bzw. H auftritt. Dies sind 604.398 von 1.220.703 erzeugten Zufallsbits. Eine ähnliche Untersuchung ergab für den in der Fig. 2 dargestellten Ringoszillatorschaltkreis eine Wahrscheinlichkeit für 1-Bits von 0,4966. Diese geringen Schiefen genügen in der Regel allen Ansprüchen wie auch standardisierten Vorgaben für Zufallszahlengeneratoren .

In der Fig. 6 ist abschließend ein beispielhaftes Ablaufdiagramm für ein entsprechendes Verfahren zum Erzeugen von Zu- fallsbitfolgen dargestellt. Eine Implementierung kann beispielsweise durch geeignete Programmierung von Steuereinrichtungen, wie sie in der Fig. 1 mit dem Bezugszeichen 5 versehen sind, denkbar.

In einem Vorbereitungsschritt SO, der optional durchgeführt wird, kann die Oszillationszeit des verwendeten Ringoszillatorschaltkreises gemessen werden. Als Ergebnis ergibt sich beispielsweise ein mittlerer Oszillationszeitraum, in dem voraussichtlich der Ringoszillator keinen Fixpunkt einnimmt.

Im Schritt Sl wird der Oszillator gestartet. Im Schritt S2 wird das Oszillatorsignal bzw. das Zufallssignal abgetastet, was gemäß dem erfassten Pegel einem logischen 1- oder 0-Pegel entspricht .

Im Schritt S3 wird dann der entsprechende Bitwert ausgegeben. Somit wird ein einzelnes Zufallsbit erzeugt.

Anschließend wird der Oszillator erneut gestartet, so dass weitere Zufallsbits gemäß der Schleife der Schritte Sl, S2, S3 erzeugt werden. Die Zufallsbitfolge kann dann z. B. als binärer Code einer Zufallszahl interpretiert werden.

Die Fig. 6 zeigt ferner eine alternative Variante des Verfahrens zum Erzeugen von Zufallsbitfolgen gemäß der Schritt S21 und S22 wobei die Ablaufpfeile gestrichelt dargestellt sind.

Nach dem Start des Ringoszillators Sl werden die Zufallspegel, also der Pegelverlauf des Zufallssignals, welches von dem Ringoszillator erfasst werden kann, im Schritt S21 verfolgt. Ein Verfolgen kann beispielsweise durch regelmäßiges Abtasten oder Einkoppeln des Zufallssignals in eine Zwischen- Speichereinrichtung, welche in Abhängigkeit von steigenden oder fallenden Taktflanken einen gespeicherten logischen Pegel ändert, erfolgen. Nach einer beispielsweise vorgegebenen Zeit wird dann der somit zwischengespeicherte Bitwert im Schritt S22 ausgegeben. Durch erneute Abfolge in einer Art einer Programmschleife der Schritte S21, S22 ergeben sich wiederum Zufallsbitfolgen.

Die Erfindung in Form der beispielhaft dargestellten Zufallszahlengeneratoren, Ringoszillatoren und Verfahrensabläufe er- reicht eine zuverlässige Erzeugung von Zufallszahlen bei extrem geringem Hardwareaufwand. Die Zufallsbitfolgen oder Zufallszahlen erreichen eine hohe statistische Qualität und können z. B. bei Verschlüsselungsverfahren oder Authentifi- zierungsalgorithmen, insbesondere auch auf RFID-Chips, einge- setzt werden.