Cyclotomic polynomial construction of discrete logarithm cryptosystems over finite fields
AssigneeCitibank, N.A.
InventorArjen K. Lenstra
Life of this patent
Estimating the term…
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.
Claims26
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).
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.
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.
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).
Dependencies are inferred from the claim text.