Random number generator and method for generating random numbers

• US 20060069706A1
• Filed: 09/28/2005
• Published: 03/30/2006
• Est. Priority Date: 09/28/2004
• Status: Active Grant

• Current Assignee: Tdk-Micronas Gmbh (TDK Corporation)
• Original Assignee: Micronas Gmbh (TDK Corporation)
• Inventors: Lazich, Dejan, Temerinac, Miodrag, Schober, Steffen, Alrutz, Herbert
• Granted Patent: US 7,797,361 B2
• Time in Patent Office: Days
• US Class Current: 708/251
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

The invention relates to a method for generating random numbers in which oscillating digital output signals (A₁, A₂, . . . , A_L) 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 (A₁, A₂, . . . , A_L) 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 (inv_1,2, inv_2,1, inv_3,1, . . . , inv_i,j, . . . , inv_L,KL) that generate oscillating digital output signals (A₁, A₂, . . . , A_L) 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 (A₁, A₂, . . . , A_L) take on a specified logical state (“1”). According to the invention, there are feedback means (xor₁, xor₂, xor₃, xor₄, . . . , xor_L) 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.

Claims

1. A method for generating random numbers in which oscillating digital output signals (A1, A2, . . . , AL) of equal or unequal periodicity are generated by at least two ring oscillators, an external parity signal (PS) representing a logical state (“

0,”

“

1”

) being generated, which external parity signal takes on the logical state “

1”

when and only when an odd number of output signals (A1, A2, . . . , AL) exhibit the logical state “

1” and

takes on the logical state “

0”

otherwise, wherein the external parity signal (PS) is fed back to an external parity input (36, 37, 38, 45, 46, 47) of each respective ring oscillator.

2. The method of claim 1 wherein for each ring oscillator there is generated in each case an internal parity signal (P₁, P₂, P₃, P₄, . . . , P_L) representing a predetermined logical state (“

0,”

“

1”

) when either the output signal (A₁, A₂, . . . , A_L) of the respective ring oscillator or the signal fed back to the external parity input (36, 37, 38, 45, 46, 47) of the respective ring oscillator takes on a specified logical state (“

1”

).

3. The method of claim 2 wherein there is generated a further parity signal (PP) 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 (P₁, P₂, P₃, P₄, . . . , P_L) exhibit the logical state “

1” and

takes on the logical state “

0”

otherwise.

4. The method of claim 3 wherein signal transitions of the internal parity signals (P₁, P₂, P₃, P₄ . . . , P_Z) are counted before parity signal generation.

5. The method of claim 1 wherein at least one of the ring oscillators is excited into oscillation with the aid of a start signal (“

1”

) supplied to a corresponding input (start/stop) of the corresponding ring oscillator.

6. The method of claim 5 wherein the ring oscillators are excited into oscillation, preferably at the same time, with the aid of the same start signal (“

1”

).

7. The method of claim 6 wherein the external parity signal (PS) is inverted before being fed back to at least one of the external parity inputs (47).

8. The method of claim 6 wherein the external parity signal (PS) is delayed before being fed back to at least one of the external parity inputs (47).

9. The method of claim 8 wherein the external parity signal (PS) is delayed by different time durations (τ

) before being fed back to different external parity inputs (36, 37, 38, 45, 46, 47).

10. The method of claim 9 wherein the periodicities of the ring oscillators and the delay time durations of the external parity signal (PS) at the external parity inputs (36, 37, 38, 45, 46, 47) of the ring oscillators are chosen such that the sum of the periodicity of an output signal (A₁, A₂, . . . , A_L) generated by a first of the ring oscillators, equal in value to an odd multiple (K₁, K₂, K₃, . . . , K_L) 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, equal in value to a multiple (M₁, M₂, M₃, . . . , M_L) 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 (A₁, A₂, . . . , A_L) generated by a second of the ring oscillators, equal in value to an odd multiple (K₁, K₂, K₃, . . . , K_L) 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, equal in value to a multiple (M₁, M₂, M₃, . . . , M_L) of the delay time of a gate, equals an even multiple of the delay time of a gate.

11. The method of claim 1 wherein the external parity signal (PS) is sampled at a specified rate (ν

) for generating random bits (78) or wherein the further parity signal (PP) is sampled at a specified rate (ν

) for generating random bits (78).

12. The method of claim 1 wherein a plurality of external, in particular sampled, parity signals (PS) are generated and wherein there is generated a super parity signal (SP) representing a logical state (“

0,”

“

1”

), which super parity 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, or wherein a plurality of further, in particular sampled, parity signals are generated and wherein there is generated a super parity signal (SP) representing a logical state (“

0,”

“

1”

), which super parity signal takes on the logical state “

1”

when and only when an odd number of the further, in particular sampled, parity signals exhibit the logical state “

1” and

takes on the logical state “

0”

otherwise.

13. The method of claim 12 wherein the external or the further parity signals (PS) are synchronously sampled at a specified rate (ν

) for generating random bits (ZB) or wherein the super parity signal (SP) is sampled at a specified rate (ν

) for generating random bits (ZB).

14. The method of claim 11 wherein sampling is performed at random, nonuniform sampling intervals, in particular wherein sampling is performed when one of the random bits (ZB) generated a predetermined logical state (“

1”

).

15. A random number generator having at least two ring oscillators, made up in particular of independently free-running inverter chains with feedback having an odd number (K) of series-connected inverters (inv_1,2, inv_2,1, inv_3,1, . . . , inv_i,j, . . . , inv_L,KL), which generate oscillating digital output signals (A₁, A₂, . . . , A_L) 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 (A₁, A₂, . . . , A_L) exhibit the logical state “

1” and

takes on the logical state “

0”

otherwise, wherein there are feedback means (xor₁, xor₂, xor₃, xor₄, . . . , xor_L) 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.

16. The random number generator of claim 15 wherein the first parity signal generating means comprise an XOR gate (XOR) at whose inputs the output signals (A₁, A₂, . . . , A_L) are present.

17. The random number generator of claim 15 comprising second parity signal generating means (xor₁, xor₂, xor₃, . . . , xor_L) that generate, for each ring oscillator, an internal parity signal (P₁, P₂, P₃, P₄, . . . , P_L) 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 or the signal fed back to the external parity input (36, 37, 38, 45, 46, 47) of the respective ring oscillator takes on a specified logical state (“

1”

).

18. The random number generator of claim 17 wherein the second parity signal generating means comprise XOR gates (xor₁, xor₂, xor₃, . . . , xor_L) 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 (A₁, A₂, . . . , A_L) of the respective ring oscillator being present at the output signal input.

19. The random number generator of claim 18 comprising 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 (P₁, P₂, P₃, P₄, . . . , P_L) exhibit the logical state “

1” and

takes on the logical state “

0”

otherwise.

20. The random number generator of claim 19 comprising counting means (88₁, 88₂, . . . , 88_L) that count signal transitions of the internal parity signals (P₁, P₂, P₃, . . . , P_L) before parity signal generation.

21. The random number generator of claim 20 wherein the counting means comprise a binary counter (88₁, 88₂, . . . , 88_L), in particular a chain with flipflops, preferably JK-flipflops (JK₁, JK₂, . . . , J_Z).

22. The random number generator of claim 15, comprising starting means that generate a start signal (“

1”

) and supply it to an input (start/stop) of at least one of the ring oscillators so that this ring oscillator is excited into oscillation.

23. The random number generator of claim 22 wherein the at least one of the ring oscillators comprises, instead of an inverter (inv₁) on the input side, a NAND gate (nand₁, nand_1,1, nand_2,1, nand_3,1, . . . , nand_i,1, . . . , nand_L,1) having the input (start/stop) for the supplying of the start signal (“

1”

).

24. The random number generator of claim 22 wherein the starting means are fashioned such that all ring oscillators are excited into oscillation, preferably at the same time, with the aid of the same start signal (“

1”

).

25. The random number generator of claim 24 wherein all ring oscillators comprise, instead of an inverter (inv₁) on the input side, a NAND gate in each case (nand₁, nand_1,1, nand_2,1, nand_3,1, . . . , nand_i,1, . . . , nand_L,1) having in each case an input (start/stop), which are connected to one another for the supplying of the start signal (“

1”

).

26. The random number generator of claim 15 wherein connected in front of at least one external parity input (47) is an inverter (inv_3,-1, inv_1,-M1, . . . , inv_1,-1, . . . , inv_L,-ML, . . . , inv_L,-1), to which the external parity signal (PS) is supplied.

27. The random number generator of claim 26 wherein connected in front of all external parity inputs are inverter chains having unequal numbers (M₁, M₂, . . . , M_L) of inverters (inv_1,-M1, . . . , inv_1,-1, . . . , inv_L,-ML, inv_L,-1), to which the external parity signal (PS) is supplied.

28. The random number generator of claim 27 wherein the sum of the periodicity of an output signal (A₁, A₂, . . . , A_L) generated by a first of the ring oscillators, equal in value to an odd multiple (K₁, K₂, K₃, . . . , K_L) 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, equal in value to a multiple (M₁, M₂, M₃, . . . , M_L) 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 (A₁, A₂, . . . , A_L) generated by a second of the ring oscillators, equal in value to an odd multiple (K₁, K₂, K₃, . . . , K_L) 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, equal in value to a multiple (M₁, M₂, M₃, . . . , M_L) of the delay time of a gate, equals an even multiple of the delay time of a gate.

29. The random number generator of claim 15 comprising sampling means that sample the external parity signal (PS) at a specified rate (ν

) for generating random bits (ZB) and/or wherein there are sampling means that sample the further parity signal (PP) at a specified rate (ν

) for generating random bits (ZB).

30. The random number generator of claims 15 wherein there are a plurality of random number generators that generate external, in particular sampled, parity signals (PS) and wherein there are super parity signal generating means that generate a super parity signal (SP) representing a logical state (“

0,”

“

1”

), which super parity 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 that generate further, in particular sampled, parity signals (PP), and wherein there are super parity signal generating means that generate a super parity signal (SP) representing a logical state (“

0,”

“

1”

), which super parity 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.

31. The random number generator of claim 30 wherein there are sampling means that sample the external parity signals (PS) or the further parity signals (PP) synchronously at a specified rate (ν

) for generating random bits (ZB) and/or wherein there are sampling means that sample the super parity signal (SP) at a specified rate (ν

) for generating random bits (ZB).

32. The random number generator of claim 31 wherein the sampling means are designed to perform sampling at random, non-uniform 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”

).

33. The random number generator of claim 32 wherein the sampling means comprise a D-flip-flop (88₁, 88₂, . . . , 88_L) driven by a pulse from a clock (C_P), in particular from an astable multivibrator (87, 87₁, 87₂, . . . , 87_L) or by a ring oscillator with feedback (RRO).