基于rsa算法的數(shù)字簽名技術(shù)

基于rsa算法的數(shù)字簽名技術(shù)

0rsa算法基于rsa算法的信息安全系統(tǒng)是迄今為止最成熟、最完整的信息安全系統(tǒng)。這是現(xiàn)代非對稱數(shù)據(jù)分布的代表。大多數(shù)信息安全產(chǎn)品和標準使用了基于加密和數(shù)字簽名功能的算法。RSA算法也是第1個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法,對解決密鑰分發(fā)和身份認證和在現(xiàn)代電子商務(wù)中都有著廣泛的應(yīng)用前景。但它存在一個明顯的缺點,即加密效率非常低。粗略地說,RSA的硬件實現(xiàn)比分組加密算法DES硬件實現(xiàn)的速度慢約1500倍,而軟件實現(xiàn)的速度也要慢約100倍。針對以上缺點,筆者嘗試進行改進。1rv算法的描述1.1算模數(shù)的計算及轉(zhuǎn)化1)生成兩個互異的大素數(shù)p和q。在實際運用中,素數(shù)的生成要先通過隨機數(shù)發(fā)生器生成隨機數(shù),然后對它進行素性檢測,考慮到抗破譯因素,RSA密鑰要求強素數(shù)。2)計算模數(shù)n=p×q。φ(n)=(p-1)(q-1)。式中:φ(n)為n的歐拉函數(shù)值(小于n且與n互素的正整數(shù)的個數(shù))。3)選一整數(shù)e。e滿足1<e<φ(n),且gcd(φ(n),e)=1,式中:gcd()為求兩個數(shù)公約數(shù)符號,測試兩個數(shù)是否互素可以用輾轉(zhuǎn)相除法。4)計算d。d滿足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元,因為e與φ(n)互素,故它的逆元一定存在。5)取(e,n)為公鑰,將其公開;取(d,n)為私鑰,將其保密。1.2百進制數(shù)m先將明文m按比特串分組,使得每個分組對應(yīng)的十進制數(shù)m小于n;然后對每個明文分組m,按式(1)進行加密運算,得到其分組密文cc≡memodn(1)c≡memodn(1)1.3memdodnmedannmedann+1nmemdodnn+1nmmodnn+1n+1n+1nmemdodnn+1n+1n對每個密文c,按式(2)進行解密運算,得到其分組明文mm≡cdmodn(2)m≡cdmodn(2)因為mφ(n)modn=1,所以cdmodn≡(memodn)dmodn≡medmodn≡mk?φ(n)+1≡mk?φ(n)mmodn=mcdmodn≡(memodn)dmodn≡medmodn≡mk?φ(n)+1≡mk?φ(n)mmodn=m所以能夠得到明文。2ad11mom從上面算法描述可以看出,在生成密鑰過程中要計算乘法逆元(即e對φ(n)的逆元d),一般求乘法逆元是用擴展的Euclid算法。該算法涉及中間變量較多,不易理解,編程復雜,這里介紹一種基于高階指數(shù)模乘的算法。在數(shù)論中,有一個Fermat-Euler定理,即設(shè)gcd(a,m)=1,則有aφ(m)≡1(modm)aφ(m)≡1(modm)該定理還可推出如下結(jié)論:使得ad≡1(modm)成立的最小正整數(shù)d,必有d|φ(m)。因此,a·ad-1≡1(modm),即a的乘法逆元為ad-1modm。具體算法如下。Inverse(a,m)1)x=a,a-1=1;2)while((x=x%m)!=1){a-1=x;x=x·a;}3)returna-1。可以看出,該算法只有3步,簡單易懂,運算也不復雜。在模數(shù)較小時,算法較優(yōu)越。對于大數(shù),由于d較大,理論上可行,但現(xiàn)實行不通(時間不允許),在大數(shù)情況下可以利用快速指數(shù)算法,因為aφ(m)≡1(modm),即a·aφ(m)-1≡1(modm),從而有d≡aφ(m)-1modm(注意這里的d和上面定理中d不同),而φ(m)=(p-1)(q-1),因此aφ(m)-1modm可通過快速指數(shù)算法來求,而且在加密解密過程中也要用到快速指數(shù)算法,這就把求逆、加密和解密統(tǒng)一起來,有利于模塊的復用,提高編碼效率。3中國剩余定理解釋同余在解密過程中,由于系統(tǒng)保留了兩個素數(shù)p,q,因此可以用中國剩余定理改進解密過程。一般解密過程為:明文m≡cdmodn,應(yīng)用中國剩余定理,因為n=p×q,所以可以先計算{c1≡cmodpc2≡cmodq和{d1≡dmod(p?1)d2≡dmod(q?1){c1≡cmodpc2≡cmodq和{d1≡dmod(p-1)d2≡dmod(q-1)再計算m1≡cd111d1modp,m2≡cd222d2modq,最后用中國剩余定理解同余方程。{m≡m1modpm≡m2modqm≡(m1×q×q?1+m2×p×p?1)modn{m≡m1modpm≡m2modqm≡(m1×q×q-1+m2×p×p-1)modn式中:q×q-1≡1(modp),p×p-1≡1(modq)。可以看出,利用中國剩余定理,其中的密文、密鑰和明文數(shù)據(jù)c1,c2,d1,d2,m1,m2以及解密模數(shù)比原來的都要小,n(在實際運用中n有1024比特)分解為兩個相對較小的數(shù)(一般為512比特)p、q,眾所周知,大數(shù)(所謂大數(shù)是超出計算機基本數(shù)據(jù)類型能夠表示的數(shù))運算是非常復雜的,因此將n分解是很有意義的。利用中國剩余定理解密,并沒有加重編程的負擔,完全可以利用原有系統(tǒng)上的現(xiàn)成模塊(包括求逆和快速指數(shù)算法)。不過中國剩余定理雖然提高了解密速度,但也占用了更多的內(nèi)存。4算法的有效性測試在RSA系統(tǒng)中,不論是生成素數(shù)用到的素性檢測算法,還是加密、解密,以及求乘法逆元,都直接或間接的用到快速指數(shù)算法,它是實現(xiàn)RSA系統(tǒng)的關(guān)鍵?？焖僦笖?shù)算法是基于模運算的性質(zhì)(a×b)modn=[(amodn)×(bmodn)]modn,具體算法如下。對于以ammodn,將m表示為二進制形式bkbk-1…b0,可得以下快速指數(shù)算法在具體實現(xiàn)過程中,筆者提出以下改進。因為(d×d)modn=((n-d)×(n-d))modn,所以當d>n-d時,可以將(n-d)賦值給d,即由于大數(shù)計算的運算量大,對于幾百位的比特計算來說,這點改進對其計算性能的改變也應(yīng)該是非常可觀的。為驗證算法改進后的性能,作者對算法性能進行了測試(數(shù)據(jù)在計算機表示范圍內(nèi),對“Ihaveadream”這篇文章的加密文本進行解密測試),因為解密算法涉及了以上所有內(nèi)容,所以在解密模塊設(shè)置了GetTickCount()函數(shù)(該函數(shù)的運行時間為從模塊運行開始計時直到算法結(jié)束)。當p、q分別為113,131ms時,用沒有改進的算法,計算機解密的運行時間為140ms;而用改進后的算法,計算機解密的時間則縮短為125ms;當p、q分別為59,227ms時,用沒有改進的算法,計算機解密的運行時間為141ms,而用改進后的算法,計算機解密的時間則縮短為125ms。若密鑰和密文數(shù)字越大(即大數(shù)),則這種改進的效果將越明顯。幾組數(shù)據(jù)的對比情況如表1所列。正如所預計的一樣,采用改進算法在提高速度的同時,程序?qū)?nèi)存的要求也有所增加,在p,q相同情況下,內(nèi)存使用情況(因為內(nèi)存不斷變化,筆者取的是變化過程中內(nèi)存最大時的數(shù)據(jù))的對比如表2所列。可以看出,使