Method for authenticating an entity by a verifier

• US 8,522,027 B2
• Filed: 06/16/2009
• Issued: 08/27/2013
• Est. Priority Date: 06/16/2008
• Status: Active Grant

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Canard, Sbastien, Coisel, Iwen, Girault, Marc
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): BAYOU, YONAS A
• Application Number:
  US12/997,109
• Publication Number:
  US 20110107102A1
• Time in Patent Office: 1,533 Days
• Field of Search: 713/170
• US Class Current: 713/170
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method for authenticating an entity by a verifier, the entity having an identifier, the verifier having a pair of private and public keys, comprising: sending to the entity a first random number selected by the verifier; a step wherein the entity encrypts a value by means of the public key of the verifier, said value including the first random number and an authentication datum on which the identifier of the entity depends; and the entity of said encrypted value sending a reply to authenticate said entity. The invention can be applied to the field of low-cost cryptography, especially the field of radio-identification.

Claims

1. A method for authenticating an entity with a verifier, the entity possessing an identifier, the verifier possessing a private key/public key pair, the method comprising the steps:

sending to the entity a first random number chosen by the verifier,

encrypting a value (v) by the entity by means of the public key of the verifier, said value comprising the first random number and an authentication datum on which the identifier of the entity depends, in which the encryption complies with a public-key encryption scheme, called the modified El Gamal scheme, wherein;

the step of encrypting the value (v) produces two elements T′

₁=v⊕

H(y^w), and T₂′

=g^w, where;

H is an identity function or a hash function, and ⊕

an exclusive or operation,

g is a generator of a group used by said scheme,

y is the public key with which the private key x of the verifier is associated, said keys being such that y=g^x,

w is a second random number chosen by the entity,

the step of decryption by the verifier of the two elements T₁ and T₂ computes T₁′

⊕

H(T₂′

^x) so as to provide said value (v), and

sending in response, by the entity, of a message comprising said encrypted value, for authentication of said entity.

2. The method as claimed in claim 1, wherein the authentication datum is an antecedent of the identifier, a one-way function applied to this antecedent producing the identifier of the entity.

3. The method as claimed in claim 1, wherein the encryption step uses at least one result of a pre-computation, stored in the entity.

4. The method as claimed in claim 1, comprising sending by the entity of an authentication message computed by means of a secret key and of a message to be protected, said secret key depending on the identifier of the entity, said message to be protected comprising at least one part of the first random number.

5. The method as claimed in claim 4, wherein the authentication datum included in the encrypted value (v) for the verifier comprises the identifier and the authentication message.

6. The method as claimed in claim 1, comprising the following steps performed beforehand:

pre-computation of a predefined number of authentication coupons, an authentication coupon comprising two parts, said two parts depending on the second random number chosen by the entity and being necessary in order to compute the two elements corresponding to the encryption of the value,

storage of said predefined number of coupons by the entity, a coupon being used by the entity to respond to an authentication request originating from the verifier.

7. An entity adapted for being authenticated by a verifier, the entity possessing an identifier, the verifier possessing a private key/public key pair, and comprising:

a receiver configured to receive from the verifier a first random number chosen by the verifier,

an encryption element configured to encrypt a value (v) by means of the public key of the verifier, said value comprising the first random number and an authentication datum on which the identifier of the tag depends, in which the encryption complies with a public-key encryption scheme, called the modified E1 Gamal scheme, wherein;

. . .

a sender configured to send said encrypted value (v) to the verifier.

8. The entity as claimed in claim 7, further comprising a storing element of at least one result of a pre-computation for use by the encryption means.

9. A verifier adapted for authenticating at least one entity, the entity possessing an identifier, the verifier possessing a private key/public key pair, the verifier comprising:

a sender configured to send a first random number to the entity,

a receiver configured to receive from the entity a value (v) encrypted by means of the public key of the verifier, said value comprising the first random number and an authentication datum on which the identifier of the tag depends, in which the encryption complies with a public-key encryption scheme, called the modified E1 Gamal scheme, wherein;

. . .

a decryption element configured to decrypt by means of the private key of the verifier the encrypted value received from the entity.

10. A non-transitory computer program product for installation in a memory of a verifier, comprising instructions which when executed by the verifier cause the verifier to perform the steps of:

sending to the entity a first random number chosen by the verifier,

encrypting a value (v) by the entity by means of the public key of the verifier, said value comprising the first random number and an authentication datum on which the identifier of the entity depends, in which the encryption complies with a public-key encryption scheme, called the modified E1 Gamal scheme, wherein;

the step of encrypting the value (v) produces two elements T′

.sub.1.v.sym.H(y.sup.w), and T′

.sub.2.g.sup.w, where;

H is an identity function or a hash function, and .sym. an exclusive or operation,

g is a generator of a group used by said scheme,

y is the public key with which the private key x of the verifier is associated, said keys being such that y=g.sup.X,

w is a second random number chosen by the entity,

the step of decryption by the verifier of the two elements T.sub.1 and T.sub.2 computes T′

.sub.1.sym.H′

(T′

.sub.2.sup.x) so as to provide said value (v), and

sending in response, by the entity, of a message comprising said encrypted value, for authentication of said entity.