一文了解现代密码学里程碑事件——DES

前言：

密码学（Cryptography）大致可分为古典密码学（Classic cryptography）和现代密码学（Modern cryptography），两者的主要差别在于计算机的使用，一般来说，古典密码学是基于字符的，而现代密码学是基于二进制位的。

本篇文章主要对现代密码学DES算法进行分析。DES 算法是一种常见的分组加密算法，由IBM公司在1971年提出。DES 算法是分组加密算法的典型代表，同时也是应用最为广泛的对称加密算法。

三大里程碑事件，奠定现代密码学基础

现代密码学具有三大里程碑事件，奠定了现代密码学的基础。

密码学发展史上的第一座里程碑性事件是划时代的内部报告《A Mathematical Theory of Cryptography（密码的一个数学理论）》的发表。1945年9月1日，Claude Elwood Shannon（克劳德•艾尔伍德•香农）完成了划时代的内部报告《A Mathematical Theory of Cryptography（密码的一个数学理论）》

1949年10月，该报告以《Communication Theory of Secrecy Systems（保密系统的通信理论）》为题在 Bell System Technical Journal（贝尔系统技术期刊）上正式发表。这篇论文首次将密码学和信息论联系到一起，为对称密码技术提供了数学基础。这也标志着近现代密码学的正式建立。

密码学发展史上的第二个里程碑性事件是DES的出现。DES全称为Data Encryption Standard，即数据加密标准，是一种使用密钥加密的分组密码算法，1977年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），并授权在非密级政府通信中使用，随后该算法在国际上广泛流传开来。

密码学发展史上的第三个里程碑性事件就是我们区块链中广泛应用的公钥密码，也就是非对称密码算法的出现。1976年11月，Whitfield Diffie 和 Martin E.Hellman 在 IEEE Transactions on Information Theory 上发表了论文《New Directions in Cryptography（密码学的新方向）》，探讨了无需传输密钥的保密通信和签名认证体系问题，正式开创了现代公钥密码学体系的研究。

在公钥密码发现以前，如果需要保密通信，通信双方事先要对加解密的算法以及要使用的密钥进行协商，包括送鸡毛信，实际上是在传送密钥。但自从有了公钥密码，需要进行秘密通信的双方不再需要进行事前的密钥协商了。公钥密码在理论上是不保密的，在实际上是保密的。也就是说，公钥密码是可以破解的，但需要极长的时间，等到破解了，这个秘密也没有保密的必要了。

DES算法

DES算法是一种常见的分组加密算法，由IBM公司在1971年提出。DES算法是分组加密算法的典型代表，同时也是应用最为广泛的对称加密算法。

部分名词解释如下：

明文

明文是指没有经过加密的数据。一般而言，明文都是等待传输的数据。由于没有经过加密，明文很容易被识别与破解，因此在传输明文之前必须进行加密处理。

密文

密文只是明文经过某种加密算法而得到的数据，通常密文的形式复杂难以识别及理解。

密钥

密钥是一种参数，它是在明文转换为密文或将密文转换为明文的算法中输入的参数。

对称加密

通信双方同时掌握一个密钥，加密解密都是由一个密钥完成的（即加密密钥等于解密密钥，加解密密钥可以相互推导出来）。双方通信前共同拟定一个密钥，不对第三方公开。

分组密码

分组密码是将明文分成固定长度的组，每一组都采用同一密钥和算法进行加密，输出也是固定长度的密文。

DES算法的主要流程如下两图所示，本文按照流程依次介绍每个模块。

IP置换

表中的数字代表原数据位置，即原数据块的第58位放到新数据的第1位，第50位放到第2位，依此类推，第7位放到第64位。置换后的数据分为L0和R0两部分，L0为新数据的左32位，R0为新数据的右32位。

密钥置换

a) DES的密钥由64位减至56位，每个字节的第8位作为奇偶校验位。产生的56位密钥由下表生成，然后根据选择置换PC-1将这56位分成两块C0(28位)和D0(28位);

b) 将C0和D0进行循环左移变化(注：每轮循环左移的位数由轮数决定)，变换后生成C1和D1，然后C1和D1合并，并通过选择置换生成子密钥K1(48位)；

c) C1和D1再次经过循环左移变换，生成C2和D2，然后C2和D2合并，通过选择置换生成密钥K2(48位)；

d) 以此类推，得到K16(48位)。但是最后一轮的左右两部分不交换，而是直接合并在一起R16L16，作为逆置换的输入块。其中循环左移的位数一共是循环左移16次，其中第一次、第二次、第九次、第十六次是循环左移一位，其他都是左移两位。

扩展置换E

右半部分Ri的位数为32位，而密钥长度Ki为48位，为了能够保证Ri与Ki可以进行异或运算需要对Ri位数进行扩展，用于扩展置换表E如下：

扩展置换表E：

S-盒代替

Rn扩展置换之后与子秘钥Kn异或以后的结果作为输入块进行S盒代替运算，功能是把48位数据变为32位数据。

代替运算由8个不同的代替盒(S盒)完成。每个S-盒有6位输入，4位输出。

所以48位的输入块被分成8个6位的分组，每一个分组对应一个S-盒代替操作。

经过S-盒代替，形成8个4位分组结果。

每一个S-盒的输入数据是64位，输出数据是4位，但是每个S-盒自身是64位。

S盒的计算规则：

例如：若S-盒1的输入为110111，第一位与最后一位构成11，十进制值为3，则对应第3行，中间4位为1011对应的十进制值为11，则对应第11列。查找S-盒1表的值为14，则S-盒1的输出为1110。8个S盒将输入的48位数据输出为32位数据。

P-盒代替

S-盒代替运算，每一盒得到4位，8盒共得到32位输出。这32位输出作为P盒置换的输入块。

P盒置换将每一位输入位映射到输出位。任何一位都不能被映射两次，也不能被略去。

经过P-盒置换的结果与最初64位分组的左半部分异或，然后左右两部分交换，开始下一轮迭代。

P-盒置换表(表示数据的位置)共32位。

逆IP置换

将初始置换进行16次的迭代，即进行16层的加密变换，得到L16和R16，将此作为输入块，进行逆置换得到最终的密文输出块。逆置换是初始置换的逆运算。

DES加密算法为最为常见的分组加密算法。其主要思想在于数据位的置换与移位过程，通过16次的迭代加密与最终的逆置换得出最终的密文。DES 的解密方式只需按照加密的逆过程求解即可。

由于DES加密过程的算法是公开的，所以密钥K的保密就显得尤为重要，只有发送方与接收方采用相同的密钥进行加密解密才能获取明文数据。

Reference

[1] https://en.wikipedia.org/wiki/Data_Encryption_Standard

[2] https://www.cxyxiaowu.com/1478.html

[3] https://blog.csdn.net/qq_27570955/article/details/52442092

[4] https://www.cnblogs.com/songwenlong/p/5944139.html