Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-08-13
2004-03-30
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06714955
ABSTRACT:
FIELD OF THE INVENTION
The present invention is in the field of encryption, and more specifically concerns a hardware solution for the implementation of a random number generator designed especially for generating encryption keys.
DESCRIPTION OF RELATED ART
The increased need for performance in cryptography combined with the need for inviolability has led the manufacturers of security systems to favor hardware solutions that are increasingly high-performance in terms of speed and random number quality.
The generator according to the invention, also called a random generator, can be associated with an additional PCI (Peripheral Component Interconnect) card for accelerating the cryptographic functions of a machine (server or station).
A card of this type coupled with a server constitutes the hardware security element of the machine.
There are two types of random number generators used in electronics.
The first type of generator is based on a random physical phenomenon such as thermal noise in a diode, radioactive emission, etc. It is called a “physical generator” in the description below.
The second type of generator is based on an algorithm fed with a “germ,” defined below, which produces as output a random number sequence with a relatively long period. It is called a “pseudo-random generator” in the description below.
A long period associated with a germ of high quality, in terms of random number quality, produces as output from a generator of this type a series of numbers that are practically unpredictable.
Physical generators are of course the only real sources of random numbers since they are completely unpredictable, but many of them are not free from correlations at the output level.
Furthermore, their speed is generally somewhat slow, on the order of several tens of kilobits per second.
Pseudo-random generators are simple to implement in software form and make it possible to supply a high random number output, on the order of several tens of megabits per second.
However, this type of generator corresponds to a deterministic process and is therefore predictable.
The quality of a random generator is difficult to assess because there is no official and standardized procedure that makes it possible to verify the more or less random nature of a series of numbers.
However, there are two series of tests for “validating” a generator of this type.
The first series of tests, called FIPS140 tests, is described in the document FIPS140-1 entitled “Security Requirements for Cryptographic Modules” issued by the American organization NIST. These tests constitute the minimum requirements for any security component wishing to claim the label “FIPS140-compliant,” one of the objectives of the present invention.
The second series of tests, developed by George Marsaglia and called DIEHARD tests, are much tougher than the FIPS tests and confer on any generator that passes all of them successfully a certain recognized level of quality.
These two series of tests are included in annexes to the present specification.
SUMMARY OF THE INVENTION
It is the specific object of the invention to eliminate the aforementioned drawbacks and to make it possible to do without a specific physical circuit such as a noise diode, while meeting the dual requirement of high speed, faster than 100 Mbits/s, and a very high quality of random numbers supplied a quality measured by the fact that the generator must successfully pass the above-mentioned FIPS140 and DIEHARD series of tests.
A high-speed random number generator (
1
) comprising a physical random number generator (
5
), having a data input, an output and a pseudo-random generator (
6
) coupled to the output of the physical generator (
5
), said pseudo random generator having an input adapted to receive a germ delivered by the physical generator and deliver at an output thereof a pseudo-random output signal, said physical generator (
5
) comprising a logic circuit (
10
) that includes at least a data input (D) and a clock input (CLK), the data input (D) receiving a first “high frequency” clock signal H
1
and the clock input (CLK) receiving a second, “low frequency” clock signal H
2
, the “high frequency” signal H
1
being sampled by the “low frequency” signal H
2
, the two clock signals H
1
and H
2
being of different frequencies respectively and issuing from two different first and second oscillators (OSC
1
and OSC
2
) operating asynchronously from one another and not adhering to the setup time of the logic circuit (
10
), the logic circuit (
10
) arranged to deliver at an output thereof a signal in an intermediate state qualified as metastable between “0” and “1” and being constituted by a random number sequence, the metastability of the signal obtained as an output from the logic circuit (1.0) being accentuated by phase noise of the first oscillator (OSC
1
) generating the “high frequency” signal H
1
, the pseudo-random generator (
6
) being arranged to re-inject part of the pseudo-random output signal into the physical generator (
5
). An internal memory (
9
) stores the random numbers obtained as output signals from the pseudo-random generator (
6
). The two generators (
5
) and (
6
) run on the same second “high frequency” clock signal H generated by an external oscillator (
7
).
The second subject of the invention is a mechanism for generating random numbers on demand, characterized in that it comprises a random number generator as defined above, a dual-port memory including a receiving buffer, coupled to the output of the generator via the bus of the generator, and in that it includes a microprocessor coupled to the dual-port memory via the microprocessor bus, communicating with the generator via the dual-port memory and posting in the dual-port memory a command word comprising an address and a count containing a maximum number of random words to be stored, and in that the buffer of the dual-port memory, at the request of the microprocessor, is fed by the internal memory of the generator until a count corresponding to a given maximum number of random numbers has elapsed, then utilized by the microprocessor.
Lastly, the third subject of the invention is a card for accelerating the cryptographic functions of a computing machine, characterized in that it supports a random number generator or a mechanism like those defined above.
The invention has the advantage of not using standard electronic circuits to produce the “physical” generator, and hence of reducing the complexity and the cost of such a generator.
REFERENCES:
patent: 4641102 (1987-02-01), Coulthart et al.
patent: 5034906 (1991-07-01), Chang et al.
patent: WO 99 61978 (1999-12-01), None
“Integrated Circuit Compatible Random Number Generator” IBM Technical Disclosure Bulletin, US IBM NY, vol. 30, No. 11, Apr. 1, 1988, pp. 333-335, XP000021682, ISSN: 0018-8689.
Petrie C S et al: “Modeling and Simulation of Oscillator-Based Random Number Generators” IEEE International Symposium on Circuits and Systems (ISCAS) US NY IEEE, May 12, 1996, pp. 324-327, XP00070462, ISBN: 0-7803-3074-9, p. 324-327.
Bull S.A.
Kondracki Edward J.
Mai Tan V.
Miles & Stockbridge P.C.
LandOfFree
High speed random number generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed random number generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed random number generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3217046