Cyclotomic polynomial construction of discrete logarithm cryptosystems over finite fields

• US 6,665,405 B1
• Filed: 10/19/2000
• Issued: 12/16/2003
• Est. Priority Date: 02/14/1997
• Status: Expired due to Term

• Current Assignee: Citibank (South Dakota) NA (Citigroup Incorporated)
• Original Assignee: Citibank (South Dakota) NA (Citigroup Incorporated)
• Inventors: Lenstra, Arjen K.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Seal, James
• Application Number:
  US09/704,722
• Time in Patent Office: 1,153 Days
• Field of Search: 380/28, 380/30, 708/492
• US Class Current: 380/28
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

Cyclotomic polynomials are used to construct subgroups of multiplicative groups of finite fields that allow very efficient implementation of discrete logarithm based public key cryptosystems, including public key encryption schemes and digital signature schemes. A field is represented with an optimal normal basis, and a generator of a subgroup of the multiplicative group of the field is used to form a public key.

Claims

1. A method of determining a shared public key for a public key cryptosystem, comprising the steps of:

obtaining a public value t with t>

1,

selecting a first prime number p,

obtaining the t-th cyclotomic polynomial evaluated at the first prime number p,

obtaining a second prime number q which is a factor of the t-th cyclotomic polynomial evaluated at the first prime number p,

finding a generator g of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number q, and

forming the shared public key (p, g, q, t).

2. The method of claim 1, further comprising the step of representing the finite field with an optimal normal basis.

3. The method of claim 1, wherein the second prime number q satisfies (log₂ q)+1≈

B, where B is a predetermined number of bits.

4. The method of claim 1, further comprising the step of selecting a control integer t′

, and wherein the cyclotomic polynomial is the t′

-th cyclotomic polynomial, and the public key includes the control integer t′

.

5. A method of generating a digital signature for a message wherein a shared public key is determined according to the method of claim 1, and the public value is also based on a first integer, comprising the steps of:

selecting a second integer,

obtaining a first signature value based on the second integer and the generator,

obtaining a second signature value based on the first signature value and the message, and

forming the digital signature to include the first and second signature values.

6. The method of claim 5, further comprising the step of representing the finite field with an optimal normal basis.

7. The method of claim 5, wherein the second prime number q satisfies (log₂ q)+1≈

B, where B is a predetermined number of bits.

8. The method of claim 5, further comprising the step of selecting a control integer t′

, and wherein the cyclotomic polynomial is the t′

-th cyclotomic polynomial.

9. The method of claim 5, wherein the first signature value is based on a bijection of the generator raised to the power of the second integer.

10. The method of claim 5, wherein the second signature value is based on combining the first signature value with a cryptographic hashing of the message.

11. A method of verifying a digital signature for a message, the digital signature being formed according to the method of claim 5, comprising the steps of:

finding an inverse integer which is the inverse of the second signature value,

finding a first intermediate value based on the inverse integer and the message,

finding a second intermediate value based on the inverse integer and the first signature value,

finding a third intermediate value based on the generator, the public value, and the first and second intermediate values,

determining that the signature is valid when the third intermediate value is equal to the first signature value.

12. The method of claim 11, wherein the third intermediate value is a bijection of the generator raised to the power of the first intermediate value multiplied by the public value raised to the power of the second intermediate value.

13. A method of determining a shared key for a secret key cryptosystem wherein a shared public key is determined according to the method of claim 1, comprising the steps of:

selecting an integer,

receiving an intermediate value which is based on the generator, and

forming the shared key as a function of the intermediate value and the integer.

14. The method of claim 13, further comprising the step of representing the finite field with an optimal normal basis.

15. The method of claim 13, further comprising the steps of finding a second intermediate value which is based on the generator and the integer, and sending the second intermediate value to a party who is to share the shared key.

16. A method for secure communication of a message wherein a shared public key is determined according to the method of claim 1, comprising the steps of:

selecting an integer,

receiving an intermediate value which is based on the generator,

forming a shared key as a function of the intermediate value and the integer, and

encrypting the message using the shared key.

17. The method of claim 16, further comprising the step of representing the finite field with an optimal normal basis.

19. A method for secure communication of a message wherein a shared public key is determined according to the method of claim 1, and the public value is also based on a first integer, comprising the steps of:

selecting a second integer,

finding a first encrypted value based on the generator and the second integer,

finding a second encrypted value based on the message, the public value and the second integer, and

forming an encrypted message from the first and second encrypted values.

20. The method of claim 19, further comprising the step of representing the finite field with an optimal normal basis.

26. A method of determining a private key for the public key cryptosystem of claim 1, wherein the public key is also based on a selected integer, comprising the step of forming the private key to include the selected integer.

18. A method for secure communication of a message, comprising the steps of:

receiving an encrypted message which has been encrypted using a shared key for a secret key cryptosystem, the shared key being formed as a function of an intermediate value and a selected integer, the intermediate value being based on a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being a second prime number which is a factor of a cyclotomic polynomial other than the first cyclotomic polynomial evaluated at a first prime number, and

decrypting the encrypted message using the shared key.

21. A method for secure communication of a message, comprising the steps of:

receiving an encrypted message formed of a first encrypted value and a second encrypted value, the first encrypted value being based on a first integer and a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being a second prime number which is a factor of a cyclotomic polynomial other than the first cyclotomic polynomial evaluated at a first prime number, the second encrypted value being based on the message, the first integer and a public value based on the generator and a second integer,

finding a first intermediate value based on the first encrypted value and a private key, the private key being based on the generator, and

decrypting the encrypted message based on the second encrypted value and the first intermediate value.

22. An apparatus for determining a shared public key for a public key cryptosystem, comprising:

means for selecting a first prime number p,

means for obtaining a cyclotomic polynomial other than the first cyclotomic polynomial evaluated at the first prime number p,

means for obtaining a second prime number q which is a factor of the cyclotomic polynomial evaluated at the first prime number p,

means for finding a generator g of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number q,

means for obtaining a public value t based on the generator g, and

means for forming the shared public key (p, g, q, t).

23. The apparatus of claim 22, further comprising means for representing the finite field with an optimal normal basis.

24. The apparatus of claim 22, wherein the second prime number q satisfies (log_{2 q})+1≈

B, where B is a predetermined number of bits.

25. The apparatus of claim 22, further comprising means for selecting a control integer t′

, and wherein the cyclotomic polynomial is the t′

-th cyclotomic polynomial, and the public key includes the control integer t′

.