网络信息与安全——EIGamal数字签名方法的研究与分析姓名：学号：班级：指导老师：时间：EIGamal数字签名方法的研究与分析【摘要】在实际生活和工作中，许多事物的处理需要当事人的签名。

尤其在现代通信中，签名更是起到了认证、核准、有效和负责等功效。

数字签名是现代密码学的一个重要组成部分，自从Diffie和Hellman于1976年首次提出数字签名以来，数字签名就在学术界和计算机网络界得到了迅猛的发展。

ElGamal就是一种原理简单，应用广泛的数字签名方法，它的成功很大程度上取决于求解离散对数问题的困难。

本文介绍了这种数字签名方法，阐述了实现的方法，分析了其安全性及可能的攻击方法，并分析了EIGamal改进型算法及其证明。

【关键词】EIGamal体制数字签名计算机网络一、前言众所周知，一个人在一份文件的最后想证明自己身份可以用他的印章或手写签名，而一个单位可以用公章。

在信息高度电子数字化的今天，很多文件，数据都不是纸质的，难道我们可以在一份数据文件上盖印章吗？回答是肯定的，这就是要使用数字签名技术。

数字签名技术作为计算机数据安全的一项重要手段，现在正被广泛应用，电子邮件（E—mail）、电子资金转账（EFT）、电子数据交换（EDI）和软件分发等方面，都要使用数字签名技术。

随着计算机网络的应用普及，网络对等实体的识别、通信保密和数据完整性显得越来越重要，而确实解决这一问题则必须要使用数字签名技术。

在1976年公钥密码体制没有发明以前，人们使用传统的密码技术解决数据交换中的安全问题，一个人能使用密码加密一个文件给另外一个人，那么另外的那个人必须要利用解密密钥才能读懂加密过的文件，这时通信双方的身份和文件的完整性都随着文件的解密是否成功而不言而喻。

1976年，W.Diffie 和M.Hell-man 发明了公钥密码体制，美国公布了数据加密标准（DES ），标志着现代密码技术到达了一个新的阶段，数字签名技术也得到了飞速地发展。

采用私钥密码体制（DES ）技术和公钥算法（如RSA 等）都可以实现数字签名。

由于私钥密码体制本身的特性，使用私钥的数字签名体制在存储和通信上花费都比较大，故一般不考虑使用。

而由于公钥密码体制的特点，其非常适合应用于签名技术，因此现在公布的几种数字签名建议标准中使用的都是公钥密码体制。

如ISO 建议过的RSA 算法和美国国家标准与技术研究所（NIST ）建议标准DSS （Digital Signature Stantard ），也是从下面我们介绍的EIGamal 公钥密码体制演变而来的。

二、什么是EIGamal 公钥密码体制EIGamal 公钥密码体制是1984年Stanford 大学的Tather EIGamal 提出的，这是基于离散对数运算基础上的公钥体制，它采用的是Diffe —Helfman 密钥分配体制的思想，综合了其他一些加密体制的优点。

利用EIGamal 公钥密码体制设计出的数字签名方法与一般公钥密码体制签名方法的不同之处，是具有高安全性和实用性。

Diffie-Hdlman 体制是指；在基于素散的有限域GF(p)上，其中P 是一素数，g 是其本原元，A 、B 两方想要通信，首先要得到双方都知道的一个通信密钥KAB ，假设A 、B 各持有一私用密钥XA 、XB ，A 可计算YA=p g XA mod ，将YA 发往B 。

B 可计算YB=p g XB mod ，将YB 发往A 。

然后双方同时计算：KAB=)mod (mod mod p g p YB p YA XAXB XA XB ==EIGamal 密码体制也是通信双方各持有一私钥密钥XA 、XB ，并将YA （p g XA mod ）、YB （p g XB mod ）作为公开密钥公布。

双方加解密的方法是通过生成一组随机数混入明文块中以产生一个二维密文数组，达到随机密码的效果。

EIGamal 数组签名方法具体如下：1.体制参数p ：一个大素数，可使p Z 中求解离散对数为困难的问题 g: 是p Z 中乘群*p Z 的一个生成元或本原元素 M: 消息空间为*p ZS ：签名空间为1*-⨯p pZ Z X ：用户密钥*p Z x ∈，公钥为p g y x mod =安全参数为k=(p,g,x,y),其中p 、g 、y 为公钥，x 为密钥。

2.签名过程给定消息M ，发送端用户进行下述工作： (1)选择秘密随机数*p Z k ∈。

(2)计算压缩值H(M)，并计算：p g r k mod =)1mod())((1--=-p k xr M H s(3)将Sig(M ，k)=(M ，r ，s)作为签名，将(M ，r ，s)送给对方。

3.验证过程收信人收到(M ，r ，s)，先计算H(M)，并按下式验证签名p g r y M H s r mod )(=这是因为p g g g r y sk rx sk rx s r mod )(+==，由上式有)1mod()()(-=+p M H sk rx 。

在此方案中，对同一消息M ，由于随机数k 不同而有不同的签名值(M ，r ，s)。

三、EIGamal 加密算法的安全性分析很明显，EIGamal 加密算法的安全性等价于Diffie-Hdlman 体制的安全性。

虽然还没有完全证明破译ELGamal 签名体制等价于求解H(M)上的离散对数问题，但从可能的攻击方法来看，其破译方法大多都等价于求解H(M)上的离散对数问题。

破译签名体制，本质上就是试图从(M,r,s)中得到签名者的私用密钥x 。

假设给定一组明文{}...2,1:=i m r 及其相关的签名{}n i s r i i ,...,1:),(=，那么破译者可根据下式列出n 个方程组：())1mod()(-+=p sk rx M H但是n 个方程有n+1个未知数，n k k k ,...,,21，x ，故有无数组解。

因此，在k 互不相同的情况下，用此方法破译ELGamal 签名体制是不行的。

若从其他途径来攻击，如求解p g r y M H s r mod )(=方程来得到x ，其等价于求解H(M)上的离散数对问题。

另外，一种威胁EIGamal 签名体制的方法是假冒签名，这分为两种情况。

一种是假冒者有任一组明文H(M)，他想假冒别人的签名，但不知道别人的私用密钥，若想满足p g r y M H s r mod )(=这一关系式，只有构造一对(r ，s)，但现在还没有有效的算法解决这一问题。

另一种是假冒者已知一组合法明文及其对应的签名，那么他就能伪造另外一组合法的明文及签名。

假设伪造者已知的明文及签名为(M,r,s),那么他可构造另外一组(''',,s r M )如下：p y g r B A mod '= )1mod(/-''-=p B r s )1mod(/''--=p B r M A这里A 、B 是两整数，且gcd （B ，p-1）=1。

这一情况在其他签名体制中也存在，但假冒者想伪造任一组明文是不可能的。

这可以用限制明文的结构和采用均匀性较好的HASH 函数压缩明文来客服这一弱点。

公钥密码体制的安全强度一般等价于求解数学中某一难题，现在已知最好的求解离散对数问题和大数分解问题的算法时间复杂性为：)ln 69.0(exp m m O ，这里m 为公钥系统的密码长度。

因此，要保证EIGamal 体制的安全性，故其密钥长度（大素数p 的长度）不能低于RSA 中所用的密钥长度。

一般要100位以上的十进制整数。

在RSA 加密系统中，每两个用户之间就需要一对私用密钥和公开密钥，即需要产生两个大素数和运行密钥产生程序。

假设系统中有N 个用户，那么公钥表就需要2N 个大素数。

而在EIGamal 系统中，全系统额用户可共用统一的p 和g ，每个用户保留自己的私用密钥x ，然后将其公开密钥y 公布即可。

这不仅减少了系统密钥生成、分配、和管理的工作量，而且也提高了系统的维护性。

这一体制适合于用户较多的安全系统，例如银行资金转账系统等。

四、EIGamal 的选择明文攻击方案由于EIGamal 体制不能隐藏明文的二次剩余特性，因此它在不可区分性选择明文攻击（Indistinguish-ability under Chosen Plain text Attack ，ND-CPA ）下是不安全的.在该算法中，设定公开参数(g ，p)，g 是整数乘法群*p Z 的生成元.在这种 参数背景下，明文的二次剩余特性可以与对应的密文联系起来。

假设随机语言机O 为EIGamal 体制建立了(p,g,y)作为公钥材料，则由欧拉准]3[则，p QNR g ∈(即g 是一个模p 的非二次剩余)。

假设Alice 是一个ND-CPA 攻击者，他可以提交一条消息p QR m ∈0，另一条消息p QNR m ∈1. 设(21,c c)是从O 返回的密文时，则有⎪⎩⎪⎨⎧⎩⎨⎧==的概率的概率%50)(mod %50)(mod ),(mod 1021p m y p m y c p g c k k k 因为g 是*p Z 的生成元，因此)(mod 11p g p ≡-，根据欧拉准]3[则，如果p QR g ∈，即)(mod 12/)1(p g p ≡-与生成元的性质矛盾，因此p QNR g ∈.Alice 可以通过判定y 、1c、2c 的二次剩余特性，明确指出被加密的明文。

首先考虑p QR y ∈的情况，容易得到：p p p k QNR m QR m QR y ∈∈∈10,,，因此，当p QR c ∈2 时，被加密明文是0m ，当p Q N R c ∈2 时，被加密明文是1m ，对于p QNR y ∈的情况，需要分析1c，当p QR c ∈1 时，由于p QNR g ∈，因此k 一定是偶数，即p k QR y ∈，由p p QNR m QR m ∈∈10,，因此，当p QR c∈2 时，被加密明文是0m ，当p QNR c ∈2 时，被加密明文是1m ，当p Q N R c ∈1 时，k 一定是奇数，因此p k QNR y ∈，即1-=⎪⎪⎭⎫ ⎝⎛p y k ，由p QR m ∈0，p QNR m ∈1，可以得到1,110-=⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛p m p m ，因此，当p QR c∈2 时，即只有是()()111=-⨯-这种情况，所以，被加密明文是1m ，当p QNR c∈2 时，即是()()111-=-⨯-这种情况，因此被加密明文是0m . 总结如下：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧⎪⎪⎩⎪⎪⎨⎧⎩⎨⎧∈⎩⎨⎧∈∈⎩⎨⎧∈∈∈∈∈∈∈）是被加密明文（当）是被加密明文（当）是被加密明文（当）是被加密明文（当）是被加密明文（当）是被加密明文（当.m ,N ,N m ,y ,N ,21201212012120p p p p p p p p p p QR c R Q c m QNR c R Q c QR c m QR cQNR R Q cm QR cm QR y五、EIGamal 改进型算法及其安全性证明ElGamal 的语义攻击利用了明文的二次剩余特性, 如果限制该密码体制只工作在QRP 中, 那么ElGamal 的语义攻击就不会成功了.下面是对EIGamal 体制的一种修改。