Cyclotomic polynomial construction of discrete logarithm cryptosystems over finite fields
First Claim
Patent Images
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).
1 Assignment
0 Petitions
Accused Products
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.
98 Citations
26 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). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 26)
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 (log2 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.
- , and wherein the cyclotomic polynomial is the t′
-
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). - View Dependent Claims (23, 24, 25)
-
Specification