03_DES源码分析
03_DES源码分析
一、DES加密步骤
这里以一个分组为例：
- 明文为：
0123456789ABCDEF（这个是HEX编码之后的数据） - 密钥为：
133457799BBCDFF1
1. 子密钥生成
首先将密钥转成二进制：
1 | 00110001 00110011 00110011 00110100 00110101 00110111 00110111 00111001 00111001 01000010 01000010 01000011 01000100 01000110 01000110 00110001 |
- 根据PC1表进行对密钥的重新排列：
1 | int PC1_Table[56] = |
这里可以看到PC1表当中虽然只有56个元素，但是出现了63这些大于56的索引，实际上是因为密钥当中mod 8 = 0的位置作为奇偶校验位，是不取的，这个PC1当中就少了8，16，24，32，40，48，56，64这8个索引，而且这个表的索引值是从1开始的。
首先会遍历这个PC1表，根据当中的索引值在原来密钥二进制串当中找到对应位置的比特位，然后按顺序编排（也就是密钥当中57的比特位放到第1位，49的放到第2位，以此类推）。然后编排成下面这个结果：
1 | 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111 |
此时就只剩下56位了，并且每组7位。然后分成左右两个部分：
1 | C0 = 1111000 0110011 0010101 0101111 |
接着根据循环左移规定的位数，得到C1D0到C16D16：
1 | key_shift = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1] |
经过循环左移的C1D1是这样的：
1 | C1 = 1110000 1100110 0101010 1011111 |
接着将C1D1拼接起来进行PC2表的置换：
1 | 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110 |
PC2表：
1 | int PC2_Table[48] = { |
此时就只剩下48位了，经过PC2重排CnDn的子密钥成为Kn，用作DES后续的16轮运算中，第n轮就是用Kn, 16个子密钥为：
1 | K1 = 000110 110000 001011 101111 111111 000111 000001 110010 |
2. 明文编排
先将明文（已经在内存中的值）转成二进制：
1 | 00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111 |
根据IP表进行初始置换：
1 | int IP_Table[64] = { |
明文重新排列后的结果：
1 | 11001100 00000000 11001100 11111111 11110000 10101010 11110000 10101010 |
3. 明文的运算
首先将明文分成左右两部分L0 和 R0：
1 | L0：11001100 00000000 11001100 11111111 |
接着进行16轮Feistel的迭代，逻辑如下图：
每轮迭代的公式如下：
$L_i = R_{i-1}$
$R_i = L_{i-1} \oplus F(R_{i-1},K_i)$
F函数：
这里传入F函数传入的是$R_{i-1}$还有$K_{i}$，但是$R_{i-1}$长度为32比特位，而K为48比特位，此时就需要对$R_{i-1}$进行扩展了，这里扩展使用的是E表：
1 | int E_Table[48] = { |
扩展之后的密钥称为E(R0)，然后和K进行异或操作，也就是$E(R0) \oplus K_i$：
1 | E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101 |
紧接着会将这48位分成8组，每组6位：
1 | B1 = 011000 |
接着在S盒当中查表，查表规则如下，$B_i$当中的i就是查哪张表，然后6位二进制的$b_0b_5$作为行索引，中间四位当作列索引在S盒当中查表：
1 | int S_Box[8][4][16] = { |
最终原先的8比特会变成4比特。上面的48位经过查表之后会变成：
1 | 0101 1100 1000 0010 1011 0101 1001 0111 |
得到的这个结果再经过P表的重排得到的值就是F函数的输出：
1 | int P_Table[32] = { |
新值：
1 | 0010 0011 0100 1010 1010 1001 1011 1011 |
有这个公式：$F = P(S(K_i \oplus R_{i-1})$
经过16轮之后得到如下的数据：
1 | L16:01000011 01000010 00110010 00110100 |
然后按照$R_{16}L_{16}$的方式拼接，得到的二进制比特串与FP表进行置换：
1 | int FP_Table[64] = { |
这个FP表的置换其实就是初始置换的逆运算，将上面拼接后的01比特串经过置换之后就会输出：
1 | 85 e8 13 54 0f 0a b4 05 |
这个就是单个分组经过DES加密之后的结果：
后半部分是填充。
二、DES源码分析
DES加密的源码有非常多不同的版本，只要能加密出来就可以，下面是随便找的一个DES加密源码。这里使用的是一个分组，ECB的模式加密。
1. C调用DES
1 | unsigned char key[8] = "12345678"; |
2. 子密钥生成函数
1 | void generateSubKeys(const unsigned char* key) { |
首先通过permute将key进行PC1置换，并将结果存储到K56当中。接着通过setBit将K56分成两组存到C,D当中。接着就是16轮循环来生成16个K值。
permute函数如下：
1 | void permute(const unsigned char* input, unsigned char* output, const int* table, int n) |
先清空output，这里用(n+7)/8是因为，传入的n是比特位的数量，如果超过n/8字节则需要再多一个字节，这里直接加7为了就是加上这个多的字节。
接着就是使用getBit从input当中获取对应位的比特了，getBit函数如下：
1 | int getBit(const unsigned char* data, int pos) |
这里取对应的比特位是通过先/8获取所在字节位置，再通过位移之后&1来获取对应的比特位的。同理，setBit的原理也差不多：
1 | void setBit(unsigned char* data, int pos, int val) |
获取到对应的比特位之后，通过或运算和与运算来控制对应位是0还是1。
子密钥生成的最终过程大致就如上面一样。最终会生成16个K存放到subKeys当中
3. 加密过程
1 | void processBlock(unsigned char* block, int isEncrypt) |
首先就是先通过permute将分组明文进行IP置换，然后存储到ipBlock当中，然后分组存放到L和R当中。接着就是16轮迭代，判断是加密还是解密来选择子密钥的顺序。
然后开始进行运算：$L_i=R_{i-1}$，$R_i = L_{i-1} \oplus F(R_{i-1},K_i)$，最后更新L，R。最后将RL拼接，并进行逆置换就得出密文了。
feistelFunc函数实现细节如下：
1 | void feistelFunc(const unsigned char* R, const unsigned char* K, unsigned char* output) |
DES的加密过程大致如上。
4. 注意事项
在开始介绍子密钥生成的过程的时候，提及到有几个位是做奇偶校验不要的，所以会发生不同的密钥也可以加解密的问题，例如03254769就是一个12345678的另一个密钥(可以用来解12345678加密出来的密文)。
三、3DES算法
这个就是进行3次DES运算，首先进行DES加密，再进行DES解密，最后进行DES加密。密钥长度为24字节。每次运算使用密钥当中的8个字节，所以密钥当中不要出现相同的分组，如果密钥三个分组一样的话，这个3DES实际上就只是一次DES加密而已。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 x0r's blog！