Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
2002-06-21
2004-04-06
Chavis, John (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C380S030000, C708S254000, C708S677000
Reexamination Certificate
active
06718536
ABSTRACT:
TECHNICAL FIELD
The present invention relates to cryptography, including such basic cryptographic components as prime number generation, key generation and pseudo-random number generation. The invention relates in particular to computer software cryptography methods and corresponding programmed hardware apparatus performing prime number generation and testing of generated candidates for probable primality, with particular emphasis on speed.
BACKGROUND ART
Large prime or probable prime numbers are useful for a variety of cryptographic applications. For example, prime numbers are used in generating key pairs in a public key cryptography system (such as RSA). Further, a pseudo-random number sequence can be generated using primes, as in U.S. Pat. No. 4,780,840 to Van Den Ende. Such sequences could in turn be used in stream ciphers for secret communications.
As the required size of the probable primes in these types of applications increases, an efficient way for the programmed computer system or chip involved in a cryptography method to quickly generate such primes becomes extremely important. In many applications it would be desirable, for added security and flexibility, that the large random prime numbers be generated immediately before use, rather than relying on a set of stored pre-computed prime values. Unfortunately, a difficulty in large prime number generation resides in the fact that probable prime candidates have to be tested through algorithms (such as Miller-Rabin or Fermat) that are time consuming or need a large amount of computing power or both. Techniques that quickly eliminate unlikely candidates would minimize the number of times that such rigorous tests need to be carried out before a probable prime is identified.
In U.S. Pat. No. 4,351,982, Miller et al. disclose generating a sequence of prime numbers, beginning with a known prime, by incrementing from a preceding prime P in the sequence to a new value hP +1 (h being random) and then testing the new value for primality. Any time a value is found to be composite, h is incremented by 2 and a new hP +1 is tested. Once a value hP +1 is found to be prime, it is used as the new prime P for the next search.
P. Mihailescu, in an article entitled “Technique for Generating Probable Primes”, IEEE P1963 submission (1994), describes a sieving method for generating prime numbers that are of the form N=2*(t+k)*Q+1, where the incremental search for prime candidates is done by increasing k in some manner.
J. Brandt et al, in the article “On Generation of Probable Primes by Incremental Search”,
Advances in Cryptology—Crypto
'92, Springer-Verlag (1993), pp. 358-370, describes an incremental search for candidates for primality testing. Here the increment for generating new candidates from the previous test candidate is always 2.
An object of the invention is to provide a computer software (or firmware) method by which a computer system or chip programmed with such software can efficiently eliminate unlikely candidates for probable primality testing so that probable primes useful for cryptographic applications such as key generation can be quickly generated and tested.
Another object of the invention is to provide a cryptographic apparatus in the form of a programmed computer system or configured processing chip that executes the aforementioned probable prime generation and testing method.
DISCLOSURE OF THE INVENTION
The above objects are met by a method and apparatus that implement a smart incrementation and small primes testing technique wherein successive candidates, beginning with a randomly generated first large candidate, which are relatively prime to very small primes (e.g., 2, 3, 5 and 7) are modularly reduced and tested against a specified set of small primes (e.g, primes from 11 through 241) until a likely candidate is identified for more rigorous probable primality testing.
The smart increment program function finds successive integer candidates by identifying an increment (not necessarily 2) to the next candidate, using a table of congruent values that are relatively prime to the selected very small primes modulus the product of the selected very small primes (e.g., mod 210). The table keeps the form of the primes eventually found by the method unknown, which is strongly desired for cryptographic security. It immediately sieves out about three-fourths of the really obvious composites so that only the remaining candidates known to be relatively prime to the very small primes are subjected to trial division in the program's small primes testing function. Use of the table also allows an increment to be found without trial division by the large integer candidates themselves.
The small primes test program function carries out trial division against a list of small primes. However, the speed of this program is increased by doing the trial division on a set of modular reduced values rather than on the very large candidates themselves (e.g, of 32 bit size instead of 1024 bits). The reduction moduli are size-limited products (e.g., at most 32 bits) of groups of the same small primes against which the candidate will be tested.
Only candidates that pass the small primes test (about ten percent of the total number of integers in any given range) will be subjected to the more rigorous probable primality test(s) like Miller-Rabin or Fermat.
BEST MODE OF CARRYING OUT THE INVENTION
The present invention is a computer-implemented method for generating and testing of large (typically 256, 324, 512, 1024 bits or larger) probable prime numbers for cryptographic use. The method is preferably implemented as software code stored on and read from a computer-readable medium and executed by a general-purpose programmable computer system. It might also be implemented as firmware in a special-purpose cryptographic computer chip (e.g., on a smart card), or even as configurable hardware (e.g., an FPGA chip) or application-specific circuitry (i.e., an ASIC chip) specifically programmed or designed to execute the steps of the method in its circuitry. Cryptographic uses for probable prime numbers include generating of keys, as in asymmetric (public-private key pair) encryption programs. Another cryptographic use for probable primes is for pseudo-random number generation, e.g. for stream cipher communications. The method of the present invention will typically be one part of a larger cryptographic computer program in which the large probable primes generated by the method are used. The computer system or special-purpose chip, when programmed to execute the method of the present invention can be considered, at that time, to be a prime number generating circuit or device.
The present method increases the speed of finding a probable prime by using a smart increment technique to avoid having to test unlikely candidates. A random number of the desired bit size (e.g., 1024 bits) is chosen and immediately incremented to a value that is relatively prime to the very small primes 2, 3, 5 and 7 to produce the initial candidate. Each candidate is tested by the programmed computer system or chip, beginning with trial integer division using a list of small primes, and if found to be composite is incremented by a selected even number (not necessarily two), to obtain the next candidate that is relatively prime to the very small primes 2, 3, 5 and 7. The present method uses this smart increment technique to minimize the number of composite numbers that are tested by integer division. The trial divisions are not conducted directly upon the large candidate number, but upon 32-bit modular reductions of the candidate, further speeding up the method. When a candidate is found that passes the small primes trial division test, the likely candidate is then tested using one or more known rigorous probable prime testing algorithms, such as the Miller-Rabin test or the Fermat test. As these latter tests are more time consuming (e.g., both of the above-named tests employ modular exponentiation), only those likely candidates found to be r
Atmel Corporation
Chavis John
Protsik Mark
Schneck Thomas
LandOfFree
Computer-implemented method for fast generation and testing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer-implemented method for fast generation and testing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer-implemented method for fast generation and testing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3197415