Process for generating DSA signatures with low-cost portable apparatuses

• US 5,625,695 A
• Filed: 11/30/1994
• Issued: 04/29/1997
• Est. Priority Date: 12/02/1993
• Status: Expired due to Term

• Current Assignee: Gemalto SA (Thales SA)
• Original Assignee: Gemplus International SA (Thales SA)
• Inventors: Naccache, David, M'Raihi, David
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Laufer, Pinchus M.
• Application Number:
  US08/347,570
• Time in Patent Office: 881 Days
• Field of Search: 380/25, 380/29, 380/30, 380/28, 380/23, 380/49
• US Class Current: 380/28
• 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 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

The invention relates to a process for generating digital signatures from portable apparatuses (A1, A2, . . . Ai . . . An) of the microprocessor-based card type, including means for computation, communication and retention of data, which means comprise at least one electrically programmable non-volatile memory, consisting in preparing enciphered data constituting coupons and loading these coupons into the non-volatile memories so as later to use these coupons in order to sign a message sent by a verifier device. According to the process, the preparation of the coupons is carried out by a certified central authority B or by the card itself.

Claims

1. Process for generating digital signatures with a portable apparatus of the microprocessor-based integrated-circuit card type, the portable apparatus including a microprocessor, a communication device, and an electrically programmable non-volatile memory, the method comprising the steps of

preparing a plurality of original coupons, the plurality of original coupons being prepared externally to the portable apparatus, the plurality of original coupons being formed of precomputed data useful in the generation of the digital signatures, wherein different coupons correspond to different individual signatures such that the generation of an individual signature involves the use of only a single coupon, and wherein the plurality of original coupons each correspond to an intermediate step in the calculation of the different individual signatures;

loading the plurality of original coupons into the portable apparatus after the plurality of original coupons have been prepared;

using the plurality of original coupons to generate the digital signatures; and

periodically reloading the apparatus with pluralities of additional coupons after the apparatus has been issued to an end user and after the plurality of original coupons has been substantially exhausted, each performance of the reloading step comprising the steps of

establishing a connection between a signature verification device and the apparatus, the signature verification device being formed of one of a verifier and a certified central authority,

preparing a plurality of additional coupons,

enciphering the plurality of additional coupons, and

sending the plurality of additional coupons from the signature verification device to the apparatus in enciphered format, the plurality of additional coupons enabling the apparatus to generate a plurality of additional digital signatures.

2. Process according to claim 1, wherein the digital signatures are generated using the DSA algorithm, and

wherein the step of preparing a plurality of additional coupons includes the steps of

drawing a random number J of Z1 bytes, and expanding the number J into a Z2-byte number i,

computing ##EQU21## mod q, and computing r=(g^k mod p) mod q, and

wherein the step of enciphering the plurality of additional coupons includes the step of computing c=DES (card_-- key, J), and

wherein the step of sending the plurality of additional coupons from the signature verification device to the apparatus includes the steps of

the signature verification device sending c and r to the apparatus,

the apparatus deciphering the plurality of additional coupons by computing J=DES^-1 (card_-- key, c), and the apparatus saving J and r in the non-volatile memory, c and r thus forming the coupon in enciphered format and J and r forming the coupon in deciphered format.

3. Process according to claim 2 wherein the c and r sending step is repeated t times so as to culminate with the saving of t different pairs {J, r} in the non-volatile memory.

4. Process according to claim 3 wherein the card generates the DSA signature of a message m by performing the following operations:

a. extracting J and r from the non-volatile memory,

b. expanding J into a Z2-byte number i,

c. computing s=(m+x r) i mod q, x being the secret DSS (Digital Signal Standard) key held by the portable apparatus,

d. sending s and r to the verifier, and

e. invalidating the pair {J, r}, including deleting it from the non-volatile memory.

5. Process according to claim 2, wherein the portable apparatus is a card, and wherein the parameter card_-- key is derived directly from the secret DSS (Digital Signal Standard) key x held by the card.

6. Process according to claim 2, wherein in order to reduce the time for generating a DSA signature with an apparatus provided with a cryptographic operator, the process further comprises the step of deterring computation of the term r=(g^k mod p) mod q to the moment of verification of the digital signature by the signature verification device, thus enabling r to be computed during the signature verification device'"'"'s work time.

7. Process according to claim 6, further comprising the following steps performed by the portable apparatus:

extracting J and r from the non-volatile memory,

expanding the J to obtain i on Z2 bytes,

receiving the message m from the signature verification device,

computing s=(m+x r) i mod q,

sending s and r to the verifier and

invalidating the pair {r, J}, deleting it from the non-volatile memory,

and while the signature verification device is verifying the validity of the pair {r, s}, drawing a new random number J of Z1 bytes and expanding the number J so as to obtain a number i of Z2 bytes, back-computing ##EQU22## mod q, computing r=(g^k mod p) nod q and overwriting the non-volatile memory with the new coupon {r, J}.

8. Process according to claim 1, wherein the digital signatures are generated using the DSA digital signature algorithm, and wherein the exchanging of data between the apparatus and the signature verification device includes the following steps:

the apparatus drawing a random number J of Z1 bytes, and sending the number J to the signature verification device,

the signature verification device computing ##EQU23## mod q and r=(g^k mod p) mod q, SHA being the secure Hash Algorithm, and x being the secret key held by the portable apparatus, and

sending r to the apparatus which records J and r in the non-volatile memory.

9. Process according to claim 8, wherein the apparatus generates the DSA signature of a message m by performing the following operations:

a. extracting J and r from the non-volatile memory,

b. computing s=(m+x r) SHA (x, J) mod q,

c. sending r and s to the signature verification device, and

d. invalidating the pair {J, r}, including deleting it from the non-volatile memory.

10. Process according to claim 1 wherein, during the enciphering step, the plurality of additional coupons are enciphered using an exclusive-OR with a secret constant.

11. Process for generating digital signatures according to claim 1, wherein the apparatus generates a DSA signature of a message m by performing at least the following operations after (1) n coupons r₁, . . . , r_n are sent to the portable apparatus and stored in the non-volatile memory and (2) after a random number J is generated by the portable apparatus and stored in the non-volatile memory:

a. extracting J and an r_b from the non-volatile memory,

b. computing s=(m+x r_b) SHA (x,J,b) mod q, SHA being the Secure Hash Algorithm,

c. sending r_b and s to the verifier, and

d. invalidating the coupon r_b, including deleting it from the non-volatile memory.

12. Process for generating digital signatures according to claim 1, wherein the apparatus generates a Schnorr signature of a message m by performing the following operations after (1) n coupons x₁, . . . , x_b are sent to the portable apparatus and stored in the non-volatile memory and (2) after a random number J is generated by the portable apparatus and stored in the non-volatile memory:

a. extracting J and x_b from the non-volatile memory,

b. computing c=SHA (m, s) mod q, SHA being the Secure Hash Algorithm,

c. computing y=SHA (s, J, b)+se mod q,

d. sending x_b and y to the verifier, and

e. invalidating the coupon {X_b }, including deleting it from the non-volatile memory.

13. Process for generating digital signatures according to claim 1, wherein the preparation of the enciphered data constituting the coupons furthermore includes the following step:

for a set of n coupons, computing a certificate (R, S) on the basis of a DSS (Digital Signal Standard) algorithm and of control data such that (R,S)=DSS (SHA (Control_-- Datum, r₁, r₂, . . . , r_n)), SHA being the Secure Hash Algorithm.

14. Process for generating digital signatures according to claim 13, wherein the signature verification device computes the certificate for a set of n coupons, and wherein the generation and reloading of the coupons then includes the following steps:

1. the apparatus drawing a random number J of Z1 bytes (8 bytes) and recording it in the non-volatile memory,

2. the apparatus sending J to the signature verification device,

3. the signature verification device computing the k_i for i=1 to n, with n being the number of coupons to be loaded, and the corresponding r_i, as follows;

For i=1 to n;

##EQU24##

17. Process for generating digital signatures according to claim 14, wherein the signing of a message m by the apparatus includes the following steps:

1. the apparatus extracting J and an r_i from the non-volatile memory,

2. the apparatus receiving the message m from the signature verification device,

3. the apparatus computing s=(m+x r_i) SHA (x,J,i) mod q, x being the secret key of the portable apparatus, and SHA being the Secure Hash Algorithm,

4. the apparatus sending s, r_i, the Certificate and the data required for its verification to the signature verification device and invalidating r_i, deleting it from the non-volatile memory.

18. Process for generating digital signatures according to claim 1, wherein there are a plurality of apparatuses, and wherein the apparatuses are one of chip cards, PCMCIA cards, badges, and contactless cards.

19. Process for generating digital signatures according to claim 1, wherein communication between the apparatus and the signature verification device is carried out by exchanging electronic signals.

20. Process for generating digital signatures according to claim 1, wherein communication between the apparatus and the signature verification device is carried out by exchanging one of radio waves and infrared signals.

15. r_i =(g^k i mod p) mod q 4. the signature verification device computing the Certificate (R, S) corresponding to the n coupons:

X being the secret key of the signature verification device

1. the signature verification device generating a random number K,

2. M=Hash (Control_-- Datum, r₁, r₂, . . . , r_n),

3. R=(g^k mod p) mod q, ##EQU25##

16. 5. the signature verification device sending the Certificate (R, S), the control data and the r_i to the apparatus, andthe apparatus recording the Certificate (R,S), the control data and the r_i in the non-volatile memory.