Cryptography – Equipment test or malfunction indication
Reexamination Certificate
2000-09-18
2004-09-28
Gregory, Bernarr E. (Department: 3662)
Cryptography
Equipment test or malfunction indication
C380S044000, C380S046000, C380S059000, C708S250000
Reexamination Certificate
active
06798883
ABSTRACT:
(U) FIELD OF THE INVENTION
(U) The present invention relates, in general, to measuring and testing and, in particular, to testing of apparatus (i.e., a randomizer).
(S) BACKGROUND OF THE INVENTION
(U) The operation of a wide range of devices is based on a number that should not be easy to predict (e.g., lottery devices, cryptographic devices, etc.). An owner of a lottery device makes money by luring players to wager a small amount of money in hopes of winning a large amount of money. If the number of lottery winners exceeds a certain percentage of the players, where the percentage is based on wager amount and prize value, then the owner loses money. If the output of the lottery device is hard to predict then fewer players will win and the owner profits by keeping a higher percentage of the wagers. This analysis applies by analogy to a cryptographic device, but the stakes may be much higher (e.g., personal security, national security, etc.).
(U) A number that is generated in a manner that is truly random is a number that is independent of any other number that is generated. In other words, any number that is produced by a device that generates numbers that are truly random generates numbers where any number produced is just as likely to be produced as any other number. That is, no number is more likely to be produced than any other number. Therefore, someone cannot predict with more certainty than a guess what the next number will be based on previously generated numbers. There is always a chance, or probability, that a person will guess correctly. The probability may be lowered, or reduced to nearly zero, by increasing the range from which the number is generated. For example, it is more difficult to guess a number in the range of 1 to 100 than 1 to 10. However, increasing the number range increases the complexity and cost of the device. So, the designer should use the widest range of numbers that is appropriate for the application. A wider range of numbers will be used in a cryptographic device used to protect sensitive information than in a lottery device for a low dollar prize.
(U) A device that attempts to produce a random number is often referred to as a randomizer. Typically, randomizers rely on one or more sources of random data (e.g., timing of random events as compared to a threshold, random natural processes, etc.). The sources of random data are typically connected to a scrambling device that mixes the random data in some complex fashion to achieve a degree of uniformity in the distribution of the output of the randomizer. Typically, randomizers produce an m-bit block of random data.
(U) Pseudo-random number generators are not based on a source of random data but on a deterministic function that is believed to be adequate in both complexity and cycle length for the proposed application. (e.g., screen-saver movements, games of chance for entertainment, etc.).
(S) To insure that a randomizer produces outputs that are sufficiently random, the outputs are typically tested by either estimating the entropy present in the outputs, performing statistical tests on the outputs, or both. There are several different mathematical definitions for entropy which produce different results. Statistical tests are good at determining whether or not a randomizer is bad but not whether or not a randomizer is good. That is, failing a statistical test (e.g., percentage of ones and zeros, frequency of occurrence of a particular pattern, etc.) indicates that the randomizer is not producing random bits, but passing the statistical test does not, necessarily, indicate that the output is sufficiently random for the proposed application. The present invention is a method of testing a randomizer in a manner that is not based on estimating entropy or traditional statistical tests.
(U) U.S. Pat. No. 4,977,596, entitled “CRYPTOGRAPHIC SYNCHRONIZATION RECOVERY BY MEASURING RANDOMNESS OF DECRYPTED DATA,” discloses a device for and method of determining whether or not two cryptographic devices that are communicating with one another are in synchronization by performing a statistical test of ones density (i.e., the percentage of ones and zeros) at the output of the decryptor. The present invention does not rely solely on the ones density statistical test to determine if the output of a randomizer is sufficiently random. U.S. Pat. No. 4,977,596 is hereby incorporated by reference into the specification of the present invention.
(U) U.S. Pat. No. 5,581,561, entitled “RANDOM BIT DIAGNOSTIC FOR A HIGH RESOLUTION MEASUREMENT SYSTEM,” discloses a device for and method of determining whether or not a bit of a word is stuck at a zero or a one by logically combining test words with the output. The present invention does not employ the method of U.S. Pat. No. 5,581,561. U.S. Pat. No. 5,581,561 is hereby incorporated by reference into the specification of the present invention.
(U) U.S. Pat. No. 6,076,097, entitled “SYSTEM AND METHOD FOR GENERATING RANDOM NUMBERS,” discloses a device for and method of producing random data from one source of random data, mixing the random data, and performing chi-squared and compression tests on the data to determine if the data is sufficiently random. The present invention does not rely on chi-squared and compression tests to determine if the output of a randomizer is sufficiently random. U.S. Pat. No. 6,076,097 is hereby incorporated by reference into the specification of the present invention.
(U) SUMMARY OF THE INVENTION
(U) It is an object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data.
(S) It is another object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data by determining the probability that an output of the randomizer will reoccur.
(S) It is another object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data by determining the minimum number of guesses one would expect to have to make to correctly determine an output of the randomizer.
(S) It is another object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data by determining the probability that an output of the randomizer will reoccur and by determining the minimum number of guesses one would expect to have to make to correctly determine an output of the randomizer.
(S) The first step of the method is receiving, for each source of probabilistic data in a randomizer, a probability of occurrence of each possible state of the source of probabilistic data.
(S) The second step of the present method is raising each result of the first step to a power of two.
(S) The third step of the present method is generating a row vector a that includes the results of the second step.
(S) The fourth step of the present method is receiving the probability that each possible state transitions to each of the other possible states.
(S) The fifth step of the present method is raising each result of the fourth step to a power of two.
(S) The sixth step of the present method is generating a matrix B that includes the results of the fifth step, where each row of B represents one of the possible states from which a transition is made, where each column of B represents one of the possible states to which a transition is made, and where each numerical entry in B represents the square of the transition probability from the state represented by the row to the state represented by the column for which the entry intersects.
(S) The seventh step of the present method is generating a column vector c, where the number of entries in c is equal to the number of possible states in the probabilistic data, and where each entry in c is a one.
(S) The eighth step of the present method is computing S(P)=a(B{circumflex over ( )}(L−1))c for each at least one source of probabilistic data, where L is a number of outputs of probabilistic data
Gregory Bernarr E.
Morelli Robert D.
The United States of America as represented by the National Secu
LandOfFree
Method of testing a randomizer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of testing a randomizer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of testing a randomizer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3198164