DH密鑰協(xié)商算法報告.doc

1、XXXX學(xué)院課程設(shè)計報告DH密鑰協(xié)商算法課程名稱： 密碼算法程序設(shè)計 學(xué)生姓名： 學(xué)生學(xué)號： 專業(yè)班級： 任課教師： 2014年12 月 1日指導(dǎo)老師評閱成績表學(xué)習(xí)與工作態(tài)度（30%）選題意義（10%）研究水平與設(shè)計能力（25%）課程設(shè)計說明說（論文）撰寫質(zhì)量（25%）設(shè)計創(chuàng)新（10%）總分指導(dǎo)老師簽名： 年 月 日課程設(shè)計答辯記錄及評價表學(xué)生講述情況教師主要提問記錄學(xué)生回答問題情況答辯評分評分項目分值評價參考標(biāo)準(zhǔn)評分總分優(yōu)良中及格差選題意義1098764研究水平與設(shè)計能力252320181510課程設(shè)計說明書（論文）撰寫質(zhì)量252320181510設(shè)計創(chuàng)新1098764答辯效果3028252

2、21915答辯小組成員簽名答辯小組組長簽名： 年 月 日課程設(shè)計成績評定表成績匯總評分項目評分比例分?jǐn)?shù)課程設(shè)計總分指導(dǎo)老師評分50%答辯小組評分50%目 錄1. 選題背景12. DH密鑰協(xié)商算法12.1 算法的產(chǎn)生12.2 算法的描述22.3 算法的安全性33.DH密鑰協(xié)商算法的實現(xiàn)43.1 設(shè)計要求43.1.1 功能要求43.2 模塊劃分及實現(xiàn)53.2.1 小素數(shù)試除53.2.2 模重復(fù)平方法53.2.3 Miller-Rabin檢測算法73.2.4 原根的產(chǎn)生83.2.5 產(chǎn)生隨機(jī)素數(shù)114.測試報告12結(jié) 論17參考文獻(xiàn)17附源代碼181. 選題背景密鑰協(xié)商實際上是一個協(xié)議，它通過兩個或

3、多個成員在一個公開的信道上通信聯(lián)合地建立一個秘密密鑰，一般情況下，一個密鑰協(xié)商方案的密鑰是某個函數(shù)的值，其輸入量由通信雙方提供，協(xié)商過程是由一系列的順序步驟完成的。會話密鑰由每個協(xié)議參與者分別產(chǎn)生的參數(shù)通過一定的計算得出。常見的密鑰協(xié)商協(xié)議，如IKE。密鑰協(xié)商協(xié)議的生成方式則可分為證書型和無證書型。證書型是指在會話密鑰的產(chǎn)生過程中，由一個可信的證書中心（CA）給參與密鑰協(xié)商的各方各分發(fā)一個證書，此證書中含有此方的公鑰，ID及其他信息。證書型密鑰協(xié)商協(xié)議的優(yōu)點是提供認(rèn)證，目前PKI（公鑰密碼體制）廣泛部署，比較成熟，應(yīng)用面廣，且由PKG管理公私鑰對有利于統(tǒng)一管理，缺點是計算代價大，需要一個可信的

4、CA，同時證書還需要維護(hù)。無證書型是指各方在進(jìn)行會話密鑰的協(xié)商過程中不需要證書的參與，這是目前密鑰協(xié)商協(xié)議的主流種類，優(yōu)點是不需要CA的參與，減少了計算量，尤其是在低耗環(huán)境下應(yīng)用的更多，同時安全性也不比證書型弱。幾乎沒有明顯的缺點，只是設(shè)計一個安全的更加低耗的無證書密鑰協(xié)商方案不是很容易?，F(xiàn)有的流行的密鑰協(xié)商協(xié)議，都使用了Diffie-Hellman，它們基本上可以看成是Diffie-Hellman的擴(kuò)展。也就是說，群組密鑰協(xié)商協(xié)議可以理解成如何使用Diffie-Hellman來實現(xiàn)群的密鑰交換。2. DH密鑰協(xié)商算法2.1 算法的產(chǎn)生Diffie-Hellman密鑰交換協(xié)議是第一個被提出的密

5、鑰協(xié)商方案，是美國斯坦福大學(xué)的W.Diffie和M.E.Hellman于1976年提出的，它是第一個發(fā)表的公鑰密碼體制，Diffie-Hellman算法的唯一目的就是使兩個用戶能安全的交換密鑰，從而得到一個共享的會話密鑰（秘密密鑰）。需要注意的是，該算法本身不能用于加密解密，只能用于密鑰的交換， 雙方確定要用的密鑰后，要使用其他對稱密鑰操作加密算法實際加密和解密消息。2.2 算法的描述1. 離散對數(shù)的概念： 1）原根：如果a是素數(shù)p的一個原根，那么數(shù)值：amodp，a2modp，a(p-1)modp是各不相同的整數(shù)，且以某種排列方式組成了從1到p-1的所有整數(shù)。 2）離散對數(shù)：如果對于一個整數(shù)

6、b和素數(shù)p的一個原根a，可以找到一個唯一的指數(shù)i，使得b=(ai)mod p，其中0ip-1，那么指數(shù)i稱為b的以a為基數(shù)的模p的離散對數(shù)。2. 算法有效性Diffie-Hellman算法的有效性依賴于計算離散對數(shù)的難度，其含義是：當(dāng)已知大素數(shù)p和它的一個原根a后，對給定的b，要計算i，被認(rèn)為是很困難的，而給定i計算b卻相對容易。3. Diffie-Hellman算法：假如用戶A和用戶B希望交換一個密鑰。取素數(shù)p和整數(shù)a，a是p的一個原根，公開a和p。 1）A選擇大的隨機(jī)數(shù)RA(0=RA=p-2)，并計算SA=(aRA) mod p，并且把SA發(fā)送給用戶B。 2）B選擇隨機(jī)數(shù)RB(0=RB=p

7、-2)，并計算SB=(aRB) mod p，并且把SB發(fā)送給用戶A。 3）A計算密鑰的方式是：K=(SB) RA modp，B計算密鑰的方式是：K=(SA) RB modp，證明：(SB) RA modp= (aRB modp) RA modp = (aRB) RA modp = (aRA) RBmodp (- 密鑰即為 a(RA*RB) modp) =(aRA modp) RB modp = (SA) RB modp由于RA和RB是保密的，而第三方只有p、a、SB、SA可以利用，只有通過取離散對數(shù)來確定密鑰，但對于大的素數(shù)p，計算離散對數(shù)是十分困難的。4. 例子：假如用戶Alice和用戶Bo

8、b希望交換一個密鑰，取一個素數(shù)p=97和97的一個原根a=5，Alice和Bob分別選擇秘密密鑰RA=36和RB=58，并計算各自的公開密鑰： SA=aRA modp=536 mod 97=50 SB=aRB modp=558 mod 97=44Alice和Bob交換了公開密鑰之后，計算共享密鑰如下： Alice：K=(SB) RA modp=4436 mod 97=75 Bob：K=(SA) RB modp=5058 mod 97=75Diffie-Hellman密鑰交換協(xié)議的基本模式如圖2-1所示：SA=aRA(mod p)用戶A 用戶BSB=aRB(mod p)圖2-1 Diffie-H

9、ellman密鑰交換協(xié)議的基本模式2.3 算法的安全性當(dāng)然，為了使這個例子變得安全，必須使用非常大的RA,RB 以及p， 否則可以實驗所有的可能取值。(總共有最多97個這樣的值, 就算RA和RB很大也無濟(jì)于事)。 如果p是一個至少 300 位的質(zhì)數(shù)，并且RA和RB至少有100位長， 那么即使使用全人類所有的計算資源和當(dāng)今最好的算法也不可能從a,p和a(RA*RB) modp中計算出 RA*RB。 這個問題就是著名的離散對數(shù)問題。注意g則不需要很大, 并且在一般的實踐中通常是2或者5。在最初的描述中，迪菲赫爾曼密鑰交換本身并沒有提供通訊雙方的身份驗證服務(wù)，因此它很容易受到中間人攻擊。 一個中間人

10、在信道的中央進(jìn)行兩次迪菲赫爾曼密鑰交換，一次和Alice另一次和Bob，就能夠成功的向Alice假裝自己是Bob，反之亦然。而攻擊者可以解密（讀取和存儲）任何一個人的信息并重新加密信息，然后傳遞給另一個人。因此通常都需要一個能夠驗證通訊雙方身份的機(jī)制來防止這類攻擊。 有很多種安全身份驗證解決方案使用到了迪菲赫爾曼密鑰交換。例如當(dāng)Alice和Bob共有一個公鑰基礎(chǔ)設(shè)施時，他們可以將他們的返回密鑰進(jìn)行簽名。有攻擊的Diffie-Hellman密鑰交換協(xié)議如圖2-2所示： SA=aRA(mod p) SA=aRA(mod p)用戶A 攻擊者C 用戶B SB=aRB(mod p) SB=aRB(mod

11、 p)圖2-2 有攻擊的Diffie-Hellman密鑰交換協(xié)議3. DH密鑰協(xié)商算法的實現(xiàn)3.1 設(shè)計要求3.1.1 功能要求（1）產(chǎn)生一個奇數(shù)p ，判斷是否是素數(shù)。素數(shù)要求介于214-215。先用小于20的素數(shù)去試除，再使用Miller-Rabin概率檢測算法進(jìn)行檢測；（2）求得模p 的一個原根，要求原根的值介于32-1024之間；（3）輸出雙方選擇的隨機(jī)數(shù)，隨機(jī)數(shù)介于25-27，使用模重復(fù)平方法進(jìn)行計算，輸出雙方的計算結(jié)果；（4）網(wǎng)絡(luò)傳輸方面，可以是C/S模式，也可以是B/S模式；（5）輸出最后協(xié)商的密鑰； 3.1.2 輸出要求（1）輸出奇數(shù)的產(chǎn)生過程，用函數(shù)實現(xiàn)產(chǎn)生滿足要求的奇數(shù)；（2

12、）輸出用小素數(shù)試除的判斷過程，并輸出每次試除之后的余數(shù)，用函數(shù)實現(xiàn)一次試除并返回試除之后的余數(shù)；（3）Miller-Rabin概率檢測算法運(yùn)行5次，輸出檢測過程及結(jié)果。用函數(shù)實現(xiàn)一次Miller-Rabin概率檢測算法并返回檢測結(jié)果；（4）如果不是奇素數(shù)，輸出下一個奇數(shù)產(chǎn)生的規(guī)則；（5）輸出產(chǎn)生模的一個原根的過程；（6）輸出使用模重復(fù)平方法進(jìn)行計算的過程和結(jié)果。3.2 模塊劃分及實現(xiàn)3.2.1 小素數(shù)試除算法描述：小素數(shù)試除主要是用隨機(jī)產(chǎn)生的數(shù)來試除小于20的素數(shù)，以此簡單判定該隨機(jī)數(shù)是否是素數(shù)。實現(xiàn)方式：以本次程序編寫為例，取小素數(shù)數(shù)組S_PrimeTable7 = 3, 5, 7, 11,

13、 13, 17, 19 ，用產(chǎn)生的大隨機(jī)數(shù)來除以數(shù)組中的元素，若所得余數(shù)不為0，則能暫時判斷該隨機(jī)數(shù)為素數(shù)。具體實現(xiàn)代碼如下：int SPrime(int odd)int i, remainder, k = 0;for (i = 0; i7; i+)remainder = odd % S_PrimeTablei;printf(第%d次小素數(shù)%d試除的余數(shù)為%d.n, i + 1, S_PrimeTablei, remainder);if (remainder = 0)k+;if(!k)printf(小素數(shù)試除判斷%d是素數(shù)。nn,odd);elseprintf(小素數(shù)試除判斷%d不是素數(shù)。nn

14、,odd);return !k;3.2.2 模重復(fù)平方法算法描述： 模重復(fù)平方法是對大整數(shù)模m和大整數(shù)e計算be(mod m)。在本次設(shè)計中，模重復(fù)平方法主要使用在米勒檢測算余值部分、求原根部分、SA和SB的計算以及最后密鑰的計算過程中，其中，SA和SB的計算以及最后密鑰的計算要求輸出計算過程。（為了界面顯示美觀，在此寫了兩個模重復(fù)平方算法的代碼，思路相同，只是在其中一個函數(shù)中寫了輸出計算過程，該函數(shù)用來計算SA和SB以及最后的密鑰。）實現(xiàn)方式：令a=1，并將十進(jìn)制數(shù)e寫成二進(jìn)制，若二進(jìn)制數(shù)值為1，則計算a(a*b)mod n,b(b*b)mod n；若二進(jìn)制數(shù)值為0，則計算aa mod n,

15、b(b*b)mod n。最后a即為最終計算結(jié)果。具體實現(xiàn)代碼如下：int MoChongFu(int m, int e,int n) int binary22;int count=0,i;int a=1,b; b=m;do binarycount=e%2;e=e/2;count+;while(e!=0);for(i=0;icount;i+)if(binaryi=1)a=(a*b)%n;b=(b*b)%n; /printf(a=%d, b=%dn,a,b);if(binaryi=0)a=a;b=(b*b)%n; /printf(a=%d, b=%dn,a,b);return a;3.2.3 Mi

16、ller-Rabin檢測算法算法描述：米勒檢測在本次設(shè)計中主要用來檢測在小素數(shù)判定了之后的隨機(jī)數(shù)是否是素數(shù)。實現(xiàn)方式：將待檢測的數(shù)n寫成n-1=2s*t，選取隨機(jī)數(shù)a，計算batmod n。若b mod n1，則n是素數(shù)。否則，做如下循環(huán)，循環(huán)次數(shù)為1s：如果b mod n-1，則b是素數(shù)，否則，bb*b mod n。具體實現(xiàn)代碼如下：int milejiance(int odd)int s=0,i,count=0;int a,b,t,num;num=odd-1;while(1) if(num%2=0)s+;num=num/2;elset=num;break;printf(將%d寫成%d-1=

17、2%d*%dttn,odd,odd,s,t);a=rand()%(odd-3)+2;printf(產(chǎn)生的隨機(jī)數(shù)a是：%dn,a);b=MoChongFu(a,t,odd);printf(第1次算出的余值是：%dn,b);if(b%odd=1|b=(odd-1) return 1;for(i=0;i1，m的歐拉函數(shù)a所有不同素因數(shù)是q1,q2,，qk，則g是模m的一個原根的充要條件是 g(a/qi)!=1(mod m),i=1,2，k 實現(xiàn)方式： 先求大素數(shù)的歐拉函數(shù)的素因數(shù)an，并通過素因數(shù)求得g的指數(shù)cn，接著驗證gcn 是否同余于1，對g=2,3，逐個驗算，直到算出最小的g值滿足gcn均不

18、同余于1，那么g便是大素數(shù)m的最小原根，因為當(dāng)cn遍歷歐拉函數(shù)a的簡化剩余系時，gcn遍歷模m的所有原根，所以可以通過歐拉函數(shù)的簡化剩余系求得滿足要求的原根。具體實現(xiàn)代碼如下：int yuangen(int yy)int n=2,g=0,q,k,j=0,a10;int i=0,l=0;int gg;int c10;int count=0,flag=0;q=yy-1;while(1)if (q%n=0)aj=n;j+;q=q/n;n+;if(qn)break;printf(模%d的歐拉函數(shù)分解質(zhì)因數(shù)為：n,yy);for(n=0;nj;+n)printf(%d ,an);printf(nn);p

19、rintf(所以指數(shù)為：);for(n=0;nj;+n)cn=(yy-1)/an;printf(%d ,cn);printf(nn);for(g=2;g+)for(n=0;n32&k1024)printf(取介于25到210之間的一個原根值為：);printf(%dnn,k);return k;return 0;3.2.5 產(chǎn)生隨機(jī)素數(shù)算法描述：使用srand()和rand()函數(shù)產(chǎn)生隨機(jī)數(shù)n，然后通過判斷n%2是否為0來判斷產(chǎn)生的是否是奇數(shù)。具體實現(xiàn)代碼如下：int S_PrimeTable7 = 3, 5, 7, 11, 13, 17, 19 ;/產(chǎn)生一個隨機(jī)數(shù)int Random_Odd

20、()int odd = 0;while (1)srand(time(NULL);odd = rand() % (16385) + 16384;if (odd % 2 != 0)break;/printf(%dn, odd);return odd;4. 測試報告產(chǎn)生奇素數(shù)，用小素數(shù)試除并且輸出試除的余數(shù)，再進(jìn)行Miller-Rabin檢測，若Miller-Rabin檢測沒有通過，則輸出產(chǎn)生下一個隨機(jī)數(shù)的規(guī)則并繼續(xù)產(chǎn)生下一個隨機(jī)數(shù)，直至產(chǎn)生滿足條件的奇素數(shù)，如圖4-1、4-2所示：圖 4-1 產(chǎn)生隨機(jī)數(shù)并用小素數(shù)試除圖 4-2 米勒檢測過程代碼調(diào)試的最終結(jié)果如圖4-3、圖4-4、圖4-5、圖4-6

21、、圖4-7、圖4-8所示：圖4-3 產(chǎn)生隨機(jī)數(shù)并用小素數(shù)試除圖4-4 米勒檢測過程圖4-5 大素數(shù)的歐拉函數(shù)分解質(zhì)因數(shù)圖4-6 求原根并計算各自的密鑰圖4-7 模重復(fù)平方法計算過程圖4-8 計算共同密鑰結(jié) 論本文是在學(xué)習(xí)了相關(guān)C語言知識、密碼學(xué)及相關(guān)信息安全數(shù)學(xué)知識之上進(jìn)行的設(shè)計，本設(shè)計采用C語言實現(xiàn)，實現(xiàn)了DH密鑰協(xié)商算法，用戶A和用戶B通過自己選取的隨機(jī)數(shù)和公開的大素數(shù)通過離散對數(shù)的某些算法求得密鑰，并相互交換密鑰，通過交換得來的密鑰產(chǎn)生共同的密鑰。由于學(xué)生水平有限，在程序可讀性和規(guī)范性上有著一定的欠缺，略顯不足，而在實現(xiàn)功能上也顯得不是很完善，需要在進(jìn)一步的學(xué)習(xí)中得到提升。在編寫程序的過

22、程中遇到了一些不可避免的錯誤和問題，但是都通過書本以及同學(xué)的幫助得以及時將這些問題解決，此次設(shè)計對我的邏輯性理解和編程能力都有一定的提高。參考文獻(xiàn)1 譚浩強(qiáng). C程序設(shè)計M.北京：清華大學(xué)出版，1999.12 2 張仕斌. 應(yīng)用密碼學(xué)M.西安：西安電子科技大學(xué)出版，2009.123 陳恭亮.簡明信息安全數(shù)學(xué)基礎(chǔ)M. 北京：高等教育出版社， 20011.1附源代碼#include#include#include#includeint Random_Odd();int SPrime(int odd);int MoChongFu(int m, int e,int n);int MoChongFua(

23、int m, int e,int n);int milejiance(int odd);int yuangen(int yy);int S_PrimeTable7 = 3, 5, 7, 11, 13, 17, 19 ;int main(void)int yy=0;int gg;int A,B,Key,Key1,Key2;int SA,SB;int i,flag1,flag2;doq:printf(*nnn);while(yy = Random_Odd();yy = Random_Odd();printf(產(chǎn)生的隨機(jī)數(shù)是:%dnn,yy);flag1=!SPrime(yy);for(i=0;i5

24、;i+)flag2=!milejiance(yy);if(flag2)printf(第%d次米勒檢測未通過。nn,i+1);printf(因為第%d次米勒檢測沒有通過，所以隨機(jī)數(shù)%d不是素數(shù)，n產(chǎn)生下一個隨機(jī)數(shù)，先用小素數(shù)試除，再進(jìn)行5次米勒檢測，如果小素數(shù)試除通過并且5次都通過，則說明該隨機(jī)數(shù)是大素數(shù)。,i+1,yy);printf(n);goto q;elseprintf(第%d次米勒檢測通過。nn,i+1);while(flag1|flag2);gg=yuangen(yy);srand(time(NULL);A = rand()%(96)+32;B = rand()%(96)+32;pr

25、intf(Alice選擇的隨機(jī)數(shù)A是：%dn,A);printf(Bob選擇的隨機(jī)數(shù)B是：%dnn,B);printf(計算SA=(ggA) mod yy:n);SA=MoChongFua(gg,A,yy);printf(n);printf(計算SB=(ggB) mod yy:n);SB=MoChongFua(gg,B,yy);printf(所以SA和SB分別是：%d,%dnn,SA,SB);printf(計算Key1=(SBA) mod yy:n);Key1=MoChongFua(SB,A,yy);printf(n);printf(計算Key2=(SAB) mod yy:n);Key2=Mo

26、ChongFua(SA,B,yy);printf(所以：Key1=%d,Key2=%dnn,Key1,Key2);if(Key1=Key2)Key=Key1;printf(所以共同密鑰Key是：%dnn,Key);return 0;/產(chǎn)生一個隨機(jī)數(shù)int Random_Odd()int odd = 0;while (1)srand(time(NULL);odd = rand() % (16384) + 16384;if (odd % 2 != 0)break;/printf(%dn, odd);return odd;/如果是素數(shù)的話返回1int SPrime(int odd)int i, r,

27、 k = 0;for (i = 0; i7; i+)r = odd % S_PrimeTablei;printf(第%d次小素數(shù)%d試除的余數(shù)為%d.n, i + 1, S_PrimeTablei, r);if (r = 0)k+;if(!k)printf(小素數(shù)試除判斷%d是素數(shù)。nn,odd);elseprintf(小素數(shù)試除判斷%d不是素數(shù)。nn,odd);return !k;int MoChongFu(int m, int e,int n) int binary22;int count=0,i;int a=1,b; b=m;do binarycount=e%2;e=e/2;count+;while(e!=0);for(i=0;icount;i+)if(binaryi=1)a=(a*b)%n;b=(b*b)%n;if(binaryi=0)a=a;b=(b*b)%n;return a;int MoChongFua(int m, int e,int n) int binary22;int count=0,i;int a=1,b; b=m;do binary