Apparatus and method for generating a random number

• US 7,647,366 B2
• Filed: 10/29/2004
• Issued: 01/12/2010
• Est. Priority Date: 04/29/2002
• Status: Active Grant

• Current Assignee: Infineon Technologies AG
• Original Assignee: Infineon Technologies AG
• Inventors: Stromberg, Guido, Stoehr, Annelie, Sturm, Thomas, Meintrup, David
• Primary Examiner(s): Do; Chat C
• Application Number:
  US10/978,241
• Publication Number:
  US 20050286718A1
• Time in Patent Office: 1,901 Days
• Field of Search: 708250-256
• US Class Current: 708/250
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

Apparatus for generating a random number includes a sampler that samples a noise signal to obtain a noise signal sample, and a provider that provides at least three noise signal threshold values selected such that a first probability of the noise signal sample being between the first and second threshold values, and a second probability of the noise signal sample being between the second and third threshold values are different from each other by less than a predetermined differential value or are identical. An outputter outputs the random number such that when the noise signal sample is between the first and second threshold values, a first digit of a random number is occupied by a first logical state, whereas a second digit is occupied with a different logical state, so that a random number which is at least 2 bits wide results from one noise signal sample.

Claims

1. An apparatus for generating a random number, comprising:

a noise source configured to generate a noise signal;

an analog-to-digital converter, coupled to the noise source, and configured to sample the noise signal to obtain a digital noise signal sample;

hardware provider logic configured to generate at least three noise signal threshold values, the at least three noise signal threshold values being selected such that a first probability of the digital noise signal sample being between the first and second noise signal threshold values, and a second probability of the digital noise signal sample being between the second and third noise signal threshold values are different from each other by less than a predetermined differential value or are identical; and

hardware output stage, coupled to the analog-to-digital converter and to the provider logic, and configured to generate the random number having at least two digits which depend on the digital noise signal sample, wherein, if the digital noise signal sample is between the first and second noise signal threshold values, a first digit of the random number obtains a first state, and a second digit of the random number, representing a range between the second noise signal threshold value and the third noise signal threshold value, obtains a second state which differs from the first state,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the hardware provider logic is configured to specify the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br><br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

2. The apparatus as claimed in claim 1,

wherein the hardware output stage comprises at least one threshold-value gate x_i into which the digital noise signal sample is fed and by which the first or second digits of the random number is determined depending on whether the digital noise signal sample exceeds or falls below the second threshold value.

3. The apparatus as claimed in claim 1,

wherein the hardware provider logic is configured to generate at least four noise signal threshold values, a smallest noise signal threshold value being a minimum noise signal sample determined by a predetermined minimum probability,

wherein a highest noise signal threshold value is a maximum noise signal sample determined by a predetermined maximum probability, and

wherein the at least two remaining noise signal threshold values are between the smallest and highest noise signal threshold values.

4. The apparatus as claimed in claim 3,

wherein each of the at least two remaining noise signal threshold values has a threshold-value gate of its own provided for it, a specific digit of the random number being determinable by each threshold-value gate, the logical state of each digit of the random number depending on whether the digital noise signal sample falls below or exceeds the threshold value associated with the respective threshold-value gate.

5. The apparatus as claimed in claim 4,

wherein at least three remaining noise signal threshold values are present, and which further comprises:

an encoder, coupled to the hardware output stage, and configured to encode the random number to obtain an encoded random number having a smaller redundancy than the random number.

6. The apparatus as claimed in claim 5,

wherein the random number and the encoded random number are binary, and the first state is a first binary state, and the second state is a second binary state differing from the first binary state.

7. The apparatus as claimed in claim 6,

wherein the encoder comprises a table, by means of which an encoded random number is uniquely associated with a random number, the encoded random number comprising fewer digits than the random number.

8. The apparatus as claimed in claim 6,

wherein the encoder is configured to implement the following logical equation:

$\begin{array}{cc}{y}_{n-i}=\underset{q<br><br>{=}^{2<br><br>{\left(n-1\right)}_{\pm <br><br><br><br>\mathrm{\dots <br><br>}<br><br>\pm <br><br>2}<br><br>\left(n-i\right)}<br><br>-1}{\oplus <br><br>}<br><br>{\hat{x}}_{q^{\mathrm{\prime <br><br>}}}<br><br><br><br>i=1,\mathrm{\dots <br><br>}<br><br>,n& \left(2\right)\end{array}$

wherein {circumflex over (x)}_q is a digit of the random number with an index q,

wherein y_n-i is a digit of the encoded random number with an index;

wherein n is the number of digits of the encoded random number;

wherein i is a control valuable running from 1 to n, and

wherein ⊕

is a modulo-2 addition of the digits X_q which are calculated by means of the following equation;

q=2<sup>(n−

1)</sup>±

. . . ±

2<sup>(n−

i)</sup>−

1.

9. The apparatus as claimed in claim 5,

wherein the hardware provider logic comprises:

a monitor configured to monitor the encoded random numbers;

a transmitter configured to transmit a statistical distribution of the encoded random numbers; and

an adapter configured to adapt the noise signal threshold values to reduce a deviation between the first and second probabilities.

10. The apparatus as claimed in claim 1,

wherein the hardware provider logic comprises:

a monitor configured to monitor the digital noise signal samples, the noise signal, or the random number;

a transmitter configured to transmit a statistical distribution of a monitored variable; and

an adapter configured to adapt the noise signal threshold values to reduce a deviation between the first and second probabilities.

11. The apparatus as claimed in claim 10,

wherein the monitor comprises a memory having a sequence of memory cells arranged in an ascending order,

wherein noise signal values or noise signal samples are sorted into the memory cell sequence depending on their magnitude,

wherein the hardware provider logic is configured to read out memory cells with equally spaced- apart ordinal numbers, each threshold value being assigned a memory cell to be read out, and

wherein the provider logic is further configured to set a noise signal threshold value to a value stored in the memory cell with the ordinal number associated with the noise signal threshold value.

12. The apparatus as claimed in claim 11, wherein re-setting of a noise signal threshold value is performed in an event of a predetermined deviation, at a predetermined point in time or in connection with a detection of a new digital noise signal sample.

13. The apparatus as claimed in claim 1,

wherein the hardware provider logic is configured

to detect a noise value defined by the digital noise signal sample,

to ascertain whether the noise value is higher or smaller than one of the noise signal threshold values,

to perform an incrementation of the noise signal threshold value by an incrementation value in an event that a “

higher”

condition has been ascertained, or to perform a decrementation of the noise signal threshold value by a decrementation value in the event that a “

smaller”

condition has been ascertained, and to use the incremented and/or decremented noise signal threshold value as an adapted noise signal threshold value.

14. The apparatus as claimed in claim 13,

wherein an adapted noise signal threshold value is formed using several iteration steps, the incrementation or decrementation value being reduced with each iteration step, and

wherein the incrementation or decrementation value is re-set to the initial value after a predetermined number of iteration steps.

15. The apparatus as claimed in claim 1, wherein the random number is used in a cryptographic application.

16. A method for generating a random number, comprising:

generating a noise signal using a noise source;

sampling the noise signal using an analog-to-digital converter, which is coupled to the noise source, to obtain a digital noise signal sample;

generating at least three noise signal threshold values using hardware provider logic, the at least three noise signal threshold values being selected such that a first probability of the digital noise signal sample being between the first and second noise signal threshold values, and a second probability of the digital noise signal sample being between the second and third noise signal threshold values are different from each other by less than a predetermined differential value or are identical; and

outputting the random number having at least two digits which depend on the digital noise signal sample using a hardware output stage which is coupled to the analog-to-digital converter and to the hardware provider logic, wherein, if the digital noise signal sample is between the first and second noise signal threshold values, a first digit of the random number obtains a first state, and a second digit of the random number, representing a range between the second noise signal threshold value and the third noise signal threshold value, obtains a second state which differs from the first state,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the step of providing includes specifying the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br><br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

17. An apparatus for generating a binary random number, comprising:

an analog-to-digital converter configured to sample a noise signal to obtain a digital noise signal sample;

hardware provider logic configured to generate at least 2ⁿ+1 noise signal threshold values, n being higher than or equal to 2, wherein the noise signal threshold values define 2ⁿ ranges for a noise signal sample, the 2ⁿ+1 noise signal threshold values being selected such that probabilities of the noise signal sample being in one of the 2ⁿ ranges differ from each other by less than a predetermined differential value or are identical; and

a hardware output stage that is coupled to the analog-to-digital converter and to the hardware provider logic, and is configured to generate the binary random number having n bits which depend on the digital noise signal sample, the n bits of the binary random number being determined such that each bit combination of the n bits of the binary random number is uniquely associated with one of the 2ⁿ ranges,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the hardware provider logic is configured to specify the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br><br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

18. The apparatus as claimed in claim 17, wherein the hardware provider logic is configured to adaptively track the noise signal threshold values.

19. A method for generating a binary random number, comprising:

generating a noise signal using a noise source;

sampling the noise signal using an analog-to-digital converter, which is coupled to the noise source,

to obtain a digital noise signal sample;

providing at least 2ⁿ⁺1 noise signal threshold values using hardware provider logic, n being higher than or equal to 2, wherein the noise signal threshold values define 2ⁿ ranges for a noise signal sample, the 2ⁿ⁺1 noise signal threshold values being selected such that probabilities of the noise signal sample being in one of the 2ⁿ ranges differ from each other by less than a predetermined differential value or are identical; and

generating and outputting the binary random number having n bits which depend on the digital noise signal sample using a hardware output stage which is coupled to the analog-to-digital converter and to the hardware provider logic, the n bits of the binary random number being determined such that each bit combination of the n bits of the binary random number is uniquely associated with one of the 2ⁿ ranges,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the step of providing includes specifying the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br><br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

20. The method as claimed in claim 19, wherein the providing step includes implementing 2ⁿ⁻

1 threshold-value gates.

21. The method as claimed in claim 19, wherein the random number is used in a cryptographic application.