Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1997-10-10
2002-01-08
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
Reexamination Certificate
active
06337909
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to public key encryption systems and more particularly to the generation of session parameters for use with public key protocols.
Public key data encryption systems are well-known and the more robust are based upon the intractability of the discrete log problem in a finite group. Such public key encryption systems utilize a group element and a generator of the group. The generator is an element from which each other group element can be obtained by repeated application of the underlying group operation, ie. repeated composition of the generator. Conventionally, this is considered to be an exponentiation of the generator to an integral power and may be manifested as a k fold multiplication of the generator or a k fold addition of the generator depending upon the underlying group operation. In such a public key encryption system, an integer k is used as a private key and is maintained secret. A corresponding public key is obtained by exponentiating the generator a with the integer k to provide a public key in the form &agr;
k
. The value of the integer k cannot be derived even though the value &agr;
k
is known.
The public and private keys may be utilized in a message exchange where one of the correspondents may encrypt the data with the recipient's public key &agr;
k
. The recipient receives the encrypted message and utilizes his private key k to decrypt the message and retrieve the contents. Interception of the message will not yield the contents as the integer k cannot be derived.
A similar technique may be utilized to verify the authenticity of a message by utilizing a digital signature. In this technique, the transmitter of the message signs the message with a private key k and a recipient can verify that the message originated from the transmitter by decrypting the message with the transmitter's public key &agr;
k
. A comparison between a function of the plain text message and of the recovered message confirms the authenticity of the message.
In both techniques, it is necessary to perform the exponentiation of the group element &agr;. To be secure, k must be a relatively large number and the exponentiation can therefore be relatively long. Where the exponent is used as a long-term public key, the time of computation is not of undue concern. However, in digital signature schemes, a short term session key is utilized together with the long-term public key. Each message is signed with a different private key k and the corresponding public session key &agr;
k
has to be computed and transmitted with the message. There is therefore the need for some efficiency in the exponentiation.
The computing time for the exponentiation can be reduced by utilizing an integer exponent k having a relatively low Hamming weight—that is, the number of 1's in the binary representation of the integer is kept low or analogously in another radix, the exponent has few non-zero coefficients. However, integers having low Hamming weights are considered vulnerable to various attacks, including a square root attack, and so their use in encryption protocols is not encouraged.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a method of computing the session parameters for public key exchange protocols that obviates or mitigates the above disadvantages.
In general terms, the present invention provides a method of computing an exponent for use in a public key exchange protocol in which an integer k′ is selected, having a Hamming weight less than a predetermined value. An exponentiation with the generator &agr; is performed and the resultant intermediate session parameter &agr;
k′
is mathematically combined with a secret value &ggr;. &ggr; is derived from a random integer i which has a Hamming weight greater than the predetermined value. The mathematical combination of &ggr; with the intermediate session parameter produces a session parameter whose exponent has a Hamming weight greater than the predetermined value and as such is considered computationally secure.
Conveniently, the secret value &ggr; can be precomputed so that the real time exponentiation is confined to the generation of the exponent that utilizes the integer k′.
The method may be used with the multiplicative group Z*
p
or may be utilized with other groups such as elliptic curves over a finite field.
REFERENCES:
patent: 5299262 (1994-03-01), Brickell et al.
patent: 5627893 (1997-05-01), Demytko
patent: 5850450 (1998-12-01), Schwelzer et al.
patent: 2734679 (1996-11-01), None
patent: WO 9747110 (1997-12-01), None
patent: 0792043 (1998-07-01), None
patent: 0854603 (1998-07-01), None
Bruce Schneier, Applied Cryptography 2e, John Wiley, 1995.*
Wayne Patterson, Mathematical Cryptology for Computer Scientists and Mathematician, Rowman & Littlefield, 1987.*
Neal Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, 1987.*
A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993.*
Schneier, Applied Cryptography, John Wiley and Sons, p. 478, Oct. 1995.*
Menezes, et al., Handbook of Applied Cryptography, CRC Press, p. 105, 1996.*
Rosati, A High Speed Data Encryption Processor for Public Key Cryptography, IEEE, 1989.*
Dimitrov, Two Algorithm for Modular Exponentiation Using Nonstandard Arithmetics, IEEE, Jan. 1995.*
Rosati T: “A High Speed Data Encrytion Processor for Public Key Crytography” Proceedings of the Custom Integrated Circuits Conference, US, New York, IEEE, vol. Conf. 11, 1989, pp. 1231-1235 XP0000757631 *PG 1231, Right Column *PG 1233 Right Column *PG 1234 Left Column.
Heiman R: “A Note on Discrete Logariths with Special Structure” Lecture Notes Incomputer Science, US, Springer Verlag, New York, NY, vol. 658, Jan. 1, 1993, pp. 454-457, XP000562427 ISSN: 0302-9743 * Entire Document.
Menezes A J Et Al.: “Eiliptic Curve Cryptosystems and Their Implementation” Journal of Cryptology, US, New York, NY, vol. 6, No. 4. Jan. 1, 1992, pp. 209-224, XP002069135 *PG 218-PG 219 * PG 222-PG 223*.
Johnson Donald B.
Lambert Robert J.
Mullin Ronald C.
Vanstone Scott A.
Certicom Corp.
Hayes Gail
Seal James
The Maxham Firm
LandOfFree
Generation of session keys for El Gamal-like protocols from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generation of session keys for El Gamal-like protocols from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generation of session keys for El Gamal-like protocols from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2835665