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

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

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

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

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

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

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

7、-2)，并計(jì)算SB=(aRB) mod p，并且把SB發(fā)送給用戶A。 3）A計(jì)算密鑰的方式是：K=(SB) RA modp，B計(jì)算密鑰的方式是：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可以利用，只有通過(guò)取離散對(duì)數(shù)來(lái)確定密鑰，但對(duì)于大的素?cái)?shù)p，計(jì)算離散對(duì)數(shù)是十分困難的。4. 例子：假如用戶Alice和用戶Bo

8、b希望交換一個(gè)密鑰，取一個(gè)素?cái)?shù)p=97和97的一個(gè)原根a=5，Alice和Bob分別選擇秘密密鑰RA=36和RB=58，并計(jì)算各自的公開(kāi)密鑰： SA=aRA modp=536 mod 97=50 SB=aRB modp=558 mod 97=44Alice和Bob交換了公開(kāi)密鑰之后，計(jì)算共享密鑰如下： 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)然，為了使這個(gè)例子變得安全，必須使用非常大的RA,RB 以及p， 否則可以實(shí)驗(yàn)所有的可能取值。(總共有最多97個(gè)這樣的值, 就算RA和RB很大也無(wú)濟(jì)于事)。 如果p是一個(gè)至少 300 位的質(zhì)數(shù)，并且RA和RB至少有100位長(zhǎng)， 那么即使使用全人類所有的計(jì)算資源和當(dāng)今最好的算法也不可能從a,p和a(RA*RB) modp中計(jì)算出 RA*RB。 這個(gè)問(wèn)題就是著名的離散對(duì)數(shù)問(wèn)題。注意g則不需要很大, 并且在一般的實(shí)踐中通常是2或者5。在最初的描述中，迪菲赫爾曼密鑰交換本身并沒(méi)有提供通訊雙方的身份驗(yàn)證服務(wù)，因此它很容易受到中間人攻擊。 一個(gè)中間人

10、在信道的中央進(jìn)行兩次迪菲赫爾曼密鑰交換，一次和Alice另一次和Bob，就能夠成功的向Alice假裝自己是Bob，反之亦然。而攻擊者可以解密（讀取和存儲(chǔ)）任何一個(gè)人的信息并重新加密信息，然后傳遞給另一個(gè)人。因此通常都需要一個(gè)能夠驗(yàn)證通訊雙方身份的機(jī)制來(lái)防止這類攻擊。 有很多種安全身份驗(yàn)證解決方案使用到了迪菲赫爾曼密鑰交換。例如當(dāng)Alice和Bob共有一個(gè)公鑰基礎(chǔ)設(shè)施時(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é)商算法的實(shí)現(xiàn)3.1 設(shè)計(jì)要求3.1.1 功能要求（1）產(chǎn)生一個(gè)奇數(shù)p ，判斷是否是素?cái)?shù)。素?cái)?shù)要求介于214-215。先用小于20的素?cái)?shù)去試除，再使用Miller-Rabin概率檢測(cè)算法進(jìn)行檢測(cè)；（2）求得模p 的一個(gè)原根，要求原根的值介于32-1024之間；（3）輸出雙方選擇的隨機(jī)數(shù)，隨機(jī)數(shù)介于25-27，使用模重復(fù)平方法進(jìn)行計(jì)算，輸出雙方的計(jì)算結(jié)果；（4）網(wǎng)絡(luò)傳輸方面，可以是C/S模式，也可以是B/S模式；（5）輸出最后協(xié)商的密鑰； 3.1.2 輸出要求（1）輸出奇數(shù)的產(chǎn)生過(guò)程，用函數(shù)實(shí)現(xiàn)產(chǎn)生滿足要求的奇數(shù)；（2

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

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

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

15、b(b*b)mod n。最后a即為最終計(jì)算結(jié)果。具體實(shí)現(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檢測(cè)算法算法描述：米勒檢測(cè)在本次設(shè)計(jì)中主要用來(lái)檢測(cè)在小素?cái)?shù)判定了之后的隨機(jī)數(shù)是否是素?cái)?shù)。實(shí)現(xiàn)方式：將待檢測(cè)的數(shù)n寫成n-1=2s*t，選取隨機(jī)數(shù)a，計(jì)算batmod n。若b mod n1，則n是素?cái)?shù)。否則，做如下循環(huán)，循環(huán)次數(shù)為1s：如果b mod n-1，則b是素?cái)?shù)，否則，bb*b mod n。具體實(shí)現(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è)原根的充要條件是 g(a/qi)!=1(mod m),i=1,2，k 實(shí)現(xiàn)方式： 先求大素?cái)?shù)的歐拉函數(shù)的素因數(shù)an，并通過(guò)素因數(shù)求得g的指數(shù)cn，接著驗(yàn)證gcn 是否同余于1，對(duì)g=2,3，逐個(gè)驗(yàn)算，直到算出最小的g值滿足gcn均不

18、同余于1，那么g便是大素?cái)?shù)m的最小原根，因?yàn)楫?dāng)cn遍歷歐拉函數(shù)a的簡(jiǎn)化剩余系時(shí)，gcn遍歷模m的所有原根，所以可以通過(guò)歐拉函數(shù)的簡(jiǎn)化剩余系求得滿足要求的原根。具體實(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之間的一個(gè)原根值為：);printf(%dnn,k);return k;return 0;3.2.5 產(chǎn)生隨機(jī)素?cái)?shù)算法描述：使用srand()和rand()函數(shù)產(chǎn)生隨機(jī)數(shù)n，然后通過(guò)判斷n%2是否為0來(lái)判斷產(chǎn)生的是否是奇數(shù)。具體實(shí)現(xiàn)代碼如下：int S_PrimeTable7 = 3, 5, 7, 11, 13, 17, 19 ;/產(chǎn)生一個(gè)隨機(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. 測(cè)試報(bào)告產(chǎn)生奇素?cái)?shù)，用小素?cái)?shù)試除并且輸出試除的余數(shù)，再進(jìn)行Miller-Rabin檢測(cè)，若Miller-Rabin檢測(cè)沒(méi)有通過(guò)，則輸出產(chǎn)生下一個(gè)隨機(jī)數(shù)的規(guī)則并繼續(xù)產(chǎn)生下一個(gè)隨機(jī)數(shù)，直至產(chǎn)生滿足條件的奇素?cái)?shù)，如圖4-1、4-2所示：圖 4-1 產(chǎn)生隨機(jī)數(shù)并用小素?cái)?shù)試除圖 4-2 米勒檢測(cè)過(guò)程代碼調(diào)試的最終結(jié)果如圖4-3、圖4-4、圖4-5、圖4-6

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

22、程中遇到了一些不可避免的錯(cuò)誤和問(wèn)題，但是都通過(guò)書本以及同學(xué)的幫助得以及時(shí)將這些問(wèn)題解決，此次設(shè)計(jì)對(duì)我的邏輯性理解和編程能力都有一定的提高。參考文獻(xiàn)1 譚浩強(qiáng). C程序設(shè)計(jì)M.北京：清華大學(xué)出版，1999.12 2 張仕斌. 應(yīng)用密碼學(xué)M.西安：西安電子科技大學(xué)出版，2009.123 陳恭亮.簡(jiǎn)明信息安全數(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次米勒檢測(cè)未通過(guò)。nn,i+1);printf(因?yàn)榈?d次米勒檢測(cè)沒(méi)有通過(guò)，所以隨機(jī)數(shù)%d不是素?cái)?shù)，n產(chǎn)生下一個(gè)隨機(jī)數(shù)，先用小素?cái)?shù)試除，再進(jìn)行5次米勒檢測(cè)，如果小素?cái)?shù)試除通過(guò)并且5次都通過(guò)，則說(shuō)明該隨機(jī)數(shù)是大素?cái)?shù)。,i+1,yy);printf(n);goto q;elseprintf(第%d次米勒檢測(cè)通過(guò)。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(計(jì)算SA=(ggA) mod yy:n);SA=MoChongFua(gg,A,yy);printf(n);printf(計(jì)算SB=(ggB) mod yy:n);SB=MoChongFua(gg,B,yy);printf(所以SA和SB分別是：%d,%dnn,SA,SB);printf(計(jì)算Key1=(SBA) mod yy:n);Key1=MoChongFua(SB,A,yy);printf(n);printf(計(jì)算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)生一個(gè)隨機(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;/如果是素?cái)?shù)的話返回1int SPrime(int odd)int i, r,

27、 k = 0;for (i = 0; i7; i+)r = odd % S_PrimeTablei;printf(第%d次小素?cái)?shù)%d試除的余數(shù)為%d.n, i + 1, S_PrimeTablei, r);if (r = 0)k+;if(!k)printf(小素?cái)?shù)試除判斷%d是素?cái)?shù)。nn,odd);elseprintf(小素?cái)?shù)試除判斷%d不是素?cái)?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