DE102016201176A1

DE102016201176A1 - Verfahren und Vorrichtung zum Erzeugen von Zufallsbits

Info

Publication number: DE102016201176A1
Application number: DE102016201176.6A
Authority: DE
Inventors: Markus Dichtl
Original assignee: Siemens AG; Siemens Corp
Current assignee: Siemens AG; Siemens Corp
Priority date: 2016-01-27
Filing date: 2016-01-27
Publication date: 2017-07-27

Abstract

Ein Verfahren zum Erzeugen von Zufallsbits (ZB) hat die Schritte: Bereitstellen (S0) einer Mehrzahl von seriell miteinander verketteten Abbildungseinrichtungen (21–2m), wobei jede der Mehrzahl von Abbildungseinrichtungen (21–2m) eingerichtet ist, eine vorgegebene Anzahl n Eingangssignale (E11–Emn) mit Hilfe einer kombinatorischen Abbildung (K1–Km) in eine vorgegebene Anzahl p Ausgangssignale (A11–Amp) abzubilden; Einkoppeln (S1) von logischen Pegelwechseln (PW) an eine erste Abbildungseinrichtung (21) der Mehrzahl der miteinander verketteten Abbildungseinrichtungen (21–2m) als Eingangsstartsignale (ES11–ES1n), wobei die jeweiligen logischen Pegelwechsel (PW) durch ein Umschalten (US1–USQ) von einem aktuellen Eingangsbitmuster (BMJ) zu einem nächsten Eingangsbitmuster (BMj + 1) erzeugt werden; Erfassen (S2) eines oder mehrerer Ausgangssignale (A11–Amp) an Ausgängen einer oder mehrerer Abbildungseinrichtungen (21–2m), welche von der ersten Abbildungseinrichtung (21) unterschiedlich sind; und Ermitteln (S3) eines oder mehrerer Bitwerte in Abhängigkeit von dem oder den erfassten Ausgangssignalen (A11–Amp) als Zufallsbit (ZB) oder Zufallsbitmuster (ZBM); wobei eine zyklischen Abfolge (ZK) von Eingangsbitmustern (BM1–BMQ) zum Erzeugen der logischen Pegelwechsel (PW) derart eingekoppelt wird, dass eine mittlere Entropie der ermittelten Zufallsbits (ZB) von einem Eingangsbitmuster (BMJ) zum nächsten (BMJ + 1) größer oder gleich einem vorgegebenen Schwellwert ist.

Description

Die vorliegende Erfindung betrifft ein Verfahren und 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 Erzeugen von Zufallsbits dienen beispielsweise der Implementierung von Zufallszahlengeneratoren. Die Erfindung ermöglicht beispielsweise die Erzeugung echter Zufallsbits.
In sicherheitsrelevanten Anwendungen, beispielsweise bei asymmetrischen Authentifikationsverfahren, sind Zufallsbitfolgen als binäre Zufallszahlen notwendig. Dabei ist es gewünscht, insbesondere bei mobilen Anwendungen einen möglichst geringen Hardwareaufwand zu betreiben. Bekannte Maßnahmen, um Zufallszahlen zu erzeugen, sind beispielsweise Pseudozufallszahlengeneratoren, analoge Zufallsquellen, Ringoszillatoren und deren Abwandlungen.
Bei Ringoszillatoren, die aus einer ungeraden Anzahl von hintereinander geschalteten Invertern 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 Signale, können bei mehrfachen Durchläufen durch die Ringoszillatorschaltung akkumuliert werden, so dass letztlich ein zufälliges analoges Signal entsteht. Nachteilig bei Ringoszillatoren 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 niedrige nicht akzeptable Datenerzeugungsraten bei Ringoszillatoren. 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 Gatterlaufzeiten kompensiert werden.
Auch der Energieverbrauch bei Oszillatorschaltungen in Zufallszahlengeneratoren wurde in der Vergangenheit als nachteilig empfunden, da im Betrieb ständig ein elektrischer Strom fließt.
Bei in der dominierenden CMOS-Technologie implementierten digitalen Schaltungen hängt der Stromverbrauch im Wesentlichen von der Anzahl der Umschaltvorgänge pro Zeit ab. Bei entsprechenden digitalen Schwingschaltungen muss dies ständig stattfinden, so dass ein eher ungünstiger Energieverbrauch bei auf Ringoszillatoren basierenden Zufallszahlengeneratoren entsteht. Insbesondere bei mobilen Anwendungen ist es wünschenswert, den Energieverbrauch bzw. die Stromaufnahme der hardwaremäßig implementierten Schaltungen gering zu halten.
In der DE 10 2014 203 648 A1 wurde daher vorgeschlagen, mehrspurige kombinatorische Abbildungen ohne Rückkopplungen zu verketten und die beim Durchlauf entstehenden Signalformen als Zufallsquelle zu nutzen. Die DE 10 2014 203 648 A1 schlägt dabei vor, Pegelwechsel in die Abbildungskette einzukoppeln, indem ein Hin- und Herschalten zwischen zwei beliebigen statischen Eingangsbitmustern erfolgt.
Aus dem Stand der Technik sind zudem das Dokument US 8531247 B2 , das Dokument US 8892616 B2 , das Dokument US 8300811 B2 , das Dokument US 9147088 B2 , das Dokument EP 2605445 B1 , das Dokument EP 2870565 A1 , das Dokument EP 2891102 A1 und das Dokument US 8843761 B2 bekannt.
Es ist insbesondere gewünscht, statistisch guten physikalischen Zufall zu generieren. Wünschenswert ist es auch, über den Betrieb eines Zufallsbitgenerators Zufallsbits, mit möglichst gleich hoher Entropie bei hoher Erzeugungsrate zu erzeugen.
Daher besteht eine Aufgabe der vorliegenden Erfindung darin, eine verbessertes Verfahren und/oder eine Vorrichtung zum Erzeugen von Zufallsbits bereitzustellen.
Demgemäß wird ein Verfahren zum Erzeugen von Zufallsbits vorgeschlagen, das die folgenden Schritte umfasst:
Bereitstellen einer Mehrzahl von seriell miteinander verketteten Abbildungseinrichtungen, wobei jede der Mehrzahl von Abbildungseinrichtungen eingerichtet ist, eine vorgegebene Anzahl n Eingangssignale mit Hilfe einer kombinatorischen Abbildung in eine vorgegebene Anzahl p Ausgangssignale abzubilden;
Einkoppeln von logischen Pegelwechseln an eine erste Abbildungseinrichtung der Mehrzahl der miteinander verketteten Abbildungseinrichtungen als Eingangsstartsignale, wobei die jeweiligen logischen Pegelwechsel durch ein Umschalten von einem aktuellen Eingangsbitmuster zu einem nächsten Eingangsbitmuster erzeugt werden;
nach dem Einkoppeln, Erfassen eines oder mehrerer Ausgangssignale an Ausgängen einer oder mehrerer Abbildungseinrichtungen, welche von der ersten Abbildungseinrichtung unterschiedlich sind;
Ermitteln eines oder mehrerer Bitwerte in Abhängigkeit von dem oder den erfassten Ausgangssignalen als Zufallsbit oder Zufallsbitmuster.
Dabei wird eine zyklischen Abfolge von Eingangsbitmustern zum Erzeugen der logischen Pegelwechsel derart eingekoppelt wird, dass eine mittlere Entropie der ermittelten Zufallsbits von einem Eingangsbitmuster zum nächsten größer oder gleich einem vorgegebenen Schwellwert ist.
Das Einkoppeln von logischen Pegelwechseln, das Erfassen des oder der Ausgangssignale und das Ermitteln des oder der Bitwerte wird vorzugsweise mindestens dreimal nacheinander, also als Abfolge oder Zyklus der Länge drei durchgeführt, und die jeweiligen logischen Pegelwechsel werden durch ein Umschalten von einem aktuellen Eingangsbitmuster zu einem nächsten Eingangsbitmuster in der Abfolge erzeugt.
Optional erfolgt der Schritt: Vergleichen einer Entropie für eine Vielzahl von ermittelte Zufallsbits von einem Eingangsbitmuster zum nächsten, und Ändern der Abfolge bis der vorgegebene Schwellwert erreicht ist.
Es wird ferner eine Vorrichtung vorgeschlagen, die sich zur Durchführung des Verfahrens eignet und umfasst:
eine Mehrzahl von Abbildungseinrichtungen, wobei jede der Mehrzahl von Abbildungseinrichtungen eingerichtet ist, eine vorgegebene Anzahl n Eingangssignale mit Hilfe einer kombinatorischer Abbildung in eine vorgegebene Anzahl p Ausgangssignale abzubilden, wobei die Abbildungseinrichtungen der Mehrzahl von Abbildungseinrichtungen miteinander verkettet sind;
eine Starteinrichtung, welche eingerichtet ist, einer ersten Abbildungseinrichtung der Mehrzahl der miteinander verketteten Abbildungseinrichtungen logische Pegelwechsel als Eingangsstartsignale einzukoppeln;
eine Erfassungsvorrichtung, welche eingerichtet ist, eines oder mehrere Ausgangssignale an Ausgängen einer oder mehrerer Abbildungseinrichtungen, welche von der ersten Abbildungseinrichtung unterschiedlich sind, zu erfassen und als ein jeweiliges Zufallsbit oder Zufallsbitmuster auszugeben; und
eine Steuereinrichtung, welche die Starteinrichtung und die Erfassungsvorrichtung derart steuert, dass ein Verfahren wie es zuvor oder im Folgenden beschrieben ist, durchgeführt wird.
Die Vorrichtung kann dabei ferner eine Speichereinrichtung aufweisen, welche eine zyklische Abfolge von Eingangsbitmustern zum Erzeugen der zyklischen logischen Pegelwechsel abgespeichert bereitstellt. Auch ein Hin- und Herschalten zwischen zwei Zuständen kann als zyklische Abfolge aufgefasst werden. Bevorzugt wird die Abfolge hinsichtlich der Länge unter dem zugehörigen Eingangsbitmuster so gewählt, dass eine möglichst hohe mittlere Entropie für die pro Eingangsbitmusterwechsel erzeugten Zufallsbits entsteht.
In Ausführungsformen werden die logischen Pegelwechsel also jeweils durch ein Umschalten von einem Eingangsbitmuster zu einem anderen darauffolgenden Eingangsbitmuster erzeugt.
Durch die aufeinander folgenden Pegelwechsel, die durch das Durchlaufen einer Abfolge oder eines Zyklusses von Eingangsbitmustern erzeugt werden, kann eine günstige Entropieausbeute für die erzeugten Zufallbits pro Zufallslauf aus dem Einkoppeln, Erfassen und Ermitteln erzielt werden.
In Ausführungsformen des Verfahrens bzw. einer entsprechend eingerichteten Steuervorrichtung wird eine zyklischen Abfolge von Eingangsbitmustern zum Erzeugen der zyklischen logischen Pegelwechsel derart eingekoppelt, dass eine mittlere Entropie der ermittelten Zufallsbits von einem Eingangsbitmuster zum nächsten über die Abfolge größer oder gleich einem vorgegebener Schwellwert ist. Zum Beispiel kann der Schwellwert dem Mittelwert aller Entropien aller möglichen Eingangsbitmusterwechsel entsprechen. Vorzugsweise ist der Schwellwert so gewählt, dass die mittlere Entropie der ermittelten Zufallsbits von einem Eingangsbitmuster zum nächsten für die jeweilige Abfolge und die jeweilige Vorrichtung mit der verketteten Abbildungseinrichtung maximal ist.
Man kann also zunächst mehrere mögliche Abfolgen betrachten und die Entropie für jeden der darin vorkommenden Übergänge von einem zum nächsten Eingangsbitmuster ermitteln. Daraus ergibt sich die jeweilige mittlere Entropie für eine Abfolge bzw. einen Zyklus. Die Abfolge mit der maximalen mittleren Entropie aus den betrachteten Abfolgen wird dann in dem Verfahren zum Erzeugen von Zufallsbits verwendet.
Durch die günstige Wahl der Abfolge von Eingangsbitmusterwechseln, nacheinander vorgenommenen Umschaltvorgängen zwischen möglichen Eingangsbitmustern bzw. der nacheinander eingekoppelten Pegelwechsel kann demnach eine optimierte Entropieausbeute erreicht werden.
Insofern wird der Energieaufwand pro erzeugtem Bit Entropie gegenüber bekannten Vorgehensweisen potenziell ebenfalls reduziert.
Die Entropie kann insbesondere durch vielfache Bestimmung eines Zufallsbits mit Hilfe der verketteten Abbildungseinrichtung empirisch ermittelt werden. Beispielsweise wird die Verteilung von Null- und Eins-Bitwerten für nacheinander bei denselben eingekoppelten Pegelwechseln ermittelt und daraus die informationstheoretische Entropie berechnet.
In Ausführungsformen werden zum Bestimmen der Abfolge die Schritte durchgeführt:
Bestimmen einer Auswahl von allen möglichen Eingangsbitmustern für die ersten Abbildungseinrichtung; und
Ermitteln der Entropie der ermittelten Zufallsbits für mögliche Bitmusterumschaltungen von einem der möglichen Eingangsbitmustern der Auswahl zu einen anderen möglichen Eingangsbitmuster der Auswahl.
Es können auch alle möglichen Eingangsbitmuster, beispielsweise acht, bei drei Eingangssignalen, bestimmt werden und anschließend alle daraus möglichen Bitmusterumschaltungen hinsichtlich ihrer Entropie untersucht werden. Bei acht möglichen Bitmustern wären dies 56 Umschaltmöglichkeiten mit mindestens einem Pegelwechsel.
Außerdem kann der Schritt erfolgen: Auswählen der zyklischen Abfolge von Bitmusterumschaltungen aus den möglichen Bitmusterumschaltungen derart, dass ein Mittelwert der Entropien der ermittelten Zufallsbits für die zyklischen Abfolge größer oder gleich einem vorgegebener Schwellwert ist. Vorzugsweise wird der Schwellwert so gelegt, dass das mögliche Maximum der mittleren Entropie der Zufallsbits für alle oder für die gemäß der Auswahl von Eingangsbitmustern ermittelten Bitmusterumschaltungen vorliegt.
Ein Erfassen erfolgt beispielsweise durch Abtasten, beispielsweise getaktet oder zu vorgegebenen anderen Zeitpunkten nach dem Einkoppeln des oder der Pegelwechsel und dient der Ableitung eines Bitwertes H oder L, der aufgrund des jeweiligen eingekoppelten Pegelwechsels und des stark schwankenden zufälligen Signals eine günstige Entropie bzw. Zufälligkeit pro Zufallslauf aufweist.
Es ist somit möglich, wiederholt Zufallsläufe als Zyklus zu vollziehen, indem an eine erste Eingangsabbildungseinrichtung festgelegte Eingangssignalpegel gelegt werden, diese einen gesteuerten Zustandswechsel vollziehen und nach Durchlauf dieses Signals bzw. der sich ergebenden Signalflanke/n durch alle Abbildungseinrichtungen an einer End- oder Ausgangsabbildungseinrichtung die anliegenden Ausgangssignale oder eines der Ausgangssignale erfasst wird. Innerhalb des jitter- und zufallsbehafteten Signalverlaufs kann gesampelt werden oder ein Zwischenspeicherelement erfasst die zeitlich nicht vorhersagbaren Zustandswechsel. Möglich ist auch, eine Zählereinrichtung an die Ausgänge, beispielsweise der letzten Ausgangsabbildungseinrichtung, anzulegen, welche Signalflanken zählt. Der oder die sich ergebenden Bitwerte können als Zufallsbit verstanden werden. Die Zufallsläufe folgen dabei einem Zyklus, der durch die Abfolge von Eingangsbitmustern bzw. Umschaltvorgängen festgelegt ist. Ein jeweiliger Zyklus wird immer wiederholt, sodass eine Zufallsbiterzeugung mit hoher Datenrate und guter Entropie pro Bit möglich ist.
Durch die vorgegebenen Pegelwechsel, beispielsweise von einem logischen Low-Pegel (0) auf einen logischen High-Pegel (1) oder umgekehrt, wird aufgrund der logischen Abbildungseinrichtungen ein Durchlaufen des oder der Signalwechsel durch die Kette von Abbildungseinrichtungen in Gang gesetzt. Durch die statistischen Schwankungen der Gatterdurchlaufzeiten entsteht dabei Jitter. Durch ein Abtasten wird jeweils ein zufälliger Pegel abgegriffen, der von der Erfassungsvorrichtung einem jeweiligen Zufallsbitwert zugeordnet ist.
In Ausführungsformen ist die Erfassungseinrichtung eingerichtet, die Ausgangssignale einer letzten Abbildungseinrichtung der Mehrzahl der miteinander verketteten Abbildungseinrichtungen als Zufallsbits zu erfassen. Beispielsweise, ist eine lineare Kette von kombinatorischen Abbildungseinrichten vorgesehen, wobei der Kette eingangsseitig Pegelwechsel zum Erzeugen von Signalflanken eingekoppelt werden, und ausgangsseitig echte Zufallssignale abgetastet werden.
Die Erfassungseinrichtung kann eingerichtet sein, ein Ausgangssignal in Abhängigkeit von einem anderen Ausgangssignal abzutasten.
Die Erfassungsvorrichtung weist beispielsweise ein Zwischenspeicherelement, insbesondere ein T-Flip-Flop, auf. Mithilfe von Flip-Flops, insbesondere T-Flip-Flops können aufwandsgünstig eine Erfassung der Ausgangssignale und eine Abbildung auf logische Zufallspegel erfolgen. Denkbar sind auch einer oder mehrere Zähler zum Erfassen von Signalflanken oder Zustandswechseln einzelner Signale. Ein T-Flip-Flop ist insbesondere geeignet, steigende oder fallende Signalflanken modulo 2 zu zählen.
In Ausführungsformen ist die Erfassungsvorrichtung ferner eingerichtet, eine zeitliche Reihenfolge von Zustandswechseln von Ausgangssignalen bei jedem wohldefinierten logischen Pegelwechsel der Eingangsstartsignale zu erfassen.
Vorzugsweise sind die Abbildungseinrichtungen derart miteinander verkettet, dass keine Rückkopplung entsteht. Dadurch ergibt sich, dass die Vorrichtung nicht kontinuierlich Umschaltvorgänge in einer Implementierung als Digitalschaltung vollziehen muss, was den Stromverbrauch begrenzt.
Man kann sagen, die Vorrichtung entwickelt keine „Schwingungen“ oder Signalwechsel propagieren nicht im Kreis. Beispielsweise sind die Ausgangssignale alle vorwärtsgekoppelt. Vorzugsweise hängt keines der Ausgangssignale kausal von sich selbst ab, indem es rückgekoppelt wird.
In Ausführungsformen sind die Abbildungseinrichtungen derart miteinander verkettet, dass keine Rückkopplungsschleife derart ausgebildet ist, dass eine Zustandsänderung mindestens eines Ausgangssignals einer Abbildungseinrichtung als eine Zustandsänderung mindestens eines Eingangssignals einer anderen Abbildungseinrichtung zugeführt ist. Prinzipiell können Rückkopplungspfade vorgesehen sein, die jedoch vorzugsweise nicht zu Schwingungen führen. Grundsätzlich ist es möglich, dass der Ausgang einer Abbildungseinrichtung bzw. ein Ausgangssignal als Eingangssignal für eine im Signalpfad stromaufwärts vorliegende Abbildungseinrichtung genutzt wird.
Die Anzahl der n Eingangssignale einer jeweiligen Abbildungseinrichtung kann der Anzahl p der Ausgangssignale entsprechen. Es ist aber auch denkbar, dass n ungleich p ist, also dass mit Hilfe einer jeweiligen Abbildungseinrichtung die Zustände der Eingangssignale auf Zustände von Ausgangssignalen abgebildet werden, wobei die Anzahl der Ausgangssignale kleiner oder größer als die Anzahl der Eingangssignale für eine jeweilige Abbildungseinrichtung ist.
Die Abbildungseinrichtungen können logische oder kombinatorische Gatter sein, die insbesondere eine bijektive Abbildung von n Eingangssignalen auf n Ausgangssignale realisieren. Die Eingangssignale schwanken zwischen Pegeln, die logischen Zuständen, wie Bits 1 bzw. High oder 0 bzw. Low zugeordnet werden können. Unter einer bijektiven Abbildung versteht man eine eineindeutige Abbildung zwischen den 2ⁿ möglichen logischen Werten der Eingangssignale und den 2ⁿ logischen Werten der Ausgangssignale.
In Ausführungsformen der Vorrichtung ist mindestens eine kombinatorische Abbildung derart eingerichtet, dass die Eingangssignale unter Beaufschlagung eines Jitters und einer logischen Funktion auf die Ausgangssignale abgebildet werden. Durch die hardwaremäßige Implementierung der kombinatorischen Abbildung durch die Abbildungseinrichtungen können sich Jitter, also Schwankungen, in dem zeitlichen Verlauf von Signalflanken ergeben. Dieser Jitter wird dann durch Vollziehen der logischen Funktion, also der Abbildung der Kombination von n Eingangssignalen oder Bitwerten auf p Ausgangssignale oder Bitwerte, jeweils weitergeführt und akkumuliert sich über die Durchläufe durch die Abbildungseinrichtungen.
Insofern ergibt sich in Ausführungsformen der Vorrichtung eine begrenzte Kette von Abbildungseinrichtungen. Die Abbildungseinrichtungen können auch als Knoten oder Gatter bezeichnet sein. Wenigstens eine der kombinatorischen Abbildungen ist insbesondere derart eingerichtet, dass im Mittel bei einer Zustandsänderung eines Eingangssignals an mehr als einem Ausgangssignal ein Zustandswechsel erfolgt. Das führt dazu, dass ein jeweiliger Jitter des Eingangssignals auf mehrere Ausgangssignale abgebildet wird und daher verstärkt wird. Ein einmal aufgetretener Jitter in einem Signal wird mit Hilfe der Abbildungseinrichtungen bzw. der darin implementierten kombinatorischen Abbildungen auf mehrere Ausgangsspuren kopiert, so dass sich Jitter-Komponenten kaum kompensieren können.
In Ausführungsformen ist mindestens eine ausgewählte Abbildungseinrichtung vorgesehen, deren Ausgangssignale von allen Eingangssignalen der übrigen Abbildungseinrichtungen entkoppelt sind. Beispielsweise kann dies die letzte Abbildungseinrichtung einer Kette von m Abbildungseinrichtungen sein, die linear miteinander verkoppelt sind. Es ergibt sich insbesondere ein endlicher Signalverlauf. Das kann bedeuten, dass ausschließlich in einem vorgegebenen Zeitintervall ein Signal- oder ein Zustandswechsel eines Signals sich durch die verketteten Abbildungseinrichtungen fortsetzt. Denn von einer ersten Eingangsabbildungsvorrichtung aus propagiert entlang der verketteten Abbildungseinrichtungen ein sich sukzessive mit Jittern und Zufallsbeiträgen ausbreitendes Zufallssignal bzw. mehrere gemäß der jeweiligen Bitbreite der Abbildungseinrichtungen. Unter einer Entkopplung kann man verstehen, dass die Ausgangssignale nicht an Eingänge anderer Abbildungseinrichtungen geführt sind.
Es können in einem derartigen Signalpfad von einer ersten bis zu einer letzten Abbildungseinrichtung, die als Ausgangsabbildung bezeichnet werden kann, weitere Schaltungen, wie Logikgatter oder Verzögerungselemente, vorgesehen sein.
Vorzugsweise sind zumindest einige der Abbildungen keine kombinatorischen Abbildungen, welche ausschließlich eine Permutation der Eingangssignale auf die Ausgangssignale liefern. Eine Permutation der Eingangssignale liegt insbesondere dann vor, wenn die Ausgangssignale den Eingangssignalen entsprechen oder lediglich durch eine Änderung der Reihenfolge aus den Eingangssignalen entstehen. Bei einer Permutation ergibt sich keine "Vervielfältigung" des Jitters.
In Ausführungsformen der Vorrichtung zum Erzeugen von Zufallsbits sind die Abbildungseinrichtungen derart eingerichtet, dass deren Signaldurchlaufzeiten gleich sind. Durch möglichst gleiche Signallaufzeiten wird das Risiko vermindert, dass sich Jitter-Beiträge gegenseitig kompensieren können. Außerdem wird eine Implementierung in der Art von ASICs oder FPGAs erleichtert. Beispielsweise sind die Abbildungseinrichtungen so eingerichtet, dass alle möglichen Zustandswechsel an den jeweiligen Ausgängen alle innerhalb eines Toleranzintervalls von 100 ps und bevorzugt innerhalb von 50 ps erfolgen.
In Ausführungsformen der Vorrichtung umfasst mindestens eine Abbildungseinrichtung eine Lookup-Table bzw. eine Nachschlagetabelle zur Implementierung der kombinatorischen Abbildung. Es ist auch möglich, dass alle Abbildungseinrichtungen mit einer oder mehreren jeweiligen Lookup-Tables versehen sind. Lookup-Tables können einfach ausgelesen werden und erfordern nur einen geringen Hardwareaufwand. Häufig sind in programmierbaren Logikchips, wie FPGAs, entsprechende Felder oder bereits Tabellen vorgesehen.
In Ausführungsformen der Vorrichtung können die Lookup-Tables mit zufälligen Bitwerten unter Verwendung von Zufallselementen gefüllt werden. Es ist beispielsweise möglich, die Lookup-Tables, die in Abhängigkeit von einem Eingangsbitmuster an Eingängen der Abbildungseinrichtungen ein entsprechendes Ausgangsbitmuster an Ausgängen liefern, so zu erzeugen, dass die durch die Lookup-Table repräsentierte Abbildung zufällig aus allen (2ⁿ)! Bijektionen von n logischen Signalen auf n logische Signale ausgewählt wird. Vorzugsweise sind in den Abbildungseinrichtungen jeweils unterschiedliche kombinatorische Abbildungen implementiert.
Vorzugsweise ist die vorgegebene Anzahl n beziehungsweise p von Eingangs- beziehungsweise Ausgangssignalen mindestens drei. In Ausführungsformen ist die Bitbreite oder die Anzahl n beziehungsweise p von vorgegebenen Eingangs- beziehungsweise Ausgangssignalen an den Abbildungseinrichtungen drei oder mehr.
Vorzugsweise ist die Anzahl der Abbildungseinrichtungen in der Kette mindestens 25. In Ausführungsformen sind jedoch auch zwischen 20 und 1000 verkettete Abbildungseinrichtungen vorgesehen.
In Ausführungsformen ist die Vorrichtung Teil einer FPGA-Einrichtung oder einer ASIC-Einrichtung.
Es werden bei dem Verfahren und der Vorrichtung insbesondere echte Zufallsbits erzeugt, die unabhängig von den Eingangsstartsignalpegeln sind. Die Signalformen haben nach dem Durchlauf der Abbildungskette in der Regel keine erkennbaren Signalflanken oder wohldefinierte Pegelwechsel. Man kann von quasi-analogen Signalverläufen sprechen, da erst durch das Abtasten mit Hilfe der Erfassungsvorrichtung logische Pegel oder Bitwerte abgeleitet werden. Es werden keine Pseudozufallsbits betrachtet.
Das Verfahren kann insbesondere über geeignete Beschreibungssprachen, beispielsweise VHDL oder Verilog, auf oder in einer FPGA- oder ASIC-Vorrichtung implementiert werden. Bei der FPGA-Vorrichtung bzw. dem Verfahren sind die Abbildungseinrichtungen vorzugsweise derart eingerichtet, dass Zustandsänderungen an einem Eingangssignal der n Eingangssignale in Abhängigkeit von der kombinatorischen Abbildung zu einem gleichen Zeitpunkt einen Zustandswechsel in einem oder mehreren der p Ausgangssignale möglichst zeitgleich hervorrufen.
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 Fachmann auch Einzelaspekte als Verbesserungen oder Ergänzungen zu der jeweiligen Grundform der Erfindung hinzufügen oder abändern.
Die für die vorgeschlagene Vorrichtung beschriebenen Ausführungsformen und Merkmale gelten für das vorgeschlagene Verfahren entsprechend.
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äutert werden.
Dabei zeigen:
1 ein Ablaufdiagramm für ein Ausführungsbeispiel für ein Verfahren zum Erzeugen von Zufallsbits;
2 eine schematische Darstellung eines ersten Ausführungsbeispiels für eine Vorrichtung zum Erzeugen von Zufallsbits, welche gemäß dem Verfahren nach 1 betrieben werden kann;
3 ein Detail einer Variante des Verfahrens gemäß 1;
4 eine schematische Darstellung zur Erläuterung eines Bitmusterzyklus zur Verwendung in einem Verfahren zum Erzeugen von Zufallsbits;
5 schematische Darstellungen von Eingangsstartsignalen, Pegelwechseln, Bitmusterwechseln und möglichen Taktsignalformen;
6 ein Ablaufdiagramm für ein Ausführungsbeispiel für ein Verfahren zum Bestimmen von Bitmusterzyklen zur Verwendung in Verfahren zum Erzeugen von Zufallsbits; und
7 eine schematische Darstellung eines weiteren Ausführungsbeispiels für eine Vorrichtung zum Erzeugen von Zufallsbits.
In den Figuren sind funktionsgleiche Elemente mit denselben Bezugszeichen versehen, sofern nichts anderes angegeben ist.
In der Beschreibung wird unter einem „wohldefinierten Pegelwechsel“ verstanden, dass eine im Wesentlichen steigende oder fallende Signalflanke erzeugt wird. Die jeweilige Signalflanke kann aber muss nicht reproduzierbar erzeugt werden.
Dass die beschriebenen Abbildungen „im Mittel“ eine Zustandsänderung eines Eingangssignals – oder eine Signalflanke – einer jeweiligen Abbildungseinrichtung auf mehr als ein Ausgangssignal der jeweiligen Abbildungseinrichtung abbilden, bedeutet, dass über alle möglichen Kombinationen von Eingangszustandsänderungen gemittelt mehr als eine Ausgangsbitmusteränderungen von einer Abbildung hervorgerufen werden.
Zum Beispiel sind alle oder eine Auswahl der kombinatorischen Abbildungen derart ausgestaltet, dass wenigstens eine Eingangsbitmusteränderung, bei der beispielsweise q Bits den Zustand ändern, zu einer Ausgangsbitänderung, bei der q + 1 Bits ihren Zustand ändern, führt.
Die Entropie wird als informationstheoretische Entropie angesehen, die einem jeweiligen erzeugten Zufallsbitmuster beigemessen werden kann.
Die 1 zeigt ein Ablaufdiagramm für eine Variante eines Verfahrens zum Erzeugen von Zufallsbits mit Hilfe von verketteten mehrspurigen kombinatorischen Abbildungseinrichtungen. Das Verfahren dient zum Beispiel dem Betreiben einer Vorrichtung wie sie in 2 gezeigt ist. Im Folgenden werden die 1 und 2 gemeinsam beschrieben.
In einem vorbereitenden Verfahrensschritt S0 werden Abbildungseinrichtungen 2 ₁–2 _m bereitgestellt, die wie es in 2 angedeutet ist, verkettet werden. Die 2 zeigt eine schematische Darstellung eines ersten Ausführungsbeispiels für eine Vorrichtung zum Erzeugen von Zufallsbits. Die Vorrichtung 1 ist in der Art einer Kette mit den Abbildungseinrichtungen 2 ₁–2 _m ausgestaltet. Dazu sind seriell hintereinander kombinatorische Digitalschaltungen 2 ₁–2 _m gekoppelt. Die kombinatorischen Digitalschaltungen 2 ₁–2 _m können auch als logische Gatter oder Abbildungseinrichtungen für eine jeweilige kombinatorische Abbildung K₁–K_m verstanden werden.
Zum Betrieb der Vorrichtung gemäß dem beschrieben Verfahren ist eine Steuereinrichtung 11 vorgesehen, die über Steuersignale CT an eine Starteinrichtung 3, eine Erfassungs- oder Abtastvorrichtung 4 und eine Auswerteeinrichtung 9 gekoppelt ist. Die Steuereinrichtung 11 koordiniert den Ablauf des Betriebs und die Durchführung der jeweiligen Verfahrensschritte. Es ist ferner eine an die Steuereinrichtung 11 gekoppelte Speichereinrichtung 12 vorgesehen.
Die Starteinrichtung 3 ist vorgesehen, um festgelegte Werte für die Eingangssignale ES₁₁–ES_1n für die erste Abbildungseinrichtung 2 ₁ bereitzustellen und davon ausgehend Pegelwechsel für diese Eingangsstartsignale zu erzeugen. Diese Einkopplung von logischen Pegelwechseln erfolgt als Schritt S1. Die dadurch entstehenden Signalflanken setzen sich durch die Kette von Abbildungen fort. An die letzte Ausgangsabbildungseinrichtung 2 _m der Kette ist die Erfassungs- oder Abtastvorrichtung 4 gekoppelt, die die Ausgangssignale A_m1–A_mn der letzten Abbildungseinrichtung 2 _m erfasst (Schritt S2). Beispielsweise werden dazu Latches oder Flip-Flops 6 eingesetzt, die Signalflanken innerhalb des zufälligen Signalverlaufs erfassen. Aus den erfassten Pegeln lässt sich im Schritt S3 ein Zufallsbit oder eine Zufallszahl ZB ableiten, die von der Abtasteinrichtung 4 ausgegeben werden kann. In der 1 ist n = p. Das Abtasten kann durch ein Taktsignal CK getriggert werden, welches ebenfalls von der Steuereinrichtung 11 erzeugt wird.
Das Einkoppeln einer oder mehrerer Signalflanken an die Eingänge der ersten Abbildungseinrichtung 2 _i als Eingangssignal E₁₁–E_1n gemäß Schritt S1, die Erfassung der Ausgangssignale A_m1–A_mn gemäß Schritt S2 und das Ermitteln der Zufallsbitwerte (Schritt S3) kann als ein Zufallslauf SL bezeichnet werden, bei dem wenigstens ein Zufallsbit ZB erzeugt wird. Die Entropie des Zufallsbits hängt dabei auch von der Wahl der eingekoppelten Pegelwechsel ab.
Es werden nun mehrere Zufallsläufe SL nacheinander durchgeführt, wobei eine zyklische Abfolge von Bitmustern an den Eingängen der ersten Abbildungseinrichtung 2 ₁ erzeugt wird. Dies ist in den 3–5 erläutert. Die Bitmuster der Abfolge oder des Zyklus sind in der Speichereinrichtung 12 abrufbar bereitgestellt.
Beim Wechsel von einem Eingangsbitmuster zu einem anderen entstehen Signalflanken. Insofern kann der Schritt S1 die Unterschritte umfassen, dass ein Eingangsbitmuster der Bitbreite n erzeugt wird (Schritt S11) und anschließend von der Starteinrichtung 3 zu einem anderen Eingangsbitmuster umgeschaltet wird (Schritt S12). Zur Vorbereitung des Verfahrens, wie es in 1 angedeutet ist, können zunächst alle möglichen 2ⁿ Eingangsbitmuster ermittelt werden und daraus eine zyklische Abfolge einer bestimmten Länge ausgewählt werden. Dabei wird vorzugsweise berücksichtigt, dass die Entropieausbeute bei der Zufallsbiterzeugung im Mittel über die gewählten Eingangsbitmusterwechsel der Abfolge bzw. des Zyklus von Umschaltvorgängen zwischen Eingangsbitmustern möglichst hoch ist.
Die 4 zeigt schematisch eine Abfolge oder einen Zyklus ZK von Eingangsbitmustern BM1–BMQ. Durch einen jeweiligen Umschaltvorgang USJ wird von einem jeweiligen Eingangsbitmuster BMJ zu einem nächsten BMJ + 1 übergegangen. Nach dem Q-ten Bitmuster BMQ wird wieder das erste Eingangsbitmuster BM1 erreicht. Jeder der Umschaltvorgänge US1–USQ führt in der Regel zu unterschiedlicher Entropieausbeute.
Das jeweils derart mit Hilfe eines Umschaltvorgangs USQ bzw. Eingangsbitmusterwechsels erzeugte Zufallsbit ZB oder Zufallsbitmuster kann einer optionalen Auswerteeinrichtung 9 zugeführt werden. Die Auswerteeinrichtung 9 unterzieht die erfassten Zufallsbits ZB für einen jeweiligen Eingangsbitmusterwechsel bzw. Umschaltvorgang USQ beispielsweise mit Hilfe statistischer Methoden einer Nachbearbeitung, um Schiefen in den erzeugten Zufallsbits ZB zu kompensieren. Man erhält dadurch am Ausgang echte Zufallsbits ZB‘. Eine Schiefe von erzeugten Zufallsbits bezeichnet das Verhältnis der Anteile von Nullen und Einsen. Bei einer idealen Schiefe liegt eine Verteilung von Zufallsbits von 1 und 0 mit einer Wahrscheinlichkeit von 0,5 vor. Eine Schiefe von 2% bedeutet, dass eine Wahrscheinlichkeit für einen H-Pegel oder eine Eins bei 0,52 liegt.
Jede Abbildungseinrichtung 2 _i hat n Eingänge für ein n Bit breites Eingangssignal E_ij mit j = 1...n und p Ausgänge für ein p Bit-breites Ausgangssignal A_ij mit j = 1...p. In der 2 sind die Ein- und Ausgänge nicht explizit angegeben. Eine jeweilige Abbildungseinrichtung 2 _i empfängt insofern E_i1–E_in Eingangssignale und gibt A_i1–A_ip Ausgangssignale aus. Die Verknüpfung zwischen Ein- und Ausgangssignalen ist über eine kombinatorische Abbildung K_i realisiert. Man erkennt in der Darstellung der 2, in der n = p ist, dass die K₁ bis K_m kombinatorischen Abbildungen hintereinander verkettet erfolgen.
Beim Betrieb der Vorrichtung zum Erzeugen von Zufallsbits 1 propagieren mit Jittern beaufschlagte Signale von der ersten Eingangsabbildungseinrichtung 2 ₁ bis zur Ausgangsabbildungseinrichtung 2 _m. Die Abbildungseinrichtungen 2 ₁–2 _m sind derart als kombinatorische Abbildungen K₁–K_m implementiert, dass im Mittel ein Zustandswechsel des an einem jeweiligen Eingang vorliegenden Signals E_k1–E_kn zu einem Zustandswechsel in mehr als einem der Ausgangssignale A_k1–A_kn führt. Das heißt, eine Veränderung eines jeweiligen Input-Bits bzw. eines logischen Zustandes eines Eingangssignals E_kj führt im Mittel (beispielsweise über eine Anzahl von Durchläufen) zu Änderungen in mehr als einem der Output-Bits des jeweiligen Knotens bzw. der jeweiligen Abbildungseinrichtung. Insofern akkumulieren und vervielfältigen sich Jitter, die in den Signalen E₁₁ bis E_mn bzw. A₁₁ bis A_m-1,n vorliegen, beim Durchlauf durch die verketteten Abbildungseinrichtungen 2 ₁ bis 2 _m. Das bedeutet, je länger der Signalweg ist, also je mehr verkettete seriell verschaltete Abbildungseinrichtungen 2 ₁–2 _m vorliegen, desto stärker wird ein vorliegender Jitter verstärkt und auf die n oder p verschiedenen Kanäle kopiert.
Obgleich dies der Einfachheit halber in der 2 so dargestellt ist, müssen die Abbildungseinrichtungen 2 ₁–2 _m nicht zwingend dieselbe Anzahl n von Ein- und Ausgängen haben. Die Bitbreite kann in der 2 im Verlauf des Signalweges von der Startvorrichtung 3 zur Abtastvorrichtung 6 variieren. Beispielsweise werden m = 100 Abbildungseinrichtungen nacheinander gekoppelt. Die Abbildungseinrichtungen können die jeweilige kombinatorische Abbildung K₁ bis K_m in der Art von Lookup-Tables 5 ₁–5 _m implementieren.
Die jeweilige Signaldurchlaufzeit in einer Abbildungseinrichtung bzw. einem logischen oder kombinatorischen Gatter 2 _i ist für alle Eingangssignale E_i1 bis E_in im Wesentlichen gleich, so dass aufgrund der implementierten kombinatorischen Abbildung K_i der Wechsel eines logischen Zustands an einem Eingangssignal E_ij im Wesentlichen zeitgleich zu logischen Wechseln an einem oder mehreren Ausgangssignalen A_il mit l = 1...n ist. Insofern ergeben sich n Kanäle mit zufälligen Signalformen, die von den Jittern hervorgerufen sind, die von den die digitalen Abbildungseinrichtungen aufbauenden Schaltelementen hervorgerufen sind.
Die schematisch angedeutete Vorrichtung zum Erzeugen von Zufallsbits 1 lässt sich insbesondere aufwandsgünstig in FPGA- oder ASIC-Einrichtungen realisieren. Gegenüber konventionellen Ringoszillatoren lassen sich mit einer höheren Datenrate Zufallsbits erzeugen, da insbesondere der den Zufall begünstigende Jitter mit Hilfe der mehreren Kanäle potenziell nfach vervielfältigt wird. Es ist durch die vielen Kanäle und Abbildungen unwahrscheinlich, dass Jitter-Beiträge einander kompensieren. Insofern kann aufwandsgünstig ein Zufallszahlengenerator mit einer hohen Zufallsbit-Erzeugungsfrequenz realisiert werden.
Aufgrund der linearen Topologie und endlichen Anzahl von kombinatorischen Abbildungen bzw. Abbildungseinrichtungen 2 ₁–2 _m durchläuft eine Signalflanke oder eine Eingangssignaländerung unter Beaufschlagung eines Jitters und Anwendung der kombinatorischen Abbildungen eine begrenzte Anzahl von Logikgattern. Demnach ist auch die Anzahl der Umschaltvorgänge beim Durchlauf einer Signalflanke oder Signaländerung von der Starteinrichtung 3 bis zur Abtasteinrichtung 6 endlich. Es ergibt sich dadurch ein besonders niedriger Stromverbrauch, so dass die vorgeschlagene Vorrichtung insbesondere zum Einsatz in mobilen Anwendungen, beispielsweise auf Chipkarten, geeignet ist. Gleichzeitig wird wegen der Auswahl der Abfolge im Mittel eine hohe Entropie pro erzeugtem Zufallsbit ZB erzielt.
Vorzugsweise sind mindestens 20 Abbildungseinrichtungen verkettet miteinander vorgesehen. In Ausführungsformen sind jedoch auch 50 oder 100 Abbildungen denkbar. Bevorzugt ist die Anzahl der miteinander verketteten Abbildungen bzw. Abbildungseinrichtungen zwischen 50 und 100. In besonderen Ausführungsformen ist die Anzahl zwischen 100 und 1.000 Abbildungseinrichtungen.
Im Folgenden wird eine mögliche Auswahl von zyklisch einzukoppelnden Eingangsbitmustern an einem Beispiel erläutert. Dabei wird vereinfacht von n = 3 Eingangsbits ausgegangen und damit eine Bitbreite von drei der Abbildungseinrichtungen 2 _i.
Die 5 zeigt schematisch Eingangsstartsignale, Pegelwechsel, Bitmusterwechsel und mögliche Taktsignalformen. Zum Start eines jeweiligen Zufallsbiterzeugungslaufs (vgl. Schritt SL in 1) mit Hilfe der Vorrichtung gemäß 2 werden Eingangssignalpegel ES₁₁...E_S3 verändert, sodass wohldefinierte Pegelwechsel PW eintreten. Der Pegelwechsel PW oder die entsprechende Signalflanke bzw. Signalflanken werden durch die Abbildungskette, wie oben beschrieben geführt. Eine mögliche zyklische Abfolge von Eingangsbitmustern BM1–BM4 der Länge vier ist in 5 oben dargestellt. Alle Eingangsstartsignale ES_i sind beim Bitmuster BM1 zunächst auf logischem L-Pegel, wie es in dem mittleren Diagramm, das den Verlauf des Eingangssignals E₁₁ zeigt, angedeutet ist. Die untere Kurve zeigt einen möglichen zeitlichen Verlauf eines Takt- oder Abtastsignals CK für die Abtasteinrichtung 4.
Es werden nun nacheinander durch die Umschaltvorgänge US1–US4 wohldefinierte Pegelwechsel der jeweiligen Eingangssignale von L auf H bzw. Null auf Eins vollzogen. Man erhält dadurch ein zweites Eingangsbitmuster BM2 = 111. Diese Signalflanken werden durch die kombinatorischen Abbildungen verzerrt, mit Jitter beaufschlagt und somit „verzufälligt“, sodass zum Zeitpunkt T1 die am Ausgang der letzten Abbildungseinrichtung 2 _m anliegenden Ausgangssignale A_m1...A_m,n gesampled werden können und die erhaltenen Daten als Zufallsbits ZB genutzt werden können.
Anschließend wird das Eingangsbitmuster BM2 durch Umschalten auf das Bitmuster BM3 = 010 und danach auf das Bitmuster BM4 gebracht. Dadurch entstehen erneut Pegelwechsel oder Signalflanken, die zu zufälligen Bitwerten der abgetasteten Ausgangssignale A_m1...A_m,n führen. Dieser Vorgang wird solange wiederholt bis der Zyklus beendet ist und das Bitmuster BM1 wieder erreicht ist. Die Verteilung der Zufallsbits bei den Läufen mit den verschiedenen Umschaltvorgängen ist dabei unabhängig voneinander, sodass auch verschiedene Entropien erzielt werden. Die Zufallsbits für die Abtastzeitpunkte T1–T4 werden anschließend Nachbehandlungsverfahren unterzogen.
Die 6 zeigt ein Ablaufdiagramm für ein Ausführungsbeispiel für ein Verfahren zum Bestimmen von günstigen Bitmusterzyklen zur Verwendung in Verfahren zum Erzeugen von Zufallsbits.
In einem ersten Schritt S01 werden alle möglichen Eingangsbitmuster ermittelt. Für eine drei Bit breite erste Abbildung K₁ (vgl. 1) ergeben sich acht mögliche Bitmuster BM1–BM8.
In einem zweiten Schritt S02 werden nun alle möglichen Umschaltvorgänge bestimmt. Dies sind bei eine Bitbreite von drei 56 Umschaltvorgänge zwischen den möglichen verschiedenen Eingangsbitmustern.

Für jeden möglichen Umschaltvorgang zum Einkoppeln von Pegelwechseln wird mit Hilfe der Vorrichtung eine erzielbare Entropie pro Bit ermittelt. Dazu werden viele, beispielsweise 1000, Zufallsläufe SL mit jeweils demselben Umschaltvorgang durchgeführt und aus den ermittelten Zufallsbitwerten im Schritt S03 die Entropie statistisch bestimmt. Anschließend wird der nächste mögliche Umschaltvorgang untersucht. In der folgenden Tabelle sind mögliche Entropiewerte beim Einkoppeln von Signalflanken durch Umschalten zwischen drei Bit breiten Eingangssignalen angegeben:

B	M1 B	M2	BM3	BM4	BM5	BM6	BM7	BM8
BM1	0	0,39904	0,151946	0,078371	0,005403	0,986149	0,041984	0,172539
BM2	0,039445	0	20,97715	0,089346	0,004461	0,027668	0,001712	0,009199
BM3	0,459892	0,127488	0	0,032225	0,013457	0,095347	0,062022	0,028147
BM4	0,052597	0,111464	0,024195	0	0,004902	0,00003	0,005765	0,000655
BM5	0,073762	0,181578	0,047688	0,002549	0	0,023921	0,019238	0,114525
BM6	0,056096	0,027278	0,097293	0,018824	0,709606	0	0,06885	0,133751
BM7	0,189715	0,186976	0,027718	0,508819	0,005321	0,096198	0	0,042869
BM8	0,018048	0,033031	0,245241	0,251424	0,003192	0,392672	0,125324	0

Die Bitmuster BM1–BM8 sind nur schematisch zu verstehen und müssen nicht mit den Beispielen gemäß der 5 übereinstimmen. Die obige Tabelle wurde mit Hilfe einer Weibull-Verteilung mit Formparameter 0,75 und Skalenparameter 0,1 erzeugt und stellt eine mögliche Entropieverteilung auf die möglichen Umschaltvorgänge dar.
Zum Beispiel wird bei einem möglichen Umschaltvorgang vom Eingangsbitmuster BM1 zum Eingangsbitmuster BM6 eine Entropie von 0,986149 Bit erzielt. Hin- und Herschalten zwischen den Eingangsbitmustern BM1 und BM6 liefert im (arithmetischen) Mittel etwa 0,52 Bit Entropie, denn der Umschaltvorgang von BM6 zu BM1 kann nur 0,056096 Bit liefern.
Es ist nun im Hinblick auf die Entropieausbeute bei mehrfach nacheinander durchgeführten Zufallsläufen günstiger, mindestens drei Bitmuster auszuwählen und zyklisch als Eingangsbitmuster zu durchlaufen. Zum Beispiel liefert der Zyklus bzw. die Abfolge BM1 zu BM6 zu BM5 zu BM1 (zu BM6 usw.) eine mittlere Entropieausbeute pro Zufallsbit von 0,5898 Bit.
Nachdem alle Entropiewerte, wie in der Tabelle oben, ermittelt wurden, wählt man nun im Schritt S04 diejenige Abfolge von möglichen Eingangsbitmustern aus, die die höchste mittlere Entropieausbeute liefert. Die Untersuchungen der Anmelderin an der vorliegenden Entropietabelle haben ergeben, dass bei diesem Beispiel die Abfolge BM1, BM6, BM5 am günstigsten ist. Der beste Zyklus der Länge vier liefert nur 0,55 Bit mittlere Entropie, der beste Zyklus der Länge fünf 0,53 Bit der Länge sechs 0,45 Bit, der Länge sieben 0,44 und der Länge acht nur 0,4 Bit mittlere Entropie.
Insofern wird mit Hilfe der vorgeschlagenen Verfahren eine besonders effiziente Zufallsbiterzeugung ermöglicht.
Die 7 zeigt eine schematische Darstellung eines weiteren Ausführungsbeispiels für eine Vorrichtung zum Erzeugen von Zufallsbits. Die Vorrichtung 10 implementiert einige optionale Abwandlungen bezüglich der in 2 dargestellten Vorrichtung 1. Die 7 zeigt m hintereinander geschaltete Abbildungsvorrichtungen 2 ₁ bis 2 _m, die jeweils kombinatorische Abbildungen K₁–K_m implementieren. Dabei ist die Bitbreite der Abbildungen nicht konstant. Beispielsweise sind die Abbildungsvorrichtungen 2 ₁ und 2 _k–2 _m als kombinatorische Abbildungen implementiert, die vier Eingangssignale auf vier Ausgangssignale abbilden. Eine Steuereinrichtung 11 liefert Steuersignale CT und koordiniert den Betrieb, wie bereits zu den 1–6 erläutert wurde. In einer Speichereinrichtung 12 sind die Eingangsbitmuster der verwendeten zyklischen Abfolge abgelegt.
Die kombinatorische Abbildung K₂, die in der Abbildungseinrichtung 2 ₂ implementiert ist, bildet vier Eingangsstartsignale ES₂₁, ... ES₂₄, welche von einer Starteinrichtung 3 eingekoppelt werden, auf vier Ausgangssignale A₂₁, A₂₂, A₂₃, A₂₄ ab. Die Starteinrichtung 3 erzeugt die Eingangsbitmuster, wie sie im Speicher 12 abgelegt sind, um die Pegelwechsel zu generieren. Die in der dritten Abbildungseinrichtung 2 ₃ implementierte kombinatorische Abbildung K₃ bildet fünf Eingangssignale auf fünf Ausgangssignale ab. Die vierte kombinatorische Abbildung K₄ die mit Hilfe der Abbildungsvorrichtung 2 ₄ implementiert ist, bildet fünf Eingangs- auf vier Ausgangssignale ab.
Das Ausgangssignal A₁₁ wird mit Hilfe eines Inverters 8 in ein Eingangssignal E₂₁ für die zweite Abbildungseinrichtung 2 ₂ invertiert. Die beiden Ausgangssignale A₁₃ und A₁₄ der ersten Abbildungseinrichtung 2 ₁ werden mit Hilfe eines logischen Gatters 7 miteinander verrundet und als Eingangssignal E₂₃ der zweiten Abbildungseinrichtung 2 ₂ zugeführt.
Grundsätzlich ist es von Vorteil, wenn ausschließlich vorwärts gekoppelte Signalpfade entstehen. Es ist jedoch unschädlich, wenn beispielsweise Rückkopplungspfade auftreten, bei denen eine Zustandsänderung eines Ausgangssignals, beispielsweise des Ausgangssignals A_k4, als Eingangssignal E₃₅ rückgekoppelt ist, aber die kombinatorische Abbildung K₃ auf einen Zustandswechsel des Eingangssignals E₃₅ nicht reagiert oder keine Vervielfältigung auf andere Ausgangssignale A₃₁ bis A₃₅ entsteht. Bei den Zufallsbiterzeugungsvorrichtungen ist keine Rückkopplungsschleife derart gebildet, dass eine Zustandsänderung mindestens eines Ausgangssignals einer Abbildungseinrichtung als eine Zustandsänderung mindestens eines Eingangssignals einer anderen Abbildungseinrichtung insbesondere signalpfadaufwärts zugeführt wird. Es würde genügen, solche Rückkopplungen auszuschließen, bei denen eine Zustandsänderung eines rückgekoppelten Ausgangssignals einer bestimmten Abbildungseinrichtung 2 _k als eine Zustandsänderung mindestens eines Eingangssignals E₃₅ einer anderen Abbildungseinrichtung 2 ₃ derart zugeführt ist, dass eines oder mehrere Ausgangssignale A_k1–A_k4 der bestimmten Abbildungseinrichtung 2 _k von der Zustandsänderung des rückgekoppelten Ausgangssignals A_k4 beeinflusst wird. Sozusagen hängt keines der Ausgangssignale von sich selbst ab.
Die Ausgangssignale A_m1–A_m4 werden einer Erfassungsvorrichtung 4 zugeführt, die vier Toggle-Flip-Flops 6 aufweist. Das jeweilige Toggle-Flip-Flop 6 zählt die steigenden Signalflanken als 0 auf 1-Durchgänge modulo 2. Am Ausgang der Erfassungsvorrichtung 4 sind dann die jeweiligen Zufallsbits ZB abgreifbar. Die Ausgabe der Zufallsbits ZB ist taktgesteuert.
Wiederum werden die Eingangsbitmuster der zyklischen Abfolge von Eingangsbitmustern zum Erzeugen der logischen Pegelwechsel derart ausgesucht, dass eine Summe der Entropien der ermittelten Zufallsbits von einem Eingangsbitmuster zum nächsten oder ein Mittelwert der Entropien der ermittelten Zufallsbits für die zyklische Abfolge möglichst groß ist.
Das vorgeschlagene Verfahren und die Vorrichtungen eignen sich insbesondere zur Implementierung in ASICs. Die logischen Funktionen der Abbildungseinrichtungen haben vorzugsweise dieselbe logische Tiefe, um eine gleiche Signallaufzeit der kombinatorischen Abbildungen zu erzielen. Auf Lookup-Tables kann insofern auch verzichtet werden. Die Erfindung ermöglicht also unter anderem eine schnelle Zufallsbiterzeugung bei geringem Hardwareaufwand mit hoher Entropie pro erzeugtem Bit.
Beispiele für eine mögliche Konstruktion für geeignete kombinatorische Abbildungen mit einem maximalen Avalancheeffekt sind in der DE 10 2014 203 648 A1 in den Absätzen 0067 bis 0076 angegeben, worauf hier vollinhaltlich Bezug genommen wird („incorporated by reference“).
Obwohl die Erfindung im Detail durch das bevorzugte Ausführungsbeispiel 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. Obwohl in den Ausführungsbeispielen jeweils alle möglichen Bitmusterumschaltungen betrachtet wurden, genügt es eine Auswahl der jeweils möglichen Eingangsbitmuster zu untersuchen und die Abfolge oder den Zyklus für die Entropieausbeute günstig festzulegen.
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

DE 102014203648 A1 [0006, 0006, 0103]
US 8531247 B2 [0007]
US 8892616 B2 [0007]
US 8300811 B2 [0007]
US 9147088 B2 [0007]
EP 2605445 B1 [0007]
EP 2870565 A1 [0007]
EP 2891102 A1 [0007]
US 8843761 B2 [0007]

Claims

Verfahren zum Erzeugen von Zufallsbits (ZB) umfassend: Bereitstellen (S0) einer Mehrzahl von seriell miteinander verketteten Abbildungseinrichtungen (2 ₁–2 _m), wobei jede der Mehrzahl von Abbildungseinrichtungen (2 ₁–2 _m) eingerichtet ist, eine vorgegebene Anzahl n Eingangssignale (E₁₁–E_mn) mit Hilfe einer kombinatorischen Abbildung (K₁–K_m) in eine vorgegebene Anzahl p Ausgangssignale (A₁₁–A_mp) abzubilden; Einkoppeln (S1) von logischen Pegelwechseln (PW) an eine erste Abbildungseinrichtung (2 ₁) der Mehrzahl der miteinander verketteten Abbildungseinrichtungen (2 ₁–2 _m) als Eingangsstartsignale (ES₁₁–ES_1n), wobei die jeweiligen logischen Pegelwechsel (PW) durch ein Umschalten (US1–USQ) von einem aktuellen Eingangsbitmuster (BMJ) zu einem nächsten Eingangsbitmuster (BMj + 1) erzeugt werden; Erfassen (S2) eines oder mehrerer Ausgangssignale (A₁₁–A_mp) an Ausgängen einer oder mehrerer Abbildungseinrichtungen (2 ₁–2 _m), welche von der ersten Abbildungseinrichtung (2 ₁) unterschiedlich sind; Ermitteln (S3) eines oder mehrerer Bitwerte in Abhängigkeit von dem oder den erfassten Ausgangssignalen (A₁₁–A_mp) als Zufallsbit (ZB) oder Zufallsbitmuster (ZBM); wobei eine zyklischen Abfolge (ZK) von Eingangsbitmustern (BM1–BMQ) zum Erzeugen der logischen Pegelwechsel (PW) derart eingekoppelt wird, dass eine mittlere Entropie der ermittelten Zufallsbits (ZB) von einem Eingangsbitmuster (BMJ) zum nächsten (BMJ + 1) größer oder gleich einem vorgegebenen Schwellwert ist.
Verfahren nach Anspruch 1, wobei zum Bestimmen der Abfolge (ZK) die Schritte durchgeführt werden: Bestimmen (S01) einer Auswahl von möglichen Eingangsbitmustern (BM1–BMP) für die ersten Abbildungseinrichtung (2 ₁); und Ermitteln (S03) der Entropien der ermittelten Zufallsbits für mögliche Bitmusterumschaltungen von einem Eingangsbitmuster (BM1–BMP) der Auswahl zu einen anderen Eingangsbitmuster (BM1’–BMP’) der Auswahl.
Verfahren nach Anspruch 1 oder 2, ferner umfassend: Auswählen (S04) der zyklischen Abfolge (ZK) von Bitmusterumschaltungen aus den möglichen Bitmusterumschaltungen derart, dass ein Mittelwert der Entropien der ermittelten Zufallsbits für die zyklische Abfolge (ZK) maximal ist.
Verfahren nach einem der Ansprüche 1–3, wobei die zyklische Abfolge (ZK) mindestens die Länge drei hat.
Verfahren nach einem der Ansprüche 1–4, wobei die kombinatorischen Abbildungen (K₁–K_m) keine kombinatorische Abbildung implementieren, welche eine Permutation der Eingangssignale (E₁₁–E_mn) auf die Ausgangssignale (A₁₁–A_mp) liefert.
Verfahren nach einem der Ansprüche 1–5, wobei mindestens eine der Mehrzahl von kombinatorischen Abbildungen (K₁–K_m) derart gewählt ist, dass eine Zustandsänderung eines Eingangssignals (E₁₁–E_mn) durch die kombinatorische Abbildung (K₁–K_m) im Mittel auf mehr als ein Ausgangssignal (A₁₁–A_mp) abgebildet wird,
Verfahren nach einem der Ansprüche 1–6, wobei keine Rückkopplungsschleife derart erzeugt wird, dass eine Zustandsänderung mindestens eines Rückkopplungsausgangssignals (A_ij) einer bestimmten kombinatorischen Abbildung (K_i) als eine Zustandsänderung mindestens eines Eingangssignals (E_kl) für eine andere kombinatorische Abbildung (K_k) derart zugeführt wird, dass eines oder mehrere Ausgangssignale (A_i1–A_ip) der bestimmten Abbildung (K_i) von der Zustandsänderung des Rückkopplungsausgangssignals (A_ij) beeinflusst wird.
Verfahren nach Anspruch 7, wobei die kombinatorischen Abbildungen (K₁–K_m) derart miteinander verkettet werden, dass keine Rückkopplungsschleife ausgebildet wird, bei der eine Zustandsänderung mindestens eines Ausgangssignals (A_ij) einer Abbildungseinrichtung (2 _i) als eine Zustandsänderung mindestens eines Eingangssignals (E_kl) einer anderen Abbildungseinrichtung (2 _k), welche signalpfadaufwärts vorgesehen ist, zugeführt ist.
Vorrichtung (1) zum Erzeugen von Zufallsbits (ZB) umfassend: eine Mehrzahl von Abbildungseinrichtungen (2 ₁–2 _m), wobei jede der Mehrzahl von Abbildungseinrichtungen (2 ₁–2 _m) eingerichtet ist, eine vorgegebene Anzahl n Eingangssignale (E₁₁–E_mn) mit Hilfe einer kombinatorischen Abbildung (K₁–K_m) in eine vorgegebene Anzahl p Ausgangssignale (A₁₁–A_mp) abzubilden, wobei die Abbildungseinrichtungen (2 ₁–2 _m) der Mehrzahl von Abbildungseinrichtungen (2 ₁–2 _m) miteinander verkettet sind; eine Starteinrichtung (3), welche eingerichtet ist, einer ersten Abbildungseinrichtung (2 ₁) der Mehrzahl der miteinander verketteten Abbildungseinrichtungen (2 ₁–2 _m) logische Pegelwechsel (PW) als Eingangsstartsignale (ES₁₁–ES_1n) einzukoppeln; eine Erfassungsvorrichtung (4), welche eingerichtet ist, eines oder mehrere Ausgangssignale (A₁₁–A_mp) an Ausgängen einer oder mehrerer Abbildungseinrichtungen (2 ₁–2 _m), welche von der ersten Abbildungseinrichtung (2 ₁) unterschiedlich sind, zu erfassen und als ein jeweiliges Zufallsbit (ZB) oder Zufallsbitmuster (ZBM) auszugeben; und eine Steuereinrichtung (11), welche die Starteinrichtung (3) und die Erfassungsvorrichtung (4) derart steuert, dass ein Verfahren nach einem der Ansprüche 1–8 durchgeführt wird.
Vorrichtung nach Anspruch 9, ferner mit einer Speichereinrichtung (12), welche eine zyklische Abfolge (ZK) von Eingangsbitmustern (BM1–BMQ) zum Erzeugen der zyklischen logischen Pegelwechsel (PW) abgespeichert bereitstellt.
Vorrichtung (1) nach Anspruch 9 oder 10, wobei die Erfassungseinrichtung (4) eingerichtet ist, die Ausgangssignale einer letzten Abbildungseinrichtung (2 _m) der Mehrzahl der miteinander verketteten Abbildungseinrichtungen (2 ₁–2 _m) als Zufallsbits zu erfassen.
Vorrichtung (1) nach Anspruch 10 oder 11, wobei die Erfassungseinrichtung (4) eingerichtet ist, die Ausgangssignale einer letzten Abbildungseinrichtung (2 _m) der Mehrzahl der miteinander verketteten Abbildungseinrichtungen (2 ₁–2 _m) als Zufallsbits zu erfassen.
Vorrichtung (1) nach einem der Ansprüche 10–12, wobei mindestens eine kombinatorische Abbildung (K₁–K_m) derart eingerichtet ist, dass die Eingangssignale (E₁₁–E_mn) unter Beaufschlagung eines Jitters und einer logischen Funktion auf die Ausgangssignale (A₁₁–A_mp) abgebildet werden.
Vorrichtung (1) nach einem der Ansprüche 10–13, wobei mindestens eine Abbildungseinrichtung (2 _q) als logisches Gatter ausgebildet ist, welches eine vorgegebene Anzahl von Eingangssignalen (E_q1–E_qn) logisch zu einer vorgegebenen Anzahl von Ausgangssignalen (A_q1–A_qp) verknüpft.
Vorrichtung (1) nach einem der Ansprüche 10–14, wobei die Vorrichtung (1, 10) Teil einer FPGA-Einrichtung oder einer ASIC-Einrichtung ist.