Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-04-23
2004-10-19
Malzahn, D. H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S251000, C708S255000
Reexamination Certificate
active
06807553
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates, in generals to circuits and techniques for generating random numbers, and in particular to digital semiconductor circuits for generating true random numbers.
2. Discussion of the Background
In cryptographic applications, for example, true random numbers are used as an encryption key for encrypting information and messages.
Such an encryption key may not be revealed easily, in order to prevent the encrypted information from being decrypted by an unauthorised person or entity.
To reduce the risk of revealing an encryption key and thus circumventing the cryptographic application, true random numbers are used for generating such a key.
However, in digital electronics, the generation of true random numbers is often deterministic and thus vulnerable to cryptographic attack, since all numbers can be predicted from the present state of the generator. In fact, a list of pseudo-random numbers is obtained with a repetitive and predictable pattern.
U.S. Pat. No. 4,905,176 discloses a digital random number generator semiconductor circuit, wherein a linear feedback shift register is driven by a system clock and an input signal delivered by a free running oscillator.
From the frequency signal delivered by the free running oscillator a noise signal is produced, to drive the linear feedback shift register. This noise signal disrupts the generation of pseudo-random numbers by the linear feedback shift register following the system clock, thereby making the generated random numbers true random numbers.
However, as will be appreciated by those skilled in the art, in semiconductor circuits, in particular in integrated semiconductor circuits, among others due to temperature and capacitive coupling effects, oscillation devices such as the free running oscillator and the system clock may “lock ” onto each other. If this occurs, the random numbers generated by the linear feedback shift register will become deterministic and predictable.
Thus, the generated true random numbers will become pseudo-random numbers, once the free running oscillator and the system clock have locked.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an improved digital true random number generator circuit, wherein the above described “locking” will hardly or not occur and wherein the linear feedback shift register remains driven by “real” noise, thus generating true random numbers.
In order to accomplish the above objective, the invention provides a digital true random number generator circuit, comprising a linear feedback shift register having an input and an output, a system clock having a system clock frequency value for driving the shift register, and a free running oscillator operatively connected to the input of the shift register. The true random number generator circuit of the invention further comprises at least one further free running oscillator operatively connected to the input, which oscillators and the system clock having different oscillation frequency values, the greatest common divisor of which having the value one.
The use of multiple free running oscillators as noise generators in accordance with the present invention, which free running oscillators have oscillation frequency values which differ among each other and with the system clock frequency value such that the greatest common divisor of these frequency values has the value one, effectively minimises the risk of “locking”.
If, for example, one of the free running oscillator “accidentally” locks on the system clock and thus making the oscillator unsuitable for generating “true” noise and true random numbers, still “true” noise (and thus true random numbers) will be generated by the other unlocked free running oscillator or oscillators.
This, because the other free running oscillator or oscillators has or have an oscillation frequency value which differs from the “locked” oscillator and also differs from the system clock frequency value in that the greatest common divisor of these values equals one, as a result of which locking of the other oscillator or oscillators is not possible such that random noise, i.e. true random numbers, always will be generated.
In an embodiment of the true random number generator circuit according to the invention, each free-running oscillator is designed as a ring oscillator, having a plurality of cascade connected inverter circuits, providing a fully digital circuit which can be easily integrated on a (digital) semiconductor chip. Each ring oscillator preferably has an odd number of inverter circuits. Preferably, the number of inverter circuits of each ring oscillator differs by two.
In another embodiment of the invention the output of each ring oscillator is operatively connected to a separate input of an exclusive OR-circuit.
In a yet further embodiment of the invention, the exclusive OR-circuit has an output which is operatively connected to an input of a latching circuit; the system clock operatively connects to a clock input of the latching circuit; and the latching circuit having an output which is operatively connected to the input of the linear feedback shift register, for driving the shift register. The latching circuit may, for example, be a D-type flip flop or equivalent.
In a preferred embodiment of the digital true random number generator circuit according to the invention, the linear feedback shift register has a plurality of n cascade connected delay stages, these stages being divided into a first sub-plurality of i stages having an output operatively connected as a first input to a further exclusive OR-circuit; the output of the linear feedback shift register being operatively connected to an input of a NOR-circuit; the NOR-circuit having an output which operatively connects to a second input of the further exclusive OR-circuit; and the further OR-circuit having a third input which forms the input of the linear feedback shift register, for driving the register. The value of i may range from 1 up to n.
The digital true random number generator circuit according to the invention may be designed as or may form part of an Application Specific Integrated Circuit (ASIC).
The invention further relates to an encryption device comprising means for encrypting and provided with a digital true random number generator circuit as disclosed above, and a transactions terminal, comprising means for performing transactions and provided with a digital true random number generator circuit according to the invention.
REFERENCES:
patent: 4799259 (1989-01-01), Ogrodski
patent: 4905176 (1990-02-01), Schulz
patent: 5117380 (1992-05-01), Tanagawa
patent: 5706218 (1998-01-01), Hoffman
patent: 6065029 (2000-05-01), Weiss
patent: 6240432 (2001-05-01), Chuang et al.
patent: 6480072 (2002-11-01), Walsh et al.
patent: 6522210 (2003-02-01), Dvorak et al.
patent: 2001/0012364 (2001-08-01), Einfeldt et al.
Malzahn D. H.
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
SafeNet B.V.
LandOfFree
Digital true random number generator circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital true random number generator circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital true random number generator circuit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3268557