密码算法详解——DES

男娘i 2022-10-02 11:57 364阅读 0赞

转载自：[https://www.cnblogs.com/luop/p/4366902.html][https_www.cnblogs.com_luop_p_4366902.html]

# 0 DES简介 #

在20世纪60年代后期，IBM公司成立了一个由Horst Feistel负责的计算机密码学研究项目。1971年设计出密码算法LUCIFER后，该项目宣告结束。LUCIFER被卖给了伦敦的Lloyd公司，用在同样由IBM公司开发的现金发放系统上。LUCIFER是分组长度为64位、密钥长度为128位、具有**Feistel结构**的分组密码算法。因为LUCIFER非常成功，IBM决定开发一个适合于芯片实现的商业密码产品。这一次由Walter Tuchman和Carl Meyer牵头，参与者不仅有IBM公司的研究人员，而且还有美国国家安全局（NSA）的技术顾问。这次努力的结果是给出了LUCIFER的一个修订版，它的抗密码分析能力更强，而且密钥长度减小为56位。

1973年，美国国家标准局（NBS）征求美国国家密码标准方案时，IBM将Tuchman-Meyer方案提交给NBS，它是所有应征方案中最好的一个，所以1977年NBS将它采纳为数据加密标准，即DES。

以上内容直接来自与参考文献\[1\]，参考文献[\[2\]][2]给出了更加详细的一些介绍，有兴趣可以阅读。

# 1 Feistel #

分组密码常用的结构有SP、Feistel[\[3\]][3]、Lai-Massey、MISTY等，其中Feistel结构的使用较为普遍，不仅DES用到了，后续的很多经典算法中都有涉及，故在此先对其进行介绍。

## 1.1 Feistel介绍 ##

![271214183498525.png][]

Feistel是以发明者Horst Feistel的名字命名的。加解密的原理如右图1，左边表示的加密过程，右边表示解密过程。

在每一轮加密过程中，明文被分成左右两部分。

加密和解密公式如下：

![271344204275857.png][]

不同的是，在加密过程中，轮数和轮密钥从小开始递增；解密时正好相反，从最大开始递减。

从图中可以看出，加密最后一轮的操作与前面的有所不同，最后一轮得到的两个部分没有交换，之所以这样是为了保持解密的流程和加密一致，这样在硬件设计时可以使用相同的结构，进而减少硬件面积。

但是对于Feistel结构最本质的特点到底是什么，我也一直不太明白，比较浅显的一点认识就是：每一轮只有一半的比特位参与计算，另外一半直接作为下一轮的输入。

## 1.2 一个简单的例子 ##

假设明文为（L0,R0），一共有两轮计算，每轮的密钥分别为k0、k1，加解密的流程如图2。

![271501068491712.png][]

# 2 算法流程 #

![271852338649140.png][]

DES算法原理如右图，相关参数如下：

*   *  明文分组长度：64 bits
     *  密钥长度：64 bits
     *  轮数：16轮

整个操作可以分为3部分：

*   *  **初始置换和逆初始置换**：这是一对可逆操作，一组数字经过初始置换（或逆初始置换）后，再经过逆初始置换（或初始置换）即可恢复原来的值；
     *  **每轮的加解密操作**：64位明文和48为密钥经过一定的操作，输出64位密文；
     *  **轮密钥计算**：64位初始密钥经过置换、循环移位等得到16轮的密钥，每轮密钥长度为48位。

接下来分别对这三种核心操作进行介绍。

## 2.1 初始置换与逆初始置换 ##

置换的操作如下表1、表2，将一个64位的输入通过各位的提到得到一个新的64位输出。观察可以发现x = IP-1 ( IP(x) ) = IP ( IP-1(x) )。

需要注意的一点是，图中的索引值从1开始（下文中的数字也类似），有些资料中是从0开始的，如果从零开始，则所有的数字减1即可。

![272039170832860.png][]

## 2.2 每轮的操作 ##

每一轮的流程如图4，从图中可以看出DES用到了Feistel结构。F即为图中虚线框的内容。

![272040401455637.png][]

图4 轮操作流程

每一轮主要涉及3中操作：

*   *  扩展/置换：将32位输入扩展成48位输出，如表3；
     *  S盒：将48位输入分成8组分别作为8个S盒的输入，每组6位，最高位和最低位作为行索引，中间4位作为列索引，得到一个值x（0<=x<=15），表示为二进制即为4位，8个S盒的输出和在一起正好32位。表4是S1的数值；
     *  置换：对32位输入进行位的变化，输出仍为32位，如表5。

![272036080528076.png][]

## 2.3 轮密钥扩展 ##

从图1和图4中可以得出，密钥扩展流程可以表示如下：

1) 64位初始密钥P进行置换选择1，得到56位输出K；

2) 将K循环左移一定位数，再进行置换选择2得到48位输出k1(即第一轮的密钥)；

3) 循环步骤2)，直至得到16轮的密钥（k1、k2、……、k16）；

4) 结束。

置换选择1、置换选择2和左移次数的值分别如表6、表7、表8。

![272033120991788.png][]

# 3 其它密码算法 #

近期介绍了DES、AES和Simon3种密码算法，他们都属于分组密码算法，后续有时间再介绍其它分组密码算法、流密码算法、杂凑函数（Hash算法）等。读者有兴趣可以参考《密码学与网络安全——原理与实践》以及网上相关资料，算法原理基本都差不多。

# 4 参考资料 #

\[1\] William Stallings著；王张宜等译. 密码编码学与网络安全——原理与实践（第五版）\[M\]. 北京：电子工业出版社，2012.1.

\[2\] http://en.wikipedia.org/wiki/Data\_Encryption\_Standard

\[3\] http://en.wikipedia.org/wiki/Feistel\_cipher

\[4\] https://github.com/tarequeh/DES

[https_www.cnblogs.com_luop_p_4366902.html]: https://www.cnblogs.com/luop/p/4366902.html
[2]: http://en.wikipedia.org/wiki/Data_Encryption_Standard
[3]: http://en.wikipedia.org/wiki/Feistel_cipher
[271214183498525.png]: /images/20220112/4ca7e4b1243a434aac4dcf86cf4967e9.png
[271344204275857.png]: /images/20220112/9a2195011d924e2db4ba5b3cd7d97db5.png
[271501068491712.png]: /images/20220112/576a85d4a9d54d61b74ca3dc9672fa03.png
[271852338649140.png]: /images/20220112/3a3ceb61543b442da30d4bea9e231908.png
[272039170832860.png]: /images/20220112/8423d900eb8844c796d7be8e248fc627.png
[272040401455637.png]: /images/20220112/994beff8a6e143fc820978483897070c.png
[272036080528076.png]: /images/20220112/31b24b6633cd45938957dd261acfa88a.png
[272033120991788.png]: /images/20220112/eb8e3e9edac54a47a004fad14ddee525.png