Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
METHOD AND DEVICE FOR GENERATING RANDOM BITS
Document Type and Number:
WIPO Patent Application WO/2014/117983
Kind Code:
A1
Abstract:
The invention relates to a method for generating a random bit, the method comprising: Generating (S1) a noise signal (RS); scanning (S2) the noise signal (RS) subject to a clock signal (CK) with the aid of a first intermediate storage element (3) for generating a first bit value (B1); scanning (S2) of the noise signal (RS) subject to the clock signal (CK) with the aid of at least one additional intermediate storage element (4) for generating at least one additional bit value (B2); and determining at least one random bit (ZS) subject to the generated bit values (B1, B2). A device (1, 100, 101) for generating a random bit comprises: A noise signal source (2) for generating a noise signal (RS), a first intermediate storage element (3), and at least one additional intermediate storage element (4) for simultaneously scanning the noise signal (RS) subject to a clock signal (CK).

Inventors:
DICHTL MARKUS (DE)
MEYER BERND (DE)
Application Number:
PCT/EP2014/050308
Publication Date:
August 07, 2014
Filing Date:
January 09, 2014
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
SIEMENS AG (DE)
International Classes:
G06F7/58
Domestic Patent References:
WO2003093971A22003-11-13
Other References:
OCTAVIAN CRE ET AL: "Implementing True Random Number Generators Based on High Fanout Nets", ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY VOLUME, 3 November 2012 (2012-11-03), pages 277 - 298, XP055112731, Retrieved from the Internet [retrieved on 20140408]
FISCHER V ET AL: "TRUE RANDOM NUMBER GENERATOR EMBEDDED IN RECONFIGURABLE HARDWARE", CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS. INTERNATIONALWORKSHOP, XX, XX, 13 August 2002 (2002-08-13), pages 415 - 430, XP001160534
MEHRDAD MAJZOOBI ET AL: "FPGA-Based True Random Number Generation Using Circuit Metastability with Adaptive Feedback Control", 28 September 2011, CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS Â CHES 2011, SPRINGER BERLIN HEIDELBERG, BERLIN, HEIDELBERG, PAGE(S) 17 - 32, ISBN: 978-3-642-23950-2, XP019166873
ARI JUELS; MARKUS JAKOBSSON; ELIZABETH A. M. SHRIVER; BRUCE HILLYER: "How to turn loaded dice into fair coins", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 46, no. 3, 2000, pages 911 - 921
ARI JUELS; MARKUS JAKOBSSON; ELIZABETH A. M. SHRIVER; BRUCE HILLYER: "How to turn lo aded dice into fair coins", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 46, no. 3, 2000, pages 911 - 921
Download PDF:
Claims:
Patentansprüche

1. Verfahren zum Erzeugen eines Zufallsbits umfassend:

Erzeugen (S1) eines Rauschsignals (RS) ;

Abtasten (S2) des Rauschsignals (RS) in Abhängigkeit von einem Taktsignal (CK) mit Hilfe eines ersten Zwischenspeicherelements (3) zum Erzeugen eines ersten Bitwertes (Bl) ;

Abtasten (S2) des Rauschsignals (RS) in Abhängigkeit von dem Taktsignal (CK) mit Hilfe mindestens eines weiteren Zwi- schenspeicherelements (4) zum Erzeugen mindestens eines weiteren Bitwertes (B2) ; und

Bestimmen (S3) mindestens eines Zufallsbits (ZS) in Abhängigkeit von den erzeugten Bitwerten (B1, B2) . 2. Verfahren nach Anspruch 1, wobei das Abtasten des Rauschsignals (RS) zu vorgegebene Taktflanken gleichzeitig mit Hilfe des ersten und der weiteren Zwischenspeicherelemente (3, 4) erfolgt. 3. Verfahren nach Anspruch 1 oder 2, wobei das Rauschsignal (RS) mit Hilfe einer physikalischen Rauschquelle (2) erzeugt wird.

4. Verfahren nach einem der Ansprüche 1 - 3, wobei das

Rauschsignal (RS) mit Hilfe eines insbesondere digitalen Ringoszillators (20) erzeugt wird.

5. Verfahren nach einem der Ansprüche 1 - 4, wobei das

Rauschsignal (RS) direkt an einen jeweiligen Dateneingang (D) der Zwischenspeicherelemente (3, 4) zugeführt wird.

6. Verfahren nach einem der Ansprüche 1 - 5, wobei mindestens fünf Bitwerte (B1...BN) erzeugt werden. 7. Verfahren nach einem der Ansprüche 1 - 6, ferner umfassend: Abbilden der Bitwerte (B1...BN) auf Bytes mit Hilfe einer Hash-Funktion.

8. Verfahren nach einem der Ansprüche 1 - 7, ferner umfassend: Unterziehen der Bitwerte (B1...BN) oder der Bytes einem Verfahren zum Erzeugen von vorgegebenen Zufallsmustern von Bitwerten.

9. Verfahren nach einem der Ansprüche 1 - 8, ferner umfassend: Zuordnen der bei einem Abtasten erzeugten Bitwerte (B1..B.N) zu einem vorgegebenen Zufallswert . 10. Verfahren nach einem der Ansprüche 1 - 9, wobei das Erzeugen der Bitwerte (Bl, B2) mehrfach nacheinander erfolgt, und das Bestimmen (S3) mindestens eines Zufallsbits (ZS) in Abhängigkeit von mehreren zuvor erzeugten Bitwerten (B1, B2) erfolgt .

11. Vorrichtung (1, 10) zum Erzeugen eines Zufallsbits mit: einer Rauschsignalquelle (2) zum Erzeugen eines Rauschsignals {RS) ;

einem ersten Zwischenspeicherelement (3) und mindestens einem weiteren Zwischenspeicherelement (4) zum gleichzeitigen Abtasten des Rauschsignals (RS) in Abhängigkeit von einem Taktsignal (CK) .

12. Vorrichtung (1, 10) nach Anspruch 11, welche eingerichtet ist, ein Verfahren nach einem der Ansprüche 1 - 10 durchzuführen .

13. Vorrichtung (1, 10) nach Anspruch 11 oder 12, wobei die Zwischenspeicherelemente (3, 4) Flip-Flop-Einrichtungen sind.

14. Vorrichtung (1, 10) nach einem der Ansprüche 11 - 13, wobei die Vorrichtung (1, 10) ausschließlich digitale Bauelemente umfasst.

15. Vorrichtung (1, 10) nach einem der Ansprüche 11 - 14, wo bei die Vorrichtung (1, 10) Teil einer FPGA-Einrichtung ist.

Description:
Beschreibung

Verfahren und Vorrichtung zum Erzeugen von Zufallsbits Die vorliegende Erfindung betrifft ein Verfahren zum Erzeugen eines Zufallsbits sowie eine Vorrichtung zum Erzeugen eines oder mehrerer Zufallsbits. Es wird zum Beispiel eine Zufallsbitfolge erzeugt, welche als binäre Zufallszahl verwendet wird. Die vorgeschlagenen Vorrichtungen und Verfahren zum Er- zeugen von Zufallsbits dienen beispielsweise der Implementierung von Zufallszahlengeneratoren.

Zufallsdaten werden beispielsweise bei Sicherheitsanwendungen benötigt. So können aus Zufallsbits kryptographische Schlüs- sei oder dergleichen abgeleitet werden. Im Idealfall haben erzeugte Zufallsbits eine gleiche Auftrittswahrscheinlichkeit und sind voneinander statistisch unabhängig. Dazu wird eine Zufallsquelle zur Erzeugung der Zufallsbits mit einer hohen Entropie gewünscht.

Aus den erzeugten Zufallsbits können weitere komplexere Zufallszahlen, wie Zufallsbitfolgen oder Zufallsbytes, abgeleitet werden. In der Vergangenheit wurden unter Anderem physikalische Prozesse, wie radioaktive Zerfälle, als zufällige Ereignisse liefernde Objekte verwendet. Dabei besteht die Schwierigkeit darin, Messungen an dem physikalischen System aufwandsgünstig durchzuführen, um die Zufallsdaten ableiten zu können. Wün- sehenswert sind insbesondere Implementierungen, die keine

Mischsignale aus analogen und digitalen Elementen erfordern.

Pseudozufallszahlengeneratoren sind bekannt und erzeugen aufgrund eines Algorithmus aus so genannten Seed-Daten Zufalls- bits . Da nach der Seed-Festlegung die abgeleitete Pseudozu- fallsbitfolge im Wesentlichen deterministisch ist, eignen sich derartige Zufallszahlengeneratoren eher nicht für kryptographische Anwendungen. In der Vergangenheit wurden Hardware-Zufallszahlengeneratoren unter der Ausnutzung von Schwankungen von Periodenlängen bzw. Jittern in RingoszillatorSchaltungen ausgenutzt. Häufig ge- nügte die erzielte Entropie und/oder Zufallsdatenrate jedoch nicht den gewünschten Anforderungen.

Daher ist eine Aufgabe der vorliegenden Erfindung, ein verbessertes Verfahren und/oder ein verbesserte Vorrichtung zum Erzeugen von Zufallsbits bereitzustellen.

Demgemäß wird ein Verfahren zum Erzeugen eines Zufallsbits vorgeschlagen, welches die Schritte umfasst:

Erzeugen eines Rauschsignals;

Abtasten des Rauschsignals in Abhängigkeit von einem

Taktsignal mit Hilfe eines ersten Zwischenspeicherelements zum Erzeugen eines ersten Bitwertes;

Abtasten des Rauschsignals in Abhängigkeit von dem Taktsignal mit Hilfe mindestens eines weiteren Zwischenspeicher- elements zum Erzeugen mindestens eines weiteren Bitwertes; und

Bestimmen mindestens eines Zufallsbits in Abhängigkeit von den erzeugten Bitwerten. Ferner wird eine Vorrichtung zum Erzeugen eines Zufallsbits vorgeschlagen, die aufweist:

eine Rauschsignalquelle zum Erzeugen eines Rauschsignals;

ein erstes Zwischenspeicherelement und mindestens ein weiteres Zwischenspeicherelement zum gleichzeitigen Abtasten des Rauschsignals in Abhängigkeit von einem Taktsignal.

Die Vorrichtung ist dabei insbesondere eingerichtet, ein entsprechendes Verfahren zum Erzeugen eines Zufallsbits durchzu- führen . In Ausführungsformen hat die Vorrichtung mindestens drei Zwischenspeicherelemente. Dadurch wird eine gute Entropie der ein Bitmuster erzeugenden Bitwerte erreicht. Das Rauschsignal stammt beispielsweise von einer Rauschsignalquelle, die ein Signal erzeugt. Beispielsweise können unregelmäßige Schwingungen erzeugt werden. Die Rauschsignalquelle kann ein auch echtes Zufallssignal liefern, welches zwischen vorgegebenen Signalpegeln schwankt. Durch das gleichzeitige Abtasten des Rauschsignals in der Art eines Sample in Abhängigkeit von einem Taktsignal zu einem Taktzeitpunkt wird in den Zwischenspeicherelementen ein jeweiliger Pegel erfasst und zwischengespeichert. Der erfasste Pegel entspricht dann einem Bitwert, beispielsweise 0 oder 1 bzw. L oder H.

Das insbesondere analoge Rauschsignal wird somit gleichzeitig mehrfach abgetastet, wobei beispielsweise durch physikalische Unterschiede der implementierten Zwischenspeicherelemente in einem Halbleiterprozess Abweichungen entstehen. Auch eine Signallaufzeit kann zu unterschiedlichen Abtastergebnissen und damit unterschiedlichen Bitwerten führen. Das Zwischenspeicherelement ist beispielsweise ein Flip-Flop. Insbesondere bei einem D-Flip-Flop erfordert das Abtasten des Eingangs- signals, in dem vorliegenden Fall des Rauschsignals, bei einer Taktflanke. Da das Rauschsignal einen unregelmäßigen zeitlichen Signalverlauf hat, ergeben sich aus der unterschiedlichen physikalischen Implementierung der Zwischenspeicherelemente Ungenauigkeiten bzw. Zufälligkeiten. Beispiels- weise kann es zu Verletzungen von Setup- und Hold-Zeiten der Flip-Flops kommen, so dass unterschiedliche Messergebnisse an unterschiedlichen Zwischenspeicherelementen erfasst werden. In den Zwischenspeicherelementen potenziell auftretende metastabile Zustände können dabei ebenfalls als Quelle von Zufall verwendete werden.

Es wird verstanden, dass eine Taktsignalquelle ein entsprechendes regelmäßig zwischen zwei Pegeln schwankendes Taktsig- nal erzeugt, wobei das Taktsignal steigende und fallende Taktflanken umfasst. Das erzeugte Taktsignal wird Takteingängen der Zwischenspeicherelemente zugeführt, welche aufgrund von Signalcharakteristiken, beispielsweise Signalflanken, in- tern eine Abtastung des Signalpegels an einem Dateneingang vollziehen und als logischen Pegel interpretieren. Der logische Pegel wird dann als Bitwert verstanden und ausgegeben.

Die Strecke von der Taktsignalquelle zu den verschiedenen Zwischenspeicherelementen kann verschieden sein, und das

Taktsignal kann daher unterschiedlich durch den Signalpfad beeinflusst werden, sodass die Signalformen sich gering unterscheiden können. Unter dem Taktsignal an einem jeweiligen Zwischenspeicherelement wird verstanden, dass ausgehend von dem Taktsignalerzeuger das Taktsignal verzweigt als „Zweigtaktsignale" den Zwischenspeicherelementen zugeführt wird. Das jeweilige Zweigtaktsignal entspricht daher im Wesentlichen modulo der Ein- flüsse durch den Signalweg oder anderer Faktoren dem erzeugten Taktsignal.

Bei den Zwischenspeicherelementen kann man auch von Sample- and-Hold oder Abtast-und Haltegliedern sprechen. Im Wesentli- chen kommen jedoch Flip-Flops zum Einsatz.

In Ausführungsformen des Verfahrens und/oder der Vorrichtung zum Erzeugen eines Zufallsbits wird das Rauschsignal direkt an einen jeweiligen Dateneingang der Zwischenspeicherelemente zugeführt bzw. die Dateneingänge der Zwischenspeicherelemente sind an einen gemeinsamen Leitungsknoten gekoppelt, an dem das Rauschsignal abgreifbar ist.

In Ausführungsformen des Verfahrens und der Vorrichtung wird das Rauschsignal mit Hilfe einer physikalischen Rauschquelle erzeugt. Es ist auch denkbar, dass das Rauschsignal mit Hilfe eines digitalen Ringoszillators erzeugt wird. Umfasst die Rauschsignalquelle einen digitalen Ringoszillatorschaltkreis, ist eine ungerade Anzahl von Invertereinrichtungen rückgekoppelt, so dass sich ein im Wesentlichen oszillierendes Signal ergibt. Bei besonders kurzen Inverterketten, beispielsweise drei oder fünf Inverter, ergibt sich eine quasi-analoge Sig- nalform durch den kurzen Rückkopplungspfad. Ein derartiges Oszillationssignal kann als Rauschsignal aufgefasst werden.

In Ausführungsformen umfasst ein entsprechender digitaler Ringoszillator zwischen drei und zehn Inverter, die direkt oder indirekt miteinander rückgekoppelt sind. In weiteren Ausführungsformen sind elf bis zwanzig Inverter rückgekoppelt.

In weiteren Ausführungsformen umfassen die digitalen Ringos- zillatorschaltkreise Glois- oder Fibonacci- und/oder einfache Ringoszillatoren.

Vorzugsweise umfasst die Vorrichtung zum Erzeugen von Zufallsbits ausschließlich digitale Bauelemente. Dies hat den Vorteil, dass keine gemischten Signalschaltkreise notwendig sind, die analoge und digitale Signale verarbeiten müssen. Insofern ist auch eine Herstellung mit Hilfe rein digitaler Schaltungskomponenten aufwandsgünstig möglich. Ein Zufallszahlengenerator bzw. eine Vorrichtung zum Erzeugen von Zu- fallszahlen kann dann mit Hilfe von Standard- Halbleiterprozessen hergestellt werden oder auch als FPGA oder in FPGA-Einrichtungen umgesetzt werden.

Bei Varianten des Verfahrens kann das Erzeugen der Bitwerte mehrfach nacheinander erfolgen, und das Bestimmen mindestens eines Zufallsbits wird dann in Abhängigkeit von mehreren zuvor erzeugten Bitwerten durchgeführt. Insofern wird aus den Sätzen von Bitwerten oder Bitmustern, die sukzessive erzeugt werden die „enthaltene" Zufälligkeit ausgenutzt um im Wesent- lichen zufällige Daten abzuleiten.

In Ausführungsformen des Verfahrens bzw. einer entsprechend implementierten Vorrichtung, die beispielsweise einen pro- grammierbaren Mikroprozessor, einen Mikrocontroller oder dergleichen als Steuereinrichtung umfasst, erfolgt ein Abbilden der Bitwerte auf Bytes mit Hilfe einer Hashfunktion. Es werden beispielsweise die bei einem Abtastvorgang erzeugen Bit- werte einer vorgegebenen Bitbreite (Anzahl der Bitwerte) auf ein Wort geringerer Bitbreite, beispielsweise eines Bytes abgebildet .

Es kann ferner eine Nachbearbeitung der Bitwerte oder Bytes erfolgen. Dabei wird z.B. ein abgewandeltes Neumann-Verfahren zum Erzeugen von vorgegebenen Zufallsmustern von Bitwerten eingesetzt. Ein denkbares Verfahren ist beschrieben in: Ari Juels, Markus Jakobsson, Elizabeth A. M. Shriver, Bruce

Hillyer: „How to turn loaded dice into fair coins" in IEEE Transactions on Information Theory, Vol. 46, No. 3, Pg. 911- 921, Year: 2000.

Ausführungsformen des Verfahrens sehen vor, dass die bei einem Abtasten erzeugten Bitwerte einem vorgegebenen Zufalls- wert zugeordnet werden. Es wird beispielsweise bei jedem Abtasten ein Zufallsmuster erzeugt, wobei abhängig von der Bitbreite bzw. der Anzahl der bei einem Abtasten erzeugten Zufallsbits eine begrenzte Anzahl von verschiedenen Mustern erzeugt werden kann. Dies hängt von der konkreten elektroni- sehen bzw. physikalischen Ausgestaltung der Vorrichtung ab.

Um Korrelationen zwischen Bitwerten bzw. Bits zu reduzieren oder zu kompensieren, sind geeignete Verfahren bekannt. Insgesamt ermöglicht das Verfahren einen schaltungstechnisch einfach zu realisierenden Zufallszahlengenerator. Es ist nur geringe Anzahl von elektronischen Komponenten notwendig, die standardmäßig hergestellt werden können. Aufgrund der Erzeugung von mehreren Bitwerten bei einem Abtastvorgang kann die Datenrate gegenüber bekannten Zufallsbiterzeugern erhöht werden. In Ausführungsformen werden vorzugsweise zwischen 48 und 72 Bitwerte erzeugt, insbesondere 64 Bitwerte. Daraus werden mindestens zwei verschiedene Zufallsbits erzeugt bzw. abgeleitet.

Weitere mögliche Implementierungen der Erfindung umfassen auch nicht explizit genannte Kombinationen von zuvor oder im Folgenden bezüglich der Ausführungsbeispiele beschriebenen Verfahrensschritte, Merkmale oder Ausführungsformen des Ver- fahrens oder des Zufallsbitgenerators. Dabei wird der Fachmann 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 Zusammenhang mit der folgenden Beschreibung der Ausführungsbeispiele, die im Zusammenhang mit den Zeichnungen näher erläu- tert werden.

Dabei zeigen:

Fig. 1 eine schematische Darstellung eines ersten Aus- führungsbeispiels für eine Vorrichtung zum Erzeugen von Zufallsbits;

Fig. 2 ein schematisches Ablaufdiagramm für ein Verfahren zum Erzeugen von Zufallsbits;

Fig. 3 eine schematische Darstellung eines zweiten Ausführungsbeispiels für eine Vorrichtung zum Erzeugen von Zufallsbits; und Fig. 4 ein Diagramm zur Erläuterung von Korrelationen zwischen Zufallsbitwerten . In den Figuren sind gleiche oder funktionsgleiche Elemente mit denselben Bezugszeichen versehen, sofern nichts anderes angegeben ist. Die Figur 1 zeigt eine schematische Darstellung eines ersten Ausführungsbeispiels für eine Vorrichtung 1 zum Erzeugen von Zufallsbits. Zum Erläutern des Betriebs und der Erzeugung von Zufallsbits ist in der Fig. 2 schematisch ein Ablaufdiagramm für ein Verfahren zum Erzeugen von Zufallsbits angedeutet.

Die erste Ausführungsform eines Zufallsbitgenerators 1 um- fasst einen Rauschsignalgenerator 2, der an einem Ausgang 5 ein Rauschsignal RS liefert. Beim Rauschsignal RS handelt es sich beispielsweise um ein analoges oder quasi-analoges Sig- nal, das von der Rauschquelle 2 erzeugt wird. Das Rauschsignal RS ist vorzugsweise durch miteinander gekoppelte Digitalschaltelemente im Rauschsignalgenerator 2 erzeugt.

Die Vorrichtung 1 umfasst zwei Zwischenspeicherelemente, die als D-Flip-Flops 3, 4 ausgestaltet sind. Jedes Flip-Flop 3, 4 hat einen Dateneingang D, einen Takteingang C und einen Datenausgang Q. Das Rauschsignal RS ist direkt an die Dateneingänge D der Flipflops 3, 4 zugeführt. An die Takteingänge C der Flipflops 3, 4 ist ein gemeinsames Taktsignal CK einge- koppelt. An den Ausgängen Q der Flipflops 3, 4 sind Bitwerte in Abhängigkeit von dem zwischengespeicherten bzw. gesampelten Pegel des Rauschsignals RS abgreifbar. Dazu sind die Ausgänge Q an einen jeweiligen Ausgang 6, 7 der ZufallsbitgeneratorVorrichtung geführt. An den Ausgängen 6, 7 sind Bitwerte Bl bzw. B2 abgreifbar.

Die Flipflops 3, 4 liefern im Wesentlichen wohldefinierte logische Pegel 0, 1 bzw. L, H als Bitwerte Bl, B2. Das Rauschsignal RS schwankt hingegen zwischen vorgegebenen Pegeln un- regelmäßig, so dass nicht vorhersehbar ist, welcher logische Pegel von den Flip-Flops 3, 4 zum jeweiligen Taktflankenzeit- punkt erfasst bzw. abgetastet ist. Zum Erzeugen von wenig korrelierten Zufallsbitwerten an den Ausgängen 6, 7 erfolgt in einem ersten Schritt Sl die Bereitstellung des Rauschsignals RS. Anschließend erfolgt in Abhängigkeit von dem Taktsignal CK, beispielsweise bei einer stei- genden oder fallenden Taktsignalflanke, ein Sampeln oder Abtasten des an die Dateneingänge D geführten Rauschsignals RS im Schritt S2. Aufgrund von beispielsweise Verletzungen von Setup- und Hold-Zeiten für die Flip-Flops 3, 4 oder sonstigen dem bestimmungsgemäßen Betrieb von Flip-Flops entgegenwirken- den Betriebsparameter, entsteht Zufälligkeit oder Entropie, welche zur Erzeugung von Zufallsbits aus den Bitwerten Bl, B2 genutzt werden kann. Im Schritt S3 erfolgt daher in Abhängigkeit von den erzeugten Bitwerten Bl, B2 die Bestimmung eines Zufallsbits. Es ist möglich, dass die unterschiedlich abge- tasteten bzw. erzeugten Bitwerte Bl, B2 von Betriebsbedingungen wie Temperaturspannung oder externen Feldern abhängt. Auch Fertigungsschwankungen bei der physikalischen Implementierung der Flipflops 3, 4 oder die Geometrie der Schaltung und Signallaufzeit können zu unterschiedlichen Abtastergeb- nissen trotz desselben Taktsignals CK führen.

Durch mehrfaches Sampeln hintereinander und einer statistischen Auswertung können Korrelationen der an den Ausgängen 6, 7 abgreifbaren Bitwerten behandelt oder kompensiert werden, sodass echte Zufallsbits oder Zufallswerte abgeleitet werden können. Im Wesentlichen ergeben sich in der einfachen Darstellung der Fig. 1 vier mögliche Bitmuster B1 B2 = 01, 10, 11, 00. Es wird beispielsweise bei jeder steigenden Taktflanke ein entsprechendes "Zufallsbitmuster" erzeugt.

In der Fig. 3 ist eine weitere Ausführungsform für einen Zu- fallsbitgenerator dargestellt. Der Zufallsbitgenerator 10 um- fasst eine (analoge) Rauschquelle 20, die an einem Ausgang 5 ein zufälliges Rauschsignal RS liefert. Die Vorrichtung 10 umfasst beispielsweise N = 64 D-Flip-Flops 3-1 bis 3-N, die jeweils Dateneingänge D, Takteingänge C und Datenausgänge Q haben. Die Dateneingänge D sind gemeinsam an den Ausgang 5 gekoppelt und empfangen das Rauschsignal RS. Die Vorrichtung ist mit einem Taktsignalgenerator 9 ausgestattet, der ein Taktsignal CK liefert, welches in die Takteingänge C der Flip-Flops 3-1 bis 3-N geführt ist. Eine Steuereinrichtung 8, beispielsweise ein Mikrocontroller oder Prozessor, der geeig- net programmiert oder eingerichtet ist, steuert über Steuersignale CT1 und CT2 die Rauschquelle 20 und den Taktgenerator 9.

In der Ausführungsform der Fig. 3 ist die Rauschsignalquelle 20 als Ringoszillator mit drei rückgekoppelten Invertern 12, 13, 14 ausgestaltet. Der Rückkopplungspfad ist über einen steuerbaren Schalter 15 unterbrechbar. Der steuerbare Schalter ist beispielsweise durch Steuersignale CT1 von der Steuereinrichtung 8 steuerbar. Ein wohldefinierter Signalpegel, beispielsweise H oder L, kann an einem Knoten 16 abgegriffen werden. Der Schalter 15 schaltet zwischen dem wohldefinierten Pegel bei einem geöffneten Rückkopplungspfad und einem geschlossenen Rückkopplungspfad. Regelmäßig wird beispielsweise der Pfad geschlossen, so dass eine zufällige Oszillation des Ringoszillators einsetzt. Aufgrund des besonders kurzen Rückkopplungspfads mit nur drei Invertern ergibt sich ein analoges Rauschsignal RS am Ausgang 5.

Beim Betrieb des Zufallsbitgenerators 10 wird in Abhängigkeit von dem Taktsignal CK das Rauschsignal RS parallel und gleichzeitig von den Flip-Flops 3-1 bis 3-N abgetastet, wodurch ein jeweiliges Bit bzw. ein Bitwert B1-BN erzeugt wird, der am jeweiligen Ausgang Q abgreifbar ist. Das Bitmuster aus den Bitwerten Bl-BN wird über eine geeignete Datenleitung an den Eingang 17 der Steuereinrichtung 8 geführt. Die Steuereinrichtung 8 kann die erfassten Bitmuster Bl-BN auswerten oder nachbehandeln. Beispielsweise können durch geeignete Rechenverfahren Schiefen oder Korrelationen der Bitwerte ausgeglichen werden.

Am Ausgang 8 in der Steuereinrichtung 8 liegt dann ein Zufallsbit oder Zahlensignal ZS an, welches am Ausgang 11 des Zufallsbitgenerators 10 ausgegeben wird. Der Zufallsbit- oder Zahlengenerator 10 kann beispielsweise als FPGA implementiert sein.

Untersuchungen der Anmelderin haben ergeben, dass beispiels- weise bei Implementierung der in Fig. 3 schematisch dargestellten Vorrichtung als FPGA mit N = 64 Flip-Flops eine verhältnismäßig geringe Korrelation der 64 Bits B1-B64 auftritt. Es ergibt sich beispielsweise, dass bei wiederholtem Starten des Ringoszillators 20 und nach einer vorgegebenen Zeit durch das Abtasten der Bitwerte Bl-BN etwa 150 verschiedene Bitmuster auftreten. Daraus ergibt sich pro Messung eine Entropie von 5,2 Bits. Insofern lassen sich Zufallsworte der Bitbreite 5 einigermaßen zuverlässig mit Hilfe der Vorrichtung 10 erzeugen .

Die Fig. 4 zeigt ein Korrelationsdiagramm mit Grauwerten, wobei ein schwarzes Kästchen eine Korrelation von 1 und ein weißes Kästchen eine Korrelation von -0,81 darstellt. An den Kanten sind jeweils die 64 möglichen Bitwerte B1-B64 aufge- tragen. Man erkennt, dass jedes Bit mit sich selbst zu 100% korreliert. Man erkennt ferner, dass Gruppen von Bits auftreten, die relativ stark miteinander korrelieren, während andere Bits weitestgehend unkorreliert vorliegen. Die Korrelation der abgetasteten Rauschsignalanteile und der daraus erzeugten Bitwerte Bl-BN kann beispielsweise von der Topologie der realisierten Digitalschaltung abhängen. Bei der Implementierung des Zufallsbitgenerators als FPGA kann die Zusammenfassung als konfigurierbare Logikblöcke von Multiple- xern, Addierern, Flip-Flops und dergleichen zu Korrelation führen, da beispielsweise bei bestimmten Flip-Flop-Gruppen Signalwege besonders ähnlich verlaufen.

Die erfassten Bitmuster aus 64 Bits können beispielsweise mit Hilfe eines Hashings auf Bytes abgebildet werden und dann mit Hilfe bekannter Verfahren nachbearbeitet werden. Ein geeignetes Verfahren ist zum Beispiel in Ari Juels, Markus Jakobs- son, Elizabeth A. M. Shriver, Bruce Hillyer: „How to turn lo- aded dice into fair coins" in IEEE Transactions on Information Theory, Vol. 46, No. 3, Pg. 911-921, Year: 2000 angegeben. Insofern ergibt sich potenziell ein Mehraufwand bei der Nachbearbeitung der erzeugten Bitmuster, die beispielsweise durch einen Mikroprozessor oder geeignete Software bewerkstelligt werden kann. Dennoch kann eine besonders hohe Bitrate mit Zufallsbits erzielt werden.

Die vorgeschlagenen Verfahren und Vorrichtungen basieren im Wesentlichen auf ausschließlich digitalen Schaltungskomponen- ten, so dass Standardprozesse zur Fertigung eingesetzt werden können. Es ist trotz der quasi-analogen Rauschsignalerzeugung mit Hilfe von kurzen Ringoszillatoren keine aufwändige Mixed- Signal-Implementierung notwendig. Insgesamt werden nur wenige elektronische Komponenten benötigt, so dass auch kostensensitive Anwendungen mit entsprechend Zufallsbit- oder Zahlengeneratoren ausgestattet werden können.

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 eingeschränkt und andere Variationen können vom Fachmann hieraus abgeleitet werden, ohne den Schutzumfang der Erfindung zu verlassen.