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

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

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

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

5、,他如果首先選擇,然后企圖找到,他就試圖“解”一個(gè)未知數(shù)的方程x (mod p ,這又是一個(gè)已知的沒(méi)有可行解法的問(wèn)題,如果Oscar 選擇一個(gè)和,然后企圖解出x ,他將再次面臨離散對(duì)數(shù)問(wèn)題log a 。因此,Oscar 利用這種方式不能簽名一個(gè)“隨機(jī)”消息,然而該方案不能排除某些特定的攻擊方法。111偽造攻擊1Oscar 同時(shí)選擇,和x 來(lái)簽名一個(gè)隨機(jī)消息:設(shè)i 和j (0i ,j p -2是整數(shù),且gcd (j ,p -1=1。利用逐步搜索法完成下列計(jì)算:391長(zhǎng)江大學(xué)學(xué)報(bào)(自然科學(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來(lái)計(jì)算的(所以我們需要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 所以這對(duì)偽造的(,x 通過(guò)驗(yàn)證,成為合法的簽名。112偽造攻擊2假設(shè)Oscar 截獲了合法簽名者Bob 所簽消息(,此時(shí)(,是消息x 的有效簽名。假設(shè)h ,i 和j(0h ,i ,j

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

8、用相同的k 值來(lái)簽名不同的兩個(gè)消息:對(duì)x 1簽名為(,1,對(duì)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 。它等價(jià)于:x 1-x 2k (1-2(mod (p -1設(shè)d =gcd (1-2,p -1,因?yàn)閐 |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 因?yàn)間cd (,p =1,可以計(jì)算=(-1mod p ,那么模p 時(shí)k 的值為:k =x (mod p ,這就產(chǎn)生

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

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

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

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

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

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

15、 =(,=(k mod p mod q =(x +k a -1mod q 1k q -1對(duì)x Z 3p ,Z q ,驗(yàn)證通過(guò)完成下列計(jì)算進(jìn)行:e 1=x-1mod q e 2=-1mod q ver k (x ,=真(e 1e 2mod p mod q =該方法修改了El Gamal 方案,使得簽名160比特消息產(chǎn)生一個(gè)320比特的簽名,但計(jì)算使用了512比特的模p 。同時(shí)該方法是在Z 3p 的大小為2160的子群中這樣作的。所以計(jì)算效率被大大提高。參考文獻(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é)理論與實(shí)踐M 1張文政譯1成都:電子科技大學(xué)出版社,199711401501編輯洪云飛522第5卷第1期:理工高三營(yíng):基于Web GIS 模式在線(xiàn)地圖綜合技術(shù)的研究與開(kāi)發(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