cplus-DES对称加密实现

Oct 18, 2016 · cplus 安全 ·

分享到:

DES（Data Encryption Standard）对称加密方法

DES算法全称为Data Encryption Standard，即数据加密标准，是一种使用密钥加密的块算法。DES算法是一种对称算法，即可以使用同一个密钥进行加密和解密。DES的具体原理解析，本人推荐J. Orlin Grabbe的名作《DES Algorithm Illustrated》以及一篇非常优秀的中文介绍：DES算法示例讲解。本文的重点是用C++代码 逐步实现DES算法的具体过程 。

0.前提说明

本文实现的是基于ECB的Zeropadding的DES加密算法。ECB指的是将加密的数据分成若干组，每组的大小跟加密密钥长度相同；然后每组都用相同的密钥加密，如果最后一个分组长度不够64位，要补齐64位。Zeropadding指的是补齐着这64位的方法是用0填充。这种模式是实现DES的基本模式。 DES的输入有三个部分，第一个部分是明文，就是需要加密内容；第二个部分是密钥，用来加密数据；第三个部分是工作模式，有两种，加密和解密。明文的长度不固定，但是都被分为固定的64位“数据块”，以一个块为单位进行加密，输出的密文也是一个64位的“块”；密钥的长度是64位，但是实际用到的只有56位，第8、16、24、32、40、48、56、64位是校验位，做加密中用不到。本文输入的格式为文本，例如明文‘12345678’，等同于16进制

1.密钥的生成

1.1实现字符到bit的转换

DES加密本质上是对二进制数据的加密，而正常我们输入电脑的多用的是文本形式，因此我们需要将字符转变为文本。我们把它放在类的成员函数中，在密钥生成阶段和明文加密阶段都会用到。本文以密钥“12345678”为例。主要分成两个函数：第一个函数：选取8字节密钥，超过8字节只选取前面8字节，不足8字节用0补齐。

 1 //设置密钥的内容，截取或补齐
 2 bool DataEncrytionStandard::SetKey(const char* _key)
 3 {
 4  int lengthCout=0;
 5  while(_key!='\0' && lengthCout<8)
 6  {
 7   this->key[lengthCout] = _key[lengthCout];//密码的长度只截取前面8位，不够的话用‘0’补齐。
 8   lengthCout++;
 9  }
10  return true;
11 }

第二个函数将8字节转换为64bits。本文使用的是64位的array<bool,64>实现。过去曾用bitset尝试过，但是bitset默认存储的是二进制数字，比特位顺序和DES加密的顺序相反；同时bitset还要考虑小端规则，对于降下来的处理不是很方便，因此用数组替代。本人发现网上的一些C++实现没有注意到这些问题，导致加密的结果与标准结果不一样。现推荐一个网站可以查看每一步实现的数据变化：JavaScript DES Example。

1array<bool,64> DataEncrytionStandard::CharToBits(char _inChar[8])
2{
3 array<bool,64> bits;
4 for(int i=0;i<8;i++)
5  for(int j=0;j<8;j++)
6   //这里注意顺序
7   bits[i*8+7-j] = (_inChar[i]>>j)&1;
8 return bits;
9}

获得密钥:0011000100110010001100110011010000110101001101100011011100111000

1.2密钥的PC-1转换

这个64位的秘钥首先根据表格PC-1进行变换，变成56位的密钥。这个表格含义是64bits密钥的第57位，变成新密钥的第1位；原密钥的第49位变成新密钥的第2位；以此类推。

 1            PC-1
 2
 357   49    41   33    25    17    9
 41   58    50   42    34    26   18
 510    2    59   51    43    35   27
 619   11     3   60    52    44   36
 763   55    47   39    31    23   15
 87   62    54   46    38    30   22
 914    6    61   53    45    37   29
1021   13     5   28    20    12    4

1
2 //第一次转换，将64bit的密钥根据PC-1变换转换成56bit。
3 array<bool,64> keyInit = CharToBits(this->key);
4 array<bool,56> keyPC_1;
5 for(int counter=0;counter<56;counter++)
6 {
7  keyPC_1[counter] = keyInit[PC_1[counter]-1];
8 }
9

56位密钥：00000000000000001111111111110110011001111000100000001111

1.3 密钥拆分与移位构成16轮子密钥

现在我们将56位的密钥拆分成前后两个等长部分（28位），C0、D0。我们现在创建16个块Cn 和 Dn, 1<=n<=16。每一对Cn 和 Dn都是由前一对Cn-1 和 Dn-1移位而来。具体说来，对于n = 1, 2, …, 16，在前一轮移位的结果上，使用下表进行一些次数的左移操作。这意味着，比如说，C3 和 D3是C2 和 D2移位而来的，具体来说，通过2次左移位；C16 和 D16 则是由C15和D15通过1次左移得到的。移位完成后，再将其拼接起来。

 1第n轮      左移位数
 21          1
 32          1
 43          2
 54          2
 65          2
 76          2
 87          2
 98          2
109          1
1110          2
1211          2
1312          2
1413          2
1514          2
1615          2
1716          1
18

具体代码如下所示：

 1 //进行16轮移位，获取16个子密钥块
 2 //array<array<bool,48>,16>subKeys; defined in the head file
 3 //array<array<bool,48>,16>subKeys; defined in the head file
 4 for(int iterator=0;iterator<16;iterator++)
 5 {
 6  if(iterator==0)
 7   offKeys[iterator] = SubKeyOff(keyPC_1,keyOff[iterator]);
 8  else
 9   offKeys[iterator] = SubKeyOff(offKeys[iterator-1],keyOff[iterator]);
10 }
11 
12 array<bool,56> DataEncrytionStandard::SubKeyOff(array<bool,56>_key56,int off)
13{
14 //将密钥拆分成左右两半，各28位。
15 list<bool> keyC;
16 list<bool> keyD;
17 //移位后的结果
18 array<bool,56> keyOffResult;
19 //前28位
20 for(int counter=0;counter<28;counter++)
21 {
22  keyC.push_back(_key56[counter]);
23 }
24 //后28位
25 for(int counter=28;counter<56;counter++)
26 {
27  keyD.push_back(_key56[counter]);
28 }
29 //循环移位,for内是一次移位
30 for(int i=0;i<off;i++)
31 {
32  bool temp = keyC.front();
33  keyC.pop_front();
34  keyC.push_back(temp);
35
36  temp = keyD.front();
37  keyD.pop_front();
38  keyD.push_back(temp);
39 }
40 for(int counter = 0;counter<28;counter++)
41 {
42  keyOffResult[counter] = keyC.front();
43  keyC.pop_front();
44 }
45 for(int counter = 28;counter<56;counter++)
46 {
47  keyOffResult[counter] = keyD.front();
48  keyD.pop_front();
49 }
50
51 return keyOffResult;
52}

可以得到如下16组子密钥。

C0 = 0000000000000000111111111111 D0 = 0110011001111000100000001111 C1: 0000000000000001111111111110 D1: 1100110011110001000000011110 C2: 0000000000000011111111111100 D2: 1001100111100010000000111101 C3: 0000000000001111111111110000 D3: 0110011110001000000011110110 C4: 0000000000111111111111000000 D4: 1001111000100000001111011001 C5: 0000000011111111111100000000 D5: 0111100010000000111101100110 C6: 0000001111111111110000000000 D6: 1110001000000011110110011001 C7: 0000111111111111000000000000 D7: 1000100000001111011001100111 C8: 0011111111111100000000000000 D8: 0010000000111101100110011110 C9: 0111111111111000000000000000 D9: 0100000001111011001100111100 C10: 1111111111100000000000000001 D10: 0000000111101100110011110001 C11: 1111111110000000000000000111 D11: 0000011110110011001111000100 C12: 1111111000000000000000011111 D12: 0001111011001100111100010000 C13: 1111100000000000000001111111 D13: 0111101100110011110001000000 C14: 1110000000000000000111111111 D14: 1110110011001111000100000001 C15: 1000000000000000011111111111 D15: 1011001100111100010000000111 C16: 0000000000000000111111111111 D16: 0110011001111000100000001111

1.4子密钥变换

以上获得的16个56位子密钥并不是最后加密用的子密钥，还需要根据PC-2变换成48位的子密钥。于是，第n轮的新秘钥Kn 的第1位来自组合子秘钥CnDn的第14位，第2位来自第17位，依次类推，知道新秘钥的第48位来自组合秘钥的第32位。这才是加密用的子密钥。

1            PC-2
214    17   11    24     1    5
33    28   15     6    21   10
423    19   12     4    26    8
516     7   27    20    13    2
641    52   31    37    47   55
730    40   51    45    33   48
844    49   39    56    34   53
946    42   50    36    29   32

1//第二次转换，通过PC-2将56位子密钥变成48位子密钥，得到最后的第n轮加密使用的子密钥。
2 for(int iterator=0;iterator<16;iterator++)
3 {
4  for(int counter=0;counter<48;counter++)
5   {
6    subKeys[iterator][counter] = offKeys[iterator][PC_2[counter]-1];
7   }
8 }

KS1:010100000010110010101100010101110010101011000010 KS2:010100001010110010100100010100001010001101000111 KS3:110100001010110000100110111101101000010010001100 KS4:111000001010011000100110010010000011011111001011 KS5:111000001001011000100110001111101111000000101001 KS6:111000001001001001110010011000100101110101100010 KS7:101001001101001001110010100011001010100100111010 KS8:101001100101001101010010111001010101111001010000 KS9:001001100101001101010011110010111001101001000000 KS10:001011110101000101010001110100001100011100111100 KS11:000011110100000111011001000110010001111010001100 KS12:000111110100000110011001110110000111000010110001 KS13:000111110000100110001001001000110110101000101101 KS14:000110110010100010001101101100100011100110010010 KS15:000110010010110010001100101001010000001100110111 KS16:010100010010110010001100101001110100001111000000

得到最终的16轮48位子密钥。

2.加密64位的数据块

2.1 字符到比特的转换

本文的明文将以“helloDES”为例。明文的预处理和密钥是一样的，我们这一节只考虑正好8个字节的明文。首先还是要将字符串转换成二进制bit位，这里用的方法和处理密钥的是一样的。

1 array<bool,64> msgInit = CharToBits(this->msg);

2进制明文：01101000 01100101 01101100 01101100 01101111 01000100 01000101 01010011

2.2 初始IP变换

IP是重新变换数据M的每一位产生的。产生过程由下表决定，表格的下标对应新数据的下标，表格的数值x表示新数据的这一位来自旧数据的第x位。原理和密钥的PC-1、PC-2变换也是一样的。区别是IP是一个64位到64位变换，位数不变。

1            IP
258    50   42    34    26   18    10    2
360    52   44    36    28   20    12    4
462    54   46    38    30   22    14    6
564    56   48    40    32   24    16    8
657    49   41    33    25   17     9    1
759    51   43    35    27   19    11    3
861    53   45    37    29   21    13    5
963    55   47    39    31   23    15    7

参照上表，明文2进制的第58位成为IP变换后的第1位，第50位成为IP变换后的第2位，第7位成为IP变换后的最后1位。

1 array<bool,64> msgIP;
2 for(int counter=0;counter<64;counter++)
3  msgIP[counter] = msgInit[IP[counter]-1];

IP转换后： 11111111 10000000 01111110 11010010 00000000 00011111 00011101 10010000

2.3 3.输入明文拆分与填充

TODO

4.拼接密文块并输出

TODO

遇到的问题

问题1.为什么网上的DES加密算法得到的结果不一样？

这个问题主要涉及编码、输入格式、输出格式、加密模式这几个方面的问题，还有一些细节问题比如空格与回车。首先是编码问题，在线的编码格式一般默认是UTF-8，因此如果网页编码不是UTF-8，则会导致加密的结果不一样。因为DES算法本质上是对二进制内容进行加密，同样的文字经过不同的编码映射成的二进制内容并不相同。其次，是输入格式问题。一般在网页的输入是文本格式（Plain Text），但是许多教程为了方便理解，写的输入格式是16进制，比如 DES算法实例讲解这篇文章里面主要用的是16进制格式作为讲解，对于许多在线工具，明文和密钥输入用的是文本格式。因此，在输入的时候一定要注意区分。然后，是输出格式的问题。有些在线加密工具输出会自动进行Base64编码，这样结果和直接加密的结果完全不同。DES加密的密文是16进制格式的，无法一一对应成ASCII码。密文要么以16进制输出，要么输出一堆乱码，而Base64能将一个较长的16进制数组编码为一个字符串，方便处理。最后，是加密模式的问题。DES本身采用的是ECB（电子密码本）模式，即将加密的数据分成若干组，每组的大小跟加密密钥长度相同，这样密文输出完全由明文和密钥决定。为了进一步加强安全性，有许多安全性扩展，就诞生了别的加密模式，比如加密块链模式CBC、加密反馈模式CFB等等。不同的模式加密结果也会完全不同。在附带一点细节问题，即空格与回车的问题。尤其是在字符串处理的时候，有些字符串会带回车换行（0x0D 0x0A）,这会造成最后一个64位字符块加密有些许差别。还有一些文本框自动（trigger）去除空格，就导致文本中的空格没有被计算在内，导致加密不同。