Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-04
2003-06-17
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06581078
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of cryptology and random number generation, and more particularly, the invention relates to a random number generating circuit and process which uses a noise source and a pseudo-random number generator.
BACKGROUND OF THE INVENTION
Cryptology can be defined as the science of concealing information. It is an essential aspect of security in chip cards (IC cards) alongside with the physical security of their components and operating systems. Cryptology encompasses cryptography, which is the art of ciphering and deciphering messages, and cyptanalysis (or deciphering), which is the art of cracking secret codes.
Random number generation is one of the essential tools of cryptology. Random number generation is used, for example, in certain cryptographic protocols. Some cryptographic algorithms involve the use of binary data grouped in words several bits in length. Sometimes the bits representing the data to be encoded are too few to form a number usable by a given cryptographic algorithm. It is then necessary to generate additional bits which, for security reasons, are generated in random fashion.
Random number generation is also used when a random analog value determined by a randomly generated number is needed. Signals which are observable from outside an electronic component can be disrupted in this way. For example, in IC cards, electrical signals are accessible from various buses upon loading a secret key into the IC card's registers. A secret key of an IC card is a set of parameters which enclose the secrecy of a cryptographic algorithm. The electrical signals can betray the key's confidentiality. By using a random analog value inside the IC card, it is possible to mask the perceptibility of some confidential information, in particular the information concerning the IC card's keys.
As another example, a random number generating circuit can be used with an electronic circuit whose characteristics need to be tested. In this case it is required to supply the circuit's input with a large number of input parameters, generated in a totally random fashion, throughout the circuit's operating range. In this way, it is possible to ensure that the performance of the electronic circuit under test is not optimized only for certain expected input parameters. The random number generation circuit and process can be used in all the above mentioned applications, as well as in any other application that requires random number generation.
Most often, physical sources of noise are at the heart of random number generation. These physical noise sources are then integrated into an electronic system, such as an IC card. The electronic system comprises at least one central processing unit which manages all the operations. Physical noise sources can comprise, for example, one or several shift registers which are sampled either at a fixed frequency different from the central processing unit's operating frequency, or at variable frequency.
Bits are thus generated in a more-or-less random fashion, often in groups of eight, to form bytes. The generated bytes, which are treated as numbers, can be exploited in circuits controlled by the central processing unit. Random numbers generated in this way should satisfy a certain number of basic empirical test properties as a function of cryptographic requirements. These can be distribution, equi-distribution, or increasing or decreasing sequence tests on the generated numbers.
It is possible that the physical noise sources do not have a sufficient level of performance to succeed in of all these tests. As an example, for reasons connected with the equipment used, in particular the presence of a clock cycling all the operations managed by the central processing unit, certain bit sequences may never, or only rarely, appear at the output of the physical noise source. In terms of probability, if an event corresponds to the generation of a random number, there is then no longer an equi-probability in the set of possible events.
As explained above, physical noise sources are most often unsatisfactory with respect to certain statistical properties to which random number generators must comply in order to perform satisfactorily in the field of cryptography.
SUMMARY OF THE INVENTION
It is an object of the present invention to overcome the above-described problems. To this end, the invention provides a random number generating circuit which uses a physical noise source and which generates a random number in binary form having sufficiently good statistical characteristics to be implemented satisfactorily in cryptography.
To meet these objectives, the invention provides a pseudo-random number generating circuit which receives a digital signal at an input. The digital signal corresponds to a number previously outputted by the pseudo-random number generator, and is modified by a digital signal delivered by the physical noise source. The circuit according to the invention thus takes advantage of the statistical characteristics at the output of an appropriate pseudo-random number generator which are most satisfactory. Moreover, the physical noise source is caused to disrupt the perfectly-determined sequence from a pseudo-random number generator to ensure that the numbers outputted from the circuit according to the invention have an unpredictable character.
The invention therefore concerns a random number generating circuit for generating, from a physical noise source, a random number in binary form. The random number generating circuit includes a logic circuit having a first input receiving digital input signals obtained from a physical noise source, and a pseudo-random number generator receiving an intermediate digital signal from the logic circuit. Also, the random number generating circuit includes a memory unit receiving a digital output signal from the pseudo-random number generator and supplying a digital return signal at a second input of the logic circuit, and an output interface receiving the digital output signal from the pseudo-random number generator.
In a specific embodiment of the circuit according to the invention, the logic circuit is a two-input exclusive-OR (EX-OR) gate. In some embodiments of the circuit according to the invention, the pseudo-random number generator is a linear congruence or inverse congruence pseudo-random number generator. According to another specific embodiment of the circuit according to the invention, the physical noise source is formed by shift registers in sufficient number to produce a digital input signal having a size adapted to the pseudo-a random number generator.
Another object of the invention is to provide a random number generation process for generating a random number in binary form, including the step of generating digital input signals from a physical noise source at a first input of a logic circuit. The process further includes producing a digital output signal, corresponding to a random number, at an output of a pseudo-random number generator, from a first digital input signal, and storing the digital output signal in a memory unit. Furthermore, the process includes combining a new digital input signal and a return digital signal corresponding to the content of the memory unit by a logic circuit each time a new digital input signal is generated. An intermediate digital signal obtained from the logic circuit is sent to the pseudo-random number generator, and a digital output signal is produced at the output of the pseudo-random number generator.
REFERENCES:
patent: 4661980 (1987-04-01), Byram
patent: 5057795 (1991-10-01), Napier
patent: 5592587 (1997-01-01), Kunoff et al.
patent: 5627775 (1997-05-01), Hong et al.
patent: 6266413 (2001-07-01), Shefi
patent: 6324558 (2001-11-01), Wilber
patent: 6327661 (2001-12-01), Kocher et al.
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Jorgenson Lisa K.
Mai Tan V.
STMicroelectronics SA.A.
LandOfFree
Random number generating circuit and process does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Random number generating circuit and process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random number generating circuit and process will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3122351