首页
论坛
课程
招聘
[原创]密码学基础:DES加密算法
2019-8-3 16:31 26933

[原创]密码学基础:DES加密算法

2019-8-3 16:31
26933

目录

基础部分概述:

  • 本节目的:这一章作为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算法的加密流程:

  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算法中得到了充分的运用,通过置换处理可以打乱输入数据的顺序,使输入的数据变得面目全非,当然也会造成雪崩效应,因为只要有一个数据位发生变化,就会影响到很多地方。

 

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

 

图示:
置换图解

 

代码演示:

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算法的分组方式

 

理论分组代码演示:

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函数处理流程:

  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
  从扩展置换表中我们可以看出如果把扩展的结果当作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盒都是一个4*16矩阵,而且每个S盒中的内容都是可以用4个Bit为来表示的,嘿嘿这里就和输出的4Bit数据扯上关系了。接下来我们就来看看每一组6Bit数据是如何定位其对应的S盒数据的,我们这里把每组数据的第一个Bit为称作最重要位(MSB),把每组数据的最后一个Bit位称作最不重要位(LSB),之所以怎么取名是和他们的权重有关,第一位的权重最高,最后一位的权重最低。我们把每组数据的最重要位和最不重要位进行组合,形成一个2个Bit位的数据,这个数据表示对应S盒的行号。将中间四位数据进行组合形成一个4个Bit位的数据,这个数据表示对应S盒的列号。

 

定位S盒数据图解:
定位S盒数据图解
  在定位了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置换表

 

代码演示:

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[1