最新产品展示
DES加密算法的实现
首先代码来自于一个很老的DES算法的实现。这份代码是用很原始的c写成的。我把代码变成了自己感觉比较顺眼的格式，也详细阅读了算法的细节，有些地方做了略微的修改（例如原来的代码里面的移位算法与书上的算法不同，做了修改）。当然还有其他一些改动，不再详细列出。
这个加密算法的实现过程中比较有意思也是比较核心的部分就是如何实现bit的移位。在这份代码里面是采用了两种方法来实现了bit移位。在代码的开头也给出了算法的大致描述，这里不再重复了，可以参考下面贴出的具体代码。
DES算法核心DES.c：
/* 实现了DES算法的加密和解密的过程
*
* 置换算法描述：
* 在这个实现中使用了两种不同的置换算法。
* 在子密钥生成的置换中采用了比较简单易懂的一个算法。是用一个unsigned char[56]的数组来代表这56个bit。这样的好处就是代码比较简单。置换的时候数组的
* 位置就是实际bit位置。左移操作也变成了数组元素的交换过程。这部分代码比较简单，在void kinit( unsigned char * );函数中就是使用这样的算法来实现。
* 而在其他地方，例如首置换，尾置换乃至S盒的置换，都采用了更复杂的置换算法。这些都是处于效率的考虑，毕竟对于一个文件的加密子密钥只需生成
* 一次，而对于每个分组都需进行每个替换。所以这里对于这两种不同需求的置换采用了不同的置换算法。下面以首置换为例大致描述一下这个算法：
* 核心思想是把每一种输入的情况的输出都存储起来。当然如果是一个64位的数据这显然是不可能的。这里也采用了一种分组的思想。例如在首置换里面是
* 对每个半字节(4 bit)的所有情况来存储结果的。三维数组第一维为16（对应于16个半字节），16（对应于半字节的所有可能的组合），8（对应于输出的8
* 字节）。在void perminit(unsigned char perm[16][16][8],unsigned char p[64]);中完成了对这个数组的初始化。确定了前两个维度后剩下的8个字节存储的就是根据这半个
* 字节把结果中应该为1的位置为1，其他位为0的一个mask。初始化之后在实际的操作中只需与上所有输入的半字节对应的mask得到的就是置换后的结果。对
* 于尾置换和S盒的置换虽然细节不同，但实现的思路是一样的。
*
* 修改自下面版本的DES源代码实现：
* Jim Gillogly, May 1977
* Modified 8/84 by Jim Gillogly and Lauren Weinstein to compile with
* post-1977 C compilers and systems
* 张旦峰 PKUCS 2005.10
*/
＃i nclude <stdio.h>
＃i nclude <string.h>
＃i nclude "DES.h"
/** 下面三个都是为了bit置换设置的矩阵，根据置换矩阵得到
*/
unsigned char iperm[16][16][8],fperm[16][16][8]; // 对应于初始置换和尾置换
unsigned char s[4][4096]; // 对应于S盒，从S1到S8
unsigned char p32[4][256][4]; // 对应于f中32bit置换
unsigned char kn[16][6]; // 保存16轮使用的子密钥
/** 下面是加密函数和解密函数
*/
// 用DES加密64-bit从inblock开始的数据，结果放到从outblock开始的地址
void endes( unsigned char * inblock, unsigned char * outblock)
{ unsigned char iters[17][8]; // 存放每轮迭代的结果
unsigned char swap[8]; // 存放左右置换的结果
register int i; // 循环变量
register unsigned char *s, *t;
permute(inblock,iperm,iters[0]); // 进行初始置换
for (i=0; i<16; i++) // 16轮迭代过程
iter(i,iters[i],iters[i+1]);
s = swap; t = &iters[16][4]; // 得到左半部分
*s++ = *t++; *s++ = *t++; *s++ = *t++; *s++ = *t++;
t = &iters[16][0]; // 得到右半部分
*s++ = *t++; *s++ = *t++; *s++ = *t++; *s++ = *t++;
permute(swap,fperm,outblock); // 进行尾置换
}
// 用DES解密64-bit从inblock开始的数据，结果放到从outblock开始的地址
void dedes( unsigned char * inblock, unsigned char * outblock)
{ unsigned char iters[17][8]; // 存放每轮迭代的结果
unsigned char swap[8]; // 存放左右交换的结果
register int i; // 循环变量
register unsigned char *s, *t;
permute(inblock,iperm,iters[0]); // 进行初始置换
for (i=0; i<16; i++) // 16轮迭代过程，不过在解密的时候用的子密钥次序是相反的
iter(15-i,iters[i],iters[i+1]);
s = swap; t = &iters[16][4]; // 得到左半部分
*s++ = *t++; *s++ = *t++; *s++ = *t++; *s++ = *t++;
t = &iters[16][0]; // 得到右半部分
*s++ = *t++; *s++ = *t++; *s++ = *t++; *s++ = *t++;
permute(swap,fperm,outblock); // 进行尾置换
}
/** DES算法中的一些具体的规范数据，包括置换矩阵，密钥置换表，密钥生成中的左移位数，8个S盒
*/
unsigned char ip[] // 初始置换矩阵P
= { 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 };
unsigned char fp[] // 尾置换矩阵F
= { 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 };
unsigned char pc1[] // 密钥置换表1
= { 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 };
unsigned char totrot[] // pc1结果每轮需要左移的位数
= { 1,1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
unsigned char pc1m[56]; // 存储子密钥生成过程中经过PC-1置换后的结果，每个取值对应于一个bit
unsigned char pcr[56]; // 存储子密钥生成过程中左移后的结果，每个取值对应于一个bit
unsigned char pc2[] // 密钥置换表2
= { 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 };
unsigned char si[8][64] // 48->32 bit压缩置换（8个S盒）
= { // S[1]
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,
// S[2]
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,
// S[3]
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,
// S[4]
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,
// S[5]
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,
// S[6]
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,
// S[7]
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,
// S[8]
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 p32i[] // P盒置换
= { 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 };
// 位操作中需要使用的数组，用来在bit的位置和实际值之间的映射
int bytebit[] // 注意位置越靠左值越大
= { 0200,0100,040,020,010,04,02,01 };
int nibblebit[] = { 010,04,02,01 };
/** 加密和解密函数中用到的子过程函数
*/
// 用置换矩阵perm来把inblock的数据置换后放到outblock中去
void permute( unsigned char * inblock, unsigned char perm[16][16][8], unsigned char * outblock)
{ register int i,j;
register unsigned char *ib, *ob;
register unsigned char *p, *q;
for (i=0, ob = outblock; i<8; i++)
*ob++ = 0; // 清零
ib = inblock;
for (j = 0; j < 16; j += 2, ib++) // 对每个输入的半byte，也就是4bit，每次处理2个
{ ob = outblock;
p = perm[j][(*ib >> 4) & 017]; // 得到对应于左半部分和右半部分的mask
q = perm[j + 1][*ib & 017];
for (i = 0; i < 8; i++) // 处理输出后的每个字节
*ob++ |= *p++ | *q++; // 对mask做或得到结果
}
}
// 一次迭代操作对应的函数
void iter(int num, unsigned char * inblock, unsigned char * outblock)
{
unsigned char fret[4];
register unsigned char *ib, *ob, *fb;
ob = outblock; ib = &inblock[4];
f(ib, num, fret); // 迭代的主要变形过程，包括了扩展，与子密钥的异或，选择压缩和置换的整个过程
*ob++ = *ib++; // 得到一轮迭代的左半部分
*ob++ = *ib++;
*ob++ = *ib++;
*ob++ = *ib++;
ib = inblock; fb = fret; // 得到一轮迭代的右半部分
*ob++ = *ib++ ^ *fb++;
*ob++ = *ib++ ^ *fb++;
*ob++ = *ib++ ^ *fb++;
*ob++ = *ib++ ^ *fb++;
}
// DES加密的最主要步骤，包括了扩展，与子密钥的异或，选择压缩和置换的整个过程
void f(unsigned char * right, int num, unsigned char * fret)
{
register unsigned char *kb, *rb, *bb; // 分别指向本轮的子密钥，结果和扩展后的48bit串p
unsigned char bigright[6]; // 存放扩展后的48bit
unsigned char result[6]; // 存放本轮迭代的结果
unsigned char preout[4]; // 存放32bit置换后的结果
kb = kn[num]; // 指针初始化
bb = bigright;
rb = result;
expand(right,bb); // 选择扩展运算扩展到48bit
*rb++ = (*bb++) ^ (*kb++); // 上面的结果和子密钥48bit做异或运算
*rb++ = (*bb++) ^ (*kb++);
*rb++ = (*bb++) ^ (*kb++);
*rb++ = (*bb++) ^ (*kb++);
*rb++ = (*bb++) ^ (*kb++);
*rb++ = (*bb++) ^ (*kb++);
contract(result,preout); // 使用S盒压缩48位到32位，核心步骤
perm32(preout,fret); // 最后的32bit置换
}
// 将32bit扩展到48bit的扩展函数
void expand( unsigned char * right, unsigned char * bigright)
{
register unsigned char *bb, *r, r0, r1, r2, r3;
bb = bigright;
r = right; r0 = *r++; r1 = *r++; r2 = *r++; r3 = *r++;
*bb++ = ((r3 & 0001) << 7) | // 32
((r0 & 0370) >> 1) | // 1 2 3 4 5
((r0 & 0030) >> 3); // 4 5
*bb++ = ((r0 & 0007) << 5) | // 6 7 8
((r1 & 0200) >> 3) | // 9
((r0 & 0001) << 3) | // 8
((r1 & 0340) >> 5); // 9 10 11
*bb++ = ((r1 & 0030) << 3) | // 12 13
((r1 & 0037) << 1) | // 12 13 14 15 16
((r2 & 0200) >> 7); // 17
*bb++ = ((r1 & 0001) << 7) | // 16
((r2 & 0370) >> 1) | // 17 18 19 20 21
((r2 & 0030) >> 3); // 20 21
*bb++ = ((r2 & 0007) << 5) | // 22 23 24
((r3 & 0200) >> 3) | // 25
((r2 & 0001) << 3) | // 24
((r3 & 0340) >> 5); // 25 26 27
*bb++ = ((r3 & 0030) << 3) | // 28 29
((r3 & 0037) << 1) | // 28 29 30 31 32
((r0 & 0200) >> 7); // 1
}
// 使用S盒将48bit压缩到32bit
void contract( unsigned char * in48, unsigned char * out32)
{ register unsigned char *c;
register unsigned char *i;
register int i0, i1, i2, i3, i4, i5; // 48bit对应的6个字节
i = in48;
i0 = *i++; i1 = *i++; i2 = *i++; i3 = *i++; i4 = *i++; i5 = *i++;
c = out32;
*c++ = s[0][07777 & ((i0 << 4) | ((i1 >> 4) & 017 ))];
*c++ = s[1][07777 & ((i1 << 8) | ( i2 & 0377 ))];
*c++ = s[2][07777 & ((i3 << 4) | ((i4 >> 4) & 017 ))];
*c++ = s[3][07777 & ((i4 << 8) | ( i5 & 0377 ))];
}
// 最后的32-bit置换实现
void perm32( unsigned char * inblock,unsigned char * outblock)
{
register int j;
register unsigned char *ib, *ob;
register unsigned char *q;
ob = outblock; // 清零
*ob++ = 0; *ob++ = 0; *ob++ = 0; *ob++ = 0;
ib=inblock;
for (j=0; j<4; j++, ib++) // 对每一个byte
{ q = p32[j][*ib & 0377]; // 得到对应的mask
ob = outblock;
*ob++ |= *q++; // 与上mask得到结果
*ob++ |= *q++;
*ob++ |= *q++;
*ob++ |= *q++;
}
}
/** 下面是置换数组的初始化过程
*/
// 初始化与ip，fp对应的置换数组
void perminit(unsigned char perm[16][16][8],unsigned char p[64])
{ register int l, j, k;
int i,m;
for (i=0; i<16; i++) // 清零
for (j=0; j<16; j++)
for (k=0; k<8; k++)
perm[i][j][k]=0;
for (i=0; i<16; i++) // 对每个半字节也就是4bit
for (j = 0; j < 16; j++) // 对4bit每种可能的组合
for (k = 0; k < 64; k++) // 对每个输出结果64bit中的可能位置
{ l = p[k] - 1; // 这个位置的bit在原来数组中的位置
if ((l >> 2) != i) // 这个位置如果不是在现在的半字节位置中，直接跳出
continue;
if (!(j & nibblebit[l & 3])) // 在这个组合中的对应位如果为0，也不用处理
continue;
m = k & 07; // 这个位置在byte中的位置
perm[i][j][k>>3] |= bytebit[m]; // 写入mask
}
}
// 初始化S盒数组
void sinit()
{ register int i,j;
for (i=0; i<4; i++) // 每次处理12bit，压缩后刚好是一个字节
for (j=0; j<4096; j++) // 对每一个可能的值，创建数组项
s[i][j]=(getcomp(i*2,j>>6)<<4) |
(017&getcomp(i*2+1,j&077));
// 每次得到一个字节的结果
}
// 从S盒中得到一个压缩后的数，k是S盒号，v是6bit输入
int getcomp(int k,int v)
{ register int i,j; // i对应S盒中的行，j代表S盒中的列
i=((v&040)>>4)|(v&1); // 第一bit和最后bit构成行
j=(v&037)>>1; // 中间4bit构成列
return (int) si[k][(i<<4)+j]; // 从S盒中得到结果
}
// 初始化32bit置换数组
void p32init()
{ register int l, j, k;
int i,m;
for (i=0; i<4; i++) // 清零
for (j=0; j<256; j++)
for (k=0; k<4; k++)
p32[i][j][k]=0;
for (i=0; i<4; i++) // 对每一个字节
for (j=0; j<256; j++) // 对这个字节的每一种可能
for (k=0; k<32; k++) // 对输出的每一个bit
{ l=p32i[k]-1; // 应该在原来的位置
if ((l>>3)!=i) // 这个位置如果不是在现在的字节位置中，直接跳出
continue;
if (!(j&bytebit[l&07])) // 在这个组合中的对应位如果为0，也不用处理
continue;
m = k & 07; // 在输出中的位置
p32[i][j][k>>3] |= bytebit[m]; // 写入mask
}
}
/** 密钥生成相关函数函数
*/
// 子密钥生成函数
void kinit( unsigned char * key)
{ register int i,j,l;
int m;
for (j=0; j<56; j++) // 得到PC-置换后的56bit1
{ l=pc1[j]-1; // 原来的位置
m = l & 07; // 得到这个位置在字节中的位置
pc1m[j]=(key[l>>3] & // 将这个位置的值变为key对应的bit
bytebit[m])
? 1 : 0;
}
for (i=0; i<16; i++) // 子密钥数组清零
for (j=0; j<6; j++)
kn[i][j]=0;
for (i=0; i<16; i++) // 生成每轮使用的子密钥
{ for (j=0; j<56; j++) // 对置换后的结果的每个bit左移适当的位数
pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
// 左半部分和右半部分是分开移动的
for (j=0; j<48; j++) // 对每个bit使用PC-2对结果进行置换得到子密钥
if (pcr[pc2[j]-1]) // 看子密钥的j bit所对应的bit是否为1
{ l= j & 07; // 是的话找到在字节中的位置
kn[i][j>>3] |= bytebit[l]; // 在恰当的字节写上这个bit
}
}
}
// DES算法结构初始化函数，使用DES之前用密钥key调用这个函数完成所有初始化
void desinit( unsigned char * key)
{
perminit(iperm,ip); // 初始化首置换矩阵
perminit(fperm,fp); // 初始化尾置换矩阵
kinit(key); // 初始化所有子密钥
sinit(); // 初始化S盒矩阵
p32init(); // 初始化f中使用的32bit置换矩阵
}
实际使用的时候需要先根据密钥调用desinit函数，随后使用endes()或者dedes()进行加密或者解密工作。作为示例下面是一个最简单的ECB模式下DES算法的实现代码：
ECB.c：
/* DES算法ECB模式的实现
*
* 张旦峰 PKUCS 2005.10
*/
＃i nclude <stdio.h>
＃i nclude "DES.h"
unsigned char key[8], plain[8], processed[8];
// 首先选择加密或是解密,输入密钥，输入输出文件名
// 随后从输入文件中读入数据，将数据用DES加密/解密后输出到输出文件。
int main()
{ int count, flag, opt;
char inname[20], outname[20];
FILE * in, * out;
count = 8;
flag = 1;
printf ( "Encryption or decryption? (1 for Encryption, 0 for decryption)\n" );
scanf ( "%d", &opt );
if ( opt!=0 && opt!=1 ) {
printf ( "Option error.\n" );
return 1;
}
printf ( "Input 64bit key:\n" ); // 输入密钥并完成初始化
scanf ( "%s", key);
desinit(key); // 完成DES算法用到的数组和子密钥的初始化
printf("Input input file name:\n"); // 得到输入和输出文件名
scanf ( "%s", inname);
printf("Input output file name:\n");
scanf ( "%s", outname);
if ((in = fopen(inname, "rb")) == NULL) // 打开文件
{ printf("Can't open %s.\n", inname);
exit(1);
}
if ((out = fopen(outname, "wb")) == NULL)
{ printf("Can't open %s.\n", outname);
return 1;
}
while ( flag ) {
count = fread( plain, sizeof( char ), 8, in ); // 读入64bit
if ( count == 0 ) // 说明文件已经读完
break;
for ( ; count<8 ; count++ ) { // 如果位数不足用0补足，并设置标志，下一轮退出
plain[count]=0;
flag = 0;
}
if ( opt ) // 加密过程
endes( plain, processed);
else
dedes( plain, processed); // 解密过程
fwrite ( processed, sizeof( char ), 8, out );
}
printf("Process complete.\n", count);
fclose( in);
fclose( out);
return 1;
}