ElGamal簽名方案的安全性分析與改進

1、收稿日期2007211226作者簡介蘆殿軍(19702,男,1992年大學(xué)畢業(yè),副教授,現(xiàn)主要從事代數(shù)組合與密碼學(xué)方面的教學(xué)與研究工作。El G amal 簽名方案的安全性分析與改進蘆殿軍,張秉儒(青海師范大學(xué)數(shù)學(xué)與信息科學(xué)系,青海西寧810008摘要通過對El G amal 簽名方案的描述,分析了兩種對El G amal 簽名體制的偽造攻擊方法和兩種條件偽造攻擊方法,提出了使用該體制的幾種失敗可能,且作了一些相應(yīng)的改進,提高了El G amal 簽名方案的運算效率。關(guān)鍵詞El Gamal 體制;El G amal 簽名方案;安全性分析;偽造攻擊中圖分類號TN911133文獻(xiàn)標(biāo)識碼A 文章編號

2、167321409(2008012N193202自1976年Diffie 和Hellman 發(fā)表了密碼學(xué)新方法之后,多種密碼算法相繼出現(xiàn),目前公認(rèn)比較安全和有效的公鑰算法體制主要有RSA 體制,離散對數(shù)體制及橢圓曲線體制等。它們具有數(shù)字簽名,認(rèn)證和鑒別等多種功能,并且保密性強,密鑰管理方便,特別適合于現(xiàn)代保密通訊的需要。而數(shù)字簽名作為一項重要的安全技術(shù),在保證數(shù)據(jù)的完整性,可用性,保密性,可控性方面,特別是在大型網(wǎng)絡(luò)安全通信中的密鑰分配,認(rèn)證以及電子商務(wù)系統(tǒng)中起著極其重要的作用。隨著電子商務(wù)的興起,如何有效地進行信息保護已成為一個研究熱點,而El Gamal 簽名方案就是實現(xiàn)信息保護的一種有效

3、手段,但在實際應(yīng)用中也存在一些不足。筆者分析了幾種對El Gamal 簽名體制的攻擊方法,作出了一些相應(yīng)的改進,以提高其運算效率。El Gamal 簽名體制1是由T 1El Gamal 在1985年提出的。其修正形式已被美國N IST 作為數(shù)字簽名標(biāo)準(zhǔn)DSS 2,同時它又是Rabin 體制3的一種變形。El Gamal 簽名方案像El Gamal 公鑰密碼體制一樣是非確定性的,這就意味著對任何給定的消息,有許多個有效的簽名,驗證算法必須能接受合法的有效簽名中的任何一個,其安全性依賴于計算有限域上離散對數(shù)這一難題。El Gamal 簽名方案描述如下:設(shè)p 是一個素數(shù),它滿足在Z p 中離散對數(shù)問

4、題是難解的,Z 3p 是一個本原元,P =Z 3p ,A =Z q Z q ,定義:K =(p ,a ,:=a (mod p 值p ,和是公開的,a 是保密的。對K =(p ,a ,和一個(秘密隨機數(shù)k ,定義:si g k (x ,k =(,=k mod p =(x -a k -1mod (p -11k q -1對x ,Z 3p 和Z p-1,定義:ver k (x ,=真x (mod p 1El G amal 簽名方案的安全性分析假設(shè)攻擊者(Oscar 在不知道a 的情況下企圖偽造一個給定消息x 的簽名。如果Oscar 選擇一個值,然后企圖找到相應(yīng)的,他必須計算離散對數(shù)log x -。另外

5、,他如果首先選擇,然后企圖找到,他就試圖“解”一個未知數(shù)的方程x (mod p ,這又是一個已知的沒有可行解法的問題,如果Oscar 選擇一個和,然后企圖解出x ,他將再次面臨離散對數(shù)問題log a 。因此,Oscar 利用這種方式不能簽名一個“隨機”消息,然而該方案不能排除某些特定的攻擊方法。111偽造攻擊1Oscar 同時選擇,和x 來簽名一個隨機消息:設(shè)i 和j (0i ,j p -2是整數(shù),且gcd (j ,p -1=1。利用逐步搜索法完成下列計算:391長江大學(xué)學(xué)報(自然科學(xué)版2008年3月第5卷第1期:理工Journal of Yangtze U niversity(N at Sc

6、i EditMar 12008,Vol 15No 11:Sci &Eng=i j mod p =-j -1mod (p -1x =-i j -1mod (p -1這里j -1是用模(p -1來計算的(所以我們需要j 和p -1互素。由于:a -j -1(mod p a (i j -j -1(mod p a -ij -1-(mod p a -ij -1-a (mod p -i j -1(mod p x (mod p 所以這對偽造的(,x 通過驗證,成為合法的簽名。112偽造攻擊2假設(shè)Oscar 截獲了合法簽名者Bob 所簽消息(,此時(,是消息x 的有效簽名。假設(shè)h ,i 和j(0h ,i ,j

7、 p -2是整數(shù),且gcd (h -j ,p -1=1,Oscar 作如下計算:=h i j mod p =(h -j -1mod (p -1x =(hx +i (h -j -1mod (p -1這里(h -j -1是模(p -1計算出來的。由于x (mod p 1,所以(,是x 的一個有效簽名。113條件偽造攻擊1假如Bo b 在簽名時泄露了隨機數(shù)k ,由于:=(x -a k -1mod (p -1k =(x -a mod (p -1a =(x -k -1mod (p -1此時計算a 是簡單的,一旦a 已知了,這個體制將被攻破且Oscar 能任意偽造簽名。114條件偽造攻擊2假如Bo b 使

8、用相同的k 值來簽名不同的兩個消息:對x 1簽名為(,1,對x 2簽名為(,2,則:1x 1(mod p 2x 2(mod p 于是有x 1-x 21-2(mod p ,由于=k mod p ,所以x 1-x 2k (1-2(mod p 。它等價于:x 1-x 2k (1-2(mod (p -1設(shè)d =gcd (1-2,p -1,因為d |p -1和d |1-2,所以d |(x 1-x 2。定義:x =x 1-x 2d =1-2d p =p -1d同余式變?yōu)?x k (mod p 因為gcd (,p =1,可以計算=(-1mod p ,那么模p 時k 的值為:k =x (mod p ,這就產(chǎn)生

9、了d 個候選k 值:k =x +ip (mod p 。對于某一個i ,0i d -1,當(dāng)然d 個候選值中,唯一正確的一個能通過k (mod p 確定。2方案改進對于偽造攻擊1和偽造攻擊2,雖然均可以產(chǎn)生有效的偽造簽名,但是在沒有先解離散對數(shù)問題時,從Oscar 的角度看并不能產(chǎn)生一個他自己選擇的消息的一個簽名,所以它們似乎并不代表對El Gamal 簽名方案的一個威脅4。211改進1對于條件偽造攻擊1和2,需要不斷更新隨機數(shù)k 的取值,才能避免方案失敗,對于頻繁的k 的更換,由于需要大量的求冪運算,使得方案計算效率不高,為此可以設(shè)計一種改進的方案,以避免每次求k -1。方案描述如下:Bob 選

10、擇Z 3p 是一個本原元,a 是一個滿足gcd (a ,p -1=1且=a (mod p 的秘密指數(shù)(0a p -2,密鑰K =(p ,a ,這里p ,和公開且a 是保密的,讓x Z p 是一個待簽名的消息,Bob 計算簽名:si g k (x ,k =(,=k mod p =(x -k a -1mod (p -1對于x ,Z 3p 和Z p-1,定義:ver k (x ,=真x (mod p 該方案只需進行一次求逆運算,因此在計算上較El Gamal 簽名方案效率更高。(下轉(zhuǎn)第225頁491長江大學(xué)學(xué)報(自然科學(xué)版2008年3月件。自主開發(fā)了地圖查詢控件,直接訪問各種GIS 數(shù)據(jù),可以與VC

11、 +、FoxPro 等結(jié)合開發(fā)前端業(yè)務(wù)處理系統(tǒng),實現(xiàn)地圖的顯示、即時打印、地圖與屬性空間數(shù)據(jù)雙向查詢等功能。將Internet 網(wǎng)絡(luò)技術(shù)應(yīng)用于GIS 上,使用IIS (Internet Informatio n Server 和ASP (Active Server Page 在互聯(lián)網(wǎng)提供數(shù)據(jù)查詢服務(wù),使得服務(wù)器方的數(shù)據(jù)動態(tài)訪問組件用于地理空間數(shù)據(jù)的動態(tài)模糊查詢具有可行性。4結(jié)語筆者闡述了基于Web GIS 地圖綜合知識的數(shù)據(jù)處理流程,提出了相應(yīng)可行性事例。重點對在線地圖綜合技術(shù)在Web 網(wǎng)絡(luò)環(huán)境下進行了系統(tǒng)性描述,并提出了該系統(tǒng)實現(xiàn)的可行性研究開發(fā)技術(shù),使地圖綜合數(shù)據(jù)基于網(wǎng)絡(luò)環(huán)境傳輸并實現(xiàn)地圖

12、可視化。該技術(shù)方法需要進一步完善之處是知識庫結(jié)構(gòu)中沒有考慮到相關(guān)在線地圖綜合中圖層要素知識的關(guān)聯(lián)性,故沒有對相關(guān)圖層要素之間的關(guān)聯(lián)性數(shù)據(jù)進行深入探究,這一問題即是后續(xù)研究的目標(biāo)。參考文獻(xiàn)1王家耀1空間信息系統(tǒng)原理M 1北京:科學(xué)出版社,20011112012王家耀,武芳1數(shù)字地圖自動制圖綜合原理與方法M 1北京:解放軍出版社,1997161513李琦1Web GIS 中地理空間Metadata 管理系統(tǒng)設(shè)計J 1中國圖像圖形學(xué)報,2000,5(A10:81281714宋關(guān)福1Web GIS -基于Internet 的地理信息系統(tǒng)J 1中國圖像圖形學(xué)報,1998,3(3:25125415閆浩文1

13、計算機地圖制圖原理與算法基礎(chǔ)M 1北京:科學(xué)出版社,2006120321116邊馥苓1GIS 地理信息系統(tǒng)原理和方法M 1北京:測繪出版社,1996115315817劉紀(jì)平1面向綜合應(yīng)用的空間數(shù)據(jù)管理方法探討與實踐J 1測繪學(xué)院學(xué)報,2001,18(4:30330618郭仁忠1空間分析M 1武漢:武漢測繪科技大學(xué)出版社,19971616919毋河海1地理數(shù)據(jù)庫系統(tǒng)M 1北京:測繪出版社,199112352381編輯易國華(上接第194頁212改進2由于以上分析的4種攻擊方法,可知El Gamal 簽名方案并不比離散對數(shù)問題有更多的安全性,所以就必須使用大的模數(shù)p ,無疑p 將至少有512比特,

14、且許多人認(rèn)為為了提供進一步的安全性,需要p 的長度為1024比特。然而,甚至一個512比特的模數(shù)也將導(dǎo)致簽名有1024比特。對于一個潛在的應(yīng)用,它們中的許多都涉及到靈巧卡的使用,此時一個更短的簽名是需要的。因此我們可以進一步作如下改進:設(shè)p 是一個512比特的素數(shù),它滿足Z p 中離散對數(shù)問題是難處理的,且q 是一個整除p -1的160比特的素數(shù),Z 3p 是模p 的q 次單位根,P =Z 3p ,A =Z q Z q ,定義:K =(p ,q ,a ,:=a (mod p 值p ,q ,和公開,值a 是保密的。對K =(p ,q ,a ,和一個(秘密隨機數(shù)k ,定義:si g k (x ,k

15、 =(,=(k mod p mod q =(x +k a -1mod q 1k q -1對x Z 3p ,Z q ,驗證通過完成下列計算進行:e 1=x-1mod q e 2=-1mod q ver k (x ,=真(e 1e 2mod p mod q =該方法修改了El Gamal 方案,使得簽名160比特消息產(chǎn)生一個320比特的簽名,但計算使用了512比特的模p 。同時該方法是在Z 3p 的大小為2160的子群中這樣作的。所以計算效率被大大提高。參考文獻(xiàn)1Mitchell C ,Piper F ,Wild P 1Digital signatures A 1In Contemporary C

16、ryptology 1The Science of Information Integrity C1IEEEPress ,1992132537812National Bureau of Standards FIPS Publication 186,Digital signatures standard S13Rabin M 1Digitized signatures and public 2key functions as intractable as factorization A 1MIT Laboratory for Computer ScienceTechnical Report C1

17、19791LCS/TR 221214斯廷森D 1密碼學(xué)理論與實踐M 1張文政譯1成都:電子科技大學(xué)出版社,199711401501編輯洪云飛522第5卷第1期:理工高三營:基于Web GIS 模式在線地圖綜合技術(shù)的研究與開發(fā)up p rogram,including signed point s of p rogram ent rance,exceptional vector setting,initialization of software and hardware,mode changing of p rocessor,enable interrut and task attemperi

18、ng1In addi2 tion,t he so urce programme of main part s is annotated detailedly1K ey w ords:Nucleus PL U;t ransplant;start up p rogram193Analysis and Improvement on the Security of El G amal Signature SchemeLU Dian2jun,Zhang Bing2ru(Qinghai N ormal Universit y,X ining810008Abstract:The paper analyzes

19、 two ways of impersonation attack upon El Gamal crypto system and two ways of conditional impersonation attack by describing El Gamal signat ure scheme it self1It p ut s for2 ward several failing possibilities and makes relevant improvement1It improves t he operation effi2 ciency of t he scheme1K ey

20、 w ords:El G amal cryptosystem;El G amal signature scheme;analysis of security;impersonation attack195The R esearch on Illumination Algorithm of Virtual R eality T echniquesWU Wen2zhen,LI Quan2Zhong(Daqing Pet roleum I nstit ute,Daqing163318Abstract:Realistic grap hics for virt ual reality technolog

21、y is t he highlight of research at home and a2 broad,t he illuminatio n model mapping and it s application of t he algorit hms are t he key techniques to achieve realistic scenes1In t his paper,t he aut hor introduces t he illumination model and t he algo2 rit hms,focuses o n ray t racing algorit hm

22、s and bounding box technology of t he global illumination model realized in t he oil field virt ual reality system and it achieves good result s1K ey w ords:virt ue reality;illumination;ray2tracing;radio sity198Design and Implementation of Virtual Simulation System for Safety Operation in Combined S

23、tation Wu X iu2qin,Liu T ie2liang,Wu X iu2ying(Daqi ng Pet roleum I nstit ute,Daqing163318Abstract:This paper introduces t he design and implementation of combined station safety operation simulation training system and discusses t he establishment of virt ual scenes,t he interaction wit h t he virt

24、 ual environment,t he collision detection and encryption technology etc1The f unctions are carried out in system such as t he demonst ration of t he correct operation;imitate operation for practice and t he roaming etc1The application of the system not only improves the security of oil production ma

25、nage2 ment and practice,but also saves the cost of training,reduces the equipment damage and injury to persons and solves the problem on the safety operation of the oilfield training cost,safety and effectiveness1K ey w ords:virt ual reality;simulation training;security operation;interaction222Study and Development on Online C artographic G eneralization T echnique B ased on WebGIS PatternG AO San2ying(L anz hou J i aotong Universit y,L anz hou730070Abstract:The realization of online cartograp hic generaliz