信息安全密码学：DES算法的核心 E盒、S盒、P盒

2023-11-08

加密密钥等于脱密密钥，或者由一个可以轻易的计算出另一个的密码体制，称为单密钥密码体制，亦或称为对称密码体制或传统密码体制。其最具代表意义的当然属于DES密码体制了。

1、DES的设计背景

1973年5月 NBS(美国国家标准局)发布通告，征集一种加密算法
1974年8月收到了IBM公司提交的算法
1976年11月被推荐为联邦标准
1977年1月发布
服役了20年

2、DES加密算法

迭代型分组算法分组长度 / 密钥长度： 64 b i t 有效密钥长度： 56 b i t ( 8 b i t 奇偶校验位 ) 迭代圈数： 16 圈圈密钥长度： 48 b i t ( 即 16 圈中每一圈所要用到的密钥位数 ( b i t ) ) \color{red}迭代型分组算法\\\;\\\color{brown}分组长度/密钥长度：\color{red}64bit\\ \color{brown}有效密钥长度：\color{red}56bit(8bit奇偶校验位)\\ \color{brown}迭代圈数：\color{red}16圈\\ \color{brown}圈密钥长度：\color{red}48bit(即16圈中每一圈所要用到的密钥位数(bit)) 迭代型分组算法分组长度/密钥长度：64bit有效密钥长度：56bit(8bit奇偶校验位)迭代圈数：16圈圈密钥长度：48bit(即16圈中每一圈所要用到的密钥位数(bit))

形式化表达为： D E S ( M ) = I P − 1 ∘ T ( 16 ) ∘ T ( 15 ) ∘ . . . ∘ T ( 1 ) ∘ I P ( m ) （由后向前运算） DES(M)=IP^{-1}\circ T(16)\circ T(15)\circ...\circ T(1)\circ IP(m)（由后向前运算） DES(M)=IP−1∘T(16)∘T(15)∘...∘T(1)∘IP(m)（由后向前运算）
IP是初始置换，IP^-1是初始逆置换，T表示16组迭代圈函数。

图形化表达：

前 15 圈的算法结构相同， 16 圈中每一圈都有不同的密钥值 \color{gray}前15圈的算法结构相同，16圈中每一圈都有不同的密钥值前15圈的算法结构相同，16圈中每一圈都有不同的密钥值

由上图可知，前 15 圈模 2 加（亦或）后，左右进行了互换，而在第 16 圈则没有。初始置换后，将 64 b i t 数据等分为 2 份 32 b i t 分别给予了 L 0 （ L e f t ）和 R 0 （ R i g h t ）由上图可知，前15圈模2加（亦或）后，左右进行了互换，而在第16圈则没有。\\ 初始置换后，将64bit数据等分为2份32bit 分别给予了L_0（Left）和 R_0（Right）由上图可知，前15圈模2加（亦或）后，左右进行了互换，而在第16圈则没有。初始置换后，将64bit数据等分为2份32bit分别给予了L0（Left）和R0（Right）

2.1 初始置换 I P 与逆初始置换 I P − 1 2.1\;初始置换IP与逆初始置换IP^{-1} 2.1初始置换IP与逆初始置换IP−1

若某一位经过初始置换又经过了逆初始置换，则其位置并没有发生改变。即，IP和IP^-1互逆

如IP转换表中，第8位对应了数字2，即表示对应着第2位；
而在IP^-1转换表中，第二位对应了数字8，即表示对应着第8位；
此时正好又将位置转换了回去。之前有提到过置换是一种古典密码 \color{gray}之前有提到过置换是一种古典密码之前有提到过置换是一种古典密码置换密码.
所以在设计置换表时可以参照此原则。

2.2 圈函数 2.2\;圈函数 2.2圈函数

前15圈

右上角的 L i − 1 L_{i-1} Li−1应该是 R i − 1 R_{i-1} Ri−1

本一圈的右部 R i − 1 R_{i-1} Ri−1 直接作为下一圈的左部 L i L_{i} Li 进行后续的运算

本一圈的（左部 L i − 1 L_{i-1} Li−1）要与（经过 f 函数 f函数 f函数的 R i − 1 R_{i-1} Ri−1 和本圈密钥 k i k_{i} ki 所得到的结果， f ( R i − 1 , k i ) f(R_{i-1},k_{i}) f(Ri−1,ki)）进行模二加（亦或）运算之后作为下一圈的右部 R i R_{i} Ri 进行后续的运算

表达式为： ( 左部，右部 ) = ( L i , R i ) = ( R i , L i − 1 ⨁ f ( R i − 1 , k i ) ) ⨁ 模 2 加： 0 + 0 = 0 ； 0 + 1 = 1 + 0 = 1 ； 1 + 1 = 0 f ( R i − 1 , k i ) : 表示在密钥 k i 的影响下 R i − 1 的值。 \:\\\color {red}表达式为：(左部，右部)=(L_{i},R_{i})=(R_{i},L_{i-1} \bigoplus f(R_{i-1},k_{i}))\\\;\\\color{blue}\bigoplus 模2加：0+0=0；0+1=1+0=1；1+1=0\\f(R_{i-1},k_{i}):表示在密钥k_i的影响下R_{i-1}的值。表达式为：(左部，右部)=(Li,Ri)=(Ri,Li−1⨁f(Ri−1,ki))⨁模2加：0+0=0；0+1=1+0=1；1+1=0f(Ri−1,ki):表示在密钥ki的影响下Ri−1的值。

第16圈

( 左部，右部 ) = ( L 16 , R 16 ) = ( L 15 − 1 ⨁ f ( k 16 , R 15 − 1 ) , R 15 ) \color{red}(左部，右部)=(L_{16},R_{16})=(L_{15-1} \bigoplus f(k_{16},R_{15-1}),R_{15}) (左部，右部)=(L16,R16)=(L15−1⨁f(k16,R15−1),R15)
\;
同前15圈相比，其左右部，一定意义上讲，没有发生交换。

这里的 k i 是由 64 b i t 密钥产生的子密钥， k i 是 48 b i t 。 D E S 的核心在于 f ( R i − 1 , k i ) 函数的功能。 f 函数是将 32 b i t 的输入转化为 32 b i t 的输出。其中涉及到了扩展和压缩。扩展是为了能和 k i 进行模 2 加，压缩是为了最后要输出 32 b i t \color{gray}这里的k_i是由64bit密钥产生的子密钥，k_i是48bit。\\ {\color{red}DES的核心在于f(R_{i-1},k_{i})函数的功能。}f函数是将32bit的输入转化为32bit的输出。\\ 其中涉及到了扩展和压缩。扩展是为了能和k_i进行模2加，压缩是为了最后要输出32bit 这里的ki是由64bit密钥产生的子密钥，ki是48bit。DES的核心在于f(Ri−1,ki)函数的功能。f函数是将32bit的输入转化为32bit的输出。其中涉及到了扩展和压缩。扩展是为了能和ki进行模2加，压缩是为了最后要输出32bit

2.3 f 函数的构造 2.3\:f函数的构造 2.3f函数的构造

f 函数的内部构造 : E 盒扩展； E 盒扩展后的值与圈密钥 k 进行模 2 加；（亦或运算） S 盒转换；（分为 8 个部分） P 盒变换； \color{gray}f函数的内部构造:\\\color{blue}\;E盒扩展；\\E盒扩展后的值与圈密钥k进行模2加；（亦或运算）\\\;S盒转换；（分为8个部分）\\\;P盒变换； f函数的内部构造:E盒扩展；E盒扩展后的值与圈密钥k进行模2加；（亦或运算）S盒转换；（分为8个部分）P盒变换；
图形化表示：图形化表示：图形化表示：

E 盒扩展： \color{blue}E盒扩展： E盒扩展：

将32bit扩展到48bit，先将32bit的字符分为8组，每一组的前后，分别添加上一个字符和下一个字符：
将 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . . . . 29 30 31 32 ⟹ 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 . . . . . . . . . . . . 28 29 30 31 32 1 将 \begin{matrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 &11 & 12 \\ 13 & 14 &15 & 16 \\ &...... \\ 29 & 30 &31 & 32 \\ \end{matrix} \implies \begin{matrix} {\color{red}32} & 1 & 2 & 3 & 4 & {\color{red}5}\\ {\color{red}4} & 5 & 6 & 7 & 8 & {\color{red}9} \\ {\color{red}8} & 9 & 10 &11 & 12 & {\color{red}13} \\ {\color{red}12} & 13 & 14 &15 & 16 & {\color{red}17} \\ {\color{red}...} & &...... & &&{\color{red}...}\\ {\color{red}28} & 29 & 30 &31 & 32 & {\color{red}1} \\ \end{matrix} 将1591329261014......303711153148121632⟹324812...281591329261014......303711153148121632591317...1
如，在下标为 1 的字符前插入上一个字符。即，下标为 32 的字符；在下标为 4 的字符后插入下一个字符。即，下标为 5 的字符；在下标为 32 的字符后插入下一个字符。即，下标为 1 的字符；按照此规律扩展 16 b i t 。如，\\\color{blue}在下标为1的字符前插入上一个字符。即，下标为32的字符；\\在下标为4的字符后插入下一个字符。即，下标为5的字符；\\在下标为32的字符后插入下一个字符。即，下标为1的字符；\\按照此规律扩展16bit。如，在下标为1的字符前插入上一个字符。即，下标为32的字符；在下标为4的字符后插入下一个字符。即，下标为5的字符；在下标为32的字符后插入下一个字符。即，下标为1的字符；按照此规律扩展16bit。

模 2 加 \color{blue}模2加模2加

就令经过E盒扩展后的48个2进制位逐一与密钥的48bit进行亦或运算。

S 盒代替 \color{blue}S盒代替 S盒代替

将48bit转换为32bit

S 盒是唯一的非线性变换（非数学变换），其是 D E S 中 f 函数的核心， S 盒的好坏决定了该算法。 S盒是唯一的非线性变换（非数学变换），其是DES中f函数的核心，S盒的好坏决定了该算法。 S盒是唯一的非线性变换（非数学变换），其是DES中f函数的核心，S盒的好坏决定了该算法。

该 S 盒分为了 8 个子盒，对应着 8 张表 ( S i ) ，每个表是 4 行 16 列，每个子盒的输入为 6 b i t ，输出为 4 b i t 该S盒分为了8个子盒，对应着8张表(S_i)，每个表是4行16列，每个子盒的输入为6bit，输出为4bit 该S盒分为了8个子盒，对应着8张表(Si)，每个表是4行16列，每个子盒的输入为6bit，输出为4bit

先将输入的48bit分为8组6bit的数据对应于8个子盒，
假定输入 S i 盒的 6 个 b i t 为 b 1 b 2 b 3 b 4 b 5 b 6 （这里每一个 b 都是一个二进制位）另 b 1 b 6 为十进制的 n ，令 b 2 b 3 b 4 b 5 为十进制的 m ，在设计的表中找出对应的 n 行 m 列对应的数字，并转换为 2 进制作为本 s i 盒的输出下面有栗子：假定输入S_i盒的6个bit为b_1b_2b_3b_4b_5b_6（这里每一个b都是一个二进制位）\\另b_1b_6为十进制的n，令b_2b_3b_4b_5为十进制的m，\\在设计的表中找出对应的n行m列对应的数字，并转换为2进制作为本s_i盒的输出\\{\color{red}下面有栗子：} 假定输入Si盒的6个bit为b1b2b3b4b5b6（这里每一个b都是一个二进制位）另b1b6为十进制的n，令b2b3b4b5为十进制的m，在设计的表中找出对应的n行m列对应的数字，并转换为2进制作为本si盒的输出下面有栗子：

栗子：如，向 s 1 盒中输入的 6 b i t 数为： 101101 b 1 b 6 为 11 ，即十进制的 3 b 2 b 3 b 4 b 5 为 0110 ，即十进制的 6 在 s 1 中，第 3 行 6 列对应着数字 1 所以最后的输出为 0001 8 组中每一个都会得到 4 b i t 的数据，最终会得到 32 b i t 的数据 {\color{red}栗子：}如，向s_1盒中输入的6bit数为：101101\\b_1b_6为11，即十进制的3\\b_2b_3b_4b_5为0110，即十进制的6\\在s_1中，第3行6列对应着数字1\\所以最后的输出为0001\\{\color{gray}8组中每一个都会得到4bit的数据，最终会得到32bit的数据} 栗子：如，向s1盒中输入的6bit数为：101101b1b6为11，即十进制的3b2b3b4b5为0110，即十进制的6在s1中，第3行6列对应着数字1所以最后的输出为00018组中每一个都会得到4bit的数据，最终会得到32bit的数据
S 盒作为 D E S 的心脏， D E S 靠它实现非线性变换 \color{red}S盒作为DES的心脏，DES靠它实现非线性变换 S盒作为DES的心脏，DES靠它实现非线性变换

P 盒转换 : \color{blue}P盒转换: P盒转换:

其本质是一种置换
\;
如原来的第1个bit被置换到第16个bit
该表格满足分组扩散与混乱原则。

3、密钥生成算法

加密的基本流程已经介绍完毕，那么如何将64bit的初始密钥生成16组48bit的圈密钥（子密钥）供每一圈使用呢？

图形化表达为：图形化表达为：图形化表达为：

P C − 1 为，置换选择算法 1 （由 64 位筛选出 56 位）； \color{blue}{\color{red}PC-1}为，置换选择算法1（由64位筛选出56位）； PC−1为，置换选择算法1（由64位筛选出56位）；
C 和 D 是两个寄存器； \color{blue}{\color{red}C和D}是两个寄存器； C和D是两个寄存器；
L S 为移位运算（循环左移） \color{blue}{\color{red}LS}为移位运算（循环左移） LS为移位运算（循环左移）
P C − 2 为，置换选择算法 2 （由 58 位选出 48 位的圈密钥） \color{blue}{\color{red}PC-2}为，置换选择算法2（由58位选出48位的圈密钥） PC−2为，置换选择算法2（由58位选出48位的圈密钥）

置换选择 1 （ P C − 1 ） \color{blue}置换选择1（PC-1）置换选择1（PC−1）

抛去每个字节的最高位，即，第8，16，24，32，40，48，56，64位，只选择剩余的56位，被抛去的字节本来就是奇偶校验位。（用于验证完整性）
将剩余的比特数，按照一定的规则，进行相应的置换。
置换后，分别放在两个寄存器C和D中

置换规则：

如，将原来的第57bit换到第1位。置换后的前28bit放在C寄存器中，其余的放在D寄存器中。

移位（ L S ）【两个 28 位密钥的寄存器循环左移】 \color{blue}移位（LS）【两个28位密钥的寄存器循环左移】移位（LS）【两个28位密钥的寄存器循环左移】

规则：第 1 ， 2 ， 9 ， 16 圈左移 1 位；其余都左移 2 位。 {\color{red}规则：}\\第1，2，9，16圈左移1位；\\其余都左移2位。规则：第1，2，9，16圈左移1位；其余都左移2位。

L S 1 、 L S 2 、 L S 9 、 L S 16 左移 1 位，其余 L S i 左移 2 位 LS_1、LS_2、LS_9、LS_{16} 左移1位，其余LS_i左移2位 LS1、LS2、LS9、LS16左移1位，其余LSi左移2位

最后 16 圈左移结束后，移位数正好等于 28 \color{gray}最后16圈左移结束后，移位数正好等于28 最后16圈左移结束后，移位数正好等于28

置换选择（ P C − 2 ）【由 56 位得到 48 位】 \color{blue}置换选择（PC-2）【由56位得到48位】置换选择（PC−2）【由56位得到48位】

按照此规则进行置换，同时去除了8位

4、脱密算法

DES的解密过程和DES加密完全类似，只不过将16圈的子密钥序列颠倒了一下，即，第一圈用 k 16 k_{16} k16 最后一圈用 k 1 k_{1} k1。
形式化表达为： D E S − 1 = I P − 1 ∘ T ( 1 ) ∘ T ( 2 ) ∘ . . . ∘ T ( 16 ) ∘ I P ( c ) （由后向前运算）形式化表达为：\\\color{red}DES^{-1}=IP^{-1}\circ T(1)\circ T(2)\circ...\circ T(16)\circ IP(c) （由后向前运算）形式化表达为：DES−1=IP−1∘T(1)∘T(2)∘...∘T(16)∘IP(c)（由后向前运算）

所以脱密的算法就在于圈密钥如何进行计算的

圈函数的分解： \color{blue}圈函数的分解：圈函数的分解：

一般地，圈函数可以表达为： ( 左，右 ) = ( x , y ) = ( y , x ⨁ f ( y , k ) ) (左，右)=(x,y)=(y,x\bigoplus f(y,k)) (左，右)=(x,y)=(y,x⨁f(y,k))，第16圈显然不能用这个表示。
可将其看作两部分，

( x , y ) → ( x ⨁ f ( y , k ) ， y ) (x,y)\to(x\bigoplus f(y,k)，y) (x,y)→(x⨁f(y,k)，y)，称为对合交换1。（Fesihel函数）
( x ⨁ f ( y , k ) ， y ) → ( y , x ⨁ f ( y , k ) ) (x\bigoplus f(y,k)，y)\to(y,x\bigoplus f(y,k)) (x⨁f(y,k)，y)→(y,x⨁f(y,k))，称为对合变换2。（左右块交换）【显然，第16圈并没有进行这一步骤】

步骤一样，为了方便表示，我们将圈迭代看成 3 圈，最后一圈同第 16 圈一样 , 仅有对合变换 1 \color{gray}步骤一样，为了方便表示，我们将圈迭代看成3圈，最后一圈同第16圈一样,仅有对合变换1 步骤一样，为了方便表示，我们将圈迭代看成3圈，最后一圈同第16圈一样,仅有对合变换1

可知，将 C 解密为 M 的过程为 M 加密为 C 的逆过程 \color{gray}可知，将C解密为M的过程为M加密为C的逆过程可知，将C解密为M的过程为M加密为C的逆过程

将此 3 圈扩展为 16 圈即为 D E S 的脱密过程 \color{blue}将此3圈扩展为16圈即为DES的脱密过程将此3圈扩展为16圈即为DES的脱密过程

总结

最后附带一张手绘总结图 \color{red}最后附带一张手绘总结图最后附带一张手绘总结图
在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)