Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system

• US 4,995,082 A
• Filed: 02/23/1990
• Issued: 02/19/1991
• Est. Priority Date: 02/24/1989
• Status: Expired due to Term

• Current Assignee: Public Key Partners
• Original Assignee: Claus P. Schnorr
• Inventors: Schnorr, Claus P.
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Cain, David
• Application Number:
  US07/484,127
• Time in Patent Office: 361 Days
• Field of Search: 380/28, 380/30, 380/25, 380/46, 380/23
• US Class Current: 713/169
• 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/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• 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/3247 involving digital signatures

Abstract

In a data exchange system working with processor chip cards, a chip card transmits coded identification data I, v and, proceeding from a random, discrete logarithm r, an exponential value x=2^r (mod p) to the subscriber who, in turn, generates and transmits a random bit sequence e to the chip card. By multiplication of a stored, private key s with the bit sequence e and by addition of the random number r, the chip card calculates a y value and transmits the y value to the subscriber who, in turn, calculates an x value from the information y, v_j and e and checks whether the calculated x value coincides with the transmitted x value. For an electronic signature, a hash value e is first calculated from an x value and from the message m to be signed and a y value is subsequently calculated from the information r, s_j and e. The numbers x and y then yield the electronic signature of the message m.

Claims

1. In a method for mutual identification of subscribers in a data exchange system working with processor chip cards and using identification data coded into the cards by a card-issuing center including subscriber-related public keys and stored in the respective chip cards along with private keys which have a logical relationship to the public keys, whereby random number-dependent check data are exchanged between the subscribers, comprising the steps of:

transmitting from a chip card the coded identification data together with a signature of the center to a subscriber entering into an information exchange with the chip card;

at the subscriber checking the correctness of the coded identification data with reference to known information including a public list or reference to the signature of the center;

forming in the chip card a x value proceeding from a random, discrete logarithm rε

(1, . . . , p-1), where p is a declared prime number modulus, and according to the rule

space="preserve" listing-type="equation">x;

=2.sup.r (mod p);

transmitting the x value to the subscriber;

transmitting from the subscriber a random bit sequence

space="preserve" listing-type="equation">e=(e.sub.l,l. . . ,e.sub.t,k)ε

{0,1}.sup.kt

to the chip card;

multiplying the stored, private key s_j representing a discrete logarithm with a binary number formed from the bits of the random bit sequence e transmitted from the subscriber to the chip card and adding the random number r allocated to the previously-transmitted x value to calculate, at the chip card, a number y according to the rule ##EQU15## transmitting the number y to the subscriber;

at the subscriber, calculating a number x with reference to the number y according to the rule ##EQU16## checking the identity of the chip card user by comparing the calculated number x and the x value previously communicated to the subscriber.

2. A method for generating a signature according to the method of claim 1, wherein:

the step of forming a x value is further defined as generating a random number r within the range of between 1 and the prime number modulus (p-1) and calculating the x value according to the rule

space="preserve" listing-type="equation">x;

=2.sup.r (mod p)

from the generated random number r;

forming a random bit sequence as a function of the x value of a message m and of a declared hash function h according to the rule

space="preserve" listing-type="equation">e;

=h(x,m)ε

{0,1}.sup.kt ;

calculating a y value from the random number r, from the private cipher s_j stored in the chip card and from the random bit sequence e according to the rule ##EQU17## transmitting the message m and the signature formed from the value x and y to the subscriber which is in information exchange with the chip card.

3. A method for generating an abbreviated signature for a message to be transmitted in a data exchange system according to the method of claim 1, and further comprising steps defined as:

at the chip card, generating a random number r lying in the range between 1 and the prime number modulus (p-1);

at the chip card, calculating a x value from the random number r according to the rule

space="preserve" listing-type="equation">x;

=2.sup.r (mod p);

at the chip card, calculating a random bit sequence e as a function of the x value and of the message according to the rule

space="preserve" listing-type="equation">e;

=h(x ,m)ε

(0,l).sup.kt ;

at the chip card, calculating a y value from the random number r, from the secret key s_j and from the random bit sequence e according to the rule ##EQU18## transmitting from the chip card the message m and the signature formed from the values e and y to the subscriber which is information exchange with the chip card.

4. The method of claim 3, and further comprising the steps of:

generating a plurality of the random numbers r and a plurality of x values and storing the same in pairs in the chip card;

employing one of the pairs of stored random numbers r and x values (r.sub.ν

, x.sub.ν

) in an identification procedure and varying the pair in such a manner that a random number r, after use thereof, is combined with a random selection of the remaining, stored random numbers; and

calculating the appertaining x value with the rejuvenated random number and storing the same with the rejuvenated random number r as a rejuvenated pair.

5. The method of claim 4, and further defined as comprising:

storing the plurality of random numbers r_l, . . . r_k and their appertaining x.sub.ν

=2^rν

(mod p) in the chip card; and

rejuvenating the pair (r, x) used in an identification procedure and/or a signature procedure by random selection (r_a(i)), x_a(i)) of the pairs for i=1, . . . , t in accordance with ##EQU19##

6. The method of claim 5, and further defined as:

selecting the prime number modulus p such that the number (p-1) is divisible by a prime number q and by such a selection of the base α

of a discrete logarithm that

space="preserve" listing-type="equation">α

.sup.q =1(mod p), x≠

1(mod p)

holds true; and

calculating discrete logarithms y, r, s_j modulo q such that key components s_j and v_j are in the relationship

space="preserve" listing-type="equation">v.sub.j =α

.sup.-s.sub.j (mod p).

7. The method of claim 6, and further defined as:

selecting the secret key s_j and the random numbers (r) such that the bit lengths of the numbers s_j, r and y are shorter than the length of the prime number modulus p.

8. The method of claim 6, and further defined as:

selecting finite groups for the formation of the discrete logarithm instead of the finite groups that arise on the basis of residual class modulo p.

9. The method of claim 8, and further defined as:

selecting one from the groups consisting of the Z_n^*, the group of invertible residue classes modulo q composite number r, a group of units of a finite field, and an elliptic curve over a finite field as a finite group.

10. A method for the verification of a signature (x,y) generated according to the method of claim 2 at the subscriber receiving the signed message m, comprising the steps of:

calculating a random bit sequence e from the message m and from the x value of the signature according to the rule

space="preserve" listing-type="equation">e;

=h(x,m)ε

{0,1}.sup.kt ;

calculating an x value according to the rule ##EQU20## from the random bit sequence e, from the public cipher v and from the y value of the signature; and

comparing the calculated x value with the x value of the signature.

11. A method for verifying an abbreviated signature generated according to the method of claim 3 at the subscriber receiving the signed message m comprising the steps of:

calculating a number x from the transmitted message m and from the signature (e, y) according to the rule ##EQU21## checking the value e of the signature for coincidence with the value h (x , m).