數(shù)字簽名標準dss及其改進方案的軟件開發(fā)

數(shù)字簽名標準dss及其改進方案的軟件開發(fā)

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