US4995082A — Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
United States Patent (19) 11 Patent Number: 4,995,082
Schnorr 45 Date of Patent: Feb. 19, 1991
(54) METHOD FOR IDENTIFYING on Public-Key Techniques", I.E.E.E., Communca
SUBSCRIBERS AND FOR GENERATING tions, vol. 25, No. 7, 1987, pp. 73-79.
AND VERIFYING ELECTRONIC Beth, T., "Efficient Zero-Knowledge Identification
SIGNATURES IN A DATA EXCHANGE Scheme for Smart Cards", Advances in Cryptology--
SYSTEM Eurocrypt, '80, pp. 77-84.
76 Inventor: Claus P. Schnorr, Frankfurterstr. 81,
6350 Bad Nauheim, Fed. Rep. of Primary Examiner-Thomas H. Tarcza
Germany Assistant Examiner-David Cain
21). Appl. No.: 484,127 Attorney, Agent, or Firm-Hill, Van Santen, Steadman &
Simpson
22 Filed: Feb. 23, 1990
30 Foreign Application Priority Data 57 ABSTRACT
Feb. 24, 1989 (EP) European Pat. Off. ........ 89.103290.6 In a data exchange system working with processor chip
51 Int. C. ............................................... H04K 1/00 cards, a chip card transmits coded identification data I,
52 U.S. C. ........................................ 380/23: 380/30; v and, proceeding from a random, discrete logarithm r,
380/25; 380/46 an exponential value x = 2 (mod p) to the subscriber
58) Field of Search ....................... 380/28, 30, 25, 46, who, in turn, generates and transmits a random bit se
380/23 quence e to the chip card. By multiplication of a stored,
56 References Cited private keys with the bit sequence e and by addition of
U.S. PATENT DOCUMENTS
the random number r, the chip card calculates a y value
and transmits they value to the subscriber who, in turn,
4,225,935 9/1980 Zscheile et al. ...................... 380/28 calculates an x value from the information y, vi and e
4,351,982 9/1982 Miller et al. ...... ... 380/30 and checks whether the calculated x value coincides
4,405,828 9/1983 Rivest et al. .......................... 380/30 with the transmitted x value. For an electronic signa
4,514,592 4/1985 Miyaguchi. ... 380/28 ture, a hash value e is first calculated from an x value
4,658,094 4/1987 Clark ..................................... 380/30
4,748,668 5/1988 Shamir et al. ......................... 380/28 and from the message m to be signed and a y value is
4,759,063 7/1988 Chaum .......... ... 380/28 subsequently calculated from the information r, sand e.
4,759,064 7/1988 Chaum ...... 380/28 The numbers x and y then yield the electronic signature
4,876,716 10/1989 Okamoto .............................. 380/30 of the message m.
OTHER PUBLICATIONS
Omura, J. K., "A Computer Dial Access System Based 11 Claims, 3 Drawing Sheets
SELECT r
CALCULATE x :- 2 (mod p)
SELECT e
CALCULATE CHECK, WHETHER
k t i
k is 2 jFl vi=1". (mod p)
U.S. Patent Feb. 19, 1991 Sheet 1 of 3 4,995,082
103313$
103J13$
U.S. Patent Feb. 19, 1991 Sheet 2 of 3 4,995,082
pou(du)
I
X.
J(IuWTi=:q•I“JIxW)
U.S. Patent 4,995,082
4,995,082
1. 2
ture are therefore invariably linked via the key algo
METHOD FOR DENTIFYING SUBSCRIBERS rithm.
AND FOR GENERATING AND VERIFYING The utilization of modern cryptographic equipment is
ELECTRONIC SIGNATURES IN A DATA intimately connected to the introduction as what are
EXCHANGE SYSTEM referred to as multi-functional processor chip cards.
The processor chip card not only enables versatile ap
BACKGROUND OF THE INVENTION plications but is also employed for accepting the neces
1. Field of the Invention sary security components (secret key and cryptoal
The present invention relates to a method for identi 10 gorithm)
user and a
in order to guarantee an identification of the
reliable authentication of the card and of the
fying subscribers and for generating and verifying elec
tronic signatures in a data exchange system working message exchanged.
Presently known algorithms for electronic signatures,
with processor chip cards, using identification data particularly
coded in a center with respective subscriber-related U.S. Pat. No.the4,405,829),
RSA algorithm (in this connection see
fully incorporated herein by
known ciphers and stored in the respective chip card 15 this reference or the algorithm
and with secret ciphers having a logical relationship to and A. Shamir (European patentdeveloped by A. Fiat
application Ser. No.
the known ciphers, whereby random number-depend 0,252,499) require either a high memory
ent check data are mutually exchanged between the far as they can be accommodated at all outlay in the
or, inso
chip be
subscribers.
2. Description of the Prior Art cause of extensive and complicated arithmetic opera
Important prerequisites for data security in modern tions, particularly, multiplications, require a great deal
20
communication systems are: of time, so that they are only conditionally suitable for
(a) the mutual identification of the communicating utilization in chip cards.
partners participating in the system; SUMMARY OF THE INVENTION
(b) the authentication of the transmitted and stored 25
data; It is therefore an object of the invention to provide
methods for mutual identification of subscribers of data
(c) the coding of the transmitted and stored data; and exchange systems and for generating signatures that,
(d) checking the authorship of the transmitted data.
As is known, a high degree of data security can only given essentially the same security guarantees, enable
be achieved by utilizing cryptographic methods that 30 shorter
tions, in
run times due to more simple arithmetic opera
comparison to known cryptographic methods.
enable an identification and authenticity check of mes
sages, subscribers and equipment beyond all doubt. The above object is achieved, according to the pres
What is generally understood by cryptography is a subscribersent invention, in a method for mutual identification of
coding of the data for secrecy purposes. In addition to processor chip in a data exchange system working with
this doubtlessly-important crypto function, however, 35 cards, utilizing identification data coded
other functions, particularly checking the authenticity in a center with respective subscriber-related known
and authorship or generating electronic signatures are secretkeys and stored in the respective chip card and with
gaining increasing significance. keys having a logical relationship to these known
Symmetrical or asymmetrical coding algorithms can keys, whereby random number-dependent check data
be employed for realizing cryptographic functions. are mutually exchanged between the subscribers, and is
Given a symmetrical algorithm, for example the DES particularly characterized in that the chip card sends
algorithm (data incryption standard), identical keys are athesignature
coded identification data, potentially together with
of the center, to the subscribers entering into
employed for coding and decoding. Symmetrical cryp
tosystems are particularly suitable when larger data sets an information exchange with the chip card, this sub
scriber checking the correctness of the coded identifica
have to be transmitted at a high rate. By contrast, disad 45 tion
vantages derive due to a relatively difficult cryptoman ence data with reference to a known list or with refer
agement because the transmitter and the receiver must to the signature of the center, then proceeding
have the same key and a reliable channel is required for from a random, discrete algorithm re(l, . . . , p - 1),
where p is a declared prime number modulus, the chip
the transmission of the key respectively employed.
In asymmetrical cryptosystems, different ciphers are SO card forms an x value according to the rule x:=2(mod
employed for coding and decoding, such that, for exam p) and sends this x value to the subscriber, after which
ple, the key for coding is known and the key for decod the subscriber sends a random bit sequence ess (eixi. . .
ing is secret. The latter is only known to the receiver. , etc.k)e(0,1}k to the chip card, and by multiplication of
On asymmetrical cryptosystems, for example, the RSA the stored secret key si that likewise represents a dis
algorithm named after the inventors Rivest Shamir and 55 crete
bits of
logarithm with a binary number formed from the
the random bit sequence e transmitted from the
Adlemann that requires a comparatively high techno
logical outlay and correspondingly long run times de subscriber to the chip card and by addition of the ran
pendent on the length of the cipher employed but that dom number r allocated to the previously-transmitted x
satisfies high security requirements on the basis of the value, the chip card calculates a number y according to
special cryptosystem. The asymmetrical cryptosystem the rule
is ideally suited for assigning a message to be transmit
ted. The message to be signed is thereby coded with the t
s; S, e, , 2-l
(mod p-1)
secret key of the signee and can be decoded by anyone y - 'd
that knows the public key. This "electronic signature'
not only contains the personal feature (possession of 65 and transmits the number y to the subscriber, then with
private or secret key of the signee but also involves the reference to the number y transmitted to the subscriber,
signed text, with the consequence that the receiver the subscriber calculates a number x according to the
recognizes any change in the text. Message and signa rule
4,995,082
4.
by a random selection (rat), Xa(i)) of the pairs for i=1,.
R (mod p) ..,t
t
x = 2 j-r 1 yi =Sei 2
(mod p-1)
ge"gld -- i ra(ii) 2.
and checks the identity of the chip card user on the basis
of a comparison between the calculated number x and (mod p)
the x value previously communicated to the subscriber. x". = ld xico.
According to another feature of the invention, the
method is particularly characterized in that the chip O
card calculates a x value according to the rule According to another feature of the invention, a
x:=27(mod p) from a random number r generated in the method is particularly characterized by such a selection
chip card and lying in the range between l and the of the prime number modulus p that (p-1) is divisible
prime number modulus (p-1), that the chip card calcu by a prime number q and by such a selection of the base
lates a random bit sequence as a function of the x value 15 a of the discrete logarithm that
of the message m and of a declared hash function h
according to the rule e:=h(x, m)”{0,1}k, that the chip
card calculates a y value from the random number r,
from the secret ciphers sistored in the chip card and applies, and in that the discrete logarithms y, r, sj are
from the random bit sequence e according to the rule 20 calculated modulo q, and in that the key components si
and v are in the relationship vi=aj(mod p). Then a
k t
r = r -- is si S. ei 2-l
(mod p-1) plays the role of the base 2 above.
y 11 it According to another feature of the invention, a
method is particularly characterized by such a selection
and that the chip card sends the message m and the 25 of the secret
signature formed from the value x and y to the sub key si and of the random numbers r that the bit
scriber in message communication with the chip card. lengths of the numbers si, r and y are shorter than the
According to another feature of the invention meth length of the prime number modulus p.
ods can be accelerated by discrete logarithms calculated According to another feature of the invention, a
in a preliminary process and intermediately stored, 30 method is particularly characterized in that other finite
whereby values once employed are combined in a ran groups are employed for the formation of discrete loga
dom fashion with other discrete logarithms in a rejuve rithm instead of the finite groups that arise on the basis
nation process. This is exemplified by a method of the of residual class formation modulo p.
type set forth above which is particularly characterized According to another feature of the invention, a
in that a plurality of random numbers r, and respec 35 method is particularly characterized in that a group of
tively appertaining x values calculated in a preliminary units Zn" of the invertible residue classes modula a com
process are stored in pairs in the chip card, in that the posite number n, a group of units of a finite body, an
pair (r, x) employed in an identification procedure and
/or signature procedure is varied in such a manner that elliptical curve over a finite field or the like are pro
vided as a finite group. Then this finite group plays the
a random number r, after use thereof, is combined with
a random selection of the remaining stored random role of the group Z'.
According to another feature of the invention, a
numbers, and in that the rejuvenated random number method for verifying
calculates the appertaining x value and is stored and/or ated according to theanthird-mentioned
abbreviated signature gener
used together with the rejuvenated randon number r as subscriber receiving the signed message feature
m, is
at the
particu
a rejuvenated pair. 45
A method for verification of a signature generated larlya
characterized in that:
number x is calculated from the transmitted message
according to the second-mentioned feature is particu
larly characterized, with respect to the subscriber re m and from the signature (e, y) according to the rule
ceiving the signed message m, in that:
a random bit sequence e is calculated from the mes 50 k t
(mod p)
sage m and from the x value of the signature according x = 2 j=r yixis
ei 2-1,
to the rule e:=h(x,m)e(0,i}k,
that an x value according to the rule
and that a check is carried out to see whether the e
k (mod p) 55 value of the signature coincides with the value h (x, m).
x = 2y at vi i ei 2 The problem to be solved in practicing the present
j= i is invention is comprised in the difficulty of calculating
is calculated from the random bit sequence e, from the the discrete logarithm. Other, known asymmetrical
public key v and from they value of the signature and cryptomethods are also constructed on this foundation
is checked to see whether the calculated x value coin 60 (for example reference may be taken to T. ElGamal, "A
cides with the x value of the signature. Public Key Cryptosystem and a Signature Scheme
With respect to rejuvenation, according to another Based on Discrete Logarithms", IEEE Transactions on
feature of the invention, a method is particularly char Information Theory, Vol. 31, 1985, pp. 469-472; D.
acterized in that a plurality of random numbers r1, ..., Chaum, J. H. Evertse, J. van de Graaf, "An Improved
rk and their appertaining x values, Xu = 2 (mod p), are 65 Protocol for Demonstrating Possession of Discrete
stored in the chip card, and in that the pair of numbers Logarithms and some Generalizations", Proceedings of
(r, x) used in an identification procedure and/or signa Eurocrypt '87, Lecture Notes in Computer Science 304,
ture procedure is rejuvenated in the following manner (1988), pp. 127-141; T. Beth, "A Fiat-Shamir-like Au
4,995,082
5 6
thentication Protocol for the ELGAMAL Scheme", ship between the public key v and the identification
Eurocrypt '88 Abstracts, pp. 41-47). Compared to the string I and monitors the signature of the center in this
known cryptomethods, the present invention has the manner. The public key v = (vt. . . VR) has a logical
advantage that the arithmetic operations can be com relationship to the secret key s-(si...sk) and is defined
paratively more simply executed in the chip card. This 2S
occurs particularly due to the set preliminary process.
This preliminary process can also be combined with the vi=2 f(mod p) for j= 1,..., k,
mentioned cryptosystems of ELGAMAL, CHAUM where p is a prime number that is at least 512 bits long.
EVERTSE-van de GRAAF and BETH. In addition, As soon as the secret key s is selected, the correspond
especially short signatures can be generated in practic O ing public key v can be easily calculated. The inverse
ing the present invention. process-calculating the secret key s from the public
BRIEF DESCRIPTION OF THE DRAWINGS key v-13 cannot be implemented because the calculation
of the discrete logarithm modulo p for such large prime
Other objects, features and advantages of the inven numbers p is beyond the range of present computers and
tion, its organization, construction and operation will be 15 algorithms. The components of the secret cipher is the
best understood from the following detailed descrip discrete logarithm modulo p of fiti, i.e.
tion, taken in conjunction with the accompanying
drawings, on which: sj= -log2 (mod p- 1) for j= 1,...,k.
FIG. 1 is a block diagram of the identification of a
subscriber in accordance with the present invention; 20 All discrete logarithms refer to the group ZZ" (the
FIG. 2 is an illustration of the method steps of the multiplicative group modulop) and, insofar as not oth
invention in the generating of a signature of a message erwise noted, to the base 2. Since the order of the group
to be transmitted; Z' is p-1, the discrete algorithm assumes the value 1,
FIG. 3 is a diagram of the steps for checking a signa 2, ...,p.-1. Instead of the finite groups that arise due to
ture generated according to FIG. 2; 25 residual formation modulo p, other finite groups can
FIG. 4 is a diagram of the method steps of the present also be employed for the formation of the discrete loga
invention in generating an abbreviated signature; and
FIG. 5 is a diagram of the steps used in the checking rithm,ible
such as, for example, the group of Zn" of invert
residue classes relative to a composite number n, the
of the abbreviated signature generated according to group of units of a finite field, an elliptic curve over a
FIG. 4. 30
finite field, etc. Knowledge of the group order is not
DESCRIPTION OF THE PREFERRED required for transferring the method to an arbitrary
EMBODIMENTS finite group. For example, it is adequate to calculate
In FIG. 1, an example is illustrated how a subscriber with the discrete logarithms on the order of magnitude
of 240.
A, for example a chip card belonging to the subscriber, 35
After the initiation, the subscriber A generates in
proves his identity vis-a-vis a subscriber B, for example
a chip card terminal. record step a random number
In a data exchange system working with chip cards, re(1, . . . , p-l),
the respective user-related chip cards are issued by one
or, potentially, more classification centers (government with the corresponding exponential value
representatives, credit card companies or the like), x = 2 (mod p).
whereby the issue of the chip cards is not instituted until
the identity of the respective user has been checked. The inverse arithmetic process, i.e. calculating the ran
The center then prepares a personal identification string dom number r from the x value is extremely difficult
I for a qualified user (name, address, ID number, etc), 45
attaches the user-related, public key to this identifica insofar as p is adequately large. The subscriber B there
tion string I, this key having potentially been generated fore has practically no possibility of discovering the
by the user himself, and publishes the pair formed of value random number r in the time available to him. This x
identification string I and the public key v in a publical calculated at the subscriber A is transmitted to the
ly-accessible list. The center itself does not see the se 50 subscriber B, i.e. to the terminal. Like the aforemen
cret keys and can therefore likewise not disclose the tioned secret keys, the random number r is a discrete
same. The identification string I, the public and secret logarithm. Following therefrom is that calculations at
keys v, is as well as a declared prime number pare stored the side of the chip card are carried out with discrete
in the chip card before the card is issued. logarithms and are carried out with the corresponding
Instead of using a public list, the center can sign each 55 exponential value at the cooperating side, i.e. in the
pair (I,v). This signature is stored in the chip card and terminal of the subscriber B.
can be easily checked with the assistance of the public Generating the random number r and the exponential
key of the center. After the chip cards and/or the public value
list have been issued, no further interaction with the
center is necessary, neither for generating nor for 60 x = 2 (mod p)
checking signatures and identifications. derived therefrom can be advantageously accelerated
The identification begins with what is referred to as by a preliminary process that offers and regenerates a
an initiation. The subscriber A or, respectively, the chip supply of a plurality of pairs each composed of a ran
card thereby sends an identification string I and the dom number r and the appertaining x value in the chip
public key v to the subscriber Bor, respectively, to the 65 card. This supply can be set up in the chip card itself or
appertaining terminal that verifies the identity. Differ can be externally loaded into the chip card. In an initi
ing from known cryptomethods, the public key is veri ated identification process, one of these pairs can there
fied in the terminal, i.e. the terminal checks the relation fore be immediately accessed, so that the respective x
4,995,082
7 8
value can be immediately transmitted to the subscriber 3. Finally, the subscriber A calculates a y value from
B. the components of the secret key s, random bit se
In the next step, the subscriber B now sends a random quence or, respectively, hash value e and random num
bit sequence ber r according to the relationship
e=(el. . . . . ek)e(0, 1}k k (mod p-1)
to the subscriber A or, respectively, to the chip card. t isX. ei 2".-
After receiving the random bit sequence e, the chip
card sends a linear combination of the secret key si
stored therein-a linear combination dependent on the O theThe number pair x, y then yields what is referred to as
electronic signature of the message m. The two
bits of a random bit sequence e-, adds the current security numbers k and t preferably lie in the range
random number r thereto and transmits the numerical
value y between 1 and 20. They yield a security level 2k, i.e. at
least 2k multiplications (modulo p) are needed for coun
terfeiting the signature or, respectively, the identity.
y = r -- S. i e 22i-1 (mod p-1) 15 For example, k=1 and t=72 yields a security level 272
11 it that is adequate for signatures.
Proceeding on the basis of this signature formed by
formed in this manner to the subscriber B. the number x and y, whereby both numbers are at least
The subscriber B now checks whether the y value 512 bits long, various possibilities of abbreviating the
sent to him is the correct answer to the question raised, 20 signature derive. One of the possibilities provides that
the subscriber A having been asked this question by the the number x be replaced by the hash value e=h(x, m)
subscriber B sending the random bit sequence e. In this that is only 72 bits long. The signature is now composed
check, the subscriber B calculates the right-hand part of of only y and evalues (see FIG. 4). A next step is com
the following equation.
25 prised in no longer taking the numbersy, r, si in the size
of the modulo p, but of only small numbers for y, r, si
k f
(mod p) that, however, are at least 140 bits long for the security
x = 2 j-it 1 is= eit 2 level 272. An especially simple possibility of achieving
short signatures is comprised therein that the prime
30 number modulus p is selected such that a second prime
and determines with reference to a comparison whether number q divides the value (p-1), whereby q is 140 bits
the calculated numerical value x coincides with the x long. The base 2 is then replaced by a number a, so that
value already previously received from the subscriber
A. This task to be carried out at the subscriber B is, in
fact, relatively involved; because of the adequate com
puter performance usually present in the terminal, it can 35 applies. It follows therefron that all discrete logarithms
be carried out in a relatively short time. The identifica can be calculated modulo q, i.e. logarithms for the se
tion check is therefore terminated, so that the subscriber lected number a are calculated, whereby all logarithms
A can initiate further measures insofar as the subscriber can then lie in the range from 1 through q. This has the
Bidentified a coincidence of the two x values. advantage that a number that is smaller than q derives
By incorporating a message n, the described identifi for the y value of the signature. Proceeding from the
cation of the subscriber. A can be expanded into an random number r
electronically-generated signature of the subscriber A retl, ...,g-1},
under the message m. This electronic signature allows
the subscriber B to document the identity of the sub 45 from
scriber A vis-a-vis a third party, for example a judge. In
addition to this, it allows the proof that the subscriber A x = a(mod p)
has signed the message m beyond all doubt. The follow
ing steps must be carried out (see FIG. 2) in order to calculated therefrom as well as from the arbitrary bit
sign a message m given utilization of the secret key si 50 sequence
stored at the subscriber A, i.e. in the chip card:
1. The subscriber A again selects a random number r
and, as already set forth in conjunction with the identity
check, calculates a x value according to the relationship and from the number y
55
x = 2 (mod p).
f mod q)
9. ei 2- (mod q
Here also, of course, there is the possibility of accessing Ec
the stored supply and directly calling in the random
numbers r and the appertaining x value. calculated therefrom, a total length of 212 bits now
60 derives from the signature formed from the numbers y
2. The subscriber. A now forms a hash value e from
the message m and from the calculated x value or, re and e with y = 140 bits and e=72 bits. A signature ab
breviated in this manner has the security level of 272, i.e.
spectively, from the x value taken from the supply, approximately
according to the relationship multiplications modulo p are required in
65
order to counterfeit a signature.
The following steps are performed by the subscriber
B, i.e. in the terminal for verification of a signature
where h is thereby a publicly known hash function composed of the numbers x and y. First, as shown in
having values in {0,1}k. FIG. 3,
4,995,082
10
lated with t additions and the new number xy can be
calculated with t multiplication. Another rejuvenation
is calculated and the equality test is then implemented of the pair (rv, x) is possible according to the rule
such that the x value calculated according to the equa
tion r". = gld -- ra(i) 2. (mod p-)
p
k (mod p)
t f (mod p)
x = 2* j=cT is
isel eit 2-1 res.
c: F x
old
10
is compared to the x value of the signature. The calculation of the new value r is produced here
Given abbreviated signatures in which x is replaced in t additions and t shifts. The new number x can be
by e, the verification according to FIG. 5 occurs in such calculated with 2t multiplications. Beginning with z = 1,
a fashion that 15 the steps
k t (mod p)
x = 2' T is eit 2
are implemented for this purpose with the index i de
is first calculated and a check is then carried out to see 20 scending from t to 1. The new value x is obtained as a
whether the number x supplies the correct evalue. The product of the old value with the most-recently calcu
latter occurs in that a check is carried out to see
whether the hash value h(x, m) coincides with the value lated number z, i.e. according to the rule
e.
Only relatively slight calculating tasks must be pro 25
duced in the chip card both in the identification proto In the rejuvenation, the selection a (t)= u has the
col and the signature protocol. Although the secret key result
sy must still be multiplied by relatively small numbers in tipliedthat a number r that was just rejuvenated is mul
by the highest power of 2. This leads to an espe
calculating the number y, this multiplication can be cially
resolved into simple additions and shift events, what are 30 geous effective
to employ
rejuvenation of the supply. It is advanta
a pair (r, x) as a signature that is formed
referred to shifts, whereby the product of s and et
merely has to be shifted i-1 positions toward the left. as a random combination of the pairs just stored. Inter
The random number r, finally, is then to be attached to of mediate values that arise anyway given the rejuvenation
this intermediate result by addition. rv, xv are well suited for this purpose.
Although the calculation of the number 35
Of course, these rejuvenation processes for the pair
(r, x) can be combined and varied. The only matter of
x=2 (mod p) consequence is that the rejuvenation occurs as quickly
as possible and cannot be duplicated from the signatures
is also involved, it can be practically neglected in terms that have been performed. A small numbert is thereby
of time expenditure due to the aforementioned prelimi expediently employed; the rejuvenation cannot be dis
nary process when x values corresponding to a few covered when the supply of numerical pairs-i.e. the
random numbers are calculated in advance and a plural number k-is adequately large. It is advantageous to
ity of pairs of numbers composed of r values and x co-employ the key pairs si vi in the rejuvenation; for
values are stored as a supply. example, a cipher pairs, v) can be selected for a num
In order to prevent having the same number of pairs 45 ber pair (ra(1), xa(i)). Given t = 6 and k = 10, the rejuve
being used over and over again at regular intervals nation of a number pair requires only 6 or, respectively,
given a limited plurality of pairs, a rejuvenation is car 12 multiplications that can be implemented more or less
ried out insofar as each pair, after use, is subsequently incidently, for example when no other arithmetic opera
combined with other, potentially all pairs of the supply, tions are to be executed in the terminal.
in particular again in a random fashion. The result 50 The versatile possibilities of rejuvenating the number
thereof is that the supply is rejuvenated and varied over pairs (r, x) can be differently used in each chip card.
and over, little by little. For example, the indices a(1), . . . , a(t31 1) and the
As an example of such a rejuvenation, let it be as combination of the cipher pairs of the supply can be
sumed that a supply of k number pairs (ri, x) is present differently fashioned in each chip card. A discovery of
for i=1 ...,k. In order to renew the pair (rv, xv) random 55 the rejuvenation process is practically impossible in this
indices a(1), . . . , a(t-1)et1,...,k}, for example, are ale.
selected, as is a pair (ru, x) that has just been rejuve In the case of the abbreviated signature, the random
nated and the new pair (rv, xv) is calculated with a(t)=u. numbers rimust be small so that they part of the signa
according to the rule
ture also remains small. This is achieved in a simple
f (mod p-1) manner in that the base a for which a 140 bit long prime
ge". eld + X. a(ii) p number q is selected for the discrete logarithms, so that
a4 = 1 (mod p) is valid. The rejuvenation of the random
(mod p) numbers ri, of course, is then calculated modulo q, i.e.
x3". = x3 . . it to the modulus p-i is replaced by the modulus q.
65 Although I have described my invention by reference
to particular illustrative embodiments thereof, many
The relationship x=2/(mod p) again holds true for changes and modifications of the invention may become
the new pair (r34, xi). The new number ru can be calcu apparent to those skilled in the art without departing
4,995,082 12
from the spirit and scope of the invention. I therefore from the generated random number r;
intend to include within the patent warranted hereon all forming a random bit sequence as a function of the x
such changes and modifications as may reasonably and value of a message m and of a declared hash func
properly be included within the scope of my contribu tion h according to the rule
tion to the art.
I claim:
1. In a method for mutual identification of subscribers
in a data exchange system working with processor chip calculating a y value from the random number r, from
cards and using identification data coded into the cards the private cipher si stored in the chip card and
by a card-issuing center including subscriber-related O from the random bit sequence e according to the
public keys and stored in the respective chip cards rule
along with private keys which have a logical relation
ship to the public keys, whereby random number k (mod p-l)
dependent check data are exchanged between the sub y = r -- j=X. 1 si,feX. ei 2-1:
scribers, comprising the steps of: 15
transmitting from a chip card the coded identification transmitting the message m and the signature formed
data together with a signature of the center to a from the value x and y to the subscriber which is in
subscriber entering into an information exchange information exchange with the chip card.
with the chip card; 3. A method for generating an abbreviated signature
at the subscriber checking the correctness of the for a message to be transmitted in a data exchange sys
coded identification data with reference to known tem according to the method of claim 1, and further
information including a public list or reference to comprising steps defined as:
the signature of the center; at the chip card, generating a random number r lying
forming in the chip card a x value proceeding from a in the range between 1 and the prime number mod
random, discrete logarithm re(1,..., p - 1), where 25
ulus (p-1);
p is a declared prime number modulus, and accord at the chip card, calculating a x value from the ran
ing to the rule dom number r according to the rule
x = 2 (mod p): x = 2 (mod p);
30
transmitting the x value to the subscriber; at the chip card, calculating a random bit sequence e
transmitting from the subscriber a random bit se as a function of the x value and of the message
quence
according to the rule
35
e=h(x,m)e(0,1);
to the chip card; at the chip card, calculating a y value from the ran
multiplying the stored, private key si representing a dom number r, from the secret key sand from the
discrete logarithm with a binary number formed random bit sequence e according to the rule
from the bits of the random bit sequence e transmit 40
ted from the subscriber to the chip card and adding K t (mod p-)
the random number r allocated to the previously y: a r -- j=X. 1 i ei 2-1: p
transmitted X value to calculate, at the chip card, a
number y according to the rule
45 transmitting from the chip card the message m and
t the signature formed from the values e and y to the
si s ei 2 (mod p - 1) subscriber which is information exchange with the
chip card.
transmitting the number y to the subscriber; 4. The method of claim 3, and further comprising the
at the subscriber, calculating a number x with refer 50 steps of:
generating a plurality of the random numbers r and a
ence to the number y according to the rule plurality of x values and storing the same in pairs in
the chip card;
k t employing one of the pairs of stored random numbers
x = 2 Tr '2 ei 2 (mod p); 55 r and X values (rv, xv) in an identification procedure
j= 1 =
and varying the pair in such a manner that a ran
checking the identity of the chip card user by con dom number r, after use thereof, is combined with
paring the calculated number x and the x value a random selection of the remaining, stored ran
previously communicated to the subscriber. dom numbers; and
60
2. A method for generating a signature according to calculating the appertaining x value with the rejuve
the method of claim 1, wherein: nated random number and storing the same with
the step of forming a x value is further defined as the rejuvenated random number r as a rejuvenated
generating a random number r within the range of pair.
between 1 and the prime number modulus (p-1) 5. The method of claim 4, and further defined as
and calculating the x value according to the rule 65 comprising:
storing the plurality of random numbers r1, ... ri and
x = 2 (mod p) their appertaining Xu = 2 (mod p) in the chip card;
and
4,995,082
13 14
rejuvenating the pair (r, x) used in an identification composite number r, a group of units of a finite
procedure and/or a signature procedure by ran field, and an elliptic curve over a finite field as a
dom selection (ra(0), xa(n) of the pairs for i=1,. . . finite group.
, t in accordance with 10. A method for the verification of a signature (x,y)
5 generated according to the method of claim 2 at the
f (mod p-1) subscriber receiving the signed message m, comprising
r": = " + š, raio 2' the steps of:
calculating a random bit sequence e from the message
f (mod p)
10
m and from the x value of the signature according
xt". - red. it xii) to the rule
S.
e:= h(x,m)e(0, 1};
6. The method of claim 5, and further defined as: calculating an x value according to the rule
selecting the prime number modulus p such that the
number (p-1) is divisible by a prime number q and 15 (mod p)
by such a selection of the base a of a discrete loga
rithm that
a'= 1 (mod p), as 1 (mod p) from the random bit sequence e, from the public
20 cipher v and from they value of the signature; and
holds true; and comparing the calculated x value with the x value of
calculating discrete logarithms y, r, si modulo q such the signature.
that key components sand viare in the relationship 11. A method for verifying an abbreviated signature
vi= a f(mod p). generated according to the method of claim 3 at the
25 subscriber receiving the signed message m comprising
7. The method of claim 6, and further defined as: the steps of:
selecting the secret key sand the random numbers (r) calculating a number x from the transmitted message
such that the bit lengths of the numbers si, r and y m and from the signature (e, y) according to the
are shorter than the length of the prime number 30 rule
modulus p.
8. The method of claim 6, and further defined as: k f
selecting finite groups for the formation of the dis x = 2 j=at 1 v, isis eit 2- (mod p);
crete logarithm instead of the finite groups that
arise on the basis of residual class modulo p. 35
9. The method of claim 8, and further defined as: checking the value e of the signature for coincidence
selecting one from the groups consisting of the Zn, with the value h (x,sk m).k k sk
the group of invertible residue classes modulo q
45
50
55
60
65