基于Visual Foxpro的EIGamal數(shù)字簽名算法＊

李淑敬，李林國(guó)

（阜陽(yáng)師范學(xué)院信息工程學(xué)院，安徽阜陽(yáng) 236041）

基于Visual Foxpro的EIGamal數(shù)字簽名算法＊

李淑敬，李林國(guó)

（阜陽(yáng)師范學(xué)院信息工程學(xué)院，安徽阜陽(yáng) 236041）

數(shù)字簽名的使用越來(lái)越廣泛，其主要的實(shí)現(xiàn)方法是公鑰密碼算法.ElGamal算法是一種比較常用的公鑰密碼算法，既可以用于加密又可以用于簽名，具有生成速度快、簽名驗(yàn)證簡(jiǎn)單的特點(diǎn).VFP（Visual Foxpro）是一種使用比較廣泛的面向?qū)ο蟮臄?shù)據(jù)庫(kù)設(shè)計(jì)系統(tǒng)，基于VFP的簽名實(shí)現(xiàn)方法比較少.介紹ElGamal數(shù)字簽名算法在VFP中的實(shí)現(xiàn)，闡述了El-Gamal數(shù)字簽名算法的原理，詳細(xì)介紹了算法的實(shí)現(xiàn)過(guò)程，最后給出在VFP中ElGamal數(shù)字簽名的實(shí)現(xiàn)界面.

EIGamal；數(shù)字簽名；Visual Foxpro

隨著網(wǎng)絡(luò)信息時(shí)代的發(fā)展，大量的電子數(shù)據(jù)通過(guò)網(wǎng)絡(luò)被傳輸?shù)绞澜绺鞯?，這使得信息的安全問(wèn)題日顯突出.簽名問(wèn)題就是出現(xiàn)的一個(gè)新的課題，數(shù)字簽名［1］是和手寫(xiě)簽名具有同等法律效力的一種電子簽名，能有效地實(shí)現(xiàn)簽名認(rèn)證、防偽造、防抵賴.

數(shù)字簽名的概念最初是由Diffie和Hellman提出，其思想是讓每個(gè)用戶公布1個(gè)公鑰用于驗(yàn)證簽名，同時(shí)還保存1個(gè)私鑰用于產(chǎn)生簽名.因此數(shù)字簽名的實(shí)現(xiàn)主要依賴于公鑰加密算法，ElGamal算法［2］由T.EIGamal在1984年提出的公鑰密碼體制，是在得到廣泛應(yīng)用的公鑰密碼算法RSA算法提出之后在密碼協(xié)議中有著大量應(yīng)用的一種公開(kāi)密鑰算法，它既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于計(jì)算有限域上離散對(duì)數(shù)這一難題.在加密過(guò)程中，生成的密文長(zhǎng)度是明文的2倍，且每次加密后都會(huì)在密文中生成一個(gè)隨機(jī)數(shù)k.

VFP（Visual Foxpro）是一種面向?qū)ο蟮臄?shù)據(jù)庫(kù)設(shè)計(jì)系統(tǒng)，使用比較廣泛，既能創(chuàng)建數(shù)據(jù)庫(kù)又能實(shí)現(xiàn)面向用戶的對(duì)象界面.但是在VFP實(shí)現(xiàn)數(shù)字簽名的算法很少，筆者提出了實(shí)現(xiàn)數(shù)字簽名的基于VFP的EIGamal算法，并驗(yàn)證了該算法的可行性.

1 ElGamal數(shù)字簽名算法

ElGamal數(shù)字簽名［3］方案是非確定性的，意味著對(duì)任何給定的信息可以產(chǎn)生許多有效的簽名［4］，并且驗(yàn)證算法能夠?qū)⑺鼈冎械娜魏我粋€(gè)作為可信的簽名而加以接受，ElGamal用于數(shù)字簽名時(shí)其通用算法［5］如下：

（1）密鑰對(duì)的產(chǎn)生.生成1個(gè)大素?cái)?shù)p，使得求解離散對(duì)數(shù)問(wèn)題在有限域Zp（只含有有限個(gè)元素的域稱為有限域.整數(shù)模p的剩余類域是Zp＝｛x｜gcd（x，p）＝1，0≤x＜p｝）上是困難的；

（2）選擇有限域Zp中的1個(gè)本原元g；

（3）隨機(jī)生成1個(gè)整數(shù)x，且0≤x＜p－1，計(jì)算y＝gx（mod p）；

（4）則公鑰為（y，g，p），私鑰為x，其中公鑰（y，g，p）可由一組用戶共享；

（5）簽名過(guò)程.A發(fā)送消息，被簽信息為M，首先選擇1個(gè)隨機(jī)數(shù)k（其中k與p－1互質(zhì)），計(jì)算a＝gk（mod p），通過(guò)M＝x×a＋k×b（mod p－1）求解得到b，簽名就是（a，b）.隨機(jī)數(shù)k須丟棄，A將消息和簽名一起打包發(fā)送給B.

（6）B收到消息驗(yàn)證過(guò)程.首先驗(yàn)證ya×ab（mod p）＝gM（mod p）是否成立，若成立說(shuō)明消息是簽名方A發(fā)送，不成立說(shuō)明消息不是A發(fā)送.驗(yàn)證的同時(shí)一定要檢驗(yàn)是否滿足1≤a＜p，否則簽名容易偽造.其驗(yàn)證的原理：如果（a，b）是M的簽名，則x×a＋k×b＝Mmod（p－1），從而有ya×ab≡gx×a×gk×b≡gx×a＋k×b≡gMmod p，因而簽名得到驗(yàn)證［5］.

2 ElGamal算法安全分析

2.1 本原根

如果（a，b）為數(shù)a和數(shù)b的最大公因子，則a≡b（mod p）為a和b模p同余.設(shè)（a，p）＝1，滿足am≡1（mod p）的最小正整數(shù)m叫作a模p的階，模p階為p－1的整數(shù)a叫作模p的本原根.

（1）素?cái)?shù)p的本原根（也稱本原元）定義.如果a是素?cái)?shù)p的本原根，則數(shù)amod p，a2mod p，...，ap－1mod p是不同的，并且包含1到p－1之間所有整數(shù)的某種排列.即若a為模p的本原根，則a，a的平方，a的3次方，......，a的p－1次方模n的余數(shù)互不相同，構(gòu)成一個(gè)模n的簡(jiǎn)化剩余系.

（2）求本原根［7］的方法.從2開(kāi)始，逐個(gè)整數(shù)依次當(dāng)作本原根g，計(jì)算S＝｛gmod p，g2modp，...，gp－1mod p｝，確認(rèn)集合S是否是Zp的一個(gè)置換，如果是，則g就是群Zp的一個(gè)本原根；如果不是，則集合里必有重復(fù)元素，g就不是本原根，如此判斷下去，直到找到為止.

2.2 ElGamal算法安全分析

ElGamal簽名［6］的安全性依賴于乘法群上的離散對(duì)數(shù)計(jì)算，素?cái)?shù)p必須足夠大，且p－1至少包含1個(gè)大素?cái)?shù)因子以抵抗攻擊.M一般都應(yīng)采用信息的HASH值（如SHA算法）.在簽名前先使用雜湊函數(shù)對(duì)消息做變換，由于雜湊函數(shù)的抗碰撞性，使得對(duì)手很難對(duì)一個(gè)真正的消息進(jìn)行偽造簽名，從而避免了偽造消息攻擊的可能性.另外，ElGamal的安全性依賴于p和g，若選取不當(dāng)則簽名容易偽造，應(yīng)保證g對(duì)于p－1的大素?cái)?shù)因子不可約，所以選取的g為p的本原根.

在簽名和發(fā)送的整個(gè)過(guò)程中，秘密密鑰x和秘密隨機(jī)數(shù)k決不能暴露，一旦暴露整個(gè)算法就被攻破.此外k只能用于1次簽名，如果用于2次或2次以上簽名，將會(huì)使算法的安全性遭受巨大威脅，甚至很容易被別有用心的人攻破.

3 簽名的具體實(shí)現(xiàn)

3.1 密鑰生成過(guò)程

（1）大素?cái)?shù)p的生成方法.隨機(jī)生成一個(gè)比較大的數(shù)，然后判斷其是否為素?cái)?shù)，如果是則保留，不是則再生成.

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

①定義2個(gè)數(shù)組by1［10 000］，byg［10 000］，且byg［10 000］＝｛1｝；

②設(shè)置for i＝1to p，將數(shù)組初始化為by1［i］＝i；

③隨機(jī)生成一個(gè)小于p的數(shù)g；

④設(shè)置循環(huán)for i＝1to p－1，對(duì)數(shù)組byg［10 000］重新進(jìn)行賦值：byg［i］＝mod（gi，p）；

⑤對(duì)數(shù)組byg前p－1個(gè)數(shù)按照從小到大的順序進(jìn)行排序；

圖1 b的生成過(guò)程

⑥設(shè)置循環(huán)，分別比較by1數(shù)組和byg數(shù)組前p－1個(gè)對(duì)應(yīng)相同下標(biāo)的數(shù)值是否相等，如果相等，程序結(jié)束，返回g的值，g就是p的一個(gè)本原根；如果不等，則退出循環(huán)，執(zhí)行g(shù)＝g＋1，如果g＜p，返回到步驟④，否則返回步驟③.

（3）x，y的生成.隨機(jī)生成一個(gè)滿足0≤x＜p－1的整數(shù)x，通過(guò)調(diào)用高次冪運(yùn)算函數(shù)highcm（g，x，p）得到y(tǒng).highcm的函數(shù)代碼為：

由此生成的公鑰（y，g，p）在網(wǎng)絡(luò)中發(fā)布，可以讓其他用戶看到，而私鑰是x，只能由用戶自己秘密保存.

3.2 簽名與驗(yàn)證過(guò)程

3.2.1 簽名過(guò)程 隨機(jī)生成整數(shù)k，用輾轉(zhuǎn)相除法來(lái)判斷是否與p－1互質(zhì)，如果不互質(zhì)，再隨機(jī)生成k直到與p－1互質(zhì).通過(guò)調(diào)用高次冪運(yùn)算highcm函數(shù)計(jì)算a，b的生成過(guò)程為如圖1所示，得到的簽名就是（a，b）.

3.2.2 驗(yàn)證過(guò)程 先檢驗(yàn)是否滿足1≤a＜p，然后計(jì)算ya×ab（mod p）.由于ya×ab（mod p）≡ya（mod p）×ab（mod p），所以在計(jì)算ya（mod p）和ab（mod p）時(shí)需要2次調(diào)用高次冪運(yùn)算highcm函數(shù)得到相應(yīng)的值比如為GM1，然后再次調(diào)用highcm函數(shù)計(jì)算gMmod p比如賦值為GM2.判斷GM1和GM2是否相等，如果相等，驗(yàn)證簽名成功，否則證實(shí)是偽造的簽名.

3.3 實(shí)現(xiàn)界面

EIGamal算法在VFP中實(shí)現(xiàn)數(shù)字簽名的界面如圖2所示，用戶在點(diǎn)擊“生成公鑰和私鑰”按鈕，生成密鑰對(duì)后即可輸入明文，然后點(diǎn)擊“簽名”即可得到（a，b）的簽名.在檢驗(yàn)a是否小于p后，點(diǎn)擊“驗(yàn)證”得到的數(shù)據(jù)和點(diǎn)擊“計(jì)算”得到的數(shù)據(jù)進(jìn)行比較，如果相等說(shuō)明是用戶簽名，如果不相等說(shuō)明簽名被偽造.該界面可以進(jìn)一步改進(jìn)，其中“明文”可以是消息生成的摘要，而本實(shí)驗(yàn)的明文是由用戶手動(dòng)輸入的數(shù)據(jù).

由此可見(jiàn)，EIGamal數(shù)字簽名方案是一種有效、安全的數(shù)字簽名方案，本文提出的基于EIGamal的數(shù)字簽名用戶認(rèn)證方案具有生成過(guò)程簡(jiǎn)單、簽名驗(yàn)證速度快的優(yōu)點(diǎn)，適合用于對(duì)數(shù)據(jù)的簽名認(rèn)證.

圖2 VFP中EIGamal數(shù)字簽名實(shí)現(xiàn)界面

4 結(jié)語(yǔ)

介紹了EIGamal數(shù)字簽名算法，給出了在VFP中使用該算法實(shí)現(xiàn)數(shù)字簽名的詳細(xì)過(guò)程和實(shí)現(xiàn)界面.目前離散對(duì)數(shù)問(wèn)題尚未解決，所以EIGamal算法是目前比較安全的數(shù)字簽名算法，該方法相比于RSA算法實(shí)現(xiàn)過(guò)程簡(jiǎn)單，實(shí)用性強(qiáng).

［1］ 李淑敬，李林國(guó).基于PKI數(shù)字簽名在校園網(wǎng)中的設(shè)計(jì)方案［J］.微計(jì)算機(jī)信息，2012，28（10）：369.

［2］ 孫金青，孫艷蕊，袁喜鳳，等.可轉(zhuǎn)化的基于EIGamal環(huán)簽名方案［J］.微計(jì)算機(jī)信息，2008，24（4－3）：49－50.

［3］ 李 濱.EIGamal簽名方案的安全性分析及其改進(jìn)［J］.西南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，32（2）：376－379.

［4］ 何少芳.基于EIGamal加密算法的非對(duì)稱數(shù)字指紋體制［J］.現(xiàn)代電子技術(shù)，2010（3）：47－48.

［5］ 許 倩.代理盲簽名理論及其在電子現(xiàn)金系統(tǒng)中的研究與應(yīng)用［D］.廣州：華南理工大學(xué)電子與信息學(xué)院，2010.

［6］ 鄧從政.EIGamal數(shù)字簽名系統(tǒng)的一種偽簽名算法及其安全性分析［J］.成都大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，25（4）：284－286.

［7］ 余姜德，商 林，于志平.EIGamal加密體制在軟件保護(hù)技術(shù)中的應(yīng)用［J］.計(jì)算機(jī)與現(xiàn)代化，2005（5）：86－88.

［8］ 張 勇.用VC程序求有限域的本原元及其應(yīng)用［J］.河北北方學(xué)院學(xué)報(bào)：自然科學(xué)版，2009，25（5）：15－17.

［9］ 尹少平.密鑰交換協(xié)議中本原根的快速確定方法及其實(shí)現(xiàn)［J］.微計(jì)算機(jī)信息，2006，22（8－3）：101－103.

（責(zé)任編輯 陳炳權(quán)）

Realization of EIGamal Digital Signature in VFP

LI Shu-jing，LI Lin-guo
（College of Information Engineering，F(xiàn)uyang Teachers College，F(xiàn)uyang 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

阜陽(yáng)師范學(xué)院科研資助項(xiàng)目（2009FSKJ16）；安徽省青年人才基金資助項(xiàng)目（2010SQTL196）；安徽省自然科學(xué)基金資助項(xiàng)目（KJ2012B138）

李淑敬（1981－），女，山東聊城人，阜陽(yáng)師范學(xué)院講師，碩士研究生，主要從事網(wǎng)絡(luò)安全研究.