ElGamal签名方案的安全性分析与改进

1、收稿日期2007211226作者简介芦殿军(19702,男,1992年大学毕业,副教授,现主要从事代数组合与密码学方面的教学与研究工作。El G amal 签名方案的安全性分析与改进芦殿军,张秉儒(青海师范大学数学与信息科学系,青海西宁810008摘要通过对El G amal 签名方案的描述,分析了两种对El G amal 签名体制的伪造攻击方法和两种条件伪造攻击方法,提出了使用该体制的几种失败可能,且作了一些相应的改进,提高了El G amal 签名方案的运算效率。关键词El Gamal 体制;El G amal 签名方案;安全性分析;伪造攻击中图分类号TN911133文献标识码A 文章编号

2、167321409(2008012N193202自1976年Diffie 和Hellman 发表了密码学新方法之后,多种密码算法相继出现,目前公认比较安全和有效的公钥算法体制主要有RSA 体制,离散对数体制及椭圆曲线体制等。它们具有数字签名,认证和鉴别等多种功能,并且保密性强,密钥管理方便,特别适合于现代保密通讯的需要。而数字签名作为一项重要的安全技术,在保证数据的完整性,可用性,保密性,可控性方面,特别是在大型网络安全通信中的密钥分配,认证以及电子商务系统中起着极其重要的作用。随着电子商务的兴起,如何有效地进行信息保护已成为一个研究热点,而El Gamal 签名方案就是实现信息保护的一种有效

3、手段,但在实际应用中也存在一些不足。笔者分析了几种对El Gamal 签名体制的攻击方法,作出了一些相应的改进,以提高其运算效率。El Gamal 签名体制1是由T 1El Gamal 在1985年提出的。其修正形式已被美国N IST 作为数字签名标准DSS 2,同时它又是Rabin 体制3的一种变形。El Gamal 签名方案像El Gamal 公钥密码体制一样是非确定性的,这就意味着对任何给定的消息,有许多个有效的签名,验证算法必须能接受合法的有效签名中的任何一个,其安全性依赖于计算有限域上离散对数这一难题。El Gamal 签名方案描述如下:设p 是一个素数,它满足在Z p 中离散对数问

4、题是难解的,Z 3p 是一个本原元,P =Z 3p ,A =Z q Z q ,定义:K =(p ,a ,:=a (mod p 值p ,和是公开的,a 是保密的。对K =(p ,a ,和一个(秘密随机数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 签名方案的安全性分析假设攻击者(Oscar 在不知道a 的情况下企图伪造一个给定消息x 的签名。如果Oscar 选择一个值,然后企图找到相应的,他必须计算离散对数log x -。另外

5、,他如果首先选择,然后企图找到,他就试图“解”一个未知数的方程x (mod p ,这又是一个已知的没有可行解法的问题,如果Oscar 选择一个和,然后企图解出x ,他将再次面临离散对数问题log a 。因此,Oscar 利用这种方式不能签名一个“随机”消息,然而该方案不能排除某些特定的攻击方法。111伪造攻击1Oscar 同时选择,和x 来签名一个随机消息:设i 和j (0i ,j p -2是整数,且gcd (j ,p -1=1。利用逐步搜索法完成下列计算:391长江大学学报(自然科学版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假设Oscar 截获了合法签名者Bob 所签消息(,此时(,是消息x 的有效签名。假设h ,i 和j(0h ,i ,j

7、 p -2是整数,且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 在签名时泄露了随机数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设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同余式变为:x k (mod p 因为gcd (,p =1,可以计算=(-1mod p ,那么模p 时k 的值为:k =x (mod p ,这就产生

9、了d 个候选k 值:k =x +ip (mod p 。对于某一个i ,0i d -1,当然d 个候选值中,唯一正确的一个能通过k (mod p 确定。2方案改进对于伪造攻击1和伪造攻击2,虽然均可以产生有效的伪造签名,但是在没有先解离散对数问题时,从Oscar 的角度看并不能产生一个他自己选择的消息的一个签名,所以它们似乎并不代表对El Gamal 签名方案的一个威胁4。211改进1对于条件伪造攻击1和2,需要不断更新随机数k 的取值,才能避免方案失败,对于频繁的k 的更换,由于需要大量的求幂运算,使得方案计算效率不高,为此可以设计一种改进的方案,以避免每次求k -1。方案描述如下:Bob 选

10、择Z 3p 是一个本原元,a 是一个满足gcd (a ,p -1=1且=a (mod p 的秘密指数(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 签名方案效率更高。(下转第225页491长江大学学报(自然科学版2008年3月件。自主开发了地图查询控件,直接访问各种GIS 数据,可以与VC

11、 +、FoxPro 等结合开发前端业务处理系统,实现地图的显示、即时打印、地图与属性空间数据双向查询等功能。将Internet 网络技术应用于GIS 上,使用IIS (Internet Informatio n Server 和ASP (Active Server Page 在互联网提供数据查询服务,使得服务器方的数据动态访问组件用于地理空间数据的动态模糊查询具有可行性。4结语笔者阐述了基于Web GIS 地图综合知识的数据处理流程,提出了相应可行性事例。重点对在线地图综合技术在Web 网络环境下进行了系统性描述,并提出了该系统实现的可行性研究开发技术,使地图综合数据基于网络环境传输并实现地图

12、可视化。该技术方法需要进一步完善之处是知识库结构中没有考虑到相关在线地图综合中图层要素知识的关联性,故没有对相关图层要素之间的关联性数据进行深入探究,这一问题即是后续研究的目标。参考文献1王家耀1空间信息系统原理M 1北京:科学出版社,20011112012王家耀,武芳1数字地图自动制图综合原理与方法M 1北京:解放军出版社,1997161513李琦1Web GIS 中地理空间Metadata 管理系统设计J 1中国图像图形学报,2000,5(A10:81281714宋关福1Web GIS -基于Internet 的地理信息系统J 1中国图像图形学报,1998,3(3:25125415闫浩文1

13、计算机地图制图原理与算法基础M 1北京:科学出版社,2006120321116边馥苓1GIS 地理信息系统原理和方法M 1北京:测绘出版社,1996115315817刘纪平1面向综合应用的空间数据管理方法探讨与实践J 1测绘学院学报,2001,18(4:30330618郭仁忠1空间分析M 1武汉:武汉测绘科技大学出版社,19971616919毋河海1地理数据库系统M 1北京:测绘出版社,199112352381编辑易国华(上接第194页212改进2由于以上分析的4种攻击方法,可知El Gamal 签名方案并不比离散对数问题有更多的安全性,所以就必须使用大的模数p ,无疑p 将至少有512比特,

14、且许多人认为为了提供进一步的安全性,需要p 的长度为1024比特。然而,甚至一个512比特的模数也将导致签名有1024比特。对于一个潜在的应用,它们中的许多都涉及到灵巧卡的使用,此时一个更短的签名是需要的。因此我们可以进一步作如下改进:设p 是一个512比特的素数,它满足Z p 中离散对数问题是难处理的,且q 是一个整除p -1的160比特的素数,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 ,和一个(秘密随机数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比特消息产生一个320比特的签名,但计算使用了512比特的模p 。同时该方法是在Z 3p 的大小为2160的子群中这样作的。所以计算效率被大大提高。参考文献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密码学理论与实践M 1张文政译1成都:电子科技大学出版社,199711401501编辑洪云飞522第5卷第1期:理工高三营:基于Web GIS 模式在线地图综合技术的研究与开发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