Verfahren und Vorrichtung zum Klassifizieren und/oder Erzeu ^¬ gen von Zufallsbits

Die vorliegende Erfindung betrifft eine Vorrichtung und ein Verfahren zum Klassifizieren und/oder Erzeugen eines oder mehrerer Zufallsbits. Es wird zum Beispiel eine Zufallsbit ^¬ folge erzeugt, welche als binäre Zufallszahl verwendet wird. Die vorgeschlagenen Vorrichtungen und Verfahren zum Erzeugen von Zufallsbits dienen beispielsweise der Implementierung von Zufallszahlengeneratoren. Die Erfindung ermöglicht beispiels ^¬ weise die Erzeugung echter Zufallsbits. Die vorgeschlagenen Verfahren und Vorrichtungen dienen bei ^¬ spielsweise der Erkennung von Zufallsbits oder Zufallsbitfol ^¬ gen, die gute zufällige Eigenschaften haben, und andererseits Bits, die als nicht zufällig gelten. Zufallsdaten werden bei ^¬ spielsweise bei Sicherheitsanwendungen benötigt, wobei aus erzeugten Zufallsbits beispielsweise kryptographische Schlüs ^¬ sel oder dergleichen abgeleitet werden.

In sicherheitsrelevanten Anwendungen, beispielsweise bei asymmetrischen Authentifikationsverfahren, sind Zufallsbit- folgen als binäre Zufallszahlen notwendig. Dabei ist es ge ^¬ wünscht, insbesondere bei mobilen Anwendungen einen möglichst geringen Hardwareaufwand zu betreiben. Bekannte Maßnahmen, um Zufallszahlen zu erzeugen, sind beispielsweise Pseudozufalls- zahlengeneratoren, analoge Zufallsquellen, Ringoszillatoren und deren Abwandlungen.

Bei Pseudozufallszahlengeneratoren werden Seeds verwendet, von denen ausgehend deterministische Pseudozufauszahlen be ^¬ rechnet werden. Zur Erzeugung des Seeds wird in der Regel ein physikalischer Zufallsgenerator verwendet. Als analoge Zu ^¬ fallsquellen werden Rauschquellen, wie z.B. das Rauschen von Zenerdioden, verstärkt und digitalisiert. Dabei ist die Ver- bindung von digitaler mit analoger Schaltungstechnik meist nur aufwändig zu verwirklichen.

Bei Ringoszillatoren, die hintereinander geschalteten Inver- tern aufgebaut sind, ergeben sich zufällige Jitter aus schwankenden Durchlaufzeiten der Signale durch die Inverter. Diese Jitter, also eine unregelmäßige zeitliche Schwankung in Zustandsänderungen der durch die Inverter geschickten Signa ^¬ le, können bei mehrfachen Durchläufen durch die Ringoszilla- torschaltung akkumuliert werden, so dass letztlich ein zufäl ^¬ liges analoges Signal entsteht. Nachteilig bei Ringoszillato ^¬ ren ist häufig die notwendige lange Zeit vom Start der

Schwingung bis ein brauchbar zufälliges Signal aufgrund der Jitter-Akkumulierung entsteht. Daher ergeben sich meist nied- rige nicht akzeptable Datenerzeugungsraten bei Ringoszillato ^¬ ren. Ferner ist möglich, dass die sich addierenden Jitter- Beiträge sich auch selbst wieder aufheben, so dass im Mittel zufällige kurze Gatterlaufzeiten durch zufällige längere Gat ^¬ terlaufzeiten kompensiert werden.

Fibonacci- und Galois-Ringoszillatoren können chaotische Schwingungs zustände aufweisen und erzeugen dann schneller zu ^¬ fällige Signalformen als klassische Ringoszillatoren. Aller ^¬ dings werden verschiedene digitale Gatter wie XOR- und NOT- Gatter eingesetzt. Dadurch können sich insbesondere bei Im ^¬ plementierungen auf ASICs große Geschwindigkeitsunterschiede der Gattertypen ergeben. Häufig besteht der Wunsch, mit Hilfe von FPGAs (Field Programable Gate Arrays) Zufallsbitfolgen zu erzeugen. Allerdings können auch bei diesen Digitalbausteinen periodische Schwingungen einsetzen, die nur eine geringe En ^¬ tropie oder Zufälligkeit in den Signalen haben. Die Ursache dieser periodischen Schwingungen ist bisher nicht bekannt; ihr Auftreten kann von Umgebungsbedingungen wie der Tempera ^¬ tur abhängen, aber auch von chipindividuellen Schwankungen bei der Herstellung.

Bei idealen Zufallsbits oder Zufallsbitfolgen haben die er ^¬ zeugten Bits eine gleiche Auftrittswahrscheinlichkeit von 0- und 1-Bits und sind voneinander statistisch unabhängig. Als Quelle für entsprechende zufällige Bits sind Einrichtungen mit hoher Entropie gewünscht. Unter anderem können physikali ^¬ sche Prozesse, wie radioaktive Zerfälle, die zufällige Ereig- nisse sind, als zufallsgebende Objekte verwendet werden.

Eine Schwierigkeit besteht meist darin, aufwandsgünstige Mes ^¬ sungen an entsprechenden physikalischen Systemen durchzufüh ^¬ ren, um Zufallsbits oder -daten ableiten zu können, und dann zu klassifizieren.

Wünschenswert ist es insbesondere, aufwandsgünstige Hardware- Zufallszahlengeneratoren zu verwenden, die dennoch für die jeweilige Anwendung ausreichend gute Zufälligkeiten, also statistische Unabhängigkeit und geringe Schiefe (Abweichung der Wahrscheinlichkeit von Null- bzw. Eins-Bits vom Idealwert Vi) , in ihren erzeugten Zufallsbits haben. Um die Zufälligkeit beispielsweise bei physikalischen Zufallszahlengeneratoren zu bestimmen, werden üblicher Weise statistische Tests einge- setzt, um Abweichungen vom statistischen Ideal zu erkennen.

Dabei wird eine große Anzahl von Zufallsbits erfasst und dann auf einem geeigneten Rechnersystem statistisch ausgewertet. Es sind in der Vergangenheit so genannte Online-Tests wichti ^¬ ger geworden, die direkt auf dem System, das auch die Zu- fallszahlen oder -bits erzeugt, ablaufen können und wenig Im ^¬ plementierungsaufwand haben. Derartige Online-Tests ermögli ^¬ chen es, bei einer starken Abweichung vom statistischen Ideal der erzeugten zufälligen Daten eine Warnung auszusenden bzw. die Zufallszahlenproduktion zu unterbinden.

Wünschenswert ist daher eine einfach mögliche Implementierung hinsichtlich der Rechen- und Speicheranforderungen von Zufäl ^¬ ligkeit stests , die online an Zufallsdaten durchgeführt werden sollen. Insofern ist es eine Aufgabe der vorliegenden Erfin- dung, ein verbessertes Verfahren und/oder eine verbesserte

Vorrichtung zum Erzeugen und/oder Klassifizieren von Zufalls ^¬ bits bereitzustellen. Demgemäß wird ein Verfahren zum Klassifizieren und/oder Er ^¬ zeugen von Zufallsbits vorgeschlagen. Das Verfahren umfasst die Schritte: Bereitstellen von Ausgangssignalen von logischen Elemen ^¬ ten eines Ringoszillatorschaltkreises, wobei die logischen Elemente zumindest teilweise rückgekoppelt sind und jeweils ein Eingangssignal in ein Ausgangssignal ausgeben;

gleichzeitiges Erfassen von mehreren Ausgangssignalen verschiedener logischer Elemente des Ringoszillatorschalt ^¬ kreises zum Erzeugen von Prüfbits;

Zuordnen der gleichzeitig erfassten Prüfbits zu einem jeweiligen Bitmuster; und

Klassifizieren eines ausgewählten Ausgangssignals als zufälliges Zufallssignal oder als nicht zufällig in Abhängig ^¬ keit von der Häufigkeit der aufgetretenen Bitmuster, wobei eine Anzahl von verschiedenen Bitmustern gezählt wird.

Unter einem Ringoszillatorschaltkreis soll dabei nicht nur die klassische Variante von einer ungeraden Zahl von Inverter in einer logischen Ringstruktur verstanden werden, sondern z. B. auch Verallgemeinerungen wie Fibonacci- oder Galois- Ringoszillatoren sowie allgemein zumindest teilweise rückge ^¬ koppelte schwingende Logikschaltungen.

Das vorgeschlagene Verfahren zum Klassifizieren und/oder Er ^¬ zeugen von Zufallsbits eignet sich insbesondere zur Implemen ^¬ tierung als Online-Test, um beispielsweise in FPGAs implemen ^¬ tierte Ringoszillatoren, die zur Erzeugung von Zufallsbits genutzt werden sollen, zu klassifizieren. Wird beispielsweise in Abhängigkeit von der Häufigkeit der aufgetretenen Bitmus ^¬ ter erkannt, dass kein ausreichender Zufall vorliegt, wird eine Zufallsbitproduktion unterbunden. Andererseits kann bei einem Erkennen von zufälligen Signalformen, bzw. chaotischen Schwingungsformen, beispielsweise an einem der Ausgangssigna ^¬ le ein entsprechend zuverlässiges echtes Zufallssignal abge ^¬ griffen werden. In Ausführungsformen umfasst das Verfahren ferner: Bestimmen einer Anzahl von verschiedenen Bitmustern, welche zu unter ^¬ schiedlichen Abtast Zeitpunkten erfasst wurden. Beispielsweise können getaktet oder in vorgegebenen Zeitab ^¬ ständen oder zu Zeitpunkten die Ausgangssignale von einer Auswahl der z. B. als Inverter implementierten logischen Ele ^¬ mente erfassen. Die sich ergebenden Bitmuster werden vorzugs ^¬ weise abgespeichert und hinsichtlich des Auftretens ihrer Häufigkeit gezählt.

In Ausführungsformen umfasst das Verfahren ferner einen

Schritt des Vergleichens der Anzahl verschiedener Bitmuster mit einem Schwellwert. Ein Schwellwert kann dahingehend fest- gelegt werden, dass beispielsweise, wenn die Anzahl unter ^¬ schiedlicher Bitmuster zu gering ist, geschlossen wird, dass keine ausreichende Zufälligkeit der Ausgangssignale vorliegt.

In weiteren Ausführungsformen des Verfahrens wird das ausge- wählte Ausgangssignal als Zufallssignal ausgegeben, falls ei ^¬ ne Anzahl von zu unterschiedlichen Abtast Zeitpunkten erfass- ten unterschiedlichen Bitmustern größer ist als ein vorgege ^¬ bener Schwellwert. Es wird vorgeschlagen, dass, wenn die verschiedenen zugeord ^¬ neten Prüfbits an den Ausgängen der logischen Elemente, bei ^¬ spielsweise der Inverter, möglichst viele verschiedene Bit ^¬ muster ausbilden, auf eine ausreichende Zufälligkeit ge ^¬ schlossen wird. Dadurch kann im Wesentlichen ausgeschlossen werden, dass statische oder periodische oszillatorische Zu ^¬ stände in dem jeweiligen Ringoszillator vorliegen.

Bei dem Verfahren kann die Häufigkeit der aufgetretenen Bit ^¬ muster über eine vorgegebene Anzahl von Abtast Zeitpunkten er- mittelt werden. Beispielsweise wird zur Klassifizierung des jeweiligen Ringoszillatorschaltkreises mit einer ungeraden Anzahl von Invertern über eine begrenzte Anzahl, von bei ^¬ spielsweise einigen Tausend Malen, ein Bitmuster ermittelt. Die Anzahl der vorgegebenen Abtast Zeitpunkte wird beispiels ^¬ weise in Abhängigkeit von der Anzahl der gleichzeitig erfass- ten Ausgangssignale bestimmt. Bei dem Verfahren kann ferner ein Abtasten des Zufallssignals zum Erzeugen eines Zufallsbits durchgeführt werden. Das als zufällig erkannte Zufallssignal hat eine zeitlich unregelmä ^¬ ßige Signalform und schwankt zufällig zwischen einem logi ^¬ schen H- und L-Pegel. Erst durch das Abtasten, beispielsweise mit Hilfe eines Zwischenspeicherelements, wie einem Flip- Flop, wird ein festgelegter Zufallsbitwert erzeugt. Dabei ergibt sich zufällig ein logischer H- oder L-Pegel am Ausgang des jeweiligen Flip-Flops. Es wird ferner eine Vorrichtung zum Erzeugen von Zufallsbits vorgeschlagen, welche umfasst:

einen Ringoszillatorschaltkreis mit mehreren, zumindest teilweise rückgekoppelten logischen Elementen, welche jeweils ein Eingangssignal in ein Ausgangssignal ausgeben;

eine Abtasteinrichtung, welche eingerichtet ist, mehrere der Ausgangssignale gleichzeitig zu erfassen und jedem er- fassten Ausgangssignal ein Prüfbit zuzuordnen, wobei die gleichzeitig erfassten Prüfbits ein Bitmuster bilden;

eine Auswerteeinrichtung, welche eingerichtet ist, eine Häufigkeit von aufgetretenen Bitmustern bei einem mehrfachen gleichzeitigen Erfassen zu bestimmen, wobei die Auswerteein ^¬ richtung ferner eingerichtet ist, eine Anzahl von verschiede ^¬ nen Bitmustern zu zählen. Die Vorrichtung ist insbesondere eingerichtet, ein wie zuvor und im Folgenden beschriebenes Verfahren durchzuführen.

Die Vorrichtung umfasst einen Ringoszillatorschaltkreis, der in der Regel aus einer ungeraden Anzahl von

Invertereinrichtungen gebildet ist. Einige der Rückkopplungs ^¬ pfade liefern dann ein meist zufälliges Schwingungsverhalten. Es kann jedoch geschehen, dass der Ringoszillatorschaltkreis in einen statischen Zustand oder periodischen Oszillator- ischen Zustand verfällt, so dass an den Ausgangsknoten der logischen Elemente in der Regel kein genügend zufälliges Sig ^¬ nal mehr abgreifbar ist. Der verwendete Ringoszillatorschalt ^¬ kreis kann dabei insbesondere als Fibonacci- oder Galois- Ringoszillator ausgestaltet sein.

Aufgrund der effizienten Prüfung und Klassifizierung der im Ringoszillatorschaltkreis vorliegenden Signalformen als zu ^¬ fällig oder nicht zufällig eignet sich die Vorrichtung insbe- sondere als Implementierung in einem FPGA oder ASIC. Die Vor ^¬ richtung und das Verfahren ermöglichen einen Online-Test ohne aufwändige Speicher- oder Rechenoperationen.

Es kann ferner eine Speichereinrichtung zum Speichern der Bitmuster vorgesehen sein. Der Ringoszillatorschaltkreis kann ferner einen Ausgang aufweisen, an dem eines der Ausgangssig ^¬ nale als Zufallssignal abgreifbar ist.

Es ist möglich, dass die Abtasteinrichtung mehrere Abtast- und Halteglieder zum Erfassen der mehreren Ausgangssignale unterschiedlicher logischer Elemente umfasst. Die Abtast- und Halteglieder können getaktet oder von einer Steuereinrichtung gesteuert operieren. Die Abtast- und Halteglieder setzen da ^¬ bei den erfassten Signalpegel in einen Prüfbitpegel um.

In Ausführungsformen ist die Vorrichtung Teil einer FPGA-Ein- richtung oder einer ASIC-Einrichtung .

Das Verfahren kann insbesondere über geeignete Beschreibungs- sprachen, beispielsweise VHDL oder Verilog, auf oder in einer FPGA- oder ASIC-Vorrichtung implementiert werden.

Weiterhin wird ein Computerprogramm-Produkt vorgeschlagen, welches auf einer programmgesteuerten Einrichtung die Durch- führung eines entsprechenden Verfahrens veranlasst.

Ein Computerprogramm-Produkt wie ein Computerprogramm-Mittel kann beispielsweise als Speichermedium, wie Speicherkarte, USB-Stick, CD-ROM, DVD oder auch in Form einer

herunterladbaren Datei von einem Server in einem Netzwerk be ^¬ reitgestellt oder geliefert werden. Dies kann zum Beispiel in einem drahtlosen Kommunikationsnetzwerk durch die Übertragung einer entsprechenden Datei mit dem Computerprogramm-Produkt oder dem Computerprogramm-Mittel erfolgen. Als programmge ^¬ steuerte Einrichtung kommt insbesondere eine Steuereinrich ^¬ tung, wie zum Beispiel ein Mikroprozessor für eine Smartcard oder dergleichen in Frage. Das Verfahren oder die Vorrichtung kann auch festverdrahtet oder in konfigurierbaren FPGAs oder ASICSs implementiert werden.

Weiterhin wird ein Datenträger mit einem gespeicherten Compu ^¬ terprogramm mit Befehlen vorgeschlagen, welche die Durchfüh ^¬ rung eines entsprechenden Verfahrens auf einer programmge ^¬ steuerten Einrichtung veranlassen.

Weitere mögliche Implementierungen der Erfindung umfassen auch nicht explizit genannte Kombinationen von zuvor oder im Folgenden bezüglich der Ausführungsbeispiele beschriebenen Vorrichtungen oder Verfahrensvarianten. Dabei wird der Fach ^¬ mann auch Einzelaspekte als Verbesserungen oder Ergänzungen zu der jeweiligen Grundform der Erfindung hinzufügen oder ab ^¬ ändern .

Die oben beschriebenen Eigenschaften, Merkmale und Vorteile dieser Erfindung sowie die Art und Weise, wie diese erreicht werden, werden klarer und deutlicher verständlich im Zusam ^¬ menhang mit der folgenden Beschreibung der Ausführungsbei ^¬ spiele, die im Zusammenhang mit den Zeichnungen näher erläu ^¬ tert werden.

Dabei zeigen:

Fig. 1 ein schematisches Ablaufdiagramm für ein Ver ^¬ fahren zum Klassifizieren von Zufallsbits; Fig. 2 eine schematische Darstellung eines Ausfüh rungsbeispiels für eine Vorrichtung zum Er zeugen und Klassifizieren von Zufallsbits;

Fig. 3, 7 schematische Darstellungen von weiteren Aus ^¬ führungsbeispielen für eine Vorrichtung zum Erzeugen und Klassifizieren von Zufallsbits mit Fibonacci-Ringoszillatoren; und

Darstellungen von Signalverläufen in Ausfüh rungsbeispielen von Vorrichtungen zum Erzeu gen und Klassifizieren von Zufallsbits mit Fibonacci-Ringoszillatoren . In den Figuren sind funktionsgleiche Elemente mit denselben Bezugszeichen versehen, sofern nichts anderes angegeben ist.

In der Fig. 1 ist ein schematisches Ablaufdiagramm für ein Verfahren zum Klassifizieren oder Erzeugen von Zufallsbits dargestellt, welches beispielsweise mit einer Vorrichtung, wie sie in der Fig. 2 als schematische Darstellung als Aus ^¬ führungsbeispiel für eine Vorrichtung zum Erzeugen und Klas ^¬ sifizieren von Zufallsbits gezeigt ist, durchgeführt werden kann .

Das Verfahren und die Vorrichtung eignen sich beispielsweise dazu, bei Zufallszahlengeneratoren, die mit Hilfe von Ringos ^¬ zillatoren zufällige Signalformen erzeugen, zu erkennen, ob ein ungewünschter Oszillationszustand eintritt. In diesem Fall kann ein Fehleralarm ausgelöst werden, so dass die er ^¬ zeugten Bits nicht als Zufallsbits verwendet werden.

In einem ersten Schritt Sl werden Ausgangssignale von logi ^¬ schen Elementen eines Ringoszillatorschaltkreises bereitge- stellt. In diesem Schritt Sl wird beispielsweise ein Ringos ^¬ zillator 2 der Vorrichtung zum Erzeugen von Zufallsbits 1 be ^¬ trachtet. Der Ringoszillator 2 umfasst eine ungerade Anzahl von Invertern 2i - 2 _n , die miteinander verkettet sind. Jeder der Inverter 2i - 2 _n hat einen Eingang und einen Ausgang, der nicht explizit bezeichnet ist. Am jeweiligen Eingang werden Eingangssignale Ei - E _n empfangen, die invertiert als Aus ^¬ gangssignale Ai - A _n ausgegeben werden.

An einigen Stellen sind Rückkopplungsschleifen vorgesehen, die eine unregelmäßige Schwingungs- oder Signalform innerhalb des Ringoszillatorschaltkreises hervorrufen. In dem Ausfüh ^¬ rungsbeispiel der Fig. 2 ist zum Beispiel zwischen dem p-ten und p+l-ten Inverter eine Rückkopplung vorgesehen.

An einem Ausgang 8 des Ringoszillators 2 ist ein Zufallssig ^¬ nal ZS abgreifbar. Das Zufallssignal ZS entspricht dabei dem Ausgangssignal A _n des n-ten Inverters 2 _n . Es sind abweichende Ringoszillatoren, beispielsweise in der Art von Galois- oder Fibonacci-Oszillatoren denkbar. Außerdem können weitere logi ^¬ sche Elemente vorgesehen werden.

Um nun zu überprüfen, ob eine zufällige Signalform am Ausgang 8 vorliegt, und nicht etwa ein Oszillationszustand oder sta ^¬ tischer Zustand erreicht wird, werden mehrere Ausgangssignale A _p - A _q abgegriffen. Es können grundsätzlich alle Ausgangs ^¬ signale Ai - A _n verwendet werden. Um Speicher und Aufwand zu sparen, genügt jedoch eine Auswahl von Ausgangssignalen.

In einem zweiten Schritt S2 werden die mehreren Ausgangssig ^¬ nale A _p - A _q der verschiedenen logischen Elemente 2 _P - 2 _q zum Erzeugen von Prüfbits erfasst. Die q-p-Prüfbits werden in ei ^¬ ner Abtasteinrichtung 3 mit Hilfe von q-p Abtast- und Halte- gliedern 3 _P - 3 _q erzeugt. Die Abtast- und Halteglieder haben jeweils einen Takteingang, dem ein Taktsignal oder Abtastsig ^¬ nal CK zugeführt ist.

In Abhängigkeit von dem Takt- oder Abtastsignal CK liefern die Abtast- und Halteglieder 3 _P - 3 _q einen logischen Aus ^¬ gangspegel, der als Prüfbit P _p - P _q verwendet wird. In dem Ausführungsbeispiel der Fig. 2 wird das Abtasten beispiels ^¬ weise zu vorgegebenen Zeitpunkten mehrfach hintereinander oder in Abhängigkeit von dem Taktsignal CK durch eine Steuer ^¬ einrichtung 5 durchgeführt. Die q-p Prüfbits P _P - P _q werden einer Speichereinrichtung 4 zugeführt, die die Prüfbits P _P - P _q für einen jeweiligen Abtast Zeitpunkt als Bitmuster BMi - BMi abspeichert. Bei p-q abgetasteten Ausgangssignalen A _p - A _q sind 2 ^p~q unterschiedliche Bitmuster BMi möglich.

Der Speicher 4 ist über Steuer- oder Datensignale CT an die Steuereinrichtung 5 gekoppelt. Die Steuereinrichtung 5 steu- ert ferner über einen Setz- oder Starteingang 7 den Ringos ^¬ zillatorschaltkreis 2. Zum Starten einer (chaotischen oder unregelmäßigen) Oszillation der miteinander verketteten In- verter 2 i - 2 _n werden beispielsweise zunächst alle Eingangs ^¬ signale Ei - E _n zunächst auf einen vorgegebenen wohldefinier- ten Pegel gebracht. Die Oszillation wird angestoßen, indem eine Signalflanke beispielsweise als Starteingangssignal Ei angekoppelt wird und die übrigen Eingangssignalpegel E ₂ - E _n frei oszillierend gelassen werden. Im Verfahren gemäß der Fig. 1 erfolgt im Schritt S3 ein Zu ^¬ ordnen der gleichzeitig erfassten Prüfbits P _p - P _q zu einem jeweiligen Bitmuster BMi . In Abhängigkeit von der Häufigkeit des Auftretens verschiedener Bitmuster BMi werden nun bei ^¬ spielsweise mit Hilfe der Steuereinrichtung 5 das ausgewählte Ausgangssignal A _n bzw. ZS als zufällig oder nicht zufällig klassifiziert. Diese Klassifizierung oder der Erzeugungs ^¬ schritt S4 können mehrere Unterschritte umfassen.

Zunächst werden im Schritt S40 die Anzahl von verschiedenen Bitmustern B _lr welche zu unterschiedlichen Abtast Zeitpunkten erfasst wurden, bestimmt. Dabei wird insbesondere die Anzahl verschiedener Bitmuster, die auftreten, erfasst. Die Anzahl der verschiedenen Bitmuster wird in einem Vergleichsschritt S41 mit einem Schwellwert verglichen. Der Schwellwert kann beliebig angepasst werden und bestimmt beispielsweise die

Sensibilität des Tests oder des Klassifizierungsvorgangs für zufällige oder nicht zufällige Daten. Wird erkannt, dass nur wenige verschiedene Bitmuster an den verschiedenen Ausgangs- Signalen A _p - A _n abgeleitet werden, also die Anzahl unterhalb des vorgegebenen Schwellwertes liegt, wird im Schritt S42 der Ringoszillator bzw. das Ausgangssignal A _n bzw. ZS als nicht zufällig eingestuft.

Die Steuereinrichtung 5 kann beispielsweise ein entsprechen ^¬ des Alarm- oder Warnsignal A an einem Warnausgang 10 ausge ^¬ ben. Die Steuereinrichtung 5 kann auch eine Ausgabe des Sig ^¬ nals ZS unterbinden. Wird jedoch im Schritt S41 erkannt, dass viele unterschiedliche Bitmuster BMi vorliegen, d.h. die er- fasste Anzahl von unterschiedlichen Bitmustern ist größer als der vorgegebene Schwellwert, erfolgt eine Klassifizierung der abgetasteten oder erfassten Ausgangssignale A _p - A _q und ins ^¬ besondere des Zufallssignals ZS als zufällig.

In der Folge wird im Schritt S5 beispielsweise gemäß der Fig. 2 durch die Steuereinrichtung 5 gesteuert, das Zufalls ^¬ signal ZS, welches dem n-ten Ausgangssignal des Inverters 2 _n entspricht, abgetastet. Das Abtasten kann mit Hilfe einer Zwischenspeichereinrichtung, wie beispielsweise einem Flip- Flop 6, erfolgen. Das Flip-Flop 6 liefert aus dem oszillie ^¬ renden, mit einem nicht definierten logischen Pegel behafte ^¬ ten Zufallssignal ZS ein Zufallsbit mit einem Pegel 1 oder 0. Dieses Zufallsbit ZB wird am Ausgang 9 ausgegeben. Insofern liefern die Vorrichtung und das Verfahren eine zuverlässige Maßnahme zum Erzeugen von echten Zufallsbits.

Die Anmelderin hat nun verschiedene als Zufallsbitgeneratoren verwendete Ringoszillatorschaltkreise mit Hilfe des vorge- schlagenen Verfahrens untersucht. In Fig. 3 ist ein Ringos ^¬ zillator 11 wiedergegeben, der als Fibonacci-Ringoszillator ausgestaltet ist. Es sind sieben verkettete Inverter 2i - 2 ₇ vorgesehen, wobei Rückkopplungen gemäß dem Rückkopplungspoly ^¬ nom x ⁷ + x ⁶ + x ³ + x ² + x + 1 implementiert sind. An den je- weiligen Ausgängen der Inverter 2i - 2 ₇ werden sieben Aus ^¬ gangssignale Ai - A ₇ abgegriffen. Diese abgegriffenen Aus ^¬ gangssignale können Prüfbits Pi - P ₇ zugeordnet werden. Die sieben Prüfbits Pi - P7 bilden zu jedem Abtast Zeitpunkt ein Bitmuster BM _± .

In den Fig. 4, 5 und 6 sind nun Signalformen des Ausgangssig- nals A ₇ wiedergegeben, das als Zufallssignal ZS betrachtet werden kann. In den Fig. 4, 5 und 6 ist jeweils ein Zeitraum von 400 ns dargestellt. Man erkennt, dass über die ersten et ^¬ wa 50 ns bei jedem Start des Ringoszillators 11 eine ähnliche Signalform erreicht wird. Ab etwa 50 ns sind die Signale je- doch qualitativ als zufällig zu erachten. Untersuchungen der Anmelderin haben nun ergeben, dass bei einem Abtasten oder Samplen von 5000 Mal in einem Abstand von 200 ns 123 ver ^¬ schiedene Bitmuster auftreten. Insgesamt sind bei sieben Prüfbits 2 ⁷ = 128 verschiedene Bitmuster B _x denkbar.

Die Fig. 7 zeigt eine weitere Ausführungsform eines

Fibonacci-Ringoszillators 12. Im Wesentlichen sind dieselben Elemente wie in der Fig. 3 enthalten, wobei jedoch das Rück ^¬ kopplungspolynom zu x ⁷ + x ⁶ + x ² + 1 gewählt ist. Betrachtet man nun den Signalverlauf A ₇ am Ausgang des letzten Inverters 2 ₇ , ergibt sich ein gleichmäßiges Schwingungsverhalten. Das heißt, wie es in der Fig. 8 dargestellt ist, ist ein periodi ^¬ scher oszillativer Verlauf des Ausgangssignals A ₇ zu erken ^¬ nen, der kaum zufällige Eigenschaften aufweist. Der Ringos- zillator, wie er in der Fig. 7 dargestellt ist, eignet sich daher nicht zum Erzeugen von Zufallsbits.

Die Anmelderin hat auch hier die Bitmuster BM _X über 5000 Durchläufe ermittelt. Es erfolgten wiederum 5000 Abtastungen von Prüfbits Pi - P ₇ im Abstand von 200 ns . Dabei wurden le ^¬ diglich 14 der 128 möglichen Bitmuster mit 7 Bits erzeugt.

Die Zahl der aufgetretenen Bitmuster unterscheiden sich mit Werten von 14 im Fall des periodisch schwingenden Generators und von 123 im Fall der chaotischen Schwingungen ganz erheb ^¬ lich. Die Wahl des Schwellwerts ist also unkritisch. Ein geeigneter Schwellwert kann zum Beispiel bei 50 angesetzt werden, wobei erkannt würde, dass lediglich 14 verschiedene Bitmuster auftreten, also die Anzahl von unterschiedlichen Bitmustern aus 7 Bits über 5000 Durchläufe oder Takt- oder Abtast Zeitpunkte unterhalb des Schwellwerts von 50 liegt. Der genaue Schwellwert kann angepasst an die Anzahl und Länge der Inverterketten erfolgen. Die Untersuchungen der Anmelderin erfolgten auf einem FPGA-Chip des Typs Spartan-3 der Fa.

Xilinx .

In weiteren Untersuchungen der Anmelderin wurden Fibonacci- Ringoszillatoren der Länge 16 mit verschiedenen Rückkopp ^¬ lungspolynomen getestet. Bei jeweils 5000 Samples im Abstand von 2 ps sind 16 Bit lange Bitmuster BMi betrachtet worden. Diejenigen Rückkopplungspolynome, die zu periodischen Schwin ^¬ gungen führen, führten lediglich zu 32, 40, 51 und 62 ver ^¬ schiedenen Prüfbitmustern . bei 26 anderen Rückkopplungspoly ^¬ nomen, die zu chaotischen Schwingungen führen, liegt die Zahl der verschiedenen erfassten Bitmuster zwischen 1261 und 2154. Insofern kann beispielsweise bei Fibonacci-Ringoszillatoren der Länge 16 ein Schwellwert für unterschiedliche Bitmuster zwischen 200 und 500 gewählt werden.

Das Verfahren liefert aufwandsgünstig einen Online-Test für insbesondere in FPGAs implementierten Zufallsbitgeneratoren, die Ringoszillatoren einsetzen. Es ergibt sich eine sichere Erkennung von Fehlfunktionen, und damit periodischem oszilla ^¬ torischen Verhalten des eingesetzten Ringoszillators. Es wird nur ein geringer Speicheraufwand benötigt, da für jedes der 2 ^p~q möglichen Bitmuster jeweils nur ein Bitspeicherplatz be ^¬ nötigt wird. Durch eine geeignete Wahl der ausgekoppelten Prüfbits kann das Verfahren und der Hardwareaufwand skaliert werden . Es ist auch möglich, beispielsweise bei Fibonacci- Ringoszil ^¬ latoren mit 16 eingesetzten Invertern nur eine Auswahl von Ausgangssignalen, beispielsweise die acht ersten Ausgangssig ^¬ nale Ai - A ₈ , zu verwenden. Die Untersuchungen der Anmelderin ergaben auch dabei, dass bei den periodisch schwingenden Fibonacci-Ringoszillatoren nur 16 oder 20 unterschiedliche Bitmuster auftreten. Bei chaotischen Signalverläufen sind je ^¬ doch zwischen 240 und 256 verschiedene Bitmuster der 2 ⁸ mög- liehen aufgetreten. Bei einem Abgriff von nur acht beispiels ^¬ weise niedersignifikanten Bits bei Fibonacci- Ringoszillato ^¬ ren der Länge 16 kann eine Schwelle von 100 gewählt werden, ab der der Ringoszillator Zufallsbits bzw. Zufallssignale liefern kann.

Obgleich in den vorbeschriebenen Beispielen Fibonacci- Ringoszillatoren untersucht wurden, kann dies genauso auf an ^¬ dere kompliziertere Ringoszillatoren angewendet werden. Bei ^¬ spielsweise kann das Verfahren insbesondere für Galois- Ring- Oszillatoren zur Zufallsbiterzeugung verwendet werden.

Obwohl die Erfindung im Detail durch das bevorzugte Ausfüh ^¬ rungsbeispiel näher illustriert und beschrieben wurde, so ist die Erfindung nicht durch die offenbarten Beispiele einge- schränkt und andere Variationen können vom Fachmann hieraus abgeleitet werden, ohne den Schutzumfang der Erfindung zu verlassen .