李淑敬，李林国

（阜阳师范学院信息工程学院，安徽阜阳 236041）

基于Visual Foxpro的EIGamal数字签名算法＊

李淑敬，李林国

（阜阳师范学院信息工程学院，安徽阜阳 236041）

数字签名的使用越来越广泛，其主要的实现方法是公钥密码算法.ElGamal算法是一种比较常用的公钥密码算法，既可以用于加密又可以用于签名，具有生成速度快、签名验证简单的特点.VFP（Visual Foxpro）是一种使用比较广泛的面向对象的数据库设计系统，基于VFP的签名实现方法比较少.介绍ElGamal数字签名算法在VFP中的实现，阐述了El-Gamal数字签名算法的原理，详细介绍了算法的实现过程，最后给出在VFP中ElGamal数字签名的实现界面.

EIGamal；数字签名；Visual Foxpro

随着网络信息时代的发展，大量的电子数据通过网络被传输到世界各地，这使得信息的安全问题日显突出.签名问题就是出现的一个新的课题，数字签名［1］是和手写签名具有同等法律效力的一种电子签名，能有效地实现签名认证、防伪造、防抵赖.

数字签名的概念最初是由Diffie和Hellman提出，其思想是让每个用户公布1个公钥用于验证签名，同时还保存1个私钥用于产生签名.因此数字签名的实现主要依赖于公钥加密算法，ElGamal算法［2］由T.EIGamal在1984年提出的公钥密码体制，是在得到广泛应用的公钥密码算法RSA算法提出之后在密码协议中有着大量应用的一种公开密钥算法，它既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题.在加密过程中，生成的密文长度是明文的2倍，且每次加密后都会在密文中生成一个随机数k.

VFP（Visual Foxpro）是一种面向对象的数据库设计系统，使用比较广泛，既能创建数据库又能实现面向用户的对象界面.但是在VFP实现数字签名的算法很少，笔者提出了实现数字签名的基于VFP的EIGamal算法，并验证了该算法的可行性.

1 ElGamal数字签名算法

ElGamal数字签名［3］方案是非确定性的，意味着对任何给定的信息可以产生许多有效的签名［4］，并且验证算法能够将它们中的任何一个作为可信的签名而加以接受，ElGamal用于数字签名时其通用算法［5］如下：

（1）密钥对的产生.生成1个大素数p，使得求解离散对数问题在有限域Zp（只含有有限个元素的域称为有限域.整数模p的剩余类域是Zp＝｛x｜gcd（x，p）＝1，0≤x＜p｝）上是困难的；

（2）选择有限域Zp中的1个本原元g；

（3）随机生成1个整数x，且0≤x＜p－1，计算y＝gx（mod p）；

（4）则公钥为（y，g，p），私钥为x，其中公钥（y，g，p）可由一组用户共享；

（5）签名过程.A发送消息，被签信息为M，首先选择1个随机数k（其中k与p－1互质），计算a＝gk（mod p），通过M＝x×a＋k×b（mod p－1）求解得到b，签名就是（a，b）.随机数k须丢弃，A将消息和签名一起打包发送给B.

（6）B收到消息验证过程.首先验证ya×ab（mod p）＝gM（mod p）是否成立，若成立说明消息是签名方A发送，不成立说明消息不是A发送.验证的同时一定要检验是否满足1≤a＜p，否则签名容易伪造.其验证的原理：如果（a，b）是M的签名，则x×a＋k×b＝Mmod（p－1），从而有ya×ab≡gx×a×gk×b≡gx×a＋k×b≡gMmod p，因而签名得到验证［5］.

2 ElGamal算法安全分析

2.1 本原根

如果（a，b）为数a和数b的最大公因子，则a≡b（mod p）为a和b模p同余.设（a，p）＝1，满足am≡1（mod p）的最小正整数m叫作a模p的阶，模p阶为p－1的整数a叫作模p的本原根.

（1）素数p的本原根（也称本原元）定义.如果a是素数p的本原根，则数amod p，a2mod p，...，ap－1mod p是不同的，并且包含1到p－1之间所有整数的某种排列.即若a为模p的本原根，则a，a的平方，a的3次方，......，a的p－1次方模n的余数互不相同，构成一个模n的简化剩余系.

（2）求本原根［7］的方法.从2开始，逐个整数依次当作本原根g，计算S＝｛gmod p，g2modp，...，gp－1mod p｝，确认集合S是否是Zp的一个置换，如果是，则g就是群Zp的一个本原根；如果不是，则集合里必有重复元素，g就不是本原根，如此判断下去，直到找到为止.

2.2 ElGamal算法安全分析

ElGamal签名［6］的安全性依赖于乘法群上的离散对数计算，素数p必须足够大，且p－1至少包含1个大素数因子以抵抗攻击.M一般都应采用信息的HASH值（如SHA算法）.在签名前先使用杂凑函数对消息做变换，由于杂凑函数的抗碰撞性，使得对手很难对一个真正的消息进行伪造签名，从而避免了伪造消息攻击的可能性.另外，ElGamal的安全性依赖于p和g，若选取不当则签名容易伪造，应保证g对于p－1的大素数因子不可约，所以选取的g为p的本原根.

在签名和发送的整个过程中，秘密密钥x和秘密随机数k决不能暴露，一旦暴露整个算法就被攻破.此外k只能用于1次签名，如果用于2次或2次以上签名，将会使算法的安全性遭受巨大威胁，甚至很容易被别有用心的人攻破.

3 签名的具体实现

3.1 密钥生成过程

（1）大素数p的生成方法.随机生成一个比较大的数，然后判断其是否为素数，如果是则保留，不是则再生成.

（2）为了提高程序的安全性，本原根的生成步骤为：

①定义2个数组by1［10 000］，byg［10 000］，且byg［10 000］＝｛1｝；

②设置for i＝1to p，将数组初始化为by1［i］＝i；

③随机生成一个小于p的数g；

④设置循环for i＝1to p－1，对数组byg［10 000］重新进行赋值：byg［i］＝mod（gi，p）；

⑤对数组byg前p－1个数按照从小到大的顺序进行排序；

图1 b的生成过程

⑥设置循环，分别比较by1数组和byg数组前p－1个对应相同下标的数值是否相等，如果相等，程序结束，返回g的值，g就是p的一个本原根；如果不等，则退出循环，执行g＝g＋1，如果g＜p，返回到步骤④，否则返回步骤③.

（3）x，y的生成.随机生成一个满足0≤x＜p－1的整数x，通过调用高次幂运算函数highcm（g，x，p）得到y.highcm的函数代码为：

由此生成的公钥（y，g，p）在网络中发布，可以让其他用户看到，而私钥是x，只能由用户自己秘密保存.

3.2 签名与验证过程

3.2.1 签名过程 随机生成整数k，用辗转相除法来判断是否与p－1互质，如果不互质，再随机生成k直到与p－1互质.通过调用高次幂运算highcm函数计算a，b的生成过程为如图1所示，得到的签名就是（a，b）.

3.2.2 验证过程 先检验是否满足1≤a＜p，然后计算ya×ab（mod p）.由于ya×ab（mod p）≡ya（mod p）×ab（mod p），所以在计算ya（mod p）和ab（mod p）时需要2次调用高次幂运算highcm函数得到相应的值比如为GM1，然后再次调用highcm函数计算gMmod p比如赋值为GM2.判断GM1和GM2是否相等，如果相等，验证签名成功，否则证实是伪造的签名.

3.3 实现界面

EIGamal算法在VFP中实现数字签名的界面如图2所示，用户在点击“生成公钥和私钥”按钮，生成密钥对后即可输入明文，然后点击“签名”即可得到（a，b）的签名.在检验a是否小于p后，点击“验证”得到的数据和点击“计算”得到的数据进行比较，如果相等说明是用户签名，如果不相等说明签名被伪造.该界面可以进一步改进，其中“明文”可以是消息生成的摘要，而本实验的明文是由用户手动输入的数据.

由此可见，EIGamal数字签名方案是一种有效、安全的数字签名方案，本文提出的基于EIGamal的数字签名用户认证方案具有生成过程简单、签名验证速度快的优点，适合用于对数据的签名认证.

图2 VFP中EIGamal数字签名实现界面

4 结语

介绍了EIGamal数字签名算法，给出了在VFP中使用该算法实现数字签名的详细过程和实现界面.目前离散对数问题尚未解决，所以EIGamal算法是目前比较安全的数字签名算法，该方法相比于RSA算法实现过程简单，实用性强.

［1］ 李淑敬，李林国.基于PKI数字签名在校园网中的设计方案［J］.微计算机信息，2012，28（10）：369.

［2］ 孙金青，孙艳蕊，袁喜凤，等.可转化的基于EIGamal环签名方案［J］.微计算机信息，2008，24（4－3）：49－50.

［3］ 李 滨.EIGamal签名方案的安全性分析及其改进［J］.西南民族大学学报：自然科学版，2006，32（2）：376－379.

［4］ 何少芳.基于EIGamal加密算法的非对称数字指纹体制［J］.现代电子技术，2010（3）：47－48.

［5］ 许 倩.代理盲签名理论及其在电子现金系统中的研究与应用［D］.广州：华南理工大学电子与信息学院，2010.

［6］ 邓从政.EIGamal数字签名系统的一种伪签名算法及其安全性分析［J］.成都大学学报：自然科学版，2006，25（4）：284－286.

［7］ 余姜德，商 林，于志平.EIGamal加密体制在软件保护技术中的应用［J］.计算机与现代化，2005（5）：86－88.

［8］ 张 勇.用VC程序求有限域的本原元及其应用［J］.河北北方学院学报：自然科学版，2009，25（5）：15－17.

［9］ 尹少平.密钥交换协议中本原根的快速确定方法及其实现［J］.微计算机信息，2006，22（8－3）：101－103.

（责任编辑 陈炳权）

Realization of EIGamal Digital Signature in VFP

LI Shu-jing，LI Lin-guo
（College of Information Engineering，Fuyang Teachers College，Fuyang 236041，Anhui China）

The digital signature is realized maily by the symmetric encryption algorithm.ElGamal algorithm，a commonly used symmetric encryption algorithm，is widly used in the digital signature and the encryption，with the advantages of fast generation and simple signature verification.Visual Foxpro is a widdely-applied targe-oriented databse designing system.In this paper the realization of ElGamal digital signature algorithm is detailedly introduced，and the course and interface of ElGamal digital signature in VFP is described.

ElGamal algorithm；digital signature；visual foxpro

TP309.2

A

10.3969／j.issn.1007－2985.2013.05.010

1007－2985（2013）05－0042－03

2013－06－12

阜阳师范学院科研资助项目（2009FSKJ16）；安徽省青年人才基金资助项目（2010SQTL196）；安徽省自然科学基金资助项目（KJ2012B138）

李淑敬（1981－），女，山东聊城人，阜阳师范学院讲师，硕士研究生，主要从事网络安全研究.