深入浅出DES
前言
本来DES算法我打算写成从做题到出题再到做题系列，但是由于没有找到好的例子，也就无从入手，而且DES算法本身已经十分的复杂，仅仅通过观察数据如何变化是很难发现端倪的。
不过我在此期间认真的学习了DES算法，了解其加密的细节。
接下来我希望我这篇浅显的文章能帮助大家对DES的理解有所帮助。
原理简介
我主要是通过阅读图解密码技术这本书来学习的，建议大家先去学习了解一下。
首先我这不会去详细的说DES加解密的原理，毕竟已经有人做了这些工作，这里只做简介。
这篇参考文章建议认真阅读一下，可以结合着这篇参考文章和我的分析过程来认识了解DES。
DES是一种将64比特的明文加密成64比特的密文的对称密码算法，它的密钥长度是56比特。但从严格来说，DES的密钥长度是64比特，但由于每隔7比特会设置一个用于错误检查的比特，因此实质上其密钥长度是56比特。
DES是以64比特的明文为一个单位来进行加密的。这一个单位称为分组，一般来说以分组为单位进行处理的密码算法称为分组密码。
DES每次只能加密64bit的数据，如果要加密的明文比较长，就需要对DES加密进行迭代，而迭代的具体方式，就称为模式。
这里只对64位明文进行加密，因此不涉及迭代模式。
加密过程
DES的结构也称为Feistel网络
在Feistel网络中，加密的各个步骤称为轮，整个加密过程就是进行若干次轮的循环
每一轮都需要使用一个不同的子密钥
轮函数的作用是根据右侧和子密钥生成对左侧进行加密的比特序列，它是密码系统的核心。
一轮的具体计算步骤：
- 将输入的数据等分为左右两部分
- 将输入的右侧直接发送到输出的右侧
- 将输入的右侧发送到轮函数
- 轮函数根据右侧数据和子密钥，计算出一串看上去是随机的比特序列
- 将上一步得到的比特序列与左侧数据进行xor运算，并将结果作为加密后的左侧
但是这样右侧的数据根本就没有加密，因此我们需要用不同的子密钥对一轮处理重复若干次，并在每次处理之间将左侧和右侧的数据对调。
如下图：
整个过程简述如下：
>初始明文处理阶段：
明文初始置换 64位
置换后的明文分为两组 32位*2
>子密钥产生阶段：
输入的密钥 64位
根据置换选择表得到密钥 28位*2
根据循环左移表，将密钥循环左移
将两个分开的密钥合并成56位，根据置换选择表2得到48位的子密钥
回到第三步根据轮数进行不同的左移，知道循环16轮，产生16个子密钥
>加密阶段：
对经过初始置换并分组的明文的一组进行E-盒拓展为48位
将拓展后的明文同对应的子密钥进行异或得到密文 48位
密文经过S-盒由48位变为32位
32位的密文经过P-盒乱序
交换左右两分组，进入下一轮加密阶段，整个加密阶段循环16轮
>最后密文逆置换阶段：
将以上操作所得的密文进行逆置换得到最终的密文
>以上过程就是对一个分组(64位)的DES加密一定要去看那篇参考文章，这里只是自己的总结
接下来就一起在IDA中动态跟踪数据流，瞅瞅DES长啥样。
IDA动态调试跟踪数据流
IDA跟进
首先对明文进行初始置换
for ( i = 0; i <= 63; ++i )
init_perm_res = (input >> (64 - byte_602060[i])) & 1 | 2 * init_perm_res;
其结果为0xFFDE6AE700FF0550
而后对置换后的明文分成左右两部分
L = __PAIR__(init_perm_res, HIDWORD(init_perm_res));
左边0xFFDE6AE7,右边0x00FF0550
暂时先不管左右两部分，我们先来生成16个子密钥
对密钥进行选择置换，此时会将64位的密钥转换为56位的密钥，也就是剔除了每个字节的最后一位。
for ( ia = 0; ia <= 55; ++ia )
permuted_choice_1 = (key >> (64 - PC1[ia])) & 1 | 2 * permuted_choice_1;
得到的结果为0xFFF6667880F
而后对56位的密钥进行分组，分为C0，D0且都为28位
C = (permuted_choice_1 >> 28) & 0xFFFFFFF;
D = permuted_choice_1 & 0xFFFFFFF;
C0为0xFFF，D0为0x667880
注意一下，这里都是位运算，C0和D0都是28位，但是用来存储其值的变量应该是32位的。
>>> 0xFFF6667880F>>28
65526
>>> hex(65526)
'0xfff6'
但是最后一字节需要去掉哦而后对C0和D0分别根据shift table进行移位操作
for ( j = 0; iteration_shift[ib] > j; ++j )
{
C = 2 * C & 0xFFFFFFF | (C >> 27) & 1;
D = 2 * D & 0xFFFFFFF | (D >> 27) & 1;
}
其结果为0x1FFE和0xCCF101E
而后将其结果合并组成56位的数，之后通过选择置换表2，将56位变成48位
sub_key[ib] = 0LL;
for ( ja = 0; ja <= 47; ++ja )
{
sub_key[ib] *= 2LL;
sub_key[ib] |= ((((unsigned __int64)C << 28) | D) >> (56 - PC2[ja])) & 1;
}
这样便产生了16个48位的子密钥
但此时明文才只是经过了初始置换并进行了分组，所以需要对32位的明文分组拓展为48位。
s_input = 0LL;
for ( jb = 0; jb <= 47; ++jb )
s_input = (HIDWORD(L) >> (32 - E[jb])) & 1 | 2 * s_input;
经过E盒的拓展之后，结果如下：
17FE80AAA0
之后便可以将子密钥和经过拓展之后明文异或
s_inputa = v3 ^ s_input;
其结果为0x503B52D78062
而后我们需要将异或的结果变为32位的数，这时S-盒就登场了
s_inputa = v3 ^ s_input;
for ( jc = 0; jc <= 7; ++jc )
s_output = S[64 * (signed __int64)jc
+ 16
* (char)(((char)((s_inputa & (145135534866432LL >> 6 * (unsigned __int8)jc)) >> (-6
* (unsigned __int8)jc
+ 42)) >> 4) | ((s_inputa & (145135534866432LL >> 6 * (unsigned __int8)jc)) >> (-6 * (unsigned __int8)jc + 42)) & 1)
+ (char)((s_inputa & (131941395333120LL >> 6 * (unsigned __int8)jc)) >> (-6 * (unsigned __int8)jc + 43))] & 0xF | 16 * s_output;S-盒是一个64位的数组，它的作用是：输入一个6位的数转换成4位然后输出，这样经过8个S-盒就可以将原本6*8的数据转化为4*8的数据了。
其结果为0x6D8201DB
然后在将其结果经过P盒的置换
for ( jd = 0; jd <= 31; ++jd )
f_function_res = (s_output >> (32 - P[jd])) & 1 | 2 * f_function_res;
结果为0xA5AEB11
而后将加密后的结果同经过初始置换的另一个分组R0进行异或，并将结果保存到R1中，同时将R0赋值给L1，进行下一轮
注意哦，此时子密钥已经全部生成了，因此只需要在进行E-盒拓展，子密钥异或，S盒变换，P盒置换即可，然后再次左右两边异或交换
temp = HIDWORD(L);
HIDWORD(L) = f_function_res ^ L;
LODWORD(L) = temp;
结果为0xF58481F6
经过16轮之后，一次加密过程基本上已经完成了，最后通过逆置换便可以得到密文
for ( id = 0; id <= 63; ++id )
inv_init_perm_res = (L >> (64 - PI[id])) & 1 | 2 * inv_init_perm_res;
return inv_init_perm_res;
最后加密的结果为0xFD181E19466FE937
到此DES的整个加密过程就是如此，其解密过程只需要将子密钥的顺序倒序即可。
文中所用代码如下：
/*
* Data Encryption Standard
* An approach to DES algorithm
*
* By: Daniel Huertas Gonzalez
* Email: [email protected]
* Version: 0.1
*
* Based on the document FIPS PUB 46-3
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define LB32_MASK 0x00000001
#define LB64_MASK 0x0000000000000001
#define L64_MASK 0x00000000ffffffff
#define H64_MASK 0xffffffff00000000
/* Initial Permutation Table */
static char IP[] = {
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
};
/* Inverse Initial Permutation Table */
static char PI[] = {
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 table */
static char E[] = {
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
};
/* Post S-Box permutation */
static char 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
};
/* The S-Box tables */
static char S[8][64] = {{
/* 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
}};
/* Permuted Choice 1 Table */
static char PC1[] = {
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 2 Table */
static char PC2[] = {
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
};
/* Iteration Shift Array */
static char iteration_shift[] = {
/* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 */
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
/*
* The DES function
* input: 64 bit message
* key: 64 bit key for encryption/decryption
* mode: 'e' = encryption; 'd' = decryption
*/
uint64_t des(uint64_t input, uint64_t key, char mode) {
int i, j;
/* 8 bits */
char row, column;
/* 28 bits */
uint32_t C = 0;
uint32_t D = 0;
/* 32 bits */
uint32_t L = 0;
uint32_t R = 0;
uint32_t s_output = 0;
uint32_t f_function_res = 0;
uint32_t temp = 0;
/* 48 bits */
uint64_t sub_key[16] = {0};
uint64_t s_input = 0;
/* 56 bits */
uint64_t permuted_choice_1 = 0;
uint64_t permuted_choice_2 = 0;
/* 64 bits */
uint64_t init_perm_res = 0;
uint64_t inv_init_perm_res = 0;
uint64_t pre_output = 0;
/* initial permutation */
for (i = 0; i < 64; i++) {
init_perm_res <<= 1;
init_perm_res |= (input >> (64-IP[i])) & LB64_MASK;
}
L = (uint32_t) (init_perm_res >> 32) & L64_MASK;
R = (uint32_t) init_perm_res & L64_MASK;
/* initial key schedule calculation */
for (i = 0; i < 56; i++) {
permuted_choice_1 <<= 1;
permuted_choice_1 |= (key >> (64-PC1[i])) & LB64_MASK;
}
C = (uint32_t) ((permuted_choice_1 >> 28) & 0x000000000fffffff);
D = (uint32_t) (permuted_choice_1 & 0x000000000fffffff);
/* Calculation of the 16 keys */
for (i = 0; i< 16; i++) {
/* key schedule */
// shifting Ci and Di
for (j = 0; j < iteration_shift[i]; j++) {
C = 0x0fffffff & (C << 1) | 0x00000001 & (C >> 27);
D = 0x0fffffff & (D << 1) | 0x00000001 & (D >> 27);
}
permuted_choice_2 = 0;
permuted_choice_2 = (((uint64_t) C) << 28) | (uint64_t) D ;
sub_key[i] = 0;
for (j = 0; j < 48; j++) {
sub_key[i] <<= 1;
sub_key[i] |= (permuted_choice_2 >> (56-PC2[j])) & LB64_MASK;
}
}
for (i = 0; i < 16; i++) {
/* f(R,k) function */
s_input = 0;
for (j = 0; j< 48; j++) {
s_input <<= 1;
s_input |= (uint64_t) ((R >> (32-E[j])) & LB32_MASK);
}
/*
* Encryption/Decryption
* XORing expanded Ri with Ki
*/
if (mode == 'd') {
// decryption
s_input = s_input ^ sub_key[15-i];
} else {
// encryption
s_input = s_input ^ sub_key[i];
}
/* S-Box Tables */
for (j = 0; j < 8; j++) {
// 00 00 RCCC CR00 00 00 00 00 00 s_input
// 00 00 1000 0100 00 00 00 00 00 row mask
// 00 00 0111 1000 00 00 00 00 00 column mask
row = (char) ((s_input & (0x0000840000000000 >> 6*j)) >> 42-6*j);
row = (row >> 4) | row & 0x01;
column = (char) ((s_input & (0x0000780000000000 >> 6*j)) >> 43-6*j);
s_output <<= 4;
s_output |= (uint32_t) (S[j][16*row + column] & 0x0f);
}
f_function_res = 0;
for (j = 0; j < 32; j++) {
f_function_res <<= 1;
f_function_res |= (s_output >> (32 - P[j])) & LB32_MASK;
}
temp = R;
R = L ^ f_function_res;
L = temp;
}
pre_output = (((uint64_t) R) << 32) | (uint64_t) L;
/* inverse initial permutation */
for (i = 0; i < 64; i++) {
inv_init_perm_res <<= 1;
inv_init_perm_res |= (pre_output >> (64-PI[i])) & LB64_MASK;
}
return inv_init_perm_res;
}
void str2hex(char *source,char *dest,int keyLen){
uint8_t i;
uint8_t highByte, lowByte;
for (i = 0; i < keyLen; i++)
{
highByte = source[i] >> 4;
lowByte = source[i] & 0x0f ;
highByte += 0x30;
if (highByte > 0x39)
dest[i * 2] = highByte + 0x07;
else
dest[i * 2] = highByte;
lowByte += 0x30;
if (lowByte > 0x39)
dest[i * 2 + 1] = lowByte + 0x07;
else
dest[i * 2 + 1] = lowByte;
}
return ;
}
int main(int argc, const char * argv[]) {
int i;
uint64_t input = 0x7177657274797569;
uint64_t key = 0x3132333435363738;
uint64_t result = 0x0000000000000000;
// char * in = "qwertyui";
// char in_hex[17];
// in_hex[16]=0;
// str2hex(in,in_hex,8);
// printf("0x%s",in_hex);
// result = des(input, key, 'e');
// printf ("E: 0x%016llx\n", result);//0x71d05d44594773b0
//result = des(result, key, 'd');
//printf ("D: %016llx\n", result);
char a[]="qwertyui";
char * reset;
// result = des(input, key, 'e');
// printf ("E: 0x%016llx\n", result);//0x71d05d44594773b0
// result = des(result, key, 'd');
// printf ("D: 0x%016llx\n", result);
uint64_t * b = a;
uint64_t re = *b;
printf("0x%016llx\n",re);
result = des(re, key, 'e');
printf ("E: 0x%016llx\n", result);
result = des(result, key, 'd');
printf ("D: 0x%016llx\n", result);
exit(0);
}魔改DES
我们已经如此详尽的描述了DES，相信对其稍微改变下也不是难事了。
我考虑了一下，最后将P-盒删除了，解密也是同样的。
最后魔改之后的代码如下：
/*
* Data Encryption Standard
* An approach to DES algorithm
*
* By: Daniel Huertas Gonzalez
* Email: [email protected]
* Version: 0.1
*
* Based on the document FIPS PUB 46-3
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define LB32_MASK 0x00000001
#define LB64_MASK 0x0000000000000001
#define L64_MASK 0x00000000ffffffff
#define H64_MASK 0xffffffff00000000
/* Initial Permutation Table */
static char IP[] = {
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
};
/* Inverse Initial Permutation Table */
static char PI[] = {
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 table */
static char E[] = {
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
};
/* Post S-Box permutation */
static char 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
};
/* The S-Box tables */
static char S[8][64] = {{
/* 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
}};
/* Permuted Choice 1 Table */
static char PC1[] = {
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 2 Table */
static char PC2[] = {
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
};
/* Iteration Shift Array */
static char iteration_shift[] = {
/* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 */
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
/*
* The DES function
* input: 64 bit message
* key: 64 bit key for encryption/decryption
* mode: 'e' = encryption; 'd' = decryption
*/
uint64_t des(uint64_t input, uint64_t key, char mode) {
int i, j;
/* 8 bits */
char row, column;
/* 28 bits */
uint32_t C = 0;
uint32_t D = 0;
/* 32 bits */
uint32_t L = 0;
uint32_t R = 0;
uint32_t s_output = 0;
uint32_t f_function_res = 0;
uint32_t temp = 0;
/* 48 bits */
uint64_t sub_key[16] = {0};
uint64_t s_input = 0;
/* 56 bits */
uint64_t permuted_choice_1 = 0;
uint64_t permuted_choice_2 = 0;
/* 64 bits */
uint64_t init_perm_res = 0;
uint64_t inv_init_perm_res = 0;
uint64_t pre_output = 0;
/* initial permutation */
for (i = 0; i < 64; i++) {
init_perm_res <<= 1;
init_perm_res |= (input >> (64-IP[i])) & LB64_MASK;
}
L = (uint32_t) (init_perm_res >> 32) & L64_MASK;
R = (uint32_t) init_perm_res & L64_MASK;
/* initial key schedule calculation */
for (i = 0; i < 56; i++) {
permuted_choice_1 <<= 1;
permuted_choice_1 |= (key >> (64-PC1[i])) & LB64_MASK;
}
C = (uint32_t) ((permuted_choice_1 >> 28) & 0x000000000fffffff);
D = (uint32_t) (permuted_choice_1 & 0x000000000fffffff);
/* Calculation of the 16 keys */
for (i = 0; i< 16; i++) {
/* key schedule */
// shifting Ci and Di
for (j = 0; j < iteration_shift[i]; j++) {
C = 0x0fffffff & (C << 1) | 0x00000001 & (C >> 27);
D = 0x0fffffff & (D << 1) | 0x00000001 & (D >> 27);
}
permuted_choice_2 = 0;
permuted_choice_2 = (((uint64_t) C) << 28) | (uint64_t) D ;
sub_key[i] = 0;
for (j = 0; j < 48; j++) {
sub_key[i] <<= 1;
sub_key[i] |= (permuted_choice_2 >> (56-PC2[j])) & LB64_MASK;
}
}
for (i = 0; i < 16; i++) {
/* f(R,k) function */
s_input = 0;
for (j = 0; j< 48; j++) {
s_input <<= 1;
s_input |= (uint64_t) ((R >> (32-E[j])) & LB32_MASK);
}
/*
* Encryption/Decryption
* XORing expanded Ri with Ki
*/
if (mode == 'd') {
// decryption
s_input = s_input ^ sub_key[15-i];
} else {
// encryption
s_input = s_input ^ sub_key[i];
}
/* S-Box Tables */
for (j = 0; j < 8; j++) {
// 00 00 RCCC CR00 00 00 00 00 00 s_input
// 00 00 1000 0100 00 00 00 00 00 row mask
// 00 00 0111 1000 00 00 00 00 00 column mask
row = (char) ((s_input & (0x0000840000000000 >> 6*j)) >> 42-6*j);
row = (row >> 4) | row & 0x01;
column = (char) ((s_input & (0x0000780000000000 >> 6*j)) >> 43-6*j);
s_output <<= 4;
s_output |= (uint32_t) (S[j][16*row + column] & 0x0f);
}
/*
f_function_res = 0;
for (j = 0; j < 32; j++) {
f_function_res <<= 1;
f_function_res |= (s_output >> (32 - P[j])) & LB32_MASK;
}
*/
temp = R;
R = L ^ s_output;
L = temp;
}
pre_output = (((uint64_t) R) << 32) | (uint64_t) L;
/* inverse initial permutation */
for (i = 0; i < 64; i++) {
inv_init_perm_res <<= 1;
inv_init_perm_res |= (pre_output >> (64-PI[i])) & LB64_MASK;
}
return inv_init_perm_res;
}
int main(int argc, const char * argv[]) {
int i;
uint64_t input = 0x7177657274797569;
uint64_t key = 0x3132333435363738;
uint64_t result = 0x0000000000000000;
char a[]="qwertyui";
char * reset;
uint64_t * b = a;
uint64_t re = *b;
printf("0x%016llx\n",re);
result = des(re, key, 'e');
printf ("E: 0x%016llx\n", result);//0x450c1d3608c12d52
result = des(result, key, 'd');
printf ("D: 0x%016llx\n", result);
exit(0);
}总结
前前后后研究了一个星期，总算写明白了，对自己的提高也很大。共勉！