密码学课程设计实验报告.docx
- 文档编号:9111200
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:26
- 大小:748.72KB
密码学课程设计实验报告.docx
《密码学课程设计实验报告.docx》由会员分享,可在线阅读,更多相关《密码学课程设计实验报告.docx(26页珍藏版)》请在冰点文库上搜索。
密码学课程设计实验报告
课程设计报告
科目:
密码学
院系名称:
计算机科学与技术
专业班级:
信安1001班
学号:
U*********
*****
指导教师:
汤学明崔永泉骆婷
报告日期:
2012.5.25
计算机科学与技术学院
第一部分数据加密标准DES
一、实验目的
1、掌握DES中各加密函数对其性能影响;
2、DES的特性分析,包括互补性和弱密钥;
3、DES的实际应用,包括各种数据类型的加/脱密、DES的短块处理。
二、实验题目及要求
2.1DES的编程实现
输入加密密钥和一串有意义的汉字,显示相应的加密结果;
输入密文和脱密密钥,显示所还原的一串有意义的汉字;
设计用户界面,界面中要有加/脱密选择、输入明/密文栏、密钥栏和加/脱密结果显示栏。
2.2DES的短块处理
针对有短块和无短块二种情况,编写并实现具有短块处理功能的DES通用加/脱密软件;
短块处理对用户透明;
设计用户界面,其结构与实验1的用户界面基本相同,但要增设明文长度和密文长度栏。
2.3DES弱密钥过滤软件设计
设计用户界面,当用户输入弱密钥时会出现提示信息;
编制过滤程序,实现对弱密钥的过滤。
2.4DES密钥差分攻击设计
输入一串密钥,进行6轮DES差分攻击,将攻击结果与原密钥比较。
三、实验原理
3.1DES基础知识
DES算法是由美国IBM公司在20世纪70年代提出,并被美国政府、美国国家标准局和美国国家标准协会采纳和承认的一种标准加密算法。
它属于分组加密算法,即在明文加密和密文解密过程中,信息都是按照固定长度分组后进行处理的。
混淆和扩散是它采用的两个最重要的安全特性。
混淆是指通过密码算法使明文和密文以及密钥的关系非常复杂,无法从数学上描述或者统计。
扩散是指明文和密钥中每一位信息的变动,都会影响到密文中许多位信息的变动,从而隐藏统计上的特性,增加密码的安全。
3.2DES加解密过程
DES算法将明文分成64位大小的众多数据块,即分组长度为64位,同时用56位密钥对64位明文信息加密,最终形成64位的密文。
如果明文长度不足64位,则将其扩展为64位(如补零等方法)。
具体加密过程首先是将输入的数据进行初始换位(IP),即将明文M中数据的排列顺序按一定的规则重新排列,生成新的数据序列,以打乱原来的次序。
然后将变换后的数据平分成左右两部分,左边记为L0,右边记为R0,然后对R0实行在子密钥(由加密密钥产生)控制下的变换f,结果记为
,再与L0做逐位异或运算,其结果记为R1,R0则作为下一轮的L1。
如此循环16轮,最后得到L16、R16。
再对L16、R16实行逆初始置换IP-1,即可得到加密数据。
解密过程与此类似,不同之处仅在于子密钥的使用顺序正好相反。
DES全部16轮的加密过程如图3.1所示。
图3.1DES加密流程图
DES的加密算法包括3个基本函数。
1.初始换位(IP)
它的作用是把输入的64位数据块的排列顺序打乱,每位数据按照下面换位规则重新组合,即将第58位换到第1位,第50位换到第2位,……,依次类推,重组后的64位输出分为L0、R0(左、右)两部分,每部分分别为32位。
58,50,42,36,18,10,2,60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,
R0和K1经过
变换后的输出结果,再和L0进行异或运算,输出结果做为R1,R0则赋给L1。
L1和R1同样再做类似运算生成L2和R2,……,经过16次运算后生成L16的R16。
2.f函数
f函数是多个置换函数和替代函数的组合函数,它将32位比特的输入变换为32位的输出,如图3.2所示。
图3.2DES算法中f函数的处理流程图
Ri经过扩展运算E变换(表3.1)后扩展为48位的
,与Ki+1进行异或运算后输出的结果分成8组,每组6比特的并联B,B=B1B2B3B4B5B6B7B8,再经过8个S盒(表3.3)的选择压缩运算转换为4位,8个4位合并为32位后再经过P变换(表3.2)输出为32位的
。
其中,扩展运算E与置换P主要作用是增加算法的扩展效果。
表3.1扩展运算E表3.2P变换
表3.3DES的S盒
DES具体的子密钥产生流程如图3.3所示。
图3.3DES子密钥产生流程
输入的初始密钥值为64位,但DES算法规定,其中第8、16、......64位是奇偶校验位,不参与DES运算。
所以,实际可用位数只有56位,经过缩小选择换位表1(表3.2)即密钥置换PC-1的变换后,初始密钥的位数由64位变成了56位,将其平分为两部分C0、D0,然后分别进行第1次循环左移,得到C1、D1,将C1(28位)、D1(28位)合并后得到56位的输出结果,再经过缩小选择换位表2(表3.3)即密钥置换PC-2,从而便得到了密钥K1(48位)。
依此类推,便可得到K2、......K16,需要注意的是,16次循环左移对应的左移位数要依据表3.1中规则进行。
表3.1左移位数规则
表3.2缩小选择换位表1表3.3缩小选择换位表2
3.逆初始置换函数IP-1
它将L16和R16作为输入,进行逆初始换位得到密文输出。
逆初始换位是初始位的逆运算,换位规则如下所列:
40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31
38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29
36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27
34,2,42,10,50,18,58,26,33,1,41,9,49,17,57,25
3.3DES弱密钥
DES的解密过程和DES的加密过程完全类似,只不过将16圈的子密钥序列K1,K2……K16的顺序倒过来。
即第一圈用第16个子密钥K16,第二圈用K15,其余类推。
如果K16=K1,K15=K2,…,K9=K8,则加密所用的子密钥与解密所用的子密钥相同,对一个明文X加密两次,得到的还是明文X。
更强的,若K1=K2=…=K16,则加密过程与解密过程完全一样。
弱密钥的定义也就是这样定义:
若k使得加密函数与解密函数一致,则称k为弱密钥。
DES至少有4个弱密钥,让我们先来看看子密钥的产生过程:
64Bits的密钥K经PC-1之后,变为56Bits,然后分为高28Bits和低28Bits,分别进行移位。
LSi是循环左移。
PC-2是从56Bits中选出48Bits输出。
若C0和D0为全0或全1,则经过移位后显然不变,于是16个子密钥都相同。
C0和D0是独立进行移位的,组合一下,就有4个弱密钥了。
因此至少有4个弱密钥。
(1)K1=…=K16=0x000000000000
(2)K1=…=K16=0xFFFFFFFFFFFF
(3)K1=…=K16=0x000000FFFFFF(4)K1=…=K16=0xFFFFFF000000
检测16个内部密钥是否完全相同,若完全相同则判断为弱密钥,否则为正常密钥。
3.46圈DES差分攻击原理
图3.4略去初始置换和末置换的3轮DES
我们先看3轮DES差分攻击的原理:
破解条件:
已知一组明文E1、E2,以及对应的密文C1、C2,其中E1和E2的低32bit相同。
令E1.L0表示E1的高32bit,E1.R0表示E1的低32bit,同理E1.L1表示E1加密一圈后的高32bit,其它的数据同理表示。
基本结论:
置换传递差分;E扩展传递差分;异或传递差分;
如图3.4所示,设E1加密到位置1的值为E1.pos1,E1加密到位置2的值为E2.pos2。
K3=E1.pos1⊕E1.pos2或者K3=E2.pos1⊕E2.pos2
根据已知条件,位置1的值很容易获得,关键是求出位置2的值或者位置2的值的可能情况。
根据基本结论,对于这组数据,位置2和位置3的差分容易获得:
E1.pos1=E(E1.R2)=E(C1.L3)(密文C1高32bit的E扩展)
E2.pos1=E(E2.R2)=E(C2.L3)(密文C2高32bit的E扩展)
E1.pos2⊕E2.pos2=E1.pos1⊕E2.pos1=E(C1.L3)⊕E(C2.L3)
E1.pos3⊕E2.pos3=DeP(E1.L2⊕E1.R3)⊕DeP(E2.L2⊕E2.R3)
=DeP(C1.R3⊕C2.R3⊕E1.R1⊕E2.R1)(E1.R0⊕E2.R0=0)
=DeP(C1.R3⊕C2.R3⊕E1.L0⊕E2.L0)(DeP为P的逆置换)
这样位置2和位置3的差分都可以求解得到,根据S盒构造如下一张表,列举出所有可能的E1.pos2情况,可以通过多组数据,匹配重叠的情况,就可以求解出K3或者K3可能的情况,由K3可以获得K的48bit,对于剩余的8bit可以穷举搜索得到。
差分表如下形式(对于每个S盒):
X1⊕X2
Y1⊕Y2
X1可能的值列表
…
…
…
对于6圈DES来说,和3轮基本类似。
问题是对于6轮的攻击,假设的输出异或是正确的概率仅为1/16。
如果我们从特征的正确对开始运作,则正确密钥Ji一定在testi中。
如果从特征的错误对开始运作,由于Ci。
错误,因此testi可假设为随机的。
四、实验环境
操作系统:
Windows7
编程工具:
QTCreator
五、实验设计
5.1DES的编程实现和整体界面设计
DES算法的编程实现现在已经非常普遍了,所以这一部分我是直接从网上拷贝下来的程序,经过自己的修改调试,再加上RSA的一部分,最终界面如图5.1所示。
图5.1界面效果预览图
5.2DES短块处理
短块处理采用了两种方式:
填充方式和密文挪用。
在填充方式下,如果最后一个块长度不满8字节,则在后面填充0,并在最后一个字节放上填充0的数目。
在密文挪用方式下,把最后一个不满8字节的块和前面一个加密后的块拼接成8字节再加密。
如图5.2所示。
图5.2密文挪用原理示意图
核心代码如下:
if(mode==FillMode)
{
if(count)
{
memset(plainBlock+count,'\0',7-count);
plainBlock[7]=8-count;
DESEncryptBlock(plainBlock,subKeys,cipherBlock);
outFile.write(cipherBlock,8);
}
}
elseif(mode==PeculateMode)
{
if(inFile.size()<8)
{
SetLastError(QString("密文挪用方式下明文长度必须大于8!
"));
returnfalse;
}
if(count)
{
for(inti=0;i<8-count;++i)
{
tempBlock[i]=cipherBlock[count+i];
}
for(inti=0;i { tempBlock[8-count+i]=plainBlock[i]; } DESEncryptBlock(tempBlock,subKeys,cipherBlock); outFile.seek(outFile.pos()+count-8); outFile.write(cipherBlock,8); } } 5.3DES弱密钥过滤 在DES程序中加入一个弱密钥检测函数,通过检测其16个内部密钥是否相同,来判断所输入的密钥是否为弱密钥。 核心代码如下: boolisWeakKey(charsubKeys[16][48]) { for(inti=1;i<16;++i) { for(intj=0;j<24;++j) { if(subKeys[0][j]! =subKeys[i][j]) { returnfalse; } } } returntrue; } 5.4DES差分攻击 在6圈DES差分攻击中,我们采用了以下两个圈特征: 4008000004000000X; 0020000800000400X。 这两个特征中每个特征都找到K6的30bit的子密钥。 它们在第6圈分别有5个S盒的输入异或为0,根据差分的性质,其输出异或也为0,其中第一个的5个S盒为S2,S5,S6,S7,S8,第二个的5个S盒为S1,S2,S4,S5,S6,使用两个圈特征,就能找到K6的42bit的子密钥。 余下的14bit可以采用穷举的方法找到。 六、实验结果 6.1DES编程实现 运行程序,进入DES加解密界面,如图6.1所示: 图6.1DES加解密界面 6.2DES短块处理 6.2.1填充方式 在输入数据框中输入明文,选择输入数据操作和填充,加密结果如图6.2所示,明、密文长度分别为10、16。 图6.2填充方式加密 解密时,把密文复制到输入数据框中。 如图6.3所示,成功解密,明文长度和密文长度不变。 图6.3填充方式解密 6.2.2密文挪用 采用密文挪用加解密时,只需要将“填充”改为选择“密文挪用”即可,加密结果如图6.4所示,解密结果如图6.5所示。 可以看到,明、密文的长度均为14,符合密文挪用的特点。 图6.4密文挪用加密 图6.5密文挪用解密 6.3DES弱密钥检测 如果输入的是弱密钥,在加解密时会被检测出来,并弹出提示框,如图6.6所示。 图6.6弱密钥检测 6.4DES差分攻击 在主界面中选择“6圈DES差分攻击”,如图6.7所示。 图6.7DES差分攻击界面 设置密钥为1010101010101010,如图6.8. 图6.8设置密钥 点击“破解密钥”,结果如图6.9所示。 图6.9破解密钥 第二部分公钥密码RSA 一、实验目的 1、通过实际编程掌握非对称密码算法RSA的加密和解密以及快速加、解密过程,加深对非对称密码算法的认识; 2、实现对RSA的解密密钥攻击。 二、实验题目及要求 1、编制或网上下载大素数生成算法,产生二个大素数p和q; 2、编写RSA的加/解密过程和快速加/解密过程; 3、通过调用时钟对二种加/解密方法的时间开销进行测试; 4、设计用户界面,界面要有加/解密方式选择,快速方式与一般方式的选择及时间开销显示。 三、实验原理 前面讲的对称密码算法要求通信双方通过交换密钥实现使用同一个密钥,这在密钥的管理、发布和安全性方面存在很多问题,而非对称密码算法解决了这个问题。 非对称密码算法是指一个加密系统的加密密钥和解密密钥是不同的,或者说不能用其中一个推导出另一个。 在非对称密码算法的两个密钥中,一个是用于加密的密钥,它是可以公开的,称为公钥;另一个是用于解密的密钥,是保密的,称为私钥。 非对称密码算法解决了对称密码体制中密钥管理的难题,并提供了对信息发送人的身份进行验证手段,是现代密码学最重要的发明。 RSA密码体制是目前为止最成功的非对称密码算法,它是在1977年由Rivest、Shamir和Adleman提出的第一个比较完善的非对称密码算法。 它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上,即将两个大素数相乘在计算上容易实现,而将该乘积分解为两个大素数因子的计算量相当大。 虽然它的安全性还未能得到理论证明,但经过20多年的密码分析和攻击,迄今仍然被实践证明是安全的。 3.1RSA算法的加解密原理 1.公钥 选择两个互异的大素数p和q,n是二者的乘积,即n=pq,使 为欧拉函数。 随机选取正整数e,使其满足 ,即e和 互质,则将 作为公钥。 2.私钥 求出正数d,使其满足 ,则将(n,d)作为私钥。 3.加密算法 对于明文M,由 ,得到密文C。 4.解密算法 对于密文C,由 ,得到明文M。 如果窃密者获得了n、e和密文C,为了破解密文必须计算出私钥d,为此需要先分解n。 为了提高破解难度,达到更高的安全性,一般商业应用要求n的长度不小于1024位,更重要的场合不小于2048位。 3.2RSA算法的快速加解密原理 3.2.1模重复平方 在计算 时,将K化成二进制序列 ,则 由此将乘法次数由 下降至 。 模重复平方法是加快RSA运算速度的主要手段。 3.2.2中国剩余定理 中国剩余定理用在RSA解密过程中,可以大大提高解密速度,对加密无效。 中国剩余定理(ChineseRemainderTheorem,CRT)是初等数论中重要的基本定理之一,它主要是刻画剩余系的结构和求解形如x≡di(modpi)(1≤i≤s)的一次同余式方程组。 定理 (CRT)[3,4,5]设p1,p2,…,ps是两两互素的正整数,即GCD(pi,pj)=1(i≠j),对于任意整数 d1,d2,…,ds(0≤di≤pi-1,i=1,2,…,s),同余式方程组: x≡d1(modp1) x≡d2(modp2) …… x≡ds(modps) 有惟一解。 计算数论中,计算中国剩余定理惟一解的方法有两种: 单基数转换法(Single2RadexConversion,SRC)和混合基数转换法(Mixed2RadexConver2sion,MRC),这两种方法都是非常实用的计算方法。 这里我们略过单基数转换法不谈,直说混合基数转换法。 利用混合基数转换法(MRC)求CRT惟一解的方法是H.L.Garner在1958年首先提出的。 之后,D.E.Kunth将其用于计算数论,并进行了有益的改进。 经Kunth改进后的MRC方法用算法描述如下: 算法1 CRT的混合基数转换法(MRC)[3]。 (1)计算Bji←p-1j(modpi),(1≤j (2)分别计算v1←d1(modp1); v2←(d2-v1)B12(modp2); …… vs←(ds-(v1+p1(v2+p2(v3+…+ps-2vs-1)…)))B1sB2s…B(s-1)s(modps). (3)计算惟一解X←vsps-1 …p2p1+…+v3p2p1+v2p1+v1。 在上述算法的第 (2)步中,感觉上计算v1,v2,…,vs的过程好象比较杂乱,不容易实现。 其实不然,深入分析各式,发现其中隐含着递归成分,很容易利用递归公式完成相应计算。 在此基础上有以下改进的算法: 算法2 改进的MRC算法(MMRC)。 (1)计算Bji←p-1j(modpi),(1≤j (2)令ai1=di(1≤i≤s),由递归公式ai(j+1)=(aij-ajj)Bji(modpi),1≤j 计算出三角形数值表斜边上的数值(即a11,a22,…,ass); (3)计算惟一解x←a11+a22p1+a33p1p2+…+assp1p2p3…ps。 由于利用MMRC的解密算法是实现RSA解密的最佳算法,它使RSA的解密速度加快大约4倍,可大大提高用于RSA的软硬件解密实现。 故我们采用MMRC算法。 算法描述如下: (1)计算d1←d(modp-1)与d2←d(modq-1); (2)计算C1←c(modp)与C2←c(modq); (3)计算M1←Cd11(modp)与M2←Cd22(modq); (4)计算B←p-1(modq); (5)计算m←M1+[(M2-M1)*B(modq)]*p。 四、实验环境 操作系统: Windows7 编程工具: QTCreator 五、实验设计 5.1RSA加解密 和DES一样,这一部分我也是直接在网上拷贝的代码,结合DES做的界面修改调试后使用。 5.2RSA快速加解密 利用模重复平方和MMRC算法编写。 MMRC算法: (1)计算d1←d(modp-1)与d2←d(modq-1); (2)计算C1←c(modp)与C2←c(modq); (3)计算M1←Cd11(modp)与M2←Cd22(modq); (4)计算B←p-1(modq); (5)计算m←M1+[(M2-M1)*B(modq)]*p 六、实验结果 打开RSA主界面,如图6.10所示。 图6.10RSA加解密主界面 点击“生成全部”,将随机生成RSA加解密所需的各种参数,如图6.11所示。 图6.11生成RSA参数 输入明文,选择加密方式(一般方式/快速方式),就会开始加密。 在这里,由于一般方式加密太慢,会导致程序未响应,故我们选择快速方式。 加密结果如图6.12所示,显示加密时间为0.03000s;解密结果如图6.13所示,解密时间为0.01000s。 图6.12RSA快速加密 图6.13RSA快速解密 实验体会 做这个实验让我把DES和RSA的内容从头又复习了一遍,对DES和RSA的相关问题有了更深一层的理解,运用起来也更加熟练。 尤其是DES差分分析的部分,上课的时候并没有很仔细地来讲,这次通过自己不断查找资料,能够掌握它的原理,并写出程序,让我很有成就感。 不过差分工作并不是很圆满,奇校验限制了密钥的选择,这点将会继续改进。 除此之外,RSA的加密分组由于时间问题也没有完成,这些都会在以后慢慢探究,慢慢补充完整。 这次实验带给了我很大的收获,让我巩固了密码学的知识并在此基础上进一步挖掘和创新,还学会了使用QT工具编程等。 我相信这将对我以后的学习产生很大的帮助。 参考文献 [1]Stinson,D.R.著,冯登国等译.密码学原理与实践(第三版).北京: 电子工业出版社,2009.7 [2]冯登国,吴文玲.分组密码的设计与分析.北京: 清华大学出版社,2000 [3]贺毅朝,刘建芹,陈维海.中国剩余定理在RSA解密中的应用.河北省科学院学报,Vol.20No.3,Aug.2003
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 密码学 课程设计 实验 报告