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

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

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