FR2734679A1 - Public key encryption based on discrete logarithms - Google Patents

Abstract

The public key cryptographic method generates a random exponent k of length N bits. The Hamming weights C of the exponent are computed and compared to a pre-set value h to determine whether the random value k produces Hamming weights greater than the pre-set value. If it does not the exponent k is rejected and a new random exponent is generated and tested. A value k that generates satisfactory Hamming weights is retained, and used to compute the expression y = g<x>(modp), where g is an integer base and p the modulus, and x is unknown. This expression is then used the exchanges of information with the other entity in the communication.

Description

PUBLIC KEY CRYPTOGRAPHY PROCESS
BASED ON DISCREET LOGARITHM
The present invention relates to a so-called public key cryptography method based on the discrete logarithm involving the calculation of a modulo p quantity.

It finds an application in the generation of digital signatures of messages, in a transfer of authentication between two entities or in the encryption of data.

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

This problem consists, given the mathematical relation y = gXmodulop which we will subsequently denote by y = gXmodp (which means y is the remainder of the division of gX by p), to find x when we sound p, g and y. This problem is impossible to solve, in the current state of knowledge, as soon as the size p reaches or exceeds 512 bits and that of x reaches or exceeds 128 bits.

In such systems, there is generally an authority which supplies the large number p constituting the module. The authority also chooses an integer g, called base such that the set generated by g that is to say the set formed of the numbers gXmodp, for x belonging to the interval [0, pi] is a subset of maximum size, at least 2128.

The parameters p and g are said to be "public", that is to say that they are provided 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 his public key.

A major drawback to the implementation of cryptographic systems lies in the need to have relatively large calculation and storage means due to the complex calculations which are carried out.

Indeed, the calculation of the magnitude gkmodp consists in carrying out modular multiplications and this is costly in calculation time and in memory space. In simple electronic devices using only standard microprocessors, this type of operation is hardly possible.

For electronic devices having a specialized processor for this type of calculation, it is despite everything desirable to limit the calculation time and the memory space required for the intermediate results.

Indeed, the calculation of the size gkmodp is in general relatively expensive by the classic method of the "square-multiplied" known by the English abbreviation SQM (Square-Multiply) since it is equivalent on average to 3/2 Log2 (p) multiplications.

According to this method, we calculate all the powers of g, i.e. all the squares: go, gl, g2 ... .gn, when k is of length n bits, then we carry out the required multiplications between these powers (for example g17 = g1.g16).

According to the simple "multiplied square" method gk requires n / 2 multiplications and n squares.

In the case where N signatures are to be provided at once, one produces Ngk, one then carries out a parallel computation.

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

A method proposed by E. BRICKELL et al.

denominated by the abbreviation BGKW makes it possible to reduce the number of multiplications in the case of the square-multiplied method but introduces a need to store many precomputed constants and therefore the need to have a very penalizing quantity of storage memories.

The introduction of a parallel calculation of N values in this method involves the use of many registers to keep the intermediate results.

This method therefore becomes more restrictive in the case where one is in a situation where it is a question of generating a large number of signatures in a very short time since in this case parallel computation is introduced.

The object of the present invention is to remedy all these drawbacks. It makes it possible to provide a flexible and inexpensive solution in terms of computation time and memory space for the implementation of cryptographic algorithms for all cryptography systems and in particular by portable devices of the microprocessor chip card type.

According to a first object of the invention, the proposed cryptography method makes it possible to reduce the number of modular multiplications in such a way that one obtains computation time savings 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 in generating "hollow" exponents k with few bits at 1, but of sufficient length to keep the system completely secure, and l 'another consisting in carrying out the calculations of the powers of g in parallel while combining the exponents between them so as not to repeat the same power calculation twice for a given exponent.

The subject of the invention is more particularly a public key cryptography method based on the discrete logarithm involving the calculation of the quantity qkmodp where p is a prime number called modulus, k a random number usually of length n bits and g an integer. called base, in which an entity E performs authentication and / or signature and / or encryption operations, comprising exchanges of signals with another entity in which this quantity intervenes, characterized in that it comprises the following steps for the entity
- generate a random exponent k of length N bits, N being equal to n + b bits,
- calculate the Hamming weight C of this exponent and compare it to a value h fixed beforehand,
- check if the random value k fulfills the condition C 2 h
- reject the random value k in the case where the Hamming weight is less than h and start the generation of new exponents again until an exponent satisfying this condition is obtained,
- or keep this value otherwise,
- calculate the gkmodp expression from the stored value,
- use this expression in an exchange of electronic signals with the other entity.

The subject of the invention is also a public key cryptography method based on the discrete logarithm involving the calculation of the quantity gkmodp where p is a prime number called modulus, k a random number usually of length n bits and g an integer called base, in which an entity E performs authentication and / or signature and / or encryption operations, comprising exchanges of signals with another entity in which several quantities of this type intervene, characterized in that it comprises the next steps for the entity
- generate a set of random exponents kj of n bits of weight ai expressed by the expression k. Cai2
- calculate in parallel the powers of g2i while combining the exponents so that the powers of g already calculated for an exponent are used for other exponents in which they occur,
- for each given kj, calculate the powers of g not yet calculated and combine all these powers to obtain the desired expression gkj modp,
- use these expressions in an exchange of signals with the other entity.

According to a first embodiment, the steps of parallel computation and of grouping comprise the following operations
- combine the exponents two by two to obtain exponents kc reflection of their common parts and reiterate the combinations on the combination result obtained,
- calculate quantities Gkc for each value of kc such that
Gkc = gkcmodp
- combine an exponent kj with the exponent kc obtained for the combination to which this exponent belongs so as to eliminate the common parts and keep only the different parts,
- define exponents k '. reflection of the different parts between a given exponent kj and a given exponent kc,
- calculate quantities Gk, such that
Gk, j = gkjmodp
- determine the expressions Gkjmodp by operating multiplications between the quantities GkC obtained at each iteration.

In a second embodiment, the parallel calculation and grouping steps include the following operations
- combine the exhibitors together so as to form all the subsets of possible combinations of exhibitors having common parts,
- define exponents kc reflection of the common parts, for each combination subset such that the non-zero bits of a given weight correspond to the non-zero bits of the same weight of the combination considered,
- calculated quantities GkC for each value of kc such as :: GkC = gkcmodp
- combine each exponent kj with all the exponents kc obtained for each combination subset to which this exponent k. belongs in such a way as to eliminate the common parts and keep only the different parts,
- define exponents k'j reflecting the different parts between a given exponent kj and a given exponent kc,
- calculate quantities Gk, j such that Gk'j = gk'jmodp
- determine the expressions gkjmodp by operating a multiplication between the quantities GSkj and Gkc for each kj.

According to another object of the invention, the combinations making it possible to obtain the common parts between the exponents are produced by logical “AND” junctions.

According to another object of the invention, the combinations making it possible to obtain the different parts are carried out by "exclusive-OR" logic functions.

Other features and advantages of the invention will become apparent on reading the description which is given and which is given by way of illustrative and non-limiting example and with reference to the drawings which represent
- Figure 1, a block diagram of a system capable of implementing the invention,
- Figure 2, a functional diagram representing the essential steps of the method in a first application,
FIG. 3, a functional diagram representing the essential steps of the method in a second application according to a first embodiment,
FIG. 4, a functional diagram, showing the essential steps of the method in the second application, according to a second embodiment,
FIG. 1 shows a block diagram of a system for implementing the cryptography method which is the subject of the invention.

This system is formed by an entity E1 wishing to exchange 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 write-once memory (ROM) 14 , 34 and / or a writable or rewritable non-volatile memory (EPROM or EEPROM) 15, 33 and an address, data, 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 involved in the method which is the subject of the invention, that is to say during a authentication session or during the generation of an electronic signature or during the encryption of electronic signals to be transmitted to the other entity.

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

Just as the processing unit and / or the ROM include the cryptography functions used specific to each cryptography algorithm and the parameters g and p. The exponents kj can be loaded beforehand into a memory that can be rewritable by the authority or, generated as they go from a random generator and a secret source random value ko. The entity El also has the secret key x.

The invention applies most particularly to the cryptographic system implemented in the banking sector where great security is required during transactions carried out on accounts. This is also the case where it is desired to authenticate the sending of messages transmitted in the form of electronic signals from another entity. This is also the case where one needs to sign messages when exchanging signals with another entity.

In practice, the entity wishing to carry out a transaction could be, for example, an integrated circuit card such as a chip card and the recipient 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 messages, it being understood 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, which is particularly suited to the case where there is an environment where the memory space is low.

In this case, the principle is to produce "hollow" exponents kj in the sense that the Hamming weight will be chosen as low as possible, while of course preserving the randomness of these exponents.

For this, the method consists in generating exponents kj either as and when required or before any exchange. Of course in this case they will be remembered. The generated exponents do not have a length of n bits but a length greater than n + b bits and fulfill a condition defined below.

When an exponent k of n + b bits is generated, the method then consists in calculating the Hamming weight
C of this exponent then to compare it with a value h fixed beforehand.

If at the end of the comparison Ch then the exponent is retained and will be used by the entity which will then calculate the expression gkmodp and use this expression in sending digital signals in which this expression will be used as a signature for example.

If the parameter C does not meet the required condition, the corresponding exponent k is rejected, a new exponent is generated, the condition checking step is restarted until an exponent k fulfilling this condition is obtained. .

Thus this solution makes it possible to have to carry out less multiplication while maintaining the same level of security as if one had exhibitors of smaller size.

According to a particular example, making it possible to reduce the number of multiplications as much as possible, we will choose
C = h.

In practice, for an exponent of size n + b bits (with n = log2 P) whose Hamming weight is h, for
have the same number of combinations as when the exponent is n bits, then the following relations must be verified
2n <Ch
n + b
and (N + b) / 2 + h S n (condition which makes it possible to reduce the number of calculations to be carried out).

ie 2n <(n + b)! / (n + b - h)! h!
and
b + 2h <n
The numbers b and h that we fix are obtained by solving this double inequality for a given n (n = 160 for example).

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

In the case of the Shnorr algorithm where n = 160 bits, and in the case of the El Gamal algorithm where n = 512 bits. These results are shown in the table below.

<tb>

<SEP> variant <SEP> o <SEP> Schnorr <SEP> El <SEP> Gamal <SEP> El <SEP> Gamal
<tb><SEP> Time <SEP> of <SEP> Space <SEP> of
<tb> effort <SEP> ss <SEP> calculation <SEP> memory
<tb> multiplications <SEP> 62 <SEP> (h) <SEP> 187 <SEP> (h) <SEP> 199 <SEP> (h) <SEP>
<tb><SEP> SQUARE <SEP> 87 (b = 15) <SEP> 279 (b = 52) <SEP> 273 (b = 35)
<tb><SEP> EFFORT <SEP> 149 <SEP> 469 <SEP> 472
<tb><SEP> GAIN <SEP> 6.8% <SEP> 9.4% <SEP> 7.8%
<tb>
The constraint placed on the signature space covered by exponents of n bits can be reduced by a factor a depending on the level of security that is desired.

The parameters n, h and b must then fulfill the condition (1)
(1) 2 na <(n + b)! / (N + bh)! H!
while retaining the possibility of generating the same signatures from different random bits of (n + b) bit size.

In practice 280 is enough to counter the various possible attacks and therefore na = 100 is a very acceptable value.

<tb>

variant <SEP>#<SEP><SEP> Exponent <SEP> Exponent <SEP> square
<tb><SEP> hollow <SEP> hollow <SEP> multiplied
<tb><SEP> time <SEP> place <SEP> simple
<tb> effort <SEP> ss <SEP> of <SEP> calculated <SEP> memory
<tb> multiplications <SEP> 37 <SEP> (h) <SEP> 49 <SEP> (h) <SEP> n / 2
<tb><SEP> squares <SEP> n / 2 + 7 <SEP> n / 2 + 2 <SEP> n / 2
<tb><SEP> (b = 14) <SEP> (b = 4)
<tb> Total <SEP> n / 2 + 44 <SEP> n / 2 + 51 <SEP> n
<tb>
This variant execution is all the more interesting as the cost (in computation time) of a square is often less than that of a modular multiplication.

In general we get
s / 2 S m <s, s being the number of squares to be calculated and m the number of multiplications, the two extreme cases being m = s and m = 2s.

Comparative results for these two extreme cases have been shown in the following table.

<tb><SEP> variant <SEP> exponent <SEP> exponent <SEP> square <SEP> GAIN
<tb><SEP> hollow <SEP> hollow <SEP> multiplied
<tb> effort <SEP> ss <SEP> time <SEP> of <SEP> place <SEP> simple
<tb><SEP> calculation <SEP> memory
<tb><SEP> Schnorr <SEP> 124 <SEP> 131 <SEP> 160 <SEP> 22.5%
<tb><SEP> (m = 2s)
<tb><SEP> El <SEP> Gamal <SEP> 300 <SEP> 307 <SEP> 512 <SEP> 41%
<tb><SEP> (m = 2s)
<tb><SEP> Schnorr <SEP> 204 <SEP> 211 <SEP> 240 <SEP> 15%
<tb><SEP> (m = s)
<tb>

<tb> El <SEP> Gamal <SEP> 556 <SEP> 563 <SEP> 728 <SEP> 24%
<tb><SEP> (m = s)
<tb>
It can be seen that the gain obtained when the method is applied to the Shnorr and El Gamal diagrams is very important compared to the simple multiplied square method and even in the case where we consider that the cost of a square is the same as that of a multiplication.

According to another embodiment, the method applies most particularly to systems not having any particular constraint concerning the memory space.

In this embodiment, the various powers of g are calculated in parallel in order to calculate the squares only once, while combining the exponents so as not to carry out the same calculation several times.

To fully understand the invention, we will describe the case where the calculation of two powers has been performed.

let k. = ài2i, kj being drawn randomly (i.e. generated from a random generator)
let kk = Kj = bi2i
According to the process, the exponents k are combined. and kk so as to define an exponent kc such that
kc = àibi2i reflects common parts between k and kk. The coefficients ai are either 1 or 0.

The exponent kc corresponds to the common part of the exponents kj and kk, i.e. if kj = 1 x 210 + ... + 0 + 1 x 20 and kk = 1 x 210 + 0 + 0 ... + 1 x 20
kc = ix 210 + 0 + ... + 1 x 20.

According to the method, the exponent k denoted kc is thus determined by means of a logic function AND.

A second combination is then carried out consisting in determining the distinct parts between the exponent kj and the exponent kc. The distinct parts between the exponent kk and the exponent kc are also sought.

We will denote by kj $ k c and kk kc these combinations 3 kk kc which are carried out for exclusive-ORs.

The following quantities are calculated in parallel
Gkj = gkj d3 kcmodp
Gkk = gkk z kcmodp
Gkc = gkcmodp
To obtain gkjmodp and Gkkmodp all you have to do is perform the operations
1) Gkj X Gkcmodp
2) Gkk x Gkcmodp
When we have, like the example just given, two powers, we carry out on average about 3n / 4 multiplications instead of n multiplications. The gain is 25%;
The method according to the invention can be generalized to a larger number of combinations of exponents. This generalization can also be implemented according to two embodiments illustrated by the functional diagrams given in Figures 3 and 4.

In this case, the invention applies most particularly to cases where it is necessary to generate a large number of signatures.

According to the first embodiment, combinations of exponents are made two by two following a tree structure as represented by the table below.
k. al a2 a3 a4
kc bl = al.a2 b2 = a3.a4
cl = bl.b2
These combinations make it possible, like the example described above, to provide exponents kc reflecting the common parts between the exponents kj.

To simplify the writing, the exponents kj are named a1, a2, a3, a4.

The exponents k c are named at level -1 of the tree, b1 and b2 and at level -2 of the tree by c1.

The combinations a1. a2, a3. a4 are performed by an AND logic function.

The combinations are reiterated at each level of the tree thus constituted. the number of multiplications decreases as one goes deeper into the tree due to the simple statistical distribution of the bits. The computational effort to be made is reduced by n / 3 multiplications.

As that was described previously, one determines sizes Gkc at each level.

So we will get
G al = gal # blmodp
Ga2 = ga2 $ blmodp
Gbl = gbîmodp
Gbl = gbl # clmodp or Gbl = Gbl Cl modp
Gb2 = gb2 &commat; cimodp or Gb2 # Gb1 modp
Gc1 = gcl modp
Gal modp = Ga1 x Gb1 modp = Ga1xGb1 x G c1 modp
In practice, galmodp will be obtained by the product Ga1 x Gb1 modp and ga2 modp will be obtained by the product Ga2 x Gblx Gc1 modp.

According to a second embodiment, the exponents are combined so as to form all the possible combination subsets, for example if we have as exponent kj: a, b, c, we will form the combinations ab, ac, bc, abc.

Combinations are therefore made making it possible to define the common parts relating to these subsets by operating a logic function AND between a and b, a and c, b and c and a, b, c. We thus define an exponent kc for each subset obtained.

We can calculate in parallel all the quantities
Gkc = g kcmodp for which kc have few bits at 1 compared to the initial k and therefore for which the modular calculation is fast.

Then another type of combination is carried out, consisting in eliminating the common parts between an exponent and the preceding combinations.

These combinations are achieved by means of logical exclusive-OR functions. Thus, following the example given, we obtain
ka = a xor abc xor ac xor ab
kb = b xor abc xor ab xor bc
kc = c xor abc xor ac xor bc
We can then calculate quantities G krj = gkj modp for which the k'j have even fewer bits at 1 than the initial kc and for which the modular modifications are even faster.

Finally, the gkjmodp expressions are obtained by kj.

In the case of the generation of N signatures obtained by this second embodiment, the computational effort will tend towards
n / N squares + n (2N-1) / N2N + (2N-1-l) multiplications.

The following table makes it possible to give results of comparisons with known methods such as the square-multiplied, the square multiplied in parallel and the invention.

<tb>

<SEP> Methods
<tb><SEP> Square <SEP> Square <SEP> Combination
<tb><SEP> Time <SEP> of <SEP> multiplied <SEP> of exponent
<tb><SEP> effort <SEP> multiplied <SEP> parallel <SEP> shaft
binary <tb><SEP>
<tb><SEP> Squares <SEP> N (nl) <SEP> nl <SEP> nl
<tb><SEP> Multiplication <SEP> N (n / 2-1) <SEP> N (n / 2-1) <SEP> Nn / 3
<tb><SEP> TOTAL <SEP> N (3n / 2-2) <SEP> N (n / 2-l) + n-1 <SEP> Nn / 3 + nl
<tb> Force <SEP> for <SEP>N>> n <SEP> 100% <SEP> 33t <SEP><SEP> 22%
<tb>
The first given embodiment (tree grouping) in the case of the application to the generation of N signatures is inexpensive in terms of memory space.

For a binary tree with 4 exponents, 8 registers of log2 (p) bits will be needed for the calculations.

The second given embodiment (N groupings) is very inexpensive in computing time because it is optimal in terms of number of multiplication. For 3 exponents, 8 registers of log2 (p) bits will be needed for the calculations.

Claims (5)

1. A method of public key cryptography based on the discrete logarithm involving the calculation of the quantity gkmodp where p is a prime number called modulus, k a random number usually of length n bits and g an integer called base, in which an entity E performs authentication and / or signature and / or encryption operations, comprising exchanges of signals with another entity in which this quantity occurs, characterized in that it comprises the following steps for the entity: - generate a random exponent k of length N bits, N being equal to n + b bits, - calculate the Hamming weight C of this exponent and compare it to a value h fixed beforehand, - check if the random value k fulfills the condition: C 2 h - reject the random value k in the case where the Hamming weight is less than h and recommend the generation of new exponents until an exponent satisfying this condition is obtained, - or keep this value otherwise, - calculate the gkmodp expression from the stored value, - use this expression in the exchange of signals with the other entity. 2. Method according to claim 1, characterized in that the condition to be fulfilled is c = h. 3. Public key cryptography method based on the discrete logarithm involving the calculation of the quantity gkmodp where p is a prime number called modulus, k a random number usually of length n bits and g an integer called base, in which an entity E performs authentication and / or signature and / or encryption operations, comprising exchanges of signals with another entity in which this quantity intervenes, characterized in that it comprises the following steps - generate a set of random exponents kj of n bits of weight ai expressed by the expression kj = ai2i - calculate in parallel the powers of g21 while combining the exponents so that the powers of g calculated for an exponent are used for other exponents in which they occur, - for each k. given, calculate the powers of g not yet calculated and combine all these powers to obtain the desired expression gkjmodp, - use these expressions in an exchange of signals with the other entity. 4. Method according to claim 3, characterized in that - the parallel calculation and grouping steps include the following operations - combine the exponents two by two to obtain exponents k c reflection of their common parts and reiterate the combinations on the combination result obtained, - calculate the quantities Gkc for each value of k c such that Gkc = gkcmodp - combine an exponent k. to the exponent k c obtained for the combination to which this exponent belongs so as to eliminate the common parts and keep only the different parts, - define exponents k, j reflecting the different parts between a given exponent kj and a given exponent k c, - calculate quantities Gk, j such that Gk, j = gmodp - determine the expressions Gkjmodp by operating multiplications between the quantities GkC obtained at each iteration. 5. Method according to claim 3, characterized in that the steps of parallel calculation and grouping comprise the following operations - combine the exhibitors together so as to form all the subsets of possible combinations of exhibitors having common parts, - define exponents k c reflection of the common parts, for each combination subset such that the non-zero bits of a given weight correspond to the non-zero bits of the same weight of the combination considered, - calculated quantities Gkc for each value of k c such as:: GkC = gkcmodp - combine each exponent kj with all the exponents k c obtained for each combination subset to which this exponent k. belongs in such a way as to eliminate the common parts and keep only the different parts, - define exponents k '. reflection of the different parts between an exponent k. given and a given exponent k c, - calculate quantities Gk, j such that Gk, j = gk imodp - determine the expressions gkjmodp by operating a multiplication between the quantities G'kj and GkC for each kj.