注意在咱们课程的古典密码学部分对a-z编码时，a对应0，z对应25
冒泡排序复杂度
- 其中的n怎么理解？
- n个数字，n确实与长度有关，因为n越大数据越多。
- 如果想要考虑得更细粒度（考试不需要），可以再继续考虑每一个数据需要m bit位，则每次必要需要比较m个bit，复杂度
- $(n-1)m+(n-2)m+…+1*m$ji
- 即 $O(mn^2)$
- 如果数据长度对问题影响比较大，那么确实就要考虑这个问题(考试不说的话就不用考虑)
超递增背包问题
for i=n,i>=1,i--{
if S>=an
xn=1,s=s-an
else
xn=0
}
n次比较和减法 -> O(n)
不用纠结每一个数是多少bit，除非真的要求
进行如此细粒度的考虑
3DES问题 p→Ek1→中间x→Ek2→Ek3→c
记Q为比较操作操作
-
$k_1$遍历E+排序 得到表B
$2^{56}（E+log_22^{56}Q)$ 加密与二分搜索≤ $2^{56}(57E)$
-
(k2,k3)遍历
- c用k3解密，再用k2解密，得到中间x’
- x’去表B中搜，是否x’在表中
- 如果找到，则输出，如果找不到，则继续下一轮遍历
$2^{112}(D+log_22^{56}Q)$ 解密与二分搜索
≤ $2^{112}(57D)$
子密钥
- 主要是看PC-1进到C/D中的问题
DES的密码编排
-
连续两轮多少比特不同，多少比特相同
- 这个是有实际意义的，如果能看到每一轮的子密钥之后，判断某一个秘钥是否是真实密钥的方法。判断方法就是
- 如上图，轮1轮2有相同数字的话就可以划掉，留下不相同的
- 老师他的学生的程序算出最后两轮子密钥是没有全部比特信息，但是我们有同学去跟老师探讨了这个问题，现在存疑，老师再让她的研究生重新统计。
