密码学基础——DES算法

        前面的密码学基础——密码学文章中介绍了密码学相关的概念，其中简要地对称密码体制(也叫单钥密码体制、秘密密钥体制）进行了解释，我们可以知道单钥体制的加密密钥和解密密钥相同，单钥密码分为流密码和分组密码。

• 流密码（或序列密码，Stream Cipher）：对明文消息按字符(如二元数字)逐位地进行加密。
• 分组密码（Block Cipher）：将明文消息分组(含有多个字符)，逐组地进行加密。

        那么本文要介绍的DES算法属于分组密码。

一、基础知识    

        在介绍DES算法之前，我们需要知道几个概念：

        1.代换

        2.扩散和混淆

        3.Feistel加密结构

1.代换

在前一篇介绍密码学基础——古典密码学的文章已经初步介绍了代换和置换的概念：

代换（替代）：将明文中的每个字符替换为另一个字符，形成密文。

置换（换位）：不改变明文中的字符，而是通过重新排列字符的位置来形成密文。

在 DES 中，代换主要通过 S 盒（Substitution Box）来实现。

 

2.扩散和混淆

（1）扩散

         定义：扩散是指将明文的统计特性散布到密文中去，使得明文的每一位影响密文中的许多位，从而使密文的统计特性与明文的统计特性无关。实现方式是使得密文中每一位由明文中多位产生。

        实现方式：在 DES 中，通过多次迭代的置换和异或操作来实现扩散。例如，在每一轮迭代中，数据会经过置换操作，将不同位置的比特进行交换，使得明文的影响逐渐扩散到整个密文。

（2）混淆

         定义：混淆是指将密钥和明文之间的关系变得复杂，使得从密文和密钥中难以推出明文的统计特性。

        实现方式：DES 通过 S 盒的非线性代换以及密钥与数据的混合操作来实现混淆。S 盒的非线性特性使得输入和输出之间的关系非常复杂，难以通过分析输出得到输入的信息。同时，密钥与数据的异或操作也增加了密钥和明文之间的混淆程度。

 

3.Feistel 加密结构

        Feistel 结构是一种分组密码的设计结构，由 Horst Feistel 提出。DES 采用了 Feistel 结构。

(1)结构原理

加密算法       

        加密算法的输入是分组长为2w的明文和一个密钥K。将长度为2w位的明文分组分成左右两个w位的子块，分别记为L0​和R0​，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。

        在进行第i轮迭代时，其计算方式为：

Li​=Ri−1​，

Ri​=Li−1​⊕F(Ri−1​,Ki​)

        其中F是轮函数，Ki​是第i轮的子密钥。一般，各轮子密钥彼此不同而且与K也不同。经过多轮迭代后，再将最后一轮得到的左右子块进行交换，得到密文。

 Feistel网络中每轮结构都相同，每轮中右半数据被作用于轮函数F后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。

每轮轮函数的结构都相同，但以不同的子密钥K作为参数。代换过程完成后，再交换左、右两半数据，这一过程称为置换。

解密算法

        解密算法每轮的左右两半用LEi 和 REi表示。

(2)轮函数F

        轮函数F是 Feistel 结构的核心组件，它通常包含了代换、置换、密钥混合等操作。通过这些操作，对输入的数据进行非线性变换，从而实现混淆和扩散的效果。不同的分组密码算法在轮函数的具体设计上会有所不同，但目的都是为了增加密码的安全性。

(3)密钥生成与使用

        在 Feistel 结构中，密钥通常会被扩展成多个子密钥，分别用于每一轮的迭代运算。密钥扩展算法的设计需要保证子密钥的安全性和独立性，以防止攻击者通过分析子密钥来破解密码。例如，在 DES 算法中，56 位的密钥会被扩展成 16 个 48 位的子密钥，用于 16 轮的迭代。

 

二、DES加密算法

        数据加密标准（Data Encryption Standard，DES）是IBM公司于1970年研制的DES (Data Encryption Standard)算法。该算法每隔五年由美国国家保密局（NSA—National Security Agency）作出评估，并重新批准它是否继续作为联邦加密标准。最后一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。

算法概述

        明文分组长度为64比特，密钥长度为56比特，生成 64 位的密文分组。16轮迭代

        如下图为DES加密算法框图，输入64bit明文数据，64bit密钥，其中8 位用于奇偶校验，实际有效密钥长度为 56 位。将64bit明文数据经过初始置换IP，再经过16轮迭代，每轮中都有置换和代换运算，第16轮变换的输出分为左右两半，并被交换次序。最后再经过一个逆初始置换IP-1（为IP的逆）从而产生64比特的密文。

        除初始置换IP和逆初始置换IP-1外，DES的结构和前面的的Feistel密码结构完全相同。

加密过程

1.初始置换（IP）

        将 64 位的明文按照特定的置换表进行位置置换，得到初始置换后的结果。

        DES的置换表如下：

2.轮函数（Feistel 结构） 

        DES 的轮函数采用 Feistel 结构，如下图为DES加密算法的轮结构。

        先看左侧将 64 bit的中间数据分为左右两个 32 bit的子块，记为记为L和R。在第i轮迭代时:

Li​=Ri−1​，

Ri​=Li−1​⊕F(Ri−1​,Ki​)

轮密钥 为48比特。

轮函数F的具体操作包括：

1. 将轮输入的右半部分R进行扩展置换（E表），从 32 位扩展到 48 位；
2. 然后与 48 位的子密钥K进行异或运算；
3. 接着将结果通过 8 个 S 盒进行代换，将 48 位数据压缩回 32 位；
4. 最后进行 P 盒置换。

 F 中的代换由8个S盒组成，每个S盒的输入长为6比特、输出长为4比特，其变换关系如下表所示，每个S盒给出了4个代换（由一个表的4行给出）

3.密钥生成

首先，将 64 位的密钥（其中包含 8 位奇偶校验位）经过置换选择 1（PC - 1），得到 56 位的密钥。

然后，将这 56 位密钥分为两部分，每部分 28 位，进行循环左移操作，移位的位数根据轮数而定。

（c）左循环移位位数

最后，经过置换选择 2（PC - 2），从 56 位密钥中选出 48 位作为每轮的子密钥，共生成 16 个子密钥，用于 16 轮的加密运算。

解密过程

        DES 的解密过程与加密过程基本相同，只是子密钥的使用顺序相反。首先对密文进行初始置换，然后按照逆序使用 16 个子密钥进行 16 轮的轮函数运算，最后进行逆初始置换得到明文。

DES系统的保密性主要取决于什么？

密钥的安全性。穷举法破解

安全性

DES的56位密钥可能太小

DES的迭代次数可能太少（16次恰巧能抵抗差分分析）