Cryptography – Communication system using cryptography – Symmetric key cryptography
Reexamination Certificate
2000-07-10
2002-04-23
Decady, Albert (Department: 2132)
Cryptography
Communication system using cryptography
Symmetric key cryptography
C380S262000, C380S030000, C713S181000
Reexamination Certificate
active
06377689
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to public key cryptography.
BACKGROUND OF THE INVENTION
It is well known that data can be encrypted by utilising a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted by the public key may only be decrypted by the private key. In this way, the public key of a recipient may be made available so that data intended for that recipient may be encrypted with the public key and only decrypted by the recipients private key.
The most well known and accepted public key cryptosystems are those based on discrete logarithms in finite groups and integer factorization. In particular, the Diffie-Hellman key exchange and the El Gamal protocol in Z
p
*
, p a prime and the RSA system for modulus n=p·q where p and q are primes have been implemented worldwide. One disadvantage of these systems is that p and n must be relatively large (at least 512 bits) to attain an adequate level of security.
To implement the public key schemes it is necessary to transfer the public key of a recipient to the sender or for the sender to store the keys of all possible recipients. For this reason researchers have looked for public key schemes which reduce the size of the public key. An attractive and promising system is the Diffie-Hellman and El Gamal protocols defined in the group associated with the points on an elliptic curve over a finite field. It appears that a 155-bit elliptic curve scheme gives comparable security to a 1024-bit RSA modulus. Nevertheless, RSA remains a very viable and practical encryption and signing process.
The implementation of RSA system requires a modulus n to be generated from two primes, p,q. The primes p,q, are also used to select a pair of integers, d,e, that are related such that the product e.d≡1 (mod(p−1)(q−1) and that the GCD (greatest common denominator) of e, p−1 and q−1=1.
The integers e together with the modulus n is used as the public key and the integer d with the modulus n is used as the private key. To encrypt a message the sender uses the public key e,n of the recipient and exponentiates the message M to the integer ‘e’ mod n to generate ciphertext C. The recipient receives the ciphertext C and uses the private key d,n to retrieve the message M by exponentiating C to power d mod n. Therefore the communication between the sender and recipient requires the sender to have access to the public key of the recipient. Typically the public key will be retrieved from the recipient at the start of transmission or it may be stored by the sender. The public key must also be associated with other information such as the recipients identity and be transmitted in a conventional frame format. Accordingly, it is desirable for the data that has to be transmitted to be as short as possible.
On the other hand, the security of the RSA system is determined by the difficulty in factoring the modulus n and this requires p and q to be as large as possible, typically at least 256 bits but preferably 512. n itself will therefore also be large, either 512 or 1024 bits.
It is an object of the present invention to provide a method for reducing the storage and transmission requirement of RSA public moduli without compromising security.
SUMMARY OF THE INVENTION
The present invention is based upon the recognition that if the modulus n is an m-bit number it is possible to specify t bits of the number where t is suitably bounded whilst retaining the requisite security. If the t bits can be random bits the criteria for retaining security is somewhat simplified. In one embodiment, a group of users may use the same t random bits and hence only m−t bits need be stored for each user and one copy of the t random bits for the entire group. In another embodiment a user may specify the t bits to be a binary representation of their user ID and other publicly available information. This situation can also be implemented by adjoining a small number of random bits after the information. The applicants have recognised that one can always specify up to m/2 of the bits, but specifying m/2 of the bits comes at the expense of longer key generation (i.e. prime generation). Varied embodiments may be implemented depending on the degrees of dependence between the primes p and q.
According to the present invention, an RSA moduli is generated in which a predetermined set of bits within the moduli have a predetermined configuration.
REFERENCES:
patent: 4200770 (1980-04-01), Hellman et al.
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4969190 (1990-11-01), Takaragi et al.
patent: 6078663 (2000-06-01), Yamamoto
patent: 6081598 (2000-06-01), Dai
“Applied Cryptography”, Bruce Schneier(pp. 564-574), Oct. 1995.*
“Applied Cryptography”, Alfred J. Menezes, et al. (pp. 285-291 and pp. 312-315), Jan. 1997.
Vanstone Scott C.
Zuccherato Robert J.
Certigom Corp.
De'cady Albert
Jack Todd
The Maxham Firm
LandOfFree
Key transmission system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Key transmission system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Key transmission system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905504