浅析一个DES源码(WjcDes.cpp)的错误以及测试的重要性
偶很久没有来论坛了,也没有玩关于密码学方面的东西了，主要感觉自己数学知识薄弱，并
不是研究此类问题的料子，况且现在满世界是现成的东西，只要有人指点一下就可以抓来
进行应用，自力更生反而是不重要的东西了。:(
前一阵子，因为需要，重新翻开书本，并对照FIPS46-3，自己写了DES的实现，以前Lordor教我
的时候我没有好好儿学，现在比较吃力:)经过反复抓虫，通过了一些测试证实了代码的正确性。
同时，由于程序员的通病:总要将自己的代码和
别人写的做比较（一是比比速度，二是比比哪个代码质量高容易使用，并且借此机会学习别人
的长处），所以找到了一些DES的实现拿来编译。
其中由王俊川编写的代码引起了我的注意，因为他的代码简练有条理，并且通过ByteToBit扩展，
将bit级别的问题简化成byte级别的操作，而且很容易在VC上面编译。
他的代码在VC知识库(www.vckbase.net)上可以被下载到:
100行的版本: http://www.vckbase.net/code/downcode.asp?id=1897
80行的版本: http://www.vckbase.net/code/downcode.asp?id=1889
实际上二者的核心是一样的，用任何一个都可以的。
以下测试平台为windows xp + MSVC 6.0 +sp5
以下引用为WjcDes.cpp.
代码:
//////////////////////////////////////////////////////////////////////////
/*
Provided by 王俊川, Northeastern University (www.neu.edu.cn)
Email: blackdrn@sohu.com
This product is free for use.
*/
//////////////////////////////////////////////////////////////////////////
#include "memory.h"
#include "WjcDes.h"
//////////////////////////////////////////////////////////////////////////
static void F_func(bool In[32], const bool Ki[48]);// f 函数
static void S_func(bool Out[32], const bool In[48]);// S 盒代替
static void Transform(bool *Out, bool *In, const char *Table, int len);// 变换
static void Xor(bool *InA, const bool *InB, int len);// 异或
static void RotateL(bool *In, int len, int loop);// 循环左移
static void ByteToBit(bool *Out, const char *In, int bits);// 字节组转换成位组
static void BitToByte(char *Out, const bool *In, int bits);// 位组转换成字节组
//////////////////////////////////////////////////////////////////////////
// initial permutation IP
const static 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
};
// final permutation IP^-1
const static char IPR_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
};
// expansion operation matrix
static const 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
};
// 32-bit permutation function P used on the output of the S-boxes
const static 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
};
// permuted choice table (key)
const static char PC1_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
};
// permuted choice key (table)
const static char PC2_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
};
// number left rotations of pc1
const static char LOOP_Table[16] = {
1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1
};
// The (in)famous S-boxes
const static char S_Box[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
};
//////////////////////////////////////////////////////////////////////////
static bool SubKey[16][48];// 16圈子密钥
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// Code starts from Line 121
//////////////////////////////////////////////////////////////////////////
void Des_Run(char Out[8], char In[8], bool Type)
{
static bool M[64], Tmp[32], *Li = &M[0], *Ri = &M[32];
ByteToBit(M, In, 64);
Transform(M, M, IP_Table, 64);
if( Type == ENCRYPT ){
for(int i=0; i<16; i++) {
memcpy(Tmp, Ri, 32);
F_func(Ri, SubKey[i]);
Xor(Ri, Li, 32);
memcpy(Li, Tmp, 32);
}
}else{
for(int i=15; i>=0; i--) {
memcpy(Tmp, Li, 32);
F_func(Li, SubKey[i]);
Xor(Li, Ri, 32);
memcpy(Ri, Tmp, 32);
}
}
Transform(M, M, IPR_Table, 64);
BitToByte(Out, M, 64);
}
void Des_SetKey(const char Key[8])
{
static bool K[64], *KL = &K[0], *KR = &K[28];
ByteToBit(K, Key, 64);
Transform(K, K, PC1_Table, 56);
for(int i=0; i<16; i++) {
RotateL(KL, 28, LOOP_Table[i]);
RotateL(KR, 28, LOOP_Table[i]);
Transform(SubKey[i], K, PC2_Table, 48);
}
}
void F_func(bool In[32], const bool Ki[48])
{
static bool MR[48];
Transform(MR, In, E_Table, 48);
Xor(MR, Ki, 48);
S_func(In, MR);
Transform(In, In, P_Table, 32);
}
void S_func(bool Out[32], const bool In[48])
{
for(char i=0,j,k; i<8; i++,In+=6,Out+=4) {
j = (In[0]<<1) + In[5];
k = (In[1]<<3) + (In[2]<<2) + (In[3]<<1) + In[4];
ByteToBit(Out, &S_Box[i][j][k], 4);
}
}
void Transform(bool *Out, bool *In, const char *Table, int len)
{
static bool Tmp[256];
for(int i=0; i<len; i++)
Tmp[i] = In[ Table[i]-1 ];
memcpy(Out, Tmp, len);
}
void Xor(bool *InA, const bool *InB, int len)
{
for(int i=0; i<len; i++)
InA[i] ^= InB[i];
}
void RotateL(bool *In, int len, int loop)
{
static bool Tmp[256];
memcpy(Tmp, In, loop);
memcpy(In, In+loop, len-loop);
memcpy(In+len-loop, Tmp, loop);
}
void ByteToBit(bool *Out, const char *In, int bits)
{
for(int i=0; i<bits; i++)
Out[i] = (In[i/8]>>(i%8)) & 1;
}
void BitToByte(char *Out, const bool *In, int bits)
{
memset(Out, 0, (bits+7)/8);
for(int i=0; i<bits; i++)
Out[i/8] |= In[i]<<(i%8);
}
//////////////////////////////////////////////////////////////////////////
// Code ends at Line 200
//////////////////////////////////////////////////////////////////////////
我最初的想法是这样的:
因为我的简陋实现是基于bit级别的，在代码中可能费时间比较多，
1)到底和WjcDes.cpp差多少时间，
2)ByteToBit扩展用增长了8倍的空间来减少代码复杂度究竟有没有作用？
我都是一个疑问，所以我准备根据Ronald L.Riverst所建议的DES测试
方法将循环值弄到100万次，然后取时间差来决定。
但是没有想到的是: 在我做测试的时候竟然发现WjcDes.cpp的加密值是错误的，无法通
过Riverst的测试，而且它本身自带的测试虽然能够反解出原字符串，但是加密的值不对。
它的测试代码和输出结果如下：
代码:
main()
{
char key[8]={1,9,8,0,9,1,7},str[8]="WJC DES"; //注意,都是8bytes
puts("Before encrypting");
puts(str);
Des_SetKey(key);
Des_Run(str, str, ENCRYPT);
puts("After encrypting");
puts(str);
/* 中间一段是我加的，用来看Hex结果。
for(int i=0;i<8;i++)
{
printf("%02X",(unsigned char)str[i]);
}
printf("\r\n");
*/
puts("After decrypting");
Des_Run(str, str, DECRYPT);
puts(str);
}
输出结果
Before encrypting
WJC DES
After encrypting
裘.?炳?
F4C318E71EB1FEE6 //这一行是Hex,正确应该为28BA8C22B074BD35
After decrypting
WJC DES
注意，标准的DES按照上面的情况加密后结果是28BA8C22B074BD35，我当时不能确定，
(虽然比较自信，但是我以前也犯过不可饶恕的错误的)所以想找一些别的代码来验证，
但是有些老代码东西移植到VC上面Tei困难了，老少头文件，所以我最后偷懒到Ivan的一台
FreeBSD机器上用OpenSSL作了一个试验：
$ od -t x1 in.txt //我先建立了一个文件，内容是WJC DES加0x00
0000000 57 4a 43 20 44 45 53 00
然后运行openssl,注意 -K 后面是Hex形式的Key
$ openssl enc -nosalt -des -K 0109080009010700 -in in.txt -out out.txt -iv 0
$ od -t x1 out.txt
0000000 28 ba 8c 22 b0 74 bd 35 cb ff 19 6f 40 7a a7 a1
输出结果的前8bytes 证实了这一点:WjcDes.cpp确实存在bug.
读者也许要问，为什么它的加密是错误的，但是能正确是反解呢？
答案是这样的，由于DES使用的Feistel结构，就像一个沙漏，正过来的就能倒过去，即使
加密值错误，但是由于这个结构的关系，程序还是能够通过16次反过来的迭代得到明文。
后面的时间我就用来替它Debug了（偶老毛病又犯了），我首先在wjcdes.cpp中插入了
显示16个48位扩展子密钥的代码.
代码:
void Des_SetKey(const char Key[8])
{
static bool K[64], *KL = &K[0], *KR = &K[28];
printf("Orignal key(From bytes):\r\n");
for(int j=0;j<8;j++)
{
for(int m=7;m>=0;m--)
printf("%d",(Key[j]>>m)&1);
}
printf("\r\nAfter ByteToBit(From bits): \r\n");
ByteToBit(K, Key, 64);
for( j=0;j<64;j++)
{
printf("%d",K[j]);
}
printf("\r\nAfter Transform:\r\n");
Transform(K, K, PC1_Table, 56);
for( j=0;j<56;j++)
{
printf("%d",K[j]);
}
printf("\r\nNow the 16 sub keys:\r\n");
for(int i=0; i<16; i++) {
RotateL(KL, 28, LOOP_Table[i]);
RotateL(KR, 28, LOOP_Table[i]);
Transform(SubKey[i], K, PC2_Table, 48);
for(int j=0;j<48;j++)
{
printf("%d",SubKey[i][j]);
}
printf("\r\n");
}
}
输出结果如下：
Orignal key(From bytes):
0000000100001001000010000000000000001001000000010000011100000000
After ByteToBit(From bits):
1000000010010000000100000000000010010000100000001110000000000000
After Transform:
01110011010000000100000000010000000000000000000000000110
Now the 16 sub keys:
010010100100000000011001000000000000000001000000
000011010100000011100001010000000000000001000000
100100110100000110001000000000001000000000001000
000110000000001110000001000000000001010000000000
000100010001100000001101000010000000000000100000
000000010010000011000100000000000100100000000000
000100000100110010100100000000000000000000010000
110100000010000100100000100000010000000000000000
010000101010100000100110000000010000001000000000
101010001010010000000010000100000000000000000000
011000000000011000101010000000000000000000000100
111000001001000000010000000000000010000010000000
000001001000101001010010001000000000000000000001
001001100111000000010010000000100000000000000010
001011100000010101000000000001000000000100000000
000000110001000101010001000001000000000000000000
可以看出这16个子密钥是错误的，原因在于之前它的ByteToBit将byte扩展成bit时候
弄反了每个字节的高低端，而DES的实现对Message和Key是按字符流形式的操作的，
即从左边第1位一直到右边64位必须按顺序的。
然后我修改了它的BytetoBit，使得16轮子密钥正确产生了，但是接下来，我发现还是
不对，无论我是否修改，S 盒子选择出来的还是有问题，它的输出竟然全部是0000！
有兴趣的读者可以试验一下。请注意一下ByteToBit(Out, &S_Box[i][j][k], 4);
然后可以打印出S盒的输出，看看是否是这样的，原版是否这样。我写到这里已经头昏眼花了。
我分析关键还是Byte到bit的扩展这个功能没有完全实现DES的从左到右的数据流规定。
在调试过程中我曾把S1的输出弄正确了，但是剩下的还有许多错误。我没能够修改。
这里给出正确的16轮密钥
000000000000000000000000000110000000010000001010
000000000000000000000000000000000001010100100100
000000000000000000000000000010000000100010100000
000000000000000000000000010000000100100000010001
000000000000000000000000000000110000000000011000
000000000000000000000000100000010001000100000000
000000000000000000000000000000000000001000100100
000000000000000000000000010100000000100010000100
000000000000000000000000000000001010000000000100
000000000000000000000000101000000010010010000000
000000000000000000000000001010000000001000000011
000000000000000000000000000101100100000000000010
000000000000000000000000000001000000000101000000
000000000000000000000000100000001010000001000000
000000000000000000000000011000001000011000000000
000000000000000000000000000000101001000000001000
以及S盒子输出，Hex
4F D1 1A 58
57 79 94 A4
0B 17 36 DC
B4 DD 44 24
BD 41 0D CC
D9 F4 D3 54
23 E6 1C 2E
FE 55 15 F5
93 54 0A 95
9E 7B 50 7C
45 51 A4 1C
22 A3 46 3B
F6 06 F8 63
75 E1 9F E8
43 4E FC 6A
F4 1E AC 6C
还有正确的中间Ri值
01110101111100000111100010001001
00111000110001100000100111100101
11011100101000000000000001100111
01000010110100011000110001100001
11100111110000101001100111111111
01100100001000000011000101000110
11001011100101011101101010000111
01011111100111101010100010100000
11101000110011010111101111010001
00101001100110100111010101001110
01010000000011010111101001011110
00100101100101010001001110000100
11000010100100111010110000101111
00111010011100100010001000111101
00001010010001111111101101010110
11000000111001001111001000100000
最后说明:
不知道网上有多少软件是直接调用WjcDes.cpp来工作的,如果是这样的话,
而且如果我上述的分析是正确的话,那么这些软件的DES都是不可靠的.如果
自己仅仅在程序内部做个加密还是可以用的. 由于S盒子输出存在大问题,它
的强度有待分析。
估计全世界所有DES源代码加一起没有几千种也有几百种了,他们存在于各式各样
的软件,芯片,IC卡中,所以,我这里就不贴我自己写的代码了.搜索一下就有的.
这个论坛中就有一些实现. 但是请注意,无论啥代码,它的CORE都要经过足够
的测试才能运用!
由于本人水平有限,如有错误欢迎指出,我将修改此文章!
同时感谢Lordor送我的包包，还有Ivan的机机，Kanxue的坛坛.
TiANWEi 20060212 于 看雪论坛(www.pediy.com) 转载请注明出处,谢谢!
附录：
fips46-3.pdf 可以到官方下载：
http://csrc.nist.gov/publications/f...-3/fips46-3.pdf
Ronald L.Riverst的DES测试方法:
http://theory.lcs.mit.edu/~rivest/destest.txt。
openssl:
http://www.openssl.org/
