Aus der WO 97/43709 ist ein Verfahren zur Erzeugung von Zufallszahlen bekannt, bei dem mittels eines stochastischen Zufallssignalgenerators ein Zufalls- signal erzeugt wird. Der bekannte Zufallssignalge- nerator weist einen spannungsgesteuerten Oszillator auf, dessen Frequenzsteuereingang mit einer Rausch- spannungsquelle verbunden ist. Der Zufallssignalge- nerator weist an seinem Ausgang ein Oszillatorsig- nal auf, dessen Frequenz entsprechend der an dem Frequenzsteuereingang anliegenden, sich sto- chastisch ändernden Rauschspannung zufällig um eine Mittenfrequenz schwankt. Der Zufallsgenerator weist außerdem mehrere dynamische Flip-Flops auf, die je- weils mit ihrem Dateneingang an einem ihnen zuge- ordneten Ring-Oszillator angeschlossen sind. Dabei ist für jedes Flip-Flop jeweils ein eigener Ringos- zillator vorgesehen, wobei die Frequenzen dieser Ringoszillatoren etwas voneinander abweichen und jeweils größer sind als die Frequenz des spannungs- gesteuerten Oszillators des Zufallsignalgenerators.

Die Takteingänge der Flip-Flops sind jeweils mit

dem Ausgang des Zufallsignalgenerators verbunden, so dass bei einer Taktflanke des sich zufällig in der Frequenz verändernden Schwingungssignals des spannungsgesteuerten Oszillators jeweils ein Sig- nalwert der einzelnen Schwingungssignale der Ring- oszillatoren abgetastet und in das den betreffenden Ringoszillator zugeordnete Flip-Flop eingelesen wird. Die in den einzelnen Flip-Flops zwischenge- speicherten Signalwerte werden dann jeweils an ei- nem Ausgang der Flip-Flops als binäres Ziffernsig- nal der zu erzeugenden, mehrere Ziffern aufweisen- den Zufallszahl ausgegeben. Die Binärwerte der am Ausgang der Flip-Flops anliegenden Ziffernsignale sollen gleich verteilt sein. Der vorbekannte Zu- fallszahlengenerator hat jedoch den Nachteil, dass er mit dem Einbau zusätzlicher Hardwarekomponenten verbunden und kompliziert aufgebaut ist.

Aus der US 4,855,690 ist ein Zufallszahlengenerator bekannt, der einen analogen Oszillator mit einem dreieckförmigen Ausgangssignal verwendet, um die Frequenz eines spannungskontrollierten Oszillators mit einer höheren Frequenz zu verändern. Der Aus- gang des spannungsgesteuerten Oszillators wird zer- legt, um zufällige digitale Werte zu erzeugen.

Aus der US 5,153,532 ist ein Zufallszahlengenerator bekannt, bei dem getrennte Zeitsignale unterschied- licher Frequenz verwendet werden.

Aufgabe der Erfindung ist es, ein Verfahren zur Ge- nerierung von Zufallszahlen zu finden, das ohne den Einsatz von zusätzlicher Hardware in einem gängigen Rechnersystem eingesetzt werden kann. Dieses Ver-

fahren soll ein eingangs beschriebenes elektroni- sches Gerät ersetzen und darüber hinaus die Fähig- keit haben, die Güte der Zufallszahlen und seine eigene Funktion zu überprüfen.

Die Aufgabe ist bei einem Verfahren zum Generieren von Zufallszahlen, wobei die Schwingungen von min- destens zwei voneinander unabhängigen Oszillatoren verglichen werden, dadurch gelöst, dass die im Be- trieb der Oszillatoren auftretende Frequenzabwei- chung zum Generieren der Zufallszahlen genutzt wird. Oszillatoren weisen im Betrieb keine exakt konstante Frequenz auf, sondern es treten Frequenz- abweichungen in Form eines sogenannten Flatterns auf. Die Frequenzabweichungen der Oszillatoren wer- den auch als Drift bezeichnet. Aufgrund der unter- schiedlichen Drifts schwingen die beiden Oszillato- ren nicht synchron zueinander, sondern es treten Phasenverschiebungen auf, die nicht vorhersehbar sind. Die Frequenzabweichung hat einen natürlichen Ursprung, kann aber auch künstlich hervorgerufen werden. Unter Frequenzabweichung wird die Summe der Frequenzabweichungen der beiden Oszillatoren verstanden.

Mittlerweile ist in einer Vielzahl elektronischer Geräte bereits ein Prozessor installiert. Das er- findungsgemäße Verfahren liefert den Vorteil, dass ein bereits installierter Prozessor verwendet wer- den kann. Es ist also keine zusätzliche Hardware, zum Beispiel in Form eines zusätzlichen Oszilla- tors, erforderlich, um die Zufallszahlen zu gene- rieren.

Ein bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass der Oszillator be- ziehungsweise der Taktgeber eines Prozessors als einer der beiden Oszillatoren verwendet wird.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass eine Echtzeituhr als einer der zwei voneinander unabhän- gigen Oszillatoren verwendet wird. Eine Echtzeituhr ist heutzutage mittlerweile in vielen elektroni- schen Geräten und fast in jedem Rechner vorhanden.

Es ist also auch für den zweiten Oszillator keine zusätzliche Hardwarekomponente erforderlich.

Selbstverständlich kann statt der Echtzeituhr aber auch ein anderer, geräteeigener oder gerätefremder Oszillator verwendet werden.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass in ei- nem ersten Verfahrensschritt die Zeit der Echtzeit- uhr abgefragt und einem Startwert zugeordordnet wird. In einem zweiten Verfahrensschritt wird die Zeit der Echtzeituhr wiederholt in Abhängigkeit von der Taktzahl des Prozessors abgefragt und mit dem Startwert verglichen, bis die abgefragte Zeit von dem Startwert abweicht. Die Zeit der Echtzeituhr wird in mehr oder weniger regelmäßigen Zeitinter- vallen aktualisiert. Nach einer Aktualisierung der Echtzeituhr stimmt die abgefragte Zeit nicht mehr mit dem Startwert überein. Durch die Verfahrens- schritte 1 und 2 kann die Anzahl der Vergleiche be- stimmt werden, die durchgeführt werden, bis die Echtzeituhr aktualisiert wird.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass die An- zahl der Vergleiche als Zufallszahl verwendet wird.

Dadurch ist es möglich, Zufallszahlen mit einer großen Entropie zu erzeugen, die mit vertretbarem Aufwand nicht vorhersehbar sind.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass der zeitliche Abstand zwischen zwei Vergleichen gemäß dem zweiten Verfahrensschritt kleiner als der Kehr- wert aus der Summe der relativen Frequenzabweichun- gen der beiden Oszillatoren ist. Dadurch wird si- chergestellt, dass der zeitliche Abstand der Zeit- abfragen kleiner ist als die aus der kombinierten Frequenzabweichung (Drift) resultierende zeitliche Abweichung der Schwingungsperiode des zweiten Os- zillators. Somit befindet sich die Messgenauigkeit der zeitlichen Abweichung der Schwingungsperiode innerhalb der unvorhersehbaren statistischen Schwankung.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass die Verfahrensschritte 1 und 2 wiederholt werden, bis eine vorgegebene Anzahl Wiederholungen erreicht ist. Wenn der Prozessor und die Echtzeituhr syn- chron arbeiten würden, dann würde die Anzahl der Vergleiche zwischen zwei Integerzahlen alternieren.

In der Praxis arbeiten der Prozessor und die Echt- zeituhr jedoch asynchron. Infolge der unvorherseh- baren Frequenzabweichungen und dem sogenannten Flattern der beiden Oszillatoren variiert die An- zahl der Vergleiche deutlich stärker als zwischen

zwei Integerzahlen. Durch die Wiederholungen der Verfahrensschritte 1 und 2 werden die unterschied- lichen Anzahlen der Vergleiche zwischen zwei Aktua- lisierungen der Echtzeit erfasst.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass die bei der Generierung der Zufallszahlen erzeugte Entropie während der Generierung der Zufallszahlen berechnet wird. Der Begriff Entropie wird im Rahmen der vor- liegenden Erfindung als Maß für die Vorhersehbar- keit der erzeugten Zufallszahlen verwendet. Die Entropie gibt den mittleren Informationsgehalt ei- ner Zeichenmenge an. Je größer die Entropie, desto geringer ist die Wahrscheinlichkeit, dass die er- zeugten Zufallszahlen vorhergesehen werden können.

Dadurch wird sichergestellt, dass die Zufallszahlen ein vorgegebenes Maß an Entropie aufweisen. Die Entropie wird vorzugsweise nach der Methode von Shannon berechnet.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass der Prozessor auch zum Vergleichen der Schwingungen der beiden Oszillatoren verwendet wird. Das liefert den Vorteil, dass die Zufallszahlen rein über Software ohne die Implementierung von weiterer Hardware er- zeugt werden können.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass der Prozessor zur Berechnung der bei der Generierung der Zufallszahlen erzeugten Entropie verwendet wird. Das liefert den Vorteil, dass der bereits

vorhandene Prozessor genutzt werden kann. Eine Imp- lementierung von zusätzlicher Hardware ist nicht erforderlich.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass die ge- nerierten Zufallszahlen einem Pseudozufallszahlen- generator als Startwert zugeführt werden. In dem nachgeschalteten Pseudozufallszahlengenerator wird deterministisch eine Zufallszahlenreihe erzeugte deren Anfangswert unbekannt ist. Durch den Pseudo- zufallszahlengenerator wird eine schnelle Regene- rierung von Zufallszahlen ermöglicht.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass die ge- nerierten Zufallszahlen durch kryptographische Me- thoden miteinander verknüpft werden. Dadurch werden die Zufallszahlen vermischt, um eine eventuell vor- handene unerwünschte Verteilung der erzeugten Zu- fallszahlen aufzulösen.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass den er- zeugten Zufallszahlen weitere, auf andere Art und Weise erzeugte Zufallszahlen hinzugefügt werden.

Die weiteren Zufallszahlen können zum Beispiel aus den Task-Switches des Prozessors oder der freien Kapazität einer Festplatte gewonnen werden.

Ein weiteres bevorzugtes Ausführungsbeispiel des Verfahrens ist dadurch gekennzeichnet, dass es sich bei dem Prozessor um den Prozessor eines insbeson- dere elektronischen Geräts mit Internetanbindung,

zum Beispiel eines Computers, einer Telekommunika- tionseinrichtung, insbesondere eines Mobiltelefons, eines Terminals, insbesondere eines Multimediater- minals, oder eines Autoradios handelt.

Bei einem elektronischen Gerät mit einem Prozessor und einem Zufallszahlengenerator ist die oben ange- gebene Aufgabe dadurch gelöst, dass der Zufallszah- lengenerator nach einem der vorab beschriebenen Verfahren arbeitet.

Die vorliegende Erfindung ermöglicht die Erzeugung von Zufallszahlen aus dem Vergleich zweier Oszilla- toren rein durch Software, ohne die Implementierung irgendwelcher zusätzlicher Hardware. Einer der Os- zillatoren wird sowohl zur Steuerung des Messab- laufs als auch zum Phasenvergleich mit dem zweiten Oszillator verwendet. Sogar die Berechnung der er- zeugten Entropie kann durch einen der"Oszillato- ren"erfolgen. Im Gegensatz dazu werden in einer auf Hardware basierenden Lösung für jede dieser Funktionen separate elektronische Baugruppen ver- wendet und entsprechend miteinander verknüpft.

Die erfindungsgemäße Lösung liefert darüber hinaus den Vorteil, dass sie im Gegensatz zu einer reinen Hardwarelösung vielseitig einsetzbar ist. Das Ver- fahren kann sowohl in. Server-Systemen als auch bei Client-Computern angewendet werden. Darüber hinaus kann das Verfahren besonders vorteilhaft in Mobil- telefonen angewendet werden.

Ein weiterer Vorteil besteht darin, dass das Ver- fahren direkt in Hochsprachen, wie JAVA oder C++,

integrierbar ist. Das Verfahren kann plattformunab- hängig in beliebigen Systemen zum Erzeugen von Zu- fallszahlen verwendet werden. Die einzige Voraus- setzung, die an die zu verwendende Hardware ge- stellt wird, ist das Vorhandensein von zwei unab- hängigen Oszillatoren.

Die beiden Oszillatoren können entweder in ein und dasselbe Gerät integriert sein, es ist aber auch möglich, zwei Oszillatoren in getrennten Geräten zu verwenden. Hauptanwendungsgebiete für das Verfahren sind Computer und Mobiltelefone mit Internetanbin- dung.

Die erzeugten Zufallszahlen können verwendet wer- den, um durch asymmetrische Verschlüsselungsverfah- ren Schlüssel zu erzeugen und um die symmetrische Verschlüsselung zu starten (SSL).

Weitere Vorteile, Merkmale und Einzelheiten der Er- findung ergeben sich aus der nachfolgenden Be- schreibung, in der unter Bezugnahme auf die Zeich- nung ein Ausführungsbeispiel im Einzelnen beschrie- ben ist. Dabei können die in den Ansprüchen und in der Beschreibung erwähnten Merkmale jeweils einzeln für sich oder in beliebiger Kombination erfindungs- wesentlich sein. Es zeigen : Figur 1 die schematische Darstellung eines Ver- gleichs der Schwingungen zweier Oszilla- toren ; Figur 2 einen Verfahrensablaufplan eines Kollek- tors für dynamische Entropie ; und

Figur 3 einen Verfahrensablaufplan eines Ausfüh- rungsbeispiels des erfindungsgemäßen Ver- fahrens.

In Figur 1 sind die Zyklen eines Prozessors mit 1 bezeichnet. Die Prozessorzyklen 1 schwanken zwi- schen Null und Eins. Mit 2 sind in Figur 1 die Zyk- len einer Echtzeituhr bezeichnet, die ebenfalls zwischen Null und Eins oszilliert. Der Prozessor 1 weist eine deutlich höhere Frequenz auf als die Echtzeituhr 2. Durch gestrichelte Linien 5 und 7 ist angedeutet, dass die Echtzeituhr 2 in mehr oder weniger regelmäßigen Abständen aktualisiert wird.

Durch einen Pfeil 10 ist eine erste Zeitabfrage an- gedeutet, deren Ergebnis einem Startwert zugeordnet wird. Durch Pfeile 12,13,15 und 16 sind weitere Zeitabfragen angedeutet. Die Zeitabfragen 12, 13, 15 und 16 erfolgen immer nach einer bestimmten An- zahl Prozessorzyklen. Nach jeder der Zeitabfragen 12,13,15 und 16 wird die abgefragte Zeit mit dem aus der Zeitabfrage 10 gewonnenen Startwert vergli- chen. In dem in Figur 1 dargestellten Beispiel er- geben die Zeitabfragen 12 und 13, dass die abge- fragte Zeit mit dem Startwert übereinstimmt. Ein Vergleich der bei der Zeitabfrage 15 abgefragten Zeit mit dem Startwert ergibt jedoch keine Überein- stimmung.

Durch Doppelpfeile 18,19,22 und 23 sind in Figur 1 Schleifen angedeutet, die nach einem positiven Vergleich durchlaufen werden. Nach einem positiven Vergleich, das heißt wenn die abgefragte Zeit dem Startwert entspricht, erfolgt eine erneute Zeitab-

frage. Durch einen Pfeil 25 ist in Figur 1 die aus der kombinierten Frequenzabweichung resultierende zeitliche Abweichung der Schwingungsperiode des Os- zillators 2 angedeutet. Durch die gestrichelte Li- nie 27 wird angedeutet, dass die Aktualisierung 7 der Echtzeituhr 2 für den Fall bereits bei 7 er- folgt, dass die kombinierte Drift zu einer zeitli- chen Verkürzung der Schwingungsperiode des Oszilla- tors 2 führt. In diesem Fall ergibt die Zeitabfrage 15, dass die abgefragte Zeit nicht mit dem aus 10 gewonnenen Startwert übereinstimmt. Für den Fall, dass die kombinierte Drift zu einer zeitlichen Ver- längerung der Schwingungsperiode des Oszillators 2 führt, würde erst die Zeitabfrage 16 einen negati- ven Zeitvergleich ergeben.

In Figur 2 ist der Verfahrensablaufplan eines Kol- lektors 29 für dynamische Entropie dargestellt. Zu- nächst wird in 30 eine als Periode bezeichnete Va- riable gleich Null gesetzt. Bei einer Zeitmarke 32 erfolgt eine erste Zeitabfrage. Die erste Zeitab- frage 32 in Figur 2 entspricht dem Pfeil 10 in Fi- gur 1. Nach der ersten Zeitabfrage 32 erfolgt bei einer zweiten Zeitmarke 34 eine zweite Zeitabfrage.

Die zweite Zeitabfrage 34 in Figur 2 entspricht dem Pfeil 12 in Figur 1. Nach der zweiten Zeitabfrage 34 wird die Periode um Eins hochgesetzt. Anschlie- ßend wird in einem Vergleich 38 überprüft, ob die Ergebnisse der Zeitabfragen 32 und 34 übereinstim- men. Wenn dies der Fall ist, erfolgt, wie durch den Pfeil 40 angedeutet ist, eine erneute Zeitabfrage 34. Die Schleife 40 wird solange wiederholt, bis der Vergleich 38 ergibt, dass die Ergebnisse der Zeitabfragen 32 und 34 nicht übereinstimmen. Bei

einem derartigen negativen Vergleich wird, wie durch einen Pfeil 42 angedeutet ist, in dem Verfah- rensschritt 44 ein Zähler i um Eins hochgesetzt.

In Figur 3 ist der Verfahrensablaufplan eines Zu- fallszahlengenerators 50 dargestellt. Der Start des Verfahrensablaufs ist durch einen Punkt 52 angedeu- tet. In einem Block 56 wird statische Entropie er- zeugt und der Zähler i gleich Null gesetzt. In ei- nem Block 58 wird entsprechend dem in Figur 2 dar- gestellten Verfahrensablauf dynamische Entropie er- zeugt und der Zähler i hochgesetzt. In einem Ver- gleich 60 wird überprüft, ob der Wert des Zählers i einem einstellbaren Vorgabewert entspricht.

Wenn dies nicht der Fall ist, wird, wie durch einen Pfeil 62 angedeutet ist, noch einmal Block 58 durchlaufen. Wenn der Wert des Zählers i den ein- stellbaren Vorgabewert erreicht hat, wird in einem Block 64 die Entropie berechnet und der Zähler i wieder auf Null gesetzt. Die i-mal durchlaufende Schleife 62 dient dazu, nicht unnötigerweise oft die Entropie zu berechnen. Die Entropieberechnung 64 wird erst dann durchgeführt, wenn zu erwarten ist, dass der Wert der Entropie ausreichend groß ist. Der Vorgabewert kann in Versuchsmessungen für ein spezielles System ermittelt werden.

Anschließend wird in einem Vergleich 66 überprüft, ob die Entropie größer als ein vorzugebender Soll- wert ist. Wenn das nicht der Fall ist, erfolgt, wie durch einen Pfeil 68 angedeutet ist, ein Rücksprung zu Block 56, wo wieder statische Entropie gesammelt wird. Als statische Entropie werden im Rahmen der

vorliegenden Erfindung zufällige Daten angesehen, die in einem Rechnersystem vorhanden sind, wie zum Beispiel der freie Speicher.

Wenn der Vergleich 66 ergibt, dass die in 64 ermit- telte Entropie größer als ein vorzugebender Soll- wert ist, werden in einem Block 70 ein sogenannter Hash-Zähler um einen Wert hochgesetzt und die Ent- ropie-Variable auf Null gesetzt. In einem Vergleich 72 wird überprüft, ob der Hash-Zähler größer als ein vorgegebener Wert ist. Wenn das der Fall ist, erfolgt, wie durch einen Pfeil 76 angedeutet ist, die Ausgabe der ermittelten Zahl. Wenn der Hash- Zähler noch nicht größer als ein vorzugebender Sollwert ist, erfolgt, wie durch einen Pfeil 74 an- gedeutet ist, ein Rücksprung zu Block 56.

Durch das Hochsetzen des Hash-Zählers in 70 werden die Daten zusätzlich durchmischt. Die Zufälligkeit der Daten bleibt erhalten, aber möglicherweise auf- tretende statistische Verteilungen innerhalb der Darstellung der Daten werden somit unterbunden.