WO1998023061A1

WO1998023061A1 - Method for signing and/or authenticating electronic messages

Info

Publication number: WO1998023061A1
Application number: PCT/FR1997/002086
Authority: WO
Inventors: Jacques Stern; Françoise LEVY-DIT-VEHEL; David Naccache
Original assignee: Gemplus S.C.A.
Priority date: 1996-11-20
Filing date: 1997-11-20
Publication date: 1998-05-28
Also published as: CA2271989A1; FR2756122B1; EP0940021A1; JP2001503162A; FR2756122A1

Abstract

The invention concerns the signing and/or authenticating of electronic messages in which a computing algorithm uses digital keys (N, e, d) implanted on chip cards; the keys comprising in particular an integer called module N. The method is characterised in that several keys (N, e, d), (N, e', d') comprise an identical module (N) and that these keys will be dedicated to the signature, verification and/or authentication of messages. The invention is particularly useful for identifying the user of the card keys or the identification of the services used by one or several users.

Description

METHOD FOR SIGNING AND / OR AUTHENTICATING ELECTRONIC MESSAGES.

The present invention relates to a method for signing and / or authenticating electronic messages.

It is particularly intended to be implemented using a portable microprocessor device of the "electronic chip card" type.

In order to preserve the exclusivity of certain services, a smart card generally includes digital keys, a digital key consisting of a string of digital characters which will be used by a calculation algorithm to sign or authenticate messages exchanged between the card and a verifier such as a reading terminal or a central authority, or else to authenticate the card used.

One can also use such keys to encrypt the transmitted messages. The messages can then be decrypted only by an organ possessing either a key equal to the encryption key (we then speak of symmetric cryptography), or a corresponding key (asymmetric cryptography) to the secret encryption key.

For example, this involves signing messages sent by a card to a reading terminal or to a central authority; or again, it involves making a transaction (electronic check) and signing this transaction so that it can be verified first by the reading terminal in which the transaction is made, then by a central authority which manages the transactions. Thereafter, the expressions "electronic signature" and "digital signature" will be used interchangeably, or the expressions "digital key" and "electronic key". Indeed, signing using keys made up of digital channels is particularly suitable for signing messages transmitted electronically.

An electronic signature is calculated using a series of calculation rules defined by an algorithm and a set of parameters used in these calculations. The signature allows both to ensure the identity of the signatory (because it involves a secret exponent specific to the signatory) and the integrity of the signed message (because it involves the message itself). The algorithm allows on the one hand, to generate signatures and on the other hand, to verify signatures; operation called verification.

Authentication is a specific verification operation during which the terminal or the central authority verifies only a signature of the card, before any exchange of significant messages. During this procedure, the verifier sends any message to the card which returns it signed. The verifier can then authenticate the signature of this message. Authentication preferably involves a different digital key from that reserved for message signature / verification operations.

The signature and authentication process which will be described is intended in particular to be used with a standardized algorithm called RSA named after its inventors (Rivest, Shamir and Adleman), a description of which can be found in US Patent 4,405,829. RSA signature generation involves a secret exponent. The audit involves a public setting that corresponds to the ^'secret exponent but is not identical to it. Each user has a pair of exhibitors (secret, public). Public exhibitors can be known to everyone, while secret exhibitors are never revealed. Anyone has the ability to verify a user's signature using their public exponent, but only the owner of the secret exhibitor can generate a signature corresponding to the pair of exhibitors.

More precisely, the RSA electronic keys comprise three parameters (N, e, d) called respectively module N, public exponent e, and secret exponent d. The first two numbers (N, e) can be read on the smart card, where they are stored, and are called public parameters. On the other hand, the secret exponent d is stored in a protected memory area of the card which cannot be read from the outside. Only the protected computing circuits of the card can access the secret exponent d for reading.

The electronic keys are installed in a card by programming an EEPROM read-only memory. The public parameters (N, e) are located in an area of the EEPROM memory accessible for reading by a terminal. On the contrary, the secret exponent d is located in a protected area of the EEPROM memory, the exponent d being supplied only to the processor of the card for its calculations.

Each parameter is made up of a whole number. The length of module N is generally greater than or equal to 512 bits. In practice, each parameter of a triplet (N, e, d) has on average a length of 512 bits. However, the public exhibitor is often shorter in order to speed up the verification of the signature.

We will recall in what follows the progress of an operation of electronic signature, verification, authentication, encryption and decryption of messages in the case of the use of the RSA calculation algorithm.

To obtain the signature S of a message M, by means of a key whose public parameters are (N, e, d), the smart card implements the following calculation:

M ^d modulo N = S. The card then transmits the pair (M, S), that is to say the message accompanied by its signature S. The card transmits or the terminal will read the parameters (N, e) which were used to calculate the signature S of the message M.

The terminal can then verify the signature S by implementing the following calculation: S ^e mod N = M '.

The terminal then checks that M 'is equal to M.

The authentication operation between a card and a verifier consists for the card of proving its identity to the verifier. For this, the verifier sends a random X message to the card; the card calculates the signature A of this message from the parameters (N ', e', d ') of another RSA key by implementing the following relation: X ^of mod N' = A.

The verifier reads or receives the module N 'and the public exponent e' and can then decode such a signed signed random message A to obtain the message X 'by implementing the following relation: A ^e mod N '= X'. Authentication is then carried out by this verifier by comparing X and X '. If the random message X and the decoded message X 'match, the signature is authenticated.

The usurpation of a signature is made impossible by the inaccessibility of the secret exponent d and by the fact that the three parameters (N, e, d) are large binary numbers. The amount of computation and the time necessary to find a secret exponent of solution of the preceding equations is considerable and makes its discovery quite improbable.

For example, on commonly used smart cards, an RSA key has three binary numbers of 512 bits each. Note that a single key then occupies a memory space of 192 bytes.

Another function of the digital keys and the RSA algorithm is to preserve the confidentiality of an exchange of messages between the card and the terminal or the central authority.

Confidentiality is obtained by encryption and decryption of the messages exchanged. The encryption of a message M is obtained by the RSA algorithm, by performing the following binary operation:

M ^e mod N = C. The encryption is therefore obtained by an operation similar to the signature, but then using the public exponent e instead of the secret exponent d. Conversely, decryption can be represented by the following binary operation:

C ^d mod N = M. The card can thus decrypt the encrypted message C using the module N and the secret exponent d of its digital key.

Note that confidentiality is preserved since decryption requires knowledge of the secret exponent d, whose discovery is almost impossible as we have seen.

In general, any triplet (N, e, d) of whole numbers must respect the mathematical condition: e ^• d = 1 mod E (N) where E (N), called "Euler's indicator", denotes the number d 'integers with N and less than N.

In practice, several keys can be installed on a smart card, each key giving access to a different service. The EEPROM memory must then contain as many triples (Nl, el, dl) (N2, e2, d2) ..., (Ni, ei, di) as there are keys.

A drawback of using such algorithms for smart cards, in the case where several keys are provided, is the occupation of a large capacity EEPROM read only memory. According to the previous example, a card having ten RSA keys of 192 bytes, requires an EEPROM read-only memory of approximately 2 kb. Another drawback comes from the large number of keys to be generated due to the large quantity of cards to be programmed, knowing that each card has several keys. Indeed, the computation time is high during the design of the digital keys. The choice of each module N and of each pair of exponents (e, d) of each key requires a series of complex operations to verify mathematical conditions guaranteeing safety and inviolability. An object of the present invention is to optimize the memory space of a smart card and to simplify the operations of signature and authentication.

Another object of the invention is to guarantee the security and inviolability of digital coding.

Surprisingly, these objects are achieved according to the invention by using digital keys (N, el, dl), (N, e2, d2), ..., (N, ei, di) comprising an identical module N, two keys differing in that the pair of exponents (el, dl) of one key is different from the pair of exponents (ei, di) of another key, and by reserving such keys for procedures of signature, verification and / or authentication.

In particular, only one digital key (N, el, dl) among the digital keys (N, el, dl), ..., (N, ei, di) comprising an identical module N can be used for encryption procedures and / or decryption.

According to the invention, provision is made to use a method for signing and / or authenticating electronic messages in which a calculation algorithm uses electronic keys in order to sign the messages and / or in order to authenticate the messages, keys being made up of strings of numeric characters and implanted on smart cards, a key comprising in particular a triplet (N, e, d) of whole numbers:

- a module (N),

- a public exponent (e) and - a secret exponent (d), two keys distinguished in that the triplet (N, e, d) of a key is different from the triplet (N ', e', d ') on the other key, the method being characterized in that several keys (N, e, d), (N, e ', d') have a identical module (N) in particular in order to recognize a user or an identical use of the card, and in that these keys are dedicated to the signature, verification and / or authentication of messages.

According to a variant, the invention is implemented by using a method in which, among the keys (N, e, d), (N, e ', d'), (N, e ", d") having a module ( N) identical, at most one key (N, e, d) is used for encryption and / or decryption of messages.

The invention is preferably carried out with a method in which the signature of a message (M) is preceded by a hashing operation.

Finally, the invention provides for producing an electronic chip card (Cl) comprising a memory containing electronic keys (N, e, d) used to sign and / or authenticate electronic messages, the keys (N, e, d) being consisting of strings of digital characters stored in the memory, a key (N, e, d) comprising in particular a triplet of whole numbers:

- a module (N)

- a public exhibitor and

- a secret exponent (d) two keys (NO, eO, dO), (NI, e3, d3), distinguished in that the triplet (N0, e0, d0) of a key is different from the triplet (Nl, e7 , d7) of the other key, characterized in that a key (N0, e0, d0) of the card comprises a module (NO) identical to the module (NO) of another key (N0, el, dl), (N0, e5, d5) of this card (Cl) or another card (C2).

The realization of the invention will be better understood on reading the description and the drawings which follow; in the accompanying drawings: - Figure 1 shows a diagram of smart cards using a method of signing, verifying and / or authenticating electronic messages according to the invention. Figure 1 schematically illustrates the implementation of several digital keys (NO, eO, dO) ... (NI, e3 ', d3') on two different cards with the method according to one invention.

A first smart card C1 is represented in two parts, a public part PI and a secret part SI, representing respectively the accessible area and the protected area of the read only memory.

EEPROM of the Cl card.

A second smart card C2 is represented in a similar manner with a public part P2 and a secret part S2 representing the accessible and protected areas of its read-only memory.

A first series of parameters NO, NI, eO, eO ', el, el', e2, e2 ', e3, e3' is represented in the public part PI of the card Cl. The first series corresponds to modules and public exhibitors stored in the accessible area of the read-only memory of the first card C1.

A second series of parameters d0, d0 ', dl, dl', d2, d2 ', d3, d3' is represented in the secret part SI of the card Cl. The second series corresponds to secret exponents stored in the protected area of the read-only memory of the first card Cl.

Similarly, on the second map C2, in the public part P2, we see a third series of parameters N0, N1, N2, e4, e4 ', e5, e5', e6, e6 ', e7, e7' and, in the secret part S2, a fourth series of parameters d4, d4 ', d5, d5', d6, d6 ', d7, d7'. The third set of parameters corresponds to modules and public exhibitors stored in the accessible area of the EEPROM read-only memory, the fourth series corresponding to secret exponents stored in the protected area of the EEPROM read-only memory of the second card C2.

These parameters grouped in triples (N, e, d) then form digital keys allowing operations of signature / verification, or authentication or encryption / decryption previously described.

The table below indicates two groups of digital keys formed for example by taking up the series of parameters of the cards C1 and C2 in FIG. 1 and the use of these keys for signature / verification, authentication and encryption operations. / decryption according to the invention.

In the second column titled digital key, we see that the card Cl has six keys (N0, e0, d0), (N0, e0 ', d0'), (N0, el, dl), (NO, el ', dl '), (N0, e2, d2) and (N0, e2', d2 '), having the same module NO. The authentication operations preferably use keys distinct from the signature / verification keys, even if these operations relate to the same service of the card.

These signature / verification and authentication keys can however have the same module. Thus, in the example of the table, it was indicated that among the six keys of the card Cl having the module NO, three keys (pairs of exponents (e0, d0), (el, dl) and (e2, d2) ) are devoted to signature / verification operations, while three other keys (exponent pairs (e0 ', d0') (el ', dl') and (e2 ', d2')) are devoted to authentication.

In general, each key having the common module NO can be associated with the use of a separate service. For example, the three keys (N0, e0, d0), (N0, el, dl) and (N0, e2, d2) can correspond to three bank accounts of the user of the Cl card. Each pair of exhibitors ( e0, d0), (el, dl) and (e2, d2) is then associated with a separate electronic signature corresponding to each of the accounts.

However, as indicated in the last column of the table, it is intended that only one of the six keys comprising an identical NO module, the key (N0, e0, d0) is used for encryption-decryption operations.

Thus, the NO module is not used in two separate encryption-decryption keys. Conditions security and inviolability of encryption operations are then respected.

The second part of the table indicates that card C2 has four keys (N0, e4, d4), (NO, e4 ', d4'), (N0, e5, d5) and (N0, e5 ', d5') including the same module

NO. It can thus be seen that a common module NO can be provided on different cards C1, C2.

However, as the module NO is in this example used by the key (N0, e0, d0) of the card Cl for encryption-decryption operations, no encryption-decryption operation must be performed by the key (N0, e4 , d4) or the key (N0, e4 ', d4') or the key

(N0, e5, d5) or the key (NO, e5 ', d5') of the second card C2. This case illustrates an application of the invention in which an identical module NO is common to several cards. For example, the keys (N0, e0, d0) and (N0, e4, d4) correspond to the same service or the same application provided for these cards. The previous table shows another series of keys (Nl, e3, d3), (NI, e3 ', d3'), (Nl, e6, d6) and (NI, e6 ', d6') having an identical NI module. In this other series, only the key (Nl, e6, d6) attached to the card C2 allows encryption-decryption operations. In short, according to a characteristic of the method according to the invention, several keys comprise an identical module and these keys are dedicated to the signature and / or authentication of messages.

And according to a variant of the method according to the invention, among such keys having an identical module, at most one key is used for encryption and / or decryption of messages. However, to ensure maximum security, precautions are taken in the choice of public exhibitors as detailed below.

First precaution, a mathematical property will limit the choice of public exponents e0, ..., ei relating to an identical module N.

Each of these public exhibitors, denoted ek, must not be a divisor of the least common multiple (in short ppcm) of the other public exhibitors: e _Q , ..., e _k _ ₁ , ek + i, ei relating to the same module.

The realization of this first precaution is in particular obtained by choosing the public exponents eθ, ..., ei among the prime numbers. Indeed, it is mathematically impossible for a prime number to be a divisor of a multiple of other prime numbers.

However, since the calculation of large prime numbers represents a considerable number of calculations, another method can be followed. It consists in choosing the public exhibitors e0, ..., ei randomly among very large numbers. We can then show that the probability of finding the keys is extremely low. This demonstration is beyond the scope of this application. By way of example, however, let us consider the choice of sixteen exponents e0, ..., el6 randomly among the binary numbers of 180 bits; In this case, the probability that one of the ek exponents is a divisor of the ppcm of the others is one in ²⁷⁰ chances. According to another example, the choice of 256 exponents e0, ..., 256 among the binary numbers of 512 bits corresponds to a probability less than 2 ^{~ 166} . This method, although less rigorous, makes it possible to obtain high safety while saving calculation time.

Second precaution, we plan to hash the messages before signing them. For this, we can use a known type hashing algorithm. This complication multiplies the number of operations necessary to discover the digital keys and makes this eventuality quite improbable. Typically hash algorithms are random functions that match binary strings, like a message M, with numbers less than an integer P, in a pseudo-random manner. The result of the hash of the message M is thus a digest of fixed binary size, the size of the integer P.

Advantageously, a SHA hashing algorithm will be used, that is to say in accordance with the "Secure Hash Standard" standard published by the National Institute of Standards and Technology. Note that if we apply a hashing algorithm whose size of the results, that is to say the size of the integer P, is much smaller than the size of the modules NO, NI, ..., it is better to apply a repeated hash. During a repeated hash the message M is truncated into sub-messages m, m ', ... and each sub-message is treated in isolation by the hash algorithm.

For example, if the numeric keys have parameters N, e, d of around 512 bits and the result of the hashing algorithm used gives results having a dimension of 128 or 160 bits, it will be preferable to apply a such repeated hashing.

A preferred embodiment of the invention provides for using a hash function h making call to the public exhibitor e and to the message M, noted in the following form:

H = h (e _. M), H being the result of the hash, ie the hashed message.

Thus the signature operation preceded by the hash follows the following relative:

S = H ^d mod N = (h (e, M)) ^d mod N. Conversely, the verification operation will be carried out by checking the following relation:

S ^e mod N = h (e, M). This hashing procedure has the advantage of giving significant security to the signature and authentication process. A preferred embodiment of the invention also provides for using a complex encryption function f before encryption. We thus obtain a coding of order 2 with two distinct coding methods, which reinforces the security of encryption. Algorithms meeting data encryption standards such as Data Enscryption Standard (DES) algorithms can thus be used to perform a symmetric encryption function.

For example, one can choose an encryption function f, calling on the message M to be encrypted and on a parameter k, and noted in the following form:

F = f (k, M) F being the encrypted message.

Being symmetrical, the function f admits an inverse function, noted f ^-1 , verifying the following relation:

M = f ^_1 (k, M) To make the encryption operation more complex, therefore more secure, the parameter k is preference obtained by hashing the public exponent e, according to the following relation: k ≈ h (e) The encrypted message F is therefore obtained, according to this embodiment, after the following calculation:

F = f (h (e), M) Finally, the encryption-encryption operation corresponds to the following relationship:

C = F ^e mod N = [f (h (e), M)] ^e mod N where C is the encrypted message then encrypted as previously established.

Conversely, the decryption-decryption operation is carried out according to the following calculation:

M = f ^-1 (h (e), C ^d mod N) The demonstration of the safety of the process and the particularly complex calculation of the infinitesimal probabilities of discovery of the keys will not be detailed in the present request.

A final precaution will consist in limiting the number of smart cards and more precisely the number i of keys (N, ei, di) comprising an identical module N.

One of the particularly interesting applications of the method according to the invention is precisely the issue of cards in limited series comprising an identical module N. This module used to recognize for example a group of users or a service used in common.

The use of keys comprising the same module makes it possible to envisage being able to sign on behalf of a group while distinguishing the identity of each signatory with the exhibitor used.

Another application of the method according to the invention is the implantation on the same card of several keys (N, ei, di) having the same module N to recognize the user or allow the recognition of a group of services offered by the same provider.

Finally, a particular application is the identification of cards before their personalization, that is to say before they are handed over to the user with keys specific to the user. In practice, the memories of smart cards are initially loaded with transport keys to test and distinguish them in the middle of a batch. Known cards include an identification number of the card, noted Id.

This identification number Id is for safety transmitted in the following signed form:

S (Id) = Id ^d odulo N (N, e, d) being the parameters of the key called transport key. During personalization, this key is replaced by a new user-specific key.

With the method according to the invention, it will be possible to reuse the module N already stored in the transport key by modifying only the pair of exhibitors (e, d).

An advantage of the invention is the limitation of the memory size used by the digital keys in the EEPROM or ROM memory. It is thus possible to use components of reduced dimensions or to use the unoccupied memory area to store other data.

Another advantage of the method according to the invention and of reducing the exchanges between a card and the terminal or the central authority. Indeed, the terminal can store the module N common to several keys while avoiding recharging it when changing the key used.

Finally, the method according to the invention provides a significant saving in computation time during the generation of the digital keys since the N modules, having been the subject of complex calculations, can be used several times.

Claims

1. Method for signing, verifying and / or authenticating electronic messages in which a calculation algorithm uses electronic keys in order to sign messages and / or in order to authenticate messages, the keys being made up of character strings numerical and installed on smart cards, a key comprising in particular a triplet (N, e, d) of whole numbers:

- a module (N), - a public exhibitor and

- a secret exponent (d), two keys distinguished in that the triplet (N, e, d) of one key is different from the triplet (N ', e', d ') of the other key, the method being characterized in that several keys (N, e, d), (N, e ', d') comprise an identical module (N) in particular in order to recognize a user or an identical use of the card, and in that these keys are dedicated to signing, verifying and / or authenticating messages.

2. Method according to claim 1 wherein an operation of signing a message (M) with a key (N, e, d) consists in calculating a signed message (S) as a function (g (M, N, d) ) of the message (M), of the module (N) and of the secret exponent (d) of the key (N, e, d) and / or in which a verification operation consists in calculating a verified message (M ') as a function (g (S, N, e)) of a signed message (S), of the module (N) and of the public exponent (e) of the key (N, e, d).

3. Method according to claim 1 or 2 wherein an authentication operation of a message (A) with a key (N ', e', d ') consists in transmitting a random message (X), in receiving a message signed random message (A), calculating an authenticated message (X ') as a function (g (A, N', e ')) of the signed random message (A), of the module (N') and of the public exponent ( e ') of the key (N', e ', d') and compare the authenticated message (X ') to the random message (X).

4. Method according to one of the preceding claims, wherein, among the keys (N, e, d), (N, e ', d'), (N, e ", d") having a module (N) identical, at most one key (N, e, d) is used for encryption and / or decryption of messages.

5. Method according to claim 4 in which an operation of encryption of a message (M), with the key (g (M, N, e)) consists in calculating an encrypted message (C) as a function (g (C, N, d)) of the message (M), of the module (N) and of the public exponent (e) of the key (N, e, d) and / or in which a decryption operation with the key (N, e, d) consists in calculating a decrypted message (M) as a function (g (C, N, d)) of an encrypted message (C), of the module (N) and of the secret exponent (d) of the key (N, e, d).

6. Method according to claim 4 or 5, in which an encryption operation is preceded by an encryption and / or in which a decryption operation is followed by a decryption, an encryption or decryption operation implementing a function invertible (f, f ^-1 ) and the public exponent (e).

7. Method according to one of the preceding claims wherein the signature of the message (M) is preceded by a hash operation.

8. Method according to one of the preceding claims, in which, among the public exponents (el, e2, ..., ei) of the keys (N, el, dl), (N, e2, d2), ..., (N, ei, di) comprising an identical module (N), each (ek) of these public exhibitors is not a divisor of the least common multiple of the other public exhibitors (el, e2, ..., ek-l , ek + l, ..., ei) relative to the identical module (N).

9. Chip card implementing a method according to one of the preceding claims.

10. Chip card (Cl) comprising a memory containing electronic keys (N, e, d) used to sign and / or authenticate electronic messages, the keys (N, e, d) consisting of strings of digital characters stored in memory, a key (N, e, d) comprising in particular a triplet of whole numbers:

- a module (N) - a public exhibitor and

- a secret exponent (d) two keys (NO, eO, dO), (NI, e3, d) being distinguished in that the triplet (N0, e0, d0) of a key is different from the triplet (Nl, e3 , d3) of the other key, characterized in that a key (N0, e0, d0) of the card comprises a module (N0) identical to the module (N0) of another key (N0, el, dl), (N0, e5, d5) of this card (Cl) or another card (C2).