《RSA算法和RSA數(shù)字簽名算法的實(shí)現(xiàn).doc》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《RSA算法和RSA數(shù)字簽名算法的實(shí)現(xiàn).doc（9頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、基于verilog的RSA實(shí)現(xiàn)和RSA數(shù)字簽名 題 目：基于verilog的RSA實(shí)現(xiàn)和RSA數(shù)字簽名 學(xué) 院： 專(zhuān) 業(yè)： 姓 名： 學(xué) 號(hào)：  摘要: RSA算法是一種公鑰密碼算法.實(shí)現(xiàn)RSA算法包括生成RSA密鑰,用RSA加密規(guī)則和解密規(guī)則處理數(shù)據(jù).RSA數(shù)字簽名算法利

2、用RSA算法實(shí)現(xiàn)數(shù)字簽名.本文詳述了RSA算法的基本原理, RSA加密算法的實(shí)現(xiàn)以及如何利用RSA實(shí)現(xiàn)數(shù)字簽名. 關(guān)鍵字: RSA算法, 數(shù)字簽名, 公開(kāi)密鑰, 私人密鑰, 加密, 解密 一、引言 隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展,信息安全性已成為亟待解決的問(wèn)題.公鑰密碼體制中,解密和加密密鑰不同,解密和加密可分離,通信雙方無(wú)須事先交換密鑰就可建立起保密通信,較好地解決了傳統(tǒng)密碼體制在網(wǎng)絡(luò)通信中出現(xiàn)的問(wèn)題.另外,隨著電子商務(wù)的發(fā)展,網(wǎng)絡(luò)上資金的電子交換日益頻繁,如何防止信息的偽造和欺騙也成為非常重要的問(wèn)題.數(shù)字簽名可以起到身份認(rèn)證,核準(zhǔn)數(shù)據(jù)完整性的作用.目前關(guān)于數(shù)字簽名的研究主要集中基

3、于公鑰密碼體制的數(shù)字簽名. 公鑰密碼體制的特點(diǎn)是:為每個(gè)用戶(hù)產(chǎn)生一對(duì)密鑰(PK和SK);PK公開(kāi),SK保密;從PK推出SK是很困難的;A,B雙方通信時(shí),A通過(guò)任何途徑取得B的公鑰,用B的公鑰加密信息.加密后的信息可通過(guò)任何不安全信道發(fā)送.B收到密文信息后,用自己私鑰解密恢復(fù)出明文. 公鑰密碼體制已成為確保信息的安全性的關(guān)鍵技術(shù).RSA公鑰密碼體制到目前為止還是一種認(rèn)可為安全的體制.本文詳述了RSA算法和用RSA算法實(shí)現(xiàn)數(shù)字簽名的理論,以及它們?cè)趯?shí)際應(yīng)用中的實(shí)現(xiàn). 二、RSA算法和RSA數(shù)字簽名算法的理論描述 1 RSA算法 RSA算法的理論基礎(chǔ)是一種特殊的可逆

4、模冪運(yùn)算. 設(shè)n是兩個(gè)不同奇素?cái)?shù)p和q的積,即:n=pq, (n)=(p-1)(q-1). 定義密鑰空間 k={(n,p,q,d,e)|n=pq,p和q是素?cái)?shù),de1 mod (n),e為隨機(jī)整數(shù)}, 對(duì)每一個(gè)k=(n,p,q,d,e), 定義加密變換為 Ek(x)=xb mod n,xZn; 解密變換為 Dk(x)=ya mod n,yZn,Zn為整數(shù)集合. 公開(kāi)n和b,保密p,q和a. 為證明加密變換Ek和解密變換 Dk滿(mǎn)足Dk(Ek(x))=x,這里不加證明的引用下面兩個(gè)定理: 定理1(Euler)對(duì)任意的a(Zn*,有a((n)(1 mod n,其

5、中Zn*={x(Zn|gcd(x,n)=1},(()表示Euler函數(shù). 定理2 設(shè)p和q是兩個(gè)不同的素?cái)?shù),n=pq, ((n)=(p-1)(q-1),對(duì)任意的x(Zn及任意的非負(fù)整數(shù)k,有 xk((n)+1(x mod n. 現(xiàn)在來(lái)證明RSA算法的加密變換和解密變換的正確性. 證明: 對(duì)于加密變換Ek和解密變換Dk.因?yàn)閍b1 mod (n),所以可設(shè)ab=t(n)+1,t是整數(shù)且t1.對(duì)于任意的xZn,有Dk(Ek(x))Dk(xb) (xb)axt(n)+1x mod n.因此解密過(guò)程是正確的. 2 RSA數(shù)字簽名算法 RSA數(shù)字簽名算法的過(guò)程為

6、:A對(duì)明文m用解密變換作: s Dk (m)=md mod n,其中d,n為A的私人密鑰,只有A才知道它;B收到A的簽名后,用A的公鑰和加密變換得到明文,因: Ek(s)= Ek(Dk (m))= (md)e mod n,又 de1 mod (n)即de=l(n)+1,根據(jù)歐拉定理m(n)=1 mod n,所以Ek(s)=ml(n)+1=[m(n)]em=m mod n.若明文m和簽名s一起送給用戶(hù)B,B可以確信信息確實(shí)是A發(fā)送的.同時(shí)A也不能否認(rèn)送給這個(gè)信息,因?yàn)槌薃本人外,其他任何人都無(wú)法由明文m產(chǎn)生s.因此RSA數(shù)字簽名方案是可行的. 但是RSA數(shù)字簽名算法存在著因計(jì)算方法本

7、身同構(gòu)造成簽名易被偽造和計(jì)算時(shí)間長(zhǎng)的弱點(diǎn),因此實(shí)際對(duì)文件簽名前,需要對(duì)消息做MD5變換. MD5函數(shù)是一種單向散列函數(shù),它將任意長(zhǎng)度的消息壓縮成128位的消息摘要.應(yīng)用MD5的單向性(即給定散列值,計(jì)算消息很難)和抗碰撞性(即給定消息M,要找到另一消息M 并滿(mǎn)足兩者的散列值很難),可以實(shí)現(xiàn)信息的完整性檢驗(yàn).另外該函數(shù)的設(shè)計(jì)不基于任何假設(shè)和密碼體制而直接構(gòu)造,執(zhí)行的速度快,是一種被廣泛認(rèn)可的單向散列算法. 三、RSA算法的實(shí)現(xiàn) RSA算法的實(shí)現(xiàn)分為:生成密鑰,加密,解密 1 密鑰的生成： 私鑰的產(chǎn)生：本實(shí)驗(yàn)鑒于運(yùn)算速度，和存儲(chǔ)器的選擇。采用由小到大選擇一與(P-1)

8、*(Q-1)互質(zhì)的e值。 公鑰的產(chǎn)生：通過(guò)e*d==1mod(n)算出d的值，d即為公鑰的值。 2 生成RSA密鑰需完成下列步驟: (1) 選擇e的值為3至65536; (2) 隨機(jī)生成大素?cái)?shù)p,直到gcd (e,p-1)=1; 其中g(shù)cd(a,b)表示a,b取最大公約數(shù) (3) 隨機(jī)生成不同于p的大素?cái)?shù)q,直到 gcd (e,q-1)=1; (4) 計(jì)算n=pq , (n)=(p-1)(q-1); (5) 計(jì)算d,滿(mǎn)足de1 (mod (n)); (6) 計(jì)算d mod (p-1), d mod (q-1); (7) 計(jì)算q-1 mod p; (8) 將n,e放入

9、RSA公鑰;將n,e,d mod (p-1),d mod (q-1) q-1 mod p放入RSA私鑰. 2.1 隨機(jī)數(shù)的產(chǎn)生 隨機(jī)數(shù)不僅用于密鑰生成,也用作公鑰加密時(shí)的填充字符.它必須具有足夠的隨機(jī)性,以防止破譯者掌握隨機(jī)數(shù)的規(guī)律性后重現(xiàn)密鑰的配制過(guò)程或者探測(cè)到加密塊中的明文.因?yàn)樵谟?jì)算機(jī)上不可能產(chǎn)生真正的隨機(jī)數(shù),實(shí)際采用周期大于2256位的偽隨機(jī)序列發(fā)生器. 實(shí)現(xiàn)過(guò)程為: 通過(guò)PRBS算法，實(shí)現(xiàn)PRBS隨機(jī)碼。通過(guò)一定時(shí)間隨機(jī)選出一個(gè)素?cái)?shù)。 2.2 素?cái)?shù)的產(chǎn)生 對(duì)隨機(jī)數(shù)作素性檢測(cè),若通過(guò)則為素?cái)?shù);否則增加一個(gè)步長(zhǎng)后再做素性檢測(cè),直到找出素?cái)?shù).素性檢測(cè)

10、采用Fermat測(cè)試.這個(gè)算法的理論依據(jù)是費(fèi)爾馬小定理:如果m是一個(gè)素?cái)?shù),且a不是m的倍數(shù),那么根據(jù)費(fèi)爾馬小定理有:a m-1=1 ( mod m). 實(shí)際應(yīng)用時(shí):a m-1 = 1 ( mod m) a m = a ( mod m) a= a m ( mod m), 因此對(duì)于整數(shù)m,只需計(jì)算a m ( mod m),再將結(jié)果與a比較,如果兩者相同,則m為素?cái)?shù).選取a=2,則a一定不會(huì)是任何素?cái)?shù)的倍數(shù). 3 加密過(guò)程 加密規(guī)則為:Ek(x)=xb mod n,xZn 加密過(guò)程的輸入為:明文數(shù)據(jù)D,模數(shù)n, 加密指數(shù)e(公鑰加密)或解密指數(shù)d(私鑰加密).輸出為密文.D的長(zhǎng)

11、度不超過(guò)[log2n]-11,以確保轉(zhuǎn)換為PKCS格式時(shí),填充串的數(shù)目不為0. 格式化明文. 采用PKCS格式: EB = 00 || BT || PS || 00 || D 其中BT表示塊的類(lèi)型,PS為填充串,D為明文數(shù)據(jù).開(kāi)頭為0確保EB長(zhǎng)度大于k.對(duì)公鑰加密BT=02,對(duì)私鑰解密BT=01.當(dāng)BT=02時(shí),PS為非0隨機(jī)數(shù);當(dāng)BT=01,PS值為FF. 明文由字符型數(shù)據(jù)轉(zhuǎn)換成整型數(shù)據(jù). RSA計(jì)算. 為整數(shù)加密塊x作模冪運(yùn)算:y = x^c mod n,0 <= y 為密文,公鑰加密時(shí),c為公鑰加密指數(shù)e;私鑰加密時(shí),c為私鑰加密指數(shù)d. 密文由整

12、型數(shù)據(jù)轉(zhuǎn)換成字符型數(shù)據(jù). 4 解密過(guò)程 解密規(guī)則為 Dk(x)=yc mod n,yZn,Zn為整數(shù)集合,x為密文. 解密過(guò)程的輸入為:密文ED;模數(shù)n;加密指數(shù)e(公鑰解密)或解密指數(shù)d(私鑰解密),結(jié)果為明文. (1) 密文整型化. (2) RSA計(jì)算. 對(duì)密文做模冪運(yùn)算:x = y^c mod n, 0 <= x < n .,其中x為明文. (3) 此時(shí)明文為整型數(shù)據(jù),轉(zhuǎn)換為ASCII型數(shù)據(jù),得到PKCS格式的明文. (4) 從PKCS格式明文中分離出原明文. 從PKCS格式分離明文的過(guò)程也是檢查 數(shù)據(jù)完整性的過(guò)程.若出現(xiàn)以下問(wèn)題則解密失敗:不能清楚的分割

13、;填充字符 少于64位或與BT所注明的類(lèi)型不匹配;BT與實(shí)際操作類(lèi)型不符. 五、RSA數(shù)字簽名算法的實(shí)現(xiàn) RSA數(shù)字簽名算法,包括簽名算法和驗(yàn)證簽名算法.首先用MD5算法對(duì)信息作散列計(jì)算.簽名的過(guò)程需用戶(hù)的私鑰,驗(yàn)證過(guò)程需用戶(hù)的公鑰.A用簽名算法將字符串形式的消息處理成簽名;B用驗(yàn)證簽名算法驗(yàn)證簽名是否是A對(duì)消息的簽名,確認(rèn)是A發(fā)送的消息;消息沒(méi)有被攥改過(guò);A一定發(fā)送過(guò)消息. 1 簽名算法 簽名算法包括三步:消息摘要計(jì)算,RSA加密. 消息摘要計(jì)算. 消息在簽名前首先通過(guò)MD5計(jì)算,生成128位的消息摘要 digest. 對(duì)摘要作RSA計(jì)算. 用加密算法,采用簽名者的

14、私鑰加密消息摘要,得到加密后的字符串.加密算法中使用的加密塊為01類(lèi)型. 2 驗(yàn)證簽名算法 驗(yàn)證簽名算法包括兩步:RSA解密得簽名者的消息摘要,驗(yàn)證者對(duì)原消息計(jì)算摘要,比較兩個(gè)消息摘要.驗(yàn)證簽名的過(guò)程輸入為消息,簽名者的公鑰,簽名;輸出為驗(yàn)證的結(jié)果,即是否是正確的簽名. RSA解密. 簽名實(shí)際是加密的字符串.用3.5所述的解密算法,采用簽名者的公鑰對(duì)這個(gè)加密的字符串解密.解密的結(jié)果應(yīng)為128位的消息摘要.在解密過(guò)程中,若出現(xiàn)得到的加密塊的類(lèi)型不是01,則解密失敗.簽名不正確. 消息摘要計(jì)算和比較. 驗(yàn)證者對(duì)消息用MD5算法重新計(jì)算,得到驗(yàn)證者自己的消息摘要.驗(yàn)證者比

15、較解密得到的消息摘要和自己的消息摘要,如果兩者相同,則驗(yàn)證成功,可以確認(rèn)消息的完整性及簽名確實(shí)為簽名者的;否則,驗(yàn)證失敗. 六、RSA算法的時(shí)間復(fù)雜性： RSA算法的時(shí)間復(fù)雜性取決于它所設(shè)計(jì)的幾個(gè)基本運(yùn)算的時(shí)間復(fù)雜性. 密鑰生成過(guò)程時(shí)間主要是生成隨機(jī)素?cái)?shù)的時(shí)間及計(jì)算公鑰和私鑰的模乘法的時(shí)間.生成隨機(jī)素?cái)?shù)的時(shí)間在于完成對(duì)隨機(jī)大數(shù)的Fermat測(cè)試的時(shí)間,Fermat測(cè)試的時(shí)間復(fù)雜度為O((log2n)3),n所測(cè)試的整數(shù).模乘法的計(jì)算方法采取先計(jì)算兩個(gè)數(shù)的乘積,再取模n,時(shí)間復(fù)雜性為O((log2n)2). RSA加密解密計(jì)算的時(shí)間主要是模冪運(yùn)算的時(shí)間,即形式為xc

16、mod n的函數(shù)的運(yùn)算時(shí)間.模冪算法采取平方乘算法,設(shè)l是c的長(zhǎng)度,則計(jì)算xc mod n至多需要2l次模乘法,因?yàn)閘[log2n]+1,所以模冪運(yùn)算能在時(shí)間O((log2n)3)內(nèi)完成.因此,RSA的加密和解密均可在多項(xiàng)式時(shí)間內(nèi)完成. 七、RSA實(shí)現(xiàn)verilog程序： //輸入十進(jìn)制必須每位都要轉(zhuǎn)換為二進(jìn)制輸入。 //****************************************************************** module RSA (input [15:0] input_number,//輸入分別用四位格雷碼表示一個(gè)十進(jìn)制數(shù)字. o

17、utput reg[15:0] output_code //輸出分別用四位格雷碼表示一個(gè)十進(jìn)制數(shù)字. ); reg[15:0] in_dec; //輸入的十進(jìn)制寄存器。 reg[47:0] out_dec; //輸出結(jié)果. reg [7:0] P,Q; reg [7:0] reger; reg [7:0] ruslt_nub1,ruslt_nub2; reg [31:0] n; reg [31:0] n_tem; //n_tem==(P-1)*(q-1) reg [15:0] e; reg [15:0] d; integer i,j,x

18、,int_nub; initial begin e=3; d=1; n=3013; n_tem=b0; reger=8b10111001; end always begin if(reger[0]!=0) ruslt_nub1=reger; else begin reger[0]=reger[7]^reger[6]; reger={reger[6:0],reger[7]}; end if(reger[0]!=b0 && reger[7]!=b1) ruslt_nub2

19、=reger; else begin reger[0]=reger[7]^reger[6]; reger={reger[6:0],reger[7]}; end if((ruslt_nub1>ruslt_nub2)||ruslt_nub1%ruslt_nub2!=0) begin P=ruslt_nub1; Q=ruslt_nub2; end else begin P=b0; Q=b0; end end always begin begin n_tem=(P-1

20、)*(Q-1); n=P*Q; in_dec[15:0]=input_number[3:0]+10*input_number[7:4]+100*input_number[11:8]+1000*input_number[15:12]; if(i

21、gin e=j; j=0; end else j=j+1; end else j=0; end always begin if(e*x>n_tem) int_nub=(e*x-1)%n_tem; else x=x+1; if(int_nub%1==0) begin d=int_nub; x=1; end else int_nub=0; end endmodule 八、通過(guò)Quartus II仿真的底層電路圖： 九、結(jié)束語(yǔ)： 本文討論了RSA算法的基本原理和RSA的verilog實(shí)現(xiàn).RSA算法是一種安全技術(shù),但是RSA算法的安全性只是一種計(jì)算安全性,絕不是無(wú)條件的安全性,這是由它的理論基礎(chǔ)決定的.本文基于硬件實(shí)現(xiàn)RSA算法，在實(shí)際應(yīng)用中發(fā)揮了FPGA的高速性和FPGA在實(shí)際嵌入式系統(tǒng)中的方便性。 但是本文有很多不足，本文的實(shí)現(xiàn)比較簡(jiǎn)單，沒(méi)有把e值取得足夠大。而且也沒(méi)有考慮由于密鑰和算法中巨大的數(shù)字而引起的存儲(chǔ)空間的問(wèn)題，所以本文離應(yīng)用還有一段距離。