Method of cryptography with public key based on the discrete logarithm

• US 5,946,397 A
• Filed: 09/24/1997
• Issued: 08/31/1999
• Est. Priority Date: 10/03/1995
• Status: Expired due to Fees

• Current Assignee: Gemalto SA (Thales SA)
• Original Assignee: Gemplus SCA
• Inventors: Vaudenay, Serge, Naccache, David, M'Raihi, David, Stern, Jacques
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/860,832
• Time in Patent Office: 706 Days
• Field of Search: 380/21, 380/30
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Method of public key cryptography based on the discrete logarithm that makes use of the computation of the variable r=g^k modp where p is a prime number called a modulus, the exponent k is a random number usually with a length of N bits and g is an integer called a base, wherein an entity E carries out operations of authentication and/or of signature, including exchanges of signals with another entity in which this variable comes into play.

Claims

1. Method of public key cryptography based on the discrete logarithm that makes use of the computation of the variable r=g^k modp where p is a prime number called a modulus, the exponent k is a random number usually with a length of N bits and g is an integer called a base, wherein an entity E carries out operations of authentication and/or of signature, comprising exchanges of signals with another entity in which this variable comes into play, characterized in that this method comprises the following steps for a given entity:

forming a data base containing a fixed number of exponents and the corresponding powers, then for each exchange of signals;

generating an exponent by carrying out a random linear combination of the exponent values of the base,

and computing the power of g on the basis of the powers of the base entering the combination,

said steps consisting in;

forming a fixed data base containing m random values x_i and the corresponding variables z_i such that z_i =g^xi modp,

generating an exponent k necessary for each signature by carrying out a random linear combination of the values x_i of the base,

computing the variable g^k modp on the basis of the variables zⁱ pertaining to the values xⁱ that come into play in the combination,

using this variable in the exchanges of signals with another entity, said method being characterized in that the generation of the variables k comprises the following other steps;

generating an exponent k such that k=Σ

a_i x_i and such that w of the m values a_i are non-zero, the choice of the a_i non-zero values being obtained randomly,

computing the variable g^k modp in using the values z_i corresponding to the values x_i that enter the linear combination of k.

2. Method of public key cryptography according to claim 1, characterized in that, to form the data base in an entity, the following steps are performed:

generating m random values x_i of N bits using a pseudo-random generator and a secret initial value x₀,

computing the variable z_i =g^xi modp by taking the product of the powers of g modulo p entering the linear combination according to which a value x_i may be broken down,

storing the m pairs (x_i, z_i). in a non-volatile memory of the entity.

3. Method of public key cryptography according to claim 1, characterized in that the steps consist in:

forming an open-ended data base containing n random values of exponents and their power (k_i, g^k i modp),

generating a new exponent k_i+1 necessary for a signature by carrying out a random linear combination of the n values k_i of the base,

computing the variable g^k i+1 modp by obtaining the product of the powers of g entering the linear combination,

updating the base by replacing the pair with this new pair,

using this variable in the exchanges of signals with another entity.

4. Method of cryptography according to claim 3, characterized in that, for an exponent k_t of the base, this exponent is a linear combination with the form:

##EQU3## with h-1=n and in which the coefficients a_i are random positive integers.

5. Method of cryptography according to claim 3, characterized in that the coefficients a_i, i=0 to h-1 are obtained by a random permutation of a fixed sequence.

6. Method of cryptography according to claim 5, characterized in that a new exponent k_t+1 is a linear combination of the other exponents expressed by the relationship:

space="preserve" listing-type="equation">k.sub.t+1 =l.sub.t (k.sub.t+i-(h-1), . . . , k.sub.t),

and l_t is a linear functional.

7. Method of cryptography according to claim 1, characterized in that it can be implemented for microprocessor cards.