System and method for generating random numbers using parity feedback

• US 7,797,361 B2
• Filed: 09/28/2005
• Issued: 09/14/2010
• Est. Priority Date: 09/28/2004
• Status: Expired due to Fees

• Current Assignee: Tdk-Micronas Gmbh (TDK Corporation)
• Original Assignee: Micronas Gmbh (TDK Corporation)
• Inventors: Schober, Steffen, Alrutz, Herbert, Lazich, Dejan, Temerinac, Miodrag
• Primary Examiner(s): Bullock, Jr.; Lewis A
• Assistant Examiner(s): Pan; Hang
• Application Number:
  US11/238,158
• Publication Number:
  US 20060069706A1
• Time in Patent Office: 1,812 Days
• Field of Search: 708/250, 708/251
• 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

A method for generating random numbers in which oscillating digital output signals of unequal or equal periodicity are generated by at least two ring oscillators, an external parity signal representing a logical state being generated when an odd number of the output signals take on a specified logical state, the external parity signal being fed back to an external parity input of each of the respective ring oscillators. Also, a random number generator having at least two ring oscillators made up of independently freewnning inverter chains with feedback having an odd number of series-connected inverters that generate oscillating digital output signals of unequal or equal periodicity, and having first panty signal generating mechanisms that generate an external parity signal representing a logical state when an odd number of the output signals take on a specified logical state.

Claims

1. A method for generating random numbers, comprising:

generating a plurality of oscillating digital output signals using at least two ring oscillators, and generating an external parity signal (PS) representing a logical state (“

0,”

“

1”

), where the external parity signal takes on the logical state “

1”

when and only when an odd number of the plurality of digital 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 of the ring oscillators wherein the sum of the periodicity of an output signal (A₁, A₂, . . . , A_L) generated by a first of oscillators, which is 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 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, which is equal in value to an odd multiple (K₁, K₂, K₃, . . . , K_L) of the delay time of gate, plus the delay time duration of the external parity signal (PS) at the external parity input 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.

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

0,”

“

1”

) when either the digital 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.

3. The method of claim 2, further comprising generating 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, 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.

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.

9. The method of claim 8, further comprising delaying the external parity signal (PS) by different time durations (τ

) before being fed back to different external parity inputs.

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

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

) for generating random bits.

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”

), where the 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 (v) 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”

).

34. The method of claim 1, wherein the generated oscillating digital output signals have equal periodicity.

35. The method of claim 1, wherein the generated oscillating digital output signals have unequal periodicity.

10. A method for generating random numbers, comprising:

generating a plurality of oscillating digital output signals using at least two ring oscillators, 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, and wherein the ring oscillators are excited into oscillation, at the same time, with the aid of the same start signal (“

1”

);

generating an external parity signal (PS) representing a logical state (“

0,”

“

1”

), where the external parity signal takes on the logical state “

1”

when and only when an odd number of the plurality of digital 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 of the ring oscillators, and wherein the external parity signal (PS) is delayed before being fed back to at least one of the external parity inputs; and

delaying the external parity signal (PS) by different time durations (τ

) before being fed back to different external parity inputs;

wherein the periodicities of the ring oscillators and the delay time durations of the external parity signal (PS) at the external parity inputs of the ring oscillators are chosen such that the sum of the periodicity of the digital output signal generated by a first of the ring oscillators, which is 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 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, which is 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 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.

15. A random number generator, comprising:

at least two ring oscillators, that comprise 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) for generating 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) for feeding back the external parity signal (PS) to an external parity input of each of the respective ring oscillators wherein the sum of the periodicity of an output signal (A ₁, A₂, . . . , A_L) generated by a first of the ring oscillators, which is 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 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 oscillators, which is 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 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.

16. The random number generator of claim 15, wherein the first parity signal generating means comprises an XOR gate (XOR) that receives the output signals (A₁, A₂, . . . , A_L).

17. The random number generator of claim 15, further comprising second parity signal generating means (xor₁, xor₂, xor₃, . . . , xor_L) for generating, 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 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, further comprising third parity signal generating means for generating 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, further comprising counting means for counting transitions of the internal parity signals (P₁, P₂, P₃, P₄, . . . , P_L) before parity signal generation.

21. The random number generator of claim 20, wherein the counting means comprises a binary counter that includes a chain with flipflops.

22. The random number generator of claim 15, further comprising starting means for generating a start signal (“

1”

) and supplying 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, a NAND gate (nand₁, nand_1,1,_2,1, nand_3,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 the ring oscillators are excited into oscillation, 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 an associated NAND gate each having 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 the at least one external parity input is an inverter 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₂, . . . , _M1) of inverters, to which the external parity signal (PS) is supplied.

29. The random number generator of claim 19, further comprising sampling means for sampling the external parity signal (PS) at a specified rate (ν

) for generating random bits (ZB) 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 for generating 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 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 for generating the 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 for sampling the external parity signals (PS) or the further parity signals (PP) synchronously at a specified rate (ν

) for generating random bits (ZB) or wherein there are sampling means that sample the super parity signal (SP) at a specified rate (v) 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 the random generator takes on a predetermined logical state (“

1”

).

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

28. A random number generator, comprising:

at least two ring oscillators, that comprise 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) for generating 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) for feeding back the external parity signal (PS) to an external parity input of each of the respective ring oscillators;

wherein connected in front of the at least one external parity input is an inverter to which the external parity signal (PS) is supplied;

wherein connected in front of all external parity inputs are inverter chains having unequal numbers (M₁, M₂, . . . , M_L) of inverters, to which the external parity signal (PS) is supplied; and

wherein the sum of the periodicity of an output signal (A₁, A₂, . . . , A_L) generated by a first of the ring oscillators, which is 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 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, which is 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 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.