Random number source and associated methods

A random number source includes a ring oscillator generating an internal clock signal having random phase noise, and a first linear feedback shift register connected to the ring oscillator. A counter is connected to a first tap of the first linear feedback shift register for generating a count signal. A feedback bit controller is connected to a second tap of the first linear feedback shift register for generating a random feedback bit for a time based upon the count signal. A second linear feedback shift register is connected to the feedback bit controller for generating a random number based upon the random feedback bit.

FIELD OF THE INVENTION

The present invention relates to the generation of random numbers, and more particularly, to a random number source and associated methods for generating a random number.

BACKGROUND OF THE INVENTION

In cryptography, true random numbers are used for generating encryption keys for encrypting information. Encryption keys should not be easily revealed to prevent the encrypted information from being decrypted by an unauthorized user. To reduce the risk of revealing encryption keys and thus circumventing the cryptographic application, true random numbers are used for generating such keys.

True random numbers for cryptographic applications are based on a true random process that is completely non-deterministic. This usually necessitates a hardware implementation instead of a software pseudo random implementation.

Generally, cryptographic quality random number sources include an array of ring oscillators for generating a true random number. The random phase jitter between the outputs of each ring oscillator is captured as entropy to produce a stream of random binary digits.

Portable military communication equipment, such as backpack radios, are battery operated and include cryptographic quality random number sources to provide high quality security. There is a requirement that this type of equipment consumes low power.

Unfortunately, ring oscillators draw large amounts of power, especially in high rate CMOS applications. For example, U.S. Patent application No. 2002/0156819 to Oerlmans discloses a true random number generator circuit comprising a plurality of ring oscillators connected to a linear feedback shift register. An output of the linear feedback shift register provides a random number.

SUMMARY OF THE INVENTION

In view of the foregoing background, an object of the present invention is to provide a random number source that consumes low power when generating random numbers.

This and other objects, advantages and features in accordance with the present invention are provided by a random number source comprising a ring oscillator generating an internal clock signal having random phase noise, and a first linear feedback shift register connected to the ring oscillator. A counter may be connected to at least one first tap of the first linear feedback shift register for generating a count signal. A feedback bit controller may be connected to a second tap of the first linear feedback shift register for generating a random feedback bit for a time based upon the count signal. The random number source may further comprise a second linear feedback shift register connected to the feedback bit controller for generating a random number based upon the random feedback bit.

The random number source in accordance with the present invention advantageously generates a true random number while consuming low power. In the prior art, a plurality of ring oscillators are used to generate the entropy or randomness of the random number. In sharp contrast, the ring oscillator in accordance with the present invention provides an internal clock signal having random noise. The first and second linear feedback shift registers accumulate the entropy or randomness for the random number being generated. Linear feedback shift registers consume less power than a plurality of ring oscillators.

The size of the first and second linear feedback shift registers may thus vary to trade off entropy versus power. In other words, larger size registers increase the entropy of the random output signal, but at the expense of more power. Smaller size registers decrease the entropy of the random output signal, but results in less power being consumed.

The random phase noise in the internal clock signal may be based upon a phase jitter between the internal clock signal and the system clock signal. The frequency of the internal clock signal is preferably greater than a frequency of the system clock signal, and the frequency of the internal clock signal may not be an integer multiple of the frequency of the system clock signal. This advantageously avoids the internal clock signal and the system clock signal from appearing to be coincidental with one another. The second linear feedback shift register may comprise a feedback path, and the random feedback bit may be input into this feedback path.

Another aspect of the present invention is directed to an encryption device comprising a random number source as defined above, and a cryptographic key generator is connected to the random number source for generating an output signal based upon the random umber.

Yet another aspect of the present invention is directed to an electronic device comprising a random number source as defined above. The electronic device may be a smart card or an electronic gaming device comprising other circuitry connected to the random number source for performing a desired operation based on the random number.

Another aspect of the present invention is directed to a method for generating a random number. The method may comprise generating an internal clock signal having random phase noise using a ring oscillator, and providing the internal clock signal to a first linear feedback shift register. A count signal may be generated using a counter connected to at least one first tap of the first linear feedback shift register. A random feedback bit may be generated for a time based upon the count signal using a feedback bit controller connected to a second tap of the first linear feedback shift register. The random number may be generated based upon the random feedback bit using a second linear feedback shift register connected to the feedback bit controller.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

A random number source10in accordance with the present invention will now be discussed. The random number source10may be used in a variety of applications requiring true random numbers. For example, an encryption device12, as shown inFIG. 1, includes a random number source10providing random numbers to a cryptographic key generator14. The cryptographic key generator14may generate random cryptographic keys, randomization vectors for an initial state of a cryptographic session or initialization vectors for the cryptographic session. A battery16powers the encryption device12and the cryptographic key generator14.

Another example application of the random number source10′ is illustrated inFIG. 2, wherein an electronic device18includes the random number source10′ for providing random numbers to other circuitry20for performing a desired operation based on the random number. The electronic device18may be, for example, a smart card or an electronic gaming device that requires the generation of random numbers. The battery16′ also powers the random number source10′ and the other circuitry20.

Referring now toFIG. 3, the random number source10as shown inFIGS. 1 and 2will be discussed in greater detail. The random number source10comprises a ring oscillator40for generating an internal clock signal at output40a. The ring oscillator40is formed by a plurality of cascade connected inverter circuits, as readily understood by those skilled in the art. The ring oscillator40is free running at a frequency set by a delay in the feedback of the oscillator design. The ring oscillator40receives at input40ba system clock signal from system clock52. The system clock52may be included with the random number source10, or it may be external the random number source.

The random phase noise in the internal clock signal is based upon a phase jitter between the internal clock signal and the system clock signal. In addition, the frequency of the internal clock signal is preferably greater than a frequency of the system clock signal, and the frequency of the internal clock signal may not be an integer multiple of the frequency of the system clock signal. This advantageously avoids the internal clock signal and the system clock signal as appearing to be coincidental with one another.

A first linear feedback shift register (LFSR)42is connected to the ring oscillator40, and is clocked by the internal clock signal at input42a. The first LFSR40is designed using a primitive polynomial. The internal clock signal functions as a seed at startup for the first LFSR42. As readily understood by those skilled in the art, the first LFSR42is made up of n shift registers that are serially connected. The shift registers may be D-type flip-flops, for example. An output44bof one of the shift registers in the first LFSR42is feedback to the other shift registers. The variable n may be between 20 and 60 bits for example.

The first LFSR42further includes a plurality of taps42c,42d,42efor outputting bits from selected shift registers. For instance, tap42cprovides a feedback bit that will be added to the feedback path of a second LFSR44. Taps42d,42eprovide respective bits to a counter46.

The counter46generates a count signal at output46abased upon the value of the bits received from taps42d,42e. The count signal is generated based upon a count cycle defined by the bits. For example, the count cycle starts when the bits received from taps42d,42eare 0,0 and the count cycle ends when the bits have cycled through 0,1; 1,0 to 1,1. The time associated with each count cycle is random. The pair of bits received by the counter46is for illustrative purposes. The actual number of bits may be equal to or greater than one as readily understood by those skilled in the art.

A feedback bit controller48receives the system clock signal at input48a, is connected to the first LFSR42for receiving the feedback bit from tap42c, and is connected to the counter46for receiving the count signal from output46a. Output48bof the feedback bit controller48provides the feedback bit to the feedback path of the second LFSR44.

The feedback bit from the first LFSR42is latched into the feedback bit controller48when the system clock signal is received. The feedback bit is latched until the count signal is received from the counter46. Even though the feedback bit controller is still receiving new feedback bits from the first LFSR42a new feedback bit is not latched until a new count signal is received.

The second LFSR44is clocked by the system clock signal at input44a. As with the first LFSR42, the second LFSR44is made up of m shift registers that are serially connected and is designed using a primitive polynomial. The variable m may be between 40 and 80 bits for example. The shift registers may also be D-type flip-flops, for example. An output of one of the shift registers in the second LFSR44is feedback to the other shift registers via output44b. However, before this bit is feedback, it is combined with the feedback bit from the feedback bit controller48via an add circuit50. The second LFSR44further includes at least one tap44cfor outputting the random number. In other words, after a large number of system clock cycles, such as 512 for example, m bits of real random data can be extracted from the second LFSR44.

The random number source10in accordance with the present invention advantageously generates a true random number while consuming low power. In the prior art, a plurality of ring oscillators are used to generate the entropy or randomness of the random number. In the present invention, the ring oscillator40provides the internal clock signal having random phase noise, and the first and second LFSRs42,44accumulate the randomness for the random number being generated. Linear feedback shift registers consume less power than a plurality of ring oscillators. In addition, the operating frequency of the ring oscillator40may be reduced to the minimum speed required to support the data rate of the random number source10. This translates directly to lower power consumption.

The size of the first and second LFSRs42,44may vary to trade off entropy versus power. In other words, larger size registers increase the entropy of the random output signal but at the expense of more power; whereas smaller size registers decrease the entropy of the random output signal but results in less power being consumed. For example, the first LFSR40may be a 41 bit register, whereas the second LFSR44may be a 67 bit register.

Another aspect of the present invention is directed to a method for generating a random number. Referring now toFIG. 4, from the start (Block100), the method comprises generating an internal clock signal having random phase noise using a ring oscillator40at Block102. The internal clock signal is provided to the first linear feedback shift register at Block104. The count signal is generated at Block106using a counter46connected to at least one first tap42d,42eof the first linear feedback shift register42. A random feedback bit is generated at Block108for a time based upon the count signal using a feedback bit controller48connected to a second tap of the first linear feedback shift register42. The random number is generated at Block110based upon the random feedback bit using a second linear feedback shift register connected to the feedback bit controller48. The method ends at Block112.