Data processing: measuring – calibrating – or testing – Measurement system in a specific environment – Electrical signal parameter measurement system
Reexamination Certificate
2002-03-26
2004-01-06
Barlow, John (Department: 2863)
Data processing: measuring, calibrating, or testing
Measurement system in a specific environment
Electrical signal parameter measurement system
C702S081000
Reexamination Certificate
active
06675113
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains to the field of random number generators and, in particular, to a digital data processing apparatus and method for generating true binary random sequences.
2. Description of the Related Art
Random-number generators are fundamentally important in this computer age. A truly random sequence is difficult to generate in real application. For example, heat is typically generated in the hardware component of the random number generator when it generates a series of 1's and 0's over a time period. Generating a 1 bit could consume more power than a 0 bit. As such, if a long sequence of 1 bits is generated, the electrical circuit becomes hot. Thus, if the circuit generates a 1 bit when it is hot, the circuit will “latch up” and generate mostly 1 bits but rarely a 0 bit. A different effect may occur if a 0 bit is generated when the circuit is hot. In this case a long sub-sequence of 1 bits becomes too rare and constitutes a non-random property. In random sequences where occasionally long sub-sequences consist of equal bits of long 0's or 1's, the biased 0/1 frequency error will have catastrophic consequences of breaching security.
Accordingly, both the detection of hardware tampering and a component failure are necessary when conducting randomness tests. Conventional randomness tests are performed through extensive statistical testing, such as chi-squared tests, delta tests, and the like, on a sequence of generated random numbers. However, such tests are very expensive to be performed in real time as they require a great amount of computational processing power.
SUMMARY OF THE INVENTION
The present invention overcomes the above-described problems, and provides additional advantages by providing a method and apparatus for providing an on-line randomness test to ensure that the generated random numbers are less susceptible to crypto-analysis by an unauthorized party.
According to an aspect of the invention, a method for testing randomness is provided. The method includes the steps of: generating a continuous stream of random binary bits; applying the generated random bits to an exponential monobit-run frequency operation to compute average monobit-run frequency values for a range of monobit-run length values; and, determining whether the generated random bits are sufficiently random by comparing the output of the exponential monobit-run frequency operation to a predetermined acceptance range, wherein the exponential monobit-run frequency operation involves identifying a plurality of sub-sequences having one of all 0's or 1's bit subsequences in a row. The method further includes the steps of: determining that the generated random bits are insufficiently random when any of the average monobit-run frequency value falls repeatedly outside the predetermined acceptance range more than a predefined number of times; notifying that the generated random bits are insufficiently random when any of the average monobit-run frequency value falls repeatedly outside the predetermined acceptance range more than a predefined number of times; generating a new set of random binary bits when any of the average monobit-run counts falls repeatedly outside the predetermined acceptance range more than a predefined number of times; and, denying the generated random bits for a subsequent application when the generated random bits are determined to be insufficiently random.
According to another aspect of the invention, a method for evaluating the random numbers generated by a random number generator is provided. The method includes the steps of: (a) generating a stream of random bits using the random-number generator; (b) applying the generated random bits to a monobit-run length operation; (c) applying the output of the monobit-run length operation to an exponential averaging to obtain average monobit-run frequency values for a range of monobit-run lengths; (d) comparing the average monobit-run frequency values to a predetermined acceptance range; and, (e) determining whether any of the average monobit-run frequency values falls outside the predetermined acceptance range more than a predefined number of times. The method further includes the steps of repeating the steps (a)-(e) until any of the average monobit-run frequency values falls outside the predetermined acceptance ranges; notifying that insufficiently random numbers are generated when the steps (a)-(e) are repeated more than the predefined number of times. The generated random bits are considered insufficiently random when any of the average monobit-run frequency values falls outside the predetermined acceptance range more than the predefined number of times.
According to a further aspect of the invention, an apparatus for evaluating the random numbers generated by a random number generator is provided. The apparatus includes means for generating random sequences comprising of binary bits; means for detecting whether the generated random sequences are insufficiently random based on an exponential monobit-run frequency operation; and, means for controlling the flow of the generated random sequences for a subsequent application when the generated random sequences are determined to be insufficiently random, wherein the exponential monobit-run frequency operation is performed to compute average number monbit-run frequency values for a range of monobit-run lengths on the generated random sequences and wherein, if the any output of the exponential monobit-run operation repeatedly falls outside a predetermined acceptance range more than a predefined number of times determining that the generated random sequences are insufficiently random. The apparatus further includes means for transmitting an alarm signal that the generated random sequence is insufficiently random when any of the average monobit-run frequency values falls repeatedly outside the predetermined acceptance range more than the predefined number of times, and means for generating a new set of random bits when any of the average monobit-run frequency values falls repeatedly outside the predetermined acceptance range more than the predefined number of times.
Yet another aspect is that the present invention may be implemented in hardware, software, or a combination of hardware and software as desired for a particular application.
Furthermore, the present invention may be realized in a simple, reliable, and inexpensive implementation.
These and other advantages will become apparent to those skilled in this art upon reading the following detailed description in conjunction with the accompanying drawings.
REFERENCES:
patent: 5675649 (1997-10-01), Brennan et al.
patent: 5781458 (1998-07-01), Gilley
patent: 6076097 (2000-06-01), London et al.
patent: 6104811 (2000-08-01), Aiello et al.
Johansson, A.J.;“Analysis of Formal Randomness in a Chaotic Random Number Generator”; Proceedings 43rdIEEE Intrnt'l Symposium on Circuits and Systems; vol. 2, Aug. 8-11, 2000; pp. 724-725.*
Kohda, T:“Eigenvalue of Pseudorandom Number Generator Determining Randomness of Random Sequence”;IEEE Intrnt'l Symposium on Circuits and Systems; vol. 2, Jun. 11-14, 1991; pp. 1109-1112.
Barlow John
Koninklijke Philips Electronics , N.V.
Washburn Douglas N
LandOfFree
Monobit-run frequency on-line randomness test does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Monobit-run frequency on-line randomness test, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Monobit-run frequency on-line randomness test will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205122