Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-04-13
2004-02-10
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S254000
Reexamination Certificate
active
06691141
ABSTRACT:
FIELD OF THE INVENTION
Aspects of this invention pertain to the field of random number generators. More particularly, this invention pertains to generating parameters for a large number of random number generators.
BACKGROUND OF THE INVENTION
FIG. 1
illustrates a cryptologically weak random number generator (CWRNG)
100
. Examples of CWRNG's are a linear congruential random number generator (LRNG) and a quadratic congruential random number generator (QRNG). Random number generators are widely used in cryptographic applications, such as for encrypting digital computer messages transmitted over a network.
LRNG's are recursions in x of a form x
i+1
=(a*x
i
+b)%c, where * denotes multiplication and % denotes a modulo function. For example, (a*x
i
+b)%c would produce an integer in a range of 0 to (c−1). a, b and c, the LRNG parameters, along with x
0
, the LRNG starting value determine succeeding values of x. The LRNG will cycle through all numbers in the range from 0 to c−1 in pseudo-random order before repeating (i.e. it has a period of c, the maximum period), if and only if:
1. b is relatively prime to c (that is, no prime factors of c are prime factors of b);
2. (a−1) is a multiple of p for every prime number p dividing c; and
3. (a−1) is a multiple of 4 if c is a multiple of 4.
Further, in order to prevent (a−1) from being a predictable value, c should not divide evenly into (a−1). This can be accomplished by imposing a fourth rule as follows:
4. at least one prime factor in c is raised to a power greater than 1 and the same prime factor used in (a−1) must be raised to a power less than the power used to raise that prime factor in c.
QRNG's are recursions in x of a form x=(d*x*x+a*x+b)%c, which generates a series of integers in a range from 0 to (c−1). a, b, c and d, the QRNG parameters, along with x
0
, the QRNG starting value determine the succeeding values of x. A QRNG will cycle through all numbers in a range of 0 to (c−1) in psuedo-random order before repeating (i.e. it has a period of c, the maximum period), if and only if:
1. b is relatively prime to c;
2. d and (a−1) are both multiples of p for every odd prime number p dividing c;
3. d is even and d is congruent to (a−1)% 4 if c is a multiple of 4;
4. d is congruent to (a−1)%2 if c is a multiple of 2; and
5. either d%9=0 or a%9=1 and (b*d)%9=6 if c%9=0.
Further, in order to prevent (a−1) and d from having predictable values, c should not divide evenly into (a−1) and d.
While LRNG's and QRNG's provide a fast and efficient method for generating quasi-random numbers, they have certain disadvantages. An outside observer can determine succeeding outputs from either a LRNG or a QNRG after observing a short sequence of outputs.
FIG. 2
shows a two-stage random number generator, which includes a cryptologically weak random number generator
100
with an output stream
110
. The output stream may be encrypted by a block encryptor
210
making it difficult for an outside observer to successfully attack this system by observing the output
212
of the block encryptor
210
.
Random number generators may be used in a communication system (e.g., Internet) where large numbers of random number generators may be used and frequently re-keyed to provide security to communications occurring in the system by, for example, providing security keys for encrypting and decrypting such communications.
Data in a communication system is placed in packets. Each packet is sent from a source to a destination and may pass through one or more intermediate locations before reaching its destination. The security keys allow for the data to be encrypted at the source and decrypted at the destination, such that an unintended recipient, for example, a hacker monitoring one of the intermediate locations, is unable to decrypt the data contained in the packets because he does not possess the security keys.
Random numbers generated by cryptologically weak random number generators will eventually repeat. The repeating numbers are in an easily guessable sequence of random numbers. The cryptologically weak random number generator, the encryptor or both, should be re-keyed well before the sequence repeats. The time for re-keying the cryptologically weak random number generator should be short for two reasons: (1) a system crash will make the re-keying of many cryptologically weak random number generators necessary and slow re-keying would effectively extend an outage; and (2) re-keying is non-productive overhead for a system during normal “sunny day” operation of the system. As such, it is appropriate to limit this overhead to be at most x percent of the system's resources. The overhead is limited to x percent of the system's resources when:
T<=
0.01
×c/p,
(1)
where T is the time to re-key in seconds, c is the number of packets transmitted between re-keys (directly proportional to cycle length) and p is the maximum speed of the data in packets per second. For instance, if x=0.1, c=1,000,000 packets, and p=100,000 packets per second, then T can be at most 10 milliseconds, with re-keying occurring every 10 milliseconds. Typically, cryptologically weak random number generators, such as linear congruential random number generators (LRNG's) and quadratic congruential random number generators (QRNG's) can be combined to achieve a long cycle. Therefore, re-keying after a crash is a limiting constraint.
The re-keying should yield practically unguessable random number generators. The parameters for the random number generator should not exhibit a strong bias that would make them easily determined by an observer. For instance, if the parameters for a ten parameter cryptologically weak random number generator were restricted to being one of the 6,542 primes between 2 and 65,535, over ten orders of magnitude fewer unique cryptologically weak random number generators would be possible than would be if the parameters were selected as being any integer in the range 2-65,535. However, generating cryptologically weak random number generators with known long non-repeating cycles restricts the choice of parameters and increases the predictability of parameters. This increase in predictability should be minimized.
SUMMARY OF THE INVENTION
A method and apparatus are provided for generating parameters for a random number generator. A random value is generated and the random value is mapped to a prime number. Each of the parameters is generated by multiplying the prime number by previously selected prime numbers. The principles of the invention allow a large number of random number generators to be quickly re-keyed.
REFERENCES:
patent: 5751808 (1998-05-01), Anshel et al.
patent: 5828752 (1998-10-01), Iwamura et al.
patent: 5850450 (1998-12-01), Schweitzer et al.
patent: 6141668 (2000-10-01), Shimada
patent: 6285761 (2001-09-01), Patel et al.
patent: 6590462 (2003-07-01), Itahara
patent: 2002/0164019 (2002-11-01), Fairclough et al.
Banner & Witcoff , Ltd.
Mai Tan V.
Science Applications International Corp.
LandOfFree
Method and apparatus for generating random number generators 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 and apparatus for generating random number generators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating random number generators will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294655