资源描述：
《同时基于离散对数和素因子分解的新的数字签名方案.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2001年3月北京邮电大学学报Mar.2001第24卷第1期JOurnalOfbeijingUniversityOfPOstsandTelecOmmunicatiOnsVOl.24NO.1==========================================================文章编号:1007-5321(2001D01-0061-05同时基于离散对数和素因子分解的新的数字签名方案吴秋新杨义先胡正名(北京邮电大学信息工程学院北京100876D摘要:提出了两个新的数字签名方案它们的安全性同时基于离散对
2、数和素因子分解两个困难问题并各有特点.对两个方案的性能和可能遭受到的攻击进行了详细讨论.关键词:因子分解S离散对数S数字签名中图分类号:TN918.2文献标识码:A离散对数和素因子分解是数学中的两个难题1976年Diffie和~ellman第1次提出公钥密码思想后一系列基于数学难题的公钥密码体制相继提出.这些密码体制的一个共同点就是:它们的安全性仅仅基于一个数学难题或者是离散对数或者是素因子分解等.如果这些数学难题变得容易求解那么相应的密码体制就不安全了.但多个数学难题同时变得容易求解是不太可能的因此设计基于多个数学难题的公
3、钥密体制将会增强密码系统的安全性.1988年Mccurley[1]提出第1个同时基于离散对数和素因子分解两个数学难题的密钥分配方案后一系列同时基于离散对数和素因子分解的密码方案被相继提出[2*4]而文献[5*8]分别指出了它们的安全漏洞因而没有达到设计要求.1新的数字签名方案1.1签名方案1(1D系统参数设p为大素数且p-1有两个大的素因子p和g显然n(p-1D.设g为有限11n=p1g1域GF(pD中阶为n的元素.设h(D是一个安全的单向哈希函数其输出为固定t比特长(例如标准哈希函数输出为128bitD系统将参数png和
4、函数h(D公开将参数p和g秘密保存11(或毁弃D.(2D用户私钥与公钥的产生2用户A随机选取I[1n]计算y=gI(mOdpD随机选取t个数U1U2~Ut使Uz[12计算l使l2其中z=12~t.(IU作为私钥n]gcd(Uz(mOdnDnD=1zzUz=-11U2~UtD收稿日期:2000-07-04基金项目:国家重点基础研究规划资助项目(G1999035805DS国家自然科学基金资助项目(6007304969882002DS高等学校骨干教授资助计划项目作者简介:吴秋新(1966D男江西吉安人博士生.62北京邮电大学学报第
5、24卷保存,(y,Z作为对应公钥对外公开.1,Z2,~,Zt)(3)签名产生过程对于任意的消息m,用户A进行如下计算;2第1步;随机选取E[1,n],且gcd(,n)=1,计算1=gmOdP,且1#1.第2步;从方程m=1x-s计算出1mOdn,-1s1=(m-1x)mOdn(1)第3步;从方程mx-1=s计算出2mOdn,-1s2=(mx-1)mOdn(2)第4步;任取U使gcd(U,n)=1,有221s1-s2O=U-mOdn(3)2U)计算h(O)=(e其中e1,e2,~,et),zE{0,1.t221es1-s2B=
6、~zmOdn(4)zU-2z=1U)则(1,O,B)为消息m的签名,用户A将签名消息组(m;(1,O,B))发送到签名验证者.(4)签名验证过程当签名验证者收到签名消息组(m;(1,O,B))后,计算h(O)=(e验证方程1,e2,~,et),t222222O-Be(m-1)(m-1)1ZzgmOdPzEyz=1是否成立,若上述方程成立,则签名有效,否则签名无效.定理1如果签名者和验证者都严格执行方案1的签名协议,则产生的签名一定是有效的.证明根据签名者的公钥(y,Z和消息m的签名(1,O,B),从式(1)(4)可得h1,Z
7、2,~,Zt)t2e222222-22(O)=(e1,e2,~,et),O-ZzB=s-1)(x-1)mOdn.即(O2-z)1-s2=(mz=1ttt22e22222e2Zez2)=(m2-12)(x2-1)mOdn,于是g(O-Zzz)B)Eg(m-1)(x-1)O-Zzz)BEz)Bz=1mOdP,1z=1z=12222m-1m-1ygmOdP.方程成立.1.2签名方案2(1)用户私钥和公钥的产生用户A选取一个大素数P,使P-1有两个大的素因子P和G且分别满足P11,1(mOd8)=3和G1(mOd8)=7,n=P1G
8、1.设g为有限域GF(P)中阶为n的元素.随机选取xE[1,n],计算2xy=g(mOdP),则(P,n,g,y)作为用户公钥对外公开,(P1,G1,x)作为私钥秘密保存.(2)签名产生过程对于任意的消息m,用户A进行如下计算;2第1步;随机选取E[1,n],且gcd(,n)=1,计算1=
