Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
GENERATION OF A NUMBER OF RANDOM BITS
Document Type and Number:
WIPO Patent Application WO/2015/000640
Kind Code:
A1
Abstract:
The invention relates to a method for generating a number of random bits by means of an electronic oscillating circuit, wherein signals are simultaneously sensed or sampled at various points within a random number generator. An optionally present statistical dependency of simultaneously sampled bits is eliminated by means of algorithmic post-processing. The simultaneously sampled bits form a tuple of bits and are subjected to the algorithmic post-processing, in which potentially more than one bit of entropy can arise from one of the formed tuples. The invention further relates to a device for carrying out the presented method.

Inventors:
DICHTL, Markus (Jutastr. 14, München, 80636, DE)
Application Number:
EP2014/060769
Publication Date:
January 08, 2015
Filing Date:
May 26, 2014
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
SIEMENS AKTIENGESELLSCHAFT (Wittelsbacherplatz 2, München, 80333, DE)
International Classes:
G06F7/58; H03K3/84
Foreign References:
US7958175B2
DE102008018678A1
Other References:
MENEZES A J ET AL: "HANDBOOK OF APPLIED CRYPTOGRAPHY", 1997, CRC PRESS, BOCA RATON, FL, USA, XP002178884, ISBN: 978-0-8493-8523-0 Seiten 172-173, Seite 173, Absatz 2
K. WOLD; C. H. TAN: 'Analysis and enhancement of random number generator in FPGA based on oscillator rings' PROC. OF RECONFIG 2008, CANCUN 2008, Seiten 385 - 390
ARI JUELS; MARKUS JAKOBSSON; ELIZABETH A. M. SHRIVER; BRUCE HILLYER: 'How to turn loaded dice into fair coins' IEEE TRANSACTIONS ON INFORMATION THEORY Bd. 46, Nr. 3, 2000, Seiten 911 - 921
Download PDF:
Claims:
Patentansprüche

1. Verfahren zum Erzeugen von einer Anzahl (k) von Zufallsbits (Z) mit einer elektronischen Schwingschaltung (1), wobei - in einem ersten Schritt (Sl) ein erstes Bit (Bl) durch eine erste Abtasteinrichtung (AI) an einer ersten Stelle in der elektronischen Schwingschaltung (1) und mindestens ein zweites Bit (B2) durch mindestens eine zweite Abtasteinrichtung (A2) an mindestens einer von der ersten Stelle abweichenden zweiten Stelle gleichzeitig abgegriffen werden;

- in einem zweiten Schritt (S2) in Abhängigkeit von dem ersten Bit (Bl) und dem mindestens einen zweiten Bit (B2) mit Hilfe einer algorithmischen Nachbearbeitung die Anzahl (k) von Zufallsbits (Z) erzeugt wird;

- als Anzahl (k) ein Wert größer als 1 erzeugt werden kann.

2. Verfahren nach Anspruch 1, wobei die elektronische

Schwingschaltung (1) als klassischer Ringoszillator,

Mehrspur-Ringoszillator, Fibonacci-Ringoszillator, Gallois- Ringoszillator, rückkopplungsfreier Mehrspur- Zufallszahlengenerator oder Multiplizierer- Zufallszahlengenerator ausgebildet wird.

3. Verfahren nach Anspruch 1 oder 2, wobei die elektronische Schwingschaltung (1) zumindest teilweise digital und/ oder zumindest teilweise analog ausgeführt wird.

4. Verfahren nach einem der vorstehenden Ansprüche, wobei die elektronische Schwingschaltung (1) als Teil einer FPGA- Einrichtung oder einer ASIC-Einrichtung ausgeführt wird.

5. Verfahren nach einem der vorstehenden Ansprüche, wobei ein jeweiliger Pegel eines ersten Zufallssignals und eines zweiten Zufallssignals durch jeweilige Zwischenspeicherelemente gespeichert wird.

6. Verfahren nach Anspruch 5, wobei durch jeweilige Inhalte der jeweiligen Zwischenspeicherelemente ein n-Tupel von Bits erzeugt wird. 7. Verfahren nach einem der vorstehenden Ansprüche, wobei der ersten Abtasteinrichtung und der mindestens einen zweiten Abtasteinrichtung ein gleichzeitiges Abtastsignal (CK) vorgegeben wird. 8. Verfahren nach Anspruch 7, wobei das Abtastsignal (CK) durch ein Takteingangssignal einer Delay-Flip-Flop-Schaltung gebildet wird.

9. Verfahren nach einem der vorstehenden Ansprüche, wobei durch die algorithmische Nachbearbeitung mehr als ein Bit Entropie erzeugt wird.

10. Verfahren nach Anspruch 9, wobei die algorithmische Nachbearbeitung durch eine kryptographische Funktion durchgeführt wird.

11. Vorrichtung (10) zum Erzeugen von einer Anzahl (k) von Zufallsbits (Z) mit einer elektronischen Schwingschaltung (1) ,

mit einer ersten Abtasteinrichtung und mindestens einer zweiten Abtasteinrichtung,

zum gleichzeitigen Abgreifen eines ersten Bits (Bl) an einer ersten Stelle in der elektronischen Schwingschaltung (1) mittels der ersten Abtasteinrichtung (AI) und mindestens eines zweiten Bits (B2) an mindestens einer von der ersten Stelle abweichenden zweiten Stelle mittels der mindestens einen zweiten Abtasteinrichtung (A2),

mit einer Nachbearbeitungskomponente (3) zum Erzeugen der Anzahl (k) von Zufallsbits (Z) mit Hilfe einer algorithmischen Nachbearbeitung in Abhängigkeit von dem ersten Bit (Bl) und dem mindestens einen zweiten Bit (B2), wobei als Anzahl (k) ein Wert größer als 1 erzeugbar ist.

12. Vorrichtung nach Anspruch 11, wobei die elektronische Schwingschaltung (1) aus einer der folgenden Schaltungen aufgebaut ist:

- klassischer Ringoszillator,

- Mehrspur-Ringoszillator,

- Fibonacci-Ringoszillator,

- Gallois-Ringoszillator,

- rückkopplungsfreier Mehrspur-Zufallszahlengenerator oder

- Multiplizierer-Zufallszahlengenerator .

13. Vorrichtung nach Anspruch 11, ferner umfassend mindestens eine weitere Einheit zum Ausführen eines Verfahrens gemäß einem der Ansprüche 2 bis 10.

Description:
Beschreibung

Erzeugen von einer Anzahl von Zufallsbits

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zum Erzeugen von einer Anzahl von Zufallsbits mit einer elektronischen Schwingschaltung.

In sicherheitsrelevanten Anwendungen, beispielsweise bei asymmetrischen Authentifikationsverfahren, sind Zufallsbitfolgen als binäre Zufallszahlen notwendig. Bekannte Maßnahmen, um Zufallszahlen zu erzeugen, verwenden analoge Zufallsquellen. Als analoge Zufallsquellen werden Rauschquellen, wie beispielsweise das Rauschen von Zenerdioden, verstärkt und digitalisiert. Dabei wird digitale mit analoger Schaltungstechnik verbunden.

Eine Quelle zur Erzeugung von Zufallsdaten ist eine wichtige Voraussetzung für viele Sicherheitsanwendungen. Insbesondere bei kryptographischen Verfahren werden aus den erzeugten Zufallsbits Schlüssel und einmalig verwendete Werte, sogenannte Nonces, abgeleitet. Dabei werden hohe Anforderungen an die Qualität der dazu verwendeten Zufallsbits gestellt: Ideale Zufallsbits müssen gleichverteilt auftreten, und mehrere Bits müssen voneinander statistisch unabhängig sein. Das heißt, die Quelle zur Erzeugung der Zufallsbits muss eine hohe Entropie besitzen.

Ferner werden Ringoszillatoren und deren Abwandlungen als Zufallszahlengeneratoren verwendet. Bei Ringoszillatoren, die aus einer ungeraden Anzahl von hintereinander geschalteten Invertern aufgebaut sind, ergibt sich beispielsweise ein zufälliger Jitter aus schwankenden Durchlaufzeiten der Signale durch die Inverter. Dieser Jitter, also eine unregelmäßige zeitliche Schwankung in Zustandsänderungen der durch die Inverter geschickten Signale, kann bei mehrfachen Durchläufen durch die Ringoszillatorschaltung akkumuliert werden, so dass letztlich ein zufälliges analoges Signal entsteht. Aus dem Stand der Technik sind Verfahren zur Erzeugung echter Zufallszahlen bekannt, welche diese Bit für Bit gewinnen. Es wird dabei ein Bit gesampelt, anschließend für eine ausrei- chend lange Zeitspanne gewartet, bis man einen vom vorigen

Zustand statistisch unabhängigen Zustand des Systems annehmen kann, und anschließend erneut ein Bit gesampelt. Diese Vorgehensweise wird iterativ angewendet. Es ist bekannt, schwingende rückgekoppelte Schaltungen an mehreren Stellen gleichzeitig zu sampeln und die gesampelten Bits algorithmisch zu einem einzigen Bit zu komprimieren. Für eine solche Komprimierung werden meist XOR-Verknüpfungen der Bits vorgenommen. Beispielsweise ist eine solche Schaltung in der Veröffentlichung von K. Wold, C. H. Tan, "Analysis and enhancement of random number generator in FPGA based on oscillator rings", Proc . of ReConFig 2008, Cancun, 2008, pp . 385-390, beschrieben. Ein Ziel bei der Erzeugung echter Zufallszahlen ist es, aus einem von einem Zufallszahlengenerator herbeigeführten Zufallsereignis möglichst viel Entropie in der Form von Zufallsbits zu gewinnen. Vor diesem Hintergrund ist es eine Aufgabe der vorliegenden Erfindung, ein Verfahren und eine Vorrichtung mit verbesserter Rate der Zufallsbiterzeugung bereitzustellen.

Diese Aufgabe wird durch ein Verfahren und eine Vorrichtung zum Erzeugen von einer Anzahl von Zufallsbits gelöst. Vorteilhafte Ausführungsformen und Weiterbildungen sind in den Unteransprüchen angegeben.

Die im Folgenden genannten Vorteile müssen nicht notwendiger- weise durch die Gegenstände der unabhängigen Ansprüche erzielt werden. Vielmehr kann es sich auch um Vorteile handeln, welche lediglich durch einzelne Ausführungsformen oder Weiterbildungen erzielt werden. Erfindungsgemäß weist ein Verfahren zum Erzeugen von einer Anzahl von Zufallsbits mit einer elektronischen Schwingschaltung, folgende Schritte auf:

- in einem ersten Schritt werden ein erstes Bit durch eine erste Abtasteinrichtung an einer ersten Stelle in der elektronischen Schwingschaltung und mindestens ein zweites Bit durch mindestens eine zweite Abtasteinrichtung an mindestens einer von der ersten Stelle abweichenden zweiten Stelle gleichzeitig abgegriffen;

- in einem zweiten Schritt wird in Abhängigkeit von dem ersten Bit und dem mindestens einen zweiten Bit mit Hilfe einer algorithmischen Nachbearbeitung die Anzahl von Zufallsbits erzeugt;

- als Anzahl kann ein Wert größer als 1 erzeugt werden.

Dadurch wird ein Verfahren bereitgestellt, welches an verschiedenen Stellen innerhalb eines Zufallszahlengenerators, insbesondere innerhalb der elektronischen Schwingschaltung, Signale gleichzeitig abtastet oder sampelt. Eine gegebenenfalls vorhandene statistische Abhängigkeit gleichzeitig gesampelter Bits wird durch die algorithmische Nachbearbeitung beseitigt. Die gleichzeitig gesampelten Bits bilden ein Tupel von Bits und werden der algorithmischen Nachbearbeitung un- terzogen, bei der aus einem der gebildeten Tupel potentiell mehr als ein Bit Entropie entstehen kann. Dabei wird je nach Inputbits durch das Nachbearbeitungsverfahren als Output mehr als ein Bit Entropie erzeugt oder weniger als ein Bit Entropie .

Unter einer Abtasteinrichtung und insbesondere der ersten Abtasteinrichtung sowie der zweiten Abtasteinrichtung wird in der vorliegenden Anmeldung ein Element bezeichnet, welches ein Signal zu einem durch ein anderes Signal festgelegten Zeitpunkt erfasst. Dabei wird insbesondere ein Signal an einer Stelle der elektronischen Schwingschaltung ausgekoppelt und einem Eingang der ersten Abtasteinrichtung zugeführt. An mindestens einer weiteren Stelle in der elektronischen Schwingschaltung, beispielsweise zwischen jedem Inverter einer klassischen Ringoszillatorschaltung, wird ebenso ein Signal ausgekoppelt und einem Eingang der zweiten bzw. der jeweiligen Abtasteinrichtung zugeführt. Das Sampeln durch die jeweilige Abtasteinrichtung erfolgt dann gleichzeitig.

Insbesondere vermeidet die elektronische Schwingschaltung digitale Speicherelemente oder eine Toggle-Flip-Flop-Schaltung. Unter einer Toggle-Flipflop-Schaltung, auch Toggle-Flipflop oder T-Flipflop genannt, wird in der vorliegenden Anmeldung ein Element verstanden, welches eine bistabile Kippstufe darstellt und mit jedem Taktimpuls seinen Ausgangszustand ändert. T-Flipflops wechseln beispielsweise den intern abge- speicherten logischen Zustand bei jeder steigenden oder fallenden Signalflanke des eingekoppelten Zufallssignals.

Gemäß einer Ausführungsform wird die elektronische Schwingschaltung als klassischer Ringoszillator, Mehrspurringoszil- lator, Fibonacci-Ringoszillator, Galois-Ringoszillatoren, rückkopplungsfreier Mehrspurzufallszahlengenerator oder Multiplizierer-Zufallszahlengenerator ausgebildet .

Bei Ringoszillatorschaltungen, wobei dieser Begriff sowohl klassische Ringoszillatoren, Mehrspurringoszillatoren,

Fibonacci-Ringoszillatoren wie auch Galois-Ringoszillatoren umfasst, wird eine Anzahl von logischen Gattern rückgekoppelt. Dabei befinden sich alle Gatter in einer durch die anderen Gatter gebildeten Rückkopplungsschleife, so dass ein Signalwechsel am Ausgang eines Gatters potentiell nach dem Weg über die aus anderen Gattern gebildete Rückkopplungsschleife wieder an einem Eingang des Gatters ankommen kann.

Bei rückkopplungsfreien Mehrspurzufallszahlengeneratoren liegt keine Rückkopplungsschleife derart vor, dass eine Zu- standsänderung mindestens eines Rückkopplungsausgangssignals einer Abbildungseinrichtung als eine Zustandsänderung mindestens eines Eingangssignal einer anderen Abbildungseinrichtung derart zugeführt ist, dass eines oder mehrere Ausgangssignale der Abbildungseinrichtung von der Zustandsänderung des Rückkopplungsausgangssignals beeinflusst wird.

Bei einem Multiplizierer-Zufallszahlengenerator wird beispielsweise ein auf einem FPGA vorhandenes binäres Multiplikationsrechenwerk verwendet. Es werden Ausgangs- bzw. Ergebnisbits an Eingangsbits rückgekoppelt, so dass Oszillationen entstehen, die praktisch zufällige Signalverläufe ergeben.

Gemäß einer Ausführungsform wird die elektronische Schwingschaltung zumindest teilweise digital und/oder zumindest teilweise analog ausgeführt. Als Baugruppen einer Schaltung können analoge Elemente wie invertierende Verstärker verbaut sein. Ferner ist der Einsatz vollständig digitaler Bauelemente in der elektronischen Schwingschaltung vorteilhalft, da eine aufwandsgünstige Implementierbarkeit möglich ist.

Gemäß einer weiteren Ausführungsform wird die elektronische Schwingschaltung als Teil einer FPGA-Einrichtung oder ASIC- Einrichtung ausgeführt.

Gemäß einer Weiterbildung wird ein jeweiliger Pegel eines ersten Zufallssignals und eines zweiten Zufallssignals durch jeweilige Zwischenspeicherelemente gespeichert.

Beispielsweise kann ein Verzögerungs-Flipflop oder Delay- Flipflop, auch D-Flipflop genannt, den jeweiligen Pegel an der jeweiligen ersten Stelle oder zweiten Stelle speichern. Das erste Zwischenspeicherelement, beispielsweise ein erster D-Flipflop, nimmt an einem ersten Dateneingang das erste Zufallssignal an und liefert an einem ersten Datenausgang einen zwischengespeicherten ersten logischen Pegel als erstes Bit.

Die jeweilige Abtasteinrichtung kann durch das jeweilige Zwischenspeicherelement gebildet werden. Insbesondere werden mehrere Zwischenspeicherelemente, wie beispielsweise mehrere Flipflops, kombiniert. Gemäß einer Weiterbildung wird durch jeweilige Inhalte der jeweiligen Zwischenspeicherelemente ein n-Tupel von Bits erzeugt .

Pro Sampeln, das heißt je einem Abtastvorgang, wird das n- Tupel durch die jeweiligen Inhalte der jeweiligen Zwischenspeicherelemente gebildet. Aus n Zwischenspeicherelementen mit jeweiligem Inhalt, also jeweiligen gespeicherten Pegeln, kann insbesondere ein n-Tupel gebildet werden.

Dies erhöht die Datenrate für die erzeugten Zufallsbits, da pro Sampeln eine durch die verbauten Zwischenspeicherelemente vorgegebene Anzahl von Bits erzeugt werden kann. In Abhängig- keit davon werden die Zufallsbits erzeugt.

In einer Weiterbildung wird der ersten Abtasteinrichtung und der mindestens einen zweiten Abtasteinrichtung ein gleichzeitiges Abtastsignal vorgegeben.

Das Abtasten des ersten Zufallssignals und des mindestens einen zweiten Zufallssignals erfolgt damit gleichzeitig oder nahezu gleichzeitig. Infolgedessen kann auch das erste Bit und das mindestens eine zweite Bit annähernd gleichzeitig ausgegeben werden sowie daraus das n-Tupel von Bits sowie daraus die Anzahl von Zufallsbits erzeugt werden. Je gleichzeitig durchgeführtem Sampeln entstehen also mehrere, das heißt mindestens zwei Bits, aus welchen die Anzahl von Zufallsbits erzeugt wird.

Gemäß einer Weiterbildung wird durch ein Takteingangssignal einer Delay-Flip-Flop-Schaltung das Abtastsignal gebildet. Eine Delay-Flip-Flop-Schaltung oder ein Delay- Flipflop oder Verzögerungs-Flipflop oder D- Flipflop ermöglicht ein getak- tetes Abtasten eines Signals. Das heißt insbesondere, dass die an mehreren Stellen innerhalb der elektronischen Schwingschaltung abgeleiteten Signale gleichzeitig durch das Vorge- ben eines Takteingangssignales am jeweiligen D-Flipflop gesampelt werden können.

Gemäß einer Ausführungsform wird durch die algorithmische Nachbearbeitung mehr als ein Bit Entropie erzeugt. Die Möglichkeit einer statistischen Abhängigkeit der gleichzeitig gesampelten Bits untereinander erfordert eine algorithmische Nachbearbeitung. Durch diese Nachbearbeitung wird ein gesampeltes Tupel derart nachbearbeitet, dass je nach Beschaffen- heit des Tupels aus einem Tupel mehr als ein Bit Entropie erzeugt wird.

Die algorithmische Nachbearbeitung kann je nach Anforderung dahingehend adaptiert werden, dass bei weniger aufwändiger Nachbearbeitung ein geringerer Teil der Entropie aus dem gesampelten Tupel extrahiert wird als bei einer aufwändigeren Nachbearbeitung, bei welcher ein größerer Teil der Entropie extrahiert wird. Asymptotisch kann die gesamte gesampelte Entropie extrahiert werden .

Von entscheidender Bedeutung für die Zufallszahlenerzeugung mit simultanem Sampeln mehrerer Signale einer elektronischen Schwingschaltung ist es, ein geeignetes algorithmisches Nachbearbeitungsverfahren zu verwenden, welches trotz der poten- tiell zwischen den simultan gesampelten Bits vorhandenen statistischen Abhängigkeiten statistisch unabhängige Outputbits liefert oder wenigstens Outputbits, die sich praktisch nicht von statistisch unabhängigen unterscheiden lassen. Setzt man voraus, dass die zu verschiedenen Zeitpunkten gesampelten Tupel von Bits einer stationären Verteilung gehorchen und voneinander statistisch unabhängig sind, dann ist das Nachbearbeitungsverfahren aus der Veröffentlichung von Ari Juels, Markus Jakobsson, Elizabeth A. M. Shriver, Bruce Hillyer "How to turn loaded dice into fair coins" in den IEEE Transactions on Information Theory Vol. 46 No . 3 pp . 911-921, 2000 optimal zur algorithmischen Nachbearbeitung geeignet. Man kann sagen, dass dieses Verfahren asymptotisch die gesamte in den Bits vorhandene Entropie extrahiert.

Die Annahme einer stationären Verteilung wird durch in der letzten Zeit von Forschern durchgeführte Untersuchungen der Akkumulation des Jitters in klassischen Ringoszillatoren in Frage gestellt. Die Ringoszillatoren haben offensichtlich einen Gedächtnismechanismus, der sich auch über längere Zeiträume von mehreren Millisekunden erstreckt.

Vor diesem Hintergrund erscheint die Annahme einer stationären Verteilung von durch chaotisch schwingende rückgekoppelte Logikschaltungen erzeugten Zufallsbits gegebenenfalls nicht gerechtfertigt. Es stellt sich daher die Frage nach einem an- gemessenen algorithmischen Nachbearbeitungsverfahren für Zufallsbits aus einer nicht stationären Verteilung.

Gemäß einer Weiterbildung wird die algorithmische Nachbearbeitung durch eine kryptographische Funktion durchgeführt.

Es kommen hier insbesondere kryptographische Funktionen in Frage. Diese sind eine aus praktischer Sicht brauchbare Lösung, insbesondere falls in einem System zur Zufallszahlenerzeugung kryptographische Funktionen vorgesehen sind.

Als kryptographische Funktionen zur Nachbearbeitung kommen Blockchiffren und Hashfunktionen in Frage. Bei beiden nimmt man aus resultierenden Zufallsbits nicht die gesamte Blockbreite, sondern etwas weniger Bits, als man den

Entropiegehalt des Inputs konservativ abgeschätzt hat. Hash- funktionen stellen wegen der für diese Anwendung nicht benötigten Kollisionsfreiheit einen Overkill dar, ihr Einsatz kann dennoch sinnvoll sein, wenn die Hashfunktion auch für andere Zwecke benötigt wird.

Die Erfindung umfasst ferner eine Vorrichtung zum Erzeugen von einer Anzahl von Zufallsbits mit einer elektronischen Schwingschaltung, mit einer ersten Abtasteinrichtung und mindestens einer zweiten Abtasteinrichtung,

zum gleichzeitigen Abgreifen eines ersten Bits an einer ersten Stelle in der elektronischen Schwingschaltung mittels der ersten Abtasteinrichtung und mindestens eines zweiten Bits an mindestens einer von der ersten Stelle abweichenden zweiten Stelle mittels der mindestens einen zweiten Abtasteinrichtung,

mit einer Nachbearbeitungskomponente zum Erzeugen der Anzahl von Zufallsbits mit Hilfe einer algorithmischen Nachbearbeitung in Abhängigkeit von dem ersten Bit und dem mindestens einen zweiten Bit,

wobei als Anzahl ein Wert größer als 1 erzeugbar ist.

Gemäß einer Weiterbildung umfasst die Vorrichtung mindestens eine weitere Einheit zum Ausführen des Verfahrens gemäß einem der beschriebenen Ausführungsformen und Weiterbildungen.

Die Erfindung wird nachfolgend mit Ausführungsbeispielen anhand der Figuren näher erläutert. Es zeigen:

Figur 1 ein schematisches Ablaufdiagramm des Verfahrens zum

Erzeugen von einer Anzahl von Zufallsbits;

Figur 2 eine schematische Darstellung der Vorrichtung zum

Erzeugen von einer Anzahl von Zufallsbits gemäß einem Ausführungsbeispiel der Erfindung.

Figur 1 zeigt ein schematisches Ablaufdiagramm für ein Verfahren zum Erzeugen von einer Anzahl von Zufallsbits mit einer elektronischen Schwingschaltung, wobei in einem ersten Schritt Sl ein erstes Bit durch eine erste Abtasteinrichtung an einer ersten Stelle in der elektronischen Schwingschaltung und mindestens ein zweites Bit durch mindestens eine zweite Abtasteinrichtung an mindestens einer von der ersten Stelle abweichenden zweiten Stelle gleichzeitig abgegriffen werden und wobei in einem zweiten Schritt S2 in Abhängigkeit von dem ersten Bit und dem mindestens einen zweiten Bit mit Hilfe ei- ner algorithmischen Nachbearbeitung die Anzahl von Zufallsbits erzeugt wird, und wobei als Anzahl ein Wert größer als 1 erzeugt wird. Bei einer experimentellen Untersuchung eines Fibonacci- Ringoszillators der Länge 14 auf einem Board mit einem

Spartan 3 FPGA der Firma Xilinx werden an den vorhandenen Ausgängen der 14 verbauten Inverter 14 jeweilige Zufallssignale ausgekoppelt und einer jeweiligen Abtasteinrichtung zu- geführt. Durch die jeweilige Abtasteinrichtung wird ein jeweiliges Bit ausgegeben. Dabei wird das jeweilige Zufallssignal im ersten Schritt Sl an den 14 Stellen gleichzeitig gesampelt. Das Rückkopplungspolynom lautet x 14 + x 13 + x 12 + x 10 + x 6 + x 4 + x 2 + x 1 + 1. Bei experimentell durchgeführtem 262144- maligem Sampeln wurden von der Anmelderin 7832 verschiedene Bitmuster als 14-Tupel beobachtet. Aus der Wahrscheinlichkeitsverteilung der auftretenden Bitmuster ergibt sich eine Entropieausbeute von 10.09 Bits pro gesampelten 14 Bits. Im zweiten Schritt S2 werden aus den gesampelten Tupeln mit Hilfe eines Nachbearbeitungsverfahrens beispielsweise 6 Zufallsbits erzeugt.

Die Anwendung des beschriebenen Verfahrens bedeutet eine Steigerung der Entropieausbeute um einen Faktor 10 im Vergleich zu bisher bekannten Verfahren zum Erzeugen von Zufallsbits .

Dies bedeutet einen erniedrigten Energieaufwand je erzeugtem Zufallsbit, da die in den Zuständen des Systems enthaltene Entropie vorteilhaft genutzt wird.

Figur 2 zeigt eine Vorrichtung 10 zum Erzeugen einer Anzahl k von Zufallsbits Z mit einer elektronischen Schwingschaltung 1, einer Abtasteinheit 2 und einer Nachbearbeitungskomponente 3. Die elektronische Schwingschaltung 1 ist beispielsweise ein klassischer Ringoszillator. Er besteht aus 15 Invertern. Bei einem klassischen Ringoszillator ist im Allgemeinen eine ungerade Anzahl von Invertern zu einem Ring verbunden.

Eine derartige Schaltung schwingt, da es stets genau einen Inverter im Ring gibt, bei welchem der aktuelle Output nicht dem logischen Inversen des aktuellen Inputs entspricht. Nach sehr kurzer Zeit nimmt der Output dieses Inverters jedoch den der logischen Funktionalität entsprechenden Zustand an, die Position des Inverters mit inkonsistentem Input und Output verschiebt sich um eine Position im Ring. Durch diese Verschiebungen des Inverters mit inkonsistentem Input und Output entstehen die Schwingungen des Ringoszillators.

Bei einem Ringoszillator aus 15 Invertern gibt es 15 mögliche Positionen für die Position des Inverters mit inkonsistentem Input und Output. Zusätzlich können an diesem Inverter Input und Output gleichzeitig den Wert von logisch 0 haben oder den Wert von logisch 1. Insgesamt ergibt sich für einen Ringoszillator der Länge 15 die Zahl seiner möglichen logischen Zu- stände als 2 x 15. Bei einer experimentellen Untersuchung auf einem Board mit einem Spartan 3 FPGA der Firma Xilinx treten bei gleichzeitigem Sampeln aller 15 Outputs der 15 Inverter 30 theoretisch geforderte Zustände auf. Theoretisch ergibt sich gemäß der Berechnung der informationstheoretischen Entropie über E =— * l°g2 Vi m it p; als Wahrscheinlichkeiten der beobachteten Muster oder Zustände eine Entropie von 4,90689 Bits bei idealer Gleichverteilung. Die Wahrscheinlichkeiten für die 30 Bitmuster sind experimentell unterschiedlich. Die nachfolgende Auflistung zeigt in der rechten Spalte die beobachteten Häufigkeiten der 30 unterschiedlichen in der linken Spalte aufgeführten Bitmuster.

001010101010101 80897

010010101010101 43615

010100101010101 87403

010101001010101 60396 010101010010101 58100

010101010100101 94117

010101010101001 72241

010101010101010 89319

010101010101011 49874

010101010101101 65542

010101010110101 120055

010101011010101 40179

010101101010101 82356

010110101010101 74662

011010101010101 90677

100101010101010 96420

101001010101010 85667

101010010101010 90990

101010100101010 42445

101010101001010 122643

101010101010010 77557

101010101010100 49930

101010101010101 83200

101010101010110 59139

101010101011010 82593

101010101101010 52999

101010110101010 50969

101011010101010 71200

101101010101010 40943

110101010101010 70427

Bei dieser experimentell beobachteten Verteilung ergibt sich eine Entropie von 4,84439 Bits pro gesampeltem 15-Bit-Muster .

Damit wird die bisher bei klassischen Ringoszillatoren durch einfaches Sampeln erzielbare Anzahl an Bits Entropie erheblich übertroffen. Die Erfindung ermöglicht also eine deutliche Steigerung der Entropieausbeute.

Figur 2 zeigt, wie mit Hilfe einer ersten Abtasteinrichtung AI und einer zweiten Abtasteinrichtung A2 das jeweilige hinter einem ersten Inverter II und einem zweiten Inverter 12 befindliche Signal abgegriffen wird. Dabei wird ein jeweiliger Pegel des ersten Zufallssignals hinter dem ersten Inver- ter II bzw. des zweiten Zufallssignals hinter dem zweiten In- verter 12 durch die erste Abtasteinrichtung AI bzw. die zwei- te Abtasteinrichtung A2 gespeichert. Es kann sich dabei um Zwischenspeicherelemente, wie insbesondere Delay-Flipflops handeln .

Ein Delay-Flipflop oder D-Flipflop speichert den jeweiligen Pegel zum durch ein Taktsignal oder Abtastsignal CK vorgegebenen Zeitpunkt. Dieser gespeicherte Pegel wird als erstes Bit Bl bzw. zweites Bit B2 einer Nachbearbeitungskomponente 3 bereitgestellt. Die Nachbearbeitungskomponente 3 erzeugt mit Hilfe einer algorithmischen Nachbearbeitung die Anzahl k Zu- fallsbits Z.

Eine aus 15 Invertern bestehende elektronische Schaltung kann in vorteilhafter Weise an bis zu 15 verschiedenen Stellen, das heißt hinter jedem Inverter innerhalb des klassischen Ringoszillators, sampeln und die jeweiligen abgegriffenen

Bits als 15-Tupel an die Nachbearbeitungskomponente 3 übergeben .

Die erste Abtasteinrichtung AI und die mindestens eine zweite Abtasteinrichtung A2 sind insbesondere als separate Abtasteinheit 2 ausgeführt. Das Abtastsignal ist dann gemeinsames Takteingangssignal für die jeweiligen Eingänge der jeweiligen Abtasteinrichtungen. Die Nachbearbeitungskomponente 3 ist insbesondere nach der Abtasteinheit 2 verbaut. Insbesondere stellt die Abtasteinheit 2 das n-Tupel als Eingangssignal der Nachbearbeitungskomponente bereit .

Das beschriebene Verfahren kann insbesondere mit dem Einsatz von Fibonacci- oder Galois-Ringoszillatoren verknüpft werden. Auch für die aus den chaotischen Schwingungen eines

Fibonacci-Ringoszillators resultierenden unterschiedlichen Pegel innerhalb der elektronischen Schwingschaltung ist ein zeitlich paralleles, das heißt gleichzeitiges Abtasten an un- terschiedlichen, vorzugsweise möglichst vielen Stellen innerhalb des Ringoszillators möglich.

Auch für Mehrspurzufallszahlengeneratoren mit oder ohne Rück- kopplung ist das Verfahren vorteilhaft anwendbar. Auch hier werden statistische Abhängigkeiten der jeweils gesampelten Bits durch ein Nachbearbeitungsverfahren, wie insbesondere das von Ari Juels, Markus Jakobsson, Elizabeth A. M. Shriver und Bruce Hillyer vorgeschlagene oben erwähnte Nachbearbei- tungsverfahren, beseitigt.

Es ist ein algorithmisches Nachbearbeitungsverfahren zu wählen, welches potentiell mehr als ein Zufallsbit erzeugt. Bekannte Verfahren wie das von-Neumann-Verfahren erzeugen ein einziges Zufallsbit. Die aus den gebildeten Tupeln der gesampelten Bits extrahierbare Entropie ist größer als ein Bit, so dass eine Verwendung eines entsprechenden algorithmischen Nachbearbeitungsverfahrens, welches potentiell mehr als ein Zufallsbit erzeugt, vorteilhaft ist. Somit wird insbesondere eine Anzahl k von Zufallsbits Z erzeugt, welche größer als 1 ist .