數(shù)字簽名標(biāo)準(zhǔn)dss及其改進(jìn)方案的軟件開發(fā)

在web和電子商務(wù)的普及以及電子商務(wù)的快速發(fā)展之后，數(shù)字簽名已成為計(jì)算機(jī)網(wǎng)絡(luò)上取代傳統(tǒng)的打印和簽字簽名，成為確保網(wǎng)絡(luò)安全的關(guān)鍵和關(guān)鍵技術(shù)之一。在眾多已提出的數(shù)字簽名方案中,美國國家數(shù)字簽名標(biāo)準(zhǔn)DSS是1個較為典型的實(shí)用的簽名方案,為此有關(guān)DSS及其改進(jìn)方案的軟件開發(fā),成為我們的研究課題。1yl方案的提出1991年8月美國國家標(biāo)準(zhǔn)局NIST公布了數(shù)字簽名標(biāo)準(zhǔn)DSS。該標(biāo)準(zhǔn)采用了DSA算法。DSA為ElGamal方案的變型,它采用了Schnorr方案中g(shù)為非原根的做法,以降低簽名的長度。DSS發(fā)布后,許多學(xué)者提出了DSS改進(jìn)方案,這當(dāng)中我們選取YENSM和LAIHCS于1995年在文獻(xiàn)提出的改進(jìn)方案為軟件開發(fā)的原型,記為YL方案。YL方案中,驗(yàn)證者無需作逆元素計(jì)算,由于求逆元素幾乎相當(dāng)于指數(shù)運(yùn)算,相當(dāng)費(fèi)時,因此適合驗(yàn)證者計(jì)算能力較小者使用。YL方案安全性與DSA完全一樣,都是基于求離散對數(shù)的困難問題。對于其它DSS改進(jìn)方案的軟件開發(fā),可參照本文進(jìn)行。1.1使用sqp算法的dss-sp-ms算法見表1.p512-1024比特長的素?cái)?shù),且長度為64的倍數(shù)q160比特長的素?cái)?shù),且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函數(shù)H(m),對DSS來說是SHA。但Hash函數(shù)可根據(jù)具體情況選取,不一定采用SHA,故本文不討論Hash函數(shù)的軟件開發(fā)。1.2計(jì)算r、gkmodp、ckmodp、km+x-1moq設(shè)m是待簽名的消息(1)隨機(jī)生成1個k,0<k<q;(2)計(jì)算r=(gkmodp)modq,及s=k(H(m)+xr)-1(modq),若H(m)=0或s=0或r=0,返回步驟(1)。計(jì)算出的(r,s)為消息m的簽名。1.3r,s屬于簽名,計(jì)算n(1)首先檢查r和s是否屬于(0,q),若不是,則(r,s)不是簽名。(2)計(jì)算t=sH(m)modq,r′=(gtysrmodp)modq。若r′=r成立,則(r,s)是消息m的合法簽名;否則為非法簽名。2字段解決方案的軟件介紹2.1軟件步驟依照YL方案,我們開發(fā)的數(shù)字簽名軟件分為3個步驟:2.1.1文件interpersonal位置按方案要求,產(chǎn)生系統(tǒng)參數(shù)—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中的系統(tǒng)參數(shù)p、q、g和x,產(chǎn)生隨機(jī)數(shù)k,并對消息文件m計(jì)算簽名(r,s),然后將簽名存入指定簽名文件中。2.1.3合法簽名的驗(yàn)證驗(yàn)證方讀取系統(tǒng)參數(shù)文件common.dss和private.dss中的參數(shù)p、q、g和y,并讀取指定簽名文件中的簽名(r,s),計(jì)算t和r′,驗(yàn)證(r,s)是否是消息m的合法簽名。2.2數(shù)字簽名軟件的設(shè)計(jì)程序語言PASCAL設(shè)計(jì)者WIRTHN有1本成名著作《算法+數(shù)據(jù)結(jié)構(gòu)=程序》。數(shù)字簽名軟件正是符合這種定義的程序。我們開發(fā)數(shù)字簽名軟件的主要工作是對位數(shù)較大的二進(jìn)制和十進(jìn)制整數(shù)進(jìn)行處理。這種大整數(shù),是數(shù)字簽名軟件的主要數(shù)據(jù)結(jié)構(gòu),它構(gòu)成了軟件的基礎(chǔ)。我們構(gòu)造的數(shù)據(jù)結(jié)構(gòu)如下:2.2.1平臺長度2.p保理型QBITS=160素?cái)?shù)q(注:二進(jìn)制數(shù))的長度PBITS素?cái)?shù)p(注:二進(jìn)制數(shù))的長度,如512BITSLENGTH=2*PBITS存放大數(shù)(注:二進(jìn)制數(shù))數(shù)組的長度,此長度應(yīng)為PBITS的2倍,以便可容納模運(yùn)算的任何中間結(jié)果DATALENGTH=BITSLENGTH/log210存放大數(shù)(注:十進(jìn)制數(shù))數(shù)組的長度2.2.2維整型數(shù)字化后的一維整型數(shù)binint用于存放大數(shù)(注:二進(jìn)制數(shù))的一維整型數(shù)組,長度BITSLENGTHbyteint用于存放大數(shù)(注:十進(jìn)制數(shù))的一維整型數(shù)組,長度DATALENGTH2.3主要模塊及算法整個數(shù)字簽名軟件采用模塊化設(shè)計(jì)方法,各模塊以函數(shù)方式實(shí)現(xiàn)。下面將就主要模塊及算法進(jìn)行闡述,同時考慮到數(shù)字簽名與公鑰算法在軟件實(shí)現(xiàn)上的類似性,而公鑰算法比分組密碼算法大約慢1000倍,故此除了軟件實(shí)現(xiàn)外,我們還必須進(jìn)行優(yōu)化,以加快軟件運(yùn)行的速度。2.3.1數(shù)字簽名模塊的設(shè)計(jì)數(shù)字簽名方案中的運(yùn)算主要是模運(yùn)算,模運(yùn)算滿足交換律、結(jié)合律和分配律,并遵循按模計(jì)算原理。按模計(jì)算原理:令a、b、n為整數(shù),OP代表+、-、*運(yùn)算符,則有(aOPb)modn=((amodn)OP(bmodn))modn按模計(jì)算有效地限制了模運(yùn)算中間結(jié)果的范圍。對于2個k比特長的數(shù)進(jìn)行模n運(yùn)算,任何加、減、乘的中間結(jié)果至多為2k比特長。這樣將不會產(chǎn)生很大的中間結(jié)果,便于存儲和處理2.2節(jié)中的數(shù)據(jù)結(jié)構(gòu)就能滿足軟件的要求。故我們開發(fā)的數(shù)字簽名軟件的基本模塊主要是模運(yùn)算、素?cái)?shù)產(chǎn)生與測試、不同類型數(shù)據(jù)的轉(zhuǎn)換等。基本函數(shù)模塊:(1)Plus功能:求2個數(shù)的和;(2)Substract功能:求2個數(shù)的差;(3)Multiply功能:求2個數(shù)的乘積;(4)Mod功能:求2個數(shù)的商及余數(shù);(5)IntRandom功能:產(chǎn)生隨機(jī)數(shù);(6)ExpMod功能:指數(shù)求余,如求gkmodp;(7)Prime功能:判斷1個數(shù)是否素?cái)?shù);(8)Inverse功能:計(jì)算某數(shù)的乘法逆元,如求a關(guān)于modn的乘法逆元a-1;(9)類型轉(zhuǎn)換模塊功能:byteint類型變量和binint類型變量的相互轉(zhuǎn)換。2.3.2計(jì)算q是否單一q素?cái)?shù)生成算法較多,我們?nèi)∪缦潞喢鞯乃惴?設(shè)|p|,|q|為所要產(chǎn)生的素?cái)?shù)p,q的長度(注:二進(jìn)制),運(yùn)行下述算法以產(chǎn)生簽名方案所需素?cái)?shù):(1)取|q|-1長的n;(2)計(jì)算q=2*n+1;(3)測試q是否素?cái)?shù),不是則q+2→q,繼續(xù)測試,直至q為素?cái)?shù);(4)如果q的長度>|q|,則返回步驟(1)重做;(5)產(chǎn)生了符合要求的素?cái)?shù)q;(6)計(jì)算: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)產(chǎn)生1個隨機(jī)數(shù)n,s<n<t;(8)p=2*n*q+1;(9)如果p不是素?cái)?shù),則返回步驟(7);(10)產(chǎn)生了符合要求的素?cái)?shù)p。2.3.3ea,n選取素?cái)?shù)測試我們采用Lehman概率測試算法,見參考文獻(xiàn)。Lehman定義:e(a,n)=a(n-1)/2modn,G={e(a,n):a∈Z*n}如果n是奇數(shù),G={1,n-1}當(dāng)且僅當(dāng)n是素?cái)?shù)時成立。如果從Z*n中挑選100個a去驗(yàn)證上式成立,則n不是素?cái)?shù)的概率是2-100。2.3.4元法求取指數(shù)運(yùn)算指數(shù)運(yùn)算是數(shù)字簽名軟件中運(yùn)算量大的計(jì)算。對于求gkmodp最簡單而直接的方法,就是將g連續(xù)乘(k-1)次,但這種方法太慢,為此我們以二元法來加快指數(shù)運(yùn)算,即先將指數(shù)表示成二進(jìn)制數(shù),再進(jìn)行運(yùn)算。例如求g23,23表示成二進(jìn)制為10111,計(jì)算方法為:(1)令A(yù)=g,并去掉10111最左邊的1;(2)由左向右掃描二進(jìn)制數(shù),遇到“0”,就將A平方;遇到“1”,就將A平方后再乘以g。計(jì)算過程為:g→g2→g4*g→g10*g→g22*g→g23以上計(jì)算,共需7次乘法(注:將平方視為乘法運(yùn)算),這樣大大加快了指數(shù)運(yùn)算。2.3.5逆元an-1,an-2modn求a關(guān)于modn的乘法逆元a-1,可采用歐拉(Euler)定理或歐幾里德(Euclid)算法,后者見參考文獻(xiàn)。歐拉定理:若(a,n)=1,則aΦ(n)=1modn,故此有aaΦ(n)-1=1modn,進(jìn)而有aΦ(n)-1=a-1modn。對于素?cái)?shù)n,Φ(n)=n-1,則逆元a-1=an-2modn。求逆后進(jìn)行驗(yàn)證,進(jìn)而可排除所選的n不是素?cái)?shù)的情況。3實(shí)現(xiàn)效率的研究我們基于本文中的數(shù)據(jù)結(jié)構(gòu)和算法,順利地實(shí)現(xiàn)