Random Number Generator

• US 20090172055A1
• Filed: 03/26/2007
• Published: 07/02/2009
• Est. Priority Date: 03/29/2006
• Status: Active Grant

• Current Assignee: Cassidian Limited (Airbus SE)
• Original Assignee: EADS Secure Networks
• Inventors: Stoffel, Roland, Radja, Patrick
• Granted Patent: US 8,209,367 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

Abstract

The invention concerns a random number generator comprising a n-bit LSFR at least one oscillator having at least one delay element introducing a variable delay in the counter feedback loop, and at least one sampling/holding device having at least one input coupled to an output of the oscillator, and at least one output coupled to a input of the LSFR, and a clock input receiving a sampling clock signal at a much lower frequency than the oscillator frequency. Said generator is for example configured to vary the delay introduced by the oscillator delay based on a number q of feedback bits among the n bits of the LSFR output, where q is a an integer such that 1≦q≦n.

Claims

1. A random number generator comprising:

a n bits linear feedback shift register, or LFSR having an input and n outputs for outputting n output bits, where n is a given integer;

at least one oscillator having an output, a feedback loop and at least one delay element introducing a variable delay into said feedback loop; and

at least one sample and hold unit having at least one input coupled to the output of the oscillator, and at least one output coupled to the input of the LFSR, and a clock input receiving a sampling clock signal (CLK1) at a much lower frequency than the frequency of the oscillator,

the generator being configured to vary the delay introduced by the delay element in the feedback loop of the oscillator as a function of a number q of feedback bits (FB1) from among the n output bits of the LFSR, where q is an integer such that 1≦

q≦

n.

2. The random number generator of claim 1, wherein:

the oscillator is a ring oscillator which comprises a number z of stages placed in cascade, where z is a determined odd integer, and a number p of distinct outputs each corresponding to the output of a respective stage, wherein p is an integer such that 1≦

p≦

n and p≦

z;

the LFSR comprises p inputs for receiving an entropy value on p bits; and

the sample and hold unit comprises p inputs respectively coupled to the p outputs of the ring oscillator, and p outputs respectively coupled to the p inputs of the LFSR for delivering the entropy value on p bits.

3. The random number generator of claim 2, wherein the ring oscillator comprises at least 2^q different delay elements, and at least one multiplexer configured to select one of the 2^q delay elements as a function of some at least of the q feedback bits.

4. The random number generator of claim 3, wherein the ring oscillator comprises a number m of multiplexers, where m is an integer such that 1≦

m≦

z, each configured to select one of the 2^q delay elements as a function of some at least of the q feedback bits.

5. The random number generator of claim 4, wherein the m multiplexers are configured to each select one out of a number 2^lk of the 2^q delay elements as a function of a number 1 of bits from among the q feedback bits, where l is an integer such that 1≦

l_k>

q for all k such that 1≦

k≦

m.

6. The random number generator of claim 5, wherein l_k=q/m for all k such that 1≦

k≦

m.

7. The random number generator of claim 1 wherein m=z.

8. The random number generator of claim 1, comprising a number p of distinct ring oscillators, where p is an integer such that 1≦

p≦

n, each having a respective output;

wherein

the LFSR comprises p inputs for receiving an entropy value on p bits; and

the sample and hold unit comprises p inputs respectively coupled to the p respective outputs of the p ring oscillators, and p outputs respectively coupled to the p inputs of the LFSR for delivering the entropy value on p bits.

9. The random number generator of claim 8, wherein each of the p ring oscillators comprises:

a number z_i of stages in cascade, where z_i is a determined integer for all i such that 1≦

i≦

p;

at least 2^qi different delay elements, where q_i is an integer such that 1≦

q_i≦

q, for all i such that 1≦

i≦

p; and

at least one multiplexer configured to select one of the 2^qi delay elements as a function of some at least of the q_i feedback bits.

10. The random number generator of claim 9, wherein each ring oscillator comprises a number m_i of multiplexers, where m_i for 1≦

i≦

p is an integer such that 1≦

m_i≦

z_i, each configured to select one of the 2^qi delay elements as a function of some at least of the q_i feedback bits.

11. The random number generator of claim 10, wherein the m_i multiplexers, for 1≦

m_i≦

z, are each configured to each select one out of a number 2^ji of the 2^qi delay elements as a function of a number j_i of bits from among the q feedback bits, where j_i is an integer such that 1≦

j_i≦

q, for all i such that 1≦

i≦

p.

12. The random number generator of claim 11, wherein j_i=q/m_i for all i such that 1≦

i≦

p.

13. The random number generator of claim 10, wherein m_i=z_i for all i such that 1≦

i≦

p.

14. The random number generator of claim 1, wherein the sampling clock signal (CLK_R2) has an unstable frequency.

15. The random number generator of claim 1, wherein the sampling clock signal has a selectively stable or unstable frequency.

16. The random number generator of claim 15, comprising an additional oscillator having at least one delay element introducing a variable delay into its feedback loop which varies as a function of a number w of feedback bits from among the n output bits of the LFSR, where w is an integer such that 1≦

w≦

n.

17. The random number generator of claim 16, wherein the additional oscillator is a ring oscillator of same structure and arranged the same way as the other oscillator.

18. Method for generating random numbers by using:

a n bits linear feedback shift register, or LFSR, having an input and n outputs for outputting n output values, where n is a determined integer;

at least one oscillator having an output, a feedback loop and at least one delay element introducing a variable delay into said feedback loop; and

at least one sampler having at least one input coupled to an output of the oscillator, and at least one output coupled to the input of the LFSR, and a clock input receiving a sampling clock signal at a much lower frequency than the frequency of the oscillator,

Wherein the delay introduced by the delay element in the feedback loop of the oscillator is varied as a function of a number q of feedback bits from among the n output bits of the LFSR, where q is an integer such that 1≦

q≦

n.

19. The method of claim 18, wherein an entropy value on p bits generated on the basis of p distinct outputs of the oscillator or on the basis of the respective outputs of p distinct oscillators is provided as input to the LFSR.

20. The method of claim 18, wherein the sampling frequency is produced by using an additional oscillator having a delay element introducing a variable delay into its feedback loop, and wherein the delay introduced by the delay element in the feedback loop of the additional oscillator is varied as a function of a number w of feedback bits from among the n output bits of the LFSR, where w is an integer such that 1≦

w≦

n.