Method for the generation of electronic signatures, in particular for smart cards

• US 5,910,989 A
• Filed: 03/06/1997
• Issued: 06/08/1999
• Est. Priority Date: 04/20/1995
• Status: Expired due to Fees

• Current Assignee: Gemplus (Thales SA)
• Original Assignee: Gemplus (Thales SA)
• Inventors: Naccache, David
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/765,483
• Time in Patent Office: 824 Days
• Field of Search: 380/23, 380/24, 380/25, 380/29, 380/30, 380/49, 380/9, 380/50, 380/59, 380/28
• US Class Current: 713/173
• 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/40975 using encryption therefor
• 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 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Processes for generating digital signatures for electronic messages. Modifying signature-generating algorithms, such as DSAs (Digital Signature Algorithms), in order to enable smart cards with reduced calculation and storage resources to produce digital signatures with a high degree of security in spite of their reduced resources. The signature-checking terminal sends a random number a and measures the time taken by the card to send back a signal s using this random number. If the time is greater than a given duration, the signature is rejected even if the check of its authenticity is positive. In addition, part of the signature (the part which does not use the secret card key but only the public algorithm parameters) is precalculated and stored in the card in the form of signature portions produced by a compression function such that they are short. Only the second part of the signature has to be calculated by the card. The calculations to be made are simple so that the card does not require extensive calculation and memory resources.

Claims

1. An electronic signature method, comprising:

(A) generating a digital signature, the digital signature being capable of certifying the integrity of a signed message and the identity of a signer unit which signs the signed message, the generating step being performed by the signer unit, and the generating step including computing the signature using the signed message and a random data element sent to the signer unit by a verifier unit, and

(B) checking the signature, the checking step being performed by the verifier unit, and the checking step including

(1) ascertaining that a mathematical condition which uses the signature sent and the random data element is fulfilled, and

(2) timing the period that elapses between an instant when the random data element is sent by the verifier unit to the signer unit and the instant when the signature using this data element returns to the verifier unit after computation by the signer unit, and

wherein the signature is accepted if the time elapsed is below a defined threshold and if the mathematical condition is fulfilled.

2. A method according to claim 1,

wherein the computing step and the checking step are performed on the basis of an algorithm of the type in which the signature generation produces two values {r, s}, s being computed from r and a secret key x, and in which the checking of the signature {r, s} consists of the checking of an equality v=f(r, s)=r between r and a function f of r and of s, and

wherein the function f is chosen to be sufficiently complex so that the period of search for a value s on the basis of the equality when there is no knowledge of the secret key is far greater, even if it is performed by a powerful computer, than the period of computation and transmission by the signer unit of the value s on the basis of r and of the secret key, this being the case even if the signer unit uses a low-power microprocessor.

3. A method according to claim 2, wherein the function f(r, s) also uses the message to be signed.

4. A method according to claim 2, wherein the function f comprises mathematical computations followed by a complex hash function H achieving both a slowing down of the obtaining of a computation result and a compression of length of the computation result.

5. A method according to claim 4, wherein the first signature value r is established by other mathematical computations, followed by the same complex hash function H.

6. A method according to claim 1,

wherein the signature sent by the signer comprises at least one signature coupon r_i and one signature complement s that is computed on the basis of the signature coupon r_i and of a secret key x of the signer unit,

wherein the checking step includes using a checking formula of the type v=f(r_i, s)=r_i ;

and wherein

a. the signature coupon is established in advance by a certified authority, in two steps;

i) the computation of a number represented by a long binary string, using a mathematical formula which uses big binary numbers, and

ii) the modification of the result of the computation by a complex compression function greatly reducing the length of this result,

b. a series of different signature coupons of small length are thus prepared in advance and stored in the signer unit,

c. the generating step comprises sending a signature coupon r_i and a signature complement s computed on the basis of at least r_i and x to the verifier unit,

d. the checking step comprises performing a mathematical computation followed by the same complex compression function as the one used to prepare the signature coupon, and comparing the result with the signature coupon for the signature checking.

15. A method according to claim 1, wherein the digital signature is computed according to the DSA algorithm.

16. A method according to claim 1, wherein the signer unit is a smart card, such that the generating step is performed by the smart card.

17. A method according to claim 1,

wherein the computing step and the checking step are performed on the basis of an algorithm of the type in which the signature generation produces two values {r, s}, s being computed from r and a secret key x, and in which the checking of the signature {r, s} consists of the checking of an equality v=f(r, s)=r between r and a function f of r and of s,

wherein, during the computing step, the value s is computed, and

wherein the value r is provided to the signer unit prior to the computing step in the form of a signature coupon.

7. An electronic signature method, comprising:

(A) generating a digital signature, the digital signature being capable of certifying the integrity of a signed message and the identify of a signer unit which signs the signed message, the generating step being performed by the signer unit, and the generating step including computing the signature using the signed message, and

(B) checking the signature, the checking step being performed by the verifier unit, and the checking step including ascertaining that a mathematical condition which takes into account the signature sent is fulfilled, the signature being accepted if the mathematical condition is fulfilled;

wherein the signature sent by the signer unit comprises at least one signature coupon r_i and one signature complement s that is computed on the basis of the signature coupon r_i and of a secret key x of the signer unit,

wherein the checking step includes using a checking formula of the type v=f(r_i, s)=r_i ;

and wherein

a. the signature coupon is established in advance by a certified authority, in two steps;

i) the computation of a number represented by a long binary string, using a mathematical formula which uses big binary numbers,

ii) and the modification of the result of the computation by a complex compression function greatly reducing the length of this result,

b. a series of different signature coupons of small length are thus prepared in advance and stored in the signer unit,

c. the generation step comprises sending a signature coupon r_i and a signature complement s computed on the basis of at least r_i and x to the verifier unit,

d. the checking step comprises performing a mathematical computation followed by the same complex compression function as the one used to prepare the signature coupon, and comparing the result with the signature coupon for the signature checking.

8. A method according to claim 7, wherein the compression function is a complex hash function.

9. A method according to claim 7, wherein the computation of the coupon is performed on the basis of a random element J generated at the outset by the signer unit and stored in the signer unit to be reused when the coupon is used to establish a signature.

10. A method according to claim 7, further comprising the following steps, which are performed by the verifier unit:

(a) sending a random element a to the signer unit,

(b) activating a timer, the timer being activated approximately when the verifier unit sends the random element a to the signer unit,

(c) measuring the time taken by the signer unit to send back the signature complement s computed on the basis of at least the random element a and the secret key x of the signer unit;

(d) carrying out a signature checking computation on the basis of at least the signature s and the random element a, and

(e) accepting the signature if the signature checking computation determines that a predetermined condition is fulfilled and if the time taken by the signer unit to send back the signature s using the random element is below a predetermined threshold.

11. A method according to claim 7, wherein the signature complement s is established on the basis of a hash function SHA(m, a) of a message to be signed and of this random element a, and in that the same hash function is used for the signature checking.

12. A method according to claim 7, wherein the signature complement s is established by a computation which uses a random element J stored in the signer unit and having been used to establish the signature coupon.

13. A method according to claim 12, wherein the computation uses the random element J stored in the signer unit also brings into play a hash function SHA (x, J, i) pertaining at least to this random element J and to index i representing the number of the coupon used, this same hash function SHA (x, J, i) having been used previously during the computation of the long binary string provided for in the computation of the corresponding coupon.

14. A method according to claim 7, wherein the signature complement s is established by a computation which uses a hash function, the same hash function of the coupon being used for the signature checking.

18. A method for the generation of digital signatures of messages by a signer unit and for the checking of these signatures by a verifier unit, the signer unit comprising a device that computes, communicates and retains data elements, the device comprising at least one electrically programmable non-volatile memory, according to which there are prepared enciphered data elements constituting signature coupons that are loaded into the non-volatile memory and that are used by the signer unit to sign messages, chiefly characterized in that:

the coupons are compressed by the application of a compression function H, also called a hash function, by a certified authority before being loaded into the memory, and in that this method comprises the following exchanges;

a message m is transmitted and this message must be certified by a signature,

the signer unit sends a coupon r_i to the verifier unit,

the verifier unit sends a random number a to the signer unit and activates a timer,

the signer unit computes the signature s of the message and sends it to the verifier unit,

the verifier unit stops the timer and ascertains that the signature has been obtained through the secret key held in the signer unit and the coupon r_i received, this checking is done by checking the equality v=f(r_i, s, m)=r_i ;

the verifier unit accepts the signature if the condition of checking v=r_i is fulfilled and if the measured time does not exceed an allocated predetermined period.

19. An electronic signature method comprising:

(A) computing a plurality of signature coupons, each of the plurality of signature coupons being computed on the basis of a number which is regenerated for each new signature and on the basis of known parameters of the signature algorithm;

(B) providing the chip card with the plurality of signature coupons;

(C) generating a digital signature, the digital signature being capable of certifying the integrity of a signed message and the identity of a chip card which operates as a signer unit and which signs the signed message, and the generating step including computing the signature using the signed message, a random data element sent to the chip card by a verifier unit, a secret key, and one of the plurality of signature coupons, and

(D) checking the signature, the checking step being performed by the verifier unit, and the checking step including

(1) ascertaining that a mathematical condition which uses the signature sent and the random data element is fulfilled, and

(2) timing the period that elapses between an instant when the random data element is sent by the verifier unit to the chip card and the instant when the signature using this data element returns to the verifier unit after computation by the chip card, and

wherein the signature is accepted if the time elapsed is below a defined threshold and if the mathematical condition is fulfilled.

20. A method according to claim 19,

wherein the computing step and the checking step are performed on the basis of an algorithm of the type in which the signature generation produces two values {r, s}, s being computed from r and a secret key x, and in which the checking of the signature {r, s} consists of the checking of an equality v=f(r, s)=r between r and a function f of r and of s,

wherein, during the computing step, the value s is computed,

wherein the value r is one of the plurality of coupons, and

wherein the function f is chosen to be sufficiently complex so that the period of search for a value s on the basis of the equality when there is no knowledge of the secret key is far greater, even if it is performed by a powerful computer, than the period of computation and transmission by the signer unit of the value s on the basis of r and of the secret key, this being the case even if the signer unit uses a low-power microprocessor.