【doc】同时基于离散对数和素因子分解的新的数字签名方案

【doc】同时基于离散对数和素因子分解的新的数字签名 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 同时基于离散对数和素因子分解的新的数 字签名方案 2001年3月北京邮电大学 第24卷第1期JournalofBeijingUniversityofPostsandTelecommunications Mar.2001 Vo】.24No1 文章编号:1007—5321(2001)01—0061—05 同时基于离散对数和素因子分解的 新的数字签名方案 吴秋新,杨义先, (北京邮电大学信息工程学院, 胡正名 摘要:提出了两个新的数字签名方案.它们的安全性同时基于离散对数和素时子分解两个困难问 题.并各有特点.对两个方案的性能和可能遭受到的攻击进行了详细讨论 关键词:因子分解;离散对数;数字签名 中图分类号:TN9182文献标识码:A 离散对数和素园子分解是数学中的两个难题,1976年.Diffie和Hellman第1次提出公钥 密码思想后,一系列基于数学难题的公钥密码体翩相继提出.这些密码体制的…个共同点就 是:它们的安全性仅仅基于一个数学难题.或者是离散对数.或者是素因子分解等.如果这些数 学难题变得容易求解,那么相应的密码体制就不安全了.但多个数学难题同时变得容易求解是 不太可能的,因此,设计基于多个数学难题的公钥密体制将会增强密码系统的安全性.1988 年,McCurley71]提出第1个同时基于离散对数和素因子分解两个数学难题的密钥分配方案 后,一系列同时基于离散对数和素因子分解的密码方案被相继提出,.而文献:j,8:分别指 出了它们的安全漏洞,因而没有达到设计要求. 1新的数字签名方案 1.1签名方案1 (1)系统参数 设p为大素数.且户1有两个大的素因子和q..--p.显然(户1).设g为有限 域GF(户)中阶为的元素.设h()是一个安全的单向啥希函数.其输出为固定t比特长(例如 标准哈希函数输出为128bit),系统将参数P,n,g和函数h()公开.将参数P和q秘密保存 (或毁弃). (2)用户私钥与公钥的产生 用户随机选取?[1,n],计算—g'(modp),随机选取t个数",".….使?[1, ],gcd("(modn).n)一1,计算.使,,"一1,其中.i一1,2.…(,"1,"2.….,)作为私钥 收稿日期 基金项目 作者简介 2000—0一04 国家重点基础研究规划资助项目(G1999oassn:)i国家自然科学基金资助项目(600730~q.69882002)t高等 学按骨干教授资助计划项目 吴袱新(1966).男,江西吉安^.博士生 北京邮电大学第24卷 ,L)作为对应公钥对外公开. 保存,(..!.… (3)签名产生过程 对于任意的消息,用户^进行如下计算: 第1步:随机选取kE[1,n],且gcd(k,n)一1.计算r—modP,且r?1- 第2步:从方程一一+modn,计算出 一(—rx)k一modn 第3步:从方程z+r=ks2mod.计算出 !一(rex—r)k一modn 第4步:任取使gcd(,n)一1.有 一 +堕土韭.d ' 计算h(d)一(…,),其中.?《0,1}. 卢一告fI:一直m.dn 则(r,..卢)为消息的签名,用户将签名消息组:(r,...9))发送到签名验证者. (4)签名验证过程 当签名验证者收到签名消息组(;(r,?,p))后,计算^(n)=(…,et),验证方程 r十JJ謦一m.dPf1 是否成立,若上述方程成立,则签名有效,否则签名无效. 定理1如果签名者和验证者都严格执行方案1的签名 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 ,则产生的签名一定是 有效 的. 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 根据签名者的公钥(_y,,,…,)和消息的签名(r,口,p),从式(1),(4)可得h (口)一(.?,…,),+兀尊一+;一(卅.+,)(+1)k-Zmodn.即k(口!一 I一1 cfTI)一(+rz)(2—1)m.dn.于是.L旦::兰g.+?1TI.d户,r.L旦兰 , g一modP. 方程成立. 1.2签名方案2 (1)用户私钥和公钥的产生 用户A选取一个大素数P,使户一1有两个大的素因子P和g,且分别满足p](mod8)一 3和q(mod8)一7.—Pq.设g为有限域GF(p)中阶为n的元素.随机选取?[1,n]一计算 _vg ,(mod声) ,则(户,n,g,_y)作为用户公钥对外公开.(,虮.)作为私钥秘密保存. (2)签名产生过程 对于任意的消息-m,用户进行如下计算: 第1步:随机选取k?[1,n],且gcd(,n)一1,计算r=gmodP,且r?1. 第2步:从方程m一一一roodn.计算出 5一(—rx;Ik-iroodn(5) D曲 第1期吴秋新等:同时基于离散对数和素固子分解的新的数字签名方案63 第3步:从方程mr+r一2mod,计算出 一 (m+r)k一rood(6) 第4步:计算一5}+;rood.且根据选择参数t: }1L(?/p)一L(A/q】)一1 l2L(A/p1)一1,L(A/qI)一一1一 12L(A/p~)一1.L(A/q)一l竹 l一1L(?/p1)一L(I)一一1 第5步:计算 一 ?mod(8) 那么,(rm,)为消息m的签名.用户A将签名消息组(;(r—f))发送到签名验证者. (3)签名验证过程 当签名验证者收到签名消息组(m:(r.,f))后,验证方程r--yt(mZ+rZ)g"_.modP是否 成立.若上述方程成立.则签名有效.否则签名无效. 定理2如果签名者和验证者都严格执行方案2的签名协议.则产生的签名一定是有效 的. 证明根据签名者的公钥(p,,g._y)和消息m的签名(rmf),由式(5),(8)可得 一t(i—S!)一t(?一)(se+1)mod 即kZs一t(!+r)(3-T1)rood,于是有 -- g"""modP ,_y,g…'modP 方程成立. 2签名方案的安全性与性能分析 分析力'案的安全性和性能之前,先介绍2个方案签名方程的构思特点和一个引理.对于签 名方案1.式(1)和式(2)是2个EIGamaI型签名方程.它们的结合避免了平方后的交叉项, 也避免了文献[10的设计失败.而式(3)和式(4)是对前2个方程的平方和的安全转移.签名方 案2的签名方程的构思与方案1类似. 引理1设P为大素数,一Pq,l(p1).其中,P,q为两个大素数.g?GF(p).且g 的阶为.设G为由元素g生成的乘法群.对任意?G.求解满足方程3'--3'(rood户)的问 题等价于在G中求解离散对数并且对数进行素因子分解. 2.1方案1的安全性与性能分析 (1)攻击者要想计算出式(1)(2)中的和必须先计算出私钥和秘密数k,由引理1 知,这等同于离散对数和素因子分解可同时求解.另外.由于和5只有签名者知道.攻击者 不可能从s和中获得任何关f私钥z和秘密数k的信息. (2)攻击者无法从式(3)(4)的和口中直接获得s和5:的值.也无法从方程a+ I兀:一Jfl2_s~一!(rood)获得.和.的值. (3)虽然在离散对数容易求解的情况下.攻击者可从方程f+(.+T-2)+1) 北京邮电大学第24卷 (rood)随意伪造任意对应的.一s;,但要进一步从方程一:ll川一+s;(rood)求 出和,这相当于求解方程+():C(mod),其中,h(z)是非线性函数.而这又等价 于大数/-/的素斟子分解. r (4)在方程(a!+{IT睁:)一k!(i+s!)一(!+r:)(+1)(modn)中由于k与r的关 =1 联性.故不存在平方因子导致的替代攻击. (5)根据引理,攻击者要从验证方程中直接伪造签名必须同时面对离散对数和素因子分 解两个困难问题求解. 从上面分析可知:签名方案l是一个安全的签名方案.其安全性同时基于离散对数和素因 子分解2个困难问题求解.从系统配置,签名过程,验证过程来看,簦名方案l的计算复杂性同 E1Gama[型签名方案相类似,只是计算量和通信量增加了一些,同时密钥量较大,但安全性增 强』,,因而签名方案l是可行的数字簦名方案. 2.2方案2的安全性与性能分析 (1)攻击者要想计算出式(5)(6)中的和必须先计算出私钥和秘密数.由引理知, 这等同于离散对数和素因子分解可同时求解.另外.由于5和.只有签名者知道,攻击者不可 能从s和中获得任何关于私钥z和秘密数的信息. (2)攻击者无莹从式(7)(8)的和5中获得和:的值. (3)在方程"+;J—f【"7:+r:)(r!+lJ(mod)中由于与r的关联性,故不存 在平方固子导致的替代攻击. (4)虽然在离散对数容易求解的情况下,攻击嚣可从方程+:一(m!r!)(;+1)_ (roodn)随意伪造任意m对应的s;,但要进一步从方程:=(i+;)(mod)求出.这相 当于求解方程z--C(mod/-/).而这又等价于大数的素因子分解. (5)根据引理,攻击青要从验证方程中直接伪造签名必须同时面对离散对数和素困子分 解2个困难问题求解. 从上面分析可知:签名方案2是一个安全的签名方案.其安全性同时基于离散对数和素因 子分解2个困难问题求解.签名案2本质上是EIGamal型和Rabin型2种数字签名方案的 结台.签名过程的复杂性增大_『,但验证过程的复杂性与E1Gamal型相同.由于安全性增强 了,所以签名方案2也成为可行的数字签名方案. 3结论 本文从一个新的角度将离散对数同题和素困子分解问题组合在一起.设计了2个数字签 名方案,经分析论证.它们的安全性同时摹于这2个困难问题的求解,达到了设计要求. 参考文献: [1McCurleyKCAkeydistributionsystemequivMemtObtctoring[J]Cryptology-l988.1(2) :95106 [2]He】.KieslerTEnhancingthesecurityofElGamal'ssignaturescheme[J~.1EEProcCom putersAnd DigitalTechniques,1994,141(4:249252 :3]LaihcS,KuoWC.NewsignatureschemesbasedOllfactoringanddiscretelogqrithms[J~. IEICETrans ? 第1期吴秋新等:同时基于离散对数和素固子分解的新的数字签名方案65 FundaglJencals.1997一E80一A【1). [4:ShaoZ.Signatureschemesbasedonfactoringanddiscretelogarithms[J]1EEProcComputersandDi— gitalTechniques.1998.145(1)-3336. C5]LeeNY,HwangT.ThesecurityofheandKiesler'ssignatureschemes[J]IEEProcCornputersand DigitalTechniques一1994,1.12f5J:370—372 [6-HarnL.Comment:EnhancingthesecurityofElGamal'ssignaturescheme[J].1EEProc— Computersand DigitalTechniques.1995,l42(5):376 73LaihCS,KuoWC.Cryptana[ysisoftheenhancedElCamaissignaturescheme[A]LNCS1029?Cryp tography:PolicyandAlgorithmslCI_SpringerPresst1996,228831 [8]LiJHXiaoGZ.Remarksonnewsignatureschemebasedtwohardproblems[J]fEELetters.1998,34 (25):2401 - 97ElGamalT.Apublickeycryptosystemandasignatureschemebasedonthediscretelogarithm[J].1EEE TransfnformTheory,1985,3l:469472. [1O3HarnI— Publickeyeryptosysterndesignbasedonfactoringanddiscretelogaridams[j]IEEProe— Com putersandDigitalTechniques.f994,141(3)193195 - 1】:HeWH— WuTCImprovementtonyangsongfastdigitalsignaturescheme[J".IEELetters.1997,33 f22]86】一】882 NewSignatureSchemesBasedon DiscreteLogarithmsandFactoring wQiu—xin,YANGYixian.HUZheng—ruing (InformationEngioeeringSch~i,BeijingUniver~itv.Postsandre/ecommunications,Beijing100876China) Abstract:Twonewdigitalsignatureschemeswhosesecurityarebasedonbothdiscreteloga rithmsandfactorization8reproposed.Thepaperalsoconsiderssonicpossibleattackstothe schemes.showsthatthetWOschemesaremoresecurethantheEIGamal'ssignaturescheme andtheRabin'ssignaturescheme. Keywords;factorization;discretelogarithm;digtalsignature