李淑敬，李林國

（阜陽師范學院信息工程學院，安徽阜陽 236041）

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

李淑敬，李林國

（阜陽師范學院信息工程學院，安徽阜陽 236041）

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

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

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

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

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

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

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

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

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

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

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

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

（6）B收到消息驗證過程.首先驗證ya×ab（mod p）＝gM（mod p）是否成立，若成立說明消息是簽名方A發(fā)送，不成立說明消息不是A發(fā)送.驗證的同時一定要檢驗是否滿足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）為數(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）素數(shù)p的本原根（也稱本原元）定義.如果a是素數(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)成一個模n的簡化剩余系.

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

2.2 ElGamal算法安全分析

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

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

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

3.1 密鑰生成過程

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

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

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

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

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

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

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

圖1 b的生成過程

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

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

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

3.2 簽名與驗證過程

3.2.1 簽名過程 隨機生成整數(shù)k，用輾轉(zhuǎn)相除法來判斷是否與p－1互質(zhì)，如果不互質(zhì)，再隨機生成k直到與p－1互質(zhì).通過調(diào)用高次冪運算highcm函數(shù)計算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次調(diào)用高次冪運算highcm函數(shù)得到相應(yīng)的值比如為GM1，然后再次調(diào)用highcm函數(shù)計算gMmod p比如賦值為GM2.判斷GM1和GM2是否相等，如果相等，驗證簽名成功，否則證實是偽造的簽名.

3.3 實現(xiàn)界面

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

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

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

4 結(jié)語

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

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

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

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

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

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

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

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

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

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

（責任編輯 陳炳權(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

阜陽師范學院科研資助項目（2009FSKJ16）；安徽省青年人才基金資助項目（2010SQTL196）；安徽省自然科學基金資助項目（KJ2012B138）

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