Title of Invention

"A RANDOM NUMBER GENERATOR"

Abstract

The invention relates to a method for generating random numbers in which oscillating digital output signals (A1, A2, ..., AL) of unequal or equal periodicity are generated by at least two ring oscillators (32, 33, 34), an external parity signal (PS) representing a logical state ("0," "1") being generated when an odd number of the output signals (A1, A2, ..., AL) take on a specified logical state ("1")- According to the invention, the external parity signal (PS) is fed back to an external parity input (36, 37, 38) of each of the respective ring oscillators (32, 33, 34). The Invention further relates to a random number generator having at least two ring oscillators (32, 33, 34), made up in particular of independently free-running inverter chains with feedback having an odd number (K) of series-connected inverters (inv1,2, inv2,1, inv3,1, ..., invi,j, ...., invL,KL) that generate oscillating digital output signals (A1, A2, ..., AL) of unequal or equal periodicity, and having first parity signal generating means (XOR) that generate an external parity signal (PS) representing a logical state ("0,"1") when an odd number of the output signals (A1, A2,..., AL) take on a specified logical state ("1")- According to the invention, there are feedback means (xor1, xor2, xor3, xor4, ..., xorL) that feed back the external parity signal (PS) to an external parity input (36, 37, 38) of each of the respective ring oscillators (32, 33, 34). In this invention the cooperation of chaotic dynamics (feedback of the parity signal) and true randomness (jitter due to thermal noise) in digital circuits, a novel theoretical principle for generating random numbers, has been made into an efficient practical solution.

Full Text

The present invention relates to a method for generating random numbers. Specification The invention relates to a random generator according to the preamble of Claim 14 and to a method for generating random numbers according to the preamble of Claim 1. Random number generators (RNGs) are used for automatically generating random binary or multivalued numbers (random numbers). Random number generators are needed in many application fields. These include for example: — Cryptographic applications — Stochastic simulations — Testing of software and hardware — Computer games In what follows, cryptographic applications of random number generators will be considered exclusively. These applications include, by way of example: — For authentication: - Challenge-response protocols - Zero-knowledge proofs — For key sharing protocols: - Diffie-Hellman methods — For key generation: - Session keys for symmetrical encryption methods - Key generation for asymmetric encryption methods (public-key methods) - Generation of binary noise (one-time pad, McEleice public-key method) - Parameter generation for public-key methods (e.g., generating random prime numbers) — For other cryptographic applications: - Password generation - Initial values (seeds) for deterministic random number generators (pseudorandom number generators) - Padding of cleartext blocks - Secure erasure of storage media (by multiple overwriting with random bit patterns) In general there are two main kinds of generators, deterministic (pseudorandom number generators or PRNGs) and physical random number generators (true random number generators or TRNGs). Deterministic generators are algorithmic procedures that derive, from a randomly chosen initial value (IV), a much longer string of numbers that appears random. Naturally, this string per se cannot be truly random because of the deterministic character of the generating method. In order that actually random strings of numbers can be generated, it is therefore necessary to employ a so-called physical random number generator. This uses either nondeterministic or chaotic physical processes to generate random numbers. The random numbers are then generated by measuring and processing certain process measurements (e.g., thermal noise voltage across a resistance). It is a goal of this invention to implement a physical random number generator that can be embedded in integrated circuits (ICs) and satisfies the following cryptographically and economically relevant quality criteria: — Implementable exclusively with the use of standardized components of conventional large-scale integrated circuits (e.g., logic gates) — Built up with the use of the fewest possible components (low cost, small surface area and low power consumption) — Embedded on the 1C as a freestanding, independent unit protected from the influence of other units — Turned on and off independently of the other units on the 1C — Quick restoration of functionality after turn-on (short warmup time) — Highest possible number of random bits generated per unit time (high rate) — Robustness with respect to ambient conditions (temperature, electromagnetic interference, variations in power supply voltage, etc.) — Robustness with respect to invasive and noninvasive attempts at manipulation (attacks) - Passive attacks - Active attacks — Satisfaction of statistical tests used to assess the quality of the randomness of both generated bits — As little deterministic post-processing of generated random numbers as possible — Capability of a functionality and quality test during operation (online test) In what follows, it will be assumed that a cryptographic random number generator is implemented as a bit source. The individual bits are combined into blocks depending on the application (e.g., 56 bits for a key of the Data Encryption Standard or DBS). It should be assumed in general that the bit strings generated by a cryptographic random number generator (e.g., a key) must remain secret in order not to compromise the security of the cryptosystem (in the list of applications in the preceding section, this does not hold for all the methods, up to challenge-response protocols and zero-knowledge proofs). In these cases, the random number generator generates the secret of the cryptographic method in question. With the aid of this secret, for example, cleartexts are encrypted. If the secret is unknown to the attacker, he always has to try out the choice of all possible bit strings (complete search). In the above example this would mean that the attacker, who has observed a cleartext encrypted with the unknown key, must try out a (statistical) average of 255 possible keys before he can expect to have found the key actually generated. This attack is the worst possible case from the viewpoint of the attacker. In order to attack a system with success, the attacker must be capable of predicting a certain number of bits that a generator generates at a certain point in time. This can happen without any knowledge of other bit strings generated by the generator or with a knowledge of bit strings that the generator has generated before or after the unknown bit string. The attacker can attempt to guess the generated bit string either in full or only in parts. In the latter case, he can find the remaining bits by a complete search. In order to make such a prediction, the attacker has access to all known technical and scientific tools. He is limited only with respect to the costs to be incurred for the attack. It can be assumed that these have to fall below a defined cost limit (an economic argument: The expected gain by the attack should not exceed the costs of the attack). The bit source can be subdivided into various security levels depending on the level of me cost limit. If a bit source resists all attacks for a given cost limit, then it should be regarded as a practically secure bit source in relation to this cost limit. FIG. 14 depicts a model of a physical random number generator TRNG in the form of a physical bit source. A substantial component of the source is a dynamic, unpredictable physical system, so-called random source 1. An internal (time-dependent) state can be associated with this random source 1. At temporal intervals, the value of the state of random source 1 is measured and processed (value acquisition 2) and one or a plurality of random bits are generated herefrom (random bit generation 3). Strings of random bits generated in this way are designated as internal random bits. These can next be subjected to algorithmic post-processing 5. Mathematical postprocessing 5 is in general performed in order to improve the quality of the internal random numbers (a measure for the quality of random numbers must still be defined here. See the next section for more detail). In general, one speaks of random extraction 5. This means the elimination of dependences between successively generated bits and the elimination of bias that is often present (unequal distribution of zeroes and ones). The random bits generated in this manner are output in a further step and, as appropriate, stored in an output memory (random bit output 5). As illustrated in FIG. 14, a physical random number generator TRNG is not an isolated system but is embedded in a physical environment 6. It should be assumed that the measured state and thus also the random bits generated are dependent on certain physical quantities of environment 6. These include quantities such as for example the power supply voltage delivered to the device, the ambient temperature, or electromagnetic fields. Various kinds of generators can be distinguished on the basis of the nature of the physical system. Two essential kinds of physical systems are used: — Quantum systems — Classical systems A quantum system means a system that is described by the laws of quantum mechanics. According to the current general scientific view, the phenomena occurring in such systems—on which random generation is then based—are truly random. Examples are decay processes in radioactive materials. Classical physical systems, in contrast, are described by the deterministic laws of (classical) physics. There can be a variety of reasons why these systems can nevertheless be unpredictable. For systems with many degrees of freedom, the interactions that arise within the system are often too complex to be predicted with exactness. What is more, the initial state of the system can often not be determined exactly. This fact has further impacts in the case of so-called chaotic systems. In such systems, tiny changes in the initial state lead, in the course of time, to widely differing and unpredictable states of the system. In order to assess a cryptographic bit source, it must be compared with the properties of the practically secure cryptographic bit source defined above. This includes a statistical assessment of the bit strings generated and a check of the possibilities of so-called side-channel attacks. These attacks actually take on great importance when random number generators are deployed in embedded systems. A side-channel attack is an attempt to predict the numbers generated by the generator or to influence their generation. This happens noninvasively by determining measured values from the environment of the generator (passive attacks) or by deliberately influencing the environment (active attacks). A further exacerbation of such an attack is represented by invasive side-channel attacks (for example, a hole might be drilled in the 1C in order to measure signals there). Typical passive, noninvasive attacks are for example the measurement of the electromagnetic radiation from, or the power consumption of, the generator. A variety of statistical tests are available for the statistical assessment of bit strings generated by a generator (e.g., Killmann, Wolfgang, and Werner Schindler, "A Proposal on Functionality Classes and Evaluation Methodology for Physical Random Number Generators" (Ein Vorschlag zu: Funktionalitatsklassen und Evaluationsmethodologie fur physikalische Zufallszahlengeneratoren), Bundesamt fur Sicherheit in der Informationstechnik (2001); Marsaglia, G., "Diehard: A Battery of Tests for Randomness," URL http://stat.fsu.edu/pub/diehard/ (1996); Ruhkin, A. L., J. Sotot, J. Nechvatal, M. Smid, M. Levenson, D. Banks, M. Vangle, S. Leigh, S. Vo and J. Dray, "A Statistical Test Suite for the Validation of Cryptography Random Number Generators," National Institute of Standards and Technology, Gaithersburg, MD (2000); Schindler, Werner, "Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications," in Kaliski, Burton S., Jr., Cetin Kaya Ko9 and Christof Paar (Eds.), "Cryptographic Hardware and Embedded Systems—CHES 2002, 4th International Workshop, Redwood Shores, CA, U.S.A., August 13-15, 2002, Revised Papers," Lecture Notes in Computer Science, Vol. 2523, Springer (2003), ISBN 3-540-00409-2, pp. 1-2). In principle, the problem of defining the concept of a random finite sequence arises in the assessment of these finite bit strings. According to Kolmogorov (Kolmogorov, Andrei N., "Three Approaches to the Quantitative Definition of Information," in Problems in Information Transmission 1 (1965), No. 1), a finite sequence is random if it cannot be compressed. This means that the length of its shortest algorithmic description with reference to a selected computer model is of the same order of magnitude as the length of the sequence itself (this is the so-called Kolmogorov complexity of a sequence, with the Turing1 machine as the computer model). The basic idea here is that a sequence that is compressible must exhibit regularities in order to permit compression. Random sequences thus exhibit no regularities in this sense. Unfortunately, this concept does not lead to direct tests for the randomness of strings because the Kolmogorov complexity is not computable in the sense of computability theory. The statistical tests are capable only of testing a bit string with respect to certain properties attributed to random (finite) bit strings. These properties are often derived from intuitive notions based on the general understanding of randomness. In fact, it can be shown of a number of tests that they are passed by bit strings random in the Kolmogorov sense (Li, Ming, and Paul Vitannyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag (1993), ISBN 0-387-94053-7). Physical random number generators are known in a multiplicity of variants from the existing art. At the beginning of the development of random number generators, primarily external random number generators, that is, those not embedded in ICs, were developed. A considerable selection of random sources employed are available for this purpose. In present-day external random number generators, a multiplicity of random sources are used, for example radioactive sources, electronic thermal noise in resistances, or random events in the environment (e.g., time intervals between key presses on a keyboard). It is only quite recently that random number generators have been embedded in commercial ICs. Here an important role is played by the kind of random source, its surface size The German-language original has Turning-Maschine.—Translator. on the 1C, technical implementation and miniaturization. Up to now, however, hardly any note has been taken of the immunity of random number generators to side-channel attacks. Examples of implemented embedded random number generators are found in DE 101 17 362 Al; Cryptography Research, Inc., "Evaluation of the VIA C3 Nehemiah Random Number Generator," URL http://www.cryptography.com/resources/whitepapersA^IA_rng.pdf; Cryptography Research, Inc., "The Intel Random Number Generator," URL http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf; US 2002/0186 086 Al; US 4,855,690; DE 101 03 071 Al; Fischer, Viktor, and Milos Drutarovsky, "True Random Number Generator Embedded in Reconfigurable Hardware," in Kaliski, Burton S., Jr., Cetin Kaya Ko9 and Christof Paar (Eds.), "Cryptographic Hardware and Embedded Systems—CHES 2002, 4th International Workshop, Redwood Shores, CA, U.S.A., August 13-15, 2002, Revised Papers," Lecture Notes in Computer Science, Vol. 2523, Springer (2003), ISBN 3-540-00409-2, pp. 415-430, US 5,706,218; WO 03/081417, DE 102 13 269 Al; US 2003/ 0185392 Al; EP 1 343 073 A2; Tkacik, Thomas E., "A Hardware Random Number Generator", in Kaliski, Burton S., Jr., Cetin Kaya Koc and Christof Paar (Eds.), "Cryptographic Hardware and Embedded Systems—CHES 2002,4th International Workshop, Redwood Shores, CA, U.S.A., August 13-15, 2002, Revised Papers," Lecture Notes in Computer Science, Vol. 2523, Springer (2003), ISBN 3-540-00409-2, pp. 450-453. The invention begins from a so-called inverter chain random number generator as is disclosed in a wide variety of embodiments according to the existing art. By way of example, reference is made to DE 102 13 269 Al. The fundamental component of these random number generators is a so-called ring oscillator 8. It comprises the serial connection of an odd number K of inverters inv1, inv2,..., invk (logical NOT gates), the output of the last inverter invk being connected to the input of the first inverter inv1 (see FIG. 15a). As a result of the delay times of the individual inverters inv1, inv2,..., invk, a periodic oscillation comes about only when the number K of gates inv1, inv2,..., invk is odd. In order to start and stop this oscillation, the first inverter inv1 can be replaced by a NAND gate nand1 with control input start/stop (see FIG. 15b). If this control input start/stop is set to a logical one ("1"), ring oscillator 9 begins to oscillate. FIG. 16a depicts a ring oscillator 10 for K = 3 having two inverters inva, inv3 and one NAND gate nand1. FIG. 16b depicts an idealized signal trace at input 11 and output 12 of an inverter inv whose delay time is T. If it is assumed that gates nandi, inv2, inv3 in ring oscillator 10 of FIG. 16a exhibit such an idealized behavior, then FIG. 16c depicts the idealized signal trace of ring oscillator 10 of FIG. 16a at points S, B, C and A = A' after input S has been set to "1" for an elapsed time T. For a technical implementation of ring oscillator 10 with K = 3 using the CMOS component 74HCT04 (with no input NAND gate, FIG. 17a), signal trace 14 recorded with an oscilloscope at point A' is illustrated in FIG. 17b. As is implied by the enlarged detail of signal trace 14 (in FIG. 17b), thermal motion of the electrons in the conductors of circuit 74HCT04 adds a thermal noise signal. FIG. 17c depicts envelope 15 of noisy oscillation signal 14 observed over a longer time interval t. As can be remarked, the noise in the flanks of signal 14 leads to the decision level being exceeded earlier or later than in the case of the noise-free signal. This temporally random shift in the flanks is called "jitter." The difference between the maximum possible flank shift, observed with reference to a fixed time t1 (FIG. 17c), is identified by the reference character A. The magnitude of this difference A increases with the distance of the flank from the reference time t\. This phenomenon is known as "jitter accumulation." An oscillation signal 14 of ring oscillator 10 from FIG. 17a, with a frequency f of approximately 25 MHz, averaged 512 times over a duration of 0.2 s, is illustrated in FIG. 18. Envelope 13 of this averaged signal depicts the behavior of the autocorrelation for various temporal intervals from the trigger point. As can be seen from FIG. 18, signal 14 is not completely decorrelated by accumulated jitter until after approximately 0.28 s. This means that the generated bits would be decorrelated, and thus could be used for a random bit source, only at a sampling rate v of 3 Hz (or less). In order to increase the maximum possible rate vmax of generated random bits, a plurality of ring oscillators with various periods (i.e., with various values for K) can be combined. FIG. 19 depicts two exemplary embodiments of circuit arrangements based on a number L of ring oscillators 17, 18, 19, 20, 21, 22. Here a parity check of the outputs (so-called XORing) is performed in each case. In concrete terms, this means that the outputs of respective ring oscillators 17, 18, 19, 20, 21, 22 are connected to the inputs of an XOR gate xor so that a "1" signal is generated at its output only if an odd number of logical "1" signals are present at the outputs of ring oscillators 17, 18, 19, 20, 21, 22. An even number of logical "1" values will generate a "0" signal at the output of the XOR gate. For this reason, the signal at the output of XOR gate xor is referred to as parity signal PS in what follows. The two circuits of FIG. 19a and FIG. 19b differ solely in the configuration of the start/stop inputs of ring oscillators 17, 18,19, 20, 21, 22. In the first embodiment according to FIG. 19a, the start/stop inputs of the individual ring oscillators 17, 18, 19 are driven together. The second possibility, illustrated in FIG. 19b, is to drive the inputs separately in order in this way to shift the initial phases of the individual oscillation signals relative to one another. FIG. 20a illustrates a circuit with parity checking of two ring oscillators 24, 25 with common start/stop signal. As can be seen in FIG. 20b and FIG. 20c, period P of parity signal PS, 29 remains constant. As a result of slow phase shifts of individual ring oscillator signals 27, 28, signal trace 29 of parity signal PS changes, within a period P over longer time intervals, as can be seen clearly in FIG. 21a. Over a time of approximately 0.2 s in FIG. 21b, envelope 30 of parity signal PS, 29 displays a more-variable autocorrelation that is smaller than the autocorrelation of the individual components (see FIG. 18). This parity checking of ring oscillators is used in many implementations of random number generators. The correlations cannot be completely removed with this technique, and so additional, rate-reducing, deterministic post-processing becomes unavoidable. It is now an object of the invention to fashion or to develop a random number generator of the kind stated above, as well as a method for generating a random number string such as is known from the existing art, in such a way that deterministic post-processing is no longer necessary. This object is achieved with a random number generator having the features of Claim 14 as well as with a method having the features of Claim 1. Advantageous fashionings and developments of the invention are identified in the dependent Claims. The invention begins from a method for generating random numbers in which oscillating digital output signals of equal or unequal periodicity are generated by at least two ring oscillators and in which there is generated an external parity signal representing a logical state, namely logical "0" or "1," which external parity signal takes on the logical state "1" when and only when an odd number of the output signals have the logical state "1" and takes on the logical state "0" otherwise. According to the invention, the external parity signal is fed back to an external parity input of each of the respective ring oscillators. As is known from the existing art, the external parity signal can be employed for generating random bits by sampling it. Because of the feedback of the parity signal to the (external parity) input of the respective ring oscillator, the autocorrelation of the parity signal is significantly reduced in relation to the method without feedback known from the existing art. For this reason, the rate of generated random bits can be significantly increased with the method according to the invention. A random number generator according to the invention comprises, in appropriate fashion, at least two ring oscillators preferably constructed from independently free-running inverter chains with feedback, having an odd number of series-connected inverters, which ring oscillators generate the aforesaid oscillating digital output signals of equal or unequal periodicity, as well as first parity signal generating means preferably formed by an exclusive-OR gate, which generate the external parity signal mentioned above. According to the invention there are feedback means, formed for example by exclusive-OR gates, which feed back this external parity signal to an external parity input of each of the respective ring oscillators (formed from inverter chains). In a preferred embodiment according to the invention, for each ring oscillator there is generated in each case an internal parity signal representing a specified logical state (e.g., "1") when either the output signal of the respective ring oscillator or the signal fed back to the external parity input of the respective ring oscillator takes on a specified logical state (e.g., "1"). These internal parity signals can in turn be converted, by further parity signal formation of the kind described above, to a further parity signal that can be employed in the manner described above for generating random bits by sampling it. As a result of this further parity formation, a signal is produced whose autocorrelation is once again significantly reduced in comparison with the external parity signal. At the same time, the possible sampling rate for generating random bits can be significantly reduced once again in this way. Accordingly, for generating the internal parity signals, the random number generator according to the invention comprises appropriate parity signal generating means. These preferably comprise exclusive-OR gates each having an external parity input and an output signal input. A signal derived from the external parity signal is present at the external parity input, for example the parity signal itself or a signal whose generation will be described in detail in what follows. The respective output signal of the respective ring oscillator is present at the output signal input. In order to generate the Further parity signal, the random number generator according to the invention comprises further parity signal generating means, which generate the further parity signal representing a logical state "0" or "1" when an odd number of internal parity signals take on a specified logical state (e.g., "1"). In appropriate fashion, these means also preferably comprise an exclusive-OR gate (XOR gate) at whose inputs the internal parity signals are present. As has already been mentioned, a starting problem can arise in particular in the case of ring oscillators formed from inverter chains. In order to avoid this problem according to the invention, in the random number generator according to the invention, there are starting means that generate a start signal (e.g., a logical "1") and supply it to a start/stop input of at least one of the ring oscillators so that this ring oscillator is excited into oscillation. To this end, this ring oscillator has a N AND gate with two inputs instead of an inverter on the input side. The one input and the output of this NAND gate are connected to the rest of the inverter chain instead of the input and the output of the removed inverter. The other input forms the aforementioned start/stop input to which the start signal is supplied. In principle, all the ring oscillators can be started separately via corresponding start/stop inputs. It has been found to be favorable in many cases, however, if all ring oscillators are excited into oscillation, preferably at the same time, with the aid of the same start signal (e.g., logical "1"). To this end, for example, instead of an inverter on the input side, all ring oscillators are each provided with a NAND gate whose start/stop inputs are connected to one another for the supplying of the start signal (e.g., a logical "1"). Another starting problem can now arise depending on the constellation. This starting problem can be eliminated by connecting an inverter in front of at least one external parity input, to which inverter the external parity signal is supplied. First, this inverter causes a delay of the signal at this external parity input; second, the signal at this external parity input with inverter connected in front experiences a reversal of polarity . The latter case leads to a reversal of polarity at the input of the corresponding ring oscillator and thus to an inception of oscillation in this ring oscillator. The other connected ring oscillators are also excited into oscillation as a consequence. In certain application cases it has proved advantageous if inverter chains differing in the number of inverters are connected in front of all external parity inputs, to which inverter chains Bie external parity signal is supplied. An oscillation of the circuit arrangement then comes about if the sum of the periodicity of an output signal generated by a first of the ring oscillators, equal in value to an odd multiple of a delay time of a gate (inverter,2 NAND gate, XOR gate), plus the delay time duration of the external parity signal at the external parity input of the first of the ring oscillators, equal in value to a multiple of the delay time, equals an odd multiple of the delay time and if the sum of the periodicity of an output signal generated by a second of the ring oscillators, equal in value to an odd multiple of the delay time, plus the delay time duration of the external parity signal at the external parity input of the second of the ring oscillators, equal in value to a multiple of the delay time, equals an even multiple of the delay time. As was already mentioned above, both the external parity signal and also the further parity signal can be employed for generating random bits. The random number generator according to the invention can therefore have sampling means that sample the external parity signal at a specified rate for generating random bits and/or sampling means that sample the further parity signal at a specified rate for generating random bits. The maximum sampling rate can be further increased if a plurality of random number generators of the kind described above are combined. Starting from random number generators that generate external, in particular sampled, parity signals and/or that generate further, in particular sampled, parity signals, it is possible by additional or repeated parity formation from these parity signals (arbitrary variations of parity signal formations are possible) to form random number generators in which the (super)parity signal provided for random number generation has an autocorrelation reduced to virtually any degree. Further random number generation requires sampling. Here it is of no import whether the external parity signals or the further parity signals or other parity signals of lower order are synchronously sampled at a specified rate for generating random bits or the (super)parity signal of highest order is sampled at the specified rate for generating random bits. Sampling can take place at temporally constant intervals, but provision is also made according to the invention for sampling to be performed at random, nonuniform sampling intervals. For example, random sampling can be achieved if sampling is performed at a time when a random bit randomly generated by one of the random generators described above takes on a predetermined logical state (e.g., "1"). The German-language original has Inventer.—Translator. For example, sampling can be effected with a D-flipflop driven by a pulse from a clock, in particular from an astable multivibrator (in the case of temporally constant sampling intervals) or by a ring oscillator of the kind described above with feedback (in the case of temporally random sampling intervals). The invention will now be described in greater detail with reference to the Drawings, in which: FIG. 1 depicts ring oscillators with feedback of parity signal; FIG. 2 depicts an example of the starting problem in the case of ring oscillators with feedback: a) before start, b) after start; FIG. 3 depicts a solution of the starting problem from FIG. 2: a) before start, b) after start; FIG. 4 depicts the signal trace of parity signal PS in the circuit of FIG. 3 in a time span of: a) 10ns; b) 40ns; c) 200ns; d) 400ns; e) 1000ns; f) 2000ns; FIG. 5 depicts an averaged parity signal of the circuit from FIG. 3; FIG. 6 depicts a general circuit diagram of ring oscillators with feedback (RRO); FIG. 7 depicts a circuit of RRO (4; 1, 3, 4, 5; 3, 2, I, 0); FIG. 8 depicts internal parity signals of RRO (4; 1, 3, 4, 5; 3, 2, 1, 0) of FIG. 7 at points P1,P2,P3andP4; FIG. 9 depicts a random bit generator implemented with RROs; FIG. 10 depicts an example of a random number generator with RRO (4; 1, 3, 4, 5; 3, 2, 1,0); FIG. 11 depicts a random number generator having a number N of RROs and sampled superparity signal; FIG. 12 depicts a random number generator having a number of N of sampled RROs and sampled superparity signal; FIG. 13 depicts a random number generator having a number N of synchronized sampled RROs and sampled superparity signal; FIG. 14 depicts a model of a physical random number generator (existing art); FIG. 15 depicts ring oscillators according to the existing art: a) inverter-chain ring oscillator; b) inverter-chain ring oscillator with control input; FIG. 16 depicts an example of the mode of functioning of a ring oscillator according to the existing art: a) a ring oscillator for K = 3 (existing art); b) an idealized delay of an inverter; c) a trace of an oscillation signal; FIG. 17 depicts an example of the practical implementation of the ring oscillator of FIG. 16: a) implementation of a ring oscillator for K = 3 with the component 74HCT04; b) trace of its oscillation signal with thermal noise added; c) envelope of the noisy oscillation signal; FIG. 18 depicts an averaged oscillation signal of the ring oscillator of FIG. 17a; FIG. 19 depicts an example of the performance of a so-called parity check (existing art): a) a circuit for parity checking of L ring oscillators with start/stop signal driven in common; b) a circuit for parity checking of L ring oscillators with start/stop signal driven separately; FIG. 20 depicts an example of the practical performance of the parity check of FIG. 19a: a) an example of a circuit for parity checking of two ring oscillators with start/stop signal driven in common; b) signals of the individual components and trace of the parity signal; c) signals of the individual components and trace of the parity signal; FIG. 21 depicts an example of the practical performance of the parity check of FIG. 19a: a) signals of the individual components and trace of the parity signal; b) an averaged parity signal of the circuit of FIG. 20a; FIG. 22 depicts an RRO with neutralized residual bias. The basic idea of the invention, as was illustrated above, consists in feedback of the parity signal to the inputs of the individual ring oscillators. FIG. 1 depicts a first exemplary embodiment of a random generator according to the invention, based on a number L of ring oscillators 32, 33, 34 whose outputs are supplied to corresponding inputs of an XOR gate xor at which a parity signal PS is formed. As FIG. 1 shows, the supplying of feedback parity signal PS to the individual inputs of ring oscillators 32, 33, 34 is effected via a number of logical XOR gates xor1, xor2,..., xorL. The input at which parity signal PS is present in each case will be referred to as external parity input 36,37,38. It is important to note that oscillation of this circuit does not come about for all value combinations of the parameters L, K1,..., KL, as the example in FIG. 2 shows for L = 3, K1 = 3, K2 = 5 and K.3 = 7 and as is described in detail in what follows. The logical state of the circuit in the off state is illustrated in FIG. 2a. FIG. 2b depicts the state of the circuit after it is turned on (i.e., after the start/stop signal has been set to logical "1"). As should be noted, the circuit is always still in a static (nonoscillating) state because all outputs of the NAND gates nandy for i = 1, 2, 3 have not changed. This starting problem can be alleviated by inserting a further inverter inv3,-1 in front of external parity input 47 of the XOR gate (see FIG. 3). Parity signal PS of this now-oscillating circuit is illustrated for various time intervals in FIG. 4. It can be clearly seen that feedback leads to a very irregular form of parity signal PS for a suitable (oscillating) parameter combination. Averaged parity signal PS shows a very low and constant autocorrelation (see FIG. 5). In comparison with FIG. 21b, this is a significant improvement, making it possible to increase substantially the rate v of generated random bits. In order to solve the starting problem in general, and in order to introduce additional jitter accumulation, chains of inverters invi,-j, i = 1,..., L, j = 1,..., Mi are introduced in front of XOR gates xorj, i = 1,..., L. The length of the individual chains M1, ..., ML is variable. In order to make certain that the start/stop problem does not arise, parameters Mi and Ki must be chosen specially. It must be the case that there exists at least one pair i, j with i, j ε {1,..., L} × {1,..., L} such that one of the two sums Mj + Kj and Mj + Kj is odd and the other is even. FIG. 6 depicts a general circuit diagram with feedback of parity signal PS. In what follows, this circuit will be referred to as ring oscillators with feedback (RRO).3 The signals at outputs P1 to PL of XOR gates xori to xorL check the parity of their input signals and are therefore referred to as internal parity signals. For distinction, parity signal PS at the output of the XOR gate XOR will be referred to as the external parity signal. FIG. 7 depicts an instance of the RRO with parameters L = 4, KI = 1, K2 = 3, K.3 = 4, K4 = 5; M1 = 3, M2 = 2, M3 = 1, IVL, = 0. The notation RRO (4; 1, 3,4, 5; 3, 2, 1, 0) will be employed for brevity. The internal parity signals are quite various because of the construction of the RRO, as FIG. 8 shows, and can be used for generating random bits. The quality is further improved by a further parity check PP of the internal parity signals P1, P2,..., PL, in which a further parity signal PP is generated, and can be employed as a random bit string ZB after sampling, as FIG. 9 illustrates. Sampling is effected with a D-flipflop 85, which is driven by a periodic clock signal Cp. Clock signal Cp can be generated by an astable multivibrator 87 and its period (uniform sampling interval) determined with a binary counter 86. In order to obtain random, nonuniform sampling intervals, astable multivibrator 87 can be replaced by an RRO. A random number generator with RRO instance RRO (4; 1, 3, 4, 5; 3, 2, 1, 0) with uniform sampling is illustrated in FIG. 10. Statistical tests of this random number generator have revealed little bias and a low correlation of bits 7. In order to eliminate these effects, a plurality of RROs were coupled via a further (super)parity check SP. This coupling can be performed in a variety of ways. In FIG. 11, uniform sampling takes place after parity check PP; in FIG. 12, in contrast, the individual RROs are sampled before (super)parity check SP. Because this takes place asynchronously, superparity signal SP must be sampled again in order to obtain random bits 7 of equal duration. In order to avoid this, sampling can also be performed synchronously, as shown in FIG. 13. A small but still disturbing bias often manifests itself in practice. Accordingly, a random bit string is generated that is not good enough. Other electronically implemented TRNGs also have this defect, which is usually due to the unmatched operating points of the active semiconductor components used. In practice heretofore, a variety of deterministic post-processings such as for example the frequently used von Neumann method have been performed after sampling (on the digital level) in order to neutralize this residual bias. All these algorithms The abbreviation RRO stands for ruckgekoppelter Ring-Oszillator (= ring oscillator with feedback). I have let it stand in the Specification because it also appears in the Drawings.—Translator. substantially reduce the rate of generated random bits. Nevertheless, using ring oscillators with feedback (RRO), this residual bias can be neutralized even before sampling if binary counters 881, 882,..., 88L of length Z (here with a number Z of JK-flipflops JK1, JK2,..., JKZ) are connected to outputs PI, P2,..., PL of ring oscillators RRO (see FIG. 9). The outputs of these counters 881, 882,..., 88L are connected to the inputs of the XOR gate, which delivers further parity signal PP (FIG. 22). By counting the signal transitions between two signal states (high and low with unequal duration), new (longer) signal states are obtained. In terms of duration, these new signal states are more similar to one another than the signal states of the original signal. The larger the number Z is, the better the signal state durations can be equalized and thus residual bias suppressed to arbitrarily small values. Good results are achieved even with Z = 1. List of Reference Characters and Abbreviations 1 Random source 2 Value acquisition 3 Random bit generation 4 Algorithmic post-processing/random extraction 5 Random bit output 6 Physical environment 8 Ring oscillator 9 Ring oscillator with control input 10 Ring oscillator 11 Input signal 12 Output signal 13 Signal envelope 14 Signal trace at conductor point A' 15 Envelope curve 17 Ring oscillator 18 Ring oscillator 19 Ring oscillator 20 Ring oscillator 21 Ring oscillator 22 Ring oscillator 24 Ring oscillator 25 Ring oscillator 27 First input signal of XOR gate 28 Second input signal of XOR gate 29 Parity signal 30 Envelope of averaged parity signal 32 Ring oscillator 33 Ring oscillator 34 Ring oscillator 36 External parity input 37 External parity input 38 External parity input 41 Ring oscillator 42 Ring oscillator 43 Ring oscillator 45 External parity input 46 External parity input 47 External parity input 47° External parity input 71 Ring oscillator 72 Ring oscillator 73 Ring oscillator 81 Ring oscillator 82 Ring oscillator 83 Ring oscillator 84 Ring oscillator 85 D-flipflop 85] D-flipflop 86 Binary counter 861 Binary counter 87 Astable multivibrator 871 Astable multivibrator 881 Binary counter A Conductor point B Conductor point C Conductor point A Conductor point DES Data Encryption Standard f Frequency inv Inverter inv1 Inverter/NOT gate inv2 Inverter/NOT gate invk Inverter/NOT gate JK1 JK-flipflop JK2 JK-flipflop JKZ JK-flipflop K Number of gates K1 Number of gates K1 Number of gates K2 Number of gates K3 Number of gates KL Number of gates L Number of ring oscillators M Number of gates MI Number of gates M2 Number of gates M3 Number of gates M4 Number o f gates ML Number of gates N Number of ring oscillators nand1 NAND gate nand2 P Period P1 Internal parity signal P2 Internal parity signal PL Internal parity signal PRNG Deterministic random generator PS External parity signal RRO Ring oscillator(s) with feedback S Conductor point SP Superparity signaf start/stop Control input t Time t1 Time point T Elapsed time TRNG Physical random generator U Voltage Ue Input voltage Ua Output voltage xor Exclusive-OR / XOR gate with logical "1" at output when an odd number of inputs are at logical "1" xor1 Exclusive-OR / XOR gate with logical "1" at output when an odd number of inputs are at logical "1" xor2 Exclusive-OR / XOR gate with logical "1" at output when an odd number of inputs are at logical "1" Z Number ZB Random bit A Difference v Sampling rate vmax Maximum sampling rate Τ Delay time We claim 1. A random number generator having at least two ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84), made up in particular of independently free-running inverter chains with feedback having an odd number (K) of series-connected inverters (inv1/2, inv2,1, inv3,1, ..., invi,j, ...., invL,KL.), which generate oscillating digital output signals (A1, A2, ..., AL) unequal in periodicity, and having first parity signal generating means (XOR), which generate an external parity signal (PS) representing a predetermined logical state ("0," "1")/ which external parity signal takes on the logical state "1" when and only when an odd number of the output signals (A1, A2, ..., AL) exhibit the logical state "1" and takes on the logical state "0" otherwise, wherein there are feedback means (xor1, xor2, xor3, xor4, ..., xorL) that feed back the external parity signal (PS) to an external parity input (36, 37, 38, 45, 46, 47) of each of the respective ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84). 2. The random number generator as claimed in claim 1 wherein the first parity signal generating means comprise an XOR gate (XOR) at whose inputs the output signals (A1, A2, ..., AL) are present. 3. The random number generator as claimed in one of claims 1 or 2 wherein there are second parity signal generating means (xor1, xor2, xor3, ..., xorL) that generate, for each ring oscillator (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84), an internal parity signal (P1, P2, P3, P4, ..., PL) representing a specified logical state ("1"), which internal parity signal takes on the logical state "1" when and only when either the output signal of the respective ring oscillator (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84) or the signal fed back to the external parity input (36, 37, 38, 45, 46, 47) of the respective ring oscillator (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84) takes on a specified logical state ("1")- 4. The random number generator as claimed in claim 3 wherein the second parity signal generating means comprise XOR gates (xor1, xor2, xor3, ..., xorL) each having an external parity input and an output signal input, a signal derived from the external parity signal (PS) being present at the parity input and the respective output signal (A1, A2, ..., AL) of the respective ring oscillator (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84) being present at the output signal input. 5. The random number generator as claimed in claim 4 wherein there are third parity signal generating means that generate a further parity signal (WP) representing a logical state ("0,","1"), which further parity signal takes on the logical state "1" when and only when an odd number of the internal parity signals (P1, P2, P3, P4, ..., PL) exhibit the logical state "1" and takes on the logical state "0" otherwise. 6. The random number generator as claimed in claim 5 wherein there are counting means (881, 882, ..., 88L) that count signal transitions of the internal parity signals (P1, P2, P3,..., PL) before parity signal generation. 7. The random number generator as claimed in claim 6 wherein the counting means comprise a binary counter (881, 882, ..., 88L), in particular a chain with flipflops, preferably JK-flipflops (JK1, JK2,..., JKZ). 8. The random number generator as claimed in one of claims 1 to 7 wherein there are starting means that generate a start signal ("1") and supply it to an input (start/stop) of at least one of the ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84) so that this ring oscillator is excited into oscillation. 9. The random number generator as claimed in claim 8 wherein the at least one of the ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84) comprises, instead of an inverter (inv1) on the input side, a NAND gate (nand1, nand1,1', nand24, nand3,1, ..., nandi,1, ...., nandL1,) having the input (start/stop) for the supplying of the start signal ("1"')- 10. The random number generator as claimed in one of claims 8 or 9 wherein the starting means are fashioned such that all ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84) are excited into oscillation, preferably at the same time, with the aid of the same start signal ("1"). 11. The random number generator as claimed in claim 10 wherein all ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84) comprise, instead of an inverter (inv1) on the input side, a NAND gate in each case (nand1, nand1,1, nand2,1, nand3,1, ..., nandi,1, ...., nandL,1) having in each case an input (start/stop), which are connected to one another for the supplying of the start signal ("1")- 12. The random number generator as claimed in one of claims 1 to 11 wherein connected in front of at least one external parity input (47) is an inverter (inv3,-1, inv1,-M1, ..., inv1,-1, ..., invL.ML, ...., invL,-1), to which the external parity signal (PS) is supplied. 13. The random number generator as claimed in claim 12 wherein connected in front of all external parity inputs are inverter chains having unequal numbers (M1, M2/ ..., ML) of inverters (inv1,-M1, ..., inv1,-1, ..., invL-ML, invL-1), to which the external parity signal (PS) is supplied. 14. The random number generator as claimed in claim 13 wherein the sum of the periodicity of an output signal (A1, A2, ..., AL) generated by a first of the ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84), equal in value to an odd multiple (K1, K2, K3,..., KL) of a delay time of a gate, plus the delay time duration of the external parity signal (PS) at the external parity input (36, 37, 38, 45, 46, 47) of the first of the ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84), equal in value to a multiple (M1, M2, M3, ..., ML) of the delay time of a gate, equals an odd multiple of the delay time of a gate and wherein the sum of the periodicity of an output signal (A1, A2, ..., AL) generated by a second of the ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84), equal in value to an odd multiple (K1, K2, K3,..., KL) of the delay time of a gate, plus the delay time duration of the external parity signal (PS) at the external parity input (36, 37, 38, 45, 46, 47) of the second of the ring oscillators (32, 33, 34, 41, 42, 43, 71, 72, 73, 81, 82, 83, 84), equal in value to a multiple (M1, M2, M3, ..., ML) of the delay time of a gate, equals an even multiple of the delay time of a gate. 15. The random number generator as claimed in one of claims 1 to 14 wherein there are sampling means that sample the external parity signal (PS) at a specified rate (v) for generating random bits (ZB) and/or wherein there are sampling means that sample the further parity signal (PP) at a specified rate (v) for generating random bits (ZB). 16. The random number generator as claimed in one of claims 1 to 15 wherein there are a plurality of random number generators according to one of claims 15 to 29 that generate external, in particular sampled, parity signals (PS) and wherein there are superparity signal generating means that generate a superparity signal (SP) representing a logical state ("0,0," "1"), which superparity signal takes on the logical state "1" when and only when an odd number of the external, in particular sampled, parity signals (PS) exhibit the logical state "1" and takes on the logical state "0" otherwise, and/or wherein there are a plurality of random number generators according to one of claims 15 to 29 that generate further, in particular sampled, parity signals (PP), and wherein there are superparity signal generating means that generate a superparity signal (SP) representing a logical state ("0,"' "1"), which superparity signal takes on the logical state "1" when and only when an odd number of the further, in particular sampled, parity signals (PP) exhibit the logical state "1" and takes on the logical state "0" otherwise. 17. The random number generator as claimed in claim 16 wherein there are sampling means that sample the external parity signal (PS) or the further parity signals (PP) synchronously at a specified rate (v) for generating random bits (ZB) and/or wherein there are sampling means that sample the superparity signal (SP) at a specified rate (v) for generating random bits (ZB). 18. The random number generator as claimed in one of claims 15 to 17 wherein the sampling means are designed to perform sampling at random, nonuniform sampling intervals and in particular to perform sampling when a random bit (ZB) randomly generated by one of the random generators according to claims 15 to 31 takes on a predetermined logical state ("1")- 19. The random number generator as claimed in one of claims 15 to 18 wherein the sampling means comprise a D-flipflop (881, 882, ..., 88L) driven by a pulse from a clock (Cp), in particular from an astable multivibrator (87, 871, 872,..., 87L) or by a ring oscillator with feedback (RRO).

Documents:

2576-DEL-2005-Abstract-(10-02-2012).pdf

2576-DEL-2005-Abstract-(11-02-2010).pdf

2576-DEL-2005-Abstract-(26-08-2011).pdf

2576-del-2005-abstract.pdf

2576-del-2005-assignment.pdf

2576-DEL-2005-Claims-(10-02-2012).pdf

2576-DEL-2005-Claims-(26-08-2011).pdf

2576-del-2005-claims.pdf

2576-DEL-2005-Correspondence Others-(10-02-2012).pdf

2576-del-2005-Correspondence Others-(23-08-2012).pdf

2576-DEL-2005-Correspondence Others-(26-08-2011).pdf

2576-DEL-2005-Correspondence-Others (11-02-2010).pdf

2576-del-2005-correspondence-others.pdf

2576-DEL-2005-Description (Complete)-(26-08-2011).pdf

2576-del-2005-description (complete).pdf

2576-del-2005-drawings.pdf

2576-DEL-2005-Form-1-(10-02-2012).pdf

2576-del-2005-form-1.pdf

2576-del-2005-form-18.pdf

2576-DEL-2005-Form-2-(10-02-2012).pdf

2576-DEL-2005-Form-2-(26-08-2011).pdf

2576-del-2005-form-2.pdf

2576-del-2005-Form-3-(23-08-2012).pdf

2576-DEL-2005-Form-3-(26-08-2011).pdf

2576-del-2005-form-3.pdf

2576-del-2005-form-5.pdf

2576-DEL-2005-GPA-(26-08-2011).pdf

2576-del-2005-gpa.pdf

2576-DEL-2005-Petition-137-(26-08-2011).pdf