Comment
Enhancing the security of ElGamal's signature scheme
L. Harn
Indexing terms: Digital signature, Cryptography, RSA cryptosystem
J. He and T, Kiesler recently proposed a digital signature scheme [1] to embed both the discrete logarithm problem and the factorization problem in the processing of signing to enhance the security of the original ElGamal signature scheme [2]. The purpose of this comment is to show that the security of the signature scheme is not as secure as they have claimed.
We now briefly describe the scheme of J. He and T. Kiesler. Let p be a large prime such that p-1 has two large prime factors p1 and q1. Let n=p1q1. Let g be a primitive element of GF(p). p is a common parameter; but the two factors of n must be kept secret from every user.
Any user A has a secret key x1 such that gcd(x1, p-1)=1. Then computes x=x12 mod p-1, and corresponding public key z=gx2 mod p. To sign a message m, A does the following steps:
(i) Randomly selects an integer t1, such that gcd(t1, p-1)=1, and computes t=t12 mod p-1.
(ii) Computes k=t2 mod p-1.
(iii) computes r=gk mod p, with rð1.
(iv) Finds s such that m=xr+st mod p-1 (i.e., s=(m-xr)t-1 mod p-1).
(v) Calculates c=t1◊x1 mod p-1.
{m, (r, s, c)} is the signature.
To verify that {m, (r, s, c)} is the signature, one simply checks the identity
gm2= zr2rs2g2rsc2 mod p.
In the analysis of the security of the scheme in [1], the authors consider various attacks and drew the conclusion that the security of this scheme is based on solving both the discrete logarithm and the factorization problems. We want to show that their claim is invalid.
Assume that a signature (r, s, c) of a known message m is given. It is then possible for the attacker to establish the following equation as
m=xr+st mod p-1.
By multiplying x on both sides of the above equation, it can obtain
mx=x2r+stx mod p-1.
Since c2=tx mod p-1, the attacker obtains the second-order equation as
rx2-mx+sc2=o mod p-1.
The equation can be solved if the factorization of p-1 is known. Thus, under known-signature attack, the signer's secret key x can be recovered if the attacker can only solve the factorization problem.
In a very similar paper proposed by L. Harn [3] recently, instead of keeping the two secret factors of n from every user, every user selects his/her secret factors of n and keeps these factors as each individual's secret. Thus, just the same as the RSA cryptosystem [4], each user has different public modulus p. The security of the proposed cryptosystem is equivalent to solving both the discrete logarithm and the factorization problems.
Oct. 10, 1994
L. Harn (Computer Science Telecommunications Program, University of Missouri-Kansas City, Kansas City, MO 64110, USA)
References
1. He, J., and Kiesler, T.: 'Enhancing the security of El Gamal's signature scheme', IEE Proc.-Comput. Digit. Tech., Vol. 141, No. 4, July 1994, pp. 249-252.
2. ElGamal, T.: 'A public key cryptosystem and a signature scheme based on discrete logarithms', IEEE Trans., IT-31, July 1985, pp. 468-472.
3. Harn, L.: 'Public-key cryptosystem design based on factoring and discrete logarithm', IEE Proc.-Comput. Digit. Tech., Vol. 141, No. 3, May 1994, pp. 193-195.
4. Rivest, R. L., Shamir, A., and Adelman, L.: 'A method for obtaining digital signatures and public-key cryptosystem', Commun. ACM, 1978, 21, (2), pp. 120-126.