Zufallsahlen werden in verschiedenen Anwendungsfeldern benö- tigt. Beispielhaft seien Simulation, Tests und kryptographi- sche Anwendungen genannt. Gerade für letztere scheidet aus Sicherheitsgründen die Verwendung von sogenannten Pseudo- Zufallszahlen aus. Daher werden oft physikalische Zufallszah- lengeneratoren verwendet. Diese basieren in der Regel auf dem stochastischen Rauschen eines physikalischen Systems. Hierbei stellen sich vor allem Probleme dahingehend, daß aus einem zufälligen physikalischen Signal möglichst schnell eine gleichverteilte Folge von Nullen und Einsen erzeugt werden soll, und daß sich die statistischen Eigenschaften eines Sig- nals, insbesondere die Wahrscheinlichkeitsdichtefunktion, mit der Zeit durch äußere Einflüsse wie Temperatur oder Druck än- dern.

Zufallszahlengeneratoren sind aus"High Quality Physical Ran- dom Number Generator", Markus Dichtl und Norbert Janssen, Proceedings of Eurosmart Security Conference, Juni 2000, Mar- seille, Frankreich, Seiten 279 bis 287, bekannt. Ein bekann- ter Zufallszahlengenerator umfaßt einen Oszillator, ein dem Oszillator nachgeschaltetes D-Flip-Flop und am Ausgang des D- Flip-Flops einen Schalter, der von einem Oszillator mit Pha- senjitter gesteuert wird. Der Oszillator mit Phasenjitter, der den Schalter am Ausgang des D-Flip-Flops steuert, hat dann, wenn die Frequenz des Oszillators in einem bestimmten Verhältnis zur Frequenz des Oszillators mit Phasenjitter ge-

wählt wird, einen Zustand, der vom vorherigen Zustand unab- hängig ist, so daß ein qualitativ hochwertiges Rauschsignal erzeugt wird. Pro Schalterbetätigung wird ein Zufallsbit er- zeugt, das einer Nachverarbeitung und Kompression unterzogen werden kann. Als Nachverarbeitung kann ein Schieberegister mit linearer Kopplung eingesetzt werden.

Ein weiterer Zufallszahlengenerator ist beispielsweise in der EP 0 903 665 A2 offenbart. Weitere Informationen finden sich auch in der Dissertation der Technischen Universität Berlin von R. Brederlow mit dem Titel"Niederfrequentes Rauschen in einer analogen CMOS-Schaltung", aus dem Jahr 1999.

Aufgrund unterschiedlicher Hardwareimplementierungen sind die in dem Stand der Technik bekannten Zufallszahlengeneratoren unterschiedlich schnell. Alle haben jedoch gemeinsam, daß ei- ne Abtastung eines Zufallsprozesses lediglich ein Bit eines Zufallszahlen-Strings erzeugt, aus dem dann unter Verwendung irgendeiner Nachbearbeitung eine Zufallszahl mit einer be- stimmten Breite, z. B. 8 Bits, erzeugt wird.

Oftmals werden Zufallszahlen schnell benötigt. Um dies zu er- reichen, müssen Abtastschaltungen, Rauschquelle und Steueros- zillatoren für die Abtastschaltungen als schnelle Bauelemente ausgeführt sein, was in einem Kostenanstieg des Zufallszah- lengenerators und auch in einer Zunahme an Platzbedarf auf einem Chip resultieren kann. Dies ist dahingehend nachteil- haft, da der Bedarf an Chipfläche typischerweise problema- tisch ist, zumal bei typischen kryptographischen Anwendungen beispielsweise auf Smart Cards eine begrenzte maximale Chip- fläche gegeben ist, die der Schaltungsentwickler ausnutzen darf. Auf dieser Chipfläche soll nicht nur der Zufallszahlen- generator, sondern eine CPU, möglicherweise Koprozessoren und insbesondere auch der Speicher untergebracht werden. Generell wird eine große Menge an Speicher bevorzugt, was dazu führt,

daß die anderen Komponenten so klein als möglich gemacht wer- den müssen. Hochgeschwindigkeits-Implementationen für den Zu- fallszahlengenerator verbieten sich daher aufgrund des hohen Platzbedarfs und nicht zuletzt auch aufgrund des hohen Strom- verbrauchs. Der Stromverbrauch fällt insbesondere dann ins Gewicht, wenn Kontaktlos-Anwendungen betrachtet werden, d. h.

SmartCards, die keine eigene Spannungsversorgung haben, son- dern von einem HF-Feld, das z. B. von einem Terminal ausgesen- det wird, mit Leistung versorgt werden. Es ist unmittelbar einsichtig, daß hier neben der Chipfläche auch der Leistungs- verbrauch einer Schaltung von großem Interesse ist.

Die Aufgabe der vorliegenden Erfindung besteht darin, eine effizientere Vorrichtung oder ein effizienteres Verfahren zum Erzeugen einer Zufallszahl zu schaffen.

Diese Aufgabe wird durch eine Vorrichtung zum Erzeugen einer Zufallszahl nach Patentanspruch 1 oder 19 oder durch ein Ver- fahren zum Erzeugen einer Zufallszahl nach Patentanspruch 18 oder 21 gelöst.

Der vorliegenden Erfindung liegt die Erkenntnis zugrunde, daß aus einer Abtastung eines Rauschsignals eine Zufallszahl mit zwei oder mehr Stellen erzeugt werden kann, indem die sto- chastischen Eigenschaften des Zufallsprozesses ausgenutzt werden. Dies wird dadurch möglich, daß der Definitionsbereich der Wahrscheinlichkeitsdichtefunktion eines Zufallsprozesses, wie z. B. das Schrotrauschen einer Diode oder ein thermisch rauschender ohmscher Widerstand oder ein mit einem Rauschsig- nal angesteuerter steuerbarer Oszillator, in Bereiche glei- cher Wahrscheinlichkeit aufgeteilt wird, um dann je nachdem, ob ein Rauschsignalabtastwert in einem der mehreren Bereiche liegt, eine oder mehrere Stellen der Zufallszahl zu belegen.

Je nach Ausführungsbeispiel sind die Stellen der Zufallszahl voneinander abhängig und somit im binären Fall keine Zufalls- bits. Die Zahlen, die durch die unabhängigen Stellen defi- niert werden, sind jedoch Zufallszahlen mit maximaler Infor- mation. In Anwendungen, bei denen Zufallszahlen benötigt wer- den, deren Stellenanzahl gleich der Anzahl von Stellen der Zufallsbits ist, können die Zufallszahlen mit voneinander ab- hängigen Stellen ausreichen. Hierzu genügt es, den Definiti- onsbereich der Wahrscheinlichkeitsdichtefunktion in wenigs- tens zwei Bereiche aufzuteilen, um eine Zufallszahl mit zwei - voneinander abhängigen-Stellen zu erzeugen, wobei die Zu- fallszahl 01 beispielsweise ausgegeben wird, wenn die Zu- fallszahl im ersten Bereich liegt, und wobei die Zufallszahl 10 ausgegeben wird, wenn die Zahl im zweiten Bereich liegt.

In Anwendungen, bei denen voneinander unabhängige"Stellen" der Zufallszahl benötigt werden, also echte Zufallsbits im informationstheoretischen Sinn, muß jedoch der Definitionsbe- reich der Wahrscheinlichkeitsdichtefunktion in wenigstens 4 Bereiche (oder 8,16, 32,. .. Bereiche) aufgeteilt werden, um eine Zufallszahl mit voneinander unabhängigen Zufallsbits im informationstheoretischen Sinn zu erzeugen, wobei die Zu- fallszahlen 00,01, 10,11 bedeuten, daß die Zufallszahl im ersten, zweiten, dritten bzw. vierten Bereich liegt. Aus die- sen Zufallszahlen mit wenigstens zwei Stellen können somit, da die Stellen voneinander unabhängig sind, ohne weiteres längere Zufallszahlen mit mehr als zwei Stellen zusammenge- setzt werden.

Existieren also bereits zwei Bereiche der Wahrscheinlich- keitsdichtefunktionen, die die gleiche Wahrscheinlichkeit ha- ben, d. h. deren Flächen unterhalb der Wahrscheinlichkeits- dichtefunktion gleich sind, so kann bereits eine Zufallszahl mit zwei-abhängigen-Stellen, d. h. im binären Fall mit zwei Bits, erzeugt werden.

Wird die Wahrscheinlichkeitsdichtefunktion in eine größere Anzahl von Bereichen gleicher Wahrscheinlichkeit eingeteilt,' so kann eine Zufallszahl mit einer erheblich größeren Menge an Stellen pro Rauschsignalabtastung erzeugt werden, wobei die Anzahl der abhängigen Stellen immer größer als die Anzahl der unabhängigen Stellen sein wird.

Dadurch, daß aus einem Rauschsignal-Abtastvorgang eine Zu- fallszahl mit zwei oder mehr Stellen erzeugt wird, kann die Geschwindigkeit des Rauschsignalgenerators im Vergleich zu einem bekannten Rauschsignalgenerator, bei dem pro Rauschsig- nal-Abtastvorgang lediglich ein Bit erzeugt wird, verdoppelt bzw. vervielfacht werden.

Damit die erzeugten Zufallszahlen tatsächlich gleichverteilt sind, wird es bevorzugt, daß die Rauschsignal-Schwellenwerte so eingestellt werden, daß die Wahrscheinlichkeiten, daß ein Rauschsignal-Abtastwert zwischen zwei benachbarten Rauschsig- nal-Schwellenwerten liegt, für verschiedene Schwellenwerte kleiner als ein vorbestimmter Differenzwert voneinander un- terschiedlich sind und vorzugsweise gleich sind.

Hierzu wird bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung eine abschnittsweise oder dauernde A- daption der Rauschsignal-Schwellenwerte vorgenommen, um Tem- peratur-Druck-bzw. sonstige Umgebungsschwankungen der gesam- ten Schaltungen und insbesondere der Rauschsignalquelle kom- pensieren zu können.

Je nach Anwendungsfall wird es ferner bevorzugt, die Zufalls- zahl mit den zwei oder mehr-abhängigen-Stellen unter Ver- wendung eines Codierers zu codieren bzw. nachzuverarbeiten, um eine codierte Zufallszahl zu erzeugen, die-voneinander unabhängige-Zufallsbits im informationstheoretischen Sinn

hat. Durch Entziehung der Redundanz aus der Zufallszahl mit den abhängigen Stellen werden codierte Zufallszahlen erzeugt, deren Stellen voneinander unabhängig sind.

In anderen Worten wird die Codierung durchgeführt, um nicht nur hinsichtlich der insgesamten Zufallszahl an sich eine Gleichverteilung zu erreichen, sondern um auch hinsichtlich der einzelnen Stellen der Zufallszahl eine statistische Gleichverteilung zu erzeugen.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend bezugnehmend auf die beiliegenden Zeich- nungen detailliert erläutert. Es zeigen : Fig. 1 ein Prinzipblockschaltbild der erfindungsgemäßen Vorrichtung zum Erzeugen einer Zufallszahl ; Fig. 2a eine beispielhafte Wahrscheinlichkeitsdichtefunkti- on eines Rauschsignals ; Fig. 2b eine Darstellung der Aufteilung des Wertebereichs der Wahrscheinlichkeitsdichtefunktion von Fig. 2a in Bereiche mit gleicher Wahrscheinlichkeit ; Fig. 3 eine Vorrichtung zum Erzeugen einer Zufallszahl ge- mäß einem ersten Ausführungsbeispiel der vorliegen- den Erfindung mit einer Wahrheitstabelle für die Codierer-Logik ; Fig. 4 eine Vorrichtung zum Erzeugen einer Zufallszahl ge- mäß einem weiteren Ausführungsbeispiel der vorlie- genden Erfindung mit Nachführung der Rauschsignal- Schwellenwerte ;

Fig. 5 eine Vorrichtung zum Erzeugen einer Zufallszahl ge- mäß einem weiteren Ausführungsbeispiel der vorlie- genden Erfindung mit einer adaptiven Nachführung der Rauschsignal-Schwellenwerte ; Fig. 6 ein weiteres Ausführungsbeispiel der vorliegenden Erfindung mit einer adaptiven Nachführung der Rauschsignal-Schwellenwerte gemäß einem weiteren Ausführungsbeispiel der vorliegenden Erfindung ; Fig. 7 eine Vorrichtung zum Erzeugen einer Zufallszahl mit einer adaptiven Nachführung der Rauschsignal- Schwellenwerte gemäß einem weiteren Ausführungsbei- spiel der vorliegenden Erfindung ; Fig. 8 eine beispielhafte Implementation für die Einrich- tung zum Bereitstellen der Rauschsignal- Schwellenwerte mit adaptiver Anpassung ; und Fig. 9 eine alternative Implementation der Einrichtung zum Bereitstellen der Rauschsignal-Schwellenwerte mit adaptiver Nachführung.

Fig. 1 zeigt eine Rauschsignalquelle 1 mit einer bestimmten Wahrscheinlichkeitsdichtefunktion p (x), auf die bezugnehmend auf die Figuren 2a und 2b näher eingegangen wird. Ein Rausch- signal, das von der Rauschsignalquelle 1 ausgegeben wird, wird in einen Abtaster 2 eingespeist, der typischerweise eine Abtasten-und Halten-Schaltung ("Sample And Hold") und einen nachgeschalteten Quantisierer aufweist, um am Ausgang des Ab- tasters 2 einen digitalen quantisierten Wert zu einer Ein- richtung 3 zum Ausgeben einer Zufallszahl zu liefern. Die Einrichtung 3 wird ferner von einer Einrichtung 5 zum Bereit- stellen von Rauschsignal-Schwellenwerten angesteuert. Die Einrichtung 5 zum Bereitstellen von Rauschsignal-

Schwellenwerten ist ausgebildet, um zumindest drei Rauschsig- nal-Schwellenwerte zu liefern, wobei die zumindest drei Rauschsignal-Schwellenwerte so gewählt sind, daß eine erste Wahrscheinlichkeit, daß ein vom Abtaster 2 gelieferter Rauschsignal-Abtastwert zwischen dem ersten und dem zweiten Rauschsignal-Schwellenwert liegt, und daß eine zweite Wahr- scheinlichkeit, daß der Rauschsignal-Abtastwert zwischen dem zweiten und dem dritten Rauschsignal-Schwellenwert liegt, sich weniger als einen vorbestimmten Differenzwert unter- scheiden oder gleich sind.

Die Einrichtung zum Ausgeben der Zufallszahl mit zumindest zwei Stellen in Abhängigkeit von dem Rauschsignal-Abtastwert ist ausgebildet, um dann, falls ein Rauschsignal-Abtastwert zwischen dem ersten und dem zweiten Rauschsignal- Schwellenwert liegt, eine erste Stelle der Zufallszahl mit einem logischen Zustand zu belegen, der sich von einem logi- schen Zustand unterscheidet, mit dem eine zweite Stelle der Zufallszahl belegt wird, wenn der Rauschsignal-Abtastwert zwischen dem zweiten und dem dritten Rauschsignal- Schwellenwert liegt. Bei Verwendung von drei Rauschsignal- Schwellenwerten ergeben sich somit zwei Bereiche, in denen der Rauschsignal-Abtastwert liegen kann, nämlich ein erster Bereich zwischen dem ersten Rauschsignal-Schwellenwert und dem zweiten Rauschsignal-Schwellenwert und ein zweiter Be- reich zwischen dem zweiten Rauschsignal-Schwellenwert und dem dritten Rauschsignal-Schwellenwert. Liegt der Rauschsignal- Abtastwert in dem ersten Bereich, so wird eine erste Stelle der Zufallszahl z. B. mit einer logischen"1"belegt, und wird eine zweite-von der ersten Stelle abhängige Stelle der Zu- fallszahl mit einer logischen"0"belegt, da der Rauschsig- nal-Abtastwert nicht in dem zweiten Bereich liegt, für den die zweite Stelle der Zufallszahl steht. Jeder Abtastvorgang, der durch den Abtaster 2 mit dem von der Rauschsignalquelle 1 ausgegebenen Rauschsignal durchgeführt wird, führt somit zu

einer 2-Bit-Zufallszahl, wobei beide Bits der Zufallszahl je- doch aufgrund der enthaltenen Redundanz voneinander abhängig sind.

Im nachfolgenden wird bezugnehmend auf die Figuren 2a und 2b auf die Natur der Rauschsignalquelle 1 von Fig. 1 eingegan- gen. Ausgegangen wird davon, daß die Rauschsignalquelle ein stochastisches Signal Y mit einer kontinuierlichen Dichte- funktion p (x) liefert. Die Dichtefunktion p (x) wird nun er- findungsgemäß in zumindest 2'Intervalle oder Bereiche unter- teilt, wobei n eine ganze Zahl ist und größer oder gleich 1 ist. Für n = 1 können Zufallszahlen mit zwei oder mehr Stel- len erhalten werden, wobei die Stellen jedoch voneinander ab- hängig sind.

Für vier oder mehr Bereiche, also n = 2, 3, 4,..., können Zufallszahlen mit voneinander unabhängigen Stellen erzeugt werden, wobei jeder Bitkombination der unabhängigen Stellen genau ein Bereich zugeordnet ist. Für 4 Bereiche hat die Zu- fallszahl somit 2 echte Zufallsbits. Für 8 Bereiche können dann 3 echte Zufallsbits pro Abtastung erhalten werden. Für 16 Bereiche können 4 echte Zufallsbits pro Abtastung erhalten werden, usw.

Diese Unterteilung findet derart statt, daß die von den Un- terteilungspunkten xi eingeschlossenen Flächen unter dem Gra- phen p (x) gleich groß sind. Eine solche Aufteilung für die beispielhafte Wahrscheinlichkeitsdichtefunktion p (x) von Fig.

2a ist in Fig. 2b gezeigt. Die Flächen unter der Wahrschein- lichkeitsdichtefunktion p (x) zwischen zwei benachbarten Rauschsignal-Schwellenwerten xi und xi+1 sind vorzugsweise i- dentisch, d. h. Ai = Ai+1 für alle i. Die Flächen unter der Wahrscheinlichkeitsdichtefunktion p (x) zwischen zwei Rausch- signal-Schwellenwerten wird durch Integrieren der Wahrschein- lichkeitsdichtefunktion p (x) von einem Rauschsignal-

Schwellenwert xi zum benachbarten Rauschsignal-Schwellenwert xi, 1 erhalten. Die Rauschsignal-Schwellenwerte sind somit der- art zu bestimmen, daß die Flächengleichheit der Bereiche, die von zwei benachbarten Rauschsignal-Schwellenwerten einge- schlossen wird, gegeben ist. Die Unterteilungspunkte bzw.

Rauschsignal-Schwellenwerte werden auch als (i/2n)-Quantile bezeichnet. Definiert man nun eine Zufallsvariable Y, indem man jedem Intervall zwischen zwei Unterteilungspunkten xi und xi+ 1 eine Zahl i zuordnet, so erhält man eine Gleichvertei- lung auf {0,... 2n-1}. Dies sieht gleichungsmäßig folgenderma- ßen aus : P (# = i) = P(xi # Y # xi+1) = 1/2n für alle i # {0,...,2n-1} (1) Mit Hilfe dieses Verfahrens erhält man aus jedem Signal eine Realisierung auf der diskreten Menge {0,... 2n-1}. Da diese a- ber eine n Bit lange Binärdarstellung besitzt, liefert jede einzelne Messung n Bits. Somit ist die Methode n-mal schnel- ler als eine direkte Erzeugung von Bits.

Weiterhin sei angemerkt, daß es keine theoretische Grenze für die Größe der Zahl n gibt. Sie wird in der Praxis durch Meß- genauigkeit, Aufwand und Auflösung des physikalischen Systems begrenzt. Darüber hinaus funktioniert das erfindungsgemäße Konzept für jedes kontinuierliche stochastische Signal unab- hängig von der Gestalt der zugehörigen Dichtefunktion.

Ein Vorteil der vorliegenden Erfindung besteht darin, daß die Erzeugung der Bits um den Faktor n schneller als eine bitwei- se Erzeugung ist. Für n gibt es keine theoretische Grenze.

Ein weiterer Vorteil der vorliegenden Erfindung besteht dar- in, daß das Verfahren unabhängig von der konkreten Gestalt der Dichtefunktion des stochastischen Signals anwendbar ist.

Ein weiterer Vorteil der vorliegenden Erfindung besteht dar- in, daß die benötigten Unterteilungspunkte bzw. Rauschsignal- Schwellenwerte entweder a priori bestimmt werden, d. h. von der Einrichtung zum Bereitstellen von Rauschsignal- Schwellenwerten bereitgestellt werden, oder mit Hilfe adapti- ver Verfahren an zeitliche Schwankungen der Verteilungsfunk- tion angepaßt werden können.

Die Rauschsignalquelle kann eine der oben ausgeführten Formen oder irgendeine Form sein, die ein stochastisches Signal mit einer Wahrscheinlichkeitsdichtefunktion liefert. Der Abtaster kann einen beliebigen Aufbau haben, solange er ausgangsseitig ein Signal mit einer solchen Genauigkeit liefert, daß ent- schieden werden kann, ob der Rauschsignal-Abtastwert, d. h. ein Ausgangswert der Rauschsignalquelle zu einem beliebigen Abtastzeitpunkt, zwischen zwei Rauschsignal-Schwellenwerten liegt oder nicht.

Wie es bereits ausgeführt worden ist, reichen bereits drei Rauschsignal-Schwellenwerte aus, um aus einem Rauschsignal- Abtastvorgang eine 2-Bit-Zufallszahl (mit voneinander abhän- gigen Stellen) zu erzeugen. Am Beispiel der Fig. 2b wäre der erste Rauschsignal-Abtastwert der Wert xo, wäre der zweite Rauschsignal-Abtastwert der Wert X4 und wäre der dritte Rauschsignal-Abtastwert der Wert x8 Alternativ können auch drei benachbarte Rauschsignal-Schwellenwerte verwendet wer- den, die nicht den Anfangspunkt xooder den Endpunkt x8 umfas- sen, wie z. B. die drei Rauschsignal-Schwellenwerte X2, X3 und X4, wobei jedoch hier nur Rauschsignal-Abtastwerte zu Zu- fallszahlen führen, die zwischen Xs und X4 liegen. Wieder al- ternativ können auch Bereiche verwendet werden, die nicht zu- sammenhängend sind, so daß ein ungültiger Bereich existiert, der zu einem gültigen Bereich benachbart ist. Fällt ein Ab- tastwert in einen solchen ungültigen Bereich, so wird für

diesen Abtastwert keine Zufallszahl ausgegeben. Ein ungülti- ger Bereich könnte beispielsweise dazu verwendet werden, eine problematische Stelle in der Wahrscheinlichkeitsdichtefunkti- on einer physikalischen Rauschquelle"auszublenden".

Es sei darauf hingewiesen, daß bei der Verwendung von drei Rauschsignal-Schwellenwerten die Information dahingehend, ob der Rauschsignal-Abtastwert in dem einen Bereich, d. h. zwi- schen den unteren beiden Rauschsignal-Schwellenwerten ist, oder in dem anderen Bereich, also zwischen den oberen Rausch- signal-Schwellenwerten ist, erfaßt wird. Die zwei Stellen sind zwar voneinander abhängig aufgrund der Redundanz in der 2-Bit-Zufallszahl. Dennoch hat eine Folge solcher z. B. 2- Bit-Zufallszahlen eine stochastische Verteilung.

Bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung wird es bevorzugt, mit mehr als drei Rauschsignal- Schwellenwerten zu arbeiten. Hierzu wird auf Fig. 3 Bezug ge- nommen. Fig. 3 zeigt eine detailliertere Implementation der Einrichtung 3 zum Ausgeben einer Zufallszahl. Die Einrichtung 3 zum Ausgeben einer Zufallszahl umfaßt verschiedene Schwell- wertentscheider 3a, 3b, 3c, die bei dem in Fig. 3 gezeigten bevorzugten Ausführungsbeispiel den untersten Schwellenwert xo von Fig. 2b und den obersten Schwellenwert x8 von Fig. 2b nicht umfassen, sondern lediglich die Schwellenwerte zwischen dem untersten und dem obersten Schwellenwert. Die Schwellwer- tentscheider sind ausgebildet, um ein logisch hohes Signal, wie z. B. ein"1"-Bit auszugeben, wenn ein von dem A/D-Wandler 2 gelieferter Rauschsignal-Abtastwert größer als die Schwelle ist, und um eine logische"0"auszugeben, wenn der Rauschsig- nal-Abtastwert kleiner als der Rauschsignal-Schwellenwert ist, der von der Einrichtung 5 entweder fest eingespeichert bereitgestellt wird, oder, wie es bezugnehmend auf die Figu- ren 4,5, 6 und 7 erläutert wird, adaptiv bereitgestellt wird.

Ist ein Rauschsignal-Abtastwert beispielsweise in dem Bereich zwischen xo von Fig. 2b und xl von Fig. 2b, so werden alle Schwellwertgatter eine logische"0"ausgeben, da der Rausch- signal-Abtastwert keines der Schwellwertgatter von Fig. 3 "auslöst", was mit anderen Worten bedeutet, daß der Rausch- signal-Abtastwert keinen der Rauschsignal-Schwellenwerte ü- berschreitet. Dieser Fall entspricht einer ersten Zeile 31 der in Fig. 3 dargestellten Wahrheitstabelle für eine Codier- logik 4 auf die nachfolgend eingegangen wird. Liegt der Rauschsignal-Abtastwert vom A/D-Wandler 2 dagegen zwischen dem Rauschsignal-Schwellenwert Xi und dem Rauschsignal- Schwellenwert X2, so wird das erste Gatter 3a eine logische "1"ausgeben, während all die anderen Gatter eine logische "0"ausgeben werden. Dies entspricht der zweiten Zeile 32 der Wahrheitstabelle von Fig. 3. Liegt der Rauschsignal- Abtastwert dagegen oberhalb des höchsten Rauschsignal- Schwellenwerts x-7, so würde dies der achten Zeile 38 der Wahr- heitstabelle entsprechen, bei der sämtliche Schwellwertgatter 3a, 3b und 3c eine logische"1"ausgeben.

In dem linken Bereich der Wahrheitstabelle, also in der Schaltung von Fig. 3 nach den Schwellwertentscheidern, befin- den sich Zufallszahlen mit voneinander abhängigen Stellen, während im rechten Bereich Zufallszahlen mit voneinander un- abhängigen Stellen zu finden sind, die echte Zufallsbits im infomationstheoretischen Sinn sind. Diese echten Zufallsbits können verwendet werden, um unter Verwendung vieler Rausch- signal-Abtastwerte beispielsweise eine 512-Bit-Zufallszahl zu erzeugen, die bei der Schlüsselerzeugung des z. B. RSA- Algorithmus benötigt wird. Hierzu wären bei 32 Bereichen (al- so fünf Zufallsbits pro Abtastung) lediglich 103 Abtastungen erforderlich, und zwar im Gegensatz von 512 Abtastungen, wenn pro Abtastung genau ein Zufallsbit erzeugt wird.

Es sei darauf hingewiesen, daß bei dem in Fig. 3 gezeigten Ausführungsbeispiel, um die Zufallszahlen zu erzeugen, Schwellwertgatter verwendet werden, die der Tatsache, ob ein' Rauschsignal-Abtastwert oberhalb oder unterhalb des Schwel- lenwertes liegt, d. h. im ersten oder im zweiten Bereich liegt, lediglich ein Bit zuweisen. Um in so einem Fall, bei der Verwendung von Schwellwertgattern, eine Zufallszahl mit zumindest zwei-abhängigen-Stellen am Ausgang der Einrich- tung 3 zu erzeugen, müssen zumindest zwei Schwellwertgatter verwendet werden, d. h. insgesamt vier Rauschsignal- Schwellenwerte, da zusätzlich der unterste Rauschsignal- Schwellenwert xo von Fig. 2b und der oberste Rauschsignal- Schwellenwert x8 von Fig. 2b verwendet werden müßte. In die- sem Fall, bei dem nur zwei Rauschsignal-Schwellenwerte xi, X2 verwendet werden, würde der Rauschsignal-Schwellenwert xi zwischen den Rauschsignal-Schwellenwerten x2 und X3 von Fig.

2b liegen, und würde der zweite Rauschsignal-Schwellenwert x2 zwischen den Rauschsignal-Schwellenwerten x5 und x6 von Fig.

2b liegen, und zwar ebenfalls unter der vorgenannten Voraus- setzung, daß die Flächen zwischen den Rauschsignal- Schwellenwerten und den entsprechenden Rand-Werten xo und x8 gleich sind und ebenfalls gleich der Flächen zwischen den beiden Rauschsignal-Schwellenwerten, die die Gatter 3a, 3b bestimmen, sind. Zur Erzeugung von echten Zufallsbits würden dagegen mindestens drei Schwellwertgatter benötigt werden, die vier Bereiche in der Wahrscheinlichkeitsdichtefunktion voneinander unterscheiden können.

Die Rauschsignalquelle 1 von Fig. 3 erzeugt somit ein sto- chastisches Signal, wobei, wie es ausgeführt worden ist, ein elektronisches Bauelement, wie z. B. ein Widerstand oder ein Transistor eingesetzt werden kann.

Dieses analoge Signal wird mittels des A/D-Wandlers 2 in 2j Stufen diskretisiert und dann, wie es ausgeführt worden ist,

mit Hilfe der Schwellwertgatter verarbeitet. Aus praktischen Gründen werden, wie es ausgeführt worden ist, nur die inneren Schwellenwerte benutzt, d. h. die Schwellenwerte für die mini- malen und die maximalen Amplituden werden nicht benötigt. Es sei darauf hingewiesen, daß die Funktionalität der Schwellen- werte mit dem A/D-Wandler 2 in einer einzigen Komponente in- tegriert werden kann.

Abhängig von der Größe des abgetasteten Rauschwerts der Rauschquelle ergibt sich an den Ausgängen der Schwellwertgat- ter eine Zufallszahl, die ein 2n-1 dimensionaler binärer Vek- tor ist. Bei bevorzugten Ausführungsbeispielen der vorliegen- den Erfindung wird es bevorzugt, diesen redundanten Vektor (linke Hälfte der Wahrheitstabelle in Fig. 3) zu codieren und auf einen n-dimensionalen Ausgangsvektor abzubilden. Hierzu wird eine Logikeinrichtung 4 verwendet, die prinzipiell als Codierer funktioniert. Die Logikeinrichtung 4 hat bei dem in Fig. 3 gezeigten bevorzugten Ausführungsbeispiel die in Fig.

3 dargestellte Wahrheitstabelle, um eine 7-Bit-Zufallszahl mit abhängigen Stellen in eine 3-Bit-codierte Zufallszahl mit echten Zufallsbits abzubilden bzw. umzucodieren. Am Ausgang der Logik 4 liegt somit ein Vektor von Zufallsbits an, der eine codierte Zufallszahl darstellt.

Zur Umsetzung der am Eingang der Logik 4 vorliegenden Zu- fallszahlen mit abhängigen Stellen wird es oftmals bevorzugt, die Redundanz-Entziehung durch den Codierer 4 zu bewirken, der in Fig. 2 und in den weiteren Figuren auch mit"Logik" bezeichnet ist, um die echten Zufallsbits zu erhalten.

Es sei darauf hingewiesen, daß die Funktion der Schwellwert- gatter und die Funktion der Logikeinrichtung 4 auch in einem einzigen Bauteil zusammengefaßt werden kann.

Alternativ muß nicht unbedingt eine Schwellwertgatterent- scheidung und nachfolgende Codierung vorgenommen werden. Die Zuordnung von zwei oder mehreren Zufallsbits zu einem Bereich kann erfindungsgemäß beliebig erfolgen, solange die n Bits der binären Zufallszahl derart bestimmt werden, daß jede Bit- kombination der n Bits der binären Zufallszahl eindeutig ei- nem der 2n Bereiche zugeordnet ist.

Die logische Funktion, die durch den Codierer 4 implementiert werden muß, kann beispielsweise durch eine ROM-Tabelle darge- stellt sein, die die Wahrheitstabelle von Fig. 3 aufweist.

Werden die Schwellenwerte xi so gewählt, daß die xi den für die Gleichverteilung erforderlichen (i/2n)-Quantilen entspre- chen, ist die Zuordnung der 2n-1 binären Ausgänge der Schwellwertgatter zum n-dimensionalen Ausgangsvektor der lo- gischen Funktion beliebig, aber vorzugsweise bijektiv.

Eine logische Funktion mit den notwendigen Eigenschaften ist beispielsweise durch einen Addierer gegeben. Gilt xi kleiner als xi+1, dann kann die logische Funktion beispielsweise auch zu einem sogenannten Prioritätscodierer implementiert werden.

Aufgrund der Redundanz im Ausgangsvektor der Schwellwertgat- ter ist eine Reihe weiterer logischer Funktionen möglich.

Wählt man beispielsweise für die Ausgangsbits yo,.., yin-l fol- gende Funktion : dann ergibt sich ebenfalls eine geeignete eindeutige Funkti- on. Hierbei bezeichnet @ die Addition modulo 2 und Jcq den binären Ausgang des Schwellwertgatters mit dem Schwellenwert xi.

Für n = 3 gilt dann beispielsweise : Y2 = #3 y1 = #5 # #1 0 - #6 # #4 # #2 # #0 (3) Diese Funktion entspricht der in Fig. 3 gezeigten Wahrheits- tabelle.

Es sei darauf hingewiesen, daß für die Güte der Gleichvertei- lung der Zufallszahlen die geeignete Wahl der Schwellwertwer- te xi bedeutsam ist. Ist die Dichtefunktion p (x) von Fig. 2a des stochastischen Signals zeitkonstant und von vorneherein hinreichend genau bekannt, können diese Werte a priori ausge- rechnet und eingestellt werden. Ist jedoch die Dichtefunktion p unbekannt oder ändert sie sich mit der Zeit, wird es bevor- zugt, die Schwellenwerte nachzuführen, d. h. zu adaptieren.

Eine Adaption der Schwellenwerte ist auch dann sinnvoll, wenn Implementierungsungenauigkeiten, beispielsweise des Ana- log/Digital-Wandlers auszugleichen sind. Wie es nachfolgend dargelegt wird, ist auch dann, wenn die Wahrscheinlichkeits- dichtefunktion p (x) zwar zeitkonstant ist, jedoch a priori nicht bekannt ist, eine automatische Ermittlung der optimalen Rauschsignal-Schwellwerte möglich. In diesem Fall muß die Einrichtung 5 zum Berechnen der Rauschsignal-Schwellenwerte auch bei unbekannter, jedoch zeitkonstanter Wahrscheinlich- keitsdichteverteilung die Rauschsignal-Schwellenwerte zu- nächst ermitteln, um dann nach einer Anzahl von Trainings- Durchläufen optimal eingestellte Schwellenwerte bereitstellen zu können.

Die a priori Auswahl der Schwellenwerte xi findet bei einer analytisch oder numerisch bekannten Verteilungsfunktion, wel- che beispielsweise durch Messung erhalten worden ist, folgen- dermaßen statt. Sei F eine gegebene Verteilungsfunktion der Zufallsvariable Y mit stetiger Dichtefunktion p, so gilt fol- gender Zusammenhang :

In diesem Fall sind die Unterteilungspunkte für eine Gleich- verteilung auf {0,..., 2n-1} wählen : Definiert man eine neue Zufallsvariable Y wie oben beschrie- ben, so ist diese auf {0,... 2n-1} gleichverteilt.

Im nachfolgenden wird anhand der Figuren 4,5, 6 und 7 auf verschiedene Möglichkeiten der adaptiven Einstellung der Rauschsignal-Schwellenwerte der Einrichtung 3 zum Ausgeben der Zufallszahlen mit zumindest zwei Stellen eingegangen.

Bei dem in Fig. 4 gezeigten Ausführungsbeispiel werden zum Nachführen der Rauschsignal-Schwellenwerte diskretisierte Ausgangswerte des A/D-Wandlers ausgewertet, wie es durch ei- nen Pfeil 40 dargestellt ist. Alternativ können auch, wie es in Fig. 5 dargestellt ist, direkt die Rauschsignal-Werte am Ausgang der Rauschquelle betrachtet und ausgewertet werden, wie es durch einen Pfeil 50 dargestellt ist. Alternativ kön- nen auch die Zufallszahlen am Ausgang der Einrichtung 3 ver- wendet werden, wie es durch Zeile 60 in Fig. 6 dargestellt ist. Alternativ können auch die codierten Zufallszahlen am Ausgang der Logikeinrichtung 4 betrachtet werden, wie es in Fig. 7 durch einen Pfeil 70 dargestellt ist. Alternativ kön- nen auch beliebige Kombinationen der in den Figuren 4,5, 6 und 7 dargestellten Möglichkeiten eingesetzt werden. Hierzu werden entweder mehrere beobachtete Werte in die Einrichtung

5 zum Bereitstellen der Rauschsignal-Schwellenwerte eingele- sen und verarbeitet. Alternativ kann auch eine Nachführung der Rauschsignal-Schwellenwerte erreicht werden, wenn nur ein aktuell beobachteter Wert eingelesen und verarbeitet wird.

Die Einrichtung 5 bildet dann eine Schätzung für die optima- len Schwellenwerte xi und gibt diese, wie es aus den Figuren ersichtlich ist, an die Schwellwertgatter weiter.

Eine Möglichkeit zur Approximation der i/(2n)-Quantile, d. h. der Rauschsignal-Schwellenwerte, der Verteilung ergibt sich durch Ermittlung der statistischen i/(2n)-Quantile der Mes- sungen. Dies kann beispielsweise dadurch geschehen, daß, wie es anhand von Fig. 8 ersichtlich ist, die Rauschdaten in auf- steigender Reihenfolge sortiert gespeichert werden. Anschlie- ßend kann durch Abzählen das entsprechende Quantil gefunden werden. Fig. 8 zeigt beispielsweise 1024 Speichereinheiten 80, die in aufsteigender Reihenfolge angeordnet sind. Zur An- wendung des in Fig. 8 gezeigten Konzepts müssen zunächst 1024 Rauschsignal-Abtastwerte, Zufallszahlen etc. erfaßt werden und in die 1024 Speichereinheiten nach ihrer Größe einsor- tiert werden, und zwar in aufsteigender Reihenfolge. Wenn die 1024 Speichereinheiten belegt sind, steht beispielsweise in der Speicherzelle a128 das 1/8-Quantil, d. h. der Rauschsignal- Schwellenwert x von Fig. 2b, während in der Speicherzelle a896 das 7/8-Quantil steht, also der Rauschsignal- Schwellenwert X7 von Fig. 2b. Ein Vorteil des in Fig. 8 ge- zeigten Konzepts besteht darin, daß es dann, wenn die 1024 Speichereinheiten erst einmal gefüllt sind, zu einer unmit- telbaren Nachführung verwendet werden kann. Werden 1024 Rauschsignalwerte erfaßt und einsortiert, und wird dann der 1025ste Wert erhalten, so muß dieser in eine Speichereinheit 80 einsortiert werden, so daß eine nächstniedrigere Spei- chereinheit einen kleineren Wert hat und eine nächsthöhere Speichereinheit einen größeren Wert hat. Dazu wird der als erstes eingefügte Wert, also der älteste Wert, aussortiert

und die Speicherelementesequenz unter Verwendung des neuen Werts umsortiert.

Landet nun in einer Speichereinheit, die ein Quantil be- stimmt, ein anderer Wert als vorher, so wird der entsprechen- de Rauschsignal-Schwellenwert in dem entsprechenden Schwell- wertgatter der Einrichtung 3 auf den neu einsortierten Wert verändert. Wesentlich an dem in dem Fig. 8 beschriebenen Kon- zept ist, daß ein schneller Einsortieralgorithmus verwendet wird.

Nachfolgend wird als alternative Option ein adaptives Verfah- ren vorgestellt, bei dem eine Schätzung für die Schwellenwer- te durch Beobachtung der erzeugten Zufallszahlen erhalten wird. Dazu sei ein Intervall [a, b] gegeben, für welches ein beliebiges, dann jedoch festes y-Quantil aus der Menge [0, 1] zu bestimmen ist. X (l) aus der Menge [a, b] bezeichnet den im 1-ten Schritt gefundenen Schwellenwert, und Rc (1) bezeichnet eine Menge von Realisierungen des Zufallsprozesses der Mäch- tigkeit c, wobei c eine natürliche Zahl ist : Die beiden folgenden Gleichungen geben die Anzahl der Elemen- te aus Rc (1) an, die größer bzw. kleiner als der Schwellen- wert x (1) sind : und B (l) : = {i # Rc (l) #i>x(l)}# Der Algorithmus hat folgenden Verlauf, wobei c fest gewählt ist : 1 : Wähle x (1) e [a, b] beliebig 2 : Wähle a E R, a > 0 beliebig 3 : 1 <-0

4 : wiederhole 5 : 1 +-1 + 1 6 : Rc (1) # c Realisierungen des Zufallsprozesses 7 A (l) <-j {i # Rc(1) # i # x (1) }# 8 : B (1) <- {i e RC (1) Ii > x (1)}# 9 : x(1+1) # x(1) + (y B (1) - (1 - γ) A (l))/ß (1) 10 : bis Adaption hinreichend gut Der Faktor ß (1) kann zur Beschleunigung der Konvergenz ge- wählt werden. Sind die Rc (1) unabhängig und ß (l) = l, so läßt sich die Konvergenz gegen das y-Quantil mit Wahrscheinlich- keit 1 mathematisch nachweisen. Die Abbruchbedingung in Zeile 10 kann z. B. durch mehrfachen Vergleich von A (l) und B (1) realisiert werden oder durch eine feste Anzahl von Iterati- onszyklen ersetzt werden. Der Algorithmus läßt sich für alle benötigten Quantile (z. B. y = i/2n, i = 1,..., 2n-1) simultan verwenden.

Nach einer festen Anzahl von Iterationszyklen empfiehlt es sich ferner, die Schrittvariable 1 wieder auf einen kleineren Wert zurückzusetzen, damit wieder eine neue Korrektur bzw.

Adaption stattfindet. Wie es bereits ausgeführt worden ist, läßt sich der Algorithmus für alle benötigten Quantile (bei- spielsweise y. in i = 1,..., 2n-1) simultan verwenden.

Der beschriebene Algorithmus führt ferner auch bei unbekann- ter Wahrscheinlichkeitsdichteverteilung p (x) zu einer automa- tischen Einstellung der Rauschsignal-Schwellenwerte.

Dies gilt ferner auch für das in Fig. 8 beschriebene Konzept, wobei auch hier nach einer bestimmten Trainings-Phase, in der Zufallszahlen nicht ausgegeben werden sollten, die Rauschsig- nal-Schwellenwerte wie benötigt automatisch eingestellt wor- den sind.

Bei einer Aktivierung des Algorithmus während der Erzeugung der Zufallszahlen ist der Fall c = 1 und im Hinblick auf eine Implementierung besonders günstig.

1 : <-l + 1 2 : i +-eine Realisierung des Zufallsprozesses 3 : falls i > x (1) dann 4 x (l+l) <-x (l) + y/ß (1) (Inkrementieren) 5 : sonst 6 : x(1+1) # x(1) - (1-γ)/ß(1) (Dekrementieren) 7 : end falls Im letzteren Szenario ist der Fall ß (1) = 2j-r, wobei r eine natürliche Zahl oder 0 ist und 2i Quantisierungsstufen im A/D-Wandler des Abtasters gegeben sind, im Hinblick auf eine Implementierung besonders interessant.

Betrachtet man beispielsweise das 1/4-Quantil, so lautet die Schleife des Algorithmus folgendermaßen : 1: 1 # 1 + 1 2 : i +-eine Realisierung des Zufallsprozesses 3 : falls i > x (1) dann 4 : x(1+1) # x(1) + 2r-i-2 (Inkrementieren) 5 : sonst 6 : x(1+1) # x(1) - 3#2r-j-2 (Dekrementieren) 7 : end falls Betrachtet man weiter das 1/2-Quantil, so lautet der Algo- rithmus : l : l <-1+1 2 : i +-eine Realisierung des Zufallsprozesses

3 : falls i > x (1) dann 4 : x (1+1) ~ x (1) + 2r-i-1 (Inkrementieren) 5 : sonst 6 : x (1+1) # x(1) - 2r-j-1 (Dekrementieren) 7 : end falls Betrachtet man schließlich das 3/4-Quantil, so lautet die Schleife im Algorithmus : 1 : 1 v 1 + 1 2 : i # eine Realisierung des Zufallsprozesses 3 : falls i > x (1) dann 4 : x(1+1) # x(1) + 3#2r-j-2 (Inkrementieren) 5 : sonst 6 : x(1+1) # x(1) - 2r-j-2 (Dekrementieren) 7 : end falls Im nachfolgenden wird auf Fig. 9 Bezug genommen, um eine schaltungsmäßige Implementation des vereinfachten Algorithmus beispielhaft für das mittlere Quantil, d. h. das 1/2-Quantil x4 aus Fig. 2b, und den Fall n = 2, r = 1 zu erläutern. Die Einrichtung zum Bereitstellen des Rauschsignal-Schwellenwerts umfaßt ein Register 90, einen Addierer 91, ein Rechenwerk 92 sowie zwei Eingänge 93 und 94, von denen der eine den Wert +2-i zum Addierer 92 liefert, während der andere den Wert "-2-j" zu dem Addierer 92 liefert. Der gesamte Schaltungs- block für den mittleren Rauschsignal-Schwellenwert X4 ist in Fig. 9 mit dem Bezugszeichen 6 bezeichnet. Insbesondere wird der aktuell verwendete Schwellenwert in dem Register 90 gehalten und je nach Zustand der aktuellen Schwellwertent- scheidung inkrementiert oder dekrementiert. Der gesamte Block 6 wird durch eine Enable-Leitung"enl"95 durch eine Kontrol- logik 7 dann aktiviert, wenn der entsprechende Schwellenwert X4 adaptiert werden soll. Dieselben Blöcke 8,9 existieren in

analoger Ausführung für die beiden anderen Schwellenwerte.

Für deren Aktivierung ist jedoch Voraussetzung, daß sich der aktuelle Rauschwert in dem Intervall]-oo, xl [ bzw. ] xi, +oo [ befindet. Aus diesem Grund wird der Kontrollogik zusätzlich noch das Ausgangssignal des Schwellwertgatters mit dem Schwellenwert X4 zugeführt, wie es aus der Fig. 9 ersichtlich ist. Es sei darauf hingewiesen, daß andere Quantile als das mittlere Quantil durch Verwenden des jeweiligen prozentualen y-Werts in Zeile 3 des obigen Algorithmus ebenfalls ermittelt werden können.

Es sei darauf hingewiesen, daß beliebige Alternativen zum Ü- berwachen der Statistik der entsprechenden Zufallszahlen und zum Nachstellen der entsprechenden Rauschsignal- Schwellenwerte implementierbar sind.

Das in Fig. 9 bezeichnete Ausführungsbeispiel führt eine A- daption pro neu erfaßtem Wert durch, die schaltungstechnisch günstig zu realisieren ist. Dies ist der Fall, da das Rechen- werk 92 lediglich als einfacher Komparator auszuführen ist, um die Zeile 3 des letztgenannten Algorithmus zu implementie- ren, und um dann eine Inkrementierung bzw. Dekrementierung vorzugsweise nach einer Gewichtung mit einer Iterationsvari- ablen, welche in Fig. 9 nicht gezeigt ist, durchzuführen. So- mit wird aus dem alten Rauschsignal-Schwellenwert X4 unter Verwendung des Addierers 91 der neuen Rauschsignal- Schwellenwert berechnet.

Bezugszeichenliste 1 Rauschsignalquelle 2 Abtaster 3 Einrichtung zum Ausgeben der Zufallszahl 3a Erster Rauschsignal-Schwellenwert 3b Zweiter Rauschsignal-Schwellenwert 3c Siebter Rauschsignal-Schwellenwert 4 Codierer 5 Einrichtung zum Bereitstellen von Rauschsignal- Schwellenwerten 6 Adaptierblock für eine Rauschsignal-Schwellenwert 7 Steuerlogik 8 Adaptierblock für einen weiteren Rauschsignal- Schwellenwert 9 Adaptierblock für noch einen weiteren Rauschsig- nal-Schwellenwert 31 Erste Zeile der Wahrheitstabelle des Codierers 32 Zweite Zeile der Wahrheitstabelle des Codierers 38 Achte Zeile der Wahrheitstabelle des Codierers 40 Überwachen der Rauschsignal-Abtastwerte 50 Überwachen der Rauschsignalwerte vor der Abtastung 60 Überwachen der Zufallszahlen 70 Überwachen der codierten Zufallszahlen 80 Speichereinheiten 90 Register 91 Addierer 92 Rechenwerk 93 Positiver Inkrementierungswert 94 Negativer Inkrementierungswert 95 Freigabeleitung