密码算法原理与实现：DES加密算法

亦凉 2022-12-02 13:59 564阅读 0赞

> 本文转自网络文章，内容均为非盈利，版权归原作者所有。  
> 转载此文章仅为个人收藏，分享知识，如有侵权，马上删除。
> 
> 原文作者：QiuJYu  
> 原文地址：[密码学基础：DES加密算法][DES]

**目录**

基础部分概述：

第一节：DES算法简介

第二节：DES算法原理

DES算法的Feistel框架：

DES算法的加密流程：

DES算法中的初始置换

DES算法中的LR分组：

DES算法中的F函数：

扩展置换E：

S盒置换：

P置换：

DES算法中的循环以及逆初始值置换：

DES算法的密钥生成算法：

密钥生成算法PC-1置换

密钥生成算法分组以及左移处理

密钥生成算法PC-2置换

DES算法的解密方法：

基础部分总结：

进阶部分概述：

优化一：将S盒和P置换表进行合并

第一步：优化S盒

第二步：合并S盒与P置换表

优化二：通过位运算替代初始置换

D3DES中相关代码：

代码块图解：

代码实现

--------------------

# 基础部分概述： #

>  *  **本节目的：**这一章作为DES算法的基础部分，目的主要是整理下密码学中DES加密与解密的相关知识点，并把它们整理出来，同时还有一些不懂之处希望得到解答，后续会跟上相应的答案。
>  *  **阅读方法：**希望大家在浏览完本章文章后可以自己去实现一下，相信一定会对你的编程技术有所提高。(附件中提供参考代码)
>  *  **具备基础：**  
>     (1)熟练掌握C语言
>  *  **学习环境：**任意C语言开发环境，一个正确的DES算法程序(方便调试，验证程序结果)

--------------------

# 第一节：DES算法简介 #

DES的英文全称是Data Encryption Standard，意思是数据加密标准。而我们本篇文章讨论的是DES的加密算法。希望大家能够将这两个名词区别开来，很多时候我们说的DES都是在指DES算法，而不是DES数据加密标准。DES算法是一种典型的分组密码，即将固定长度的明文通过一系列复杂的操作变成同样长度密文的算法。也就是运行一次DES算法只能对64位长度的数据进行加密操作，这样做的缺点就是如果处理大量数据就会花费相当长的时间，所以DES算法也就不适合对大数据进行处理。DES在现代密码学中属于对称加密算法，即该算法能够使用相同的密钥进行加密和解密。  
　　DES算法在设计中使用了分组密码设计的两个原则：混淆和扩散，混淆是使密文的统计特性与密钥的取值之间的关系尽可能复杂化，以使密钥和明文以及密文之间的依赖性对密码分析者来说是无法利用的。扩散的作用就是将每一位明文的影响尽可能迅速地作用到较多的输出密文位中，以便在大量的密文中消除明文的统计结构，并且使每一位密钥的影响尽可能迅速地扩展到较多的密文位中，以防对密钥进行逐段破译。主要目的就是增加数据被破解的难度，造成雪崩效应，即在输入时即使发生了微小的变化都会对结果产生不可分辨性的变化。

# 第二节：DES算法原理 #

DES算法使用的是Feistel框架，Feistel框架的密码结构是用于分组密码中的一种对称结构，Feistel框架使用的是对同一处理流程进行多次循环的方式。DES算法就是采用的16轮循环的加密，当然循环次数越多加密的效果越好，同时时间成本也会上去，设计者需要考虑这两方面的因素进行密码设计。因为这个框架是用于处理分组密码的，我们就要了解一下什么是分组密码，分组密码是一种加解密方案，将输入的明文分组当作一个整体处理，并输出一个等长的密文分组，典型的分组大小为64位和128位，随着对加密算法安全性能的要求不断提高，分组大小也就会越来越大。DES算法所采用的分组大小为64位分组，所以输入的数据和密钥都是按照64位进行处理的，输出的密文也是64位一组。

## DES算法的Feistel框架： ##

![DES的Feistel框架][DES_Feistel]

## DES算法的加密流程： ##

1.  将输入的明文进行初始置换。
2.  将初始置换后的结果按照每组32位数据分成L、R两组。
3.  将48位子密钥k\[i\]和32位R\[i\]组数据输入F函数进行处理，输出32位处理结果。
4.  将32位F函数处理结果与32位的L\[i\]组数据按位进行异或操作。
5.  将32位的异或处理结果赋值给R\[i+1\]分组，将32位的R\[i\]分组数据赋值给L\[i+1\]。  
    L\[i+1\] = R\[i\],  
    R\[i+1\] = L\[i\]^(F(k\[i\], R\[i\]))
6.  对3、4、5步处理进行16次循环，得到L\[16\]，R\[16\]。
7.  将L\[16\]、R\[16\]数据进行交叉合并得到64位数据。
8.  对得到的64位数据进行逆初始值置换，得到想要的密文Y。

(从这里大家也可以看出来，在进行最后一轮循环时R\[15\]被赋值给L\[16\]，L\[15\]经过一系列运算后结果赋值给了R\[16\]，这里进行了一次交换，而在逆初始值置换之前又进行了一次交换，相当于没有变化。这里其实是为了保持16轮循环处理的过程一致，方便学习。如果大家觉得需要优化下，完全可以将R\[15\]直接赋值给R\[16\],L\[15\]经过一系列运算后结果赋值给L\[16\]，这是完全没有问题的。)

## DES算法中的初始置换 ##

置换处理：在密码学中置换是指在保持数据不变的情况下，打乱数据的位置顺序的操作称作置换，在DES算法中每个置换处理都会按照 相应的置换表进行操作，置换处理在DES算法中得到了充分的运用，通过置换处理可以打乱输入数据的顺序，使输入的数据变得面目全非，当然也会造成雪崩效应，因为只要有一个数据位发生变化，就会影响到很多地方。

**初始置换表：**  
![初始置换表][format_png]  
　　这个初始置换表怎么使用呢？如何通过该表进行DES初始置换呢？  
　　首先我们就要把明文的64位数据按照从左到右，从上到下进行排列，形成一个8\*8的矩阵。我们以初始置换表的第0行第0列为例进行讲解，在初始置换表中该位置的数值是58，我们就要将数据中的第58个Bit位移动到第一个Bit位上，这就完成了一次置换。因为这个表的大小有64位，所以就要进行64次置换才会得出结果。

**图示：**  
![置换图解][format_png 1]

**代码演示：**

const unsigned char IP_Table[64] =
    {
        58, 50, 42, 34, 26, 18, 10, 2,
        60, 52, 44, 36, 28, 20, 12, 4,
        62, 54, 46, 38, 30, 22, 14, 6,
        64, 56, 48, 40, 32, 24, 16, 8,
        57, 49, 41, 33, 25, 17,  9, 1,
        59, 51, 43, 35, 27, 19, 11, 3,
        61, 53, 45, 37, 29, 21, 13, 5,
        63, 55, 47, 39, 31, 23, 15, 7
    };
     
    int IP_Substitution(const unsigned char* BitPlain, unsigned char* Bit_IP_Table)
    {
        int ret = 0;
     
        for (int i = 0; i < 64; i++)
        {
            Bit_IP_Table[i] = BitPlain[IP_Table[i] - 1];
        }
     
        return ret;
    }

## DES算法中的LR分组： ##

从表面上看，这里就是将上面置换后的结果进行分组，每组32位数据。实际上这里是有一个坑的，因为从字面意思上理解他是要将8\*8矩阵的数据分成左右两组，也就是左边4列为L组，右边数据为R组。但是实际上网上的DES加密工具所进行的分组不是这样子的，如果按照左右分组，最终得到的结果也就和网上加密工具的结果不一致，同样也就无法解密数据。所以我们这里就使用前后分组来进行处理，将前32为数据分给L组，后32位数据分给R组，保持最后的结果一致。

**分组图示：**  
![DES算法的分组方式][DES 1]

**理论分组代码演示：**

int Create_LR_Group(const unsigned char *Bit_IP_Table, unsigned char *BitL_Table, unsigned char*BitR_Table)
    {
     
        for (int i = 0; i < 8; i++)
        {
            //左半边拷贝
            memcpy(&BitL_Table[i * 4], &Bit_IP_Table[i * 8], 4);
     
            //右半边拷贝
            memcpy(&BitR_Table[i * 4], &Bit_IP_Table[i * 8 + 4], 4);
        }
     
        return 0;
    }

**实际分组代码演示：**

unsigned char Bit_IP_Table[64];      //初始置换后的明文表
    unsigned char BitL_Table[17][32];    //L表Bit组
    unsigned char BitR_Table[17][32];    //R表Bit组
     
    memcpy(BitL_Table[0], Bit_IP_Table,         32);
    memcpy(BitR_Table[0], &Bit_IP_Table[32],    32);

## DES算法中的F函数： ##

在DES算法中F函数蕴含了DES算法的主要操作，也是该算法中最重要的地方。从DES算法的Feistel框架图中，我们可以清楚的看到F函数有两个输入，一个是右分组的32位数据，另一个是子密钥的48位数据，这两个长度不同的数据是怎样进行处理的呢？这里我们就先来看看它的处理流程图吧：  
![F函数处理流程图][F]

**F函数处理流程：**

1.  将输入的32位R组数据进行扩展置换，生成48位的数据。
2.  将置换后的48位结果与输入的48位子密钥进行异或运算，得到48位的运算结果。
3.  将48位运算结果分成8组，每组6Bit数据，按照组号对应相应的S盒，进行8个S盒置换，生成8个4Bit的数据。
4.  将这8个4Bit数据合并，得到一个32位数据。
5.  将32位进行置换P就得到最后的32位处理结果。

这里看起来比较复杂我们接下来就把赋值的问题简单化，对他进行逐个击破。我们就从上往下进行分析:

### 扩展置换E： ###

在扩展置换上面，我们发现了一个F函数的输入数据——32位的右分组R\[i-1\]。在它经过扩展置换后数据长度就变成48位了，到底发生了什么样的变化呢？我们之前说过置换不会改变数据的内容，只会改变数据的顺序，至于是什么样的顺序就要通过置换表了解了。现在就上扩展置换表：  
![扩展置换表E][E]  
　　从扩展置换表中我们可以看出如果把扩展的结果当作6\*8的数据矩阵，其中中间的四列是R组的32位原始数据，两边的两列就是扩展的重复数据，通过这种扩展就可以完美的将32位数据变成48位数据。该置换的主要目的是在加密数据的过程中制造一些雪崩效应，使用数据块中的1位将在下一步操作中影响更多位，从而产生扩散效果。

**代码演示：**

//扩展置换E表     f函数内
    const unsigned char E_Table[48] =
    {
        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
    };
     
    int E_Substitution(const unsigned char* BitR_Table, unsigned char* BitE_Table)
    {
        int ret = 0;
     
        for (int i = 0; i < 48; i++)
        {
            BitE_Table[i] = BitR_Table[E_Table[i] - 1];
        }
     
        return ret;
    }

### S盒置换： ###

S盒置换是F函数中最重要的处理，也是最麻烦的处理了。在置换开始前，需要将异或运算的结果进行分组，从前往后分组即可，每组6Bit数据，分成8组。然后对每组进行分别处理，将前6Bit数据组编为1组，第7-12Bit数据编为2组，直到将最后6Bit数据编为8组。每一个组对应一个S盒表，第1组对应S1盒，第2组对应S2表，最后一组对应S8盒(这里说的S盒是一种特殊的置换表)。我们从F函数流程图可以看出，每一组数据在经过S盒置换后都会从6Bit数据变成了4Bit数据，它的置换过程比较特殊，所以我们先来观察下这8个S盒表的内容吧：  
![S盒][S]  
　　通过观察S盒我们发现，每一个S盒都是一个4\*16矩阵，而且每个S盒中的内容都是可以用4个Bit为来表示的，嘿嘿这里就和输出的4Bit数据扯上关系了。接下来我们就来看看每一组6Bit数据是如何定位其对应的S盒数据的，我们这里把每组数据的第一个Bit为称作最重要位(MSB)，把每组数据的最后一个Bit位称作最不重要位(LSB)，之所以怎么取名是和他们的权重有关，第一位的权重最高，最后一位的权重最低。我们把每组数据的最重要位和最不重要位进行组合，形成一个2个Bit位的数据，这个数据表示对应S盒的行号。将中间四位数据进行组合形成一个4个Bit位的数据，这个数据表示对应S盒的列号。

**定位S盒数据图解：**  
![定位S盒数据图解][S 1]  
　　在定位了S盒位置后，就可以取得对应位置的数据，该数据是一个整数，我们必须把这个整数转换成4个二进制数据(转换方法见文末)，这样就会得到这一组6Bit数据在经过S盒置换后的4Bit结果。因为一共由8组数据需要进行S盒置换，所以将所有4Bit数据合并后就会得到一个32位Bit数据。合并的方法和分组时的方法类似。

**代码演示：**

//S盒置换  f函数内
    const unsigned char S_Table[8][4][16] =
    {
        //S1盒
        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,
     
        //S2盒
        15, 1,  8,  14, 6,  11, 3,  4,  9,  7,  2,  13, 12, 0,  5,  10,
        3,  13, 4,  7,  15, 2,  8,  14, 12, 0,  1,  10, 6,  9,  11, 5,
        0,  14, 7,  11, 10, 4,  13, 1,  5,  8,  12, 6,  9,  3,  2,  15,
        13, 8,  10, 1,  3,  15, 4,  2,  11, 6,  7,  12, 0,  5,  14, 9,
     
        //S3盒
        10, 0,  9,  14, 6,  3,  15, 5,  1,  13, 12, 7,  11, 4,  2,  8,
        13, 7,  0,  9,  3,  4,  6,  10, 2,  8,  5,  14, 12, 11, 15, 1,
        13, 6,  4,  9,  8,  15, 3,  0,  11, 1,  2,  12, 5,  10, 14, 7,
        1,  10, 13, 0,  6,  9,  8,  7,  4,  15, 14, 3,  11, 5,  2,  12,
     
        //S4盒
        7,  13, 14, 3,  0,  6,  9,  10, 1,  2,  8,  5,  11, 12, 4,  15,
        13, 8,  11, 5,  6,  15, 0,  3,  4,  7,  2,  12, 1,  10, 14, 9,
        10, 6,  9,  0,  12, 11, 7,  13, 15, 1,  3,  14, 5,  2,  8,  4,
        3,  15, 0,  6,  10, 1,  13, 8,  9,  4,  5,  11, 12, 7,  2,  14,
     
        //S5盒
        2,  12, 4,  1,  7,  10, 11, 6,  8,  5,  3,  15, 13, 0,  14, 9,
        14, 11, 2,  12, 4,  7,  13, 1,  5,  0,  15, 10, 3,  9,  8,  6,
        4,  2,  1,  11, 10, 13, 7,  8,  15, 9,  12, 5,  6,  3,  0,  14,
        11, 8,  12, 7,  1,  14, 2,  13, 6,  15, 0,  9,  10, 4,  5,  3,
     
        //S6盒
        12, 1,  10, 15, 9,  2,  6,  8,  0,  13, 3,  4,  14, 7,  5,  11,
        10, 15, 4,  2,  7,  12, 9,  5,  6,  1,  13, 14, 0,  11, 3,  8,
        9,  14, 15, 5,  2,  8,  12, 3,  7,  0,  4,  10, 1,  13, 11, 6,
        4,  3,  2,  12, 9,  5,  15, 10, 11, 14, 1,  7,  6,  0,  8,  13,
     
        //S7盒
        4,  11, 2,  14, 15, 0,  8,  13, 3,  12, 9,  7,  5,  10, 6,  1,
        13, 0,  11, 7,  4,  9,  1,  10, 14, 3,  5,  12, 2,  15, 8,  6,
        1,  4,  11, 13, 12, 3,  7,  14, 10, 15, 6,  8,  0,  5,  9,  2,
        6,  11, 13, 8,  1,  4,  10, 7,  9,  5,  0,  15, 14, 2,  3,  12,
     
        //S8盒
        13, 2,  8,  4,  6,  15, 11, 1,  10, 9,  3,  14, 5,  0,  12, 7,
        1,  15, 13, 8,  10, 3,  7,  4,  12, 5,  6,  11, 0,  14, 9,  2,
        7,  11, 4,  1,  9,  12, 14, 2,  0,  6,  10, 13, 15, 3,  5,  8,
        2,  1,  14, 7,  4,  10, 8,  13, 15, 12, 9,  0,  3,  5,  6,  11
    };
     
     
    unsigned char Bit_Xor[8][6];          //存放异或运算的结果
    unsigned char Bit_Integer[8][4];      //将整数变成Bit位
    unsigned char Row;                    //S盒的行号
    unsigned char Col;                    //S盒的列号
    unsigned char Integer;                //从S盒中取得的32位整数
     
    for (int i = 0; i < 8; i++)
    {
        //计算S盒的行号和列号
        Row = (Bit_Xor[i][0] << 1) + Bit_Xor[i][5];
        Col = (Bit_Xor[i][1] << 3) + (Bit_Xor[i][2] << 2) + (Bit_Xor[i][3] << 1) + Bit_Xor[i][4];
     
        //从S盒中取得整数
        Integer = S_Table[i][Row][Col];
     
        //将取得的4Bit数转换成Bit组
        for (int j = 0; j < 4; j++)
        {
            Bit_Integer[i][j] = Integer >> (3 - j) & 1;
        }
    }

### P置换： ###

**P置换和初始IP置换类似，只是打乱数据的位置，因此这里就不过多叙述，直接上图和置换代码：**  
![P置换表][P]

**代码演示：**

const unsigned char P_Table[32] =
    {
        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
    };
     
    int P_Substitution(const unsigned char *Bit_Integer, unsigned char* BitP_Table)
    {
        int ret = 0;
     
        for (int i = 0; i < 32; i++)
        {
            BitP_Table[i] = Bit_Integer[P_Table[i] - 1];
        }
     
        return ret;
    }

F函数介绍完毕！

## DES算法中的循环以及逆初始值置换： ##

当R组数据经F函数处理后，接下来的过程就非常简单了，我们就在这里简单的介绍下。用F函数输出的32位数据与L\[i\]组数据进行按位异或运算，得到32位的运算结果，最后把这个处理结果赋值给R\[i+1\]，R\[i\]组32位数据原封不动的赋值给L\[i+1\]。至此就完成的DES算法的一轮操作。当经过16轮一样的处理后就会得到最后一组数据L\[16\]、R\[16\]。对应的公式为:

R[i+1] = L[i] ^ F(R[i], K[i]);
    L[i+1] = R[i];

**代码演示：**

for (int i = 0; i < 16; i++)
    {
        //将R组和子密钥组进行F函数运算
        DES_F_Function(BitR_Table[i], BitSubKey[i], Bit_F_Out);
     
        //L组盒F函数的输出结果进行异或运算
        DES_XOR(BitL_Table[i], Bit_F_Out, BitR_Table[i + 1], 32);
     
        //Li+1 = Ri
        memcpy(BitL_Table[i + 1], BitR_Table[i], 32);
    }
     
    //L[16]和R[16]进行交叉合并
    memcpy(BitRL_Table,         BitR_Table[16], 32);
    memcpy(&BitRL_Table[32],    BitL_Table[16], 32);

最后就需要将L\[16\]、R\[16\]，这两个分组的数据进行交叉合并，也就是将R\[16\]作为的前32位数据，将L\[16\]作为后32位数据，合并后就会得到一个64位数据。最后就是将这64位数据进行逆初始值置换处理，处理方式和初始值置换类似不过多叙述，直接上逆初始值置换表和对应的代码：  
![逆初始值置换表][format_png 2]

**代码演示：**

const unsigned char reIP_Table[64] =
    {
        40, 8, 48, 16, 56, 24, 64, 32,
        39, 7, 47, 15, 55, 23, 63, 31,
        38, 6, 46, 14, 54, 22, 62, 30,
        37, 5, 45, 13, 53, 21, 61, 29,
        36, 4, 44, 12, 52, 20, 60, 28,
        35, 3, 43, 11, 51, 19, 59, 27,
        34, 2, 42, 10, 50, 18, 58, 26,
        33, 1, 41,  9, 49, 17, 57, 25
    };
     
    int reIP_Substitution(const unsigned char *BitRL_Table, unsigned char *Bit_reIP_Table)
    {
        int ret = 0;
     
        for (int i = 0; i < 64; i++)
        {
            Bit_reIP_Table[i] = BitRL_Table[reIP_Table[i] - 1];
        }
     
        return ret;
    }

至此这64位数据经过逆初始值置换就和得到密文的二进制形式，最后就需要将这些二进制数据转换成16进制数据后输出就是最后想要的密文信息了。DES算法加密部分介绍完毕！

--------------------

## DES算法的密钥生成算法： ##

我想大家应该都注意到了把，在DES算法的循环处理中的F函数中由两个输入数据，一个是R组数据，另一个是子密钥数据。而且每一轮循环都要使用一个不同的子密钥，由16轮循环也就会由16个子密钥数据。我们这节就来讨论下这16个子密钥的生成算法。先来看下流程图：  
![密钥生成流程图][format_png 3]

### 密钥生成算法PC-1置换 ###

通过观察流程图我们注意到一点，密钥刚开始是64位的，但是经过PC-1置换处理后就变成了56位了，这说明在密钥数据中有8位密钥参加子密钥的生成。到底是哪些位没有参加子密钥的生成呢？这里我们就要观察下PC-1置换表：  
![PC-1置换表][PC-1]  
　　从表中观察我们发现，这个PC-1置换表是一个7\*8矩阵。其中的内容缺少了8、16、24、32、40、48、56、64，也就是说这8个位置没有参加密钥的生成，他们被当作了校验位。如果没有对校验位做出相应的处理，就会出现多组密钥可以解密同一个加密密文的情况。比如：  
![多解情况][format_png 4]  
　　我们可以发现，对相同的数据进行加密，使用不同的密钥生成的加密数据和解密结果都是相同的，而且解密结果正确。这个PC-1置换表也就导致了虽然输入的密钥是64位，但实际上只有56位起着作用。这里希望大家留意！  
**代码演示：**

const unsigned char PC_1_Table[56] =
    {
        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, 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
    };
     
    int PC_1_Substitution(const unsigned char *BitKey, unsigned char *BitKey_PC_1)
    {
        int ret = 0;
     
        for (int i = 0; i < 56; i++)
        {
            BitKey_PC_1[i] = BitKey[PC_1_Table[i] - 1];
        }
     
        return ret;
    }

### 密钥生成算法分组以及左移处理 ###

经过PC-1处理后就要进行数据分组了，这个分组的方法和DES算法的分组方法类似，都是前后分组，只不过每组数据都是28位的，前28位数据分给C组，后28位分给D组。这里也就不过多叙述了。  
　　这节主要介绍每组数据的左移操作。在右移前我们把数据分成了两组，所以这里的左移是将两组数据分别进行左移处理，而且左移的位数相同。比如：将C组左移2位，就要把所有数据向左移动两位，并把前面超出范围的两位数据移动到数据的最后面。当然每组左移的位数也不是随意确定的，当i=1、2、9、16轮中，C、D两组向左移动一位；在其他轮中，C、D两组向左移动两位(i>=1)。这里需要注意的是，如果把所有移动位数加起来刚好等于每组数据的位数，也就是一共需要移动28位。也就是移动前的数据等于最后移动后的数据：C\[0\] = C\[16\]; D\[0\] = D\[16\];在这里我们就把移动的位数做成一共移位表，方便编程。  
![移位表][format_png 5]

**代码演示：**

const unsigned char Bit_Round[16] =
    {
        1, 1, 2, 2,
        2, 2, 2, 2,
        1, 2, 2, 2,
        2, 2, 2, 1
    };
     
    int BitRound_L(const unsigned char* SrcBitGroup, unsigned char* DesBitGroup, int nBit)
    {
        int ret = 0;
     
        memcpy(DesBitGroup,             &SrcBitGroup[nBit], 28 - nBit);
        memcpy(&DesBitGroup[28 - nBit], SrcBitGroup,        nBit);
     
        return ret;
    }
     
    //将C、D两组进行轮转移位操作    左移
    BitRound_L(BitC_Table[i], BitC_Table[i + 1], Bit_Round[i]);
    BitRound_L(BitD_Table[i], BitD_Table[i + 1], Bit_Round[i]);

### 密钥生成算法PC-2置换 ###

\*\*在进行PC-2置换前，需要将C、D两组左移后的数据进行合并，合并方法与前方类似。C、D两组合并后形成一个56Bit数据块，这个数据块经过PC-2置换后就会变成一个48Bit的子密钥。通过如此这般16轮循环处理就可以形成16个48位的子密钥，这就是子密钥的生成过程。这里直接上PC-2置换表和代码。  
![PC-2置换表][PC-2]

**代码演示：**

const unsigned char PC_2_Table[48] =
    {
        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
    };
     
    int PC_2_Substitution(const unsigned char *BitKey, unsigned char *SubKey)
    {
        int ret = 0;
     
        for (int i = 0; i < 48; i++)
        {
            SubKey[i] = BitKey[PC_2_Table[i] - 1];
        }
     
        return ret;
    }

**密钥生成算法结束！至此DES算法的加密算法介绍完毕。**

## DES算法的解密方法： ##

当我们了解了DES的加密算法后，它的解密算法也就大致明白了。为什么这么说呢？是因为与加密相比解密的方法就是将生成的16组子密钥按照相反的顺序输入到F函数即可完成解密，比如：加密时子密钥输入的顺序分别是1-16组，解密的顺序就应该是16-1组了。只不过对数据处理上有些许不同，这种差别会在附件的参考代码中体现处来。

--------------------

# 基础部分总结： #

在我们把输入数据当作二进制信息进行处理时，首先不是思考使用什么方法处理这些数据，而是一共思考这些数据应该如何转换成二进制信息。因为二进制的转换形式非常多，每个人对数据的处理也都会不同，这里举个例子：以0x34数据为例，可以把它转换成0011 0100，因为这样解析数据很直观；也可以把她转换成0010 1100，这就是将这个数据按照地址进行解析，从最不重要位到最重要位。这里也就没有什么对与错，不过我一直认为应该按照第二种方式进行转换，因为这种方式是最符合计算机处理逻辑的。但是本文为了可以得到与公开加密工具相同的结果，阅读了很多代码发现，他们都是按照第一种方式进行转换的。所以本文的参考代码也只好如此了。这里还有一个问题就是，为什么在DES加密框架中的分组不是左右分组而是前后分组。如果标准代码不是左右分组，和书上的介绍就会不一致，会不会误导读者呢？希望大佬们给予解答，谢谢。最后附上两种数据转换方式。

**代码演示：**

//第一种   0x34 --->  00110100
    int ByteToBit(const unsigned char *Byte, unsigned char *Bit)
    {
        int ret = 0;
     
        for(int i = 0; i < 8; i ++)
        {
            for (int j = 0; j < 8; j++)
            {
                Bit[i * 8 + j] = Byte[i] >> (7 - j) & 1;
            }
        }
     
        return ret;
    }
     
    //第二种   0x34 --->  00101100
    int ByteToBit(const unsigned char *ByteStr, unsigned int *BitStr)
    {
        for (int i = 0; i < 64; i++)
        {
            BitStr[i] = ByteStr[i / 8] >> (i % 8) & 1;
        }
    }

对以上问题的解答：(1)为什么分组叫左右分组，而不是前后分组？因为在以前DES算法输入的64位明文数据，不是用64个Char类型组合的，而是由2个int类型组成的，左分组表示int\[0\]，右分组表示int\[1\]。这就是左右分组。(2)密码算法对数据的处理：密码算法对数据默认是将数据解析成大端对齐的，而不是小端对齐。所以0x34应该被解析成0011 0100b。

--------------------

# 进阶部分概述： #

>  *  **本文目的：**写本章主要是要对基础部分的DES算法代码做进一步的优化，使其效率有所提高。由于我的能力有限，优化的方法只能一个个的慢慢更新。另外还要感谢看场雪版主对我的指点，如果不是版主我可能还不知道基础部分的代码可以得到进一步的升级。
>  *  **具备基础：**  
>     (1)、C语言基础  
>     (2)、对DES加密算法有所了解
>  *  **学习环境：**任意C语言开发环境

--------------------

# 优化一：将S盒和P置换表进行合并 #

## 第一步：优化S盒 ##

我们都知道在DES算法中，S盒是一个三维的数组，分别表示选择的S盒编号、S盒的行号、S盒的列号。我们可以从S盒的定位方式上发现，在获取S盒的行号和列号时，和其他的表不一样，而且非常特殊。行号时由6Bit数据中的最重要位和最不重要位决定的，列号是由6Bit数据的中间4位决定的。这种定位虽然看起来比较高大上，可能对加密算法的安全性有所提高，但却又有些多余。如果我们把每个S盒中的数据顺序换一下，让它按照顺序排列。这样可以省区计算行号列号的时间，可以直接通过输入6Bit的下标获取S盒的数据。  
![定位S盒数据图解][S 2]  
　　我们以第一个S盒为例，它是一个4行16列的表，当我们输入的6Bit数据为000000b时，选择的行号为0，列号为0，对应的数值为14。当我们输入000001b时，选择的行号为1，列号为0，对应的数值为0。当我们输入的6Bit数据为000010b时，选择的行号为0，列号为1，对应的数值为4。当我们输入000011b时，选择的行号为1，列号为1，对应的数值为15.....  
![S1盒][S1]  
　　如果我们按照这个顺序排列形成一个新的S1盒就可以直接使用输入的6Bit数据来获取其对应的数值了，这可以省区计算行号列号的操作。那么接下来我们就可以考虑如何获取新的S1盒内容了，总不能一个一个的找吧！我们可以设计一个循环，循环64次，通过这个循环就可以将S1盒的内容全部打印下来了。

**代码演示**

const unsigned char S_Table[4][16] =
    {
        //S1盒
        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
    }
     
    void main()
    {
        for (int i = 0; i < 64; i++)
        {
            if (i % 16 == 0)
                printf("\n");
     
            unsigned int Row = (((i >> 5) & 1) << 1) + (i & 1);             //S盒的行号
            unsigned int Col =
                (((i >> 4) & 1) << 3) +
                (((i >> 3) & 1) << 2) +
                (((i >> 2) & 1) << 1) +
                (((i >> 1) & 1) << 0);                  //S盒的列号
     
            printf("%2d, ", S_Table[Row][Col]);
        }
        printf("\n");
        system("pause");
        return;
    }

**得到的新S1盒：**  
![新S1盒][S1 1]

我们就用这种方法将剩余的新S盒全部打印出来，就可以得到8个不需要计算行号和列号的新S盒。也就是将S盒从三维数组转换成了二维数组，这个二维数组每个下标分别表示S盒编号、S盒的下标。现在将新S盒替换到以前的程序中，修改对应F函数就会完成对S盒的优化了。

**新的F函数：**

//优化的S盒表    f函数内
    const unsigned char S_Table[8][64] =
    {
        //S1盒
        14,  0,  4, 15, 13,  7,  1,  4,  2, 14, 15,  2, 11, 13,  8,  1,
         3, 10, 10,  6,  6, 12, 12, 11,  5,  9,  9,  5,  0,  3,  7,  8,
         4, 15,  1, 12, 14,  8,  8,  2, 13,  4,  6,  9,  2,  1, 11,  7,
        15,  5, 12, 11,  9,  3,  7, 14,  3, 10, 10,  0,  5,  6,  0, 13,
     
        //S2盒
        15,  3,  1, 13,  8,  4, 14,  7,  6, 15, 11,  2,  3,  8,  4, 14,
         9, 12,  7,  0,  2,  1, 13, 10, 12,  6,  0,  9,  5, 11, 10,  5,
         0, 13, 14,  8,  7, 10, 11,  1, 10,  3,  4, 15, 13,  4,  1,  2,
         5, 11,  8,  6, 12,  7,  6, 12,  9,  0,  3,  5,  2, 14, 15,  9,
     
        //S3盒
        10, 13,  0,  7,  9,  0, 14,  9,  6,  3,  3,  4, 15,  6,  5, 10,
         1,  2, 13,  8, 12,  5,  7, 14, 11, 12,  4, 11,  2, 15,  8,  1,
        13,  1,  6, 10,  4, 13,  9,  0,  8,  6, 15,  9,  3,  8,  0,  7,
        11,  4,  1, 15,  2, 14, 12,  3,  5, 11, 10,  5, 14,  2,  7, 12,
     
        //S4盒
         7, 13, 13,  8, 14, 11,  3,  5,  0,  6,  6, 15,  9,  0, 10,  3,
         1,  4,  2,  7,  8,  2,  5, 12, 11,  1, 12, 10,  4, 14, 15,  9,
        10,  3,  6, 15,  9,  0,  0,  6, 12, 10, 11,  1,  7, 13, 13,  8,
        15,  9,  1,  4,  3,  5, 14, 11,  5, 12,  2,  7,  8,  2,  4, 14,
     
        //S5盒
         2, 14, 12, 11,  4,  2,  1, 12,  7,  4, 10,  7, 11, 13,  6,  1,
         8,  5,  5,  0,  3, 15, 15, 10, 13,  3,  0,  9, 14,  8,  9,  6,
         4, 11,  2,  8,  1, 12, 11,  7, 10,  1, 13, 14,  7,  2,  8, 13,
        15,  6,  9, 15, 12,  0,  5,  9,  6, 10,  3,  4,  0,  5, 14,  3,
     
        //S6盒
        12, 10,  1, 15, 10,  4, 15,  2,  9,  7,  2, 12,  6,  9,  8,  5,
         0,  6, 13,  1,  3, 13,  4, 14, 14,  0,  7, 11,  5,  3, 11,  8,
         9,  4, 14,  3, 15,  2,  5, 12,  2,  9,  8,  5, 12, 15,  3, 10,
         7, 11,  0, 14,  4,  1, 10,  7,  1,  6, 13,  0, 11,  8,  6, 13,
     
        //S7盒
         4, 13, 11,  0,  2, 11, 14,  7, 15,  4,  0,  9,  8,  1, 13, 10,
         3, 14, 12,  3,  9,  5,  7, 12,  5,  2, 10, 15,  6,  8,  1,  6,
         1,  6,  4, 11, 11, 13, 13,  8, 12,  1,  3,  4,  7, 10, 14,  7,
        10,  9, 15,  5,  6,  0,  8, 15,  0, 14,  5,  2,  9,  3,  2, 12,
     
        //S8盒
        13,  1,  2, 15,  8, 13,  4,  8,  6, 10, 15,  3, 11,  7,  1,  4,
        10, 12,  9,  5,  3,  6, 14, 11,  5,  0,  0, 14, 12,  9,  7,  2,
         7,  2, 11,  1,  4, 14,  1,  7,  9,  4, 12, 10, 14,  8,  2, 13,
         0, 15,  6, 12, 10,  9, 13,  0, 15,  3,  3,  5,  5,  6,  8, 11
    };
     
    //新的F函数
    int DES_F_Function(const unsigned char* BitR_Table, const unsigned char* SubKey, unsigned char* BitP_Table/*输出P表置换的结果*/)
    {
        int ret = 0;
     
        //1、定义变量
        unsigned char BitE_Table[48];       //E(R)扩展置换结果
        unsigned char Bit_Xor[8][6];        //存放异或运算的结果
        //unsigned char Row;                    //S盒的行号
        //unsigned char Col;                    //S盒的列号
        unsigned char Index;                //S盒的下标
        unsigned char Integer;              //从S盒中取得的32位整数
        unsigned char Bit_Integer[8][4];    //将整数变成Bit位
     
        //2、变量初始化
        memset(BitE_Table, 0, sizeof(BitE_Table));
        memset(Bit_Xor, 0, sizeof(Bit_Xor));
        //Row = 0;
        //Col = 0;
        Index = 0;
        Integer = 0;
        memset(Bit_Integer, 0, sizeof(Bit_Integer));
     
        //3、进行扩展置换      32 -->> 48
        E_Substitution(BitR_Table, BitE_Table);
     
        //4、将置换后的结果与传入的子密钥进行异或运算
        DES_XOR(BitE_Table, SubKey, (unsigned char*)Bit_Xor, 48);
     
        //5、将运算后的结果进行8个S盒压缩置换
        for (int i = 0; i < 8; i++)
        {
            //(1)、计算S盒的下标
            //Row = (Bit_Xor[i][0] << 1) + Bit_Xor[i][5];
            //Col = (Bit_Xor[i][1] << 3) + (Bit_Xor[i][2] << 2) + (Bit_Xor[i][3] << 1) + Bit_Xor[i][4];
            Index = (Bit_Xor[i][0] << 5) + (Bit_Xor[i][1] << 4) +
                    (Bit_Xor[i][2] << 3) + (Bit_Xor[i][3] << 2) +
                    (Bit_Xor[i][4] << 1) + Bit_Xor[i][5];
     
            //(2)、从S盒中取得整数
            Integer = S_Table[i][Index];
     
            //(3)、将取得的4Bit数转换成Bit组
            for (int j = 0; j < 4; j++)
            {
                Bit_Integer[i][j] = Integer >> (3 - j) & 1;
            }
        }
     
        //6、进行P置换
        P_Substitution((unsigned char *)Bit_Integer, BitP_Table);
     
        return ret;
    }

## 第二步：合并S盒与P置换表 ##

通过上一步我们可以直接从输入的6Bit索引值获取到对应的S盒4Bit数值。我们需要把8个4Bit数值合并成32位数据，这也就是P置换表的输入数据。我们这一步的目的就是要省去P表的置换处理，要达到这一目的我们就要找到S盒与P置换表的对应关系，通过输入6Bit数据直接获得该6Bit数据P置换后的结果，然后将8个置换后的结果相与就会得到最终的结果。这就就是优化的思路。  
![P置换表][P 1]  
　　我们知道S1盒的输出数据位于所有32位数据的1-4Bit位。S2盒的输出位于所有数据的5-8Bit位。S3盒的输出位于所有数据的9-12Bit位......然后我们观察P置换表发现，S1盒的输出结果最终会位于所有32位数据的第9、17、23、31位。我们以S1盒输出的4Bit数据为1110b其他S盒结果为0来举例，1110b通过P置换后，高位的3个1会被移动到32位数据的第9、17、23位，最低位的0会被移动到第31位。最终会得到置换结果0x00410100。这样我们就找到了新S盒与P置换表的对应关系，新S1盒的索引0对应的结果位14，经P置换后结果为0x00410100。也就是我们在将来的SP1表输入000000b，将会输出0x00410100。  
　　找到了对应关系，我们就要计算新的SP表中的数据了，我们使用以下方法来打印SP1表中的数据，使用应该for循环，循环64次，获取新S1盒的内容，然后将这个内容进行移位操作，就会获得SP1表。

**代码演示**

const unsigned char S1_Table[64] =
    {
        //新S1盒
        14,  0,  4, 15, 13,  7,  1,  4,  2, 14, 15,  2, 11, 13,  8,  1,
         3, 10, 10,  6,  6, 12, 12, 11,  5,  9,  9,  5,  0,  3,  7,  8,
         4, 15,  1, 12, 14,  8,  8,  2, 13,  4,  6,  9,  2,  1, 11,  7,
        15,  5, 12, 11,  9,  3,  7, 14,  3, 10, 10,  0,  5,  6,  0, 13,
    }
     
    int main()
    {  
        for (int j = 0; j < 64; j++)
        {
            if (j % 4 == 0)
            {
                printf("\n");
            }
     
            unsigned char integer = S1_Table[j];
     
            unsigned int Int = 0;
     
            Int += ((integer >> 3) & 0x01) << 8;
            Int += ((integer >> 2) & 0x01) << 16;
            Int += ((integer >> 1) & 0x01) << 22;
            Int += ((integer >> 0) & 0x01) << 30;
     
            printf("0x%08X, ", Int);
        }
        printf("\n\n");
        system("pause");
        return 0;
    }

**打印结果：**  
![SP1表][SP1]

**我们就可以通过这种方法将所有的SP盒内容打印出来。有了合并后的SP盒我们就应该修改下以前的流程图了。新的流程图如下：**

![新F函数处理流程图][F 1]

**通过这个新的流程图我们就该对F函数做修改了，修改后的结果如下：**

const unsigned int SP_Table[8][64] =
    {
        //SP1盒
        0x00410100, 0x00000000, 0x00010000, 0x40410100,
        0x40010100, 0x40410000, 0x40000000, 0x00010000,
        0x00400000, 0x00410100, 0x40410100, 0x00400000,
        0x40400100, 0x40010100, 0x00000100, 0x40000000,
        0x40400000, 0x00400100, 0x00400100, 0x00410000,
        0x00410000, 0x00010100, 0x00010100, 0x40400100,
        0x40010000, 0x40000100, 0x40000100, 0x40010000,
        0x00000000, 0x40400000, 0x40410000, 0x00000100,
        0x00010000, 0x40410100, 0x40000000, 0x00010100,
        0x00410100, 0x00000100, 0x00000100, 0x00400000,
        0x40010100, 0x00010000, 0x00410000, 0x40000100,
        0x00400000, 0x40000000, 0x40400100, 0x40410000,
        0x40410100, 0x40010000, 0x00010100, 0x40400100,
        0x40000100, 0x40400000, 0x40410000, 0x00410100,
        0x40400000, 0x00400100, 0x00400100, 0x00000000,
        0x40010000, 0x00410000, 0x00000000, 0x40010100,
     
        //SP2盒
        0x08021002, 0x00020002, 0x00020000, 0x08021000,
        0x00001000, 0x08000000, 0x08001002, 0x08020002,
        0x08000002, 0x08021002, 0x00021002, 0x00000002,
        0x00020002, 0x00001000, 0x08000000, 0x08001002,
        0x00021000, 0x08001000, 0x08020002, 0x00000000,
        0x00000002, 0x00020000, 0x08021000, 0x00001002,
        0x08001000, 0x08000002, 0x00000000, 0x00021000,
        0x08020000, 0x00021002, 0x00001002, 0x08020000,
        0x00000000, 0x08021000, 0x08001002, 0x00001000,
        0x08020002, 0x00001002, 0x00021002, 0x00020000,
        0x00001002, 0x00020002, 0x08000000, 0x08021002,
        0x08021000, 0x08000000, 0x00020000, 0x00000002,
        0x08020000, 0x00021002, 0x00001000, 0x08000002,
        0x08001000, 0x08020002, 0x08000002, 0x08001000,
        0x00021000, 0x00000000, 0x00020002, 0x08020000,
        0x00000002, 0x08001002, 0x08021002, 0x00021000,
     
        //SP3盒
        0x20800000, 0x00808020, 0x00000000, 0x20008020,
        0x00800020, 0x00000000, 0x20808000, 0x00800020,
        0x20008000, 0x20000020, 0x20000020, 0x00008000,
        0x20808020, 0x20008000, 0x00008020, 0x20800000,
        0x00000020, 0x20000000, 0x00808020, 0x00800000,
        0x00808000, 0x00008020, 0x20008020, 0x20808000,
        0x20800020, 0x00808000, 0x00008000, 0x20800020,
        0x20000000, 0x20808020, 0x00800000, 0x00000020,
        0x00808020, 0x00000020, 0x20008000, 0x20800000,
        0x00008000, 0x00808020, 0x00800020, 0x00000000,
        0x00800000, 0x20008000, 0x20808020, 0x00800020,
        0x20000020, 0x00800000, 0x00000000, 0x20008020,
        0x20800020, 0x00008000, 0x00000020, 0x20808020,
        0x20000000, 0x20808000, 0x00808000, 0x20000020,
        0x00008020, 0x20800020, 0x20800000, 0x00008020,
        0x20808000, 0x20000000, 0x20008020, 0x00808000,
     
        //SP4盒
        0x00080201, 0x02080001, 0x02080001, 0x02000000,
        0x02080200, 0x02000201, 0x00000201, 0x00080001,
        0x00000000, 0x00080200, 0x00080200, 0x02080201,
        0x02000001, 0x00000000, 0x02000200, 0x00000201,
        0x00000001, 0x00080000, 0x00000200, 0x00080201,
        0x02000000, 0x00000200, 0x00080001, 0x02080000,
        0x02000201, 0x00000001, 0x02080000, 0x02000200,
        0x00080000, 0x02080200, 0x02080201, 0x02000001,
        0x02000200, 0x00000201, 0x00080200, 0x02080201,
        0x02000001, 0x00000000, 0x00000000, 0x00080200,
        0x02080000, 0x02000200, 0x02000201, 0x00000001,
        0x00080201, 0x02080001, 0x02080001, 0x02000000,
        0x02080201, 0x02000001, 0x00000001, 0x00080000,
        0x00000201, 0x00080001, 0x02080200, 0x02000201,
        0x00080001, 0x02080000, 0x00000200, 0x00080201,
        0x02000000, 0x00000200, 0x00080000, 0x02080200,
     
        //SP5盒
        0x01000000, 0x01002080, 0x00002080, 0x01000084,
        0x00002000, 0x01000000, 0x00000004, 0x00002080,
        0x01002004, 0x00002000, 0x01000080, 0x01002004,
        0x01000084, 0x00002084, 0x01002000, 0x00000004,
        0x00000080, 0x00002004, 0x00002004, 0x00000000,
        0x01000004, 0x01002084, 0x01002084, 0x01000080,
        0x00002084, 0x01000004, 0x00000000, 0x00000084,
        0x01002080, 0x00000080, 0x00000084, 0x01002000,
        0x00002000, 0x01000084, 0x01000000, 0x00000080,
        0x00000004, 0x00002080, 0x01000084, 0x01002004,
        0x01000080, 0x00000004, 0x00002084, 0x01002080,
        0x01002004, 0x01000000, 0x00000080, 0x00002084,
        0x01002084, 0x01002000, 0x00000084, 0x01002084,
        0x00002080, 0x00000000, 0x00002004, 0x00000084,
        0x01002000, 0x01000080, 0x01000004, 0x00002000,
        0x00000000, 0x00002004, 0x01002080, 0x01000004,
     
        //SP6盒
        0x10000008, 0x00000408, 0x00040000, 0x10040408,
        0x00000408, 0x10000000, 0x10040408, 0x00000400,
        0x00040008, 0x10040400, 0x00000400, 0x10000008,
        0x10000400, 0x00040008, 0x00000008, 0x10040000,
        0x00000000, 0x10000400, 0x10040008, 0x00040000,
        0x00040400, 0x10040008, 0x10000000, 0x10000408,
        0x10000408, 0x00000000, 0x10040400, 0x00040408,
        0x10040000, 0x00040400, 0x00040408, 0x00000008,
        0x00040008, 0x10000000, 0x10000408, 0x00040400,
        0x10040408, 0x00000400, 0x10040000, 0x10000008,
        0x00000400, 0x00040008, 0x00000008, 0x10040000,
        0x10000008, 0x10040408, 0x00040400, 0x00000408,
        0x10040400, 0x00040408, 0x00000000, 0x10000408,
        0x10000000, 0x00040000, 0x00000408, 0x10040400,
        0x00040000, 0x10000400, 0x10040008, 0x00000000,
        0x00040408, 0x00000008, 0x10000400, 0x10040008,
     
        //SP7盒
        0x00000800, 0x80000840, 0x80200040, 0x00000000,
        0x00200000, 0x80200040, 0x80200800, 0x00200840,
        0x80200840, 0x00000800, 0x00000000, 0x80000040,
        0x80000000, 0x00000040, 0x80000840, 0x80200000,
        0x00200040, 0x80200800, 0x80000800, 0x00200040,
        0x80000040, 0x00000840, 0x00200840, 0x80000800,
        0x00000840, 0x00200000, 0x80200000, 0x80200840,
        0x00200800, 0x80000000, 0x00000040, 0x00200800,
        0x00000040, 0x00200800, 0x00000800, 0x80200040,
        0x80200040, 0x80000840, 0x80000840, 0x80000000,
        0x80000800, 0x00000040, 0x00200040, 0x00000800,
        0x00200840, 0x80200000, 0x80200800, 0x00200840,
        0x80200000, 0x80000040, 0x80200840, 0x00000840,
        0x00200800, 0x00000000, 0x80000000, 0x80200840,
        0x00000000, 0x80200800, 0x00000840, 0x00200000,
        0x80000040, 0x00200040, 0x00200000, 0x80000800,
     
        //SP8盒
        0x04100010, 0x00100000, 0x00004000, 0x04104010,
        0x00000010, 0x04100010, 0x04000000, 0x00000010,
        0x04004000, 0x00004010, 0x04104010, 0x00104000,
        0x00104010, 0x04104000, 0x00100000, 0x04000000,
        0x00004010, 0x04000010, 0x00100010, 0x04100000,
        0x00104000, 0x04004000, 0x04004010, 0x00104010,
        0x04100000, 0x00000000, 0x00000000, 0x04004010,
        0x04000010, 0x00100010, 0x04104000, 0x00004000,
        0x04104000, 0x00004000, 0x00104010, 0x00100000,
        0x04000000, 0x04004010, 0x00100000, 0x04104000,
        0x00100010, 0x04000000, 0x04000010, 0x00004010,
        0x04004010, 0x00000010, 0x00004000, 0x04100010,
        0x00000000, 0x04104010, 0x04004000, 0x04000010,
        0x00004010, 0x00100010, 0x04100010, 0x00000000,
        0x04104010, 0x00104000, 0x00104000, 0x04100000,
        0x04100000, 0x04004000, 0x00000010, 0x00104010
    };
     
    int DES_F_Function(const unsigned char* BitR_Table, const unsigned char* SubKey, unsigned char* BitP_Table/*输出P表置换的结果*/)
    {
        int ret = 0;
     
        //1、定义变量
        unsigned char BitE_Table[48];       //E(R)扩展置换结果
        unsigned char Bit_Xor[8][6];        //存放异或运算的结果
        //unsigned char Row;                    //S盒的行号
        //unsigned char Col;                    //S盒的列号
        unsigned char Index;                //S盒的下标
        unsigned int Integer;               //从S盒中取得的32位整数
        unsigned char Bit_Integer[8][4];    //将整数变成Bit位
     
        //2、变量初始化
        memset(BitE_Table, 0, sizeof(BitE_Table));
        memset(Bit_Xor, 0, sizeof(Bit_Xor));
        //Row = 0;
        //Col = 0;
        Index = 0;
        Integer = 0;
        memset(Bit_Integer, 0, sizeof(Bit_Integer));
     
        //3、进行扩展置换      32 -->> 48
        E_Substitution(BitR_Table, BitE_Table);
     
        //4、将置换后的结果与传入的子密钥进行异或运算
        DES_XOR(BitE_Table, SubKey, (unsigned char*)Bit_Xor, 48);
     
        //5、将运算后的结果进行8个S盒压缩置换
        for (int i = 0; i < 8; i++)
        {
            //(1)、计算S盒的下标
            //Row = (Bit_Xor[i][0] << 1) + Bit_Xor[i][5];
            //Col = (Bit_Xor[i][1] << 3) + (Bit_Xor[i][2] << 2) + (Bit_Xor[i][3] << 1) + Bit_Xor[i][4];
            Index = (Bit_Xor[i][0] << 5) + (Bit_Xor[i][1] << 4) +
                    (Bit_Xor[i][2] << 3) + (Bit_Xor[i][3] << 2) +
                    (Bit_Xor[i][4] << 1) + Bit_Xor[i][5];
     
            //(2)、从S盒中取得整数
            //Integer = S_Table[i][Index];
            Integer |= SP_Table[i][Index];
     
            //(3)、将取得的4Bit数转换成Bit组
            //for (int j = 0; j < 4; j++)
            //{
            //  Bit_Integer[i][j] = Integer >> (3 - j) & 1;
            //}
        }
     
        //6、进行P置换
        //P_Substitution((unsigned char *)Bit_Integer, BitP_Table);
     
        //6、将整数变成Bit位
        for (int i = 0; i < 32; i++)
        {
            BitP_Table[i] = (Integer >> i) & 0x01;
        }
     
     
        return ret;
    }

**优化一介绍完毕！其他优化等待后续跟新。。。。**

# 优化二：通过位运算替代初始置换 #

> 　　**优化代码采用Richard Outerbridge的D3DES(V5.09)中的位运算方法，取代初始置换过程。由于作者的计算方法过于精简，所以通过图解的方式进行演示。通过图解笔者发现了其代码中存在了快30年的问题，并附上正确的解决方案。**

## D3DES中相关代码： ##

//block存储需要初始置换的明文数据  类型 unsigned int[2];
    register unsigned long work, right, leftt;
    register int round;
     
    leftt = block[0];
    right = block[1];
    work = ((leftt >> 4) ^ right) & 0x0f0f0f0fL;
    right ^= work;
    leftt ^= (work << 4);
    work = ((leftt >> 16) ^ right) & 0x0000ffffL;
    right ^= work;
    leftt ^= (work << 16);
    work = ((right >> 2) ^ leftt) & 0x33333333L;
    leftt ^= work;
    right ^= (work << 2);
    work = ((right >> 8) ^ leftt) & 0x00ff00ffL;
    leftt ^= work;
    right ^= (work << 8);
    right = ((right << 1) | ((right >> 31) & 1L)) & 0xffffffffL;
    work = (leftt ^ right) & 0xaaaaaaaaL;
    leftt ^= work;
    right ^= work;
    leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL;

--------------------

## 代码块图解： ##

**对应代码块：**

leftt = block[0];
    right = block[1];

![图解1][1]

--------------------

**对应代码块：**

work = ((leftt >> 4) ^ right) & 0x0f0f0f0fL;
    right ^= work;
    leftt ^= (work << 4);

**对应图解：**  
![图解2][2]

--------------------

**对应代码块：**

work = ((leftt >> 16) ^ right) & 0x0000ffffL;
    right ^= work;
    leftt ^= (work << 16);

**对应图解：**  
![图解3][3]

--------------------

**对应代码块：**

work = ((right >> 2) ^ leftt) & 0x33333333L;
    leftt ^= work;
    right ^= (work << 2);

**对应图解：**  
![图解4][4]

--------------------

**对应代码块：**

work = ((right >> 8) ^ leftt) & 0x00ff00ffL;
    leftt ^= work;
    right ^= (work << 8);
    right = ((right << 1) | ((right >> 31) & 1L)) & 0xffffffffL;

**对应图解：**  
![图解5][5]

--------------------

**对应代码块：**

work = (leftt ^ right) & 0xaaaaaaaaL;
    leftt ^= work;
    right ^= work;
    leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL;

**对应图解：**  
![图解6][6]

**重点：在最后一个代码上，大家可能发现leftt这个数据块已经和初始置换表上的前32位一致了，然而最后一句代码竟然把leftt完美的移位给破坏了，而right数据块还是与初始置换表的后32位有点差距的。所以我们就找到了这个代码存在了数十年的问题，leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL;这句话应该用于处理right数据块，而不是处理leftt。那要怎么改呢？我们从图解中发现，如果将right的最后一位移动到第一位上，那么存在置换表的替换就完成了。所以改动后的最后一句代码如下：**

//leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL;
    right = ((right >> 1) | ((right << 31))) & 0xffffffffL;

**在进行初始置换前，作者还将输入的明文数据进行了由小端序转换成大端序的处理，所以如果要彻底替换初始置换，还需要进行大小端序转换，然后进行初始置换的移位操作，最后不要忘了将大端序转换成小端序。**

附上修改后的加密函数：

static void IP(register unsigned long *block)
    //register unsigned long *block, *keys;
    {
        register unsigned long right, leftt, work;
     
        leftt = block[0];
        right = block[1];
        work = ((leftt >> 4) ^ right) & 0x0f0f0f0fL;
        right ^= work;
        leftt ^= (work << 4);
        work = ((leftt >> 16) ^ right) & 0x0000ffffL;
        right ^= work;
        leftt ^= (work << 16);
        work = ((right >> 2) ^ leftt) & 0x33333333L;
        leftt ^= work;
        right ^= (work << 2);
        work = ((right >> 8) ^ leftt) & 0x00ff00ffL;
        leftt ^= work;
        right ^= (work << 8);
        right = ((right << 1) | ((right >> 31) & 1L)) & 0xffffffffL;
        work = (leftt ^ right) & 0xaaaaaaaaL;
        leftt ^= work;
        right ^= work;
     
        //leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL;
        right = ((right >> 1) | ((right << 31))) & 0xffffffffL;
     
        block[0] = leftt;
        block[1] = right;
    }
     
    //将小端序转换成大端序
    static void scrunch(register unsigned char *outof, register unsigned long *into)
    //register unsigned char *outof;
    //register unsigned long *into;
    {
        *into = (*outof++ & 0xffL) << 24;
        *into |= (*outof++ & 0xffL) << 16;
        *into |= (*outof++ & 0xffL) << 8;
        *into++ |= (*outof++ & 0xffL);
        *into = (*outof++ & 0xffL) << 24;
        *into |= (*outof++ & 0xffL) << 16;
        *into |= (*outof++ & 0xffL) << 8;
        *into |= (*outof & 0xffL);
        return;
    }
     
    //将大端序转换成小端序
    static void unscrun(register unsigned long *outof, register unsigned char *into)
    //register unsigned long *outof;
    //register unsigned char *into;
    {
        *into++ = (*outof >> 24) & 0xffL;
        *into++ = (*outof >> 16) & 0xffL;
        *into++ = (*outof >> 8) & 0xffL;
        *into++ = *outof++ & 0xffL;
        *into++ = (*outof >> 24) & 0xffL;
        *into++ = (*outof >> 16) & 0xffL;
        *into++ = (*outof >> 8) & 0xffL;
        *into = *outof & 0xffL;
        return;
    }
     
    //对明文组进行初始IP置换
    unsigned long work[2];
    scrunch(PlainText, work);
    IP(work);
    unscrun(work, PlainText);

# 代码实现 #

代码实现：[代码实现与优化][Link 1]

[DES]: https://bbs.pediy.com/thread-253558.htm
[DES_Feistel]: /images/20221123/44a357d9a20549788904747a7aa8c3b2.png
[format_png]: /images/20221123/b0cecc306e9e4aadbe23eb30268b096b.png
[format_png 1]: /images/20221123/cf236397fbb641c38eb46c5bc6078610.png
[DES 1]: /images/20221123/537b1050c14a4581884f85491f554994.png
[F]: /images/20221123/b1b77509bad947e28fbb3ca47ac5f9c0.png
[E]: /images/20221123/32f9f78c2861478b89f373c6c7071068.png
[S]: /images/20221123/1536d7001d3545af915761f8f36c317f.png
[S 1]: /images/20221123/7b8aa8e9131347a3aad937116cde8c43.png
[P]: /images/20221123/dfc4e2ab527b40ecba235bdb62acc9d3.png
[format_png 2]: /images/20221123/c548e83083a14e4c8599665f6754b76a.png
[format_png 3]: /images/20221123/a9f5b138608742b19c81b5508a746f98.png
[PC-1]: /images/20221123/eb2aa9dfbaf74f62815b371f22ab07f4.png
[format_png 4]: /images/20221123/a9f06f61e43d488a9186764edc8ca656.png
[format_png 5]: /images/20221123/47fc857425ee4fbaa1d955eae2a3bfd6.png
[PC-2]: /images/20221123/3531127e558a4eb3b3ed85d7e6fbae8d.png
[S 2]: /images/20221123/eb7a8168756a4f59b54c2a6f1f845784.png
[S1]: /images/20221123/f09921e110a24674add271aedeabecc4.png
[S1 1]: /images/20221123/70fb84708a514611acedbf923f5b8d40.png
[P 1]: /images/20221123/aa7f8706ecd0439cb6941e044d2bfb54.png
[SP1]: /images/20221123/f940293f07a046b680355b10a52aa91e.png
[F 1]: /images/20221123/e484778977be48fbaa8bbe9f48e32c9c.png
[1]: /images/20221123/780511f447a0404f8495dc4848ddb2af.png
[2]: /images/20221123/3f8bda5ccf854b62965b9654f0b48157.png
[3]: /images/20221123/b1f151bd77c9480fabfc5aa0b4824ff6.png
[4]: /images/20221123/e3b6cd3592a0433c88eba1d1c8c19d12.png
[5]: /images/20221123/db0b098735134fbea59d64a338f4fcbf.png
[6]: /images/20221123/ce161c999d6141a585b0a912271b2a1a.png
[Link 1]: https://download.csdn.net/download/u013469753/12889203