密码学课程设计实验报告

1、密码学课程设计实验报告院 系 计算机科学与技术 学院 专 业 信息安全 班 级 0703 学 号 xxxxxxxxxx 姓 名 xxxxxx 指导教师 xxxxxxxx 2010 年 3 月 18 日目录第一部分一、实验目的二、实验环境及工具三、实验内容四、实验原理五、实验过程65.1设计思路65.2程序的实现部分11六、程序测试126.1制定测试方案126.2测试效果12七、源代码13第二部分一、实验目的14二、实验环境及工具14三、实验内容14四、实验原理14五、实验过程145.1设计思路145.2程序的流程图17六、程序测试196.1制定测试方案196.2测试效果20七、源代码20第三部

2、分实验总结21第一部分三圈des的差分攻击一、实验目的通过课程设计，使学生进一步熟悉密码算法以及算法安全性的基本概念和原理；培养学生将密码理论和技术应用于实际的能力，使学生具备实施数据加/脱密和基本的密码分析的能力。二、实验环境及工具操作系统microsoft windows xp home edition 版本2002 service pack3ide环境microsoft visual c+ 6.0 （sp6）硬件环境intel（r）atom cpu n270 1.60ghz,0.99gb的内存物理地址扩展三、实验内容题目：三圈des的差分攻击；要求：设计必需的界面环境，（1） 输入明文及

3、其对应的密文，产生相应的密钥（2） 设计有好的窗口显示实验结果四、实验原理des加密算法中的各种置换和扩展对差分没有影响，只有s盒可以阻挡差分；设 x=x1x2，y=y1y2,其中x1和x2是s盒的六位输入，y1和y2是相应的四位输出即x1-s=y1,x2-s=y2；那么我们就可以以x为行索引，以y为列索引建立一个64*16的二维矩阵，矩阵中的元素为可能的x值，我们把这个矩阵称作s盒的差分表，如下表所示：yxx011415016263我们一共可以构造八个差分表，下面我们给出三圈des的加密过程（省略了ip置换）：在选择明文攻击的情况下我们很容易保证r0=0，那么我们就可以得到下列式子：-11)

4、 a=e（l3）；2) b=p（r3l0）由于l3、r3、l0在选择明文攻击时都是可求的,所以a、b也是可求的。由于a是s盒的输入b是s盒的输出，我们又能求得a、b所以我们通过查差分表就可以把a局限在一个较小的范围内（在这个范围内穷举是可行的），又由于k3=ac= ae(l3)，所以子密钥k3也被局限到了一个较小的范围内而des的主密钥k的穷举时间是k3的256倍,所以穷举k也是可行的。五、实验过程5.1设计思路其实具体的算法已经在实验原理中给出了，我就是按照此原理设计了一个cattack类用来进行差分攻击，下面是它的头文件：/ attack.h: interface for the catt

5、ack class./#if !defined(afx_attack_h_5c3e3c22_41ec_4d03_8249_6a9d80ecfa07_included_)#define afx_attack_h_5c3e3c22_41ec_4d03_8249_6a9d80ecfa07_included_#if _msc_ver 1000#pragma once#endif / _msc_ver 1000#include des.h#define plaintext00#define plaintext11#define encryptograph02#define encryptograph13

6、#define plaintext24#define plaintext35#define encryptograph26#define encryptograph37class cattack : public cdespublic:cattack();virtual cattack();/*/名称：initattack/功能：初始化8个s盒的差分表/ 参数：/返回：/ 备注：/更新：2010/3/10/作者：王凤伟/*void initattack();/*/名称：tryattack/功能：进行差分攻击/ 参数：key:out 返回破解出来的密钥/返回：成功为ture，否则为false/

7、备注：成功为ture,否则为false/更新：2010/3/10/作者：王凤伟/*bool tryattack(cstring &key);/*/名称：setdata/功能：设置破解参数/ 参数：nflag:in 参数标志/ str:in 参数值/返回：成功为ture,否则为false/ 备注：/更新：2010/3/10/作者：王凤伟/*bool setdata(uint nflag,cstring& str);protected:/*/名称：calcdelta/功能：计算各个差分值/ 参数：byplaintext0:in 明文串0/ byencryptograph0:in 密文串0/ byp

8、laintext1:in 明文串1/ byencryptograph1:in 密文串1/返回：/ 备注：/更新：2010/3/10/作者：王凤伟/*void calcdelta(byte byplaintext0,byte byencryptograph0,byte byplaintext1,byte byencryptograph1);/*/名称：bittouint/功能：二进制位串到整型数据的转换/ 参数：byt:in 二进制串/ len:in 二进制串的长度/返回：转换结果/ 备注：/更新：2010/3/10/作者：王凤伟/*uint bittouint(byte byt,uint le

9、n);/*/名称：uinttobit/功能：整型数据到二进制位串的转换/ 参数：byt:out 二进制串/ len:in 二进制串的长度/ n:in 整数/返回：/ 备注：/更新：2010/3/10/作者：王凤伟/*void uinttobit(byte byt,uint len,uint n);/*/名称：calcsubkey/功能：计算所有可能的子密钥k3/ 参数：r:in 密文的右半部分/ delx:in x的差分/ dely:in y的差分/ subkey:out可能的子密钥/返回：/ 备注：/更新：2010/3/10/作者：王凤伟/*void calcsubkey(byte r,by

10、te delx,byte dely,clist subkey);/*/名称：calcsubkey/功能：穷举56位主密钥/ 参数：/返回：成功为ture，否则为false/ 备注：/更新：2010/3/10/作者：王凤伟/*bool calcmainkey();/*/名称：conjoin/功能：求子密钥交集的函数key2=key2交key1/ 参数：key2in/out:子密钥key2集合/ key1in:子密钥key1集合/返回：/ 备注：/更新：2010/3/10/作者：王凤伟/*void conjoin(clist key2,clist key1);protected:clist m_s

11、86416;/ 用于保存差分表clist m_key18;/ 用于保存可能子密钥集合的链表clist m_key28;/ 用于保存可能子密钥集合的链表byte m_byattackedsubkeyround48;/ 3圈子密钥byte m_byattackeddeskey56;/ 密钥cstring m_strattackeddeskey;/ 密钥串byte m_byencryptograph064;/ 密文0byte m_byplaintext064;/ 明文0cstring m_strplaintext0;/ 明文串0cstring m_strencryptograph0;/ 密文串0by

12、te m_byencryptograph164;/ 密文1byte m_byplaintext164;/ 明文1cstring m_strplaintext1;/ 明文串1cstring m_strencryptograph1;/ 密文串1byte m_byencryptograph264;/ 密文2byte m_byplaintext264;/ 明文2cstring m_strplaintext2;/ 明文串2cstring m_strencryptograph2;/ 密文串2byte m_byencryptograph364;/ 密文3byte m_byplaintext364;/ 明文3

13、cstring m_strplaintext3;/ 明文串3cstring m_strencryptograph3;/ 密文串3byte m_bydeltal032;/ l0的差分byte m_bydeltal332;/ l3的差分byte m_bydeltar3_l032;/ r3的差分异或l0的差分byte m_bydeltaa48;/ a的差分（s盒的输入）byte m_bydeltab32;/ b的差分（s盒的输出）;#endif / !defined(afx_attack_h_5c3e3c22_41ec_4d03_8249_6a9d80ecfa07_included_)5.2程序的实

14、现部分既然原理已经很清楚了，那么设计算法就不在困难了，这里我进一步给出算法的流程图，算法的详细内容请参照文件夹des attacker中的源程序。说明：保存subkey时并不是真正的保存subkey的完整部分，而是将subkey每6位分为一组保存，这样可以大大地减少存储空间（乘法原理）。六、程序测试6.1制定测试方案为了便于测试，我编写了一个简单的三圈des加密程序（des 3 rounds.exe），可以在des 3 rounds文件夹中找到，由用户自主选择密钥和满足条件的明密文对，然后把相应的参数输入到三圈des差分攻击主程序(des attacker.exe)中，进行破译，最后与用户的密

15、钥进行比较。6.2测试效果6.2.1生成破解参数运行程序des 3 rounds.exe，输入相应的明文和密钥，生成参数图6.2.1生成破解参数6.2.1进行破译运行des attacker.exe，并把刚才生成的破解参数复制到相应的编辑框中。图6.2.1 进行破译七、源代码由于该程序的主框架是由mfc的appwizard生成的，代码量很大，所以就不把源代码放到实验报告里了，若要看源代码请打开当前目录下的des attacker文件夹。一、实验目的通过课程设计，使学生进一步熟悉密码算法以及算法安全性的基本概念和原理；培养学生将密码理论和技术应用于实际的能力，使学生具备实施数据加/脱密和基本的密

16、码分析的能力。二、实验环境及工具操作系统microsoft windows xp home edition 版本2002 service pack3ide环境microsoft visual c+ 6.0 （sp6）硬件环境intel（r）atom cpu n270 1.60ghz,0.99gb的内存物理地址扩展三、实验内容题目：rsa解密密钥攻击；要求：设计必需的界面环境，（1） 加密密钥和解密密钥，求p、q，使n=p*q（2） 设计有好的窗口显示实验结果四、实验原理定理：已知k1，k2求p和q，k1*k2=m* （n）+1，若能求x*x=1(mod n)的非平凡根，则可求p和q且p=（x+

17、1,n）,q=(x-1,n)；算法：（1）k1*k2-1-r;0-s; （2）i+1-s,n=r/2; （3）若2|r,则转（2），否则转（4）；（2）-（3）步骤目的是求k1*k2=r*2s） （4）任取w，1wv;若v=1，则转（4）；否则转（6） （6）r/2-r;vr-tem;若tem=1则转（6）；若tem=-1,则转（4）否则p=（tem+1,n）,q=(tem-1,n)，成功说明：算法的关键是第6步，在判断tem的值时，没有简单的判断tem=1或tem=-1时直接重新计算随机数w，而是对tem=1的情况进行了优化，即在tem=1时，把v的指数除二然后得到新的tem，这种优化是必要

18、的，也是有效的。因为v(2s)是收敛于1的，也就是说在随着s的增大v(2s)=1的概率将越来越接近1，而若不把指数缩小很难找到tem!=1的w值，这与利用穷举法分解n的效率相当。我曾经在没有优化的情况下做过实验，当时分解一个20位（16进制）的n，大约需要30分钟，而且都是在（w,n）!=1的条件下返回的（这正是穷举的结果），而经过优化后分解的时间只有几百毫秒的时间，而且都是在第六步返回的。五、实验过程5.1设计思路具体的算法已经在实验原理中给出了，我就是按照此原理设计了一个cattack类用来进行大数分解，而其中最关键的就是cattack:attack()函数，下面给出了源代码：#defin

19、e check(x)if( !(x) ) return false;bool cattack:attack()static bigint r,tem,tem1,v,sem,m,rands,rands1;uint i=0;/ 利用简单的加解密判断用户输入的参数是否正确check(m_obigint.powmod(tem,m_obigint.two,m_k1,m_n)check(m_obigint.powmod(tem1,tem,m_k2,m_n)check(!m_obigint.cmp(tem1,m_obigint.two)check(m_obigint.mul(tem,m_k1,m_k2)ch

20、eck(m_obigint.sub(sem,tem,m_obigint.one)tem=sem;/ 计算k1*k2-1=r*2sdo r=tem;check(m_obigint.div(tem,rands,r,m_obigint.two) while (!m_obigint.cmp(rands,m_obigint.zero);/ 2s-mcheck(m_obigint.div(m,tem1,sem,r)/ 生成随机数rands1check(m_obigint.randval(rands1,m_n.len+1)do do b:if (icycle)i=0;check(m_obigint.rand

21、val(rands1,m_n.len+1)i+;/ 生成满足条件1randsvcheck(m_obigint.powmod(v,rands,r,m_n)check(m_obigint.add(tem,v,m_obigint.one)/ 若v=1或v=-1，则重新生成随机数if (!m_obigint.cmp(v,m_obigint.one)|!m_obigint.cmp(tem,m_n)goto b;tem1=m;/ 2s-temloop:check(m_obigint.div(tem1,tem,tem1,m_obigint.two)/ 计算tem1/2-tem1check(m_obigint

22、.powmod(tem,v,tem1,m_n)/ 计算vtem1-tem/ 如果vtem1=1，则计算v(tem1/2)if(!m_obigint.cmp(tem,m_obigint.one)goto loop;check(m_obigint.add(tem1,tem,m_obigint.one)while(!m_obigint.cmp(tem1,m_n); / 如果vtem1=-1则重新生成随机数rands，否则成功check(m_obigint.add(rands,tem,m_obigint.one)check(m_obigint.sub(rands1,tem,m_obigint.one)

23、check(m_obigint.glb(m_p,rands,m_n)/ p=(tem+1,n)check(m_obigint.glb(m_q,rands1,m_n)/ q=(tem-1,n)cgfl:halfbytetostr(m_strp,m_p.bit,m_p.len);cgfl:halfbytetostr(m_strq,m_q.bit,m_q.len);return true;声明：大数的计算我用的是东北大学的开源的算法库cbigint和通用库cgfl来实现的，在这里我向作者表示感谢。5.2程序的流程图六、程序测试6.1制定测试方案为了便于测试，我编写了一个简单的rsa参数生成程序（generate rsa.exe），可以在generate r