華北電力大學(xué)-網(wǎng)絡(luò)信息安全綜合實驗報告

1、綜合實驗報告（ 2013 - 2014 年度第 1 學(xué)期 ）名稱： 網(wǎng)絡(luò)信息安全綜合實驗題目： RSA公鑰加密解密院 系： 計算機系 班 級： 網(wǎng)絡(luò)工程 學(xué) 號：學(xué)生姓名：指導(dǎo)教師： 李天設(shè)計周數(shù)： 1 周成 績：日期： 2013 年 1月 18日、綜合實驗的目的與要求要求：了解 RSA產(chǎn)生公鑰和私鑰的方法，掌握 RSA 的加密、解密過程，編寫程序設(shè)計 RSA 加解密工具。RSA加解密參考： RSA的安全性依賴于大數(shù)分解， 公鑰和私鑰都是兩個大素數(shù) (大于 100 個十進制位) 的函數(shù)。據(jù)猜測， 從一個密鑰和密文推斷出明文的難度等同于分解兩個大素數(shù) 的積。密鑰的產(chǎn)生：1. 選擇兩個保密的大素數(shù)

2、 p 和 q；2. 計算 n=p*q 和歐拉函數(shù)值 E(n)=(p-1)(q-1) ；3. 選一整數(shù) e，且滿足 1<e<E(n) 和 gcd(E(n),e)=1 ；4. 計算 d，且滿足 d*e=1 mod E(n) ；5. 公鑰為 e, n ，私鑰 d, n 。二、RSA算法的描述1RSA 依賴大數(shù)運算，目前主流 RSA 算法都建立在 1024 位的大數(shù)運算之上。 而大多數(shù)的編譯器只能支持到 64 位的整數(shù)運算，即我們在運算中所使用的整數(shù)必須小于等 于 64 位，即： 0xffffffffffffffff，也就是 18446744073709551615，這遠(yuǎn)遠(yuǎn)達不到 RSA

3、的需要，于是需要專門建立大數(shù)運算庫來解決這一問題。 最簡單的辦法是將大數(shù)當(dāng)作數(shù)組進行 處理，也就是將大數(shù)用 09 這十個數(shù)字組成的數(shù)組進行表示，然后模擬人們手工進行“豎 式計算”的過程編寫其加減乘除函數(shù)。但是這樣做效率很低，因為二進制為 1024 位的大數(shù) 其十進制也有三百多位， 對于任何一種運算， 都需要在兩個有數(shù)百個元素的數(shù)組空間上做多 重循環(huán)， 還需要許多額外的空間存放計算的進退位標(biāo)志及中間結(jié)果。另外， 對于某些特殊的運算而言， 采用二進制會使計算過程大大簡化， 這種大數(shù)表示方法轉(zhuǎn)化成二進制顯然非常麻 煩，所以在某些實例中則干脆采用了二進制數(shù)組的方法來記錄大數(shù)，這樣效率就更低了。 一個有

4、效的改進方法是將大數(shù)表示為一個 n 進制數(shù)組， n 可以取值為 2 的 16 次方，即 0x1000，假如將一個二進制為 1024位的大數(shù)轉(zhuǎn)化成 0x1000 進制，它就變成了 64位，而每 一位的取值范圍就不是二進制的 01 或十進制的 09，而是 0-0xffff ，我們正好可以用一 個無符號整數(shù)來表示這一數(shù)值。所以 1024 位的大數(shù)就是一個有 64 個元素的 unsigned int 數(shù)組，針對 unsigned int 數(shù)組進行各種運算所需的循環(huán)規(guī)模至多 64 次而已。而且 0x10000 進制 與二 進制， 對于計 算機來 說， 幾乎 是一回 事，轉(zhuǎn) 換非 常容 易。加 法: A=

5、Sumi=0 to p(Ai*0x10000*i) ； B=Sumi=0 to q(Bi*0x10000*i) ， p>=q ； C=Sumi=0 to n(Ci*0x10000*i)=A+B。 如 果 用 carryi 記 錄 每 次 的 進 位 則 有 ：Ci=Ai+Bi+carryi-1-carryi*0x10000 ， 其 中 carry-1=0 。 若 Ai+Bi+carryi-1>0xffffffff ，則 carryi=1 ；反之則 carryi=0 ，若 carryp=0 ， 則 n=p；反之則 n=p+1。減法與加法同理。因 此 ： Ci=Sumj=0 to q(

6、Ai-j*Bj)+carryi-1-carryi*0x10000 ， 其 中 carry-1=0 ， carryi=(Sumj=0 to q(Ai-j*Bj)+carryi-1)/0x10000， n=p+q-1 ，若 carryn>0 ，則 n=n+1， Cn=carry除 法 設(shè) A=Sumi=0 to p(Ai*0x10000*i) ， B=Sumi=0 to q(Bi*0x10000*i)，p>=q， C=Sumi=0 to n(Ci*0x10000*i)=A/B。由于無法將 B 對 A “試商”， 我們只能轉(zhuǎn)換成 Bq 對 Ap 的試商來得到一個近似值， 所以 我 們不

7、能 夠 直 接 計 算 C。 但 是 ， 我 們 可 以 一步 一 步 地 逼 近 C。 顯 然 ， (Ap/Bq-1)*0x10000*(p-q)<C ， 令 X=0 ， 重 復(fù) A=A-X*B ， X=X+(Ap/Bq-1)*0x10000*(p-q) ，直到 A<B。則有 X=C。1、選取長度相等的兩個大素數(shù) p 和 q，計算其乘積： n = pq 然后隨機選取加密密鑰 e，使 e和(p 1)(q 1)互素。 最后用歐幾里德擴展算法計算解密密鑰d，以滿足ed = 1(mod(p 1) ( q 1)即 d = e 1 mod(p 1)(q 1)e和 n是公鑰， d 是私鑰2、加

8、密公式如下： ci = mie ( mod n)3、解密時，取每一密文分組 ci 并計算：mi = cid ( mod n )Cid = (mie)d = mi(ed) = mik(p1)(q1)+1 = mi mik( p1)(q 1) = mi *1 = mi4、消息也可以用 d 加密用 e 解密三、編程思路編程思路總共分為以下部分：1、檢驗兩個數(shù)是否互素；2、由歐拉公式算出相應(yīng)的密鑰 d；3、實現(xiàn)冪函數(shù)的取余，從而得以進行解密或加密。4、實現(xiàn)主要函數(shù)編寫。實現(xiàn) RSA算法。并加解密。說明：為了方便實現(xiàn)，分組可以小一點，比如兩個字母一組。(1) 選擇兩個大的素數(shù) p 和 q(典型情況下為

9、1024 位)(2) 計算 n = p * q 和 z = (p-1)*(q-1 ).(3) 選擇一個與 z 互素的數(shù)，將它稱為 d(4) 找到 e，使其滿足 e*d = 1 mod z提前計算出這些參數(shù)以后， 我們就可以開始執(zhí)行加密了。 首先將明文分成塊， 使得每個明文 消息 P落在間隔 0*P<n中。為了做到這一點， 只要將明文劃分成 k位的塊即可， 這里 k是滿 足 2k<n 的最大整數(shù)。為了加密一個消息 P，只要計算 C=Pe(mod n) 即可。為了解密 C，只要計算 P=Cd(mod n) 即可?？梢宰C明，對于指定范圍內(nèi)的所有P，加密盒解密互為反函數(shù)。為了執(zhí)行加密，你需

10、要 e 和 n ；為了執(zhí)行解密，你需要 d 和 n。因此，公鑰是有( e ，n)對組成，而私鑰是有( d， n)對組成。實例：根據(jù)已知參數(shù)： p=3， q=11，M=2，計算公私鑰，并對明文進行加密，然后對密文 進行解密。由題意知： n = p * q 33，z = (p-1 )*(q-1 ) 20，選 d7，計算得 e=3，所以C=Me(mod n) 8M=Cd(mod n) 2四、主要程序說明1. 關(guān)鍵環(huán)節(jié)1求模逆元的擴展歐幾里德算法原理：正整數(shù) a 和 b 滿足 sn*a + tn*b =(a,b), 當(dāng) (a,b)=1 時， sn = a-1 mod b其中 s0 = 1,s1 = 0

11、,sj = (sj-2) (qj-1)*s(j-1 ；t0 = 0,tj = (tj-2) (qj-1)*t(j-1) 輸入大數(shù) a 和 b輸出： a-1 mod b 或 0(不存在逆元)(1) s0 = 1,s1 = 0( 2) while b>0 do1.1 q = a/b;s2 = s0-q*s1;1.2 s0 = s1;s1 = s2;1.3 t = b;b = a%b;a = t;( 3) if a=1 return s0;else return 0;2. 明文(數(shù)值)長度要小于 key_N，才符合 RSA算法，否則很容易出錯，我選擇了一個大于 key_N 的明文，發(fā)現(xiàn)經(jīng)過驗證

12、并不符合RSA算法。那么，處理那些明文(數(shù)值)很大的辦法就是將明文分成一小段一小段， 否則，解密的信息必然是一堆亂碼 (除非原明文數(shù)值并不大) 。 分成一小段之后， 然后利用加密公式和解密公式對其進行處理， 這樣得到的結(jié)果就是準(zhǔn)確結(jié) 果了。2. 主要函數(shù)公鑰和私鑰的生成 void generate_key()( 1)首先利用 strongprime 函數(shù)生成兩個素數(shù) key_P_Q0,key_P_Q1, 然后利用 multiply 函數(shù)得到 key_N = key_P_Q0 * key_P_Q1,用 subtract 函數(shù)和 add 函數(shù)實現(xiàn) key_Z =(key_P_Q0 - 1 ) *

13、(key_P_Q1 1) = key_N (key_P_Q0 + key_P_Q1) + 1。( 2)隨機生成一個密鑰 key_D，然后利用 extend_gcd 函數(shù)求同余方程 key_D *key_E mod key_Z = 1 。得到 key_E, 作為公鑰。( 3)至此將公鑰( key_N,key_E )寫入文件中，將私鑰( key_N,key_D )寫入文件中保存。 加密信息 void encode_information()將加密的信息長度判斷是否大于 key_N的長度，如果大于 key_N的長度， 應(yīng)該將加密信息分 成一小段一小段， 各小段長度均小于 key_N 長度，然后利用讀

14、取已經(jīng)保存在文件中的公鑰和 私鑰， 對加密信息每小段每小段進行加密， 并將加密信息密文存放到加密文件中。 加密將用 到的函數(shù)為 powmod(key_P,key_E,key_N, key_C) 。解密信息 void decode_information()解密信息和加密信息采用同樣的道理， 即利用保存好的密鑰對密文一段一段進行解密。 解密 將用到的函數(shù)為 Powmod(key_C,key_D,key_N,key_P)五、實驗結(jié)果( 1)公鑰長度為 1024 位進行驗證：圖（ 1）生成公鑰和私鑰圖（ 2）加密文件 e:200424321.txt ，并顯示加密文件中信息圖（ 3）解密文件，并顯示解

15、密文件中信息圖（ 4）選擇鍵。可以選擇 4 程序結(jié)束圖（ 5） e:200424321.txt加密后的密文2）公鑰長度為 2048 位進行驗證：圖（ 6）生成公鑰和私鑰圖（ 7）對 e:200424322.txt文本文件進行加密圖（ 8）對加密密文 e:20042432key_C.dat 進行解密，并存放在 e:222.txt 中，并 在屏幕上顯示解密后的信息。圖（ 9）圖中可以看到其中原明文信息為 2.txt ，對它加密后 key_P_Q.dat 中存放兩個大 素數(shù)， key_N.dat 存放兩個素數(shù)相乘后的結(jié)果。 Key_D 為隨機生成的與 key_Z （存放在key_Z.dat 文件中)

16、 ( 即 key_Z = key_N key_P_Q0 key_P_Q1 + 1) 互素的大整數(shù)，存放在 key_D.dat 文件中。 key_E 為解同余方程后的大數(shù)，存放在 key_E.dat 文件中。其中 key_C 為加密后的明文信息，存放在 key_C.dat 文件中，并在解密時對這個 密文文件進行解密。圖（ 10） e:200424322.txt加密后的密文六、綜合實驗總結(jié)通過這次試驗我對非對稱密碼算法RSA 的理解加深了，會運用一些現(xiàn)成的算法進行編程，對一些比較復(fù)雜的算法開始基本認(rèn)識并深刻的掌握。對對稱密碼算法 DES更加的深刻， 程序要仔細(xì)耐心調(diào)試察看， 不要被錯誤嚇到， 同時

17、在修改老師給的源程序的時候懂得了如何 細(xì)心的認(rèn)真的仔細(xì)的看每一個編程程序。通過這次的實驗，了解了非對稱密碼算法 RSA，會 運用一些現(xiàn)成的算法進行編程， 對一些比較復(fù)雜的算法開始基本認(rèn)識并深刻的掌握。 在以后 所涉及這方面的知識將會有全新的了解和掌握。RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因 為沒有證明破解 RSA 就一定需要作大數(shù)分解。經(jīng)過這次設(shè)計，使我學(xué)到了很多很多。首先 為對大數(shù)的認(rèn)識。大數(shù)的存儲形式靈活多樣，可以1， 0 二進制存儲，可以十進制存儲，也可以 2*n 進制存儲。對于講究空間效率來講，顯然，尋找合適的 n, 使用 2*n 進制存儲數(shù) 據(jù)

18、將會高效的多。而且，對于大數(shù)的運算技巧也要要求思考的嚴(yán)密一些。我通過參考 miracl 大數(shù)庫， 通過閱讀相關(guān)代碼， 弄懂了其大數(shù)存儲及實現(xiàn)機制。 而且， 現(xiàn)在想來， 我覺得我在閱讀代碼所花費的時間上有所不值。 我想， 如果我將花費的大半時間 用來自己寫一個大數(shù)庫， 將會實在的多。 已經(jīng)為我們設(shè)計好的大數(shù)庫雖然用起來方便， 但閱讀起來， 并弄懂其思想并不簡單。 特別是我認(rèn)識到老外寫的代碼靈活性太強， 他們寫代碼沒 有規(guī)矩的， 想到哪寫到哪，非常難以閱讀，特別在實現(xiàn)RSA算法中加密解密的算法時， 我始發(fā)現(xiàn)錯誤百出。 但經(jīng)過我一遍而且，我自己寫的代碼結(jié)構(gòu)性我覺得這是我比較慚愧的，終就沒有看懂到底在

19、寫些什么， 后來我干脆自己來寫，一寫， 又一遍的調(diào)試， 終于能夠順利實現(xiàn)了課程設(shè)計所要求的功能， 非常強，很好閱讀。算法實現(xiàn)也簡單易懂。然而，唯一遺憾之處就是借用了大數(shù)庫里現(xiàn)成的一些函數(shù)，miracl 大數(shù)庫如果我自己來寫個大數(shù)庫，也許心里會心安理得一些。不過，我完全弄懂了 里相關(guān)函數(shù)的運算機制。 并掌握了其實現(xiàn)機制?？梢哉f， 通過閱讀別人的代碼，也學(xué)到了不 少?？偟膩碚f， 我這次課程設(shè)計時間分配不大合理， 花在閱讀代碼的時間太長， 事實上它占 據(jù)了我大部分時間，如果我用這個時間自己來寫大數(shù)運算庫，恐怕早寫完了?；顑悍浅？?。 不過我依然欣慰，我從別人哪里的確學(xué)到了不少。程序運行相對順利， 通過

20、讀取代碼我們了解到密鑰生成中和加密處理一般都是依賴于數(shù) 據(jù)的位運算。 位運算， 對于計算機而言是最簡單的運算。 對于加密這種需要頻繁執(zhí)行的程序 應(yīng)用安慰運算應(yīng)是最為合適的。可以修改成為大數(shù)分解算法。目前， RSA 的一些變種算法 已被證明等價于大數(shù)分解。不管怎樣，分解 n 是最顯然的攻擊方法?，F(xiàn)在， 人們已能分解多 個十進制位的大素數(shù)。因此，模數(shù) n 必須選大一些，因具體適用情況而定。四、參考文獻1 斯托林斯 . 網(wǎng)絡(luò)安全基礎(chǔ)應(yīng)用與標(biāo)準(zhǔn) . 清華上大學(xué)出版社 , 2007.72 馬民，趙虹，孫犁等 . 計算機技術(shù)在電力系統(tǒng)故障診斷中的應(yīng)用 . 計算機學(xué)報， 2003，17（4）：13233 高

21、傳善 等 主編 數(shù)據(jù)通信與計算機網(wǎng)絡(luò) （第 2 版） 高等教育出版社 1999 年4 陳建偉 等 主編 計算機網(wǎng)絡(luò)與信息安全 中國林業(yè)出版社 2006 年附錄 1流程圖程序流程圖附錄 2核心代碼：extern "C"#include "miracl.h"#include "big.h"#include "stdlib.h"#include "string.h"#include "stdio.h"#include"malloc.h"static miracl

22、 *mip;static big pd,pl,ph;#define PRIME_BITS 512 /= int abs(int x)if (x>= 0)return x;else return (-x);/= / 產(chǎn)生一個強素數(shù)/= void strongprime(big p,int n,long seed1,long seed2)int r,r1,r2;irand(seed1); / 產(chǎn)生一個隨機數(shù)，即初始化BOOLbigbits(2*n/3,pd); / 生一個 2*n/3 位( bit )的 pd 隨機數(shù) nxprime(pd,pd); /nxprime(pd,x) 找到一個 x

23、 大于 pd 的素數(shù)，返回值為 expb2(n-1,ph); /ph = 2(n-1),即 2 的 (n-1) 次方divide(ph,pd,ph); /ph = ph/pdexpb2(n-2,pl); divide(pl,pd,pl); /pl=pl/pd subtract(ph,pl,ph); /ph = ph-plirand(seed2); bigrand(ph,ph);add(ph,pl,ph); r1=subdiv(pd,12,pl); /pl=pd/12 r2=subdiv(ph,12,pl); /pl=ph/12r=0; while (r1*(r2+r)%12!=5)r+;inc

24、r(ph,r,ph); /ph=ph+rdo /find p=2*r*pd+1 = 11 mod 12 multiply(ph,pd,p); /p = ph*pd premult(p,2,p); /p = p*2 incr(p,1,p);/p = p+1incr(ph,12,ph); /ph = ph+12 while (!isprime(p); /= / 同余 extend_gcd/= void extend_gcd(big key_D,big key_Z,big key_E)big s0,s1,s2,zero,z1;s0 = mirvar(1);/ 初始化為 1 s1 = mirvar(0

25、);s2 = mirvar(0); zero = mirvar(0);z1 = mirvar(0); copy(key_Z,z1);big q,t; q = mirvar(0); t = mirvar(0);while(compare(key_Z,zero) > 0)copy(key_Z,t); /t = key_Z divide(key_D, key_Z,q); /q= key_D / key_Zcopy(key_D, key_Z);/ key_Z = key_Dcopy(t, key_D);/ key_D = tmultiply(q,s1,t); /t = q*s1 subtract

26、(s0,t,s2); /s2 =s0 -q*s1copy(s1,s0); /s0 = s1 copy(s2,s1); /s1 =s2convert(1,t);/t = 1if(compare(t, key_D) != 0) convert(0, key_E);else if(compare(s0,zero) > 0)copy(s0, key_E);else add(s0,z1, key_E); return; /= / 生成公鑰和私鑰 generate_key()/= void generate_key() int i; long seed4;big one,key_P_Q2,key_N

27、,key_Z,key_D,key_E/*,key_ZR*/; FILE *outfile;mip=mirsys(100,0); / 初始化操作 pd=mirvar(0); pl=mirvar(0); ph=mirvar(0);one = mirvar(0); key_P_Q0=mirvar(0); key_P_Q1=mirvar(0);key_N = mirvar(0); key_Z = mirvar(0); key_D = mirvar(0); key_E = mirvar(0);for (i=0;i<4;i+)seedi = abs(brand();printf("ttn

28、正在產(chǎn)生公鑰和私鑰，請等候 n");/ 產(chǎn)生兩個素數(shù)strongprime(key_P_Q0,PRIME_BITS,seed0,seed1);strongprime(key_P_Q1,PRIME_BITS,seed2,seed3); multiply(key_P_Q0,key_P_Q1,key_N);/key_N = key_P_Q0 * key_P_Q1 mip->IOBASE=16;/ 寫到 key_P_Q.dat 文件中outfile=fopen("key_P_Q.dat","wt");cotnum(key_P_Q0,outfile

29、);cotnum(key_P_Q1,outfile);fclose(outfile);%dprintf("ttn 公 鑰 長 度 key_N = key_P_Q0 * key_P_Q1 有 位!n",logb2(key_N);printf("nt= 輸出公鑰 key_N=n"); cotnum(key_N,stdout);mip->IOBASE=16;/ 寫到 key_N.dat 文件中outfile=fopen("key_N.dat","wt");cotnum(key_N,outfile);fclose(o

30、utfile);/key_Z = key_N - key_P_Q0 - key_P_Q1 + 1; convert(1,one);subtract(key_N,key_P_Q0,key_Z);subtract(key_Z, key_P_Q1,key_Z);add(key_Z,one,key_Z);mip->IOBASE=16;/ 寫到 key_Z.dat 文件中outfile=fopen("key_Z.dat","w+");cotnum(key_Z,outfile);fclose(outfile);printf("nt= 輸出解密密鑰 k

31、ey_D=n");dobigrand(key_P_Q0,key_D);subtract(key_D,one,key_D);while(!isprime(key_D);cotnum(key_D,stdout);mip->IOBASE=16;/ 寫到 key_D.dat 文件中outfile=fopen("key_D.dat","w+");cotnum(key_D,outfile);fclose(outfile);printf("nt=- 輸出加密密鑰 key_E=n");extend_gcd(key_D,key_Z,ke

32、y_E);cotnum(key_E,stdout);mip->IOBASE=16;/ 寫到 key_E.dat 文件中outfile=fopen("key_E.dat","w+");cotnum(key_E,outfile);fclose(outfile);/=/ 加密 encode_information()/= void encode_information()big key_N,key_E,key_P,key_C;char buffer130,ifname32;int buffer_length,i = 0;FILE *infile,*out

33、file;BOOL flag;key_N = mirvar(0);key_E = mirvar(0);key_P = mirvar(0);key_C = mirvar(0);if (infile=fopen("key_N.dat","rt")=NULL)printf("n 不能打開文件 key_N.dat"); return ;mip->IOBASE=16;cinnum(key_N,infile);fclose(infile);if (infile=fopen("key_E.dat","rt&quo

34、t;)=NULL)printf("n 不能打開文件 key_E.dat"); return ;mip->IOBASE=16; cinnum(key_E,infile); fclose(infile);printf("t 要加密的文件為 = "); getchar();gets(ifname);if (infile=fopen(ifname,"rt")=NULL)printf("n不能打開文件%sn",ifname);return ;elseprintf("n正在加密信息 n");outfi

35、le =fopen("key_C.dat","w+");if (fgets(buffer,128,infile) = NULL) flag = true;elseflag = false;while(!flag)buffer_length = strlen(buffer); bufferbuffer_length = '0' mip->IOBASE=128; cinstr(key_P,buffer);cotnum(key_P,stdout);powmod(key_P,key_E,key_N,key_C);mip->IOBASE

36、=16;cotnum(key_C,outfile);if (fgets(buffer,128,infile) = NULL) flag = true;printf("n"); fclose(infile); fclose(outfile);/= / 解密 decode_information()/= void decode_information()big key_N,key_D,key_C,key_P;char ifname32;FILE *infile,*outfile;key_N = mirvar(0);key_D = mirvar(0);key_C = mirvar(0);key_P = mirvar(0);/ 打開 key_N.dat 文件，寫入 key_N if(outfile = fopen("key_N.dat","rt") = NULL) printf(" 不能打開 key_N.dat 文件 n"); return ; mip->IOBASE=16; cinnum(key_N,outfile); fclose(outfile);/