课 程 设 计 报 告
题目： 密码学课程设计
课程名称： 密码学课程设计
专业班级： 信安1904班
学 号： U201912177
姓 名： 段帅杰
指导教师： 路松峰老师
报告日期： 2021/10/12
教师评语：
分数：
网络空间安全学院
目录
一、设计过程 1
1.1 SPN实现 1
1.2线性分析 2
1.3差分分析 3
1.4 SPN增强 4
1.5 RSA参数计算 5
1.6模重复平方 6
1.7中国剩余定理 7
1.8 PKCS7 8
1.9彩虹表 9
二、实验心得 10
三、对课程设计内容和过程的建议 11
一、设计过程
1.1 SPN实现
（1）设计内容
按照课本给出的的S盒和P盒以及密钥编排方案来实现分组密码SPN加解密。有两个输入，分别是32比特的密钥和16比特的明文。要正确输出密文和对明文最后一比特取反解密得到的明文。加密过程主要包括三个部分：代换，置换和轮密钥异或。
（2）设计过程
算法所注意的问题：加密与解密主要在于密钥编排顺序不同，算法过程基本相同。最后一轮没有经过P盒。
解决这道题最直接的思路就是开数组及进行运算，但这样显然速度不够快。后来摒弃这种做法，采用位运算，速度快了不少而且这种做法方便快读快写的程序实现。但还是有几个数据点过不了oj，后面打了一个65536的表，将时间提高至1100ms左右。最后采用了快写才将时间稳定在700ms左右。
（3）小结
采用打表的方式程序速度确实有提高，但是程序很臃肿。程序中还有些算术运算并没有转换为位运算。
图1-1 SPN实现oj结果图示
1.2线性分析
（1）设计内容
线性分析是一种已知明文的分析方法，基于S盒逼近，需要大量的明密文对。oj上给了8000对明密文对。并且只对最后一轮子密钥进行分析。在密钥生成算法固定的情况下，获得最后一轮子密钥可以为分析别的密钥提供可能。遍历可能的密钥空间并进行计数，结束后正确的密钥计数值接近1/2±ϵ，并且应该在一定范围内对计数值较大的可能密钥进行验证。
（2）设计过程
首先使用书中给出的线性分析链，分析出第5轮第2、4部分的密钥。再选择新的偏差较大的线性分析链，在第2、4部分密钥已知的基础上分析出第1、3部分的密钥。接着在已知起始密钥低16位的基础上，穷举高16位密钥对给出的8000个明密文对进行验证。由于在加密过程中进行了5轮的S代换和P置换，其实相同明文在不同密钥下得到相同密文的概率极低，因此并没有验证8000个明密文对是否对应，而仅验证了3个判断密钥是否合适。
程序有两层主循环，第一层主循环遍历可能的第5轮第2、4部分密钥，第二层在已知第5轮第2、4部分密钥的基础上生成并遍历可能的第5轮第1、3部分密钥，同时穷举高16位密钥并进行验证。
（3）小结
为了提高速度，程序中同样采用了打表。但是在oj上仍然差了300ms，最后是开启了03优化才能全部通过(开启这个优化通过oj，算不上很完美)。
#pragma GCC optimize(3,”Ofast“,”inline“)
图1-2 线性分析oj结果图示
1.3差分分析
（1）设计内容
实验目的是实现对SPN网络的差分密码分析。差分密码与线性密码分析相似。主要区别在于它将两个输入的异或与其相对应的两个输出的异或相比较，是一种选择明文攻击。差分攻击的基础是一个非均匀的输出分布。和线性分析进行类似的计数操作并在计数值一定范围内对密钥进行验证。
（2）设计过程
首先使用书中给出的差分链分析出第5轮第2、4部分的密钥。再选择新的差分链分析出第5轮第1、3部分密钥，然后穷举高16位密钥情况，并验证密钥正确性。
与线性分析不同的是，由于差分分析中可以找到一条第5轮仅包含第1、3部分且偏差很大的差分链，因此不需要在已知第5轮第2、4部分的基础上进行差分分析，也因此减小了部分时间开销。
代码实现流程为：快速读入数据并存入数组中；根据已有的明密文对分别对第5轮第2、4部分和第1、3部分进行差分分析，记录每一种密钥对应的count值。在一定范围内遍历第5轮第2、4部分和第1、3部分密钥，穷举高16位密钥并验证正确性，得到正确密钥后快速输出密钥。
（3）小结
程序提交oj的时候最后一个测试点偶尔会出现超时的情况。
图1-3 差分分析oj结果图示
1.4 SPN增强
（1）设计内容
对原始SPN进行改进，自定义密钥长度，分组长度，S盒，P盒等信息，对输入比特流进行加密使输出能够通过oj的随机数检测标准。
（2）设计过程
相比于之前的SPN，做了些改动。采用CBC模式，随便设置一个初始向量，并且将密钥增加到128位，SPN加密长度增加到64位，使用自定义的P盒。这样才通过了随机性检测。
（3）小结
这道题不像之前的题目卡时间那么难受，虽然安全性相比于最初的SPN有所提高，但是真正应用的话，安全性还是不行。
图1-4 SPN增强oj结果图示
1.5 RSA参数计算
（1）设计内容
实验目的是自己利用gmp库提供的大整数基本运算来实现求逆和最大公因数，输出RSA参数d，并检查RSA参数的合法性。
（2）设计过程
首先是利用vcpkg在主机vs2019上搭建好了运行环境。实现了素性检测，gcd的求解以及求逆等过程。主要遇到的问题是在验证安全性上，判断参数是否正确。首先e不能太小，主要为了提高计算的难度；p和q间隔不能太小；p-1和q-1不能太光滑，即gcd(p-1,q-1)应该比较小，经过询问和验证，这个值大概在20以内。
（3）小结
这个实验主要熟悉了gmp库提供的大整数相关的基本函数运算。比较麻烦的是需要自己摸索测试方法，探索p和q的间隔，(p-1)和(q-1)的最大公因数大小等。在运行速度上倒是没遇到什么大问题。
图1-5 RSA参数计算oj结果图示
1.6模重复平方
（1）设计内容
实验目的是利用gmp库提供的加法，减法，乘法，模运算等基本运算来自己实现expmod(a,e,n)。
（2）设计过程
这道题逐步计算就行，需要注意的是递归或者普通的循环是行不通的。为了加快运行速度，要尽量减少循环次数。
（3）小结
这道题主要还是gmp库提供的函数的应用。
图1-6模重复平方 oj结果图示
1.7中国剩余定理
（1）设计内容
实验内容：正确计算c^d(modpq)。利用1.5中的求逆运算从加密密钥e计算解密密钥d。
利用1.6中实现的模幂运算和中国剩余定理计算c^d(modpq)。
（2）设计过程
这道题主题要是与前面两题的结合，使用p，q并运用中国剩余定理解密。为了加快速度解决的问题：
1.避免重复计算，用变量将不会改变的值保存好，避免不必要的计算。
2.在求解模幂时，将解密指数d模除以p-1和q-1，加速计算。
（3）小结
虽然经过改进，运行时间有所提高，但是最后一个测试点还是压着边过的。
图1-7中国剩余定理oj结果图示
1.8 PKCS7
（1）设计内容
PKCS#7是PKI中用于消息加密的语法标准。可以用于给拥有公钥的用户发加密邮件、传送加密文件等。实验目的是解开PKCS#7包装，获取明文消息。
（2）设计过程
这道题首先是查找PKCS#7的相关知识，了解它的用途。算是对上学期所学知识的综合应用的一个实例。然后利用openssl库提供相关的函数进行解密。
（3）小结
这道题时间并不是问题。还是比较轻松的。
图1-8 PKCS7 oj结果图示
1.9彩虹表
（1）设计内容
有一些链头和链尾，每条链从链头开始，依次调用了10000次SHA1和R函数得到链尾。
实验目的是从这些链中找到SHA1值对应的口令。
（2）设计过程
在程序中定义了UnitSHA1函数来寻找SHA1，通过findstr函数判断是否恰当。为了加快运行速度，程序中同样采用了快读快写以及位运算等。
（3）小结
这道题虽然时间限制提高至2000ms，但最后有几个测试点还是开了03优化才过的。
图1-9 彩虹表oj结果图示
二、实验心得
这次试验包含了SPN加解密及其分析，RSA参数，模重复平方，中国剩余定理，PKCS7，彩虹表等九个实验的内容。在实验过程中，要到了许许多多的问题。主要有以下几点：
SPN的位运算，最初因为对位运算不够熟悉并没有想着用位运算来实现SPN的加解密，多走了很多弯路。
密码分析问题，线性分析和差分分析否需要自己依据原理来找到最理想的链，而且需要先对概念原理有个清楚的认知，这就迫使我再次回顾密码学课本和网课上的知识点。
运行时间问题，为了缩短运行时间，采取了很多办法。比如打表，快读快写，在某些不改变的变量前面加const，在常用的变量前加register，算术运算转变为位运算等等。实在过不了的开启了02，03优化。
第三方库的安装与链接，在采用了许多方法无果后，采用了vcpkg库管理工具实现了gmp，gmssl，openssl等的安装与链接，减少了许多配置的麻烦。
密码学课程知识的回顾，过了一个暑假，部分密码学的细节知识有所遗忘，为了完成这次实验，需要重新学习一遍。这种回顾知识的机会自高中结束以来很少有了。上学期主要进行理论学习，这次试验弥补了实践的缺失。
总的来说，这次课设给我留下了深刻印象。自己写的代码不能正常运时的焦虑感是做其他实验没有的。大部分问题都要重新回顾之前的密码学知识。通过网上搜索相关概念，询问老师和同学解决。有些细节问题也会与同学交流讨论。这次实验让自己对密码学的认识和自己的编程能力上升了一个台阶。
希望能够在完成人数适当的时候进行一次讲解，这样可以让没有方向的同学知道如何着手，也可以让已经完成的同学进行思路的比对，有所改进。小范围讨论和统一讲解同样重要。
希望oj上的时间增加一点，因为时间而卡在一道题上过不去的滋味并不好受。而且实验是在锻炼我们的思考问题和实践的能力。如果时间太少的话，就只能参考别人的思路来缩短运行速度，同质化严重。不利于学生独立思考，写出各种各样的程序。我们写的程序最终也不会进行应用，更重要的是锻炼，纠结于几百毫秒反而降低了学生的热情。
在课设结束后发出参考样例方便有需要的同学进行改进。
希望实验课能越来越好，通过实验来吸引更多对密码学有兴趣的人。
点击咨询