A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE

SCHEME BASED ON DISCRETE LOGARITHMS

TaherElGamal'
Hewlett-Packard Labs
1501 Page Mill Rd
Palo Alto CA 94301

A new signature scheme is proposed together with an implementation of the Diffie Eell- -
man key distribution scheme that achieves a public key cryptosystem. The security of both
systems relies on the d i f h u l t y of computing discrete logarithms over finite flelds.

1. 1NTRODUCTION

In 1976. Diffie and Hellman [3] introduced the concept of public key cryptography. Since
then, several attempts have been made to flnd practical public key systems (see for example
[8.7.9]) depending on t h e dwiculty of solving some problems. For example, the RSA system
[9] depends on the difficulty of factoring large integers. This paper presents systems that
rely on the difficulty of computing logarithms over finite flelds.

Section 2 shows a r a y to implement the public key distribution scheme introduced by

Diffie and Hellman [3] to encrypt and decrypt messages. The security of this system is
equivalent to that of t h e distribution scheme. Section 3 introduces a new digital signature
scheme t h a t depends on the difficulty of computing discrete logarithms over finite flelds. It is
not yet proved that breaking the system is equivalent t o computing discrete logarithms. Sec-
tion 4 develops s o m e attacks on the signature scheme, none of which seems to break it.
This work was supported by the WSF under contract ECSBJ O f 1 4 1 while the author wns at the
information systems laboratory. Stanford University.

G.R. Blakley and D. Chaum (Eds.): Advances in Cryptology - CRYPT0 '84, LNCS 196, pp. 10-18, 1985.
0 Springer-Verlag Berlin Heidelberg 1985
 11

Section 5 gives some properties of the system. Section 6 concludes and gives some remarks.

2. THE PUBLIC KEY SYSTEM

-
First. the Diffie Hellman Key distribution scheme is reviewed. Suppose that A and B
want to share a s e c r e t K m where A has a secret 2".and B has a secret ZB. Let p be a large

prime and a be a primitive element m o d p , both known. A computes yA = a" mod p , and
sends YA. Similarly B computes y~ = a=* n o d p and sends yB. Then the secret K m is com-
puted a s

KAB= a ~ A mud
~ Bp
= yAz* m o d p
=v
~ mod
= ~p .
Hence both A and B a r e able to compute Ka. But for an intruder computing K a appears t o
be difficult. Note t h a t i t is not yet proved that breaking the system is equivalent to computing
discrete logarithms. For more details refer to [3].

In any of the cryptographic systems that are based on discrete logarithms, p must be
chosen such t h a t p - 1has at least one large prime factor. If p - 1 has only small prime fac-
tors, then computing discrete logarithms is easy (see [a]).
Now suppose that A rants t o send B a message m . where 0 d rn p - 1. First A chooses
a number k uniformly between 0 and p - 1. Note that k wiU serve as the secret ZA in the key
distribution scheme. Then A computes the "key"

K = y~~ m o d p , (1)
where = as# nrod p is either in a public file, o r is sent by B. The encrypted message (or
ciphertext) is t h e n t h e pair ( c c ), where

c,=u* modp, cg = K m modp.

and K is computed in (1).

Note that t h e size of the ciphertext is double the size of of the message. Also note t h a t
the multiplication operation in (2) can be replaced by any other invertible operation such a s
addition mod p.

"he decryption operation splits into 2 parts. The f i s t step is recovering K. which is easy
for B since K = ( a* )'B = c y * mod p . and rBis k n o w n t o B only. The second s t e p is to divide
cg by K and recover the message m .
The public file consists of ane entry for each user. namely vt for user i (since a and p are
known for all users). I t is possible that each user chooses his own a and p , which is preferable
 12

from the security point of view but that will triple the size of the public Ale.

I t is not advisable to use the same value k for enciphering more than one block of t h e
message, since if k is used more than once, knowledge of one block m, of the message
enables an intruder t o compute other blocks a s follows:
Let

cl,l = ak m o d p , c 2 , ] = m ,K m o d p ,
and

c,.~=[x*modp. ~2.2=m2K
modp.

Then 2=
m2
% mad p . and m2 is easily computed if rn
c2.2
is known.

I t can be easily seen t h a t breaking the system is equivalent to breaking the Diflte - Hell-
man distribution scheme. First. if m can be computed from c,. c2. and y. then K can also be
computed from y. c,. and c 2 (which appears like a random number since k and m are unk-
nown). That is equivalent t o breaking the distribution scheme. Second. (even if m is known)
computing k or z from clr cz. and y is equivalent to computing discrete logarithms. The rea-
son is that both r and k appear in the exponent in y and cl.

3. A DIGITAL SIGNATLJRE SCHEME

A new signature scheme is described in this section. The public dle contains the same
public keys for encrypting messages as well as verifying signatures.

Let m be a document t o be signed, where 0 s m s p - 1. The public me still consists of

the public key y ='a mod p for each user. To sign a document, a user A should be able t o
use the secret key tAto flnd a signature for m in such a way that all users can verify t h e
authenticity of the signature using t h e public key YA (together with a and p ) . and no one can
forge a signature without knowing t h e secret 2,.

The signature for m is t h e pair ( r , s). 0 4 r , s < p - I. chosen such that the equation
a" = y' T' mod p (3)
is satisfled.

3.1. The Signing Procedure

The signing procedure consists of the following 3 steps:

A. Choose a random number k. uniformly between 0 and p - 1, such that

gcd (k . p - 1) = 1.
 13

B. Compute
t = ak mod p .
C. Now (3)c a n be written a s

am = as r s modp ..
whish c a n be solved for s using

m = z r + k s mod(p-1).
Equation (6) h a s a solution for s if k is chosen such that gcd ( k , p - 1 ) = 1.
3.2. The Veriflcation P r o c e d u r e

Given m , T , and s, i t is e a s y t o verify the authenticity of t h e signature by computing

both sides of (3)and checking t h a t t h e y a r e equal.

Note

As will b e shown in section 4. the value of k chosen in step A should never be used m o r e
than once. This c a n be guaranteed, f o r example. by using as a "k generator" a DES chip used
in t h e c o u n t e r mode as a stream cipher.

4. SOME ATTACXS ON THE SIGNATURE SCHEME

This section i n t r o d u c e s s o m e of t h e possible attacks on the signature scheme. Some of

these a t t a c k s are easily shown t o be equivalent t o computing discrete logarithms over G F ( p ) .
It is n o t y e t proved that breaking t h e signature scheme is equivalent t o computing discrete
logarithms. o r equivalent t o breaking t h e distribution scheme. However, none of t h e a t t a c k s
shown in this section a p p e a r t o b r e a k t h e system. The reader is encouraged t o develop new
attacks, or And fast algorithms t o perform one of t h e attacks described in this section. The
a t t a c k s r i l l b e divided i n t o t w o groups. The f i s t group includes some attacks for recovering
t h e s e c r e t key z.a n d i n t h e s e c o n d group we show some attacks for forging signatures
without recovering z .

4.1. Attacks aiming t o recover z

4.1.1. Given I m, : i = 1 , 2 , . . . , 1 { documents. together with the corresponding signa-

tures (ri , S,) : i = I , 2 , . ,l I, a n intruder may try to solve l equations of t h e form ( 6 ) .

Since t h e r e are I + 1 unknowns (since each signature uses a different k). the system of
 14

equations is underdetermined a n d the n u m b e r of solutions is large. The reason is t h a t e a c h

value for 1: yields a solution f o r the 4 ' s since a system of linear equations with a diagonal
matrix of coefficients r i l l result. Since p - 1 is chosen to have a t least one large prime f a c t o r
q . recovering z mod q requires a n exponential number of message-signature pairs.

Note

If any k is used twice in t h e signing, t h e n the system of equations is uniquely d e t e r m i n e d

and 1: c a n b e recovered. So for the s y s t e m t o be secure, any value of k should never be u s e d
twice.

4.1.2. Trying t o solve equations of the form (3) is always equivalent t o computing discrete
logarithms over C F ( p ) . since b o t h unknowns z , and k appear in the exponent.

4.1.3. A n i n t r u d e r might t r y t o develop some linear dependencies among t h e unknowns 1

4 , i = 1. 2 , . . , L j. This is also equivalent t o computing discrete logarithms since if
8

kt = c k~ mod (p - 1).then r, = rjc mod p . and if c can be computed then computing

discrete logarithms is easy.

4.2. Attacks for Forging Signatures

4.2.1. Given a d o c u m e n t m. a forger may t r y t o find r , s such t h a t (3) is satisfied. If

T = aJ m o d p is Axed f o r s o m e j chosen a t random, then computing s i s equivalent t o solving
a discrete logarithm problem over CF@).

If t h e forger ! h e s s first t h e n r could be computed from the equation

' = A mod p .
r' y (7)
solving equation (7)for r is n o t yet. proved t o be at least as hard as computing d i s c r e t e loga-
rithms, but we believe that i t is not feasible t o solve (7) in polynomial time. The r e a d e r i s
encouraged t o find a polynomial time algorithm for solving (7).

4.2.2. I t s e e m s possible t h a t (3) can be solved for both T and s simultaneously. b u t we

have not been able t o Bnd an efficient algorithm t o do that.

4.2.3. The signature s c h e m e allows t h e following attack, whereby t h e intruder, knowing

one legitimate signature for one message, can generate other legitimate signatures a n d mes-
sages. This a t t a c k does n o t allow t h e intruder t o sign an arbitrary message and t h e r e f o r e
does not break the s y s t e m . This p r o p e r t y exists in all the existing digital signature s c h e m e s
and c a n be avoided by e i t h e r requiring t h a t m has to be of certain structure, or by applying a
 15

one-way function to the message m before signing it.

Given a signature ( t , s ) for the message (m). then

am = yr T' mod p .
Select integers A , 8.and C arbitrarily, such that ( A r 0 ) -
is relatively prime t o p - 1. Set

r ' = r AaBy c m o d p .
= ~ r ' / ( A r- CS) mod (p - 1).
S'
and m' = r ' ( h + Bs)/(Ar - [=s) mod (p - 1).
Then it is claimed t h a t ( r ' , s ' )signs the message (m'). Calculate
-' = tlr'(tA aB yC)m'/(k - Q)
yr'
- (yr'Av -r'D +r'0 rkr' a 8 h ' ) I / ( A r - a)
=((vr +)k*a h r ' ) 1 / ( , 4 r -a)
**w*
=&(w -0)
=a"' (dlcalculations mod p).
As a special case, setting A = 0.legitimate signatures can be generated with corresponding
messages without ever seeing any signatures:

r *= a B y c mod p .
s ' = - T ' / C m o d @ -1).
m ' = - r ' B / C mod (p 1). -
It can be shown t h a t ( r ' . ~ signs
') (m').

5. PROPERTIES O F O U R SYSTEM AND COMPARISON TO OTHER SIGNATURE SCHEMES AND PUB-

LJC KEY SYSTEMS

Let m be t h e number of bits in either p for the discrete logarithm problem. or TI for the
integer factoring problem. Then t he best known algorithm for both computing discrete loga-
rithms and factoring integers (which is the function used in some of the existing systems such
a the RSA system [Q]) is given by (see [ 1.5.101)

O(exp-Jcrn h r n 1 , (8)
where t h e best estimate for c is c = 0.89 for factoring
integers, (due to Schnorr and Lenstra
[lo]). as well as for discrete logarithms over GF@) (see [ 5 ] ) . These estimates imply that we
have to use numbers of about the size of the numbers used in the RSA system to obtain the
same level of security (assuming the current value for c for both the discrete logarithms
problem and t h e integer factorization problem). So, the size of the public file is larger than
that for the RSA system. (For the RSA system. each user has one entry n as his public key
together with t h e encryption key in the public file.)
 16

5.1. Properties of the public key system

As shown above our system has some differences with the other known systems. First,
due to the randomization in the enciphering operation, the cipher text for a given message m
is not repeated, i.e. if we encipher the same message twice we will not get the same cipher
text [C 1 , cpj. This prevents attacks like a probable text attack where if the intruder suspects
that the plain text is, for example, rn. then he tries to encipher rn and Ands out if it was
really m. This attack. and similar ones, will not succeed since the original sender chose a
random number k for enciphering, and different values of k will yield diflerent values of
Ic, , ce{. Also. due to the structure of our system, there is no obvious relation between the
enciphering of m,.m2. and m ,m2, or any other simple function of m, and mz.T h i s is not the
case for the known systems, such as the RSA system.

Suppose t h a t p is of about the same size as that required for n in the case of the RSA
system. Then t h e size of t h e cipher text is double the size of the corresponding RSA cipher
text.

For the enciphering operation two exponentiations are required. That is equivalent t o
about 2 log p multiplications in GF(p). For the deciphering operation only one exponentia-
tion (plus one division) is needed.

5.2. Properties of the signature scheme

For the signature scheme using the above arguments for the sizes of the numbers in our
system and the RSA system, the signature is double the size of the document. Then. the size
of the signature is of t h e s a m e size as that needed for the RSA scheme, and half the size of the
signature for the new signature scheme t h a t depends on quadratic forms published by Ong
and Schnorr[B]. and also Ong,Schnorr. and Shamir[7] (since both systems are based on t h e
integer factoring problem). The Ong-Schnorr-Shamir system has been broken by Pollard and
new variations are being suggested. Thus it is not clear at the present time whether a secure
system based on modular equations can be found and hence no further remarks will be made
regarding these schemes.

Note that, since t h e number of signatures is p 2 while the number of documents is o n l y p ,

that each document m has a lot of signatures, but any signature signs only one document.

For the signing procedure. one exponentiation (plus a few multiplications) is needed. To
verify a signature. it s e e m s t h a t t h r e e exponentiations are needed, but it was pointed t o the
author by A. Shamir t h a t only 1.675 exponentiations are needed. This is done by representing
 17

the three exponents m , r , s in their binary expansion. A t each step square the number
u- 'yr and divide by the necessary factor t o account for the different expansions of rn, f , and
s. The different multiples of a- , y , and T can be stored in a table consisting of eight
entries. We expect t h a t 0.875 of the time a multiplication is needed. That accounts for the
1.875 exponentiations needed.

6. CONCLUSIONS AND REMARKS

The paper described a public key cryptosystem and a signature scheme based on t h e
difficulty of computing discrete logarithms over flnite flelds. The systems are only described
in G F f p ) . The public key system can be easily extended to any GF(pm), but due to recent
progress in computing discrete logarithms over GF(pm), where m is large (see [ 2 . 5 ] ) ,it is
advisable t o use G F ( p ) instead since it seems that it is harder to compute logarithms over
G F ( p ) than over CF(gm) for large rn if p and q m are of the same size. The subexponential
time algorithm has been extended to GF($) [4] and it appears that it can be extended to all
finite fields. Hence. it seems t h a t it is better to use G F ( p ) for implementing any crypto-
graphic system. The estimates for the running time of computing discrete logarithms and
factoring integers are the best known so far. These estimates imply that the public fle size is
larger in this scheme than in the RSA scheme, but the difference is a t most a factor of two
due t o t h e structure of both schemes. Also the size of the cipher text is double t h a t of the
RSA system.

ACKNOWLEDGEMENT

The author would like t o thank a referee for including the attack described in section
4.2.3.

REFERENCES

[ l ] L. Adleman, A Subexponential Algorithm for the Discrete Logarithm Problem with Appli-
cations t o Cryptography, Proc. 20th IEEE Foundations of Computer Science Symposium
(1979). 55-50.

[2] D. Coppersmith. Fast Evaluation of Logarithms in Fields of Characteristic two, IEEE Tran-
sactions on Information Theory IT-30(1964), 587-594.
 18

[3] w. Didie a n d M. Hellman. New Directions in Cryptography, lEEE Transactions on Informa-

tion Theory, IT-22(1976). 472-492.

[4] T. EICamal. A Subexponential-Time Algorithm for Computing Discrete Logarithms over

GF(p2).s u b m i t t e d t o lEEE Transactions on Information Theory.

[ 5 ] A. Odlyzko. Discrete Logarithms in Finite Fields and Their Cryptographic Significance. t o

a p p e a r in Proceedings of Eurocrypt '84.

[6] H. Ong and C. Schnorr, Signatures Through Approximate Representations by Quadratic

Forms, t o be published.

[7] H. Ong, C. Schnorr, a n d A. Shamir, An eflicient Signature Scheme Based on Quadratic

Forms, p p 208-216 i n Proceedings of 16th ACM Symposium on Theoretical Computer Sci-
ence, 1984.

[a] S.Pohlig a n d M. Hellman, An improved algorithm for computing logarithms over G F O )

and i t s cryptographic significance, IEEE Transactions on Information Theory It-24 (1978).
106-110.

[9] R. Rivest, A. Shamir, a n d L Adleman, A Method for Obtaining Digital Signatures a n d Public
Key Cryptosysterns. Communications of t h e ACM. Feb 1978, volume 21. n u m b e r 2. 120-
128.

[lo] C. S c h n o r r and H. W. Lenstra 3r.. A Monte Car10 Factoring Algorithm with Finite Storage.
t o a p p e a r i n Mathematics of Computation.