Method of transferring a secret, by the exchange of two certificates between two microcomputers which establish reciprocal authorization

• US 5,218,637 A
• Filed: 06/11/1991
• Issued: 06/08/1993
• Est. Priority Date: 09/07/1987
• Status: Expired due to Term

• Current Assignee: Etat Francais, Represente Par Le Ministere Des Postes, Des Telecommunications Et De L'Espace, US Philips Corporation (Koninklijke Philips N.V.), Telediffusion De France SA
• Original Assignee: ETAT Francais Represente PAR Le Ministre Des Postes et Telecommunications Centre National
• Inventors: Guillou, Louis, Quisquater, Jean-Jacques, Angebaud, Didier, Giachetti, Jean-Luc
• Primary Examiner(s): CAIN, DAVID C
• Application Number:
  US07/714,120
• Time in Patent Office: 728 Days
• Field of Search: 380/23, 380/25
• US Class Current: 713/173
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/0826 Embedded security module
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

According to the invention, the chip card issues a first certificate comprising its letter of credentials (Crc), an exponential (X), an optional message (M), these quantities being signed. The security module verifies the signature and in return issues a second certificate containing its letter of credentials (Crm), an exponential (Y), an optional message (M'"'"'), a cryptogram (C), these quantities being signed. A common secret key is constituted between the card and the security module by the exponentials and allows the card to interpret the cryptogram addressed to it and to act in accordance therewith.

Claims

1. A method of secured transfer of information S to a first microcomputer belonging to a chip card from a second microcomputer belonging to a security module, the first and second microcomputers establishing reciprocal authentication, this method being characterized in that:

a) a first authority is entitled to issue cards which have previously been provided with a first public key constituted by a first modulus n, a first verification exponent v and a first signature exponent s, each card having been defined by an accreditation Bc obtained by signature of a credential Crc, which signature can be verified with the aid of this first public key,

b) a second authority is entitled to issue security modules which have also previously been provided with a second public key constituted by a second modulus n'"'"', a second verification exponent v'"'"' and a second signature exponent s'"'"', the security module having been defined by an accreditation Bm obtained by signature of a credential Crm, which signature can be verified with the aid of the second public key,

c) finally, the first and second microcomputers have previously publicly agreed to use exponentials in a finite set suitable to establish a common transistory key,

d) this method comprises the following steps;

A) in a first computational stage, realized by the first microcomputer, calculating an exponential X, an optional message M and a calculated signature from the exponential X and the optional message M, this signature being verifiable with the aid of the first public key,

B) in a first data transfer, transmitting, from the first microcomputer to the second microcomputer, a first certificate which comprises the credentials of the card Crc, as well as the calculated signature,

C) in a second computational stage, realized by the second microcomputer,

i) verifying, with the aid of the first public key, whether the certificate received by the second microcomputer has been properly signed by the card, and,

ii) if so, calculating the exponential of the exponential X, which constitutes a common transitory key,

iii) then calculating an optional message M'"'"' and the second microcomputer'"'"'s own exponential Y,

iv) thereafter working out a cryptogram C from the common transitory key K and from the information S to be transmitted, and

v) signing the optional message M'"'"', the exponential of the second microcomputer Y and the cryptogram C,

D) in a second data transfer, transmitting, from the second microcomputer to the first microcomputer, a second certificate which comprises the credential of the security module Crm as well as the signed exponential of the second microcomputer Y, optional message M'"'"' and cryptogram C,

E) in a third computational stage, realized by the first microcomputer,

i) verifying with the aid of the second public key, whether the second certificate received from the second microcomputer has been properly signed by the second microcomputer,

ii) if so, calculating the exponential of the exponential Y received from the second microcomputer, which gives the common transitory key K; and

iii) extracting, from the cryptogram C using the common transitory secret K, the information S which is contained in the cryptogram C and which is intended for the first microcomputer,

all of the variables herein representing integers.

2. A method as claimed in claim 1, characterized by the fact that the first and second authorities are one and the same.

3. A method as claimed in claim 1, characterized in that

A) the first calculation stage includes,

i) randomly selecting an element r from the set of integers mod*n

ii) calculating the v^th power of this element r, to yield an initial evidence Tb (Tb=r^v mod*n),

iii) applying a compression function ("Hash") to a bit train containing the exponential X, the optional message M and the initial evidence Tb,

iv) developing an initial pseudo challenge db having a value from 0 to v-1, (db=select(Hash(X,M,Tb)) by selecting bits from the result of the compression, and

v) calculating mod*n the product of the element r by the db^th power of the first microcomputer'"'"'s accreditation Bc, the result being an answer D, (D=r·

Bc^db mod*n) and

B) the first certificate is a bit train containing the credential of the card Crc, the value of the exponential X, the optional message M, the initial pseudo-challenge db and the answer D, the initial pseudo-challenge db and the answer D signing the exponential (X) and the optional message (M).

4. A method as claimed in claim 1, characterized in that

in step d)C)iv), the second microcomputer calculates the cryptogram C from the common transitory key K and from the information S by an exclusive-OR operation between S and K,

in step d)E)iii), the first microcomputer extracts the information S from the cryptogram C by the same exclusive-OR operation between the cryptogram C and the common transitory key K.

5. A method as claimed in claim 1, further comprising the steps of

defining each card by a representative Jc obtained by redundancy of the credential (Jc=Red(Crc)),

in the entitled authority, raising the representative Jc to a power -s mod*n, to yield the accreditation Bc (Jc·

Bc^v mod*n=1),

defining each security module by a representative Jm obtained by redundancy of the credential of the security module (Jm=Red(Crm)),

in the entitled authority, raising the representative Jm to a power -s'"'"' mod*n'"'"', to yield an accreditation Bm (Jm·

Bm^v mod*n'"'"'=1).

6. A method as claimed in claim 3 wherein

C) the second computational stage includes

i) to verify that the first certificate is correct

α

) calculating mod*n the product of the v^th power of the answer D by the db^th power of its representative Jc, to yield a final evidence Tf (Tf=D^v Jc^db mod*n),

β

) applying the compression function ("Hash") to a bit train containing the exponential X, the optional message M, and the final evidence Tf,

γ

) developing a final pseudo-challenge df having a value from 0 to v-1 by selecting bits of the result of the compression, (df=select (Hash(X,M,TF))),

δ

) accepting continuation of processing if, and only if, the final pseudo-challenge df is equal to the initial pseudo-challenge db, which indicates that the first microcomputer has properly signed the exponential X and the message M, and therefore that the first certificate is correct,

v) to sign the optional message M'"'"', the exponential Y, and the cryptogram C

α

) randomly selecting an element r'"'"' from the set of integers mod*n'"'"',

β

) calculating mod*n'"'"' the v'"'"'^th power of this element, to yield an initial evidence Tb'"'"', (Tb'"'"'=r'"'"'^v'"'"' mod*n'"'"'),

γ

) applying the compression function ("Hash") to a bit train containing the exponential Y, the optional message M'"'"', the cryptogram C, and the initial evidence Tb'"'"', (Hash(Y,M'"'"',C,Tb),

δ

) developing an initial pseudo-challenge db'"'"' having a value from 0 to v'"'"'-1 from bits of the result of the compression, (db'"'"'=select(Hash(Y,M'"'"',C,Tb'"'"'))),

ε

) calculating mod*n'"'"' the product of the element r'"'"' by the db'"'"'^th power of the accreditation of the module Bm to yield an answer D'"'"', (D'"'"'=r'"'"'Bm^db'"'"' mod*n'"'"'),

D) the second certificate comprises a bit train containing the credential of the module CRM, the exponential of the second microcomputer Y, the optional message M'"'"', the cryptogram C, the initial pseudo-challenge db'"'"', the answer D'"'"', the two data elements db'"'"' and D'"'"' signing the exponential of the second microcomputer Y, the optional message M'"'"' and the cryptogram C.

7. A method as claimed in claim 6, characterized in that the third computational stage includes

i) as part of verifying the second certificate

α

) calculating mod*n'"'"' the product of the v'"'"'^th power of the answer D'"'"' by the db'"'"'^th power of the representative of the module Jm corresponding to the credential of the security module Crm to yield a final evidence Tf'"'"', (Tf'"'"'=D'"'"'^v'"'"' Jm^db'"'"' mod*n),

β

) applying the compression function ("Hash") to a bit train containing the exponential of the second microcomputer Y, the optional message M'"'"', the cryptogram C, and the final evidence Tf'"'"',

γ

) developing a final pseudo-challenge df'"'"' having a value from 0 to v'"'"'-1 from bits of the result of the compression, (df'"'"'=select(Hash(Y,M'"'"',C,Tf'"'"'))),

δ

) accepting continuation of processing if, and only if, the final pseudo-challenge df'"'"' is equal to the initial pseudo-challenge db'"'"', which indicates that the second microcomputer has properly signed the exponential X, the optional message M'"'"', and the cryptogram C, and therefore that the second certificate is correct.

12. A method as claimed in claim 6, characterized in that d)C)i) verifying the second certificate includes

α

) calculating mod*n'"'"' the product of the v'"'"'^th power of the answer D'"'"' by the db'"'"'^th power of the representative of the module Jm corresponding to the credential of the security module Crm to yield a final evidence Tf'"'"', (Tf'"'"'=D'"'"'^v'"'"' Jm^db'"'"' mod*n),

β

) applying the compression function ("Hash") to a bit train containing the exponential of the second microcomputer Y, the optional message M'"'"', the cryptogram C, and the final evidence Tf'"'"',

γ

) developing a final pseudo-challenge df'"'"' having a value from 0 to v'"'"'-1 from bits of the result of the compression, (df'"'"'=select (Hash(Y,M'"'"',C,Tf'"'"'))),

δ

) accepting continuation of processing if, and only if, the final pseudo-challenge df'"'"' is equal to the initial pseudo-challenge db'"'"', which indicates that the second microcomputer has properly signed the exponential X, the optional message M'"'"', and the cryptogram C, and therefore that the second certificate is correct.

15. The method of claim 1 wherein

the finite set is a finite field having a first number p as its characteristics and a base which is a primitive element a of the field,

step d) A) comprises calculating the exponent X according to the equation X=a^x mod p, where x is a positive exponent less than p,

step d)C)v) comprises selecting a positive integer y less than p and calculating the exponential of the second microcomputer according to the equation Y=a^y mod p,

step d)C)iv) comprises calculating the common transitory key according to the equation K=(a^x)^y mod p, and

step d)E)ii) comprises calculating the common transitory key according to the equation K=(a^y)x mod p.

8. A method of secured transfer of information to a first microcomputer belonging to a chip card from a second microcomputer belonging to a security module, the first and second microcomputers establishing reciprocal authentication, this method being characterized in that:

a) a first authority is entitled to issue cards which have previously been provided with a first public key constituted by a first modulus n, a first verification exponent v and a first signature exponent s, each card having been defined by an accreditation Bc obtained by signature of a credential Crc, which signature can be verified with the aid of this first public key,

b) a second authority is entitled to issue security modules which have also previously been provided with a second public key constituted by a second modulus n'"'"', a second verification exponent v'"'"', and a second signature exponent s'"'"', a security module having been defined by an accreditation Bm obtained by signature of a credential Crm, which signature can be verified with the aid of the second public key,

c) the first and second microcomputers have previously publicly agreed to use exponentials in a finite set suitable to establish a common transitory key,

d) this method comprises the following steps;

A) in the second microcomputer,

i) retrieving a stored first certificate including credentials of the card Crc and a signature of an exponential X and an optional message M,

ii) verifying with the aid of the first public key whether the first certificate has been properly signed,

iii) if so, calculating the exponential of the exponential X to yield a common transitory key K,

iv) then calculating an optional message M'"'"' and the second microcomputer'"'"'s own exponential Y,

v) thereafter working out a cryptogram C from the common transitory key K and from the information S to be transmitted, and

vi) signing the optional message M'"'"', the exponential of the second microcomputer Y'"'"' and the cryptogram C,

B) transmitting, from the second microcomputer to the first microcomputer, a second certificate which comprises the credential of the security module Crm as well as the signed exponential of the second microcomputer Y, optional message M'"'"', and cryptogram C,

C) in the first microcomputer,

i) verifying with the aid the of the second public key, whether the second certificate received from the second microcomputer has been properly signed by the second microcomputer,

ii) if so, calculating the exponential of the exponential Y received from the second microcomputer, to yield the common transitory key K, and

iii) extracting, from the cryptogram C using the common transitory key K, the information S which is contained in the cryptogram C and which is intended for the first microcomputer,

all of the variables herein representing integers.

9. The method of claim 8 wherein the first and second authority are one and the same.

10. A method as claimed in claim 8, further comprising the steps of

defining each card by a representative Jc obtained by redundancy of the credential (Jc=Red(Crc)),

in the entitled authority, raising the representative Jc to a power -s mod*n, to yield the accreditation Bc (Jc·

Bc^v mod*n=1),

defining each security module by a representative Jm obtained by redundancy of the credential of the security module (Jm=Red(Crm),

in the entitled authority, raising the representative Jm to a power -s'"'"' mod*n'"'"', to yield an accreditation Bm (Jm·

Bm^v mod*n'"'"'=1).

11. A method as claimed in claim 8 wherein

d)A)i) the first certificate is a bit train containing the credential of the card CRC, the value of the exponential X, the optional message M, an initial pseudo-challenge db and an answer D, the initial psuedo challenge db and the answer D signing the exponential X and the optional message M, where

13. The method of claim 8 wherein, in order to store the first certificate in the directory, the second authority performs the following steps:

assigning to each card a rank in a group of cards,

assigning a common exponent x to the group, and

calculating a collective certificate valid for the group, with the aid of an auxiliary microcomputer and based on using the exponent x as the exponent for the whole group.

14. The method of claim 8 wherein

the finite set is a finite field having a first number p as its characteristics and a base which is a primitive element a of the field,

the exponent X satisfies the equation X=a^x mod p, where x is a positive exponent less than p,

step d)A)iv) comprises selecting a positive integer y less than p and calculating the exponential of the second microcomputer according to the equation Y=a^y mod p,

step d)A)iii) comprises calculating the common transitory key according to the equation K=(a^x)^y mod p, and

step d)C)ii) comprises calculating the common transitory key according to the equation K=(a^y) x mod p.

16. A method as claimed in claim 8, characterized in that

in step d)A)v), the second microcomputer calculates the cryptogram C from the common transitory key K and from the information S by an exclusive-OR operation between S and K,

in step d)C)iii), the first microcomputer extracts the information S from the cryptogram C by the same exclusive-OR operation between the cryptogram C and the common transitory key K.