Oscillators – Electrical noise or random wave generator
Reexamination Certificate
2000-04-18
2002-11-12
Kinkead, Arnold (Department: 2817)
Oscillators
Electrical noise or random wave generator
C331S057000, C331S046000, C708S250000, C708S251000, C708S252000
Reexamination Certificate
active
06480072
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to generating random numbers and more specifically to generating random numbers using an oscillator having a variable output frequency.
2. Description of the Related Art
Random numbers are used in various encryption applications, which are particularly important in providing security for e-commerce applications as well as for a wide variety of other computer based or internet based communications and transactions.
One approach to generating random numbers uses ring oscillators. In one approach using ring oscillators, a free running ring oscillator is used to clock a linear feedback shift register (LFSR). In another random number generator a single, slow voltage controller oscillator (VCO), which receives a noise input, samples the output of high speed ring oscillators.
One problem with some ring oscillators based random number generators, is that the sample frequency may be correlated to the ring oscillator frequency for a duration long enough to cause individual random number generator bits to be correlated and therefore, less random.
It would be desirable to provide a random number generator that reduces or eliminates that correlation and produces random numbers that are more unpredictably random.
SUMMARY OF THE INVENTION
Accordingly, the invention utilizes an oscillator in an open loop configuration, such as a voltage controlled oscillator (VCO), whose output frequency is randomly controlled. The VCO output signal is sampled at a frequency much lower than and asynchronous to the frequency of the VCO output signal. The frequency of the VCO output signal is made to change significantly during each sample period. Due to the asynchronous relationship between the VCO output signal and the sample clock and the significant change in frequency during the sampling period, the exact number of VCO output periods, including any fractional parts, varies during each sample period. That variation is the basis for creating unpredictable randomness.
In one embodiment, the random number generator includes an oscillator supplying an oscillator output signal having a frequency determined according to a control input. A sampling circuit, coupled to the oscillator, samples the oscillator output signal using a sample clock at a sampling frequency that is asynchronous to and lower than the frequency of the oscillator output signal. The control input to the oscillator is used to cause the oscillator output frequency to change significantly within each sample period.
The random number generator may further include an exclusive OR circuit coupled to provide a signal used in generating the control input for the oscillator, the output from the exclusive OR gate changing within each sample period thereby causing the oscillator output frequency to change significantly within each sample period.
The random number generator may use the sample clock to generate, at least in part, the control input for the oscillator. Because the sample clock changes values within each sample period, the oscillator output frequency changes within each sample period.
The random number generator may also include a linear feedback shift register whose outputs are coupled to generate at least, in part, the control input to the oscillator. One of the outputs of the linear feedback shift register is provided to an exclusive OR circuit, which supplies one of the signals (preferably the most significant bit) used to generate the control input to the oscillator. The oscillator also receives a clock signal such as the sampling clock, thereby ensuring that the oscillator output signal changes significantly during each sampling period.
The random number generator may further include a distilling circuit coupled to the sampling circuit.
In another embodiment, the invention provides a method of supplying an oscillator output signal having a frequency determined according to a control input. A sampling circuit samples the oscillator output signal using a sampling clock at a sampling frequency lower than and asynchronous to the frequency of the oscillator output signal and supplies a sampled output signal. The oscillator output frequency is changed significantly during each sampling interval using the control input.
The method may further include shifting the sampled output signal into a linear feedback shift register, generating pseudo random numbers in the linear feedback shift register and generating the control input using the pseudo random numbers.
The method may further include logically combining one of the outputs of the linear feedback shift register and the sample clock signal in an exclusive OR circuit and providing an output from the exclusive OR circuit to generate, at least in part, the control input, to ensure that the output frequency of the oscillator changes greatly during the sample period.
The method may further include shifting successive outputs from the sampling circuit into a distilling circuit to generate an N bit random number.
REFERENCES:
patent: 4694412 (1987-09-01), Domenik et al.
patent: 4810975 (1989-03-01), Dias
patent: 4905176 (1990-02-01), Schulz
patent: 5007087 (1991-04-01), Bernstein et al.
patent: 5706218 (1998-01-01), Hoffman
patent: 5961577 (1999-10-01), Soenen et al.
patent: 5963104 (1999-10-01), Buer
patent: 0 095 272 (1983-11-01), None
Jun and Kocher, “The Intel® Random Number Generator”, Cryptography Research, Inc. White Paper Prepared for Intel Corporation, Apr. 22, 1999, pp. 1-8.
Fairfield, Mortenson, et al., “An LSI Random Number Generator (RNG)”,Advances in Cryptology: Proceedings of CRYPTO 84, Springer-Verlag, 1985, pp. 203-230.
Schneier, “Protocols, Algorithms, and Source Code in C”, Applied Cryptography, 1996, pp. 423, 678, and 697.
Biesterfeldt Randall Paul
Walsh James J.
Advanced Micro Devices , Inc.
Kinkead Arnold
Zagorin O'Brien & Graham LLP
LandOfFree
Method and apparatus for generating random numbers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating random numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating random numbers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2950710