-
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 Authentifikationsverfahren
notwendig, Zufallszahlen zu erzeugen und zu verwenden. Insbesondere
bei RFID-Tags mit Sicherheitsfunktionalität sind entsprechende
Zufallszahlen mit besonders niedrigem Hardwareaufwand zu generieren.
Wünschenswert ist es dabei, lediglich digitale Logikschaltungen,
welche aufwandsgünstig implementiert werden können,
einzusetzen.
-
In
der Vergangenheit wurden Zufallszahlengeneratoren z. B. unter Verwendung
analoger Rauschquellen, deren Signale digitalisiert werden, verwendet.
Hybride Analog/Digital-Schaltungen sind jedoch nur aufwändig
zu implementieren.
-
Auch
mit reinen Digitalschaltungen können Zufallszahlen erzeugt
werden, wobei zum Beispiel die statistischen Schwankungen von Periodenlängen von
Ringoszillatoren ausgenutzt werden. Digitale Ringoszillatoren werden üblicherweise
aus einer ungeraden Anzahl von Invertern, die zyklisch angeordnet
bzw. miteinander rückgekoppelt sind, ausgebildet. Die Schwankungen
der Periodenlängen werden insbesondere als Jitter bezeichnet
und sind in der Regel klein gegenüber der Periodenlänge
(etwa 1% der Periode). Dies schränkt meist die Verwendung bei
einer besonders schnellen Zufallszahlen- oder Zufallsbiterzeugung
ein.
-
Jitter-basierende
Zufallszahlenerzeugung ist im Wesentlichen in Form von zwei Verfahren
bekannt. Es besteht einerseits die Möglichkeit, mehrere Perioden
des Jitters abzuwarten, so dass sich die Beiträge durch
die Jitter-Fluktuationen zu einer vollständig zufälligen
Phasenlage des jeweiligen Ringoszillators akkumulieren. Ein großer
Nachteil dieser Vorgehensweise besteht darin, dass nur geringe Datenraten
der Zufallsbits erreicht werden können, da bis zu mehrere
Tausend Periodenlängen berücksichtigt werden müssen,
um eine zufällige Phasenlage des verwendeten Ringoszillators
zu erzielen. Entsprechend lange Wartezeiten ergeben sich aus dem zentralen
Grenzwertsatz der Wahrscheinlichkeitsrechnung gemäß dem
die Standardabweichung der Phasenlage eines Ringoszillators nach
n Perioden nur das √n-fache der Standardabweichung einer
entsprechenden Periode beträgt.
-
Andererseits
wurde zum Beispiel in der
EP
1 562 291 B1 vorgeschlagen, die Phasenlage der eingesetzten
Ringoszillatoren derart einzustellen, dass eine Abtastung möglichst
immer in der Nähe einer Signalflanke erfolgt. Dies hat
allerdings den Nachteil, dass ein erhöhter Regelungs- und
Schaltungsaufwand erforderlich ist und ferner unerwünschte
statistische Abhängigkeiten zwischen den erzeugten Zufallsbit
auftreten können.
-
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 eine Oszillatoreinrichtung,
mehrere Verzögerungseinrichtungen, eine Logikeinrichtung
und eine Abtasteinrichtung auf. Die Oszillatoreinrichtung erzeugt
ein mit einem Jitter beaufschlagtes Oszillatorsignal. Die Verzögerungseinrichtungen
liefern jeweils ein verzögertes Oszillatorsignal. Die Logikeinrichtung
verknüpft die verzögerten Oszillatorsignale und
optional auch das Oszillatorsignal logisch zu einem Zu fallssignal.
Die Abtasteinrichtung tastet das Zufallssignal ab und erzeugt ein
Zufallsbit.
-
Es
ist ebenfalls möglich, die Vorrichtung mit nur einer Verzögerungseinrichtung
auszustatten und das sich ergebende verzögerte Oszillatorsignal
mittels der Logikeinrichtung mit dem Oszillatorsignal zum Erzeugen
des Zufallssignals logisch zu verknüpfen.
-
Ein
entsprechendes Verfahren sieht dabei vor, ein Oszillatorsignal,
welches einen Jitter aufweist, mehrfach zu verzögern und
die verzögerten Oszillatorsignale (und das Oszillatorsignal)
zum Erzeugen eines Zufallssignals logisch miteinander zu verknüpfen.
-
Auch
ein logisches Verknüpfen des Oszillatorsignals mit einem
einzelnen verzögerten Oszillatorsignal verwirklicht die
vorgeschlagene Erfindung und liefert ein verbessertes Zufallssignal.
-
Durch
die Erzeugung und Verwendung mehrerer, jeweils einen Jitter aufweisende,
Oszillatorsignale bzw. verzögerte Oszillatorsignale, wird
durch die logische Verknüpfung die Wahrscheinlichkeit vergrößert,
beispielsweise eine periodische Abtastung des somit erzeugten Zufallssignals
in der Nähe einer Signalflanke vorzunehmen. Das Abtasten
oder das Sampling einer Jitter-behafteten Signalflanke erfolgt bei
einer Anzahl k von Verzögerungselementen oder Verzögerungseinrichtungen
um den Faktor k + 1 wahrscheinlicher gegenüber dem Abtasten
von nur einem Oszillatorsignal. Eine Rate der Zufallsbiterzeugung
kann im Vergleich zu einem einfachen Ringoszillator dessen Oszillatorsignal
abgetastet wird um den Faktor (k + 1)2 gesteigert
werden. Damit ergibt sich eine höhere Zufallsbiterzeugungsrate
um den Faktor 16 bei drei Verzögerungseinrichtungen bzw. verzögerten
Oszillatorsignalen und 25 bei vier Verzögerungseinrichtungen
bzw. verzögerten Oszillatorsignalen.
-
Zur
Erzeugung der Oszillatorsignale eignet sich insbesondere ein digitaler
Ringoszillatorschaltkreis, welcher ein digitales zwischen zwei logischen Pegeln
schwankendes Oszillatorsignal erzeugt.
-
Der
Vorteil eines Einsatzes vollständig digitaler Bauelemente
bei der Vorrichtung zum Erzeugen der Zufallsbits besteht unter Anderem
in der einfachen aufwandsgünstigen Implementierbarkeit
beispielsweise in RFID-Einrichtungen oder auf Smart-Cards.
-
Die
Verzögerungseinrichtungen können seriell verschaltet
werden. Es ist jedoch auch denkbar, mehrere unterschiedliche Verzögerungszeiten
liefernde Verzögerungseinrichtungen parallel vorzusehen.
Eine maximale Verzögerungszeit des jeweiligen verzögerten
Oszillatorsignals ist vorzugsweise geringer als die halbe Oszillationsperiode
des von beispielsweise dem Ringoszillatorschaltkreis gelieferten Oszillations-
oder Oszillatorsignals.
-
Als
Logikeinrichtung zum logischen Verknüpfen der verzögerten
Oszillatorsignale (und dem nicht verzögerten Oszillatorsignal)
eignet sich insbesondere ein XOR-Gatter. Die Abtastvorrichtung,
welche zum Beispiel als D-Flip-Flop ausgeführt sein kann,
ist bei einer Ausführungsform derart eingerichtet, dass eine
Abtastung des Zufallssignals periodisch erfolgt. Um eine digitale
Zufallszahl in binär codierter Form abzuleiten, kann eine
Registereinrichtung zum Speichern mehrerer erfasster Zufallsbits
vorgesehen werden. Beispielsweise kann ein Schieberegister, in das die
nacheinander erfassten Zufallsbits eingeführt werden, verwendet
werden.
-
Beim
Verfahren zum Erzeugen einer Zufallsbitfolge werden zum Beispiel
die folgenden Verfahrensschritte durchgeführt:
Bereitstellen
eines Oszillatorsignals mit einem Jitter, Verzögern des
Oszillatorsignals zum Erzeugen von mehreren verzögerten
Oszillatorsignalen, logisches Verknüpfen der verzögerten
Oszillatorsignale zum Erzeugen eines Zufallssignals, und Abtasten
des Zufallssignals zu vorgegebenen Zeitpunkten zum Erzeugen eines
Zufallsbits.
-
Alternativ
können auch ausschließlich die verzögerten
Oszillatorsignale miteinander logisch verknüpft werden
oder nur ein einzelnes verzögertes Oszillatorsignal mit
dem unverzögerten Oszillatorsignal.
-
Weitere
vorteilhafte Ausgestaltungen der Erfindung sind Gegenstand der Unteransprüche
sowie der im Folgenden beschriebenen Ausführungsbeispiele
der Erfindung. Im Weiteren wird die Erfindung anhand von Ausführungsbeispielen
unter Bezugnahme auf die folgenden Figuren näher erläutert.
Es zeigt dabei:
-
1:
ein Schaltbild einer ersten Ausführungsform einer Vorrichtung
zur Erzeugung von Zufallsbits;
-
2: mögliche Signalformen von
Oszillatorsignalen und Abtastsignalen;
-
3:
ein Ablaufdiagramm für ein Verfahren zum Erzeugen von Zufallsbits;
und
-
4:
ein Schaltbild einer zweiten Ausführungsform einer Vorrichtung
zur Erzeugung von Zufallsbits.
-
In
den Figuren sind gleiche oder funktionsgleiche Elemente mit denselben
Bezugszeichen versehen worden, sofern nichts Anderes angegeben ist.
-
In
der 1 ist eine Vorrichtung 1 dargestellt,
welche ein Zufallsbit ZB an einem Ausgang 9 liefert. Die
Vorrichtung zur Zufallszahlenerzeugung 1 hat eine Oszillatoreinrichtung 2,
welche als Ringoszillator ausgeführt ist. Dabei ist der
Ringoszillator 2 aus einer ungeraden Anzahl von seriell
verschalteten Invertern 10–14 ausgebildet,
wobei das Ausgangssignal dieser Inverterkette OS dem Eingang des
ersten Inverters 10 zurückgekoppelt ist. Dieser
digitale Schwingkreis bzw. Ringoszillator 2 liefert somit
am Ausgang 29 ein Oszillationssignal OS. Aufgrund von Störungen
und nichtidealen elektronischen Bauelementen oder auch Temperatureinflüssen
ergibt sich kein ideales oszillierendes Signal, sondern ein Jitter beaufschlagtes
Oszillationssignal OS. D. h., es treten grundsätzlich Schwankungen
in den Periodenlängen aufeinander folgender Schwingungszyklen
auf. Wie bereits eingangs erwähnt, bewegt sich dieser typische
Jitter um etwa 1% der nominalen Oszillationsperiode.
-
Es
sind mehrere Verzögerungseinrichtungen 3, 4, 5 vorgesehen,
die Eingänge 15, 16, 17 und
Ausgänge 18, 19, 20 haben. Ein
an einem jeweiligen Eingang 15, 16, 17 vorliegendes
Signal wird am Ausgang 18, 19, 20 um
eine jeweilige Verzögerungszeit später ausgegeben.
Die in der 1 dargestellten drei Verzögerungsglieder 3, 4, 5 sind
seriell miteinander verschaltet und dem Eingang 15 des
ersten Verzögerungsgliedes des Oszillatorsignals OS zugeführt.
Ein erstes verzögertes Oszillatorsignal D1 liegt somit
am Ausgang 18 des ersten Verzögerungsgliedes 3 vor.
Das erste verzögerte Oszillatorsignal D1 ist dem Eingang 16 des
zweiten Verzögerungsgliedes 4 zugeführt,
welches an seinem Ausgang 19 ein zweites verzögertes
Oszillatorsignal D2 bereitstellt. Dieses zweite verzögerte
Oszillatorsignal D2 ist dem Eingang 17 des dritten Verzögerungsgliedes 5 zugeführt,
das an seinem Ausgang 20 ein drittes verzögertes
Oszillatorsignal D3 liefert. Es liegen somit vier verschiedene zeitlich
verschobene Oszillatorsignale OS, D1, D2, D3 vor, die jeweils mit
einem Jitter behaftet sind.
-
Eine
als XOR-Gatter ausgeführte Logikeinrichtung 6 nimmt
diese Jitter-beaufschlagten Oszillatorsignale OS, D1, D2, D3 an
Eingängen 21–24 entgegen und
liefert unter Anwendung einer logischen XOR-Funktion an einem Ausgang 25 ein
Zufallssignal ZS. Durch die logische Verknüpfung hat das
Zufallssignal ZS je nach Einstellung der Verzögerungszeiten
der Verzögerungsglieder 3, 4, 5 – zum
Beispiel, wenn die zeitliche Verzögerung des dritten verzögerten
Oszillatorsignals D3 gegenüber dem ursprünglichen
Oszillatorsignal OS geringer ist als die halbe Periode der nominellen
Ringoszillatorperiode – innerhalb einer nominalen Ringoszillatorperiode
T, drei zusätzliche fluktuierende, nämlich gemäß dem Jitter
schwankende, Signalflanken.
-
Dieses
Zufallssignal ZS wird nun einer als D-Flip-Flop 7 ausgeführten
Abtasteinrichtung zugeführt. Das D-Flip-Flop 7 hat
einen Dateneingang 26, einen Takteingang 27 und
einen Datenausgang 28. Das taktflankengesteuerte D-Flip-Flop 7 erfasst
das an seinem Dateneingang 26 vorliegende Signal bei einer
steigenden Signalflanke an seinem Takteingang 27. Dazu
ist ein Abtastsignal SM, das beispielsweise ein periodisches Taktsignal
sein kann, dem Takteingang 27 zugeführt. Die Zufallszahlerzeugungsvorrichtung 1 hat
dazu einen Eingang 8, dem ein entsprechendes Abtast- oder
Taktsignal zugeführt werden kann.
-
In
der 2 sind zur näheren Erläuterung mögliche
Signalformen für Oszillatorsignale und ein Taktsignal dargestellt.
In der 2A ist beispielhaft ein Oszillatorsignal
OS, welches zwischen zwei logischen Pegeln L und H schwankt, im
zeitlichen Verlauf dargestellt. Die zusätzlichen vertikalen
Linien an den Signalflanken sollen den Jitter symbolisieren. Grundsätzlich
ergibt sich eine durchschnittliche (nominale) Periodendauer T, welche
jedoch lediglich dem zeitlichen Mittel über viele Schwingungen
bzw. Oszillationen entspricht. Grundsätzlich ergibt sich
durch den Jitter eine Verteilung um die nominale Ringoszillatorperiode
T herum.
-
Durch
die Verzögerungsglieder 3, 4, 5 in
der Zufallszahlerzeugungsvorrichtung 1 werden weitere ähnliche
Signalverläufe zeitlich verschoben erzeugt. Insbesondere
durch den Einsatz der Logikeinrichtung bzw. des XOR-Gatters 6 ist
bei einer periodischen Abtastung des sich ergebenden Zufallsignals ZS
die Wahrscheinlichkeit deutlich gegenüber dem Einzelsignal,
wie es in der 2A dargestellt ist, bei einer
Signalflanke abzutasten, erhöht.
-
2B zeigt
beispielhaft ein als Taktsignal ausgeführtes Abtastsignal
SM. In dem Ausführungsbeispiel der 1 erfolgt
eine Abtastung und Erfassung des Zufallssignals jeweils zu den steigenden
Signalflanken des Abtastsignals SM. Das somit abgetastete oder gesampelte
Zufallssignal ZS ist als logisches Zufallsbit ZB am Ausgang 28 des
Flip-Flops 7 abgreifbar und ist, wie in der 1 dargestellt
ist, als Zufallsbit ZB dem Ausgang 9 zugeführt.
-
In
der 3 ist schematisch ein beispielhaftes Ablaufdiagramm
des Verfahrens zum Erzeugen von Zufallsbits, welches insbesondere
durch die Vorrichtung, wie sie in der 1 dargestellt
ist, implementiert werden kann, dargestellt. Es wird zunächst im
Schritt S1 ein Oszillatorsignal beispielsweise mittels eines digitalen
Ringoszillatorschaltkreises erzeugt. Das entsprechende Oszillatorsignal
hat dabei einen Jitter.
-
Im
folgenden Schritt S2 werden verzögerte Oszillatorsignale
erzeugt, indem das Oszillatorsignal zeitlich unterschiedlich verzögert
wird.
-
Im
Schritt S3 erfolgt eine logische Verknüpfung der verzögerten
Oszillatorsignale und des Oszillatorsignals.
-
Anschließend
wird das durch die logische Verknüpfung erzeugte Zufallssignal
beispielsweise periodisch abgetastet bzw. gesampelt. Dies geschieht
im Schritt S4. Ergebnis dieser Abtastung ist ein Zufallsbit ZB,
welches beispielsweise als eine binäre Stelle in einer
Zufallszahl verwendet werden kann.
-
Durch
wiederholtes Durchlaufen der Schritte S1–S4 wird somit
eine Zufallsbitfolge erzeugt, welche als binäre Stellen
einer Zufallszahl, wie im Schritt S5 angedeutet ist, verwendet werden
können.
-
Insofern
wird der Verfahrensschritt S1 durch den Ringoszillator 2,
wie in der 1 dargestellt ist, realisiert.
Die Verzögerung im Schritt S2 erfolgt durch die Verzögerungsglieder 3, 4, 5.
Die logische Verknüpfung im Schritt S3 wird durch das XOR-Gatter 6 vorgenommen.
Das Samplen erfolgt durch das D-Flip-Flop 7.
-
Die 4 zeigt
eine zweite Ausführungsform einer Vorrichtung 100 zur
Erzeugung von Zufallsbits bzw. einer Zufallszahl. Die Vorrichtung 100 weist
im Wesentlichen dieselben Elemente auf, wie sie in der 1 dargestellt
sind. Auf gleiche oder funktionsgleiche Elemente wird daher nicht
weiter eingegangen.
-
Ein
digitaler Ringoszillator 2 liefert ein Oszillatorsignal
OS, welches an Eingänge 15, 16 von zwei verschiedenen
Verzögerungsgliedern 3, 4, zuführt ist.
Die Verzögerungsglieder 3, 4 haben dabei
unterschiedliche Verzögerungszeiten, wobei die maximale Verzögerungszeit
vorzugsweise geringer ist als die Hälfte der nominalen
Periode des Ringoszillators 2. An Ausgängen 18, 19 der
Verzögerungsglieder 3, 4 sind somit verzögerte
Oszillatorsignale D1, D2 abgreifbar. Mittels eines XOR-Gatters 6 wird
aus den an Eingängen 21, 22, 23 anliegenden
Oszillatorsignalen bzw. verzögerten Oszillatorsignalen
OS, D1, D2 ein Zufallssignal ZS erzeugt, welches am Ausgang 25, des
XOR-Gatters 6 abgreifbar ist.
-
Der
Ringoszillator 2 kann durch ein Aktivierungssignal AKT
gestartet und gestoppt werden. Dazu ist eines der Verzögerungselemente
nicht als Inverter, sonder NAND-Gatter 110 ausgeführt.
Der Ringoszillator 2 weist somit drei Logikelemente 110, 11, 12 auf,
die seriell miteinander verschaltet sind. Davon ist das erste Logikelement 110 ein
NAND-Gatter, dem das Aktivierungssignal AKT zugeführt ist
sowie das am Ausgang des letzten in der Kette von Invertern 11, 12 vorliegende
Ausgangssignal, welches dem Oszillatorsignal OS entspricht.
-
Die
Vorrichtung 100 weist zudem eine Steuereinrichtung 31 auf,
die einerseits ein Aktivierungssignal AKT zum Starten des Ringoszillators 2 erzeugt,
ein Abtastsignal SM, welches dem Takteingang 27 eines D-Flip-Flops 7 zugeführt
ist, und ein Steuersignal CT liefert, welches ein an den Datenausgang 28 des
D-Flip-Flops nachgeschaltetes Schieberegisters 32 steuert.
-
Das
Zufallssignal ZS ist dem Dateneingang 26 des D-Flip-Flops 7 zugeführt
und das durch das D-Flip-Flop 7 erfasste bzw. abgetastete
Zufallsbit ZB dem Schieberegister 32. Bei jeder Abtastung,
beispielsweise durch eine steigende Signalflanke des Takt- bzw.
Abtastsignals SM, gibt das Flip-Flop 7 ein Zufallsbit ZB
an das Schieberegister 32 aus, so dass dieses nach und
nach gefüllt wird. Sind ausreichend viele Zufallsbits für
eine Zufallszahl vorgegebener Bitbreite vorhanden, veranlasst die
Steuereinrichtung 31 eine Ausgabe der Zufallsbitfolge als
binär codierte Zufallszahl ZZ am Ausgang 9 der
Vorrichtung 100.
-
Obwohl
die vorliegende Erfindung anhand ausgewählter Ausführungsbeispiele
näher erläutert wurde, ist sie nicht darauf beschränkt,
sondern vielfältig modifizierbar. Die vorgeschlagene Anzahl
von Verzögerungselementen bzw. Logikelementen in den Ringoszillatorschaltkreisen
kann selbstverständlich verändert werden. Ferner
sind neben den beispielhaft genannten logischen Verknüpfungen
oder Abtasteinrichtungen weitere Implementierungen möglich,
die beispielsweise die in der 3 dargestellten Verfahrensschritte
umsetzen.
-
ZITATE ENTHALTEN IN DER BESCHREIBUNG
-
Diese Liste
der vom Anmelder aufgeführten Dokumente wurde automatisiert
erzeugt und ist ausschließlich zur besseren Information
des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen
Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt
keinerlei Haftung für etwaige Fehler oder Auslassungen.
-
Zitierte Patentliteratur
-