METHOD FOR AUTHENTICATING AN ENTITY BY A VERIFIER

• US 20110107102A1
• Filed: 06/16/2009
• Published: 05/05/2011
• Est. Priority Date: 06/16/2008
• Status: Active Grant

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Coisel, Iwen, Girault, Marc, Canard, Sébastien
• Granted Patent: US 8,522,027 B2
• Time in Patent Office: Days
• 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, 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, wherein the encryption complies with an El Gamal public-key encryption scheme, and further comprising the step:

encrypting the value (v) to produce two elements T₁=v·

y^w and T₂=g^w, where

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, and

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

T₂<sup>−

x</sup> so as to provide said value (v).

5. The method as claimed in claim 1, wherein the encryption complies with the modified El Gamal public-key encryption scheme, and further comprising the steps:

encrypting the value (v) to produce two elements T′

₁=v⊕

H(y^w), and T′

₂=g^w, where

H is an identity 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, and

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

₁⊕

H (T′

₂^x) so as to provide said value (v).

6. The method as claimed in claim 1, wherein the encryption complies with the modified El Gamal public-key encryption scheme, and further comprising the steps:

encrypting the value (v) to produce two elements T′

₁=v⊕

H(y^w), and T′

₂=g^w, where

H′

is 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, and

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

₁⊕

H′

(T′

₂^x) so as to provide said value (v).

7. The method as claimed in claim 5, 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.

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

9. The method as claimed in claim 4, 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.

13. A non-transitory computer program product for installation in a memory of a verifier, comprising instructions for the implementation of the steps of the method for authenticating an entity as claimed in claim 1, which are executed by the verifier when the program is executed by a processor.

14. A data medium on which the computer program as claimed in claim 13 is recorded.

15. A non-transitory computer program product for installation in a memory of an entity, comprising instructions for the implementation of the steps of the method for authenticating an entity as claimed in claim 1, which are executed by the entity when the program is executed by a processor.

10. 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 designed to receive from the verifier a first random number chosen by the verifier,

an encryption element designed 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, and

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

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

12. 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 designed to send a first random number to the entity,

a receiver designed 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, and

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