Attack On ElGamal Cryptosystem

In1985, Taher ElGamal proposed ElGamal algorithm which could be used not only in Encryption, but also in digital signature. DSA(digital signature algorithm)is a variant of the ElGamal Signature Scheme. With the same secu-rity strength, the key size of Elliptic curve cryptosystem is relatively small, and therefore. Elliptic curve ElGamal algorithm is also widely used in the smart card industry.The security of ElGamal algorithm is based on the difficulty of discrete logarithm problem. There are some algorithms which could be used to compute discrete logarithm. Shanks[16] proposed Baby-Step Giant-Step algorithm which needs O((?) logn) time complexity and O((?)logn) space complexity. Pohlig-Hellman algorithm could be applied when the order of group is smooth. Besides, there are Pollard’s p algorithm, Index Calculus al-gorithm. All of the algorithms could improve the efficiency of computation, but there is no Polynomial time algorithm to compute discrete logarithm.For elliptic curve discrete logarithm problem, Agustin et al.[5] proposed a method by using fault injection. By analyzing elliptic curve scalar multi-plication algorithm over binary field, they found the algorithm does not uti-lize the curve parameter a. Besides, after comparing NIST-recommended el-liptic curves E(a,b) with the corresponding curves E(a.b), they notice that the group E(a, b) is cryptographically weak with great probability, where Tr(u)=1-Tr(a). with the observation, Agustin et al. inject a fault while computing scalar multiplication to make sure the x-coordinate of fault point P is on curve E(a,b), and then compute P and Q=kP. The above operations turn the difficult discrete logarithm problem on strong elliptic curves to be a easier one. Then, the discrete logarithm k or partial information of k could be computed by using Pohlig-Hellman algorithm.Recently. Berzati et al. proposed a method to attack DSA. To avoid solving difficult discrete logarithm problem, the method adopts lattice attack and fault injection. The attacker inject a fault that affect randomly on byte of the public parameter p. The fault is supposed to occur t steps before the end of exponentiation. The fault p is written by p. The attacker guesses both p and the least significant part of k, kt, and then computes kt by analyzing the signature. If the attacker could get several fault signature with several fault injection, then recovering the private key of DSA will be transformed into solving the closest vector problem by constructing lattice, so the private key could be recovered by using Babai’s algorithm at last.In this paper we proposed a method to attack ElGamal encryption sys tem. First, for elliptic curve ElGamal encryption system, let the cryptosystem defined over group G, the attack algorithm could get partial informaition of private key efficiently if the order of G has some other factors except one large prime factor. if we suppose that p0if the largest prime fac-tor of ord(G), so the order of the base point P could be p0while constructing ElGamal cryptosystem. Let Q=dP be public key, where d is private key, and then the cipertext would be (H, m’)=(kP,x(kQ (?) m)), where k is randomly chosen and m is the message to be encrypted. Given decryption oracle, we forge one cipertext (pR,m"), where R is the generator of G and m" is chosen randomly as a known value. The decryption oracle would compute dpR and then return x(dpR)(?) m". we could obtain dpR with the returned value, and then compute d mod using Pholig-Hellman algorithm. The attack al-gorithm obtain the rest information using an exhaustive search. The complete attack procedure is presented as Algorithm4in chapter2.Take80-bit secure elliptic curve ElGamal cryptosystem as an example, our attack method could obtain partial information of private key with about99.4%possibility, and this value will increase as the security level increases Comparing with computing discrete logarithm, our attack method could de-crease time complexity significantly. The examples in chapter2could recover the private key basically.For ElGamal encryption system defined in finite field, the attack method is similar to algorithm4. However, the attack process is different because of different cryptosystem construction. The core of the attack is to turn the difficult discrete logarithm to be a easier one. Let a be a primitive element of finite field Zp, where p-1=p1p2e2...Pses.Given decryption oracle, by forging cipertext (γ, M), where γ=aP1, we can obtain γa(a is private key) with returned value of decryption oracle. Then we use Pohlig-Hellman algorithm to compute: a1≡a mod p2e2...pses,The rest information of private key could be obtained with an exhaustive search if the bits of p1/p2e2...pses is Pses is within computing power. The rest information could be written as a2≡a mod p1,The entire private key could be computed with CRT at last. The complete procedure is presented in Algorithm5.From the attack method, We conclude that the parameters should be chosen more strictly while constructing ElGamal encryption algorithm. For elliptic curve ElGamal encryption system, one large prime factor is not enough for the order of elliptic curve point group. For ElGamal encryption system defined in finite field, the rest factors of p-1should be considered seriously except that p is a large prime number and p-1has one large prime factor. We present some countermeasures to prevent the attack method in chapter2.