Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-31
2004-02-03
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06687721
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of computer systems. More particularly, the present invention relates to the field of random number generators for use by computer systems.
2. Description of Related Art
Random number generators may be used for a variety of electronic applications, such as lotteries, gambling machines, video games, image processing and reconstruction, music and graphics composition, scientific and financial modeling simulation, program and algorithm testing, equation-solving, and computer security for example. For computer security applications such as cryptography, digital signatures, and protected communication protocols, for example, random numbers are a fundamental building block for strengthening and securing the confidentiality of electronic communications.
Random numbers are a sequence of independent numbers with a specified distribution and a specified probability of falling in any given range of values. An ideal random number generator provides a stream of uniformly distributed, non-deterministic, independent bits over an infinite data.
Random number generators generate and output random bits each with some amount of entropy or randomness depending on how the random bits are generated. A single bit can have anywhere between zero entropy, that is the single bit has a fully predictable value, and full entropy, that is the single bit has a fully unpredictable value, depending on the quality of the random number generation scheme used to generate the single bit. For typical random number generators, transient perturbations, such as injected noise or periodic phase correlation between oscillators in the random number generator for example, can reduce the entropy of generated random bits.
To compensate for such reduced entropy, typical random number generators inject the generated random bits into an entropy accumulator. One typical entropy accumulator is known as a linear feedback shift register (LFSR) and comprises a series of latches with an output random bit flowing back to the input of the LFSR. Each random bit input to the LFSR is typically exclusive-ORed with the random bit being output from the last latch in the LFSR, with the exclusive-OR result being input to the first latch in the LFSR. One or more random bits output from the first or an intermediate latch may also be exclusive-ORed with the random bit being output from the last latch in the LFSR, with the exclusive-OR result being input to the next latch in the LFSR. As a result, the random bits output from the LFSR have an entropy approximating the average entropy injected into the LFSR. The LFSR therefore effectively filters out instantaneous reductions of entropy.
The random bit output from the last latch in the LFSR, however, is also output by the random number generator and therefore becomes known. That random bit therefore has zero entropy with respect to the random bits not yet output and therefore does not contribute to the entropy added to the first latch through the first exclusive-OR operation. Because the amount of entropy output by the LFSR can exceed the amount of entropy injected into the LFSR and because the LFSR state can be derived by reading n bits of output, where n is the number of latches in the LFSR, propagating random bits through an LFSR in this manner offers relatively minimal entropy accumulation.
REFERENCES:
patent: 3790768 (1974-02-01), Chevalier et al.
patent: 4578649 (1986-03-01), Shupe
patent: 4694412 (1987-09-01), Domenik et al.
patent: 4791594 (1988-12-01), Harney et al.
patent: 4810975 (1989-03-01), Dias
patent: 4855690 (1989-08-01), Dias
patent: 5007087 (1991-04-01), Bernstein et al.
patent: 5473692 (1995-12-01), Davis
patent: 5539828 (1996-07-01), Davis
patent: 5568552 (1996-10-01), Davis
patent: 5627775 (1997-05-01), Hong et al.
patent: 5706218 (1998-01-01), Hoffman
patent: 5778069 (1998-07-01), Thomlinson et al.
patent: 5778070 (1998-07-01), Mattison
patent: 5781458 (1998-07-01), Gilley
patent: 5805712 (1998-09-01), Davis
patent: 5828753 (1998-10-01), Davis
patent: 5835594 (1998-11-01), Albrecht et al.
patent: 5844925 (1998-12-01), Dent
patent: 5844986 (1998-12-01), Davis
patent: 6026016 (2000-02-01), Gafken
patent: 6061702 (2000-05-01), Hoffman
patent: 6104811 (2000-08-01), Aiello et al.
patent: 6195433 (2001-02-01), Vanstone et al.
patent: 6209098 (2001-03-01), Davis
patent: 6253223 (2001-06-01), Sprunk
patent: 4006251 (1991-04-01), None
patent: WO 00/59153 (2000-10-01), None
patent: WO 00/59153 (2001-01-01), None
U.S. patent application No. 09/540,915, filed Mar. 31, 2000, entitled Secure Hardware Random Number Generator, by Steven E. Wells, V. Niles Kynett and Lance W. Dover.
U.S. patent application No. 09/752,088, filed Dec. 29, 2000, entitled Integrated Circuit Chip Having Firmware and Hardware Security Primitive Device(s), by Steven E. Wells and V. Niles Kynett.
Schneier, Bruce, Applied Cryptography, John Wiley & Sons, Inc., pp. vii-xiv and 369-395 (2nd Ed., 1996).
Blum, M., et al., “Independent Unbiased Coin Flips from a Correlated Biased Source—A Finite State Markov Chain,” Combinatorica, vol. 6, No. 2, pp. 97-108 (1986).
Chor, Benny, et al., “Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity,” SIAM Journal on Computing, vol. 17, No. 2, pp. 230-261 (Apr. 1988).
Cooper, J. Arlin, Computer Security, pp. 2072-2086 (published prior to Mar. 31, 1999).
Fairfield, R.C., et al., “An LSI Random Number Generator (RNG),” published in Proceedings in Advances in Cryptology Conference on CRYPTO, pp. 203-215 (1984).
Gude, Michael, “Concept for a High Performance Random Number Generator Based on Physical Random Phenomena,” Frequenz, 39, pp. 187-190 (Jul./Aug. 1985).
Murry, Herschell F., “A General Approach for Generating Natural Random Variables,” IEEE Transactions on Computers, pp. 1210-1213 (Dec. 1970).
Santha, Miklos, et al., “Generating Quasi-Random Sequences from Slightly-Random Sources,” Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pp. 434-440 (Oct. 24-26, 1984).
Santha, Miklos et al., “Generating Quasi-random Sequences from Semi-random Sources,” Journal of Computer and System Sciences, vol. 33, No. 1, pp. 75-87 (Aug. 1986).
von Neumann, John, “Various Techniques Used in Connection With Random Digits,” Applied Mathematics Series, vol. 12, United States Department of Commerce, National Bureau of Standards, pp. 36-38 (Jun. 11, 1951).
Shift Registers, pp. 1725-1727 (published prior to Mar. 31, 1999).
U.S. patent application No. 09/283,096, filed Mar. 31, 1999, entitled Duty Cycle Corrector for a Random Number Generator, by Steven E. Wells and David A Ward.
U.S. patent application No. 09/283,769, filed Mar. 31, 1999, entitled Programmable Random Bit Source, by Steven E. Wells.
Ward David A.
Wells Steven E.
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Mai Tan V.
LandOfFree
Random number generator with entropy accumulation 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 generator with entropy accumulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random number generator with entropy accumulation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3320885