ElGamal算法[6]由Taher ElGamal在1985年提出,ElGamal算法既可用于加密,也可用于数字签名,DSA(数字签名算法)亦是由ElGamal演变而来的,在相同的安全强度下,椭圆曲线密码体制的密钥尺寸比较小,又使得椭圆曲线ElGamal算法广泛应用在智能卡行业。ElGamal算法的安全性基于离散对数问题的困难性,目前有一些计算离散对数的算法,Shanks[16]提出了小步大步法,该算法需要P((?)nlog n)的时间复杂度以及同样多的空间复杂度,Pohlig-Hellman算法则可以在群的阶是光滑数的情况下使用,另外,还有Pollard p算法[12],Index Calculus算法等,这些算法都极大地提高了计算的效率,但是目前还没有计算离散对数问题的多项式时间算法对于椭圆曲线离散对数问题,Agustin[5]等人提出了一种故障攻击的方法。该方法通过对特征为2的椭圆曲线点乘算法进行分析,得出点乘运算与曲线参数a无关,在对比了NIST推荐的椭圆曲线E(a,b)和改变参数a后的曲线E(a,b)后,其中Tr(a)=1-Tr(a),又发现了改变参数a后的椭圆曲线点群在密码学意义上以很大的概率是弱的,即群的阶是比较小的素因子的乘积。基于以上事实,Agustin等人在进行椭圆曲线点乘运算时植入故障,从而使得输入点(基点)P的x坐标落到曲线E(a.b)上,进而通过点乘运算分别得到曲线上的点P和点Q=kP,这样就把强椭圆曲线上的困难的离散对数问题转化到弱椭圆曲线上的较容易的离散对数问题,然后通过Pohlig-Hellman算法求得离散对数k或k的部分信息。最近,Bcrzati等人在[18]中提出了一种针对DSA(Digital Signature Al-gorithm)的攻击方法,这种攻击方法通过使用格攻击和故障攻击两种工具,有效地绕过了求解离散对数的困难问题。假设在进行DSA签名的第一部分模指数运算的最后t步之前,对公开参数p植入一个字节的故障,记改变后的p为p,通过猜测随机数k的最后t比特kt以及p,并根据对签名的分析得到的一些性质来验证猜测的结果从而求得kt,如果攻击者能够通过多次植入故障的方法得到多个故障签名,那么可通过构造格将求DSA私钥的问题转化为求格的最近向量问题,最后使用Babai的求格算法求出私钥。本文提出了一种对ElGamal加密体制的攻击方法。首先,对于椭圆曲线ElGamal加密算法,令G是密码算法所在的椭圆曲线点群,如果G=<g>的阶除了一个大素数因子外还有一些其他因子,那么本文的攻击算法可以成功地得到密钥的部分信息。令段设p0是ord(G)的最大素因子,即在构建ElGamal密码体制时从G中选择一个阶为po的点作为基点P,Q=dP为公钥,d为私钥,贝ElGamal加密体制最后生成的密文形如(H,m’)=(kP,x(kQ*(?)m)),其中k是随机数,m是待加密的信息。假设给定解密喻示,则可以伪造一个密文(pR,m"),其中R是阶为Πi=0j-1piei的点,m"随机选取且已知,解密喻示会计算dpR并返回x(dpR)(?)m",根据返回值可以求出dpR,然后利用Pholig-Hellman算法求出如果的大小在穷搜能力范围之内,该攻击算法可以穷搜出密钥的剩余信息,从而恢复出整个密钥,第二章算法4给出了具体的攻击步骤。以80比特安全的椭圆曲线ElGamal密码体制为例,本文的攻击方法能以大约99.4%的概率获得密钥的部分信息,这个概率会随着群的阶的比特数的增加而提高。从具体攻击中可以知道与直接计算离散对数的方法相比,该攻击方法可以很明显地降低时间复杂度,本文的几个例子基本上都可以恢复出整个密钥。对于有限域上ElGamal加密体制,和对椭圆曲线ElGamal加密体制的攻击思路一致,但由于两种密码体制的构造不同使得具体的攻击过程也有相应的不同。首先也需要把困难的离散对数问题转化为一个较易解决的离散对数问题,假设α是有限域Zp的本原元,且已知p-1的分解为p-1=plp2e2…pses,若给定解密喻示,则构造密文(γ,M),其中γ=αp1,由解密喻示的返回值求出γa(a为私钥),然后根据(γa,γ)使用Pohlig-Hellman算法计算：a1≡a mod p2e2…p2es假如此时p1/p2e2…pses的大小也在计算能力之内时,那么可以利用穷搜的方法搜索a mod p1的剩余信息,即求得：a2≡a mod p1,最后利用中国剩余定理求出完整的密钥a mod p-1,第二章算法5介绍了具体的攻击过程。本文的攻击方法表明在构建ElGamal加密算法时要更严格地选择参数,对椭圆曲线ElGamal加密体制来说,仅考虑椭圆曲线点群的阶有一个大素数因子是不充分的,而对于有限域上的ElGamal加密体制来说,除了要满足p是一个大素数以及p-1至少有一个大素数因子外,还要考虑p-1的其他因子,第二章给出了具体地抵抗本文攻击算法的措施。