Robust random number generator

Details Robust random number generator Robust random number generator

1999-12-07

2001-06-26

Malzahn, David H. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S003000

Reexamination Certificate

active

06253223

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates in general to random number generators and more specifically to random number generators which use both digital and analog random number sources.
Random number generators are used for a variety of purposes such as cryptography. Correct use of cryptography depends on a statistically high quality source of random numbers. Unfortunately, conventional random number generators (“RNG”) have disadvantages.
Simple random number generators use digital techniques to produce pseudorandom numbers. Pseudorandom numbers are substantially or highly random numbers which are produced by a digital process. Digital techniques can produce pseudorandom numbers which are deterministic because of their digital nature. In other words, two identical digital random number generators produce the same pseudorandom number when the digital input values are the same. Accordingly, digital techniques produce less than ideal results because the pseudorandom numbers are predictable.
A common digital technique for generating a random number is a linear congruential generator algorithm. This algorithm iterates to produce an output which is used as the seed for the next output. However, the sequence of random numbers produced by this technique is small and repeats after a relatively small number of distinct outputs. An orbit is defined herein as the number of outputs the digital random number generator produces until one output is the same as a previous output. As can be appreciated, a recursive algorithm will produce unique outputs in the orbit until an output is repeated. Once the first value repeats, the subsequent values will also be repeats. A repeating pattern is undesirable since it is predictable. This algorithm is found in most C programming language libraries.
To provide robust random numbers, conventional systems rely upon analog random number generators. Analog random number generators produce a stream of random numbers which do not have a periodic orbit like the digital random number generators. These analog random number generators typically convert a random analog voltage, such as noise, into a digital stream of random data. These circuits are typically separate integrated circuits which generate a stream of random numbers at a rate of 100 Kbits or less. However, these random number generation rates are inadequate for very high performance cryptography, where a large number of random bits is needed in a short period of time.
Analog random number generators are prone to failure. The lifetimes of analog random number generators are considerably less than the digital circuits which use the random numbers. As can be appreciated by those skilled in the art, failure of the analog random number generator can defeat effective cryptology. Additionally, the source of the analog voltage used to generate the random number is vulnerable to control by an attacker. Accordingly, there is a need for more reliable analog random number generators which are less vulnerable to attack.
Analog random number generators are typically located on a separate integrated circuit from the digital circuits which use the random numbers because digital semiconductor processes are generally incompatible with analog semiconductor processes. Digital integrated circuits typically have high gain and are optimized for fast CMOS switching. However, analog random number generators require linear analog characteristics to effectively amplify the source of the random voltage in order to randomly produce a digital data stream. Modifying the digital semiconductor process to create better analog characteristics is possible, but the digital circuit performance would be adversely affected. Accordingly, integrating an analog random number generator on the same integrated circuit is very difficult with conventional techniques.
Additionally, an analog random number generator located on an integrated circuit separate from the integrated circuit containing the digital cryptographic function is prone to attack. More specifically, the trace on the circuit board which carries the random number to the cryptographic function is vulnerable. For example, an attacker can manipulate or replace the signal from the analog random number generator. As those skilled in the art can appreciate, this attack would render the cryptographic algorithm and keys more easily determinable.
In summary, it is desirable to develop a random number generator which reliably produces random numbers at a high data rate. Additionally, the random number generator should accommodate integration with digital circuits on the same integrated circuit.
SUMMARY OF THE INVENTION
According to the invention, methods and an apparatus for generating random numbers are disclosed. In a first embodiment, a method for generating random numbers involves producing a second random number. A pseudorandom number is produced from a digital random number generator and a first random number is produced from an analog random number generator. The first random number is combined with the pseudorandom number to produce a second random number that is a result of both generators' outputs.
In another embodiment, a method generates a random number using a cryptographic function. A pseudorandom number is generated from an output of the cryptographic function and a first random number is generated from an analog random number generator. The pseudorandom number and the first random number are coupled to an input of the cryptographic function in order to generate a second random number from the output of the cryptographic function where the second random number is related to the pseudorandom number and first random number.
In yet another embodiment, a random number generator apparatus having an output, a digital random number generator and an analog random number generator. The digital random number generator produces a pseudorandom number. The analog random number generator generates a random number. The random number generator's output is coupled to both the digital and analog random number generators.


REFERENCES:
patent: 5627775 (1997-05-01), Hong et al.
patent: 6070178 (2000-05-01), Anderson et al.
patent: 6104810 (2000-08-01), DeBellis et al.
patent: WO 97/05720 (1997-02-01), None

Affiliated with

Also associated with

Rating

Robust 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 Robust random number generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust random number generator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2499299