WO2014125206A1

WO2014125206A1 - Cryptographic method for generating a pair of user keys for an entity having a public identifier i, and system

Info

Publication number: WO2014125206A1
Application number: PCT/FR2014/050262
Authority: WO
Inventors: Sébastien CANARD; Matthew Robshaw
Original assignee: Orange
Priority date: 2013-02-15
Filing date: 2014-02-11
Publication date: 2014-08-21
Also published as: FR3002350A1

Abstract

The invention relates to a cryptographic method for generating a pair of user keys for an entity having a public identifier /, and a system. The method according to the invention comprises: the generation (G10), by a certification authority, of either a master public key comprising an RSA modulus n which is the product of two first numbers p and q, a whole number b higher than or equal to 1, two quadratic residues a and g modulus n and a value h determined from a variate z, or a master secret key comprising p and q; the generation (G20), by said entity, of a user secret key s; the evaluation (G30), by the entity, of a value v = g~s (mod n); the transmission (G40) of v to the authority with proof of knowledge of s; the generation (G50), by the authority, of a certificate {A, e) wherein e is a variate associated with / and A ^eb = f (h ⁱ , v, n), f being a pre-determined function; the transmission (G60) of (A, e) to the entity; and the production (G80) of a pair of user keys for the entity, comprising s, and a user public key formed from A, e and I.

Description

Cryptographic method for generating a user key pair for an entity having a public identifier /, and system Background of the invention

The invention relates to the field of securing data and exchanges between different entities using public key cryptographic techniques.

It relates more particularly to the certification of a public key of a device having an identifier in order to improve the security of a mechanism for authenticating this device or for digitally signing a message by this device based on a diagram of the GPS type or "cryptoGPS" (named after its inventors Girault, Poupard and Stern).

The GPS scheme is described in detail in the document entitled "On the Fly Authentication and Signature Schemes based on Groups of Unknown Order", Journal of Cryptology, pages 463-488, vol. 19 n ° 4, 2006. This is a protocol with zero knowledge disclosure (or "zero knowledge" in English), offering a secure solution at low cost, in terms of computing power and / or memory. storage.

Thus, the GPS scheme has a preferred application in the field of radio-identification or RFID (for Radio Frequency IDentification).

In a known manner, radio-identification is a technique used to store and retrieve data remotely using markers called radio-tags or radio tags or RFID tags. It is commonly used in many sectors of activity such as the pharmaceutical industry, distribution, fashion or libraries, for the traceability of various objects.

Due to its low complexity, the GPS scheme can be easily embedded in radio-identification systems. It makes it possible for a first device that is not very powerful in terms of computing power and memory, such as an RFID tag, to authenticate and authenticate itself securely with a second, more powerful device, such as a reader. RFID tags. The GPS protocol is advantageously such that the cost of authentication for the first least powerful device can be reduced substantially by means of a series of optimizations.

There is in particular a so-called "coupons" mode, which consists in calculating during a preliminary step all the values that can be and storing these precalculated values (i.e. the coupons) on the RFID tag. This leaves the RFID tag with only a minimum of operations to perform during the actual authentication session.

An example of implementation of a GPS authentication scheme of a first device E1 with a second device E2 is illustrated in FIG. 1. E1 is for example an RFID tag and E2 is an RFID tag reader.

It is conventionally composed of two phases, namely a first phase PI configuration during which authentication data (parameters, public / private key and where appropriate coupons) are calculated and / or provided to the first device El, then a second authentication phase P2 during which the first device El authenticates with the second device E2 using these data of authentication. The PI phase is a preliminary phase that can be executed only once in the life of the authentication system, unlike the P2 phase which is implemented at each authentication of the device El.

During the PI configuration phase, a public key v / private key pair was generated. In the example illustrated in FIG. 1, the keys s and v are linked by the following relation:

v = g ^{~ s} modn

where n = pq is a module called RSA (Rivest Shamir Adleman) resulting from the product of two prime numbers p and q, g is an element of the multiplicative group Z ^* = (Ζ / ηΖ) \ {θ}, Z denoting the set relative integers. The parameters n, g, and the key v are public, that is, they are accessible by the device E2. On the other hand, the private key remains secret and is specific to the device El. It is stored on the device El and is never transmitted to the outside.

The P2 authentication phase is carried out in three main steps.

The device El randomly chooses an integer r and then evaluates a commitment x = g ^r modn (step E10) which it transmits to the device E2 (step E20).

In the so-called coupon mode, a plurality of commitment values or coupons x are similarly precalculated _; , \ ≤i≤N using random r _; , \ ≤i≤N, during the configuration phase Pl. These coupons are then stored on the device El in order to limit the calculations made by the device El during the authentication phase P2.

On receipt of this commitment, the device E2 randomly chooses a challenge c (step E30), which it transmits to the device El (step E40).

The device El evaluates a response to this challenge y = r + cxs (step E50), which it sends to the device E2 for verification (step E60). This check consists for the device E2 to ensure that x = g ^y v ^c modn (step E70). If necessary, the device El is validly authenticated.

The GPS scheme can also be used by an El device to digitally sign a message m.

In this case, the challenge c is generated by the device E1 not randomly but by applying a hash function h to a vector resulting from the concatenation of the message m and the commitment x. The digital signature associated with the message m is then formed by the pair (c, y).

Upon receipt of the message m and its signature (c, y), the device E2 verifies that the signature is valid by calculating the value x '= g ^y / v ^c ) modn and the value c' = i (m, ') then making sure that c = c '. To enhance the security of the GPS scheme, the use of a public key infrastructure (PKI) is required to establish a link between the public key that is used during authentication or signing, and the public key infrastructure. However, such an infrastructure is relatively complex to implement and manage.

One solution to overcome this disadvantage is to use an authentication or signature mechanism based on the GPS scheme and based on the identity of the device that seeks to authenticate or to sign a message.

For example, the public key of the device El can be replaced by its identity (for example its code EPC (Electronic Product Code) for an RFID tag). Thus, the link between the device and its public key is direct.

However with such a solution, when the secret key of the device is compromised, for example because the device on which it is stored is lost, the identity of the device is also compromised. But it is not always possible to obtain another pair of keys for the same identity.

An alternative solution, still based on the identity of the El device that seeks to authenticate itself or to sign a message, is proposed by Marc Girault in the document entitled "Self-certified public keys", Eurocrypt'91, vol. 547, Lecture Notes in Computer Science, pp. 490-497, Springer, 1991.

According to this solution, a certification authority CA signs the identity I of the device El by generating a certificate, while respecting the constraints of the GPS scheme (non-disclosure of the secret key s of the device El, and in particular to the authority of certification). Then the device El uses a public user key formed by the certificate and its identity to authenticate with an E2 device using a GPS authentication scheme.

An example of implementation of this solution is illustrated in Figure 2.

At first (step F10), a so-called "master" key pair is generated for the CA from:

an RSA module n = pq defined as the product of two prime numbers p and q;

an integer e prime with (p-1) and (q-1) and an integer d = e ^{~ 1} (mod (p - ï) (q - ï));

and an element ^ of the multiplicative group Z ^* = (Z InZ) \ {0}, where Z denotes the set of relative integers.

The master key pair of the CA includes MasterPubK master public key and MasterSecK master private key defined by:

MasterPubK = (n, e, g)

MasterSecK = (p, q, d)

At the device El, during a configuration step, a secret key s of the device El is generated randomly (step F20). Then the device El generates the value v = g ^s moan (step F30) and sends it to the CA with its identity / and a proof of knowledge of the secret key s to zero disclosure of knowledge (step F40) . This proof is provided via the implementation of a GPS scheme.

After verifying the knowledge of the secret key s by the device El, the CA CA calculates a certificate A (step F50) according to:

then transmits it to the device El (step F60).

Upon receipt of the certificate A, the device El verifies that (step F70):

v = A ^e + I (modw).

In this case, the device El has a pair of user keys comprising a user public key UPubK = (A, I) and a user secret key USecK = s (step F80).

The authentication of the device El with a device E2 is then carried out using a GPS authentication mechanism as described above with reference to FIG. 1, applied to the secret user key s of the device E1, the element g and a public key v = A ^e + 1 generated by the device E2 from the public key UPubK = (A, I) of the device El (step F90).

The advantage of such a solution is that it makes it possible to certify the identity / device El without using a PKI public key infrastructure and while remaining compatible with the implementation of an authentication scheme or GPS signature.

However, according to this solution, it is easy for an adversary to obtain a valid user key pair, without the intervention of the certification authority. In fact, the adversary can randomly choose a secret key s ^* , a value A ^* and then calculate an identity

I ^* = g ^{~ *} + A ^{* e} (modn). Although in practice, the probability of operation of such an attack is very low, the opponent can not control the value of the identity f, this attack is still possible.

There is therefore a need for a mechanism for generating a public key certified based on the identity of a device and compatible with an authentication scheme or GPS signature, not having the disadvantages of the prior art in terms of security and without resorting to a PKI infrastructure.

Object and summary of the invention

The invention responds in particular to this need by proposing a cryptographic method for generating a user key pair for an entity having a public identifier /, this method comprising: A step of generating, by a certification authority, a pair of master keys comprising:

a master public key, comprising an RSA n module, produces two prime numbers p and q, an integer b greater than or equal to 1, two quadratic residues a and g modulo n, and a value h determined from a random z;

a secret master key comprising the prime numbers p and q;

A step of generation by the entity of a secret user key from a random;

An evaluation step by the entity, from the secret user key and the master public key, of a value v = g ^{~ s} (mod);

A step of sending by the entity of this value v to the certification authority with a proof of knowledge of the secret user key according to a protocol with null disclosure of knowledge;

A step of generation by the certification authority, based on the public identifier / entity and the value v, of a certificate consisting of a pair of values {A, e) in which e is a hazard associated with the public identifier / and:

A ^e "= f {h, v, n),

where f is a predetermined function; and

A step of sending the certificate (A, e) to the entity by the certification authority;

these steps resulting in obtaining a user key pair for the entity comprising the user secret key s and a user public key formed from the values A and e and the identifier / entity.

Thus, according to the invention, and as in the diagram proposed by M. Girault, the relationship between the public identity of the entity and its public key is established by a certification authority via the generation of a certificate allowing the signing of the certificate. public identity of the entity, so that the public user key of the entity consists of its public identity and the certificate thus generated by the certification authority.

The secret key of the entity is also never disclosed, including to the certification authority, since only a proof of knowledge of the secret key to zero knowledge disclosure is provided to it, without ever disclosing the secret key. The zero-knowledge protocol used by the entity relies for example on a GPS type authentication scheme.

However, according to the invention, on the one hand, the hazard e used in the certificate is specific to each public identifier /, and on the other hand, the relationship linking the certificate, the secret key and the public identity is now tamper-proof due in particular to the presence by exposing the identity of the entity in the certificate generated by the certification authority. The function f makes it possible to make sure that no entity, without knowing the factorization of the module RSA n, can not find a couple of values (A, e) which will verify the relation A ^eb = f (h ', v, n). Only the certification authority can generate such a pair of values.

To better illustrate the advantages of the invention and in particular this unfalsifiable character, we will consider several examples of functions f that can be used by the certification authority to generate the certificate (A, e).

In a first embodiment of the invention:

h = g ^{~ z} (mod ri),

and the certificate (A, e) generated by the certification authority verifies:

A = (ah'v ^ mod ri),

with d = (mod (p-1) (q> - 1)) and b greater than 1.

Moreover, to enhance the security of the schema thus proposed, the generation method may furthermore comprise a verification step by the entity that: v = - - (mod n).

ah ^{1 J}

In this first embodiment, an adversary can certainly randomly choose a secret key s ^* , a value A ^* and then calculate, from the master public key, the value h = a A ^e g ^s (modw). However, from this value, it can not generate a public identity /, because of the complexity of the discrete logarithmic problem to be solved. The use of an RSA module to generate the master public key of the certification authority also reinforces this complexity.

The user key pair generated according to the invention is therefore unfalsifiable, the adversary being unable to generate a valid user key pair from the information published by the certification authority and by the entity.

The proof of the level of security attained by this first embodiment of the invention (in other words the tamper-proof nature of the user key pair generated) can be provided by relying on a demonstration similar to that conducted by Mr. Joye in the document entitled "An efficient on-line / off-line signature scheme without random oracles", CANS'08, vol. 5339 of Lecture Notes in Computer Science, pages 98-107, Springer, 2008. This document proposes indeed a method of signature of a message, presented as an alternative to the GPS signature scheme but which contrary to the GPS scheme, does not exist. not rely on a random oracle model. According to this method, the message is signed using a signature verifying a relationship analogous to that linking the public / entity identity, the certificate (A, e) generated by the certification authority and the element g issued by the certification authority according to the invention.

The inventors had the judicious idea to transpose the signature scheme of a message described in the document of Mr. Joye to the problem of the certification of the identity of the entity embedded in an identity-based GPS mechanism, to generate a pair of user keys compatible with a GPS authentication or signature mechanism of a message. In this way, the invention can easily be part of a low-cost cryptography logic allowing the entity to authenticate itself or to sign a message according to a GPS mechanism.

It suffices for this purpose that the verifier device in charge of authenticating the entity possessing a user key pair generated according to the invention or of verifying the signature of a message produced by such an entity, applies an authentication mechanism or type of GPS signature as described above with reference to Figure 1 based:

- on the user's private key of the entity,

- on the element published by the certification authority, and

On a public key v generated by the verifier device from the public user key of the entity according to:

A ^e "

v = - (mod n).

(ah)

The invention therefore provides a secure solution to the certification of the identity of the entity as part of a GPS authentication or signature mechanism.

It should be noted that the method of generating a user key pair proposed by the invention also makes it possible to envisage dimensions for the user secret key, the random variables, the RSA module, etc., which are reasonable, with a choice of appropriate function f, so that the complexity of embodiment of the invention remains limited and is compatible with low cost cryptography logic. This is particularly the case when the pair (A e) generated by the certification authority verifies:

A = (ah ^l v) ^d (mod n),

with d = {mod (p-1) (q> - 1)) and b greater than 1.

The dimensions of these parameters depend, of course, on a security / complexity compromise.

However, preferentially, a small value is chosen for the integer b, such as, for example, b = 4, an identifier of the entity of dimension greater than or equal to 160 bits, and a user secret key s comprising at least 400 bits.

The invention is not limited to the aforementioned function f.

Thus, in another embodiment of the invention, the certificate (A, e) generated by the certification authority verifies:

A ^e = ah ^l v (mod)

(Le., B = 1 in this embodiment).

The verifier device responsible for authenticating the entity having a user key pair generated according to this embodiment of the invention or verifying the signature of a message produced by such an entity, applies a GPS authentication or signature mechanism based on the entity's private user key, on the g element issued by the certification authority, and on a public key v generated by the verifier device from the public user key of the entity according to:

A ^e

v = - (mod n).

(ah ¹ )

This solution, although very advantageous in terms of security, however, requires parameter sizes, including secret key, more important.

In yet another embodiment, the certificate (A, e) generated by the certification authority verifies:

A ^e = h ^I + v (mod ri).

The verifier device in charge of authenticating the entity having a user key pair generated according to this embodiment of the invention, or of verifying the signature of a message produced by such an entity, applies an authentication mechanism or type of GPS signature based on the user's private key of the entity, on the element g published by the certification authority, and on a public key v generated by the verifier device from the public key user of the entity according to:

v = A ^e - h ¹ (mod n).

These examples are of course not exhaustive. Other functions that provide advantages similar to those described above and which make it possible to generate a pair of user keys compatible with an authentication or GPS signature scheme can be envisaged.

As a corollary, in another aspect, the invention provides a method of authenticating an entity having a public identifier / with a verifier device, by using a user key pair generated in accordance with the generation method according to the invention. , the authentication of the entity being performed using a GPS type authentication scheme implemented between the entity and the verifier device.

This method has both the advantages of the generation method according to the invention and the advantages of a GPS authentication method, recalled above, in terms of complexity (computing power and / or storage memory).

Such a method, because of its low complexity, can be easily implemented between an RFID tag and an RFID tag reader.

According to another aspect, another aspect of the invention is a method of signing a message by an entity having a public identifier / using a pair of user keys generated in accordance with the generation method according to the invention, the signature of the message being carried out at using a GPS type signature scheme. This method also benefits both the advantages of the generation method according to the invention and the advantages of a GPS signature method, mentioned above.

The invention relies, as mentioned above, firstly on an entity having a public identifier and seeking to authenticate or to sign a message according to a GPS mechanism based on the identity, and secondly on a certification authority, able to establish a relationship between the public identifier of the entity and its public key.

Thus, the invention also relates to a method for obtaining by an entity having a public identifier / of a pair of user keys comprising a user public key and a user private key, this method comprising:

A step of generating the secret user key from a random;

An evaluation step from:

o this secret user key; and

o of a public key master of a certification authority comprising an RSA n module, product of two prime numbers p and q, an integer b greater than or equal to 1, two quadratic residues a and g modulo n, and a value h determined from a randomness z, of a value v = g ^{~ s} (mod n);

A step of sending the value v to the certification authority with a proof of knowledge of the secret user key according to a protocol with null disclosure of knowledge;

A step of receiving the certification authority of a certificate consisting of a pair of values (A, e), in which e is a random associated with the public identifier /, and:

A ^e "= f {h, v, n),

where / is a predetermined function; and

A step of obtaining the public user key from the values A and e and the identifier / entity.

Correlatively, the invention relates to an entity having a public identifier / comprising:

A module for generating a secret user key from a random;

- an evaluation module, able to evaluate from:

o this secret user key; and

o of a public key master of a certification authority comprising an RSA n module, product of two prime numbers p and q, an integer b greater than or equal to 1, two quadratic residues a and g modulo n, and a value h determined from a randomness z, a value v = g ^{~ s} (mod n);

A module for sending the value v to the certification authority with a proof of knowledge of the secret user key according to a protocol with null disclosure of knowledge;

A reception module from the certification authority, a certificate consisting of a pair of values (A, e) in which e is a hazard associated with the public identifier / and: A ^e "= f {h, v, n),

where / is a predetermined function; and

A module for obtaining a public user key from the values A and e and the identifier /.

The invention also relates to a method of sending by a certificate authority a certificate to an entity having a public identifier / for forming a user public key for this entity, this method comprising:

A step of generating a pair of master keys comprising:

a secret master key comprising the prime numbers p and q;

A step of receiving from the entity a value v = g ^{~ s} (mod) generated by the entity using its user private key s, and a proof of knowledge of the secret key user according to a protocol with zero disclosure of knowledge;

A step of generating, from the public identifier / entity and the value v, a certificate formed of a pair of values (A, e) in which e is a random associated with the public identifier /, and:

A ^e "= f {h, v, n),

where / is a predetermined function; and

A step of sending the certificate (A, e) to the entity.

Correlatively, the invention provides a certification authority comprising:

A module for generating a pair of master keys comprising:

a secret master key comprising the prime numbers p and q;

A receiving module from the entity of a value v = g ^{~ s} (mod n) generated by the entity using its user private key s, and a proof of knowledge of the key secret user according to a protocol with zero disclosure of knowledge;

A module for verifying said proof of knowledge;

A generation module, from the public identifier / entity and the value v, of a pair of (A, e) in which e is a random associated with the public identifier /, and:

A ^eb = f {h, v, n),

where / is a predetermined function; and

A module for sending the pair (A, e) to the entity. The obtaining method, the sending method, the entity and the certification authority benefit from the same advantages as mentioned above for the method of generating a user key pair.

In a particular embodiment, the various steps of the obtaining method and the sending method are implemented by a silicon chip which comprises transistors adapted to constitute logic gates of a non-programmable hardwired logic. This embodiment is particularly advantageous in the context of RFID tags.

In another particular embodiment, the various steps of the method of obtaining and the method of sending are determined by computer program instructions.

Consequently, the invention also relates to a computer program on an information medium, this program being capable of being implemented in an entity or more generally in a computer, this program comprising instructions adapted to the implementation of steps of a production process as described above.

The invention also relates to a computer program on an information medium, this program being capable of being implemented in a certification authority or more generally in a computer, this program comprising instructions adapted to the implementation steps of a sending method as described above.

Each of these programs 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 form what other form is desirable.

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 entity 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 floppy disk or a disk. hard.

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

According to another aspect, the invention also provides a system comprising:

An entity having a public identifier / according to the invention; and

A certification authority according to the invention; In a particular embodiment, this system further comprises a verifier device, able to authenticate the entity by applying a GPS authentication scheme or to check the validity of a signature of a message generated by the entity by applying a GPS signature scheme.

It can also be envisaged, in other embodiments, that the generation method, the sending method, the method of production, the system, the entity and the certification authority according to the invention present in combination all or some of the aforementioned features. Brief description of the drawings

Other features and advantages of the present invention will emerge from the description given below, with reference to the drawings and the appendix which illustrate embodiments having no limiting character. In the figures:

FIG. 1, already described, schematically represents a GPS authentication scheme of the state of the art;

FIG. 2, already described, schematically represents a GPS authentication scheme based on the identity proposed in the state of the art;

- Figure 3 schematically shows a system according to the invention comprising an entity and a certification authority according to the invention in a particular embodiment;

FIG. 4 illustrates the main steps of a generation method, a sending method and a method of obtaining according to the invention as they are implemented in a particular embodiment respectively by the system, the certification authority and the entity of Figure 3; and

FIG. 5 illustrates an application of the user key pair generated according to the invention to a GPS authentication mechanism of the entity of FIG. 3 with a verifier device.

Appendix 1 recalls the recommendations concerning cryptographic parameter dimensions of the ECRYPTII instance.

Detailed description of the invention

As mentioned above, the invention proposes a secure mechanism based on the generation, by a certification authority, of a public key (A, e, l) certified for an entity and based on its identity / (or identifier public), this public key being advantageously unfalsifiable and compatible with an authentication scheme or GPS signature. More specifically, in accordance with the invention, the certification authority generates, for the public / entity identifier, a certificate consisting of a pair of values (A, e) where e is a hazard specific to the public / entity identifier and A is in the form:

A ^eb = f (h, v, n),

where / is a predetermined function, n is an RSA module, b is an integer greater than or equal to 1, v is a value generated by the entity using its private key s and transmitted to the certification authority, and h is a value determined by the certification authority from a randomly kept secret by the certification authority.

The function / is such that no entity, without knowing the factorization of the RSA n module, can find a pair of values (A, e) satisfying the relation A ^gb = f (h ', v, n). Only the certification authority can advantageously generate such a pair of values, so that the public key (A, e, l) generated according to the invention is tamper-proof. Various examples of functions / are proposed in the remainder of the description for illustrative purposes.

FIG. 3 represents, in its environment, a system 1 according to the invention, in a particular embodiment.

This system 1 comprises an entity 2, a certification authority 3 and a verifier device 4, in accordance with the invention. In the example envisaged here, the entity 2 is an RFID tag seeking to authenticate itself to the verifier device 4, using a GPS authentication scheme based on the identity as presented above. The verifier device 4 is here an RFID tag reader.

However, no limitation is attached to the nature of the entity 2 and the verifier device 4. The invention applies to other types of systems in which an authentication mechanism between two devices or a mechanism of Signing a message can be implemented. Thus, for example, the entity 2 may be a terminal and the verifier device 4 a server from which the entity 2 seeks to authenticate.

Moreover, although the invention has a privileged application in association with a GPS-type authentication or signature mechanism, the invention can be used in association with other asymmetric cryptographic mechanisms using a certificate of an authority certification.

Entity 2 has an identifier /, such as for example an electronic product code or EPC (Electronic Product Code). This identifier is public, that is to say accessible by or known to other entities, such as, for example, the certification authority 3 or by the verifier device 4. The identifier / is, in the example envisaged here , an integer of 160 bits.

In the embodiment described here, the entity 2 integrates a silicon chip 2A and communication means 2B with the certification authority 3 and the verifier device 4. The silicon chip 2A comprises transistors adapted to constitute gates logical of a non-programmable hardwired logic for executing the steps of the method for obtaining a user key pair described later with reference to FIG.

In another embodiment of the invention, the entity 2 has the hardware architecture of a computer, and comprises in particular a processor, a read-only memory, a random access memory, a non-volatile memory and communication means with a computer. The certification authority 3 and the verifier device 4. The read-only memory of the entity 2 constitutes a recording medium in accordance with the invention, readable by the processor and on which is recorded a computer program according to the invention. , comprising instructions for performing the steps of the method of obtaining a pair of user keys. This computer program defines, in an equivalent way, functional modules of the entity 2 able to implement the steps of the obtaining method. The certification authority 3 has, in the embodiment described here, the hardware architecture of a computer.

It comprises in particular a processor 3A, a read-only memory 3B, a random access memory 3C, a non-volatile memory 3D and communication means 3E with the entity 2.

The ROM 3B of the certification authority is a recording medium according to the invention, readable by the processor 3A and on which is recorded a computer program according to the invention, including instructions for execution steps of a method of sending a certificate according to the invention described now with reference to Figure 4, in a particular embodiment. This computer program defines, in an equivalent manner, functional modules of the certification authority capable of implementing the steps of the obtaining method.

We will now describe, with reference to FIG. 4, the main steps of a method for generating a user key pair intended for the entity 2, as implemented by the system 1 in a mode particular embodiment. This generation process is based on the method of sending a certificate associated with the public identifier / of the entity 2 implemented by the certification authority 3, and on the method of obtaining a user key pair by entity 2 from this certificate.

According to the invention, the certification authority 3 generates a pair of master keys comprising a master public key mpk and a master secret key msk (step G10).

For this purpose, the certification authority 3 determines an RSA module n = pq, for example of 768-bit dimension, where p and q denote two prime numbers.

It also chooses an integer b greater than 1, for example b = 4, and two quadratic residues a and g modulo n, Le., A, g £ ¾.

The certification authority 3 generates from these numbers and a hazard z, a value h such that:

h = g ^{~ z} (rnod). In the embodiment described here, the master key pair is then given by: mpk = (n, g, a, h, b) and msk = (p, q, z).

The master public key mpk of the certification authority 3 is published.

Entity 2 generates a user secret key usk from an integer s of dimension 400 bits here (step G20), i.e. usk = s.

Then it evaluates from its secret key s and the public key mpk of the certification authority 3, a value v = g ^{~ s} (mod ri) (step G30).

The entity 2 then sends the certification authority 3 its public identifier /, the value v and a proof of knowledge of the secret user key s according to a protocol with zero disclosure of knowledge (step G40). This protocol is based for example on a GPS type authentication scheme as described above or as illustrated in the document by Mr. Girault. Such a protocol is known per se and will not be described in more detail here.

On receipt of these elements, the certification authority 3 verifies the proof of knowledge sent by the entity 2, then generates, from the public identifier / and the value v, a certificate formed of a pair of values (A, e) (step G50).

More specifically, e is an integer chosen randomly by the certification authority 3 and associated with the public identifier / (i.e. a distinct integer e is chosen for each public identifier J), of 128-bit dimension here. Furthermore, in the embodiment described here, the certification authority 3 generates the value A according to:

A = (ah'v ^ mod ri),

i

with d = - (mod (p-) (q-1)).

In other words, A ^{eb is} written as:

A ^e "= f (h, v, ri)

with f (h ^l , v, ri) = ah ^l v (mod ri) and b greater than 1.

Then the certification authority 3 sends the certificate (A, e) thus generated to the entity 2 (step G60).

In the embodiment described here, upon receipt of this certificate, the entity 2 verifies that (step G70):

- (mod ri).

If necessary, the user public key upk is formed from the certificate (A, e) received from the certification authority 3 and the public identifier / from the entity 2 (step G80), otherwise upk = (A, e, I).

Advantageously, the user key pair (upk, usk) thus obtained by the entity 2 is compatible with an authentication or signature scheme of a GPS type message.

More specifically, with reference to FIG. 5, we will briefly describe how the user key pair thus obtained can be used to enable the entity 2 to authenticate itself to the verifier device 4 by means of a schema. GPS authentication based on the public / entity identifier 2.

Following the implementation of the generation method described with reference to FIG. 4 (step H10), the entity 2 thus obtains the user key pair (upk, usk) generated according to the invention (step H 20).

In order to authenticate according to a GPS scheme with the verifier device 4, it sends to it its public key upk = (A, e, I) certified by the certification authority 3 (step H30).

On receipt of the public key upk, the verifier device 4 evaluates a new public key v 'according to:

A ^e "

v '= - (modw)

(ah)

using the master public key issued by the certification authority 3 (step H40).

A GPS authentication scheme is then implemented between the entity 2 and the verifier device 4, similarly to what has been described above with reference to FIG. 1, but applied to the public key v 'evaluated by the verifier device 4, to the element g published by the certification authority 3, and to the secret key usk of the entity 2 (step H50). The steps of this diagram being identical to those described with reference to Figure 1, they will not be described again here.

Similarly, the entity 2 can sign a message m according to a GPS signature mechanism as described above, using the user key pair (upk, usk) generated in accordance with the invention. The verifier device 4 then verifies, upon receipt of the message m and its signature, that the signature is valid by applying the verification steps detailed previously and using as public key v '.

In the previous example, we considered an identifier / of the entity 2 of dimension

160 bits, an RSA module n of 768 bits dimension, an integer b = 4 and a secret key s of the entity 2 of dimension 400 bits. However, the invention is not limited to these numerical values. Other numerical values may be considered depending on the level of security required, as illustrated now.

In the rest of the description, we note: - LEV, the required security level and LS a security parameter,

- Ln, the size in bits of the RSA n module,

- bit size of the z randomness,

The size in bits of the identifier / of the entity 2,

The size in bits of the element e and

- Lusk the bit size of the secret key of entity 2,

Based on the work of Mr. Joye cited above, the following relationships can be established between these parameters to maintain the LEV security level:

Ln> 2 (The + 2) (1)

b {The - 1)> Lusk + 1 (2)

Ln - 4> Lusk> Lz + Ll + ls (3)

The = LEV + 30 (4)

Relations (2) and (3) also lead to the following relation:

b (The - 1)> Lusk> Lz + Ll + LS (5)

In general, the LEV, LS, Ln, Lz and L1 parameters are set according to the level of security that is desired for the underlying cryptographic problems that result from the certification proposed by the invention (ie factoring, logarithms These problems are relatively standard in the state of the art, the fixing of these parameters does not pose any difficulty in itself to the skilled person.

The values of the parameters Le, b and Lusk can then be set according to the values chosen for the parameters LEV, LS, Ln, Lz and Ll.

For example, one can choose as a secret key dimension Lusk, a dimension consistent with the recommendations of various instances in cryptography, and in particular for example by the consortium ecrypt2. These recommendations are recalled at the following URL: http: //www.keylength.eom/en/3/ and an excerpt is reproduced in Appendix 1. More details on these recommendations are available in the document entitled "Yearly Report on Algorithms". and KeySizes (2011) ", D.SPA.17 Rev. 1.0, ICT-2007-216676 ECRYPT II, June 2011.

As an illustration, according to these recommendations, if one chooses a level of security LEV = 80 bits (extracted from the "symmetrical" column of the table in appendix 1), one has:

Ln = 1248 bits (extracted from the "asymmetric" column of the table in appendix 1),

= 160 bits (extract from the "discrete key" column of the table in appendix 1),

Ll = 160 bits (from the "hash" column of the table in Appendix 1),

LS = 80 bits (extracted from the "symmetrical" column of the table in Appendix 1), and

L = 110 bits (see application of relation (4)).

It follows from relation (5) that b = 4 and Lusk = 400 bits.

According to another example, if one chooses a level of security LEV = 128 bits, one has: Ln = 3248 bits,

= 256 bits, U = 256 bits,

LS = 128 bits, and

= 158 bits (see application of relation (4)).

It follows from relation (5) that b = 5 and Lusk = 640 bits.

Of course these examples are given for illustrative purposes, and other numerical values may be chosen for the execution of the invention. However, in order to guarantee a sufficient level of security, a public identifier / for the entity 2 comprising at least 160 bits and a user secret key of at least 400 bits is preferably chosen.

In the example illustrated in FIG. 4, the certification authority 3 used during the step G50, to generate the certificate (A, e), a function of the form:

f (h ^l , v, ri) = ah'v (nod ri)

with

A ^eb = f {h, v, n)

h = g ^{~ z} (mod ri) and b being greater than 1 (eg b = 4).

This example, although very advantageous, is however not limiting in itself, and other functions may be envisaged alternatively.

Thus, in an alternative embodiment, the certification authority 3 generates during the step G50 a certificate CA, e) for the public identifier I, where e is an integer chosen randomly by the certification authority 3 and associated with the public identifier / (the a distinct integer e is chosen for each public identifier 1), and the value A is generated according to:

A ^e = (ah ¹ v) (rnod r 1),

where the value h is a random value of the same dimension as n, determined from a randomness z. The hazard z is for example the seed of a pseudo-random generator.

In other words, A ^{eb is} written as:

A ^e "= f {h, v, n)

with f (h ^l , v, ri) = ah ^l v (rnod ri) and b = \ at step G10.

Correlatively, upon receipt of this certificate, entity 2 then verifies during step G70 that:

A ^e

v = - 7 (rnod ri).

ha

Moreover, with reference to FIG. 5, the authentication of the entity 2 by the verifier device 4 is based on the evaluation by the verifier device 4 of a new public key v 'during the step H40 according to:

using the master public key issued by the CA 3.

For such a function, building on the work described in the document by J. Camenisch et al. entitled "A signature scheme with efficient protocols", SCN'02, vol. 2576 of Lecture Notes in Computer Science, pages 268-289, Springer 2002, one can consider using the following parameter dimensions, with the notations introduced previously:

Ln = 1024 bits,

U = 160 bits,

the = 162 bits,

Lusk = 1346 bits.

Moreover, for an 80-bit security, we can take Lz = 80 bits

In another variant embodiment, the certification authority 3 generates during the step G50 a certificate CA, e) for the public identifier /, where e is an integer chosen randomly by the certification authority 3 and associated to the public identifier / (ie a separate integer e is chosen for each public identifier J), and the value A is generated according to:

A ^e = (h ¹ + v) (rnod r 1),

where the value h is a random value of the same dimension as n, determined from a randomness z.

The hazard z is for example the seed of a pseudo-random generator.

In other words, A ^{eb is} written in this variant in the form:

A ^eb = f {h, v, n)

with f (h ^l , v, ri) = h ¹ + v) (nod ri) and b = \ at step G10.

v = A ^e + h ^l (mod ri).

v '= A ^e + h'Cmod ri)

using the master public key issued by the CA 3. Annex 1

Extract of the recommendations ECRYPT II (20111

Symmetric Asymmetric Level Discrete Key Hash Curve Group

Elliptical Loqarithmic

1 32

2 64 816 128 816 128 128

3 72 1008 144 1008 144 144

4 80 1248 160 1248 160 160

5 96 1776 192 1776 192 192

6 112 2432 224 2432 224 224

7 128 3248 256 3248 256 256

8 256 15424 512 15424 512 512

Claims

A cryptographic method for generating a user key pair for an entity (2) having a public identifier /, the method comprising:

A step of generating (G10), by a certification authority (3), a pair of master keys comprising:

a secret master key comprising the prime numbers p and q;

A step of generation (G20) by the entity (2) of a secret user key s from a random;

An evaluation step (G30) by the entity (2), from the secret user key and the master public key, of a value v = g ^{~ s} (mod n);

A step of sending (G40) by the entity (2) this value v to the certification authority (3) with a proof of knowledge of the secret user key according to a protocol with null disclosure of knowledge;

A generation step (G50) by the certification authority, based on the public identifier / entity and the value v, of a certificate formed of a pair of values {A, e) in which e is a hazard associated with the public identifier / and:

A ^e "= f {h, v, n),

where / is a predetermined function; and

A step of sending (G60) the certificate (A, e) to the entity by the certification authority;

these steps resulting in obtaining (G80) a user key pair for the entity comprising the user secret key s and a user public key formed from the values A and e and the identifier / entity .

2. The method of claim 1 wherein:

h = g ^{~ z} (mod), and

A = (ah ^l v) ^d (mod),

(mod (p-1) (q-1)) and b greater than 1.

3. The method of claim 1 or 2 further comprising a verification step (G70) by the entity (2) that: v = - 7 {mod ri).

ha

4. Method according to any one of claims 1 to 3 wherein the public identifier / comprises at least 160 bits.

5. Method according to any one of claims 1 to 3 wherein the secret user key s comprises at least 400 bits.

The method of claim 1 wherein:

A ^e = ah'v mod n).

7. Method according to any one of claims 1 to 6 wherein the zero knowledge disclosure protocol is based on a GPS type authentication scheme.

8. A method of authenticating an entity (2) having a public identifier / with a verifier device (4), by using a user key pair generated according to the generation method according to any one of claims 1 to 7, the authentication (H50) of the entity (2) being performed using a GPS type authentication scheme implemented between the entity and the verifier device.

9. A method of signing a message by an entity (2) having a public identifier / using a user key pair generated according to the generation method according to any one of claims 1 to 7, the signature of the message being realized using a GPS type signature scheme.

10. Method of obtaining by an entity (2) having a public identifier / of a pair of user keys comprising a user public key and a user private key, this method comprising:

A step of generating (G20) the secret user key s from a random;

An evaluation step (G30) starting from:

o this secret user key; and

a public key master of a certification authority (3) comprising an RSA module n, produced of two prime numbers p and q, an integer b greater than or equal to 1, two quadratic residues and g modulo n, and a value h determined from a hazard z,

a value v = g ^{~ s} (mod n); A step of sending (G40) the value v to the certification authority (3) with a proof of knowledge of the secret user key according to a protocol with null disclosure of knowledge;

A step of receiving (G60) the certification authority (3) of a certificate consisting of a pair of values (A, e), in which e is a random associated with the public identifier /, and:

A ^e "= f {h, v, n),

where / is a predetermined function; and

A step of obtaining (G80) the user public key from the values A and e and the identifier / entity.

11. A method of sending by a certificate authority (3) a certificate to an entity (2) having a public identifier / for forming a public user key for that entity, the method comprising:

A step of generating (G10) a pair of master keys comprising:

a secret master key comprising the prime numbers p and q;

A reception step (G40) originating from the entity of a value v = g ^{~ s} (mod) generated by the entity using its user private key s, and a proof of knowledge of the secret user key according to a protocol with zero disclosure of knowledge;

A generation step (G50), from the public identifier / entity and the value v, of a pair of (A, e) in which e is a random associated with the public identifier / , and:

A ^eb = f {h, v, n),

where / is a predetermined function; and

A step of sending (G60) the pair (A, e) to the entity.

12. Entity (2) having a public identifier / comprising:

A module for generating a secret user key from a random;

- an evaluation module, able to evaluate from:

o this secret user key; and

o of a public key master of a certification authority comprising an RSA n module, product of two prime numbers p and q, an integer b greater than or equal to 1, two quadratic residues a and g modulo n, and a value h determined from a randomness z, a value v = g ^{~ s} (mod);

A module for sending the value v to the certification authority with a proof of knowledge of the secret user key according to a protocol with null disclosure of knowledge; A reception module from the certification authority, a certificate consisting of a pair of values (A, e) in which e is a random associated with the public identifier /, and:

A ^eb = f {h, v, n),

where / is a predetermined function; and

13. Certification Authority (3) comprising:

A module for generating a pair of master keys comprising:

a secret master key comprising the prime numbers p and q;

A module for verifying said proof of knowledge;

A ^eb = f {h, v, n),

where / is a predetermined function; and

A module for sending the pair (A, e) to the entity.

14. System (1) comprising:

An entity (2) having a public identifier / according to claim 12; and

A certification authority (3) according to claim 13;

15. System (1) according to claim 14 further comprising a verifier device (4), able to authenticate the entity (2) by applying a GPS authentication scheme or to check the validity of a signature of a message generated by the entity (2) by applying a GPS signature scheme.

Computer program comprising instructions for carrying out the steps of the obtaining method according to claim 10 or the sending method according to claim 11 when said program is executed by a computer.