WO2008001009A1

WO2008001009A1 - Public-key cryptographic system and method for the authentication of a first entity by a second entity

Info

Publication number: WO2008001009A1
Application number: PCT/FR2007/051534
Authority: WO
Inventors: David Lefranc; Hervé SIBERT; Marc Girault
Original assignee: France Telecom
Priority date: 2006-06-30
Filing date: 2007-06-26
Publication date: 2008-01-03
Also published as: FR2903258A1

Abstract

The invention relates to a public-key cryptographic system and method for the authentication of a first entity (E1) possessing a secret key S associated with a public key P by a second entity (E2) possessing said public key P, said secret key S belonging to a first or to a second group (G1, G2) respectively generated by first and second primitives g1 and g

Description

Title of the invention

Public key cryptographic system and 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, storing it in the memory of the card, reading it at each transaction and verifying it by interrogating a network application capable of implementing the transaction, where the authentication values already allocated 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 list of arguments determined at each authentication; the argument list may comprise a hazard (the hazard being a data item 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 chip is identical to the authentication value calculated by the application, the chip is deemed authentic and the transaction between the 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 a public transit gate, know the secret key held by said chip. It follows from a major drawback that, if it is desired that said device can authenticate any chip issued in connection with the application, either 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 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 in performing simultaneously two conventional authentication methods where the chip and the application interchange roles in both protocols.

The best-known solutions for performing such authentication mechanisms are generally based on difficult mathematical problems such as factorization or discrete logarithm; these two problems generate in their realization calculations of modular exponentiations, ie calculations of the type x ^e modn where

"mod" is 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. That is why it is essential to go 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. For example, consider an application / defined on the set G ₁ XG ₂ in G where G ^ G ₂ and G are groups (mathematical notion). Suppose ^ ₁ and g ₂ of the (or primitive) generators respectively of G ₁ and G ₂ , the function / is called bilinear of G ₁ XG ₂

The current problem with these bilinear applications is that their evaluations generate enormous calculations, much more complex than the calculation of a (simple) modular exponentiation. Hence the difficulty in a classic setting, to make such calculations. In addition, existing solutions seem very inefficient to use 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 I mproved Identification Scheme," Progress in Computer Science and Applied Logic, Berkhauser-Verlag, November 2003. The second protocol is described in the paper 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, ACI SP '02, pp. 362-378, Springer - Verlag, 2002.

Figure 4 shows a table detailing the characteristics of the protocol of Wang and Wang (referenced M1) and that of Kim and Kim (referenced M2).

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) of 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 NB For a bilinear application, the fourth column indicates the number of exponents NE by an exponent of the same size as that of the order of g and the fifth column indicates the number of NP phases 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 objective and to facilitate the comparison between the different methods. 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 secret key S belonging to a first or to a second group (G ^ G ₂ ) respectively generated by first and second primitive primitive primitive primitives g ₁ and g ₂ , 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 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 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 that to which the secret key S, 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 furthermore comprises identical public parameters for any first entity, said public parameters comprising a first parameter equal to the first primitive ^ ₁ , 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 ^ ₁ and g ₂ . 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,

sending by the first entity to the second entity a first value W = e (g _ι , g ₂ ) ^r equal to the image by the bilinear application e of the pair (^ ₁ , g ₂ ) formed by said first and second primitives brought to the power of said first natural number r, -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 ₂ ^r S ^c where Y = g [S ^c defining said response, said second value being equal to the product between a first term g \ or g [, and a second term S ^c , 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 ^c being equal to the secret key S brought to the power of said second natural number c, sending said second value F to the second entity, and verifying by the second entity if the image e (g _ι , Y) or e (γ, g ₂ ) by the bilinear application e of the pair formed by said primitive belonging to the other of the first and second groups (G ^ G ₂ ) and said second value Y is equal to the product Wv ^c 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 lower overall computational cost. current authentication schemes.

Advantageously, said first value W ^ e (g _ι, g ₂₎ ^r and / or said first term g ₂ or g [are precalculated.

This makes the online execution of the protocol faster, since the first values have already been calculated offline.

According to one particularity 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 ₂ ) are equal and comprise a common primitive, the primitives ₁ and g ₂ being then 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 the implementation of the method cryptographic device according to at least one of the above features. This first entity may, for example, advantageously be constituted by an electronic chip, and this second entity may then be constituted by an application or a verification device responsible for authenticating the electronic chip.

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 at least one of the above features, when run on a computer or microchip.

Brief description of the drawings

Other features and advantages of the invention will appear on reading the description given below, by way of indication but not limitation, with reference to the accompanying drawings, in which:

FIG 1 schematically illustrates a public key cryptographic system 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, FIG. 1 schematically illustrates a public key cryptosystem comprising a first entity E1 and a second entity E2.

The first entity E1 and the second entity E2 may be interconnected via a communication line 3 by contact or remotely or via a communication network.

The first entity E1 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, in charge of the authentication of the first entity E1, such as those present in a public telephone, an electronic payment terminal or a transit gate.

The first entity E1 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 or a second group (G ^ G ₂ ) respectively generated by first and second generators or primitives ^ ₁ and g ₂ of order q, where q is a prime number preferably large (by example q> ^2,160 ). Indeed, we assume the existence of a bilinear mapping e defined on G ₁ XG ₂ and with a value in a third group G, so that the groups G ₁ and G ₂ are respectively generated by the elements ^ ₁ and g ₂ of order q (i.e., e (g ", g ₂ ) = e (g ₁ , g ₂ ) ^ab 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 (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 that to which the secret key S (that is to say, v = e (g _1, S) or v = e (S, g ₂₎ and secondly, this primitive (that is to say ₁ or g ^ ₂ respectively).

More particularly, the public key may correspond to a quadruplet comprising three parameters in addition to the public value _{w = e} {g _ι , S) or v = e (S, ^ ₁ ). For example, the first parameter is equal to the first primitive ^ _1, the second parameter is equal to the second primitive g ₂ and the third parameter v = e (g _ι, g ₂₎ are \ equal to the image by bilinear application e of the first and second primitives ^ ₁ and g ₂ . In other words, the public key P can be constituted by a quadruplet of the form (^ _1, g _2, g e _{I, G _2), v = e (g _ι, S)) or (g _1, g ₂ , e (g ₁ , g ₂ ), v = e (S, g ₂ ))

Advantageously, the first ^ ₁ , second g ₂ , and third v = e (g _{ , g ₂ ) public parameters are identical for any first entity E1.

Thus, the variables or parameters ^ ₁ , g ₂ and eig ^ 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 = ^ g ₁₅ S) or v = e (S, g ₂ )

It will be noted that FIG. 1 is also an illustration of the main steps of the cryptographic method according to the invention for the authentication of the first entity E1 (entity to be verified) by the second entity E2 (audit entity).

Indeed, in order to verify the authenticity of the first entity E1, the second entity E2 sends (step N4) a challenge to the latter. Upon receiving this challenge, the first entity E1 calculates (step N5) a response that takes into account the challenge and the secret key S.

In step N6, the first entity E1 sends this response to the second entity E2. On receiving the response, the second entity EΞ2 checks (step N7) this response using the challenge and the public key P.

Figure 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 E1 the number of NB evaluations of a bilinear application is equal to "zero", the number of exponentiations NE by an exponent of the same size as that of the order of the primitive g is equal at three ". In addition, this table indicates that for the second entity E2 the number of NB evaluations of a bilinear application 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 E1 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 E1 and the second entity E2 can be achieved with only a linear application evaluation, four exponentiations and three transfer phases, which represents a cost overall calculation less 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 E1 by the second entity E2.

In step N1 1, the first entity E1 chooses a first natural number r. This natural number is advantageously chosen randomly from the integers strictly smaller than the first order q of the primitive ^ ₁ or g ₂ (that is to say 0 <r <q). The first entity E1 then calculates a first value W = e {g _x , g ₂ ) equal to the image by the bilinear application e of the pair (g _ι , g ₂ ) formed by the first and second primitives 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 E1 sends this first value W = Kg ₁₅ ^ ₂ ) to the second entity EΞ2. Then, in step N13, the second entity EΞ2 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 [θ, 2 * [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 is "broken".

In step N14, the second entity E2 sends this second natural number c to the first entity E1.

In step N15, after the reception of this second natural number c, the first entity E1 calculates a second value Y = g ₂ ^r S ^c where Y = g [S ^c defining the response to the challenge (see step N5 of FIG. 1). This second value is equal to the product between a first term g ₂ ^r or g [, and a second term S ^c . The first term g ₂ ^r 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 ^c is equal to the secret key S brought to the power of the second natural number c. Advantageously, the first term g ₂ or g [may be precalculated.

In step N16, the first entity E1 sends this second value F to the second entity E2.

Finally, in step N17, the second entity checks whether the image e {g _x , Y) or e (Y, g ₂ ) by the bilinear application e of the pair formed by the primitive belonging to the other of the first and second groups (G ₁ , G ₂ ) and the second value Y is equal to the product Wv ^c between the first value W and the public key v brought to the power of the second natural number c (that is, e {g _x , Y) = Wv ^c or respectively e (Y, g ₂ ) = Wv ^c ).

Thus, if the equality is verified, the authentication of the first entity E1 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 the step N17 is verified, the set of steps N11 to N17 is validated, and the first and second entities E1 and E2 begin a new execution of these steps.

It is also possible to execute these steps several times in parallel, simultaneously executing a set of these steps N11 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 determined number of times, without there being 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 the second group G ₂ . When the secret key S is chosen in the second group G ₂ , the public value v is equal to e {g _x , S). On the other hand, when the secret key S is chosen in the first group G ₁ , the public value v is equal to e (S, g ₂ ).

It should be noted that the first and second groups (G ₁ , G ₂ ) 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 G ₂ equal to this same group, the calculations are effective. In this case, it is advantageous to choose the first group G ₁ equal to the second group G ₂ (G ₁ = G ₂ ) and having a common primitive g. The primitives ^ ₁ and g ₂ are then both equal to g. This reduces the number of data to be published.

On the other hand, for choices of keys of high size, it is difficult in the current state of knowledge to find a group such that, taking Gl and Gl equal to this 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 other form desirable shape.

The invention also relates to a computer-readable information medium, comprising 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 means magnetic recording, for example a floppy disk or a hard disk.

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 electrical or optical cable, by radio or by other means. The program according to the invention can in particular be downloaded to a network of the Internet type.

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 that 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

REVENDI CATI ONS

A public key cryptographic 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 second groups (G ₁ , G ₂ ) respectively generated by first and second primitives ^ ₁ and g ₂ of first order q, said method comprising the following steps: - sending a challenge by the second entity ( E2) to the first entity (E1),

calculation 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 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 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 that to which the secret key S belongs, and on the other hand, this 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 ^ ₁ , 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 ₂ .

3. Method according to claim 1 or claim 2, characterized in that it comprises the following steps:

by the first entity (E1) of a first natural number r,

sending by the first entity (E1) to the second entity (E2) 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,

by the second entity (E2) of a second natural number c defining said challenge,

sending said second natural number c to the first entity (E1),

calculating by the first entity (E1) a second value Y = g ₂ ^r S ^c where Y = g [S ^c defining said response, said second value being equal to the product between a first term g ₂ ^r or ^ ₁ " , and a second term S ^c , said first term g ₂ ^r 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 ^c being equal to the secret key S brought to the power of said second natural number c,

sending said second value F to the second entity (E2), and verifying by the second entity (E2) if the image e {g _ι , Y) or e (Y, g ₂ ) by the bilinear application e the pair formed by said primitive belonging to the other of the first and second groups (G ₁ , G ₂ ) and said second value Y is equal to the product Wv ^c between said first value W and said public key v brought to the power of said second natural number c.

4. Method according to claim 3, characterized in that said first value W = Kg ₁₅ ^ ₂ ) and / or said first term g ₂ ^r or g [are precalculated.

5. Method according to claim 3 or 4, characterized in that said steps are repeated a predetermined number of times in parallel or sequential manner.

6. Method according to any one of claims 1 to 5, characterized in that the first and second groups (G ₁ , G ₂ ) are equal and comprise a common primitive g, primitives ^ ₁ and g ₂ then being both equal to g.

7. Public key cryptosystem comprising a first entity (E1) having a secret key S associated with a public key P and a second entity (EΞ2) having said public key P, said system being adapted for the implementation of the cryptographic method according to at least one of claims 1 to 6.

8. Cryptographic system according to claim 7, characterized in that said first entity (E1) is constituted by an electronic chip and said second entity (E2) is constituted by an application or a verification device responsible for authenticating said electronic chip.

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 executing 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.