True random number generator

True random number generation circuitry utilizes a pair of oscillators driving a pair of linear feedback shift registers, with their output being combined to generate random numbers. At least one of the oscillators is programmable with a variable frequency. One embodiment controls the variable frequency of oscillators with output from one or more sets of oscillators and linear feedback shift registers. In other embodiments, linear feedback shift register output is captured and used to control the frequency of oscillators.

FIELD OF THE INVENTION

The present invention generally relates to random number circuitry and, more specifically, to circuitry for generating true random numbers.

BACKGROUND OF THE INVENTION

A random number generator (often abbreviated as RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e., appear random. Computer-based systems for random number generation are widely used, but often fall short of this goal, though they may meet some statistical tests for randomness intended to ensure that they do not have any easily discernible patterns. Methods for generating random results have existed since ancient times, including dice, coin flipping, the shuffling of playing cards, the use of yarrow stalks in the I Ching, and many other techniques.

Pseudo-random number generators (“PRNG”s) are algorithms that can automatically create long runs (for example, millions of numbers long) with good random properties but eventually the sequence repeats exactly (or the memory usage grows without bound). One of the most common PRNGs is the linear congruential generator, which uses the recurrence Xn+1=(aXn+b) mod m to generate numbers. The maximum number of numbers the formula can produce is the modulus, m. Most computer programming languages include functions or library routines that purport to be random number generators. They are often designed to provide a random byte or word, or a floating point number, uniformly distributed between 0 and 1. Such library functions often have poor statistical properties and some will repeat patterns after only tens of thousands of trials. They are often initialized using a computer's real time clock as the seed. These functions may provide enough randomness for certain tasks (for example video games) but are unsuitable where high-quality randomness is required, such as in cryptographic applications, statistics or numerical analysis. Many operating systems provide better PRNGs with statistically more random results. Yet, they are still pseudo-random and often compute intensive.

There is general agreement that, if there are such things as “true” random numbers, they are most likely to be found by looking at physical processes which are, as far as we know, unpredictable. This unpredictability is the distinguishing factor of a true random number generator (“TRNG”). A physical random number generator can be based on an essentially random atomic or subatomic physical phenomenon whose randomness can be traced to the laws of quantum mechanics. An example of this are the Atari 8-bit computers, which used noise from an analog circuit to generate true random numbers. Other examples include radioactive decay, thermal noise, shot noise and clock drift. To provide a degree of randomness intermediate between specialized hardware on the one hand and algorithmic generation on the other, some security related computer software requires the user to input a lengthy string of mouse movements, or keyboard input. All of these random number generators utilizing physical processes are slow (in terms of computer speeds), expensive, and invariably require custom hardware that typically cannot be integrated onto an integrated circuit (“IC”).

BRIEF SUMMARY OF THE INVENTION

True random number generation circuitry utilizes a pair of oscillators driving a pair of linear feedback shift registers, with their output being combined to generate random numbers. At least one of the oscillators is programmable with a variable frequency. One embodiment controls the variable frequency of oscillators with output from one or more sets of oscillators and linear feedback shift registers. In other embodiments, linear feedback shift register output is captured and used to control the frequency of oscillators.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the present invention are useful in, for example, cryptography applications where a true random number is required. Various embodiments are a pure digital circuitry architecture that complies with true random number generator well-known/de-facto standard test suite like NIST 800-22 and/or DIEHARD. It is primarily based on 2 independent variable frequency ring oscillators (“VFRO”) whose outputs feed independent linear feedback shift registers (“LFSR”). The values provided by these LFSRs are mixed together and the resulting value provided to a software user interface. A bit part-select of the first LFSR output is used in one embodiment to modify the VFRO frequency and vice-versa, creating variable frequency of the ring oscillators in an unpredictable way.

This architecture embodiment benefits from utilizing several variable frequency ring oscillators with their variable frequencies deriving from their scrambled and interlaced phases. Validation test suite were passed with a pure digital circuitry architecture. There is no need of utilizing analog cells and the high unpredictability of the results remains guaranteed. This architecture can typically be fully modeled using RTL code and is thus fully synthesizable by computer automated tools.

Embodiments of the invention typically take place in an integrated circuit of microcontroller type but can be placed in any other kind of circuit.FIG. 1represents a simple microcontroller with a TRNG module connected as a peripheral of the microprocessor core.

FIG. 1is a drawing illustrating a microcontroller with an embedded TRNG module, in accordance with an embodiment of the invention. A microcontroller10comprises a microprocessor11being able to access peripheral circuitries like Timers15, Universal Asynchronous Receiver/Transmitter (“UART”)16, and True Random Number Generator (“TRNG”) controller17. The data exchanges are typically performed by means of the system bus20which comprises (not shown) a read data bus carrying data from peripherals to microprocessor, a write data bus carrying data from microprocessor11to peripherals, an address bus, and control signals to indicate transfer direction on system bus20. In an embodiment, since the address bus of the system bus is typically shared by all peripherals connected to the system, it is desirable to decode the values carried on this bus to select one peripheral at a time. A circuitry12acts as an address decoder by receiving the address bus (part of system bus20) signals and provides select signals21,22,23,24,25. These select signals will be typically read by peripheral circuits15,16,13,14,17, respectively, to take into account values of signals carried on system bus20.

On-chip memories13can be utilized to store the application software processed by microprocessor101. The chip10is powered by means of different set of terminals40. Terminals40comprises a series of physical access terminals (“PAD”s) to power the microcontroller10, some for providing voltage (VDD), some for providing Ground (GND). Also available are Clock43and Reset44PADs. A user application typically runs software which is loaded within on-chip memories13during startup of the microcontroller (boot section). The software located in on-chip memory13is fetched by microprocessor11by means of system bus20. The on-chip memory13is selected (signal23is active) as soon as the address value of the address bus matches the address range allocated for the on-chip memory. The address decoder12is typically designed accordingly, the address range used at startup being hard-wired in the address decoder. As a response, the memory provides the corresponding data onto the system bus20, which is read by microprocessor11, and processed accordingly. If software requires TRNG data, the microprocessor11is then instructed to load data from TRNG17using read accesses performed on the system bus20. The address value placed on system bus20causes the address decoder12to set the select signal25. TRNG module17will then provide its data on the system bus20, that will be read by microprocessor11. The software may also be aware of the availability of a data through an interrupt signal27. When set, this interrupt signal27triggers an interrupt module14. Then the interrupt controller14signals the event directly to a dedicated pin of the microprocessor11. A central interrupt module typically allows any number of interrupts to be handled by a single input pin on the microprocessor. When the microprocessor is triggered by the interrupt signal, its internal state machine interrupts the processing of the current task and performs a read access on the interrupt controller14by means of system bus20to get the source (peripheral) of interrupt. Then the software interrupt handler may performs, for example, a read access on TRNG module17to get a new data that can be used further in the software processing.

The architecture details of examples of a TRNG module17are provided inFIGS. 2-10. For these FIGs., as well as forFIG. 11following them, thin lines indicate what is typically a single bit signal, while thick lines indicate what are typically multi-bit signals, for example, thirty-two (32) bits wide in the example shown inFIG. 11.

FIG. 2is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a first embodiment of the present invention. In this example, a pair of oscillators52,62or clock generators are shown, with each oscillator52,62coupled to and providing a single bit stream signal as a clock signal120,121to a Linear Feedback Shift Register (LFSR) or counter51,61, respectively. Generally, the two LFSR polynomials (seeFIG. 12below) are different for the two LFSRs including potentially different high order terms and “taps”. In this embodiment, the first oscillator52is a variable frequency oscillator (“VFO”) providing a numerically controlled or varied frequency output clock signal120, dependent upon input select signal(s)422,423(seeFIG. 13), while the second oscillator is a fixed frequency oscillator (“FFO”)62providing a fixed frequency output clock signal121. An example of a variable frequency oscillator (“VFO”) is a variable frequency ring oscillator (“VFRO”), an example of which is shown inFIG. 13. An example of a fixed frequency oscillator (“FFO”) is a fixed frequency ring oscillator (“FFRO”) similar to the VFRO shown inFIG. 13, except that it does not contain the variable delay elements of the VFRO controlled by select signals422,423. The output signals122from the first LFSR/Counter51and the output signals123from the second LFSR/Counter61are combined in a combinational mixer module104(seeFIG. 11for an example) to generate the true random number generator (TRNG) signal124which is the output of the TRNG module17.

In this example, a means to vary the first oscillator frequency56is shown providing one or more control or select signals to the first oscillator52to dynamically vary the frequency of the output clock signals120from the first oscillator. Various such means for varying the first oscillator52frequency56are shown in subsequent FIGs. and embodiments. Other such means for varying the first oscillator52frequency56are also within the scope of the present invention.

A linear feedback shift register (LFSR)54,64is may be used instead of a binary counter in thisFIG. 2. A fixed frequency oscillator coupled to and providing clock signals to a LFSR provides a value which is “pseudo-random”, since it ultimately repeats and can therefore be predicted. Typical linear feedback shift register (LFSR) architecture details is shown inFIG. 12below. However, other methods of generating pseudo-random numbers are also within the scope of the present invention, including a non-binary code counter.

The resulting bit stream122from the first LFSR/Counter51could be predicted if a FFO were used as a first oscillator52and there were no second LFSR/Counter61, since such an LFSR/Counter51is ruled by a linear equation with a polynomial characterizing its intrinsic behavior. It is therefore a PRNG, instead of a desired TRNG. In order to create a more unpredictable system, a VFO is used as the first oscillator52and a second branch is added. This second branch includes a FFO62as a second oscillator running at a different frequency than the first oscillator52and providing a clock signal121to a second LFSR/Counter61with a polynomial different from the first LFSR/Counter51. Both LFSR/Counter51,61outputs122,123are then combined together within Combinational Mixer104to form a resulting value124which is extremely difficult to predict. Therefore it is termed a “true random number generator” (“TRNG”). The Combinational Mixer104can be made of a series of 2-input XOR cells, with each bit of the LFSR.sub.154being XORed with the corresponding bit of LFSR.sub.264(refer toFIG. 11).

FIG. 3is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a second embodiment of the present invention. This example is similar to the embodiment shown inFIG. 2, except that the second oscillator62is a variable frequency oscillator which is responsively coupled to and whose frequency is controlled or modified by a means to vary the second oscillator frequency66. As with the means to vary the of the first oscillator52frequency56inFIG. 2, various such means to vary the second oscillator frequency56are shown in subsequent FIGs. and embodiments.

FIG. 4is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a third embodiment of the present invention. This example is similar to the embodiment shown inFIG. 2, except that the means to vary the first oscillator52frequency56is responsively coupled to output signals122from the first LFSR54in order to provide pseudorandom variation of the first oscillator52frequency.

FIG. 5is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a fourth embodiment of the present invention. This example is similar to the embodiment shown inFIG. 4, except that the means to vary the first oscillator52frequency56is responsively coupled to output signals123from the second LFSR64in order to provide interlaced pseudorandom variation of the first oscillator52frequency56.

FIG. 6is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a fifth embodiment of the present invention. This example is similar to the embodiment shown inFIG. 5, except that the means to vary the first oscillator52frequency56is a first capture circuit58responsively coupled to and capturing output signals123from the second LFSR64in order to provide pseudorandom variation of the first oscillator52frequency.

The Sampling/Hold and Processing (SHP) or capture circuitry58captures the output123of LFSR64and adapts it to the number of bits of select for VFO52. This can be done, for example, by capturing a bit part-select of the LFSR64output123or combining some part of the LFSR64output123to reduce to the desired number of bit (size of select input of 52). It may use the clock signal120from VFO52to trigger the SHP circuitry. The variation of frequency can be applied at different periods of time. In this example, a timer circuitry and a comparator may be designed accordingly in SHP module58. If a pseudo random value is required for the frequency variation, one can, for example, design a LFSR within SHP module58to act as a comparison value with the embedded timer to define the period of variation. Other different circuitries can be designed in this module according to the specifications of the period variations, in accordance with an embodiment of the present invention.

FIG. 7is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a sixth embodiment of the present invention. This embodiment may be seen as a combination of other previously shown embodiments. This doubly interlaced embodiment has a first capture circuit58that is responsively coupled to output signals123from the second LFSR64and is coupled to and provides control or select signals to the first oscillator52in order to provide pseudorandom variation of the first oscillator52frequency. Similarly, a second capture circuit68is responsively coupled to output signals122from the first LFSR54and is coupled to and provides control or select signals to the second oscillator62in order to provide pseudorandom variation of the second oscillator62frequency.

FIG. 8is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a seventh embodiment of the present invention. This example is similar to the embodiment shown inFIG. 4, except that the means to vary the first oscillator52frequency56is a first capture circuit58responsively coupled to and capturing the output signals122of the first LFSR54in order to provide pseudorandom variation of the first oscillator52frequency.

FIG. 9is a drawing showing an example of a true random number generator (“TRNG”), in accordance with an eighth embodiment of the present invention. This embodiment is similar to the embodiment shown inFIG. 3. In this embodiment, both the first oscillator52and second oscillator62are variable frequency oscillators whose frequencies are controlled by output signals from a PRNG. The PRNG comprises a third oscillator53that is coupled to and provides a clock signal to a third LFSR55. The third LFSR55is in turn is coupled to and provides control or select signals to the first oscillator52and second oscillator62in order to provide pseudorandom variation of the first oscillator52and second oscillator62frequencies.

FIG. 10is a drawing showing an example of a true random number generator (“TRNG”), in accordance with a ninth embodiment of the present invention. This embodiment is similar to the embodiment shown inFIG. 3. In this embodiment, both the first oscillator52and second oscillator62are variable frequency oscillators, each controlled by a separate PRNG. A third oscillator53is coupled to and provides a clock signal to a third LFSR55, which in turn is coupled to and provides control or select signals to the first oscillator52in order to provide pseudorandom variation of the first oscillator52frequency. Similarly, a fourth oscillator63is coupled to and provides a clock signal to a fourth LFSR65, which in turn is coupled to and provides control or select signals to the second oscillator62in order to provide pseudorandom variation of the second oscillator62frequency.

FIG. 11is a drawing illustrating Combinational Mixer details104, in accordance with one embodiment of the present invention. In this example, the two input signals In1122and In2123are thirty-two (32) bits wide/long. They are combined by adding (XOR) the corresponding bits from In1122and In3123to generate a corresponding thirty-two bit output signal Out124. This is exemplary, and other methods of combining input signals and the sizes or widths of input and output signals are also within the scope of this invention.

The value returned on the data bus, part of system bus20inFIG. 1, is the (in this example thirty-two bit) Out signal124, output of Combinational Mixer module104. Depending on features of TRNG module17(configurable module with enable/disable of the module activity, modifiable polynomials), it is desirable for user configurable registers and status information that can be accessed through the system bus of a microcontroller as described inFIG. 1, so that the output signal124can be multiplexed with other data (e.g. configuration registers, status of module14) prior to being sent on data part of system bus20. An example of waveforms of circuitry ofFIGS. 2-10is described inFIG. 15.

FIG. 12is a drawing illustrating details of an example of a Linear Feedback Shift Register (“LFSR”), in accordance with an embodiment of the present invention. In its minimal architecture, a typical LFSR comprises a shift register whose elements are made of (clocked) D Flip-Flops (“DFF”)203,204, . . . ,208connected in series. The first DFF203is driven by the sum of several DFF205,207outputs (“taps”). The sum may be physically implemented with a series of XOR gates200,201,202. This circuitry acts like a well known binary counter by repeating a sequence of binary values. The sequence is not ruled like the binary counter with a simple formula like Xt1=Xt0+1 (where t0, t1represents time for each clock cycle of the CLOCK signal) but rather uses the formula:
Xt=1+T1·X1+T2·X2+ . . . +TN·XN
where XNrepresents the value of NthDFF of the series and TNis zero (0) if there is no logical combination/connection of NthDFF output to 1stDFF input, 1 if there is (the “taps”). This is one form for the characteristic or feedback polynomial describing a given LFSR. Depending on the connections (or taps), the length of the sequence differs but it is no longer than 2*expN−1 whereas a classical binary counter sequence length is 2*expN(0 has no lock effect). A logical zero (0) for all DFF outputs would lock the repetition of binary sequence. To avoid such a lock state for any reason and to get the complete sequence, the circuitry detects a zero (0) on all DFFs except the last, and forces a one (1) on the first DFF (203) input in this case. This is physically implemented in this example with a NOR gate209. So, if the numeric value “0000 . . . 01” is present on DFF outputs (‘1’ being the value of the last DFF208, right location in the schematic), the next value will be 0000.00 because the last DFF208input is driven by a 0 and first DFF203input receives the value of feedback plus (+)202correction from NOR gate209=>‘1’+‘1’=‘0’ (base 2). For this new sequence value (all 0s), the zeros (0s) detection on “all outputs except the last one” is still active and forces a one (1) at the input of the first DFF203by adding (XOR)202in the output of the NOR gate209(‘1’+‘0’ from feedback), thus preventing the lock state. Therefore NOR gate209allows the maximum possible length of a sequence for a LFSR based circuitry.

FIG. 13is a drawing illustrating a typical programmable variable frequency ring oscillator (“VFRO”), in accordance with one embodiment of the present invention. A VFRO is one example of a variable frequency oscillator52shown inFIGS. 2-10above, and VFRO is an example of a programmable variable frequency clock generator. Variable frequency ring oscillators can be constructed by modifying Fixed Frequency Ring Oscillators (“FFRO”), which are example of Fixed Frequency Oscillators (“FFO”)62shown inFIGS. 2,4,5,6, and8above, and which are, in turn, examples of fixed frequency clock generators. FFROs can be constructed of an odd number of inverters407.408,409connected in series where the last inverter409output feeds directly the first inverter401input and is fed back to drive its first inverter401.

Due to intrinsic delay of combinational cells such inverters, a fixed frequency ring oscillator (FFRO) generates approximately a square wave at the output (120,121). The discrepancies with a true square wave are primarily due to the difference of propagation delays for CMOS cell when its output switches from 0 to 1 or 1 to 0, typically resulting from the performance difference between p-type and n-type transistors. If all inverters of the ring oscillator have the same electrical characteristics, Tpd—hl=propagation delay high-to-low and Tpd—lh=propagation delay low-to-high, then the ring oscillator frequency is:
Freq=1/(N×(Tpd—hl+Tpd—lw))MHz
if Tpd—hland Tpd—lhare given in microseconds. The frequency typically depends on temperature and voltage because propagation delay of cells depend also on these factors. The variation of frequency also depends on the manufacturing technology, therefore two circuits embedding the same architecture will typically not exactly generate the same frequency even if temperature and voltage are strictly the same. This is a good point for unpredictability in random number generation. To get a number from a frequency signal, an integration may be performed. But a basic integration performed by a binary counter clocked by output of the ring oscillator provides an image of the phase of the signal but remains linear and therefore highly predictable.

To improve the unpredictability of the circuitry described onFIG. 2, a ring oscillator can be modified to run at a programmable frequency. In order to make a true random number generator, the variation of frequency generally should be unpredictable or difficult to estimate. A variation of frequency can be achieved by modifying the number of basic delays (inverters or others) of the ring oscillator. Typically, in order to make the ring oscillator programmable, it should typically be possible to bypass basic delays or not according to a select input. Multiplexers can be used for this purpose.

InFIG. 13, programmable basic delay elements410and411are added in the ring. Each delay is realized by means of the intrinsic propagation delay of inverters401,402and multiplexer403or404,405and multiplexer406. These delay elements are non inverting of the logical level since each delay increment utilizes an even number of inverters. Thus, if the number of fixed basic delay elements (407,408,409) is odd, the number of programmable delay elements should be even, resulting in an odd total number of delay elements. The input of multiplexers403,406allows a modification of the delay of the ring. For example if “sel1” input (423) is cleared, multiplexer406output421is a copy of VFRO output420, a small intrinsic delay is added in the ring. If the sel1input pin423is set, multiplexer406selects output of405, therefore the added delay corresponds to two (2) inverter delays plus the input to output delay of the multiplexer406. Therefore in such case, ring total delay depends on logical value of pin “sel0”. if cleared, only programmable delay is added in the ring else two (2) inverter delays are also added.

In this example of a VFRO, two programmed delay cells410,411, are coupled in series with an odd number of inverters407,408,409to generate an output signal420. The first programmable delay cell410comprises an even number of inverters401,402, connected in series with and providing a second input to a first multiplexer403with a first multiplexer select (Sel0)422. The input of the first inverter401is the first input to the multiplexer403, and the output of the first multiplexer403is the output of the first programmable delay cell410. Similarly, the second programmable delay cell411comprises an even number of inverters404,405, connected in series with and providing a second input to a multiplexer405with a second multiplexer select (Sel1)423. The input of the first inverter404is the first input to the second multiplexer406, and the output of the second multiplexer403is the output of the second programmable delay cell411. Thus, the delay for the first programmable delay cell410is the intrinsic propagation delay of the first multiplexer403if the first select (Sel0)422is negated (0), and that of the intrinsic propagation delays of the first multiplexer403and the even number of inverters401,402, if the first select (Sel0)422is asserted (1). The second programmable delay cell411operates similarly. The length of the clock signal420is thus twice the sum of the two (or more) programmable delay cells410,411and the intrinsic propagation delays of the odd number of delay elements (inverters here)407,408,409. Other implementations and types of programmable variable frequency clock generators are also within the scope of the present invention, including voltage controlled oscillator (VCO) and other types of numerically controlled oscillators (NCO).

FIG. 14is a diagram illustrating a sample waveforms generated by the VFRO shown inFIG. 13. Depending on the number of basic programmable delays of the ring, the frequency varies. Several options exist to drive the select inputs422,423of the VFRO. Three signals are shown here, Sel0422, Sel1423, and the resulting Clock420. At the left, with both Sel0422and Sel1423negated (0), the resulting Clock420signal is a narrow square wave. The square wave Clock signal420increases in length in the middle as Sel1423is asserted (1), and increases even more when Sel0422is also asserted (1). Thus, as more selects422,423are asserted, the length of the Clock signal420square wave lengthens, and the VFRO runs at a correspondingly slower frequency.

FIG. 15is a diagram illustrating waveforms of a TRNG, in accordance with one embodiment of the present invention. Clock signals120and121are shown (outputs from Oscillators52,62) with the corresponding outputs122,123from the two corresponding LFSRs54,64. The output124from the Combinational Mixer104is shown on the bottom, based on its inputs122,123from the two LFSRs54,64. In this example, the second oscillator62is running faster than the first oscillator52, resulting in a faster clock signal123than the clock signal120from the first oscillator52. The resulting output123from the second LFSR64is thus also running faster than the output122from the first LFSR54.

Other similar and/or derivative architectures are also within the scope of the present invention. Those skilled in the art will recognize that modifications and variations can be made without departing from the spirit of the invention. Therefore, it is intended that this invention encompass all such variations and modifications as fall within the scope of the appended claims.