Cryptography – Communication system using cryptography – Pseudo-random sequence scrambling
Reexamination Certificate
1998-04-08
2002-06-11
Peeso, Thomas R. (Department: 2131)
Cryptography
Communication system using cryptography
Pseudo-random sequence scrambling
C380S044000, C380S029000, C713S174000
Reexamination Certificate
active
06404890
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to cryptography, and, more particularly, is directed to generation of a modulus, part of a public key according to the Rivest-Shamir-Adleman (RSA) cryptographic scheme, wherein the modulus is generated so as to have a predetermined portion.
The RSA scheme is described more fully in U.S. Pat. No. 4,405,829 (Rivest et al.), “Cryptographic Communications System and Method”, the disclosure of which is hereby incorporated by reference. In a set-up phase of the RSA scheme, a participant picks two prime numbers, p and q, each having a selected number of bits, such as 512 bits, with p≠q. The participant keeps p and q secret. The participant computes an RSA modulus n, with n=p*q. When p and q each have 512 bits, n has 1023 or 1024 bits. The participant picks an RSA exponent e that has no factors in common with (p−1)(q−1). For efficiency purposes, the RSA exponent e is often chosen of much shorter length than the RSA modulus. When the RSA modulus n has 1024 bits, the RSA exponent e typically has at most 64 bits. The owning participant makes the public key (n, e) available to other participants.
During operational use of the RSA scheme, other participants use the public key (n, e) to encrypt messages for the participant which owns that key. The owning participant is able to decrypt messages encrypted with the public key (n, e) due to possession of the secret prime numbers p and q.
Participants must store not only the public key of other participants, but also identifying information such as the name, address, account number and so on of the participant owning each stored public key. There are problems with this situation.
One problem with the present technique for using the RSA encryption scheme is that, although the RSA modulus n is 1024 bits, the amount of security provided actually corresponds to only 512 bits, since an attacker who knows one of p and q can readily obtain the other of p and q. Instead of having to store 1024 bits to obtain 512 truly secure bits, it is desirable to store far fewer bits, such as approximately 512 bits, to obtain the 512 truly secure bits.
Another problem with the present technique is the additional storage required for the identifying information. It is desirable to reduce the amount of additional storage as much as possible.
Generating RSA moduli having a predetermined portion has been considered by Scott A. Vanstone and Robert J. Zuccherato in “Short RSA Keys and Their Generation”, J.
Cryptology
, 1995, volume 8, pages 101-114, the disclosure of which is hereby incorporated by reference.
In “Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known”, U. Maurer ed., EUROCRYPT '96 Proceedings, pages 178-189, Springer Verlag 1996, the disclosure of which is hereby incorporated by reference, Don Coppersmith has analyzed the security of the Vanstone methods, and found that all but one of Vanstone's methods provide inadequate security. Specifically, for the Vanstone methods having predetermined high order bits, the RSA modulus n is generated in such a way that somewhat more than the high order ((¼)log
2
n) bits of p are revealed to the public, which enables discovery of the factorization of the RSA modulus n, thus leaving the scheme vulnerable to attack.
SUMMARY OF THE INVENTION
In accordance with an aspect of this invention, there is provided a method of determining an RSA modulus having a predetermined leading portion s and first and second prime p and q. A number is selected as the first factor p. A number n having the predetermined leading portion s is set. The factor q is obtained as n/p.
If the factor q is prime, then the number n is the desired RSA modulus. If the factor q is not prime, then q is adjusted and the adjusted q is checked to determine whether it is prime.
According to a further aspect of the invention, the step of adjusting the factor q may be performed by incrementing or decrementing the factor q by a predetermined amount, and may further include correspondingly incrementing or decrementing the number n by the product of the predetermined amount and the number p.
In accordance with another aspect of this invention, there is provided a method of determining an RSA modulus having a predetermined leading portion s
1
and predetermined trailing portion s
2
, and first and second factors p and q. A number is selected as p. A number n having the predetermined leading portion s
1
and predetermined trailing portion s
2
is set. The factor q is obtained as n/p.
If the factor q is prime, then the number n is the desired RSA modulus. If the factor q is not prime, then q is adjusted, and the adjusted q is checked to determine whether it is a prime number.
In accordance with a further aspect of this invention, there is provided a method of determining an RSA modulus having a predetermined leading portion s
1
and a predetermined trailing portion s
2
, and first and second prime factors p and q. A number is selected as one of p
1
and q
1
. A number n
1
is set, the number n
1
having the predetermined leading portion to s
1
and a trailing portion which is a function of the selected one of p
1
and q
1
. The other of p
1
and q
1
is obtained as the number n
1
divided by the selected one of p
1
and q
1
.
A number is selected as one of p
2
and q
2
. The other of p
2
and q
2
is obtained as the predetermined trailing portion s
2
divided by the selected one of p
2
and q
2
.
The numbers p
1
and p
2
are concatenated to produce the factor p, and the numbers q
1
and q
2
are concatenated to produce the factor q.
If each of the factors p and q are prime, then the desired RSA modulus is the product of the factors p and q. If at least one of the factors p and q is not prime, new numbers are obtained for p
2
and q
2
, concatenated with p
1
and q
1
, respectively, to produce the revised factors p and q, and it is checked whether the revised factors p and q are prime numbers.
In accordance with another aspect of this invention, there is provided a method of encrypting a message a using a public exponent b and an RSA modulus n, comprising performing a multiplication portion of obtaining a
b
mod n, and performing a division portion of obtaining a
b
mod n using only multiplication operations and without using division operations.
Corresponding methods of decrypting a message a using a secret exponent b and an RSA modulus n, signing a message a using a secret exponent b and an RSA modulus n, and verifying a signature a using a public exponent b and an RSA modulus n are also provided.
It is not intended that the invention be summarized here in its entirety. Rather, further features, aspects and advantages of the invention are set forth in or are apparent from the following description and drawings.
REFERENCES:
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4870681 (1989-09-01), Sedlak
Vanstone, S. A., et al., “Using Four-Prime RSA In Which Some of the Bits Are Specified”,Electronics Letters, vol. 30, No. 25, pp. 2118-2119, Dec. 8, 1994.
R.L. Rivest, et al., “A Method for Obtaining Digital Signatures and Public-Key Crytosystems”,Communications of the ACM, vol. 21, No. 2, pp. 120-126, 1978.
A.K. Lenstra and H.W. Lenstra, Jr., “Algorithms in Number Theory”,Handbook Of Theoretical Computer Science, pp. 675-715, 1990.
S.A. Vanstone and Robert J. Zuccherto, “Short RSA Keys and Their Generation”,Journal of Cryptology, vol. 8, pp. 101-114, 1995.
D. Coppersmith, “Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known”,Eurocrypt '96 Proceedings, LNCS 1070, pp. 178-189, Springer-Verlag Berlin Heidelberg 1996.
U. M. Maurer, “Fast Generation of Prime Numbers and Secure Public-Key Crytographic Parameters”,Journal of Cryptology, vol. 8, pp. 123-155, 1995.
P.L. Montgomery, “Modular Multiplication Without Trial Division”,Mathematics Of Computation, vol. 44, No. 170, pp. 519-521, 1985.
Robert D. Silverman, “Fast Generation of Random, Strong RSA Primes”,RSA Laboratories' CryptoBytes, vol. 3, No. 1, pp
Citibank, NA
Morgan & Finnegan , LLP
Peeso Thomas R.
LandOfFree
Generating RSA moduli including a predetermined portion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generating RSA moduli including a predetermined portion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating RSA moduli including a predetermined portion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926523