A public key criptosystem, taher el gamal

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-31, NO. 4, JULY 1985

A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms
TAHER ELGAMAL, MEMBER, IEEE

Abstract—A new signature scheme is proposed, together with an implementation of the Diffie-Hellman key distribution scheme that achieves a public key cryptosystem. The security of both systems relies on thedifficulty of computing discrete logarithms over finite fields.

I. INTRODUCTION

I

N 1975, Diffie and Hellman [3] introduced the concept of public key cryptography. Since then, several attempts have been made to find practical public key systems (see, for example, [6], [7], [9]) depending on the difficulty of solving some problems. For example, the RivesShamirAdleman (RSA) system [9] depends on thedifficulty of factoring large integers. This paper presents systems that rely on the difficulty of computing logarithms over finite fields. Section II shows a way 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 the distribution scheme. Section III introduces a new digitalsignature scheme that depends on the difficulty of computing discrete logarithms over finite fields. It is not yet proved that breaking the system is equivalent to computing discrete logarithms. Section IV develops some attacks on the signature scheme, none of which seems to break it. Section V gives some properties of the system. Section VI contains a conclusion and some remarks. II. THE P UBLIC KEYS YSTEM

Hence both A and B are able to computer KAB. But, for an intruder, computing K AB appears to be difficult. It 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 based on discrete logarithms, p must be chosen such that p - 1 has at least one large prime factor. If p - 1 has onlysmall prime factors, then computing discrete logarithms is easy (see [8]). Now suppose that A wants to send B a message m, where 0 C m C p - 1. First A chooses a number k uniformly between 0 and p - 1. Note that k will serve as the secret xA in the key distribution scheme. Then A computes the “key” k K y B mod p, (1) xB where y B mod p is either in a public file or is sent by B. The encryptedmessage (or ciphertext) is then the pair (c1, c 2), where k mod p c2 Km mod p c1 (2) and K is computed in (1). Note that the size of the ciphertext is double the size of the message. Also note that the multiplication operation in (2) can be replaced by any other invertible operation such as addition mod p. The decryption operation splits into two parts. The first x step is recovering K, which is easyfor B since K H ( k ) B x H c1 B mod p , and xB is known to B only. The second step is to divide c2 by K and recover the message m . The public file consists of one entry for each user, namely yi for user i (since and p are known for all users). It is possible that each user chooses his own and p , which is preferable from the security point of view although that will triple the size of the publicfile. It is not advisable to use the same value k for enciphering more than one block of the message, since if k is used more than once, knowledge of one block m 1 of the message enabled an intruder to computer other blocks as follows. Let k mod p c 1,1 c 2,1 m1 K mod p, k mod p c 1, 2 c 2, 2 m 2 K mod p.
Then m 1/m 2 c2,1/c2,2 mod p, and m 2 is easily computed if m 1 is known. Breaking the systemis equivalent to breaking the Diffie-Hellman distribution scheme. First, if m can be computed from c1, c2, and y, then K can also be computed from y, c1, and c2 (which appears like a random

First, the Diffie-Hellman key distribution scheme is reviewed. Suppose that A and B want to share a secret KAB, where A has a secret xA and B has a secret xB. Let p be a large prime and be a primitive...