FR2903258A1 - CRYPTOGRAPHIC SYSTEM AND METHOD WITH A PUBLIC KEY FOR THE AUTHENTICATION OF A FIRST ENTITY BY A SECOND ENTITY - Google Patents

Abstract

A public key cryptographic system and method for authenticating a first entity (E1) having a secret key S associated with a public key P by a second entity (E2) having said public key P, said secret key S belonging to a first or a second group (G1, G2) respectively generated by first and second primitive g, and g2 of first order q, said method comprising the following steps: - sending a challenge by the second entity (E2) to the first entity (E1), - computation by the first entity (E1) of a response taking into account said challenge and said secret key S, - sending by the first entity (E1) of said response to the second entity, and- checking the response by the second entity (E2) using said challenge and the public key P, said public key P comprising, on the one hand, a public value v = e (g1, S) or v = e (S, g2) equal to the image by a bile application n is defined on said first and second groups (G1, G2) of a pair of elements formed by the secret key S and the primitive belonging to the other of the first and second groups (G1, G2) than that to which the secret key S, and on the other hand this primitive.

Description

Title of the Invention Public Key System and Cryptographic Method

  for authentication of a first entity by a second entity.

  TECHNICAL FIELD OF THE INVENTION The invention relates to the field of cryptography. More particularly, that of public key cryptography for the authentication of a first entity having a secret key associated with a public key by a second entity having the public key. By way of example, the invention can be used for the protection against the fraud of an electronic chip in transactions between an application and the chip. BACKGROUND OF THE INVENTION Currently, smart cards are susceptible to different types of fraud. A first type of fraud involves duplicating the card without authorization, the term cloning being often used to characterize this operation. A second type of fraud consists of modifying the data attached to a card, in particular the amount of the credit entered in the card. To fight against these frauds, cryptography is used, on the one hand to ensure the authentication of the card by means of authentication and / or to authenticate the data by means of a digital signature, and on the other hand to ensure the confidentiality of the data by means of encryption. In general, cryptography involves two entities, which are in the case of authentication a verifier and an object to be verified, and it can be either symmetrical or asymmetrical. When it is symmetric (or "secret key", the two terms being synonymous), the two entities share exactly the same information, in particular a secret key. When it is asymmetric (or "public key", the two terms being synonymous) one of the two entities has a pair of keys, one of which is secret and the other is public; there is no shared secret key.

The first authentication mechanisms developed in symmetric cryptography consist in calculating once and for all an authentication value, different for each card, in storing it in the memory of the card, in reading it at each transaction and in verifying it in querying a network application capable of implementing the transaction, where the previously assigned authentication values are either stored or recalculated. These mechanisms provide insufficient protection because the authentication value can be spied upon, reproduced and replayed fraudulently since it is always the same for a given card; a fraudster can thus make a clone of this card. To combat clones, passive card authentication mechanisms are replaced by active authentication mechanisms that can further ensure the integrity of the data. The general principle of the symmetric active authentication mechanisms is as follows: during an authentication, the electronic chip and the application calculate an authentication value which is the result of a function applied to a given list of arguments at each authentication; the argument list may comprise a hazard (the hazard being a piece of data determined by the application at each authentication), a piece of data contained in the electronic chip and a known secret key of the electronic chip and the application. When the authentication value calculated by the electronic chip is identical to the authentication value calculated by the application, the electronic chip is deemed authentic and the transaction between the electronic chip and the application is authorized.

However, the secret key mechanisms require that the verification device, in charge of the authentication of the chip, such as those present in a public telephone, an electronic payment terminal, or even a public transit gate, know the secret key held by said chip. A major disadvantage is that, if it is desired that said device can authenticate any chip issued in connection with the application, or it must store the secret keys of all chips, or it must store a basic key, also called mother-key or master key, to find the secret key 10 of any chip. In both cases, each of these devices stores enough information to be able to retrieve the secret keys of all the chips issued, and thus stores enough information to be able to make clones of any of them. It follows that a successful intrusion against any of the verification devices would destroy the security of the application as a whole. Thus, solutions based on public key cryptography may be preferred over secret key mechanisms. The operating principle of public key authentication mechanisms is then as follows: the chip seeking to authenticate calculates values depending on its private key (which is associated with its public key) and possible random parameters; the application then checks the consistency of the values calculated by the chip without requiring knowledge of the private key of the chip; only the use of the public key of the smart card is necessary as well as any other non-secret parameters. It is also possible that the chip is authenticated to the application but also that the chip authenticates the application with which it communicates. In this case, the term "mutual authentication" is used. This type of mutual authentication is done simultaneously running two conventional authentication methods where the chip and the application interchange roles in both protocols. The most known solutions making it possible to carry out such authentication mechanisms are generally based on difficult mathematical problems such as factoring or discrete logarithm, these two problems generate in their realization calculations of modular exponentiations, that is to say calculations of the type xe modn where "mod" corresponds to the mathematical function of modular reduction. This type of calculation is a priori the most complex operation that can be performed in a reasonable time (without any particular assumption on computing power) by a smart card. However, if we find efficient algorithms to solve these problems, then these problems would become unusable in cryptography. Therefore, it is essential to start looking for mathematical problems of another nature and authentication mechanisms using these new problems. In recent years, bilinear applications, well known to mathematicians, have appeared in the field of cryptography. Consider, for example, an mapping f defined on the set G, xG2 in G where G ,, G, and G are groups (mathematical notion). Suppose g, and g, generators (or primitives) respectively of G, and G2, the function f is bilinear of G, xG2 in G if f (g,, g = f (gag,) ah. these bilinear applications are that their evaluations generate enormous computations, much more complex than the computation of a (simple) modular exponentiation, hence the difficulty in a classical framework of making such calculations. Existing solutions appear to be very inefficient in allowing them to be used for mutual authentication.

Currently, there are two authentication schemes using bilinear applications. The first protocol is described in the article by G. Yao, G. Wang, and Y. Wang titled "An Improved Identification Scheme," Progress in Computer Science and Applied Logic, Berkhauser-Verlag, November 2003. The second protocol is described in the article by Kim and K. Kim entitled "A New Identification Scheme Based on the Bilinear Diffie-Hellman Problem", 7th Australian Conference on Information Security and Privacy, ACISP '02, pages 362-378, Springer-Verlag 2002. Figure 4 illustrates a table detailing the characteristics of the Wang and Wang protocol (referenced M1) and that of Kim and Kim (M2 referenced). Each protocol M1 or M2 can be characterized by the number of mathematical operations necessary to carry out an iteration between an electronic chip E101 and an application E102. These operations comprise the number of phases (referenced NP) of data transfer, the number of exponentiations (referenced NE) by an exponent of the same size as that of the order of the primitive g and the number of evaluations (referenced NB ) a bilinear application. In fact, the first column of the table indicates the type of protocol M1 or M2, the second column indicates the entity EN (that is to say, the chip E101 or the application E102), the third column indicates the number of evaluations NB of a bilinear application, the fourth column indicates the number of exponences NE by an exponent of the same size as that of the order of g and the fifth column indicates the number of 25 phases NP of data transfer . It should be noted that the values given are average values. In addition, these values are given for methods that do not perform precalculations, which remain a very contextual possibility. This makes it possible to make the comparison between the different methods objective and easy.

These protocols have very interesting security properties but in practice require a lot of calculations. This presents a great obstacle to their development.

OBJECT AND SUMMARY OF THE INVENTION The present invention relates to a public key cryptographic method for authenticating a first entity having a secret key S associated with a public key P by a second entity having said public key P, said key secret S belonging to a first or a second group (G 1, G 1) respectively generated by first and second primitives g, and g, of first order q, said method comprising the following steps: - sending a challenge by the second entity to the first entity, - calculation by the first entity of a response taking into account said challenge 15 and said secret key S, - sending by the first entity of said response to the second entity, and - verification of the response by the second entity using said challenge and the public key P. Said method is remarkable in that said public key P 20 comprises, on the one hand, a public value v = e (g, S) or v = e (S, g,) equal to the image by a bilinear application e defined on said first and second groups (G ,, G,) of a pair of elements formed by the secret key S and the primitive belonging to the other of the first and second groups (G ,, G,) than the one to which the secret key S belongs, and on the other hand this primitive. Thus, the authentication protocol of the present invention allows the use of a bilinear application with a calculation cost lower than existing schemas, which allows secure and efficient authentication between the two entities. This protocol finds a very advantageous application in the use of new processes currently considered too expensive in computing time. The present invention therefore aims to propose a new solution to effectively reduce this computing time.

Advantageously, said public key P further comprises identical public parameters for any first entity, said public parameters comprising a first parameter equal to the first primitive g a second parameter equal to the second primitive g2, and a third parameter v = e (g, , g2) equal to the image by said bilinear application e of said first and second primitives g, and g2. Setting these parameters universally and publishing them simplifies calculations. According to one embodiment, the method according to the invention comprises the following steps: -choice by the first entity of a first natural number r, -send by the first entity to the second entity of a first value W = e (g ,, g)) 'equal to the image by the bilinear application e of the pair (g ,, g_) formed by said first and second primitives brought to the power of said first natural number r, 20 -choice by the second entity of a second natural number c defining said challenge, - sending said second natural number c to the first entity, - calculating by the first entity a second value Y = g, rS` or Y = g, S` defining said response, said second value being equal to the product between a first term g 'or g, r, and a second term S`, said first term g; or g; being equal to the primitive belonging to the same group as that of the secret key brought to the power of said first natural number r, and said second term S` being equal to the secret key S brought to the power of said second natural number c, 2903258 8 - sending said second value Y to the second entity, and -checking by the second entity if the image e (g, Y) or e (Y, g) by the bilinear application e of the pair formed by said primitive belonging to to the other of the first and second groups (G ,, G,) and said second value Y is equal to the product Wv` between said first value W and said public key v brought to the power of said second natural number c. Thus, the validation or the non-validation of the verification step makes it possible to consider that the authentication is successful or not successful respectively. In either case, the calculation operations between the first and second entities can be performed with only one linear application evaluation, four exponentiations and three transfer phases, which represents a global computational cost. less than the current authentication schemes. Advantageously, said first value W = e (g, g,) r and / or said first term gz or g; are precalculated. This makes the online execution of the protocol faster, since the first values have already been calculated offline. According to a feature of the invention, said steps are repeated a predetermined number of times in parallel or sequential manner. Thus, the security of the authentication is increased. According to a variant, the first and second groups (G 1, G 1) are equal and comprise a common primitive g the primitives g, and g, then being both equal to g. This reduces the number of data to be published. The invention also relates to a public key cryptosystem comprising a first entity having a secret key S associated with a public key P and a second entity having said public key P, said system being adapted for implementing the cryptographic method according to at least one of the above features. The invention also relates to an electronic chip card adapted for implementing the cryptographic method according to at least one of the above characteristics. The invention also relates to a computer program downloadable from a communication network and / or stored on a computer readable medium and / or executable by an electronic chip, comprising code instructions for executing the steps of the cryptographic method according to unless one of the above features, when executed on a computer or an electronic chip. BRIEF DESCRIPTION OF THE DRAWINGS Other features and advantages of the invention will emerge from a reading of the description given below, by way of indication but without limitation, with reference to the appended drawings, in which: FIG. 1 schematically illustrates a public key cryptosystem comprising a first entity and a second entity, according to the invention; FIG. 2 illustrates a table detailing the characteristics of the cryptographic method according to the invention; FIG. 3 is an example schematically illustrating the main steps of the authentication of the first entity by the second entity; and FIG. 4 illustrates a table detailing the characteristics of the cryptographic methods according to the prior art. DETAILED DESCRIPTION OF EMBODIMENTS In accordance with the invention, Figure 1 schematically illustrates a public key cryptosystem having a first entity El and a second entity E2. The first entity El and the second entity E2 can be interconnected via a communication line 3 by contact or remotely or via a communication network. The first entity El can be an object to check such as a chip of a phone card, credit card or ticket. The second entity E2 may be an application or a verification device 10, in charge of the authentication of the first entity El, such as those present in a public telephone, an electronic payment terminal or a transit gate. The first entity El has a public key P and a secret key S associated with this public key P, and the second entity E2 has the public key P. The secret key S belongs to a first group or a second group (G ,, G,) respectively generated by first and second generators or primitives g, and g2 of order y, where y is a prime number preferably large (for example q> 2160) 20 Indeed, we assume the existence of a bilinear mapping e defined on G1 xG2 and with a value in a third group G, so that the groups G, and G, are respectively generated by the elements g, and g2 of order q (that is to say e (g;, g;) = e (g1, g, Y) for all a and all b). According to the invention, the public key P comprises on the one hand a public value v equal to the image by the bilinear application e defined on the first and second groups (G1, G2) of a pair of elements. formed by the secret key S and the primitive belonging to the other of the first and second groups (G ,, G,) than that to which the secret key 5 belongs (i.e. v = e (g, , S) or v = e (S, g2) and on the other hand, this primitive (i.e., g, or g, respectively), More particularly, the public key may correspond to a quadruplet having three parameters in addition to the public value 5 v = e (g,, S) or v = e (S, g), for example, the first parameter is equal to the first primitive g, the second parameter is equal to second primitive g2 and the third parameter v = e (g ,, g,) is equal to the image by the bilinear application e of the first and second primitives g, and g2, that is, the public key P may be of a quadruplet of the form (g1, g2, e (g1, g2), v = e (g ,, S)) or (g ,, g ,, e (g1, g2), v = e (S, g2)) Advantageously, the first g !, second g2, and third v = e (g g), public parameters are identical for any first entity El. Thus, the variables or parameters g,, g, and e ( g ,, g,) can be set "universally", i.e. they are set equal for all protocol actors and published as universal parameters of the protocol. In this case, the public key, specific to each entity, is then reduced to v = e (g, S ') or v = e (S, g). It will be noted that FIG. 1 is also an illustration of the main steps. the cryptographic method according to the invention for the authentication of the first entity El (entity to be verified) by the second entity E2 (audit entity). Indeed, in order to verify the authenticity of the first entity El, the second entity E2 sends (step N4) a challenge to the latter. Upon receiving this challenge, the first entity El calculates (step N5) a response that takes into account the challenge and the secret key S. In step N6, the first entity El sends this response to the second entity E2.

On receiving the response, the second entity E2 checks (step N7) this response using the challenge and the public key P. FIG. 2 illustrates a table detailing the characteristics of the protocol according to the authentication scheme of the present invention.

This table indicates that for the first entity E the number of NB evaluations of a bilinear application is equal to zero, the number of exponents NE by an exponent of the same size as that of the order of the primitive g is equal to three. In addition, this table indicates that for the second entity E2 the number of NB evaluations of a bilinear application 10 is equal to one, the number of exponences NE by an exponent of the same size as that of the order of g is equal to one. The table also indicates that the number of data transfer phases NP between the first entity El and the second entity E2 is equal to three. Thus, this table shows that the average number of operations for an iteration between the first entity El and the second entity E2 can be achieved with only a linear application evaluation, four exponentiations and three transfer phases, which represents a overall computation cost lower than the authentication schemes of the prior art (see FIG. 4). In particular, it will be noted that the overall number of exponentiations (which require a great deal of computing time) is small compared with this prior art. FIG. 3 is an example illustrating the main steps of the authentication of the first entity El by the second entity E2. In step N11, the first entity El chooses a first natural number r. This natural number r is advantageously chosen randomly from the integers strictly smaller than the first order q of the primitive g, or g, (that is to say 0 <r <q). The first entity El then calculates a first value W = e (g,, g2) equal to the image by the bilinear application e of the pair (g ,, g,) formed by the first and second primitives 2903258 13 brought to the power of the first natural number r. Advantageously, the first value W = e (g ,, g) can be precalculated. In step N12, the first entity El sends this first value W = e (g1, g2) to the second entity E2.

Then, in step N13, the second entity E2 chooses a second natural number c defining a challenge or a question (see step N3 of FIG. 1). This second natural number c can be chosen in an interval of integer [0,2k [where k is a value which depends on the public value v = e (g ,, S) or v = e (S, g,). It should be noted that the larger the k, the less likely it is that the cryptographic system will be "broken". In step N14, the second entity E2 sends this second natural number c to the first entity El. In step N15, after the reception of this second natural number c, the first entity El calculates a second value Y = g; S y Y = 15 defining the answer to the challenge (see step N5 of Figure 1). This second value is equal to the product between a first term g; or g; , and a second term S`. The first term g; or g; is equal to the primitive belonging to the same group as that of the secret key brought to the power of the first natural number r. The second term S` is equal to the secret key S brought to the power of the second natural number c. Advantageously, the first term g; or g; can be precalculated. In step N16, the first entity El sends this second value Y to the second entity E2. Finally, in step N17, the second entity checks whether the image 25 e (g ,, Y) or e (Y, g2) by the bilinear application e of the pair formed by the primitive belonging to the other of the first and second groups (G1, G2) and the second value Y is equal to the product Wvc between the first value 2903258 14 W and the public key v brought to the power of the second natural number c (i.e. (g ,, Y) = Wvc or respectively e (Y, g,) = Wvc). Thus, if the equality is verified, the authentication of the first entity El is validated. On the other hand, if the equality is not verified, the authentication is not validated. Note that the above steps can be repeated a predetermined number of times. Indeed, when the equality of step N17 is verified, the set of steps N11 to N17 is validated, and the first and second entities E1 and E2 start a new execution of these steps. It is also possible to execute these steps several times in parallel manner, simultaneously executing a set of these steps Nil to N17. In fact, in the parallel case, the set of values calculated during one of the parallel executions is not necessary for another of the parallel executions. In this case, all executions continue. Thus, steps N11 to N17 can be repeated a predetermined number of times in parallel or sequential manner. In both cases, the authentication is successful when the equality of the step N17 has been checked the specified number of times, without there having been an execution in which it has not been verified. This example shows that the secret key S can belong to the first group G, or to the second group G2. When choosing the secret key S in the second group G2, the public value v is equal to 25 e (g ,, S). On the other hand, when the secret key S is chosen in the first group G1, the public value v is equal to e (S, g2). It should be noted that the first and second groups (G 1, G 2) can be chosen equal or distinct.

Indeed, for choices of keys of standard size, it is easy to find a group such that, taking G, and G2 equal to the same group, the calculations are effective. In this case, it is advantageous to choose the first group G equal to the second group G2 (G1 = G2) and having a common primitive g. The primitives g, and g2 are then both equal to g. This reduces the number of data to be published. On the other hand, for high key choices, it is difficult in the current state of knowledge to find a group such that, taking GI and G2 equal to that same group, the calculations are effective. It is therefore in this case more advantageous to take two distinct groups. The invention also relates to a computer program downloadable from a communication network comprising code instructions for executing the steps of the cryptographic method according to the invention when it is executed on a computer, a microprocessor or an electronic chip. This computer program can be stored on a computer readable medium. This program can use any programming language, and be in the form of source code, object code, or intermediate code between source code and object code, such as in a partially compiled form, or in any another desirable form. The invention is also directed to a computer-readable information carrier having instructions of a computer program as mentioned above. The information carrier may be any object or device capable of storing the program. For example, the medium may comprise storage means, such as a ROM, for example a CD ROM or a microelectronic circuit ROM, or a magnetic recording medium, for example a diskette (floppy disc) or a hard disc. On the other hand, the information medium may be a transmissible medium such as an electrical or optical signal, which may be conveyed via an electric or optical cable, by radio or by other means. The program according to the invention can be downloaded in particular on an Internet type network. Alternatively, the information carrier may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the execution of the method in question. The invention also relates to an electronic chip card which can conventionally comprise a processing unit, a memory, an input unit and an output unit and adapted for implementing the cryptographic method according to the invention.

Claims (9)

  A public key cryptographic method for authenticating a first entity (El) having a secret key S associated with a public key P by a second entity (E2) having said public key P, said secret key S belonging to a first or second groups (G 1, G 2) respectively generated by first and second primitive g, and g 2 of prime order q, said method comprising the following steps: sending a challenge by the second entity (E 2) at the first entity (E1), - calculating by the first entity (E1) a response taking into account said challenge and said secret key s - sending by the first entity (E1) of said response to the second entity, and verification of the response by the second entity (E2) using said challenge and the public key P, said method being characterized in that said public key P comprises, on the one hand, a public value v = e ( g ,, S) or v = e (S, g,) equal to the image by an app bilinear equation e defined on said first and second groups (G 1, G 2) of a pair of elements formed by the secret key S and the primitive belonging to the other of the first and second groups (G 1, G 2) that the one to which the secret key S belongs, and on the other hand that primitive.   2. Method according to claim 1, characterized in that said public key P further comprises identical public parameters for any first entity, said public parameters comprising a first parameter equal to the first primitive g, a second parameter equal to the second primitive g , and a third parameter v = e (g ,, g) equal to the image by said bilinear application e of said first and second primitives g,, g2.   3. Method according to claim 1 or claim 2, characterized in that it comprises the following steps: -choice by the first entity (El) of a first natural number r, -send by the first entity (E1) at the second entity (E2) of a first value W = e (g1, g2) equal to the image by the bilinear application e of the pair (g, g2) formed by said first and second primitives brought to the 10 power of said first natural number r, -choice by the second entity (E2) of a second natural number c defining said challenge, -sending of said second natural number c to the first entity (El), -calculated by the first entity ( El) of a second value Y = g; S` or Y = g; S 'defining said response, said second value being equal to the product between a first term g2 or g; , and a second term S`, said first term g; or g; being equal to the primitive belonging to the same group as that of the secret key brought to the power of said first natural number r, and said second term S` being equal to the secret key S 20 brought to the power of said second natural number c, - sending from said second value Y to the second entity (E2), and - checking by the second entity (E2) if the image e (gi, Y) or e (Y, g2) by the bilinear application e of the pair formed by said primitive belonging to the other of the first and second groups (G1, G2) and said second value Y is equal to the product WV` between said first value W and said public key v brought to the power of said second natural number c. 2903258 19   4. Method according to claim 3, characterized in that said first value W = e (g,, g,) and / or said first term g, or g; are precalculated.   5. Method according to claim 3 or 4, characterized in that said five steps are repeated a predetermined number of times in parallel or sequential manner.   6. Process according to any one of claims 1 to 5, characterized in that the first and second groups (G 1, G 2) are equal and 10 have a common primitive g, the primitives g and g being then both equal to g.   7. Public key cryptosystem comprising a first entity having a secret key S associated with a public key P 1 a second entity having said public key P, said system being adapted for implementing the cryptographic method according to at least one Claims 1 to 6.   An electronic chip card adapted for carrying out the cryptographic method according to at least one of claims 1 to 6.   9. Computer program downloadable from a communication network and / or stored on a computer-readable medium and / or executable by an electronic chip, characterized in that it comprises code instructions for the execution of the steps of the cryptographic method according to at least one of claims 1 to 6, when executed on a computer or an electronic chip.