2015密碼學(xué)課程設(shè)計(jì)報(bào)告 (2)

1、課 程 設(shè) 計(jì) 報(bào) 告題目：SPN和RSA密碼算法的快速實(shí)現(xiàn)與安全性分析課程名稱： 密碼學(xué) 專業(yè)班級(jí)： 信安二班 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師： 報(bào)告日期： 2015.9.20 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院密碼學(xué)課程設(shè)計(jì)任務(wù)書題目：SPN和RSA密碼算法的快速實(shí)現(xiàn)與安全性分析課題內(nèi)容：（1）原始SPN（教材上）算法的實(shí)現(xiàn)。（2）對(duì)上述算法進(jìn)行線性密碼分析及差分密碼分析（求出所有32比特密鑰）。（3）增強(qiáng)以上SPN的安全性（如增加分組的長度、密鑰的長度、S盒、輪數(shù)等）。（4）對(duì)原始及增強(qiáng)的SPN進(jìn)行隨機(jī)性檢測(cè)，對(duì)檢測(cè)結(jié)果進(jìn)行說明。（5）生成RSA算法的參數(shù)（如p、q、N、私鑰、公鑰等）。（6）快速實(shí)現(xiàn)R

2、SA（對(duì)比模重復(fù)平方、蒙哥馬利算法和中國剩余定理）。（7）結(jié)合RSA和增強(qiáng)后的SPN實(shí)現(xiàn)文件（或通信）的加解密。課題任務(wù)要求：（1） 掌握線性、差分分析的基本原理與方法。（2） 體會(huì)位運(yùn)算、預(yù)計(jì)算在算法快速實(shí)現(xiàn)中的作用。（3） 可借助OpenSSL、GMP、BIGINT等大數(shù)運(yùn)算庫的低層基本函數(shù)，實(shí)現(xiàn)過程中必須體現(xiàn)模重復(fù)平方、中國剩余定理和蒙哥馬利算法的過程。（4） 獨(dú)立完成課程設(shè)計(jì)內(nèi)容，現(xiàn)場(chǎng)演示并講解。（5） 課程設(shè)計(jì)完成后一周內(nèi)，提交課程設(shè)計(jì)報(bào)告。主要參考文獻(xiàn)（由指導(dǎo)教師選定）（1） 密碼學(xué)原理與實(shí)踐（第三版）. DouglasR.Stinson著，馮登國譯，電子工業(yè)出版社，2009（2）

3、 應(yīng)用密碼學(xué)：協(xié)議算法與C源程序（第二版）. Bruce Schneier著，吳世忠等譯，機(jī)械工業(yè)出版社，2014同組設(shè)計(jì)者 無47目錄緒論11、實(shí)驗(yàn)?zāi)康?2、實(shí)驗(yàn)內(nèi)容及基本要求22.1 SPN算法22.2 RSA算法22.3 文件的加解密以及隨機(jī)性檢測(cè)23、實(shí)驗(yàn)原理33.1 SPN算法33.2 RSA算法73.3 文件加解密與隨機(jī)性檢測(cè)74、實(shí)驗(yàn)過程84.1 SPN算法84.2 RSA算法204.3 文件加解密與隨機(jī)性檢測(cè)265、結(jié)果分析375.1 SPN算法375.2 RSA算法405.3文件加解密與隨機(jī)性檢測(cè)426、實(shí)驗(yàn)心得和體會(huì)45緒論課題背景和意義當(dāng)前，重視實(shí)驗(yàn)與實(shí)踐教育是各國高等教

4、育界的發(fā)展潮流，實(shí)驗(yàn)與實(shí)踐教學(xué)與理論教學(xué)是相輔相成的，具有同等重要的地位。它是在開放教育的基礎(chǔ)上，為配合理論教學(xué)、培養(yǎng)學(xué)生分析問題和解決問題的能力以及加強(qiáng)訓(xùn)練學(xué)生專業(yè)實(shí)踐能力而設(shè)置的教學(xué)環(huán)節(jié)；對(duì)于完成教學(xué)計(jì)劃、落實(shí)教學(xué)大綱，確保教學(xué)質(zhì)量，培養(yǎng)學(xué)生分析問題、解決問題的能力和實(shí)踐操作技能更具有特別重要的意義。密碼學(xué)是信息安全與保密技術(shù)的核心，是一門實(shí)踐性非常強(qiáng)的課程，實(shí)踐教學(xué)是培養(yǎng)密碼技術(shù)應(yīng)用性人才的重要途徑，實(shí)踐教學(xué)質(zhì)量的好環(huán)，實(shí)際上也決定了應(yīng)用型人才培養(yǎng)質(zhì)量的高低。因此，加強(qiáng)密碼學(xué)課程實(shí)踐教學(xué)環(huán)節(jié)，提高實(shí)踐教學(xué)質(zhì)量，對(duì)培養(yǎng)高質(zhì)量的應(yīng)用型人才至關(guān)重要。密碼學(xué)是研究編制密碼和破譯密碼的技術(shù)科學(xué)。研

5、究密碼變化的客觀規(guī)律，應(yīng)用于編制密碼以保守通信秘密的，稱為編碼學(xué)；應(yīng)用于破譯密碼以獲取通信情報(bào)的，稱為破譯學(xué)?？偡Q密碼學(xué)。課程設(shè)計(jì)的主要研究工作本次課程設(shè)計(jì)是以課堂中所學(xué)的密碼學(xué)的內(nèi)容為基礎(chǔ)，使用Code Blocks、Microsof Visual C+作為開發(fā)工具，使用了GMP大數(shù)庫。系統(tǒng)具有SPN加解密、RSA加解密、文件加解密三個(gè)主要的功能，包括簡單的SPN算法的實(shí)現(xiàn)、線性差分分析，加強(qiáng)SPN算法的實(shí)現(xiàn)，RSA加解密，文件加解密等子模塊。能夠滿足對(duì)任意大小的文件進(jìn)行加解密。文件加解密的設(shè)計(jì)合理，在保證了速度的同時(shí)，也沒有占用太大的內(nèi)存空間。1、 實(shí)驗(yàn)?zāi)康耐ㄟ^課程設(shè)計(jì)，使學(xué)生進(jìn)一步熟悉密

6、碼算法以及算法安全性的基本概念和原理；培養(yǎng)學(xué)生將密碼理論和技術(shù)應(yīng)用于實(shí)際的能力，使學(xué)生具備實(shí)施數(shù)據(jù)加解密和基本的密碼分析的能力。2、 實(shí)驗(yàn)內(nèi)容及基本要求2.1 SPN算法的編程實(shí)現(xiàn)（1）了解書本中對(duì)稱密碼體制的內(nèi)容，熟練掌握并實(shí)現(xiàn)教材中的SPN算法；（2）線性分析：了解線性分析的原理，通過對(duì)明密文對(duì)的線性分析，配合暴力破解，破解出初始加密密鑰；（3）差分分析：了解差分分析的原理，通過對(duì)明密文對(duì)的差分分析，配合暴力破解，破解出初始加密密鑰；（4）通過增加分組長度，秘鑰長度，S盒、輪數(shù)等方式，增強(qiáng)上述SPN算法的安全性。2.2 RSA的參數(shù)生成以及快速實(shí)現(xiàn)（1）生成RSA算法的參數(shù)；（2）通過中國

7、剩余定理，蒙哥馬利算法，模重復(fù)平方算法，快速實(shí)現(xiàn)RSA；（3）通過調(diào)用時(shí)鐘對(duì)三種解密方法的時(shí)間開銷進(jìn)行測(cè)試。2.3 文件的加解密以及隨機(jī)性檢測(cè)（1）結(jié)合RSA和增強(qiáng)后的SPN算法實(shí)現(xiàn)文件的加解密；（2）密文的隨機(jī)性反映了密碼的強(qiáng)度，對(duì)原始的和增強(qiáng)后的SPN算法進(jìn)行隨機(jī)性檢測(cè)，對(duì)檢測(cè)的結(jié)果進(jìn)行說明。3、 實(shí)驗(yàn)原理3.1 SPN算法3.1.1代換置換網(wǎng)絡(luò)（SPN）SPN就是一類特殊的迭代置換密碼，一個(gè)SPN包括兩個(gè)變換，分別記s和p，其中s就是對(duì)一L個(gè)比特的向量，用另一個(gè)L比特的向量來代替它，置換p則用來置換Lm個(gè)比特，打亂一個(gè)長度為Lm比特的向量內(nèi)部各個(gè)比特的順序。將要給出的SPN由Nr輪組成，

8、先用異或操作混入該輪的輪秘鑰，再用s經(jīng)行m次代換，再用p進(jìn)行一次置換，基于s和p，下面給出一個(gè)SPN的具體算法。加密過程使用如下算法描述：w0=xfor r=1 to Nr-1 ur=wr-1kr / 白化 for i=1 to m do vr=s(ur) / 代替wr=(vrp(1),vrp(2),.,vrp(lm) / 置換uNr=wNr-1kNrfor i=1 to m do vNr=s(uNr) / 代替y=vNrkNr+1 / 白化output y其中該SPN的第一個(gè)和最后一個(gè)操作都是異或輪秘鑰，這叫做白化，白話可以使一個(gè)不知道秘鑰的攻擊者無法開始一個(gè)加解密操作。最后具體的過程如下圖

9、3.1所示：圖3.1 SPN加密算法3.1.2線性密碼分析線性密碼分析是一種已知明文攻擊，在一個(gè)明文比特集與最后一輪即將進(jìn)行代換的輸入狀態(tài)比特子集之間找到一個(gè)概率線性關(guān)系，即存在一個(gè)子集使得其中元素的異或表現(xiàn)出非隨機(jī)的分布，使用大量的用同一未知秘鑰K加密的明密文對(duì)，對(duì)每一個(gè)明密文對(duì)，將用所有可能的候選秘鑰來對(duì)最后一輪解密密文，對(duì)每一個(gè)候選秘鑰，計(jì)算包含在線性關(guān)系式中的相關(guān)轉(zhuǎn)態(tài)比特的異或值，然后確定上述線性關(guān)系是否成立，如果成立，就在對(duì)應(yīng)于特定候選秘鑰的計(jì)數(shù)器上加1，在這個(gè)過程的最后，計(jì)數(shù)器離明密文對(duì)數(shù)的一半最遠(yuǎn)的候選秘鑰含有那些秘鑰比特的正確值。在線性分析的過程中不需要對(duì)全部密鑰空間進(jìn)行窮舉，

10、只需要對(duì)隨機(jī)變量有影響的密鑰比特進(jìn)行窮舉，這些密鑰比特稱為候選子密鑰。在計(jì)算出候選子秘鑰的正確值之后，采用窮舉的辦法，暴力破解出秘鑰其余比特的正確值，最終得到完整的秘鑰。線性分析的具體算法如下：線性攻擊(T, T, s-1) ： for (L1,L2)=(0,0) to (F,F) / L1,L2表示候選子密鑰k5和k5do CountL1,L2=0 / 每個(gè)候選子密鑰分配一個(gè)計(jì)數(shù)器并初始化為0for each (x,y) T for (L1,L2)=(0,0) to (F,F) v4 = L1yv4 = L2yu4 = s-1(v4)u4 = s-1(v4)z = x5x7x8u46u48u

11、414u416 / 計(jì)算隨機(jī)變量值if z=0 then CountL1,L2 +;max = -1for (L1,L2)=(0,0) to (F,F) CountL1,L2 = | CountL1,L2 - T/2 |if CountL1,L2 max max = CountL1,L2 maxkey = (L1,L2)Output(maxkey) / maxkey即為所求子密鑰3.1.3差分密碼分析差分密碼分析是一種選擇明文攻擊，我們首先產(chǎn)生大量的四元組（x,x*,y,y*），其中異或值x=xx*是固定的，明文x與x*通過同一個(gè)秘鑰K加密得到y(tǒng)與y*。對(duì)這些四元組中的每一個(gè)，將應(yīng)用所有可能的

12、候選秘鑰來對(duì)改密碼的最后一輪經(jīng)行解密。對(duì)于每一個(gè)候選秘鑰，計(jì)算某些轉(zhuǎn)態(tài)比特的值，并確定他們的異或是否有一個(gè)確定的值，如果是就把對(duì)應(yīng)于特定候選秘鑰的計(jì)數(shù)器加1。在這個(gè)過程的最后，對(duì)應(yīng)計(jì)數(shù)器數(shù)值最大的候選秘鑰就是正真秘鑰特定比特的取值。在差分分析的過程中不需要對(duì)全部密鑰空間進(jìn)行窮舉，只需要對(duì)隨機(jī)變量有影響的密鑰比特進(jìn)行窮舉，這些密鑰比特稱為候選子密鑰。在計(jì)算出候選子秘鑰的正確值之后，采用窮舉的辦法，暴力破解出秘鑰其余比特的正確值，最終得到完整的秘鑰。差分分析的具體算法如下：for (L1,L2)=(0,0) to (F,F) / L1,L2表示候選子密鑰k5和k5do CountL1,L2=0 /

13、 每個(gè)候選子密鑰分配一個(gè)計(jì)數(shù)器并初始化為0for each (x,x*,y,y*) T if (y=y* and y=y*) then / 只考慮y和y=0 for (L1,L2)=(0,0) to (F,F) v4 = L1yv4 = L2yu4 = s-1(v4)u4 = s-1(v4)(v4)*= L1(y)*(v4)* = L2(y)*(u4)* = s-1(v4) *)(u4)* = s-1(v4)*)(u4)=u4(u4)*(u4)=u4(u4)*if (u4)=0110 and (u4) = 0110) then CountL1,L2 +; max = -1for (L1,L2)

14、=(0,0) to (F,F) if CountL1,L2 max then max = CountL1,L2 maxkey = (L1,L2) Output(maxkey) / maxkey即為所求子密鑰3.1.4加強(qiáng)的SPN算法與原有的初始的SPN算法大致相同，通過增加分組長度，秘鑰長度，選擇更復(fù)雜的S盒、增加輪數(shù)等方式，對(duì)上述SPN算法的安全性進(jìn)行增強(qiáng)，在本次設(shè)計(jì)中改進(jìn)后的SPN算法每一次對(duì)64比特的數(shù)據(jù)進(jìn)行處理，采用AES的S盒，每一次對(duì)8比特的數(shù)據(jù)進(jìn)行置換，一次S盒的操作需要8次置換，P盒將64比特中的數(shù)據(jù)進(jìn)行重新排列，每一輪秘鑰的長度也需要64比特，總共加密9輪，需要128比特的初

15、始秘鑰。秘鑰K也是通過一個(gè)長度為128比特的數(shù)組保存的，第一輪使用前64比特，之后每一輪向后移8位，作為新一輪的秘鑰。3.2 RSA算法3.2.1 RSA密碼體制由于在對(duì)稱密碼體制中，加解密使用的是同一個(gè)秘鑰，所以加解密的雙方必須交換秘鑰，這就存在一個(gè)安全交換秘鑰的問題，因此人們就提出了非對(duì)稱的密碼體制，也就是公鑰密碼體制，即接收方生成保密的私鑰和相應(yīng)的公開的公鑰，發(fā)送方用公鑰加密之后將加密的文件發(fā)給接收方，接收方就可以用相應(yīng)的私鑰解密，解決了對(duì)稱密碼體制秘鑰交換的問題，其中RSA算法就是一種十分著名的公鑰密碼算法，RSA算法基于一個(gè)十分簡單的數(shù)論事實(shí)：將兩個(gè)大素?cái)?shù)相乘十分容易，但是想要對(duì)其乘

16、積進(jìn)行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。RSA算法描述如下：（1） 參數(shù)生成選擇兩個(gè)互異的大素?cái)?shù)p和q，n是二者的乘積，即n=pq，使(n)=(p-1)(q-1)為歐拉函數(shù)。隨機(jī)選取正整數(shù)e，使其滿足gcd(e, (n) =1，即e和(n) 互質(zhì)，則將(n,e)作為公鑰。求出正數(shù)d，使其滿足ed=1(mod(n)，則將(n,d)作為私鑰。（2） 加密算法對(duì)于明文M，由C=Me(mod n)，得到密文C。（3） 解密算法對(duì)于密文C，由M=Cd(mod n)，得到明文M。3.2.2 RSA參數(shù)生成在本次課程設(shè)計(jì)中采用的是GMP大數(shù)庫，使用了大數(shù)庫中基于大數(shù)的一些加法，乘法，求逆等

17、基本運(yùn)算。RSA參數(shù)的生成過程如下：（1） 生成兩個(gè)大素?cái)?shù)p，q，p!=q；（2） n=pq,且(n)=(p-1)(q-1)；（3） 隨機(jī)選擇隨機(jī)數(shù)e（1e(n)），使其滿足gcd(e, (n) =1；（4） d=b-1mod(n)；（5） 公鑰為（n,e）, 私鑰為（p,q,a）；3.3 文件加解密與隨機(jī)性檢測(cè)3.3.1 加密體制本次加密算法采用RSA與加強(qiáng)的SPN相結(jié)合的密碼體制，發(fā)送方選擇一個(gè)秘鑰，用其對(duì)文件進(jìn)行加密，再用接收方的公鑰E對(duì)K進(jìn)行加密后，將秘鑰的密文和文件的密文一同發(fā)送給接受方，接收方先用私鑰解密出秘鑰K，再用秘鑰K解密加密的文件。在加強(qiáng)的SPN加密文件時(shí)，采用的是CBC模

18、式。3.3.2 短塊處理由于加強(qiáng)的SPN每一次加密都是對(duì)64比特的數(shù)據(jù)進(jìn)行變換，在文件的加密操作中，文件的大小可能并不是64比特的整數(shù)倍，就需要對(duì)最后一次加密進(jìn)行短塊處理，本次設(shè)計(jì)中所采用的方法是不足64比特的部分先用0填充，在最后一個(gè)字節(jié)即最后8個(gè)比特用需要填充的比特的個(gè)數(shù)轉(zhuǎn)換成2進(jìn)制數(shù)填充。3.3.3 隨機(jī)性檢測(cè)密文的隨機(jī)性反映了密碼的強(qiáng)度，對(duì)原始的和增強(qiáng)后的SPN算法，使用老師所給的檢測(cè)工具進(jìn)行隨機(jī)性檢測(cè)，并對(duì)檢測(cè)的結(jié)果進(jìn)行說明。4、實(shí)驗(yàn)過程4.1 SPN算法4.1.1 代換置換網(wǎng)絡(luò)（SPN）（1）數(shù)據(jù)結(jié)構(gòu)與基本設(shè)計(jì)思想本次實(shí)驗(yàn)中采用兩個(gè)長度為16的整形數(shù)組結(jié)構(gòu)保存相應(yīng)的明文和密文，加密

19、過程的使用的S盒和P盒也是采用兩個(gè)含有16個(gè)整形元素的數(shù)組進(jìn)行保存，便于進(jìn)行相應(yīng)的操作。解密過程與加密過程類似。秘鑰K也是通過一個(gè)長度為32比特的數(shù)組保存的，第一輪使用前16比特，之后每一輪向后移4位，作為新一輪的秘鑰，每一輪對(duì)秘鑰進(jìn)行異或操作時(shí)，只需要相應(yīng)的指針向后移動(dòng)便可。加密過程可以參考實(shí)驗(yàn)原理中已經(jīng)給出的算法，實(shí)現(xiàn)比較簡單，解密過程則是對(duì)加密過程的逆操作，使用的S盒的逆與P盒的逆通過預(yù)計(jì)算用長度為16的整形數(shù)組保存。（2）S盒操作首先取出需要轉(zhuǎn)換的原文的4比特，轉(zhuǎn)化成對(duì)應(yīng)的10進(jìn)制數(shù)之后通過S盒進(jìn)行置換，再轉(zhuǎn)換成相應(yīng)的二進(jìn)制數(shù)保存在原數(shù)組中。具體代碼如下：void Sboxop(int

20、 *plain) int i,m=0; for(i=3;i=N;i=i+4) int temp=0; for(m=i-3;m=i-3;m-) plainm = temp % 2; temp = temp / 2; （3）p盒操作首先設(shè)立一個(gè)16個(gè)整形元素的緩存區(qū)數(shù)組，將待轉(zhuǎn)化的數(shù)組復(fù)制保存在緩存區(qū)中，再通過P盒進(jìn)行置換，將置換之后的寫回原數(shù)組中。具體代碼如下：void Pboxop(int *plain) int i; int tempN; for (i = 0; i N; i+) tempi = plaini; for(i = 0; i N; i+) plain(pboxi-1) = tem

21、pi;（4）加解密算法的實(shí)現(xiàn)與課本上所給的算法相同，解密算法就是一個(gè)逆過程，總的來說比較簡單。void Encrypt(int* plain,int*cipher) int nr=5,i,j; for (i = 0; i N; i+) cipheri = plaini; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(cipher); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sboxop(cipher); Xor(cipher,key + 4*i); for(j=0;jN;j+) prin

22、tf(%d,cipherj); printf(n);void Decrypt(int *cipher,int* plain) int i,nr=5,j; for (i = 0; i =0; i-) Pboxnop(plain); Sboxnop(plain); Xor(plain,key + 4*i); for(j=0;jN;j+) printf(%d,plainj); printf(n);4.1.2 線性密碼分析（1）明密文對(duì)的生成調(diào)用簡單的SPN算法，產(chǎn)生8000對(duì)明密文對(duì)，寫入文件中保存，具體代碼如下：int main(void)int plainN,i,cipherN,nr=5,j;

23、FILE *fin; fin=fopen(E:pairs.txt,w);for(j=0;j8000;j+) for(i = 0; i 16; i+) plaini = rand() % 2; for(i=0;iN;i+) fprintf(fin,%d ,plaini); fprintf(fin,n); for (i = 0; i N; i+) cipheri = plaini; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(cipher); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sbo

24、xop(cipher); Xor(cipher,key + 4*i); for(i=0;iN;i+) fprintf(fin,%d ,cipheri); fprintf(fin,n); fclose(fin);（2）候選子秘鑰的計(jì)算線性密碼分析在一開始猜測(cè)部分比特的與課本上描述的算法完全相同，首先從文件中讀取出已經(jīng)生成的明密文對(duì)，8000對(duì)，保存在兩個(gè)數(shù)組中，進(jìn)行線性分析，分析出來的正確的候選秘鑰通過change函數(shù)，放入最終猜測(cè)的32比特的秘鑰中正確的位置，具體代碼實(shí)現(xiàn)如下：int Count256,xM16,yM16,j,L12564,L22564,v24,v44,i,z,maxkey,k

25、32; FILE *fin; fin=fopen(E:pairs.txt,r); for(i=0;iM;i+) for(j=0;jN;j+) fscanf(fin,%d,&xij); for(j=0;jN;j+) fscanf(fin,%d,&yij); fclose(fin); for(j=0;j=0;i-) L2ji=k%2; k=k/2; for(i=3;i=0;i-) L1ji=k%2; k=k/2; for(i=0;i256;i+) Counti=0; for(i=0;i8000;i+) for(j=0;j256;j+) Xorl(L1j,yi+4,v2); Xorl(L2j,yi+

26、12,v4); Sboxnop(v2); Sboxnop(v4); z=(xi4+xi6+xi7+v21+v23+v41+v43)%2; if (z=0) Countj=Countj+1; int Max=-1; for(i=0;iMax) Max=Counti; maxkey=i; change(k,maxkey,31,28);maxkey=maxkey/16;change(k,maxkey,23,20);（3）窮舉法猜測(cè)完整秘鑰對(duì)于剩下的24位沒有猜測(cè)出來的秘鑰，通過窮舉法，對(duì)于每一個(gè)可能的秘鑰，依次用其去加密10個(gè)明文，并與已知的正確的密文比較，若是全部通過，則便是正確的秘鑰。其中cha

27、nge函數(shù)也是在最終猜測(cè)的秘鑰中選擇正確的位置，放入猜測(cè)具體數(shù)值，spn函數(shù)就是spn算法，具體代碼的實(shí)現(xiàn)如下：int i1,i2,i3,i4,i5,i6,i7,i8,i9,cipherN;for(i1=0;i116;i1+) change(k,i1,3,0);for(i2=0;i216;i2+) change(k,i2,7,4);for(i3=0;i316;i3+) change(k,i3,11,8);for(i4=0;i416;i4+) change(k,i4,15,12);for(i5=0;i516;i5+) change(k,i5,19,16);for(i6=0;i616;i6+) c

28、hange(k,i6,27,24); i9=0; for(i8=0;i810;i8+) spn(xi8,cipher,k); for(i=0;iN;i+) if(cipheri!=yi8i) i9=1; break; if(i9=1) break; if(i9=0) for(i7=0;i732;i7+) printf(%d,ki7); if(i7+1)%4)=0) printf( ); printf(n); system(pause); return 1; 4.1.3 差分密碼分析（1）明密文對(duì)的生成調(diào)用簡單的SPN算法，產(chǎn)生500對(duì)明密文對(duì)，寫入文件中保存，具體代碼如下：int main(v

29、oid)int plainN,i,cipherN,nr=5,j,xN; FILE *fin; fin=fopen(E:pairscf.txt,w);for(j=0;j500;j+) for(i = 0; i 16; i+) plaini = rand() % 2; Xorl(plain,xl,x); for(i=0;iN;i+) fprintf(fin,%d ,plaini); fprintf(fin,n); for (i = 0; i N; i+) cipheri = plaini; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(

30、cipher); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sboxop(cipher); Xor(cipher,key + 4*i); for(i=0;iN;i+) fprintf(fin,%d ,cipheri); fprintf(fin,n); /對(duì)X進(jìn)行處理 for(i=0;iN;i+) fprintf(fin,%d ,xi); fprintf(fin,n); for (i = 0; i N; i+) cipheri = xi; for (i = 0; i nr-2; i+) Xor(cipher,key + 4*i); Sboxop(cip

31、her); Pboxop(cipher); Xor(cipher,key + 4*i); i+; Sboxop(cipher); Xor(cipher,key + 4*i); for(i=0;iN;i+) fprintf(fin,%d ,cipheri); fprintf(fin,n); fprintf(fin,n); fclose(fin);（2）候選子秘鑰的計(jì)算差分密碼分析在一開始猜測(cè)部分比特的與課本上描述的算法完全相同，首先從文件中讀取出已經(jīng)生成的明密文對(duì)，500對(duì)，保存在兩個(gè)數(shù)組中，進(jìn)行差分分析，分析出來的正確的候選秘鑰通過change函數(shù)，放入最終猜測(cè)的32比特的秘鑰中正確的位置，具

32、體代碼實(shí)現(xiàn)如下：int Count256,x1M16,x2M16,y1M16,y2M16,j,L12564,L22564,v24,v44,i,maxkey,vl24,vl44,u24,u44,Max,k32; FILE *fin; fin=fopen(E:pairscf.txt,r); for(i=0;iM;i+) for(j=0;jN;j+) fscanf(fin,%d,&x1ij); for(j=0;jN;j+) fscanf(fin,%d,&y1ij); for(j=0;jN;j+) fscanf(fin,%d,&x2ij); for(j=0;jN;j+) fscanf(fin,%d,&

33、y2ij); fclose(fin); for(j=0;j=0;i-) L2ji=k%2; k=k/2; for(i=3;i=0;i-) L1ji=k%2; k=k/2; for(i=0;i256;i+) Counti=0; for(i=0;iM;i+) if(y1i0=y2i0&y1i1=y2i1&y1i2=y2i2&y1i3=y2i3&y1i8=y2i8&y1i9=y2i9&y1i10=y2i10&y1i11=y2i11) for(j=0;j256;j+) Xorl(L1j,y1i+4,v2); Xorl(L2j,y1i+12,v4); Sboxnop(v2); Sboxnop(v4);

34、Xorl(L1j,y2i+4,vl2); Xorl(L2j,y2i+12,vl4); Sboxnop(vl2); Sboxnop(vl4); Xorl(v2,vl2,u2); Xorl(v4,vl4,u4); if(u20=0&u21=1&u22=1&u23=0&u40=0&u41=1&u42=1&u43=0) Countj+; Max=-1; for(i=0;iMax) Max=Counti; maxkey=i; change(k,maxkey,31,28);maxkey=maxkey/16;change(k,maxkey,23,20);（2）窮舉法猜測(cè)完整秘鑰這部分的內(nèi)容與線性分析中相應(yīng)內(nèi)

35、容完全一樣，最終得到32比特的正確秘鑰。4.1.4加強(qiáng)的SPN算法（1）數(shù)據(jù)結(jié)構(gòu)與基本設(shè)計(jì)思想本次實(shí)驗(yàn)中采用兩個(gè)長度為64的整形數(shù)組結(jié)構(gòu)保存相應(yīng)的明文和密文，加密過程的使用的S盒和P盒也是采用兩個(gè)分別含有256和64個(gè)整形元素的數(shù)組進(jìn)行保存，便于進(jìn)行相應(yīng)的操作。解密過程與加密過程類似。秘鑰K也是通過一個(gè)長度為128比特的數(shù)組保存的，第一輪使用前64比特，之后每一輪向后移8位，作為新一輪的秘鑰，每一輪對(duì)秘鑰進(jìn)行異或操作時(shí)，只需要相應(yīng)的指針向后移動(dòng)便可。加密過程可以參考實(shí)驗(yàn)原理中已經(jīng)給出的算法，實(shí)現(xiàn)比較簡單，解密過程則是對(duì)加密過程的逆操作，使用的S盒的逆與P盒的逆通過預(yù)計(jì)算保存在相應(yīng)的數(shù)組中。（2

36、）S盒與P盒操作與未加強(qiáng)前的操作基本一致，每一次分別對(duì)64比特的數(shù)據(jù)進(jìn)行相應(yīng)的操作。（3）加解密算法的實(shí)現(xiàn)具體算法如下所示：void Encrypt1(int* plain1,int*cipher1) int nr=10,i,j; for (i = 0; i N1; i+) cipher1i = plain1i; for(j=0;jN1;j+) printf(%d,cipher1j); if(j+1)%4=0) printf( ); printf(n); for (i = 0; i nr-2; i+) Xor1(cipher1,key1 + 8*i); Sboxop1(cipher1); Pb

37、oxop1(cipher1); Xor1(cipher1,key1 + 8*i); i+; Sboxop1(cipher1); Xor1(cipher1,key1 + 8*i); for(j=0;jN1;j+) printf(%d,cipher1j); if(j+1)%4=0) printf( ); printf(n);void Decrypt1(int *cipher1,int* plain1) int i,nr=10,j; for(j=0;jN1;j+) printf(%d,cipher1j); if(j+1)%4=0) printf( ); printf(n); for (i = 0;

38、i =0; i-) Pboxop1(plain1); Sboxnop1(plain1); Xor1(plain1,key1 + 8*i) for(j=0;jN1;j+) printf(%d,plain1j); if(j+1)%4=0) printf( );4.2 RSA算法4.2.1 RSA的參數(shù)生成算法（1）生成大素?cái)?shù)算法本次實(shí)驗(yàn)采用的是GMP的大數(shù)庫，在生成大素?cái)?shù)這個(gè)環(huán)節(jié)中，調(diào)用了兩個(gè)庫函數(shù)，一個(gè)是mpz_nextprime (mpz_t rop, mpz_t op)用來置 rop 為比 op 大的下一個(gè)素?cái)?shù)，再用mpz_probab_prime_p函數(shù)進(jìn)行判定，這個(gè)函數(shù)首先做一些試除，然

39、后再作 Miller-Rabin 概率素性判別。進(jìn)行20輪的判定，如果是合數(shù)，放棄這個(gè)數(shù)，在生成一個(gè)可能的大素?cái)?shù)進(jìn)行判定。具體的算法如下所示：void CreateBigPrime(mpz_t mpzPrime,int bits)int i,last_rand=0;char *char_rand = new char bits+1;char_rand0 = 1;char_randbits = 0;mpz_init(mpzPrime);dofor(i=1;ibits;i+)if(rand()=last_rand) printf(ERROR);last_rand = rand();char_ran

40、di = 0+(0x01&last_rand);mpz_set_str(mpzPrime,char_rand,2);mpz_nextprime(mpzPrime,mpzPrime);while(0=mpz_probab_prime_p(mpzPrime,PRIME_PROBABILITY);return;（2）RSA具體參數(shù)的生成這個(gè)過程也比較簡單，通過生成素?cái)?shù)算法生成512比特的素?cái)?shù)p,q。求得他們的乘積n，通過p-1和q-1求出Fn，之后設(shè)置e為65537,通過gmp庫中提供的求逆函數(shù)mpz_inver，得到d，所有參數(shù)生成完畢，具體算法如下圖所示。void RSA(mpz_t p,mpz

41、_t q,mpz_t n,mpz_t fn,mpz_t e,mpz_t d)unsigned long rp=0,rq=0,e1=65537;mpz_t p0,q0; mpz_init(p0);mpz_init(q0); CreateBigPrime(p,512);srand( (unsigned)time( NULL ) ); CreateBigPrime(q,512);mpz_mul(n,p,q);/求出p、q 和n gmp_printf(素?cái)?shù)p: %Zdn,p); gmp_printf(素?cái)?shù)q: %Zdn,q);mpz_set_ui (e, e1) ; gmp_printf(e: %Zd

42、n,e); mpz_sub_ui(p0,p,1);mpz_sub_ui(q0,q,1);mpz_mul(fn,p0,q0); gmp_printf(fn: %Zdn,fn); mpz_invert(d,e,fn); gmp_printf(d: %Zdn,d); mpz_clear(p0);mpz_clear(q0);4.2.2 模重復(fù)平方算法模重復(fù)平方的思想是將指數(shù)n寫成二進(jìn)制形式n=n0+n1*2+nk-1*2k-1，令a=1（1）若n0=1，則計(jì)算a0=a*b(mod m),否則取a0=a，即計(jì)算a0=a*bn0(mod m)，再計(jì)算b1=b2(mod m).（2）若n1=1，則計(jì)算a1=a0*b1(mod m)