Cryptography – Key management – Having particular key generator
Reexamination Certificate
2006-10-10
2006-10-10
Moise, Emmanuel L. (Department: 2137)
Cryptography
Key management
Having particular key generator
C380S046000, C380S047000, C380S030000, C708S250000, C708S253000, C708S256000, C708S490000, C708S507000, C463S022000
Reexamination Certificate
active
07120248
ABSTRACT:
A process is provided for searching in parallel for a plurality of prime number values simultaneously includes the steps of: randomly generating a plurality of k random odd numbers (wherein k is preferably more than 2, but could also be one or more) expressed as n0,0, n1,0, . . . n((k−1)),0, each number providing a prime number candidate; determining a plurality of y additional odd numbers based on each one of the randomly generated odd numbers n0,0, n1,0, . . . n(k−1),0to provide additional prime number candidates thereby yielding a total number of prime number candidates; sieving the total number of prime number candidates by performing a small divisor test on each of the candidates in order to eliminate candidates revealed to be composite numbers by the small divisor test thereby yielding a sieved number s of candidates; and performing a first probabilistic primality test on each of the sieved number s of candidates, each of the plurality of s first primality tests including an associated exponentiation operation executed by an associated one of a plurality of s of the exponentiation units, the exponentiation operations being performed by the plurality of s exponentiation units substantially simultaneously in order to eliminate candidates revealed to be composite numbers by the primality test thereby yielding a remaining number r of candidates.
REFERENCES:
patent: 4168396 (1979-09-01), Best
patent: 4200770 (1980-04-01), Hellman et al.
patent: 4218582 (1980-08-01), Hellman et al.
patent: 4278837 (1981-07-01), Best
patent: 4319079 (1982-03-01), Best
patent: 4351982 (1982-09-01), Miller et al.
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4424414 (1984-01-01), Hellman et al.
patent: 4433207 (1984-02-01), Best
patent: 4465901 (1984-08-01), Best
patent: 4514592 (1985-04-01), Miyaguchi
patent: 4995082 (1991-02-01), Schnorr
patent: 5046094 (1991-09-01), Kawamura et al.
patent: 5321752 (1994-06-01), Iwamura et al.
patent: 5343527 (1994-08-01), Moore
patent: 5351298 (1994-09-01), Smith
patent: 5421006 (1995-05-01), Jablon et al.
patent: 5761310 (1998-06-01), Naciri
patent: 5835594 (1998-11-01), Albrecht et al.
patent: 5844986 (1998-12-01), Davis
patent: 6078565 (2000-06-01), Simoni
patent: 6307938 (2001-10-01), Matyas et al.
patent: 6330332 (2001-12-01), Itoh et al.
patent: 6345098 (2002-02-01), Matyas et al.
patent: 6378072 (2002-04-01), Collins et al.
patent: 6578057 (2003-06-01), Hori
patent: 6718536 (2004-04-01), Dupaquis
A. Menezes et al, Handbook of Applied Cryptography, CRC Press 1996, pp. 133-168.
Kent White, Ph.D.: “Experiments in Parallel Processing for Undergraduate Students” 29th ASEE/IEEE Frontiers in Education Conference, Nov. 1999, pp. 11a3-1-11a3-4.
Daniel M. Gordon: “A Survey of Fast Exponentiation Methods” Journal of Alogrithms 27, 129-146, 1998.
S.A. Vanstone et al., “Using Four-Prime RSA in Which Some of the Bits are Specified,” Dec. 8, 1994, Electronics Letter, vol. 30, No. 25. pp. 2118-2119.
C. Couvruer et al., “An Introduction to Fast Generation of Large Prime Numbers,” 1982, Philips Journal of Research, vol. 37, Nos. 5-6, pp. 231-264.
Y. Desmedt et al., “Public-Key Systems Based on the Difficulty of Tampering (Is There a Difference Between DES and RSA?),” 1986, Lecture Notes in Computer Science, Advances in Cryptology-CRYPTO '86 Proceedings.
J. J. Quisquater et al., “Fast Decipherment Algorithm.for RSA Public-Key Cryptosystem” Oct. 1982, Electronic Letters, vol. 19, No. 21.
Cetin Kaya Koc, “High-Speed RSA Implementation (Version 2.0),” Nov. 1994, RSA White Paper, RSA Laboratories.
Rivest et al., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Feb. 1978, Communications of the ACM, vol. 21.
PKCS #1: RSA Encryption Standard (Version 1.5), Nov. 1993, RSA Laboratories Technical Note.
M.O. Rabin, “Digitalized Signatures and Public-Key Functions as Intractable as Factorization,” Jan. 1979, MIT Laboratory for Computer Science.
R. Lidl et al., “Permutation Polynomials in RSA-Cryptosystems,” 1984, Advances in Cryptology—Crypto '83, pp. 293-301.
D. Boneh et al., “Generating a Product of Three Primes with an Unknown Factorization,” Computer Science Department, Stanford University.
J. J. Quisquater et al., “Fast Generation of Large Prime Numbers” Jun. 1982, Library of Congress, Catalog No. 72-179437, IEEE Catalog No. 82CH1767 IT, pp. 114-115.
A. J. Menezes et al., “Handbook of Applied Cryptography”, 1997, Library of Congress catalog No. 96-27609, pp. 89, 612-613.
P.J. Flinn et al., “Using the RSA Algoithm for Encryption and Digital Signatures: Can You Encrypt, Decrypt, Sign and Verify Without Infringing the RSA Patent?”, Jul. 9, 1997, 17 pgs, http://www.cyberlaw.com/rsa.html.
Nemo, “RSA Moduli Should Have 3 Prime Factors”, 1996.
Collins Thomas W.
Hopkins W. Dale
Wang Ruth A.
Wierenga Steven W.
Callahan Paul
Moise Emmanuel L.
LandOfFree
Multiple prime number generation using a parallel prime... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple prime number generation using a parallel prime..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple prime number generation using a parallel prime... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3651136