900字范文 > 【现代密码学原理】——分组密码和数据加密标准DES（学习笔记）

【现代密码学原理】——分组密码和数据加密标准DES（学习笔记）

时间：2024-09-07 16:06:20

📖 前言：20世纪70年代以前，密码学的大部分都是政府的安全范畴。直到70年代发生的两件事将密码学带入公众领域，并正式拉开了现代密码学的帷幕。这两件事就是公开的标准加密系统诞生与公钥加密算法的发明。

🕒 0. 思维导图🕒 1. 传统分组密码结构🕘 1.1 流密码与分组密码🕤 1.1.1 流密码🕤 1.1.2 分组密码🕘 1.2 Feistel密码结构的设计动机🕘 1.3 Feistel密码🕤 1.3.1 混淆和扩散🕤 1.3.2 Feistel 密码结构🕒 2. 数据加密标准🕘 2.1 DES的加密过程🕤 2.1.1 初始置换（IP）🕤 2.1.2 16轮处理🕤 2.1.3 轮函数🕞 2.1.3.1 扩展置换（E）🕞 2.1.3.2 异或XOR（⊕）🕞 2.1.3.3 S盒置换🕞 2.1.3.4 P盒置换🕤 2.1.4 逆初始置换（IP^-1^）🕤 2.1.5 密钥生成🕞 2.1.5.1 置换选择1🕞 2.1.5.2 循环左移🕞 2.1.5.3 置换选择2🕒 3. DES的一个例子🕘 3.1 结果🕘 3.2 雪崩效应🕘 3.3 练习题🕒 4. DES的强度🕘 4.1 解决方案🕒 5. 中英文对照表

🕒 0. 思维导图

🕒 1. 传统分组密码结构

🕘 1.1 流密码与分组密码

🕤 1.1.1 流密码

流密码连续不断地处理明文中的各个元素1次加密1个元素，产生1个输出，继续读取next元素可能是1字节，可能是1bit

典型代表：

Vigenère密码Vernam密码一次一密的Vernam

🕤 1.1.2 分组密码

分组密码将一个明文分组作为整体进行加密，通常得到一个与明文等长的密文分组典型的分组大小为64位或128位

分组密码的应用范围比流密码要广泛，大部分基于网络的对称密码使用的都是分组密码；通信双方要共享一个对称加密的密钥

🕘 1.2 Feistel密码结构的设计动机

分组密码作用在一个n位的明文分组上，对应产生一个n位的密文分组明文分组共有2n种不同的可能加密应该是一个可逆的过程，密文能够通过相应的逆运算还原出唯一的原始明文一个密文分组对应着一个唯一的明文分组，这样的变换为可逆变换n = 2，即明文分组的长度为 2 bit，共22种不同的可能

当明文分组不同时，对应的密文分组也是不同的

密文分组共2位，也有22种可能上面左图的密码体制属于可逆变换。如密文分组11，只可能由明文分组00生成，对应的明文分组只有00中图的密码体制属于不可逆变换

如密文分组01，可以由明文分组10生成，也可以由明文分组11生成，对应着两个明文分组右图的密码体制属于n位可逆变换

密文分组共n位，有𝟐𝒏种不同的可能

对于第一个明文分组，可以选择𝟐𝒏个密文分组中的任意一个；

对于第二个明文分组，从剩下的𝟐𝒏−𝟏个分组中选择一个

依次类推，一共有𝟐𝒏×𝟐(𝒏−𝟏)×…×𝟐×𝟏=𝟐𝒏！𝟐^𝒏×𝟐^{(𝒏−𝟏)}×…×𝟐×𝟏=𝟐^𝒏！2n×2(n−1)×…×2×1=2n！种不同的明文密文对应关系对于16种输入状态中的每一种，都能被加密算法映射成唯一的一个输出状态这是分组密码的最一般的形式，也是最理想的形式，此时加密规则达到最大16！种。

练习题：某4位分组密码的加密规则如上所示，请使用该密码加密大写字母A（ASCII值为65）。
解答：
将十进制65 转化为8位二进制数 0100 0001
第一组0100 ：对应十进制为4，加密规则将4号输入状态转换为2号输出状态，对应二进制0010；第二组0001 ：对应十进制为1，加密规则将1号输入状态转换为4号输出状态，对应二进制0100；
因此密文为0010 0100，十进制为36

明文字母e的ASCII值为101，二进制01100101，由2个明文分组0110、0101构成，它们使用频率最高通过该分组密码，生成两个连续的密文分组1011、1111，它们出现频率最高通过这种统计特征可以实施攻击对于像n=4这样比较小的分组，密码系统等价于传统代替密码密文分组保留了明文的统计特征，易于攻击脆弱性由分组过小导致

n充分大

当n充分大，一个明文分组可能由非常多的字母构成明文分组几乎不会有高频率出现的可能，统计规律被掩盖 n充分大的这种分组密码是不可行的比如n=4的某个分组密码，它的加密规则如上，无法描述出加密算法以及密钥，这种情况下映射本身就是密钥密钥长度（4位）*（16行）对于一个n位的分组密码，密钥长度为（n位）× (2n行)=n×2n假设分组长度64位时能抵御攻击，密钥规模将达到1021位

一般的分组密码

理想分组密码有2n！种明文密文映射规则为实现方便，一般的分组密码只涉及到这些映射的一个子集

y1=k11x1+k12x2+k13x3+k14x4y2=k21x1+k22x2+k23x3+k24x4y3=k31x1+k32x2+k33x3+k34x4y4=k41x1+k42x2+k43x3+k44x4\begin{array}{l} y_{1}=k_{11} x_{1}+k_{12} x_{2}+k_{13} x_{3}+k_{14} x_{4} \\ y_{2}=k_{21} x_{1}+k_{22} x_{2}+k_{23} x_{3}+k_{24} x_{4} \\ y_{3}=k_{31} x_{1}+k_{32} x_{2}+k_{33} x_{3}+k_{34} x_{4} \\ y_{4}=k_{41} x_{1}+k_{42} x_{2}+k_{43} x_{3}+k_{44} x_{4} \end{array}y1=k11x1+k12x2+k13x3+k14x4y2=k21x1+k22x2+k23x3+k24x4y3=k31x1+k32x2+k33x3+k34x4y4=k41x1+k42x2+k43x3+k44x4

某分组密码使用线性方程来定义映射当n=4时，明文分组[x1 x2 x3 x4]中的四个比特分别代入方程，得到密文分组[y1 y2 y3 y4]加密算法是四元一次方程组，而密钥是一个4行4列的矩阵，由4*4个比特构成若算法被攻击者获得，密钥很容易被分析出来

🕘 1.3 Feistel密码

理想分组密码Feistel密码分组长度n位n位分组可能2n2n密钥长度n×2nk明密变换2n!2k原理代替代替+置换\begin{array}{|c|c|c|} \hline & \text { 理想分组密码 } & \text { Fe istel密码 } \\ \hline \text { 分组长度 } & n \text { 位 } & n \text { 位 } \\ \hline \text { 分组可能 } & 2^{n} & 2^{n} \\ \hline \text { 密钥长度 } & n \times 2^{n} & k \\ \hline \text { 明密变换 } & 2^{n} ! & 2^{k} \\ \hline \text { 原理 } & \text { 代替 } & \text { 代替+置换 } \\ \hline \end{array}分组长度分组可能密钥长度明密变换原理理想分组密码n位2nn×2n2n!代替Feistel密码n位2nk2k代替+置换

🕤 1.3.1 混淆和扩散

密文PF…FA明文e…e\begin{array}{|l|l|l|l|l|l|} \hline \text { 密文 } & \text { P } & \text { F } & \ldots & \text { F } & \text { A } \\ \hline \text { 明文 } & & \text { e} & \ldots & \text { e} & \\ \hline \end{array}密文明文PFe……FeA

截获到密文，加密算法为Caesar密码攻击者拥有明文统计特征的知识，已知e使用频率最高12.7%，而该特征体现在了密文中，密文字母F出现频率最高12.7%密文字母F 对应着明文字母eCaesar密码中，明文 = 密文-密钥（mod26），

e = F – k

4 = 5 – k，推导出密钥为1

密文G…R…G明文e……e\begin{array}{|l|l|l|l|l|l|} \hline \text { 密文 } & \text { G } & \ldots & \text { R } & \ldots & \text { G } \\ \hline \text { 明文 } & \text { e} & \ldots & & \ldots & \text { e} \\ \hline \end{array}密文明文Ge……R……Ge

截获到密文，加密算法是n位密钥的Vigenere攻击者拥有明文统计特征的知识，已知e使用频率最高，而该特征体现在了密文中，在每隔n位的所有密文字母中 G出现频率最高密文字母G 对应着明文字母e

Vigenere密码中，明文值 = 密文值 – 密钥值，e = G – k，

4 = 6 – k，推导出密钥词的第一位值为2，即c

扩散

y𝟏=E(x𝟏,k)y_𝟏=E(x_𝟏,k)y1=E(x1,k)

y𝟏=E(x𝟏,x𝟐,......x𝒏,k)y_𝟏=E(x_𝟏 ,x_𝟐,...... x_𝒏,k)y1=E(x1,x2,......xn,k)

扩散是将明文的统计特征消散在密文中一个密文字母不再只取决于一个明文字母，而是被许多明文字母影响明文和密文之间的统计关系变得复杂

yn=(∑i=1km(n+i))mod26y_{n}=\left(\sum_{i=1}^{k} m_{(n+i)}\right) \bmod 26yn=(i=1∑km(n+i))mod26

用上述方法加密消息𝐌=𝒎𝟏,𝒎𝟐,….,𝒎𝒏𝐌=𝒎_𝟏,𝒎_𝟐,….,𝒎_𝒏M=m1,m2,….,mn，k=3

密文字母𝒚𝟏=(𝒎(𝟏+𝟏)+𝒎(𝟏+𝟐)+𝒎(𝟏+𝟑))𝒎𝒐𝒅𝟐𝟔𝒚_𝟏=(𝒎_{(𝟏+𝟏)}+𝒎_{(𝟏+𝟐)}+𝒎_{(𝟏+𝟑)}) 𝒎𝒐𝒅𝟐𝟔y1=(m(1+1)+m(1+2)+m(1+3))mod26

=(𝒎𝟐+𝒎𝟑+𝒎𝟒)𝒎𝒐𝒅𝟐𝟔=(𝒎_𝟐+𝒎_𝟑+𝒎_𝟒) 𝒎𝒐𝒅𝟐𝟔=(m2+m3+m4)mod26

密文字母𝒚𝟐=(𝒎(𝟐+𝟏)+𝒎(𝟐+𝟐)+𝒎(𝟐+𝟑))𝒎𝒐𝒅𝟐𝟔𝒚_𝟐=(𝒎_{(𝟐+𝟏)}+𝒎_{(𝟐+𝟐)}+𝒎_{(𝟐+𝟑)}) 𝒎𝒐𝒅𝟐𝟔y2=(m(2+1)+m(2+2)+m(2+3))mod26

=(𝒎𝟑+𝒎𝟒+𝒎𝟓)𝒎𝒐𝒅𝟐𝟔=(𝒎_𝟑+𝒎_𝟒+𝒎_𝟓) 𝒎𝒐𝒅𝟐𝟔=(m3+m4+m5)mod26

用上述方法加密消息𝒉𝒆𝒉𝒂，密钥k=2

密文字母𝒚𝟏=(𝒎(𝟏+𝟏)+𝒎(𝟏+𝟐))𝒎𝒐𝒅𝟐𝟔𝒚_𝟏=(𝒎_{(𝟏+𝟏)}+𝒎_{(𝟏+𝟐)}) 𝒎𝒐𝒅𝟐𝟔y1=(m(1+1)+m(1+2))mod26

=(𝒎𝟐+𝒎𝟑)𝒎𝒐𝒅𝟐𝟔=( 𝒎_𝟐 + 𝒎_𝟑 ) 𝒎𝒐𝒅𝟐𝟔=(m2+m3)mod26

=(𝒆+𝒉)𝒎𝒐𝒅𝟐𝟔=(𝒆+𝒉)𝒎𝒐𝒅𝟐𝟔=(e+h)mod26

=(𝟒+𝟕)𝒎𝒐𝒅𝟐𝟔=(𝟒+𝟕)𝒎𝒐𝒅𝟐𝟔=(4+7)mod26

=𝟏𝟏=𝑳

密文字母𝒚𝟑=(𝒎(𝟑+𝟏)+𝒎(𝟑+𝟐))𝒎𝒐𝒅𝟐𝟔𝒚_𝟑=(𝒎_{(𝟑+𝟏)}+𝒎_{(𝟑+𝟐)}) 𝒎𝒐𝒅𝟐𝟔y3=(m(3+1)+m(3+2))mod26

=(𝒎𝟒+𝒎𝟏)𝒎𝒐𝒅𝟐𝟔=( 𝒎_𝟒 + 𝒎_𝟏 ) 𝒎𝒐𝒅𝟐𝟔=(m4+m1)mod26

=(𝒂+𝒉)𝒎𝒐𝒅𝟐𝟔=(𝒂+𝒉)𝒎𝒐𝒅𝟐𝟔=(a+h)mod26

=(𝟐+𝟕)𝒎𝒐𝒅𝟐𝟔=(𝟐+𝟕)𝒎𝒐𝒅𝟐𝟔=(2+7)mod26

=𝟗=𝑱

同是明文字母h，加密后却生成了不同的密文字母L、J

无法再使用统计特征建立某个明文字母与某个密文字母的联系，也就无法推导出密钥

混淆

扩散：削弱了明文和密文之间的对应规律，明文的统计特征不再适用于密文，如置换混淆：削弱了密钥和密文之间的对应规律，密文的统计特征不足以推导出密钥，如代替即使攻击者拥有密文的统计特征，并建立了某密文字母L 和明文字母e 之间的映射。由于使用密钥k生成密文字母L的方法十分复杂，推导密钥k变得极其困难

多选题
以下说法正确的是？
A. 小明用明文字母累加模26的方法来得到密文，本质上是对信息做扩散处理
B. 特工设计的一款密码中，对密钥进行置换、累加再用到加密算法中，是在做混淆处理
C. 小红拿到的密码是明文四个字母为一组，进行数学运算得到一个密文字母，再做扩充，本质是对明文字母做了扩散处理
D. 某密码先选择密钥中的几位，再进行扩充和数学变换，这种处理本质上是扩散
答案：ABC

🕤 1.3.2 Feistel 密码结构

明文分组长度为2w位划分为等长的两部分：左边𝑳𝑬𝟎，右边𝑹𝑬𝟎共有16轮加密，由密钥𝑲 推导生成16个子密钥𝑲𝒊，分别作用于每一轮

将左边 𝑳𝑬𝟎与右边 𝑹𝑬𝟎互换位置，进行置换

𝑹𝑬𝟎换到左边，变为 𝑳𝑬𝟏

𝑳𝑬𝟎换到右边，但需要进行一些操作才能变为 𝑹𝑬𝟏

把 𝑹𝑬𝟎与本轮密钥𝑲𝟏输入轮函数F

将轮函数F的输出与 𝑳𝑬𝟎进行异或，得到的结果作为 𝑹𝑬𝟏

DES数据加密标准使用的就是Feistel密码结构DES 只不过是Feistel 算法的具体实现比如解决分组2w到底是多少位、密钥Ki是怎么产生的，以及使用的轮函数F是什么等等技术细节

多选题
关于Feistel加密过程，下列说法正确的有：
A. 明文分组被划分为等长的 𝑳𝑬𝟎、 𝑹𝑬𝟎
B. 它们经过一轮加密后变为 𝑹𝑬𝟏、 𝑳𝑬𝟏
C. 𝑹𝑬𝟏= 𝑳𝑬𝟎
D. 𝑳𝑬𝟏= 𝑹𝑬𝟎
答案：ABD

多选题
关于Feistel加密过程，下列说法正确的有：
A. 16轮加密一共用了16把密钥
B. 最终密文分组是𝑳𝑬𝟏𝟕、𝑹𝑬𝟏𝟕
C. 𝑳𝑬13= 𝑹𝑬12
D. 𝑹𝑬17= 𝑳𝑬16
答案：ABCD

密文分组 𝑹𝑬𝟏𝟔 𝑳𝑬𝟏𝟔

解密过程里：左边记作 𝑳𝑫𝟎= 𝑹𝑬𝟏𝟔 ；右边记作 𝑹𝑫𝟎= 𝑳𝑬𝟏𝟔

共有16轮解密，由密钥𝑲推导生成16个子密钥𝑲𝒊，分别作用于每一轮

把𝑹𝑫𝟎，也就是 𝑳𝑬𝟏𝟔换到左边，变为 𝑳𝑫𝟏

加密算法中 𝑳𝑬𝟏𝟔=𝑹𝑬𝟏𝟓，所以左边变为 𝑹𝑬𝟏𝟓

把 𝑳𝑫𝟎换到右边，但需要进行一些操作才能变为 𝑹𝑫𝟏

把 𝑹𝑫𝟎，也就是 𝑳𝑬𝟏𝟔与本轮密钥𝑲𝟏𝟔输入轮函数F

将轮函数F的输出与 𝑳𝑫𝟎 进行异或，得到的结果作为 𝑹𝑫𝟏

𝑹𝑫𝟏可证等于 𝑳𝑬𝟏𝟓

小结：

分组越长，安全性越高，但是会降低加密和解密的速度；通过扩散增加安全性；DES使用的分组长度为64bit密钥越长，安全性越高，但是会降低加密和解密的速度；通过混淆增加安全性；DES使用的密钥长度为56bit单轮不够安全，采取多层加密的思想；迭代轮数的典型值为16；轮函数F越复杂，安全性越高

重要公式

LEi=REi−1LE_i = RE_{i-1}LEi=REi−1

REi=LEi−1⊕F(REi−1,ki)RE_i = LE_{i-1}⊕F(RE_{i-1},k_i)REi=LEi−1⊕F(REi−1,ki)

LD16−i+1=RD16−i=LEi=REi−1LD_{16-i+1} = RD_{16-i} = LE_i = RE_{i-1}LD16−i+1=RD16−i=LEi=REi−1

多选题
关于Feistel解密过程，下列说法正确的有：
A. 解密过程与加密本质上相同
B. 解密输入的是密文分组与逆序密钥
C. 𝑳𝑫𝟏= 𝑹𝑫𝟎
D. 𝑹𝑫𝟎= 𝑹𝑬𝟏𝟕= 𝑳𝑬𝟏𝟔
答案：ABCD

证明：RD2=LE14RD_2 = LE_{14}RD2=LE14
解答：
16轮LEi=REi−1LE_i = RE_{i-1}LEi=REi−1
REi=LEi−1⊕F(REi−1,ki)RE_i = LE_{i-1}⊕F(RE_{i-1},k_i)REi=LEi−1⊕F(REi−1,ki)LD2=RD1=LE15=RE14LD_2 = RD_1 = LE_{15} = RE_{14}LD2=RD1=LE15=RE14
RD2=LD1⊕F(RD1,k15)RD_2 = LD_1⊕F(RD_1,k_{15})RD2=LD1⊕F(RD1,k15)
=RE15⊕F(LE15,k15)= RE_{15}⊕F(LE_{15},k_{15})=RE15⊕F(LE15,k15)
=LE14⊕F(RE14,k15)⊕F(LE15,k15)= LE_{14}⊕F(RE_{14},k_{15})⊕F(LE_{15},k_{15})=LE14⊕F(RE14,k15)⊕F(LE15,k15)
=LE14= LE_{14}=LE14

🕒 2. 数据加密标准

DES（Data Encryption Standard），即数据加密标准

它是世界上最常用的加密方案，以至于在很长一段时间内，DES就是密码生成的同义词

就像全球定位系统(Global Positioning System，GPS)，由于美国率先研制，在一段时间内，GPS定位系统也是全球定位系统的同义词

🕘 2.1 DES的加密过程

🕤 2.1.1 初始置换（IP）

64位明文分组按照置换表进行重排列，元素的位置发生改变，产生64位的输出

5850423426181026052443628462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157\begin{array}{|c|c|c|c|c|c|c|c|} \hline 58 & 50 & 42 & 34 & 26 & 18 & 10 & 2 \\ \hline 60 & 52 & 44 & 36 & 28 & 20 & 12 & 4 \\ \hline 62 & 54 & 46 & 38 & 30 & 22 & 14 & 6 \\ \hline 64 & 56 & 48 & 40 & 32 & 24 & 16 & 8 \\ \hline 57 & 49 & 41 & 33 & 25 & 17 & 9 & 1 \\ \hline 59 & 51 & 43 & 35 & 27 & 19 & 11 & 3 \\ \hline 61 & 53 & 45 & 37 & 29 & 21 & 13 & 5 \\ \hline 63 & 55 & 47 & 39 & 31 & 23 & 15 & 7 \\ \hline \end{array}5860626457596163505254564951535542444648414345473436384033353739262830322527293118241719212310121416911131524681357

练习题
经过初始置换后，输出的前8位二进制数是什么？
0000000100100011010001010110011110001001101010111100110111101111\begin{array}{|llllllll|} \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ \hline \end{array}0000111100110011010101010000000000001111001100110101010111111111
解答：
按照初始置换表顺序读，答案为 11001100

🕤 2.1.2 16轮处理

64位数据继续进行16轮处理，每轮都是相同的Feistel结构，最终产生64位输出

🕤 2.1.3 轮函数

轮函数内部又包含4种变换，分别为扩展置换、XOR、S盒置换、P盒置换

🕞 2.1.3.1 扩展置换（E）

将32位输入按扩展置换表扩展成为48位输出，使得扩展后数据长度与48位子密钥等长

32123454567898910111213121314151617161718192223242524252627282928293031321\begin{array}{|c|cccc|c|} \hline 32 & 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 6 & 7 & 8 & 9 \\ 8 & 9 & 10 & 11 & 12 & 13 \\ 12 & 13 & 14 & 15 & 16 & 17 \\ 16 & 17 & 18 & 19 & 20 & 21 \\ 20 & 21 & 22 & 23 & 24 & 25 \\ 24 & 25 & 26 & 27 & 28 & 29 \\ 28 & 29 & 30 & 31 & 32 & 1 \\ \hline \end{array}3248121620242815913172125292610141822263037111519232731481216202428325913172125291

🕞 2.1.3.2 异或XOR（⊕）

将扩展置换生成的48位输出，与48位子密钥进行按位异或XOR

🕞 2.1.3.3 S盒置换

将48位输出每6位分成一组，每一组都通过S盒置换变为了4位

6位中取第1位和第6位组成行号，剩余第2、3、4、5位组成列号

从S盒置换表中取出相应的十进制数，转化为4位二进制数

练习题
S盒的输入为111100，输出是什么？
1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613\begin{array}{|rrrrrrrrrrrrrrrr|} \hline 14 & 4 & 13 & 1 & 2 & 15 & 11 & 8 & 3 & 10 & 6 & 12 & 5 & 9 & 0 & 7 \\ 0 & 15 & 7 & 4 & 14 & 2 & 13 & 1 & 10 & 6 & 12 & 11 & 9 & 5 & 3 & 8 \\ 4 & 1 & 14 & 8 & 13 & 6 & 2 & 11 & 15 & 12 & 9 & 7 & 3 & 10 & 5 & 0 \\ 15 & 12 & 8 & 2 & 4 & 9 & 1 & 7 & 5 & 11 & 3 & 14 & 10 & 0 & 6 & 13 \\ \hline \end{array}1404154151121371481482214134152691113218111731015510612116129312117145931095100035678013
解答：
答案是0101

每个S盒的每一行都是整数0到15的一个置换改变S盒的任一输入比特，其输出至少有两比特发生改变

🕞 2.1.3.4 P盒置换

32位输出数据进行P盒置换，仍然输出为32位数据

167291228171152326518311028241432273919133062211425\begin{array}{|lccccccc|} \hline 16 & 7 & 20 & 21 & 29 & 12 & 28 & 17 \\ 1 & 15 & 23 & 26 & 5 & 18 & 31 & 10 \\ 2 & 8 & 24 & 14 & 32 & 27 & 3 & 9 \\ 19 & 13 & 30 & 6 & 22 & 11 & 4 & 25 \\ \hline \end{array}161219715813243021261462953222121827112831341710925

🕤 2.1.4 逆初始置换（IP-1）

🕤 2.1.5 密钥生成

DES 提供了64位的密钥，但实际仅用到了其中的56位。密钥扩展过程如下所示

🕞 2.1.5.1 置换选择1

给64位密钥从1到64编号，忽略每个第8位，按照置换表进行选择与重新排列，产生56位的输出

C05749413325179158504234261810259514335271911360524436D0635547393123157625446383022146615345372921135284\begin{array}{|llcccccc|} \hline C_{0} & 57 & 49 & 41 & 33 & 25 & 17 & 9 \\ & 1 & 58 & 50 & 42 & 34 & 26 & 18 \\ & 10 & 2 & 59 & 51 & 43 & 35 & 27 \\ & 19 & 11 & 3 & 60 & 52 & 44 & 36 \\ \hline D_{0} & 63 & 55 & 47 & 39 & 31 & 23 & 15 \\ & 7 & 62 & 54 & 46 & 38 & 30 & 22 \\ & 14 & 6 & 61 & 53 & 45 & 37 & 29 \\ & 21 & 13 & 5 & 28 & 20 & 12 & 4 \\ \hline \end{array}C0D057110196371421495821155626134150593475461533425160394653282534435231384520172635442330371291827361522294

🕞 2.1.5.2 循环左移

56位密钥循环左移一次，产生56位的输出

迭代次数12345678910111213141516移位次数1122222212222221\begin{array}{|l|llllllllllllllll|} \hline \text { 迭代次数 } & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline \text { 移位次数 } & \color{Red} 1 &\color{Red} 1 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 1 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 2 &\color{Red} 1 \\ \hline \end{array}迭代次数移位次数112132425262728291102112122132142152161

C0=1111000011001100101010101111D0=0101010101100110011110001111C1=1110000110011001010101011111D1=1010101011001100111100011110C2=1100001100110010101010111111D2=0101010110011001111000111101C3=0000110011001010101011111111D3=0101011001100111100011110101C4=0011001100101010101111111100D4=0101100110011110001111010101\begin{array}{l} C_{0}={\color{Red} 1111} 0000110011001010101011{\color{Red} 11} \\ D_{0}={\color{Red} 0101} 0101011001100111100011{\color{Red} 11} \\ C_{1}={\color{Red} 1110} 0001100110010101010111{\color{Red} 11} \\ D_{1}={\color{Red} 1010} 1010110011001111000111{\color{Red} 10} \\ C_{2}=1100001100110010101010111111 \\ D_{2}=0101010110011001111000111101 \\ C_{3}=0000110011001010101011111111 \\ D_{3}=0101011001100111100011110101 \\ C_{4}=0011001100101010101111111100 \\ D_{4}=0101100110011110001111010101 \end{array}C0=1111000011001100101010101111D0=0101010101100110011110001111C1=1110000110011001010101011111D1=1010101011001100111100011110C2=1100001100110010101010111111D2=0101010110011001111000111101C3=0000110011001010101011111111D3=0101011001100111100011110101C4=0011001100101010101111111100D4=0101100110011110001111010101

练习题
C4 = 0011001100101010101111111100
D4 = 0101100110011110001111010101
迭代次数123456移位次数112222\begin{array}{|l|l} \hline \text { 迭代次数 } & \text { 1 2 3 4 5 6 } \\ \hline \text { 移位次数 } & \text { 1 1 2 2 2 2 } \\ \hline \end{array}迭代次数移位次数123456112222
问：C6，D6分别为什么？
答案：
C6 = 0011001010101011111111000011
D6 = 1001100111100011110101010101

🕞 2.1.5.3 置换选择2

56位输入按照置换表进行选择与重新排列，产生48位的输出

141711241532815621102319124268167272415231374755304051453348444939563453464250362932\begin{array}{|cccccc|} \hline 14 & 17 & 11 & 24 & 1 & 5 \\ 3 & 28 & 15 & 6 & 21 & 10 \\ 23 & 19 & 12 & 4 & 26 & 8 \\ 16 & 7 & 27 & 20 & 13 & 2 \\ 41 & 52 & 31 & 37 & 47 & 55 \\ 30 & 40 & 51 & 45 & 33 & 48 \\ 44 & 49 & 39 & 56 & 34 & 53 \\ 46 & 42 & 50 & 36 & 29 & 32 \\ \hline \end{array}1432316413044461728197524049421115122731513950246420374556361212613473334295108255485332

🕒 3. DES的一个例子

明文：02468aceeca86420密钥：0f1571c947d9e859密文：da02ce3a89ecac3b\begin{array}{|l|l|} \hline \text { 明文：} & 02468aceeca86420 \\ \hline \text { 密钥： } & 0f1571c947d9e859 \\ \hline \text { 密文：} & da02ce3a89ecac3b \\ \hline \end{array}明文：密钥：密文：02468aceeca864200f1571c947d9e859da02ce3a89ecac3b

明文、密钥以及密文均为十六进制1位十六进制数表示4位二进制数明文分组、密钥、密文分组长度为16×4=64bit

🕘 3.1 结果

轮数子密钥KiLEiREiIP5a005a003cf03c0f11e030fo3080d29303cf03c0fbad2284520a31293432242318bad2284599e9b723\begin{array}{|c|c|c|c|} \hline \text { 轮数 } & \text { 子密钥 } K_{\mathrm{i}} & L E_{i} & R E_{i} \\ \hline \color{orange}IP & & 5 a 005 \mathrm{a00} &\color{green} \text { 3cf03c0f } \\ \hline 1 & 1 \mathrm{e} 030 \mathrm{fo3080d2930} &\color{green} \text { 3cf03c0f } &\color{Red} \text { bad22845 } \\ \hline 2 & 0 a 31293432242318 &\color{Red} \text { bad22845 } & 99 \mathrm{e} 9 \mathrm{b} 723 \\ \hline \end{array}轮数IP12子密钥Ki1e030fo3080d29300a31293432242318LEi5a005a003cf03c0fbad22845REi3cf03c0fbad2284599e9b723

明文分组首先进行一次初始置换IP

将新产生的明文分组划分为等长的两部分，记作 𝑳𝑬𝟎、 𝑹𝑬𝟎

第一轮的子密钥𝑲𝟏

将明文分组 𝑳𝑬𝟎、 𝑹𝑬𝟎进行第一轮的处理， 𝑹𝑬𝟎可以直接换到左边变为 𝑳𝑬𝟏； 𝑳𝑬𝟎要经过一系列处理之后才可以变成 𝑹𝑬𝟏

第二轮的子密钥𝑲𝟐

将分组 𝑳𝑬𝟏、 𝑹𝑬𝟏进行第二轮的处理， 𝑹𝑬𝟏可以直接换到左边变为 𝑳𝑬𝟐； 𝑳𝑬𝟏要经过一系列处理之后才可以变成 𝑹𝑬𝟐

轮数子密钥KiLEiREiIP5a005a003cf03c0f11e030fo3080d29303cf03c0fbad2284520a31293432242318bad2284599e9b723…………162921080b1314302575e8fd8f25896490322589649075e8fd8fIP−1da02ce3a89ecac3b\begin{array}{|c|c|c|c|} \hline \text { 轮数 } & \text { 子密钥 } K_{\mathrm{i}} & L E_{i} & R E_{i} \\ \hline I P & & 5 a 005 \mathrm{a00} & \text { 3cf03c0f } \\ \hline 1 & 1 \mathrm{e} 030 \mathrm{fo3080d2930} & \text { 3cf03c0f } & \text { bad22845 } \\ \hline 2 & 0 a 31293432242318 & \text { bad22845 } & 99 \mathrm{e} 9 \mathrm{b} 723 \\ \hline \ldots & \ldots & \ldots & \ldots \\ \hline 16 & 2921080 \mathrm{b} 13143025 &\color{Red} 75 \mathrm{e} 8 \mathrm{fd} 8 \mathrm{f} &\color{Red} 25896490 \\ \hline 32 & &\color{Red} 25896490 &\color{Red} 75 \mathrm{e} 8 \mathrm{fd8f} \\ \hline \color{Red} IP^{-1} & &\color{Red} \text { da02ce3a } &\color{Red} 89 \mathrm{ecac3b} \\ \hline \end{array}轮数IP12…1632IP−1子密钥Ki1e030fo3080d29300a31293432242318…2921080b13143025LEi5a005a003cf03c0fbad22845…75e8fd8f25896490da02ce3aREi3cf03c0fbad2284599e9b723…2589649075e8fd8f89ecac3b

🕘 3.2 雪崩效应

若明文或者密钥的某一位发生变化，密文某几位随之变化，攻击者就可以缩小明文或者密钥的可能范围我们希望明文或密钥的微小改变能够对密文产生非常大的影响，增大了攻击明文或密钥的难度当明文分组的第4位改变，十六进制0对应的二进制0000变成了0001明文分组从024…变成了124…两个相差1位的明文分组，在经过第一轮加密后，产生了两个不同的密文分组密文分组只有1位不同它们在经过第二轮加密后，产生的密文分组出现了5位不同在经过短短三轮加密后，密文分组已经达到了18位的差异全部16轮加密完成后，两组密文相差32位明文保持不变，使用的密钥仅在第4位有差异经过几轮加密后也出现了雪崩效应，最终生成的密文也有一半左右的差异

🕘 3.3 练习题

本题给出了用一轮 DES 加密具体数值的例子。假设明文和密钥 K 有着相同的位模式。

用十六进制表示： 0123456789ABCDEF\quad \text{0 1 2 3 4 5 6 7 8 9 A B C D E F}0123456789ABCDEF

用二进制表示： 00000001001000110100010101100111\quad 0000 \ 0001 \ 0010 \ 0011 \ 0100 \ 0101 \ 0110 \ 011100000001001000110100010101100111

10001001101010111100110111101111\hspace{2.45cm}1000 \ 1001 \ 1010 \ 1011 \ 1100 \ 1101 \ 1110 \ 111110001001101010111100110111101111

a. 推导第一轮的子密钥 K1K_{1}K1 。

b. 推导 L0L_{0}L0 和 R0R_{0}R0 。

c. 扩展 R0R_{0}R0 得到 E[R0]E\left[R_{0}\right]E[R0] , 其中 E[⋅]E[\cdot]E[⋅] 是 2.1.3.4小节的 P盒置换（即扩展函数）。

d. 计算 A=E[R0]⊕K1A=E\left[R_{0}\right] \oplus K_{1}A=E[R0]⊕K1 。

e. 把 d\mathrm{d}d 问中的 48 位结果分成 6 位（数据）一组的集合并求对应 S\mathrm{S}S 盒代替的值。

f. 级联 e\mathrm{e}e 问中的结果得到一个 32 位的结果 BBB 。

g. 应用置换获得 P(B)P(B)P(B) 。

h. 计算 R1=P(B)⊕L0R_{1}=P(B) \oplus L_{0}R1=P(B)⊕L0 。

i. 写出密文。

解答：

置换选择1：

C01111000011001100101010100000D01010101011001100111100000000\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_{0} & 1111 & 0000 & 1100 & 1100 & 1010 & 1010 & 0000 \\ \hline D_{0} & 1010 & 1010 & 1100 & 1100 & 1111 & 0000 & 0000 \\ \hline \end{array}C0D011111010000010101100110011001100101011111010000000000000

循环左移1位：

C11110000110011001010101000001D10101010110011001111000000001\begin{array}{|c|c|c|c|c|c|c|c|} \hline C_{1} & 1110 & 0001 & 1001 & 1001 & 0101 & 0100 & 0001 \\ \hline D_{1} & 0101 & 0101 & 1001 & 1001 & 1110 & 0000 & 0001 \\ \hline \end{array}C1D111100101000101011001100110011001010111100100000000010001

置换选择2：

K1：000010110000001001100111100110110100100110100101\begin{array}{|c|c|c|c|c|c|} \hline 0000 & 1011 & 0000 & 0010 & 0110 & 0111 \\ \hline 1001 & 1011 & 0100 & 1001 & 1010 & 0101 \\ \hline \end{array}000010011011101100000100001010010110101001110101

二进制：0000101100000010011001111001101101001001101001010000 \ 1011 \ 0000 \ 0010 \ 0110 \ 0111 \ 1001 \ 1011 \ 0100 \ 1001 \ 1010 \ 0101000010110000001001100111100110110100100110100101

十六进制：0B02679B49A50 \ \mathrm{B} \ 0 \ 2 \ 6 \ 7 \ 9 \ \mathrm{B} \ 4 \ 9 \ \mathrm{A} \ 50B02679B49A5

按初始置换表顺序：

L011001100000000001100110011111111R011110000101010101111000010101010\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline L_{0} & 1100 & 1100 & 0000 & 0000 & 1100 & 1100 & 1111 & 1111 \\ \hline R_{0} & 1111 & 0000 & 1010 & 1010 & 1111 & 0000 & 1010 & 1010 \\ \hline \end{array}L0R01100111111000000000010100000101011001111110000001111101011111010

扩展置换表：

E(R0)：011110100001010101010101011110100001010101010101\begin{array}{|c|c|c|c|} \hline 011110 & 100001 & 010101 & 010101 \\ \hline 011110 & 100001 & 010101 & 010101 \\ \hline \end{array}011110011110100001100001010101010101010101010101

A：011100010001011100110010111000010101110011110000\begin{array}{|c|c|c|c|} \hline 011100 & 010001 & 011100 & 110010 \\ \hline 111000 &010101 & 110011 & 110000 \\ \hline \end{array}011100111000010001010101011100110011110010110000

S100(1110)=S10(14)=0(十进制)=0000(二进制)S201(1110)=S21(14)=12(十进制)=1100(二进制)S300(1110)=S30(14)=2(十进制)=0010(二进制)S410(1110)=S42(14)=1(十进制)=0001(二进制)S510(1110)=S52(14)=6(十进制)=0110(二进制)S601(1110)=S61(14)=13(十进制)=1101(二进制)S711(1110)=S73(14)=5(十进制)=0101(二进制)S810(1110)=S82(14)=0(十进制)=0000(二进制)\mathrm{S}_{1}{} ^{00}(1110)=\mathrm{S}_{1}{ }^{0}(14)=0 \ ( 十进制 )=0000 (二进制) \\ \mathrm{S}_{2}{ }^{01}(1110)=\mathrm{S}_{2}{ }^{1}(14)=12( 十进制 )=1100 (二进制) \\ \mathrm{S}_{3}{ }^{00}(1110)=\mathrm{S}_{3}{ }^{0}(14)=2 \ ( 十进制 )=0010 (二进制) \\ \mathrm{S}_{4}{ }^{10}(1110)=\mathrm{S}_{4}{ }^{2}(14)=1 \ ( 十进制 )=0001 (二进制) \\ \mathrm{S}_{5}{ }^{10}(1110)=\mathrm{S}_{5}{ }^{2}(14)=6 \ ( 十进制 )=0110 (二进制) \\ S_{6}{ }^{01}(1110)=S_{6}{ }^{1}(14)=13( 十进制 )=1101 (二进制) \\ \mathrm{S}_{7}{}^{11}(1110)=\mathrm{S}_{7}{}^{3}(14)=5 \ ( 十进制 )=0101 (二进制 ) \\ \mathrm{S}_{8}{ }^{10}(1110)=\mathrm{S}_{8}{ }^{2}(14)=0 \ ( 十进制 )=0000 (二进制)S100(1110)=S10(14)=0(十进制)=0000(二进制)S201(1110)=S21(14)=12(十进制)=1100(二进制)S300(1110)=S30(14)=2(十进制)=0010(二进制)S410(1110)=S42(14)=1(十进制)=0001(二进制)S510(1110)=S52(14)=6(十进制)=0110(二进制)S601(1110)=S61(14)=13(十进制)=1101(二进制)S711(1110)=S73(14)=5(十进制)=0101(二进制)S810(1110)=S82(14)=0(十进制)=0000(二进制)

B=00001100001000010110110101010000\mathrm{B} = 0000 \ 1100 \ 0010 \ 0001 \ 0110 \ 1101 \ 0101 \ 0000B=00001100001000010110110101010000

P盒置换表

P(B)=10010010000111000010000010011100\mathrm{P(B)} = 1001 \ 0010 \ 0001 \ 1100 \ 0010 \ 0000 \ 1001 \ 1100P(B)=10010010000111000010000010011100

R1=01011110000111001110110001100011\mathrm{R_1} = 0101 \ 1110 \ 0001 \ 1100 \ 1110 \ 1100 \ 0110 \ 0011R1=01011110000111001110110001100011

L1=R0\mathrm{L_1 = R_0}L1=R0 ，密文为L1\mathrm{L_1}L1和R1\mathrm{R_1}R1连接起来，即

1111 0000 1010 1010 1111 0000 1010 1010

0101 1110 0001 1100 1110 1100 0110 0011

🕒 4. DES的强度

DES 密钥长度56位，共𝟐𝟓𝟔≈𝟕.𝟐×𝟏𝟎𝟏𝟔种可能，若对密钥发起穷举攻击，至少也要尝试一半的次数当时有人提出制造一台专门用于加密的并行计算机，带有100万个加密器，每个加密器耗时1ms，穷举时间大约10个小时随着多核处理技术的迅猛发展，一台现代多核英特尔处理器的加密速度约为每秒5亿次

更有超级计算机可以达到每秒𝟏𝟎𝟏𝟑次今天的超级计算机只需一个小时就可以穷举攻击找出DES加密的56位密钥

表穷尽密钥搜索所需的平均时间

密钥大小/位密码密钥个数每微秒执行1次解密的时间每微秒执行1000万次解密的时间56DES256≈7.2×1016255ns=1.125年1小时128AES2128≈3.4×10382127ns=5.3×105.3×101683DES2168≈3.7×10502167ns=5.8×1033年5.8×1029年192AES2192≈6.3×10572191ns=9.8×1040年9.8×1036年256AES2256≈1.2×10772255ns=1.8×1060年1.8×1056年26个字符的排列组合单字母代替2!=4×10262×1026ns=6.3×109年6.3×106年\begin{array}{c|c|c|c|c} \hline \text { 密钥大小/位 } & \text { 密码 } & \text { 密钥个数 } & \text { 每微秒执行 } 1 \text { 次解密的时间 } & \text { 每微秒执行 } 1000 \text { 万次解密的时间 } \\ \hline 56 & \text { DES } & 2^{56} \approx 7.2 \times 10^{16} & 2^{55} \mathrm{~ns}=1.125 \text { 年 } & \color{red}1 \text { 小时 } \\ \hline 128 & \text { AES } & 2^{128} \approx 3.4 \times 10^{38} & 2^{127} \mathrm{~ns}=5.3 \times 10^{21} \text { 年 } & 5.3 \times 10^{17} \text { 年 } \\ \hline 168 & 3 \mathrm{DES} & 2^{168} \approx 3.7 \times 10^{50} & 2^{167} \mathrm{~ns}=5.8 \times 10^{33} \text { 年 } & 5.8 \times 10^{29} \text { 年 } \\ \hline 192 & \mathrm{AES} & 2^{192} \approx 6.3 \times 10^{57} & 2^{191} \mathrm{~ns}=9.8 \times 10^{40} \text { 年 } & 9.8 \times 10^{36} \text { 年 } \\ \hline 256 & \mathrm{AES} & 2^{256} \approx 1.2 \times 10^{77} & 2^{255} \mathrm{~ns}=1.8 \times 10^{60} \text { 年 } & 1.8 \times 10^{56} \text { 年 } \\ \hline 26 \text { 个字符的排列组合 } & \text { 单字母代替 } & 2 !=4 \times 10^{26} & 2 \times 10^{26} \mathrm{~ns}=6.3 \times 10^{9} \text { 年 } & 6.3 \times 10^{6} \text { 年 } \\ \hline \end{array}密钥大小/位5612816819225626个字符的排列组合密码DESAES3DESAESAES单字母代替密钥个数256≈7.2×10162128≈3.4×10382168≈3.7×10502192≈6.3×10572256≈1.2×10772!=4×1026每微秒执行1次解密的时间255ns=1.125年2127ns=5.3×102167ns=5.8×1033年2191ns=9.8×1040年2255ns=1.8×1060年2×1026ns=6.3×109年每微秒执行1000万次解密的时间1小时5.3×105.8×1029年9.8×1036年1.8×1056年6.3×106年