一种不需要散列函数和消息冗余的数字签名方案

一种不需要散列函数和消息冗余的数字签名方案第27卷第5期 2006年5月 通信 JournalonCommunications ,.27NO.5 May2006 一 种不需要散列函数和消息冗余的数字签名方案 康立,唐小虎, (1.西南交通大学信息安全与国家网格计算实验室,四川成都610031;2.东南大学移动通信国家重点实验室,江苏南京210096) 摘要t研究了基于离散对数问题带消息恢复功能的数字签名Shieh方案和Chang方案,首先,给出对这2种方 案称为参数约化攻击的攻击方法,揭示出这2种方案的缺陷,其次提出一种新的三参数数字签名方案.该方案不 需要利用散列函数和消息冗余,经过安全性分析该方案能抵抗已知的攻击方法. 关键词?密码学;数字签名:消息恢复;散列函数 中图分类号:TN918.1文献标iflti-q:A文章编号:1000436X(2006)050018.03 Digitalsignatureschemewithouthashfunctionsandmessageredundancy KANGLi.TANGXiaohu., (1.InformationSecurityandNationGridComputingLaboratory,SouthwestJiaotongUniversity,Chengdu610031,China; 2.NationalMobileCommunicationResearchLab,SoutheastUniversity,Nanjing210096,China) Abstract:InvestigatedtheShiehSandChangsdigitalsignatureschemeswithmessagerecoverybasedonthediscrete logarithmproblem.Firstly,gaveanattackcalledparameterreductiononthetwoschemes,andthenreveedacommon fatalflawofthem.Secondly,proposedanewsignatureschemewiththreeparameters,whichdidnotemployhashrune? tionandmessageredundancy,andgavethesecurityanalysisofthenewscheme. Keywords:cryptography;digitalsignature;messagerecovery;hashfunction 1引言 基于离散对数问题(DLP)安全性的数字签名方 案由于不同于基于RSA问题能提供消息恢复功能, 所以人们一般将基于DLP的签名分为2种类型:附 加消息型和带消息恢复型. 在附加消息模式中,消息与签名一起发送给接收 者.为抵抗伪造攻击,消息原文应通过单向散列函数 进行处理,然后对处理后的值进行数字签名.E1Gamal 签名方案及其相关变形属于附加消息型l,2】. 在带消息恢复模式中,只需将签名发送给接收 者.接收者可从接收到的签名中直接恢复出消息原 文.NR方案【3是第一种基于DLP安全的带消息恢 复的数字签名方案,与EIGamal签名方案及其变形 比较,NR方案节省了通信量,具有更高的效率. 然而,为了抵抗伪造攻击,NR方案不得不使用消 息冗余方案J. 最近,Shieh等人提出了一种不使用散列函数和 消息冗余的三参数数字签名方案(Shieh方案)J, 但随后Hwang和Li便找出了伪造攻击的方法【6J. 在总结Shieh方案漏洞的基础上,Chang等人提出了 新的方案(Chang方案)可以抵抗对Hwang方法的有效 攻击71.然而,研究中相继发现新方案也并不安全【8,. 因此,构造一种安全的不需要散列函数和消息冗余的 收稿日期:2005.10.26:修回日期:200602.20 基金项目:全国优秀博士学位论文作者专项资金资助项目(200341):东南大学移动通信国家重点实验室开放基金资助项目 FoundationItems:TheFoundationfortheAuthorofNationalExcellentDoctoralDissertationofPRChina(200341);TheFounda- tionofNationalMobileCommunicationResearchLabofSoutheastUniversity 第5期康立等:一种不需要散列函数和消息冗余的数字签名方案:!: 安全数字签名方案仍是一个未解决的公开问题. 这里首先将指出Shieh和Chang方案易受伪造 攻击的致命缺陷,然后构建新的不使用散列函数和 消息冗余的安全数字签名方案,最后对新方案进行 安全性分析. 2Shieh方案和Chang方案的缺陷 在Shieh方案和Chang方案中,需要用到下面 的一些参数:系统公开参数P和g,P是一个大素 数,g是z的本元根.用户Alice选择私钥,满 足gcd(x,P一1)=1,然后计算相应公钥Y=gmodp. Shieh方和Chang方都由3个部分组成:签 名算法,恢复算法和验证算法. Shieh方案具体如下: 1)签名算法:Alice计算S=Y肘modP;从1, 1】中选择的随机整数k,计算,.=Mgmodp;从 +t=.(kr)mod(p一1)中计算出t;发送M的 签名(,:S,f)给接收者Bob验证. 2)恢复算法:验证者Bob接收到(,:S,f)后恢复: M辜),rgmodP. 3)验证算法:Bob验证等式S=YmodP是 否成立,如果成立,Bob相信由(,;S,f)恢复的M来 自声明的发送者. Chang方案具体如下: 1)签名算法:Alice计算S=Y肘modP;从1, Pl】中选择的随机整数k,计算,=Msgmodp; 从S+t=(k一,.)mod(p一1)中计算出f;发送M 的签名(f)给接收者Bob验证. 2)恢复算法:验证者Bob接收到(S,f)后恢复: M兰),rgSmodp; 3)验证算法:Bob验证等式S=YmodP是 否成立,如果成立,Bob相信由(,;S,f)恢复的M来 自声明的发送者. 对上述2种方案已有几种成功攻击方法【6】, 这里通过参数变化给出一个更一般的攻击方法,并 将由此进一步揭示其致命的缺陷,称这种新的攻击 为参数约化攻击. 在Shieh方案中令t=s-l-t,在Chug方案中令 f=+fM,消息恢复方程可转化成: 这里的(,.,S,t)fl(r,S,f)是一一映射的,所以合 法的(,.,S,f)能表示合法的(,.,f),反之亦然. 对比NR方案,Shieh方案和Chang方案为避 免使用散列函数或消息冗余均采用引入第三参数 S=Y肘modP的办法,力求用它来阻止可能的伪造 攻击.但是在式(1)中,可以清楚地发现通过上述参 数变化,参数S并没有出现在消息恢复方程中.因 此,实质上NR方案,Shieh方案和Chang方案都 是两参数的方案.从而预期的通过引入第三参数来 阻止伪造攻击地目的未能实现. 具体地说,可以采用如下攻击办法:攻击者选 择任意的f和,.,由式(1)先计算出M,再生成S;在 Shieh方案中发送(,:S,t-S),在Chang方案中发送(,; S,t-抖M)给接收者.那么接收者一定会被欺骗, 因为上述两组参数均能恢复出满足验证等式的M. 对比文献69与上述的攻击方案,不难看出使 用上述的攻击方案更明显地指明了被攻击方案的 代数结构缺陷,通过使用约化方法有利于对己知的 签名方案或是加密方案的安全性进行分析,更易发 现已知方案中是否存在结构上的缺陷,从而对已知 方案进行安全性评价.这就是参数约化攻击,而文 献【69中攻击都可以看作是参数约化攻击的具体 运用. 3新的签名方案 此处给出一种新的三参数数字签名方案,该方 案不使用散列函数和消息冗余,可以抵抗已知的伪 造攻击.新方案同样由2部分组成:签名部分和验 证部分.其中参数设置与上述Chang方案相同. 3.1签名部分 假设Alice要签署消息MZ,进行如下步骤 的计算: 1)Alice计算 S=Y朋modP(2) 2)Alice从1,P一1】中选择的随机整数k计算 j叫p(1)3?2=YMroodp一 ,.=S+MgmodP(3) 3)Alice从下式中计算出t S+t=一(七一,.)mod(p一1)(4) 4)Alice发送M的签名(S,D给接收者Bob验证. 验证部分 验证者Bob接收到(S,f)后执行如下操作: 通信第27卷 1)Bob计算 M三(,.一s)y州gmodP(5) 2)Bob验证等式S=Ymodp是否成立,如果 成立,Bob相信由S,f)恢复的M来自声明的发送 者. 造出满足签名方程的消息M和签名.观察提出的新 方案,攻击者试图通过消息恢复方程的代数结构构 造出,.和t,进而生成相应的消息M,然而参数S 及验证等式S=Y埘modP必然会阻止这一系列的 攻击,并且新方案能抵抗参数约化攻击,所以新方 案对前述攻击方法的抵抗是有效的. 4安全性分析5结论 首先,将证明新方案可以抵抗恢复私钥的攻 击:进而,说明新方案可以防止参数约化攻击;最 后,将分析新方案在不使用散列函数和消息冗余的 情况下可以抵抗已知的伪造攻击. 1)恢复私钥的攻击 攻击1:由于参数k出现在指数上,所以攻击 者想从式(3)qh计算出k等同于求解离散对数问题. 攻击2:攻击者想从式(4)oo解出参数也是不 可行的,因为式(4)中有2个未知数和k. 2)参数约化攻击 消息恢复式(5)可以转化为如下2种形式 M兰(,.一s)ygroodP(6) M三,.YgHmodP(7) 这里f,:=f+和,.,-r.通过化简式(5)中的参数 始终不能达到约减其中某一参数的目的,这说明新 方案能抵抗参数约化攻击.因而它能抵抗对Shieh 方案和Chang方案的所有已知攻击.为下面分析方 便起见,用式(7)代替消息恢复式(5). 3)伪造攻击 攻击3:给定消息,伪造攻击者试图寻找(r S,f)三元组满足式(2)和式(7). 在这种情况下先固定S=YmodP,尝试从等 式M誊rrYg.+modp中计算出,.和f.如果固定t, 尝试从 MgY叫兰,.YmodP(8) 中计算出,.,虽然未被证明但据文献1确信从中求 解f的难度不会小于对离散对数问题的计算. 如果固定,.,从方程M(,.)g.+詈YroodP 中解出f等同于计算离散对数. 最后攻击者试图从式(8)中同时求解出f和,., 但是目前尚未找到有效的求解方法llJ. 攻击4:在EIGamal签名方案中,如果不使用 单向散列函数,攻击者能利用其特殊的代数结构构 为抵抗对NR方案的伪造攻击,Shich等人 和Chang等人在其新方案中引入了第三参数S, 以试图阻止伪造攻击.这里对上述2种方案应用 提出的约化攻击,通过约化,增加的参数S被消 去了,因而预期用S来抵抗伪造攻击的目的未能 达到.基于上述分析提出了新的三参数数字签名 方案,通过安全性分析证实它可以抵抗所有已知 的攻击. 参考文献: 【1】EIGAMALTApublickeycryptosystemandasignaturescheme basedondiscretelogarithmJ.IEEETranslnfTheory,1985,31(4): 469472. 【2】HARNL,XUY.DesignofgeneralizedEIGamaltypedigitalsignature schemesbasedO/:1discretelogarithm【J1.ElectronLeG,1994,30(24): 2O25.2026. 【3】NYBERGK,RUEPPELRA.Messagerecoveryforsignatureschemes basedondiscretelogarithmproblemlA1.AdvancesinCryptol ogyProceedingsofEurocrypt94,LectureNotesinComputerSci, eneeC.Springer-Verlag,1995.182193. 【4】李子臣,李中献,杨义先.具有消息恢复签名方案的伪造攻击【J】.通 信,2000,2l(5):8487. UZC,LIZX,YANGYX.Anewforgeryattackonmessagerecov- erysignaturesJ.JournalofChinaInstituteofCommunications,2000, 21(5):8487. 【5】SHIEHSLINCYANGWB.Digitalmultisignatureschemesfor authenticatingdelegatesinmobilecodesystemsJ.IEEE”lYansVoh Techno,2000,49(4):14641473. 6】HWANGSJ,LIETCryptanalysisofShieh?LinYangSunsignature schemeJ.IEEECommunLett,2003,7(4):195196. 【7】CHANGCC,CHANGYFSigningadigitalsignaturewithoutusing onewayhashfunctionsandmessageredundancys