《2015密码学课程设计报告 (6).doc》由会员分享，可在线阅读，更多相关《2015密码学课程设计报告 (6).doc（42页珍藏版）》请在三一文库上搜索。
1、课 程 设 计 报 告课程名称： 密码学课程设计 专业班级： 信息安全201302班 学 号： 姓 名： 指导教师： 报告日期： 2015年9月29日 计算机科学与技术学院目录2一任务书3二课题任务要求3三实验原理3四实验过程8五实验结果35六 体会40一任务书（1）原始SPN（教材上）算法的实现。（2）对上述算法进行线性密码分析及差分密码分析（求出所有32比特密钥）。（3）增强以上SPN的安全性（如增加分组的长度、密钥的长度、S盒、轮数等）。（4）对原始及增强的SPN进行随机性检测，对检测结果进行说明。（5）生成RSA算法的参数（如p、q、N、私钥、公钥等）。（6）快速实现RSA（对比模重复
2、平方、蒙哥马利算法和中国剩余定理）。（7）结合RSA和增强后的SPN实现文件（或通信）的加解密。二课题任务要求（1） 掌握线性、差分分析的基本原理与方法。（2） 体会位运算、预计算在算法快速实现中的作用。（3） 可借助OpenSSL、GMP、BIGINT等大数运算库的低层基本函数，实现过程中必须体现模重复平方、中国剩余定理和蒙哥马利算法的过程。（4） 独立完成课程设计内容，现场演示并讲解。（5） 课程设计完成后一周内，提交课程设计报告。三实验原理3.1分组密码SPN（1）迭代密码：迭代密码的核心是一个密钥编排方案和一个轮函数密钥编排方案对密钥k进行变换，生成Nr个子密钥(也叫轮密钥)，记为k1
3、,k2,.,kNr轮函数g是一个状态加密函数，以ki为密钥对当前状态wr-1进行变换，输出新的状态值wr，即g(wr-1,ki)=wr；轮函数是单射函数，存在一个逆变换g-1，有g-1(wr,ki)=wr-1将密钥k编排成Nr个轮密钥k1,k2,.,kNr加密：将明文x定义为初始状态w0，经过Nr轮变换得到wNr为密文y，即w0=x, w1=g(w0,k1), w2=g(w1,k2), .wNr-1=g(wNr-2,kNr-1), wNr=g(wNr-1,kNr)y=wNr解密：将密文y定义为初始状态wNr，经过Nr轮逆变换得到w0为明文x，即y=wNr, wNr-1=g-1(wNr,kNr)
4、，wNr-2=g-1(wNr-1,kNr-1).w1=g-1(w2,k2), w0=g-1(w1,k1),x=w0 （2）代换-置换网络：代替-置换网络是一种简单的迭代密码，处理的明文单元和状态值长度为lm。轮函数g包括两个核心变换代替和置换，分别记为s和p，有s : 0,1l 0,1lp : 1,2,.,lm 1,2,.,lm 在进行轮函数变换前，先用轮密钥和状态值进行异或(称为白化)（3） SPN密码体制：设l,m,Nr是正整数,P=C=0,1lmK(0,1lm)Nr+1是由初始密钥k用密钥编排算法生成的所有可能的密钥编排方案集合，一个密钥编排方案记为(k1,k2,.,kNr+1)状态值w
5、长度为lm，记为w1,w2,.,wlm；w可以看成m个长度为l的子串连接而成，记为w=w,w,.,w，其中w=w(i-1)l+1,w(i-1)l+2,.,w(i-1)l+l（4） SPN加密算法：SPN(x,s,p,(k1,k2,.,kNr+1)w0=xfor r=1 to Nr-1 ur=wr-1kr / 白化 for i=1 to m vr=s(ur) / 代替 wr=(vrp(1),vrp(2),.,vrp(lm) / 置换uNr=wNr-1kNrfor i=1 to m vNr=s(uNr) / 代替y=vNrkNr+1 / 白化 最后一轮不做置换return y（5） SPN解密算法
6、解密算法为加密算法的逆过程，故不再赘述。2. 线性密码分析（1）线性密码分析：是通过分析S盒的线性特性，从而发现明文比特、密文比特和密钥比特之间可能存在的线性关系，如果S盒设计不当，这种线性关系会以较大的概率存在，称为概率线性关系。是一种已知明文攻击方法，已知x和y，确定k或k的部分比特。（2）线性密码分析思路：是找到足够多的明文-密文对，对可能的密钥进行穷举，计算相关随机变量的偏差，正确的密钥作用下，偏差的绝对值最大，不需要对全部密钥空间进行穷举，只需要对随机变量有影响的密钥比特进行穷举，这些密钥比特称为候选子密钥。对随机变量有影响的密钥比特：置换置换K5u4v4u46u48u414u416
7、yyyk5yk5y只需要穷举密钥中的8位即可，即穷举28=256个密钥y和k5异或，可得到v4，再通过逆置换可得到u4，最终得到u46和u48。同样的方法可以得到u414和u416（3） 线性密码分析算法：线性攻击(T, T, s-1)for (L1,L2)=(0,0) to (F,F) / L1,L2表示候选子密钥k5和k5 CountL1,L2=0 / 每个候选子密钥分配一个计数器并初始化为0for each (x,y) T for (L1,L2)=(0,0) to (F,F) v4 = L1yv4 = L2yu4 = s-1(v4)u4 = s-1(v4)z = x5x7x8u46u48
8、u414u416 / 计算随机变量值if z=0 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)/ maxkey即为所求子密钥Maxkey中的L1是第6组密钥，L2是第8组密钥，因为暴力破解时要破解出8组密钥，所以总共要用六层循环，在循环内部用两组明密文验证密钥是否正确，得出正确结果。3. 差分密码分析（1）差分密码分析：通过分析明文对的差值对密文对差值的影响来恢复某些密钥比特
9、的分析方法。分析两个输入的异或和两个输出的异或之间的线性关系。构造若干个明文串对，每对明文的异或结果相同，观察相应的密文异或结果。是一种选择明文攻击方法，比线性分析更早提出，分析效果略差于线性分析。（2）差分密码分析思路：找到足够多的四元组(x,x*,y,y*)，其中x=xx*固定不变。对可能的密钥进行穷举，计算相关差分的扩散率，正确的密钥作用下，扩散率应最大，和线性分析一样，不需要对全部密钥空间进行穷举，只需要对候选子密钥进行穷举即可。（3）差分密码分析算法：差分攻击(T, T, s-1)for (L1,L2)=(0,0) to (F,F) / L1,L2表示候选子密钥k5和k5 Count
10、L1,L2=0 / 每个候选子密钥分配一个计数器并初始化为0for each (x,x*,y,y*) T if (y=y* and y=y*) / 只考虑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 CountL1,L2 +; max = -1for (L1,L2)=(
11、0,0) to (F,F) if CountL1,L2 max max = CountL1,L2 maxkey = (L1,L2) / maxkey即为所求子密钥Maxkey中的L1是第6组密钥，L2是第8组密钥，因为暴力破解时要破解出8组密钥，所以总共要用六层循环，在循环内部用两组明密文验证密钥是否正确，得出正确结果。4. SPN加强版SPN加强版改进的时候从分组长度，密钥长度，S盒和轮数四个方面着手。我将输入设置为了64比特，密钥设为了128比特，用了8组S盒，每一轮用不同的S盒加密，一共进行8轮加密。解密是加密的逆过程，每一轮用S盒的逆置换解密，其他的与SPN普通版相同。5. RSA的加
12、解密（1） RSA算法描述生成密钥选取两个大素数p和q，计算n=pq。随机选取加密密钥e，使e和(p-1)(q-1)互素。计算解密密钥d，使ed1 mod(p-1)(q-1)，即ed=k(p-1)(q-1)1。e和n是公开密钥，放在一个公共目录供大家访问，d是私人密钥，p和q不再需要，密钥生成后可抹去，但决不能泄漏。数据加密加密m时，首先将它分成比n小的数据分组，对每个分组min加密，得到密文ci：ci=mie mod n数据解密解密时，对每个密文分组ci计算：micid mod nmied mod nmik(p-1)(q-1)+1 mod nmi*mik(p-1)(q-1) mod nmi（
13、2） 模重复平方法算法平方-乘算法 Square-Multiply(a, b, n)z=1for i=l-1 downto 0 z = z2 mod n if bi=1 z = (za) mod n return z（3） 中国剩余定理原理将中国剩余定理公式带入rsa计算即可（4） 蒙哥马利原理蒙哥马利乘算法蒙哥马利算法四实验过程4.1 SPN普通版加密SPN加解密函数明密文都是16位的，密钥是32位。采用ECB加密模式。ECB模式特点：将消息分为等长的分组，对每一个分组：加密：Ci = EK(Pi)解密：Pi = DK(Ci) ，分组之间无任何联系，简单有效，可以并行处理，不存在误差传递问题
14、。ECB的工作模式：短块分组：需要短块处理的处理方式为：缺几位补几，例如每组有8个比特的时候，缺5位，则补5个5；不需要短块处理的处理方式为：补组数大小个组数大小，例如每组有8个比特的时候，不需要短块处理，则补8个8；具体实现如下：加密部分：在主函数中进行分组以及短块处理fpin=fopen(SPN1.txt,rb);/打开文件 if(fpin=NULL) printf(打开文件失败); else printf(打开文件成功n); fseek(fpin,0,SEEK_END); len=ftell(fpin);/计算文件长度 fseek(fpin,0,SEEK_SET); blocks=(le
15、n/2)+1;/计算分组数 pad=blocks*2-len;/计算短块字节数 block_out=(char *)calloc(2*blocks,sizeof(char); for(i=0;iblocks-1;i+)/非短块的分组 fread(block_in,sizeof(char),2,fpin); for(j=0;j-1;k-) in_sixteenj*8+k=(unsigned char)block_inj%2; block_inj=(unsigned char)block_inj/2; SPN_Start(in_sixteen,out_sixteen);/调用SPN普通版加密函数
16、for(j=0;j2;j+) block_outi*2+j=0; for(k=0;k8;k+) block_outi*2+j*=2; block_outi*2+j=block_outi*2+j+out_sixteenj*8+k; for(i=0;i2;i+)/需要填充短块的最后一组 if(i-1;j-) in_sixteeni*8+j=(unsigned char)block_ini%2; block_ini=(unsigned char)block_ini/2; else rand2=pad; for(j=7;j-1;j-) in_sixteeni*8+j=rand2%2; rand2/=2
17、; SPN_Start(in_sixteen,out_sixteen); for(i=0;i2;i+) block_out(blocks-1)*2+i=0; for(j=0;j8;j+) block_outblocks*2-2+i*=2; block_outblocks*2-2+i=block_outblocks*2-2+i+out_sixteeni*8+j; fclose(fpin); fpout=fopen(SPN2.txt,wb); fwrite(block_out,sizeof(char),blocks*2,fpout);/写入SPN2.txt fclose(fpout);在子函数中进
18、行SPN 普通版加密void SPN_Start(int *MesIn,int *MesOut)/SPN普通版加密 int i,j; static int Mid16=0; static int Mid116=0; Copy(Mid,MesIn,16);/将要加密的16位明文拷贝到Mid中 SPN_K();/对密钥进行分组 for(i=0;i4;i+) SPN_XOR(Mid,Keyi,16);/异或函数 BitToTen(Mid1,Mid,16);/二进制转十进制函数 for(j=0;j4;j+) Midj=S_BoxMid1j;/调用S盒 TenToBit(Mid1,Mid,16);/十进
19、制转二进制 if(i3) SPN_Trans(Mid,Mid1,16,P_Box);/置换 else continue; SPN_XOR(Mid1,Keyi,16);/异或 Copy(MesOut,Mid1,16);解密部分： fpin=fopen(SPN2.txt,rb);/打开密文文件夹 if(fpin=NULL) printf(打开文件失败); else printf(打开文件成功n); fseek(fpin,0,SEEK_END); len=ftell(fpin); fseek(fpin,0,SEEK_SET); blocks=(len/2);/计算分组数 block_out=(cha
20、r *)calloc(2*blocks,sizeof(char); for(i=0;iblocks;i+)/非短块的分组 fread(block_in,sizeof(char),2,fpin); for(j=0;j-1;k-) in_sixteenj*8+k=(unsigned char)block_inj%2; block_inj=(unsigned char)block_inj/2; SPN_D1(in_sixteen,out_sixteen);/调用解密函数 for(j=0;j2;j+)/短块的分组 block_outi*2+j=0; for(k=0;k-1;i-) if(i-1;j-)
21、 DMj=SO_BoxDM1j;/S盒逆置换 TenToBit(DM1,DM,16);/十进制转二进制 SPN_XOR(DM1,Keyi,16);/异或 Copy(MesInM,DM1,16);调用到的子函数：void Copy(int *Out,int *In,int len)/拷贝函数 int i; for(i=0;ilen;i+) Outi=Ini;void BitToTen(int *Out,int *In,int num)/数组形式二进制转十进制 int i; for(i=0;i=0;i-) Outi=Ini/4%2; Ini/4/=2; void SPN_Trans(int *Ou
22、t,int *In,int num, int *change)/置换 int i; static int temp32=0; for(i=0;inum;i+) tempi=Inchangei-1; Copy(Out,temp,num);void SPN_XOR(int *DatA,int *DatB,int num)/异或函数，并将异或结果存入DatA中 int i=0;for(i=0;inum;i+)DatAi=DatAiDatBi;void SPN_K(void)/将密钥K分成5个16位数组 int i,j; int z=0; for(i=0;i5;i+) for(j=0;j16;j+,z
23、+) Keyij=Kz; z-=12; 4.2 线性密码分析具体实现void SPN_Wire(int len)/线性密码分析 int L1,l1,L2,l2,z; int i,j,m,tmp; int b,c,e,d,f,g,h; int Key_Out32=0; int count1616; int RanIn16=0; int RanOut16=0; int RanOut216=0; int U24=0,U44=0; for(L1=0;L116;L1+) for(L2=0;L216;L2+) countL1L2=0; for(m=0;mlen;m+) Rantext(RanOut,Ran
24、In);/生成随机明密文 for(L1=0;L116;L1+) for(L2=0;L216;L2+) l1=L1(RanOut4*8+RanOut5*4+RanOut6*2+RanOut7); l2=L2(RanOut12*8+RanOut13*4+RanOut14*2+RanOut15); i=SO_Boxl1;/S盒逆置换 TenToBit(U2,&i,4); j=SO_Boxl2; TenToBit(U4,&j,4); z=RanIn4RanIn6RanIn7U21U23U41U43; if(z=0) countL1L2+; int max=-1; int key6,key8; for(
25、L1=0;L116;L1+) for(L2=0;L2max) max=countL1L2; key6=L1; key8=L2; TenToBit(&Key_Out20,&key6,4);TenToBit(&Key_Out28,&key8,4);/暴力破解 for(e=0;e16;e+) Trans(Key_Out,e); for(d=0;d16;d+) Trans(&Key_Out4,d); for(f=0;f16;f+) Trans(&Key_Out8,f); for(g=0;g16;g+) Trans(&Key_Out12,g); for(h=0;h16;h+) Trans(&Key_Ou
26、t16,h); for(j=0;j16;j+) Trans(&Key_Out24,j); srand(unsigned)time(NULL); int judge=0; for(c=0;c2;c+) if(judge=0) for(b=0;b0|tmp=0)&tmp5)RanInb=0; elseRanInb=1; SPN_Start(RanIn,RanOut); SPN_Start1(Key_Out,RanIn,RanOut2); if(!compare(RanOut,RanOut2,16)judge=1; if(!judge) for(i=0;i32;i+) printf(%d,Key_O
27、uti); 4.3差分密码分析具体实现void SPN_Cha(int len) int L1,l1,L2,l2,z; int i,j,m,p,q,r,t; int b,c,e,d,f,g,h; int x16=0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0; int Key_Out32=0; int count1616; int RanIn16=0,RanIn116=0; int RanOut16=0,RanOut116=0,RanOut216=0; int U2,U4,U2_1,U4_1; for(L1=0;L116;L1+) for(L2=0;L216;L2+) countL1L2=0; for(m=0;mlen;m+) Rantext(RanOut,RanIn); for(i=0;i16;i+) RanIn1i=RanInixi; SPN_Start(RanIn1,RanOut1); BitToTen(&p,RanOut,4); BitToTen(&q,&Ran