数字签名标准dss及其改进方案的软件开发

数字签名标准dss及其改进方案的软件开发

在web和电子商务的普及以及电子商务的快速发展之后，数字签名已成为计算机网络上取代传统的打印和签字签名，成为确保网络安全的关键和关键技术之一。在众多已提出的数字签名方案中,美国国家数字签名标准DSS是1个较为典型的实用的签名方案,为此有关DSS及其改进方案的软件开发,成为我们的研究课题。1yl方案的提出1991年8月美国国家标准局NIST公布了数字签名标准DSS。该标准采用了DSA算法。DSA为ElGamal方案的变型,它采用了Schnorr方案中g为非原根的做法,以降低签名的长度。DSS发布后,许多学者提出了DSS改进方案,这当中我们选取YENSM和LAIHCS于1995年在文献提出的改进方案为软件开发的原型,记为YL方案。YL方案中,验证者无需作逆元素计算,由于求逆元素几乎相当于指数运算,相当费时,因此适合验证者计算能力较小者使用。YL方案安全性与DSA完全一样,都是基于求离散对数的困难问题。对于其它DSS改进方案的软件开发,可参照本文进行。1.1使用sqp算法的dss-sp-ms算法见表1.p512-1024比特长的素数,且长度为64的倍数q160比特长的素数,且q|p-1gh(p-1)/q(modp),0<h<p,且h(p-1)/q(modp)>1x0<x<q,秘密钥ygx(modp),公开钥其中:p、q和g公开,也可以为用户公用。秘密密钥是x,公开密钥是y。另外,算法使用了1个单向Hash函数H(m),对DSS来说是SHA。但Hash函数可根据具体情况选取,不一定采用SHA,故本文不讨论Hash函数的软件开发。1.2计算r、gkmodp、ckmodp、km+x-1moq设m是待签名的消息(1)随机生成1个k,0<k<q;(2)计算r=(gkmodp)modq,及s=k(H(m)+xr)-1(modq),若H(m)=0或s=0或r=0,返回步骤(1)。计算出的(r,s)为消息m的签名。1.3r,s属于签名,计算n(1)首先检查r和s是否属于(0,q),若不是,则(r,s)不是签名。(2)计算t=sH(m)modq,r′=(gtysrmodp)modq。若r′=r成立,则(r,s)是消息m的合法签名;否则为非法签名。2字段解决方案的软件介绍2.1软件步骤依照YL方案,我们开发的数字签名软件分为3个步骤:2.1.1文件interpersonal位置按方案要求,产生系统参数—p、q、g、x和y.p、q和g存放在文件common.dss中,y存放在文件public.dss中,x存放在文件private.dss中。common.dss和public.dss文件公开,private.dss文件为签名方的私有文件。2.1.2iii东南角签名签名方读取文件common.dss和private.dss中的系统参数p、q、g和x,产生随机数k,并对消息文件m计算签名(r,s),然后将签名存入指定签名文件中。2.1.3合法签名的验证验证方读取系统参数文件common.dss和private.dss中的参数p、q、g和y,并读取指定签名文件中的签名(r,s),计算t和r′,验证(r,s)是否是消息m的合法签名。2.2数字签名软件的设计程序语言PASCAL设计者WIRTHN有1本成名著作《算法+数据结构=程序》。数字签名软件正是符合这种定义的程序。我们开发数字签名软件的主要工作是对位数较大的二进制和十进制整数进行处理。这种大整数,是数字签名软件的主要数据结构,它构成了软件的基础。我们构造的数据结构如下:2.2.1平台长度2.p保理型QBITS=160素数q(注:二进制数)的长度PBITS素数p(注:二进制数)的长度,如512BITSLENGTH=2*PBITS存放大数(注:二进制数)数组的长度,此长度应为PBITS的2倍,以便可容纳模运算的任何中间结果DATALENGTH=BITSLENGTH/log210存放大数(注:十进制数)数组的长度2.2.2维整型数字化后的一维整型数binint用于存放大数(注:二进制数)的一维整型数组,长度BITSLENGTHbyteint用于存放大数(注:十进制数)的一维整型数组,长度DATALENGTH2.3主要模块及算法整个数字签名软件采用模块化设计方法,各模块以函数方式实现。下面将就主要模块及算法进行阐述,同时考虑到数字签名与公钥算法在软件实现上的类似性,而公钥算法比分组密码算法大约慢1000倍,故此除了软件实现外,我们还必须进行优化,以加快软件运行的速度。2.3.1数字签名模块的设计数字签名方案中的运算主要是模运算,模运算满足交换律、结合律和分配律,并遵循按模计算原理。按模计算原理:令a、b、n为整数,OP代表+、-、*运算符,则有(aOPb)modn=((amodn)OP(bmodn))modn按模计算有效地限制了模运算中间结果的范围。对于2个k比特长的数进行模n运算,任何加、减、乘的中间结果至多为2k比特长。这样将不会产生很大的中间结果,便于存储和处理2.2节中的数据结构就能满足软件的要求。故我们开发的数字签名软件的基本模块主要是模运算、素数产生与测试、不同类型数据的转换等。基本函数模块:(1)Plus功能:求2个数的和;(2)Substract功能:求2个数的差;(3)Multiply功能:求2个数的乘积;(4)Mod功能:求2个数的商及余数;(5)IntRandom功能:产生随机数;(6)ExpMod功能:指数求余,如求gkmodp;(7)Prime功能:判断1个数是否素数;(8)Inverse功能:计算某数的乘法逆元,如求a关于modn的乘法逆元a-1;(9)类型转换模块功能:byteint类型变量和binint类型变量的相互转换。2.3.2计算q是否单一q素数生成算法较多,我们取如下简明的算法:设|p|,|q|为所要产生的素数p,q的长度(注:二进制),运行下述算法以产生签名方案所需素数:(1)取|q|-1长的n;(2)计算q=2*n+1;(3)测试q是否素数,不是则q+2→q,继续测试,直至q为素数;(4)如果q的长度>|q|,则返回步骤(1)重做;(5)产生了符合要求的素数q;(6)计算:s=(2|p|−1−1)/(2*q)t=(2|p|−1−1)/(2*q)s=(2|p|-1-1)/(2*q)t=(2|p|-1-1)/(2*q)(7)产生1个随机数n,s<n<t;(8)p=2*n*q+1;(9)如果p不是素数,则返回步骤(7);(10)产生了符合要求的素数p。2.3.3ea,n选取素数测试我们采用Lehman概率测试算法,见参考文献。Lehman定义:e(a,n)=a(n-1)/2modn,G={e(a,n):a∈Z*n}如果n是奇数,G={1,n-1}当且仅当n是素数时成立。如果从Z*n中挑选100个a去验证上式成立,则n不是素数的概率是2-100。2.3.4元法求取指数运算指数运算是数字签名软件中运算量大的计算。对于求gkmodp最简单而直接的方法,就是将g连续乘(k-1)次,但这种方法太慢,为此我们以二元法来加快指数运算,即先将指数表示成二进制数,再进行运算。例如求g23,23表示成二进制为10111,计算方法为:(1)令A=g,并去掉10111最左边的1;(2)由左向右扫描二进制数,遇到“0”,就将A平方;遇到“1”,就将A平方后再乘以g。计算过程为:g→g2→g4*g→g10*g→g22*g→g23以上计算,共需7次乘法(注:将平方视为乘法运算),这样大大加快了指数运算。2.3.5逆元an-1,an-2modn求a关于modn的乘法逆元a-1,可采用欧拉(Euler)定理或欧几里德(Euclid)算法,后者见参考文献。欧拉定理:若(a,n)=1,则aΦ(n)=1modn,故此有aaΦ(n)-1=1modn,进而有aΦ(n)-1=a-1modn。对于素数n,Φ(n)=n-1,则逆元a-1=an-2modn。求逆后进行验证,进而可排除所选的n不是素数的情况。3实现效率的研究我们基于本文中的数据结构和算法,顺利地实现