Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-31
2004-09-14
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06792438
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.
Cryptography is the art and science of keeping messages secure and involves authentication, confidentiality, and integrity.
Authentication involves ensuring each entity communicating with one another is who the other entity or entities think it is. For an exemplary authentication protocol, a client requests access over a network to password protected information stored on a server. The server responds with a random challenge, such as a random number possibly combined with other information. The client encrypts the random challenge using its password as a key and returns the encrypted challenge to the server. The server encrypts the same random challenge with the client's password which the server obtains from its own password database. The server compares the two results. If the results match, the server has authenticated the client without the client ever sending its password over the network. Random number generation is therefore critical to help ensure no unauthorized entity observing an encrypted random challenge can impersonate the client by similarly responding to new random challenges.
Confidentiality involves ensuring that no unauthorized entity listening to a communication is able to extract meaningful information. Confidentiality is typically provided through data encryption which is the process of combining the original message with a cryptographic key in a well-defined manner to encrypt the message. In an ideal cryptosystem, only an entity with a decryption key can decrypt the encrypted message. By ensuring that the decryption key cannot be predicted or replicated and that only the intended recipient of the message has the required decryption key, the message can be protected from observation by an unauthorized entity. Cryptographic keys can be symmetric or asymmetric. Symmetric keys are used for both encrypting and decrypting data. Asymmetric keys are produced in pairs, each pair consisting of a public key to encrypt data and a private key to decrypt data. The strength of a cryptosystem lies in the strength of the key which is a function of not only the number of bits in the key but also the randomness of the number used to generate the key. Random number generation is therefore critical to help ensure the confidentiality of a message.
Integrity involves ensuring no undetected changes are made to a communication. Digital signatures help maintain the integrity of a message. A digital signature is a fixed-length binary string unique to a given message and signed with a private key. The unique string is known as a message digest or cryptographic hash. Because the unique string is signed with the originator's private key, any entity with the originator's public key can decrypt the message and know the owner of the private key originated the message. By generating another hash of the message using the same hashing algorithm as the originator and comparing the new hash with the signed hash, the recipient can verify that the message did not change after leaving the originator. Random number generation is critical to the strength of a signature generated using random numbers to avoid forgery of the signature.
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 set.
Typical computer programs use software random number generators as a random number generator may then be added to a computer system with relative ease. Software random number generators typically require a seed which is used as an operand in a mathematical algorithm to create a random number. The sequence of numbers generated by such software random number generators will eventually repeat, however, and are therefore better characterized as pseudo random numbers. Incorporating randomness into the seed and using sufficiently long mathematical computations help to generate numbers with relatively more randomness. Typically, the seed is generated from bits of data collected from the computer system, such as the clock, running processes, status registers, keystrokes, key press timing, and mouse movements, for example. System interrupt and event handling within different computer systems, however, may reduce the effective randomness of at least some of these seed sources.
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: 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: 5871400 (1999-02-01), Yfantis
patent: 6026016 (2000-02-01), Gafken
patent: 6061702 (2000-05-01), Hoffman
patent: 6104811 (2000-08-01), Aiello et al.
patent: 6193607 (2001-02-01), Kay
patent: 6195433 (2001-02-01), Vanstone et al.
patent: 6209098 (2001-03-01), Davis
patent: 6324558 (2001-11-01), Wilber
patent: 6480072 (2002-11-01), Walsh et al.
patent: 6480869 (2002-11-01), Fujioka
patent: 4006251 (1991-04-01), None
patent: WO 00/59153 (2000-10-01), None
patent: WO 00/59153 (2001-01-01), None
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 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.
Dover Lance W.
Kynett V. Niles
Wells Steven E.
LandOfFree
Secure hardware 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 Secure hardware random number generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secure hardware random number generator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3189247