Public key cryptography method

Abstract

The invention features a public key cryptography method based on the discrete logarithm which computes a value G.sup.k mod p. Two solutions are proposed to reduce the number of multiplications, one consisting in generating "hollow" k exponents with a few bits of value 1, but of sufficient length to maintain the total security of the system, and the other consisting of performing calculations of the powers of g in parallel while combining the exponents with each other in order to prevent repeating the same power computations twice for a given exponent. The invention is useful for generating digital signatures, authentication and encryption.

Claims

What is claimed is:

1. A public-key cryptography method based on the discrete logarithm using the calculation of the quantity g.sup.k modp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which this quantity acts, characterised in that it includes the following steps for the entity:

generating a random exponent k of length N bits, N being equal to n+b bits,

calculating the Hamming weighting C of this exponent and comparing it with a value h fixed in advance,

checking whether the random value k fulfils the condition C.gtoreq.h

rejecting the random value k where the Hamming weighting is less than h and recommencing the generation of new exponents until an exponent satisfying this condition is obtained,

or keeping this value in the contrary case,

calculating the expression g.sup.k modp from the kept value,

using this expression in the exchanges of electronic signals with the other entity.

2. A method according to claim 1, characterised in that the condition to be fulfilled is c=h.

3. A public-key cryptography method based on the discrete logarithm using the calculation of the quantity g.sup.k modp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which this quantity acts, characterised in that it includes the following steps:

generating a set of random exponents k.sub.j of n bits of weighting a.sub.i expressed by the expression:

k.sub.j =.SIGMA.a.sub.i 2.sup.i

calculating in parallel the powers of .sub.g 2.sup.i whilst combining the exponents so that the powers of g already calculated for an exponent serve for other exponents in which they act,

for each given k.sub.j, calculating the powers of g not yet calculated and grouping together all these powers in order to obtain the required expression gk.sub.j modp,

using these expressions in an exchange of signals with the other entity.

4. A method according to claim 3, characterised in that:

parallel-calculation and grouping-together steps include the following operations:

combining the exponents in pairs in order to obtain exponents k.sub.c which are a reflection of their common parts and reiterating the combinations on the combination result obtained,

calculating the quantities G.sub.kc for each value of k.sub.c such that:

G.sub.kc =g.sup.kc modp

combining an exponent k.sub.j with the exponent k.sub.c obtained for the combination to which this exponent belongs so as to eliminate the common parts and keep only the different parts,

defining exponents k.sup.'.sub.j which are a reflection of the different parts between a given exponent k.sub.j and a given exponent k.sub.c,

calculating quantities G.sub.k'j such that :

G.sub.k'j =g.sup.k'j modp

determining the expressions G.sub.kj modp by performing multiplications between the quantities G.sub.kc obtained at each iteration.

5. A method according to claim 3, characterised in that parallel-calculation and grouping-together steps include the following operations:

combining the exponents together so as to form all the subsets of possible combinations of exponents having common parts,

defining exponents k.sub.c which are a reflection of the common parts, for each subset of combinations such that the non-nil bits of given weighting correspond to the non-nil bits of the same weighting of the combination under consideration,

calculating quantities G.sub.kc for each value of k.sub.c such that: G.sub.kc =g.sup.kc modp

combining each exponent k.sub.j with all the exponents k.sub.c obtained for each subset of combinations to which this exponent k.sub.j belongs so as to eliminate the common parts and keep only the different parts,

defining exponents k'.sub.j which are a reflection of different parts between a given exponent k.sub.j and a given exponent k.sub.c,

calculating quantities G.sub.k'j such that:

G.sub.k'j =g.sup.k'j modp

determining the expressions g.sup.kj modp by performing a multiplication between the quantities G'.sub.kj and G.sub.ko for each k.sub.j.

Description

The object of the present invention is a cryptography method of the so-called public key type based on the discrete logarithm using the calculation of a modulo p quantity.

It finds an application in the generation of digital message signatures, in an authentication session between two entities or in the encoding of data.

In such procedures, security is based on the extreme difficulty that there is in reversing certain functions and particularly the discrete logarithm.

This problem consists, given the mathematical relationship y=g.sup.x modulo p, which will be denoted hereinafter y=g.sup.x modp (which means y is the remainder of the division of g.sup.x by p), of finding x when p, g and y are known. This problem is impossible to resolve, in the current state of knowledge, as soon as the size of p reaches or exceeds 512 bits and the size of x reaches or exceeds 128 bits.

In such systems, there is in general an authority which supplies the number p of large size, constituting the modulus. The authority also chooses an integer g, referred to as the base, such that the set generated by g, i.e. the set formed by the numbers g.sup.x modp) for x belonging to the interval [0, p-1], is a subset of maximum size, at least 2.sup.128.

The parameters p and g are said to be "public", i.e. they are supplied by the authority to all the users attached to this authority.

According to certain variants, these parameters are chosen individually by each user and, in this case, form an integral part of its public key.

A major drawback of the use of cryptographic systems lies in the need to have relatively large calculation and storage means because of the complex calculations which are performed.

This is because the calculation of the quantity g.sup.k modp consists in performing modular multiplications and this is expensive in calculation time and memory space. In simple electronic devices using only standard microprocessors, this type of operation can scarcely be performed.

For electronic devices having a specialised processor for this type of calculation, it is in spite of everything desirable to limit the calculation time and memory space necessary for the intermediate results.

This is because calculating the quantity g.sup.k modp is in general relatively expensive using the conventional method of "square-multiply", known by the English abbreviation SQM, since it is equivalent on average to 3/2 Log.sup.2 (p) multiplications.

According to this method all the powers of g are calculated, i.e. all the squares: g.sup.0, g.sup.1, g.sup.2 . . . g.sub.n, when k is n bits long, since the required multiplications between these powers are performed (for example g.sup.17 =g.sup.1.multidot.g.sup.16)

According to the simple "square-multiply" method, g.sup.k requires n/2 multiplications and n squares.

Where N signatures are to be supplied on a single occasion, Ng.sup.k is produced, and then a parallel calculation is performed.

The parallel "square-multiply" method requires N.times.n/2 multiplications and n squares.

A method proposed by E. BRICKEL et al, referred to by the abbreviation BGKW, makes it possible to reduce the number of multiplications in the case of the square-multiply method but introduces a requirement to store numerous precalculated constants and therefore the need to have a highly disadvantageous quantity of storage memories.

Introducing a parallel calculation of N values into this method entails the use of numerous registers for keeping the intermediate results.

This method therefore becomes much more constraining when there is a situation where it is a case of generating a large number of signatures in a very short time since in this case parallel calculation is introduced.

The object of the present invention is to remedy all these drawbacks. It affords a solution, flexible and inexpensive in calculation time and memory space, to the implementation of cryptographic algorithms for all cryptography systems and in particular by means of portable appliances of the microprocessor chip card type.

According to a first object of the invention, the proposed cryptography method reduces the number of modular multiplications so that savings in calculation times are obtained of 15 to 40% and more depending on the cryptography schemes used (Schnorr or El Gamal).

According to the invention, two solutions are proposed in order to reduce the number of multiplications, one consisting of generating "hollow" exponents k with few bits at 1, but of sufficient length to keep all the security for the system, and the other consisting in performing the calculations of the powers of g in parallel whilst combining the exponents with each other so as not to perform the same power calculation twice for a given exponent.

An object of the invention is more particularly a public key cryptography method based on the discrete logarithm using the calculation of the quantity q.sup.k modp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which this quantity acts, characterised in that it includes the following steps for the entity:

generating a random exponent k of length N bits, N being equal to n+b bits,

calculating the Hamming weighting C of this exponent and comparing it with a value h fixed in advance,

checking whether the random value k fulfils the condition C.gtoreq.h

rejecting the random value k where the Hamming weighting is less than h and recommencing the generation of new exponents until an exponent satisfying this condition is obtained,

or keeping this value in the contrary case,

calculating the expression gkmodp from the kept value,

using this expression in an exchange of electronic signals with the other entity.

Another object of the invention is a public-key cryptography method based on the discrete logarithm using the calculation of the quantity g.sup.k modp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which several quantities of this type act, characterised in that it includes the following steps for the entity:

generating a set of random exponents k.sub.j of n bits of weighting a.sub.i expressed by the expression:

k.sub.j =.SIGMA.a.sub.i 2.sup.i

calculating in parallel the powers of .sub.g 2.sup.i whilst combining the exponents so that the powers of g already calculated for an exponent serve for other exponents in which they act,

for each given k.sub.j, calculating the powers of g not yet calculated and grouping together all these powers in order to obtain the required expression g.sup.kj modp,

using these expressions in an exchange of signals with the other entity.

According to a first embodiment, these steps of calculating in parallel and grouping together include the following operations:

combining the exponents in pairs in order to obtain exponents k.sub.c which are a reflection of their common parts and reiterating the combinations on the combination result obtained,

calculating quantities G.sub.kc for each value of k.sub.c such that:

G.sub.kc =g.sup.kc modp

combining an exponent k.sub.j with the exponent k.sub.c obtained for the combination to which this exponent belongs so as to eliminate the common parts and keep only the different parts,

defining exponents k'.sub.j which are a reflection of the different parts between a given exponent k.sub.j and a given exponent k.sub.c,

calculating quantities G.sub.k'j such that:

G.sub.k'j =g.sup.k'j modp

determining the expressions G.sub.kj modp by performing multiplications between the quantities G.sub.kc obtained at each iteration.

In a second embodiment, the steps of calculating in parallel and grouping together include the following operations:

combining the exponents together so as to form all the subsets of possible combinations of exponents having common parts,

defining exponents k.sub.c which are a reflection of the common parts, for each subset of combinations such that the non-nil bits of given weighting correspond to the non-nil bits of the same weighting of the combination under consideration,

calculating quantities G.sub.kc for each value of k.sub.c such that: G.sub.kc =g.sup.kc modp

combining each exponent k.sub.j with all the exponents k.sub.c obtained for each subset of combinations to which this exponent k.sub.j belongs so as to eliminate the common parts and keep only the different parts,

defining exponents k'.sub.j which are a reflection of different parts between a given exponent k.sub.j and a given exponent k.sub.c,

calculating quantities G.sub.k'j such that:

G.sub.k'j =g.sup.k'j modp

determining the expressions g.sup.kj modp by performing a multiplication between the quantities G'.sub.kj and G.sub.ko for each k.sub.j.

According to another object of the invention, the combinations making it possible to obtain the common parts between the exponents are made by AND logic functions.

According to another object of the invention, the combinations for obtaining the different parts are effected by exclusive-OR logic functions.

Other particularities and advantages of the invention will emerge from a reading of the description made, which is given by way of illustrative and non-limitative example with regard to the drawings, which depict:

FIG. 1, an outline diagram of a system able to implement the invention,

FIG. 2, a functional diagram depicting the essential steps of the method in a first application,

FIG. 3, a functional diagram depicting the essential steps of the method in a second application according to a first embodiment,

FIG. 4, a functional diagram, depicting the essential steps of the method in the second application, according to a second embodiment.

FIG. 1 depicts an outline diagram of a system implementing the cryptography method which is the object of the invention.

This system is formed by an entity E1 wishing to effect exchanges of electronic signals with at least one other entity E2. The two entities are provided respectively with a processing unit (CPU) 11, 30, a communication interface, a random access memory (RAM) 13, 32 and/or a read only memory (ROM) 14, 34 and/or a non-volatile writable or rewritable memory (EPROM or EEPROM) 15, 32 and an address, data and control bus 16, 35.

The processing control unit and/or the ROM contain programs or calculation resources corresponding to the execution of the calculation steps taking part in the method which is the object of the invention, i.e. during an authentication session or during the generation of an electronic signature or during the encoding of electronic signals to be transmitted to the other entity.

The processing unit or the ROM have the necessary resources for multiplications, additions and modular reductions.

Just as the processing unit and/or the ROM have the used cryptography functions proper to each cryptography algorithm and the parameters g and p. The exponents k.sub.j can be loaded in advance into a rewritable memory by the authority or generated as needed from a random generator and a secret source random value ko. The entity E1 also has a secret key x.

The invention applies particularly to the cryptography system set up in the banking field where a high level of security is required during transactions performed on accounts. It is also the case where it is wished to authenticate the sending of messages transmitted in the form of electronic signals from another entity. It is also the case where there is a need to sign messages during exchanges of signals with another entity.

In practice, the entity wishing to perform a transaction may for example be an integrated circuit card such as a chip card, and the destination entity will then be a bank terminal.

The remainder of the description will be given in the context of the application of the method to the signing of digital methods, it being understood of course that the invention applies to any cryptography system based on a discrete algorithm.

The method according to the invention proposes a first solution for considerably reducing the number of multiplications particularly adapted to the case where there is an environment where the memory space is small.

In this case, the principle is to produce exponents k.sub.j which are "hollow" in that the Hamming weighting will be chosen as small as possible, whilst of course preserving the random character of these exponents.

To do this, the method consists of generating exponents k.sub.j either as needed or prior to any exchange. Naturally, in this case, they will be stored in memory. The exponents generated do not have a length of n bits but a greater length n+b bits and fulfilling a condition defined hereinafter.

When an exponent k of n+b bits is generated, the method next consists in calculating the Hamming weighting C of this exponent and then comparing it with a value h fixed in advance.

If at the end of the comparison C.gtoreq.h, the exponent is retained and will be used by the entity, which will then calculate the expression g.sup.k modp and use this expression in the sending of digital signals in which this expression will be used as a signature for example.

Where the parameter C does not fulfil the required condition, the corresponding exponent k is rejected, a new exponent is generated, and the condition verification step is recommenced until an exponent k fulfilling this condition is obtained.

This solution thus makes it possible to have to perform fewer multiplications whilst preserving the same security level as if there were exponents of smaller size.

According to a particular example, making it possible to reduce the number of multiplications to the maximum possible extent, C will be chosen equal to h.

In practice, for an exponent of size n+b bits (with n=log.sub.2 p) whose Hamming weighting is h, in order to have the same number of combinations as when the exponent is of n bits, then the following relationships must be verified:

2.sup.n.ltoreq.C.sup.h.sub.n+b

and (N+b)/2+h.ltoreq.n (a condition which makes it possible to reduce the number of calculations to be performed)

i.e. 2.sup.n.ltoreq.(n+b)!/(n+b-h)!h!

and b+2h.ltoreq.n

The numbers b and h which are chosen are obtained by resolving this double inequality for a given n (n=160 for example).

By way of illustration, the results of the method according to the invention were compared with the known methods.

In the case of the Schnorr algorithm where n=160 bits, and in the case of the E1 Gamal algorithm where n=512 bits. These results are indicated in the following table.

         Variant {character pullout}                  El Gamal      El Gamal
                                      Calculation     Memory
        effort {character pullout}     Schnorr        time          space
        multiplications     62 (h)        187 (h)       199 (h)
        SQUARE          87 (b = 15)   279 (b = 52)  273 (b = 35)
        EFFORT              149           469           472
        GAIN               6.8%          9.4%          7.8%

     Variant {character pullout} Hollow exponent      Hollow       Simple
                        calculation       exponent      square-
    effort {character pullout}      time         memory space    multiply
    multiplications       37 (h)           49 (h)       n/2
    squares           n/2 + 7 (b = 14)  n/2 + 2 (b = 4)  n/2
    total                n/2 + 44         n/2 + 51      n

     variant {character pullout}  hollow
                  exponent       hollow       simple
                  calculation     exponent      square-
    effort {character pullout}   time      memory space    multiply    GAIN
    Schnorr          124           131          180     22.5%
    (m = 2s)
    El Gamal         300           307          512       41%
    (m = 2s)
    Schnorr          204           211          240       15%
    (m = s)
    El Gamal         556           563          728       24%
    (m = s)

                                      Methods
                                      Parallel       Combination
                       Square-         square-       of exponent
    Effort time       multiply        multiply       binary tree
    Square            N (n - 1)         n - 1           n - 1
    multiplication   N (n/2 - 1)     N (n/2 - 1)        Nn/3
    Total           N (3n/2 - 2)  N (n/2 - 1) + n - 1 Nn/3 + n - 1
    Effort for N>>n     100%             33%             22%

• Inventors
  M'Raihi, David; Naccache, David;
• Assignee
  Gemplus (Gemenos, FR)
• Published
  Oct-1-2002
• Current US Classes:
  380/30
• Application #
  194980
• International Classes
  H04L 009/30
• Field of Search
  380/30 380/28 380/44 708/270 708/277 708/490
• Examiner
  Smithers; Matthew
• Agent
  Plottel; Roland
• US Patent References:
  5204901
  5483597