RSA算法和RSA數(shù)字簽名算法的實現(xiàn).doc

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

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

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

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

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

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

6、:A對明文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一起送給用戶B,B可以確信信息確實是A發(fā)送的.同時A也不能否認送給這個信息,因為除了A本人外,其他任何人都無法由明文m產(chǎn)生s.因此RSA數(shù)字簽名方案是可行的. 但是RSA數(shù)字簽名算法存在著因計算方法本

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

8、*(Q-1)互質(zhì)的e值。 公鑰的產(chǎn)生：通過e*d==1mod(n)算出d的值，d即為公鑰的值。 2 生成RSA密鑰需完成下列步驟: (1) 選擇e的值為3至65536; (2) 隨機生成大素數(shù)p,直到gcd (e,p-1)=1; 其中g(shù)cd(a,b)表示a,b取最大公約數(shù) (3) 隨機生成不同于p的大素數(shù)q,直到 gcd (e,q-1)=1; (4) 計算n=pq , (n)=(p-1)(q-1); (5) 計算d,滿足de1 (mod (n)); (6) 計算d mod (p-1), d mod (q-1); (7) 計算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 隨機數(shù)的產(chǎn)生 隨機數(shù)不僅用于密鑰生成,也用作公鑰加密時的填充字符.它必須具有足夠的隨機性,以防止破譯者掌握隨機數(shù)的規(guī)律性后重現(xiàn)密鑰的配制過程或者探測到加密塊中的明文.因為在計算機上不可能產(chǎn)生真正的隨機數(shù),實際采用周期大于2256位的偽隨機序列發(fā)生器. 實現(xiàn)過程為: 通過PRBS算法，實現(xiàn)PRBS隨機碼。通過一定時間隨機選出一個素數(shù)。 2.2 素數(shù)的產(chǎn)生 對隨機數(shù)作素性檢測,若通過則為素數(shù);否則增加一個步長后再做素性檢測,直到找出素數(shù).素性檢測

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

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

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

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

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

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

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

17、utput reg[15:0] output_code //輸出分別用四位格雷碼表示一個十進制數(shù)字. ); reg[15:0] in_dec; //輸入的十進制寄存器。 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 八、通過Quartus II仿真的底層電路圖： 九、結(jié)束語： 本文討論了RSA算法的基本原理和RSA的verilog實現(xiàn).RSA算法是一種安全技術(shù),但是RSA算法的安全性只是一種計算安全性,絕不是無條件的安全性,這是由它的理論基礎(chǔ)決定的.本文基于硬件實現(xiàn)RSA算法，在實際應(yīng)用中發(fā)揮了FPGA的高速性和FPGA在實際嵌入式系統(tǒng)中的方便性。 但是本文有很多不足，本文的實現(xiàn)比較簡單，沒有把e值取得足夠大。而且也沒有考慮由于密鑰和算法中巨大的數(shù)字而引起的存儲空間的問題，所以本文離應(yīng)用還有一段距離。