Cryptography – Key management – Having particular key generator
Reexamination Certificate
1999-03-31
2003-11-04
Barron, Gilberto (Department: 2134)
Cryptography
Key management
Having particular key generator
C708S250000, C708S254000
Reexamination Certificate
active
06643374
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer security, and more specifically to generating an approximately uniform duty cycle in a random number generator.
BACKGROUND OF THE INVENTION
Random number generator circuits are used in a variety of electronic applications. One important application for random number generators is in the field of computer security where message data is encrypted and decrypted. Cryptography involves the transformation of data into a coded message that is to be sent to and decoded only by the intended recipient. Most common cryptographic techniques use ciphers (or “keys”) used by the sender to encode the message and by the receiver to decode the encoded message. Common cipher systems use either a single key, one to code and decode a message, or two keys, one to encode the message and the other to decode the message.
The keys used to encode and decode messages are basically binary data patterns against which a message is processed or filtered. Effective cipher systems require the use of keys that have a sufficiently high number of bits to make replication of a key nearly impossible. Furthermore, the data patterns comprising the keys must be sufficiently random so that their pattern or the patterns in the message encoded by the key cannot be predicted. Effective cryptographic systems thus require the use of high quality random number generators to ensure that the binary data within a message is transformed in a totally unpredictable manner. In general, any lack of randomness in an encryption scheme produces some degree of correlation between the coded and uncoded data. This correlation can then be used crack the code through techniques such as iterative trial and error predictions of possible output patterns based on a coded message.
A desirable feature of a binary random number generator is that it output one and zero bits in a purely random order. Thus, the value of the output bit at any given time should be totally unpredictable. It is desirable that the duty cycle of the output of the random number generator be approximately fifty percent over an infinite sample size, so that the chance of an output being a logic low (zero) is equal to the chance of the output being a logic high (one). It is also desirable for a random number generator to exhibit low correlation (e.g., approximately zero correlation) between any bit and any other bit, and a flat Fourier distribution among the output bits.
Present known random number generators, however, have a tendency to generate an uneven number of zeros or ones over a statistically significant sample size. A common reason for prior art random number generators to exhibit an unequal duty cycle is that the latches comprising the random number generator typically favor one of the two states if data is latched during a forbidden setup/hold time. A common present method of decreasing duty cycle variations in random number generators involves the use of a Linear Feedback Shift Register (LFSR) at the output stage of a random bit source.
FIG. 1
illustrates an example of a prior art random number generator that uses a Linear Feedback Shift Register
104
coupled to the output of a random bit source
102
. LFSR
104
comprises a number of latches
105
and gates
106
through which the output bits from random bit source
102
are propagated. The states of the output bits are randomly inverted by gates
106
, and the order of the bits is further mixed up through feed-back of the bits through latches
105
.
In general, Linear Feedback Shift Registers, such as that illustrated in
FIG. 1
possess certain disadvantages and do not fully correct non-level duty cycle characteristics exhibited by typical random bit sources. As illustrated by. LFSR
104
, a typical LFSR itself comprises a number of latches and gates. These latches and gates will tend to exhibit the same propensity to latch a zero or one in certain circumstances, as the latches in the random bit source
102
. Therefore, a typical LFSR does not itself produce a uniform duty cycle output of ones and zeros, and thus cannot entirely correct any duty cycle variations in a random bit source.
A further disadvantage of Linear Feedback Shift Registers is the requirement of a large number of latches and gates. For example, a 32-bit LFSR, such as shown in
FIG. 1
, requires 32 D-type latches, as well as a number of combinatorial gates. This adds significantly to the amount of silicon area required for a random number generator circuit that uses such an LFSR.
SUMMARY OF THE INVENTION
A method and apparatus is disclosed for producing a corrected bit stream from a random bit stream output by a random bit source. Sequential pairs of bits in the random bit stream are compared. If both bits in a pair of bits are identical, the output bits are discarded. If both bits in a pair of bits are different, one bit of the pair of bits is taken as the output bit.
REFERENCES:
patent: 3706941 (1972-12-01), Cohn
patent: 3790768 (1974-02-01), Chevalier et al.
patent: 4355366 (1982-10-01), Porter
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: 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: 5987483 (1999-11-01), Edelkind et al.
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: 4006251 (1991-04-01), None
patent: WO 00/59153 (2000-10-01), None
patent: WO 00/59153 (2001-01-01), None
Schneier, “Applied Cryptography,” 2nd Edition, Oct. 1985, John Wiley & Sone, pp. 28-29, 31-34, and 398-400.*
Michael Gude, “Concept for a High Performance Random Number Generator Based on Physical Random Phenomena,” Frenquz, vol. 39, 1985, pp. 187-190.*
S. Wolfram, “Random Sequence Generation by Cellular Automata,” Advances in Applied Mathematics, vol. 7, Jun. 1986, pp. 123-169.*
International Search Report mailed Sep. 21, 2000 for PCT application No. PCT/US00/06916 (7 pages).
Blum, M., “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 Transacations 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 (publish
Ward David A.
Wells Steven E.
Barron Gilberto
Blakely , Sokoloff, Taylor & Zafman LLP
Callahan Paul E.
Intel Corporation
LandOfFree
Duty cycle corrector for a random number generator does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Duty cycle corrector for a random number generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Duty cycle corrector for a random number generator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3135141