前言

本来DES算法我打算写成从做题到出题再到做题系列,但是由于没有找到好的例子,也就无从入手,而且DES算法本身已经十分的复杂,仅仅通过观察数据如何变化是很难发现端倪的。

不过我在此期间认真的学习了DES算法,了解其加密的细节。

接下来我希望我这篇浅显的文章能帮助大家对DES的理解有所帮助。

原理简介

我主要是通过阅读图解密码技术这本书来学习的,建议大家先去学习了解一下。

首先我这不会去详细的说DES加解密的原理,毕竟已经有人做了这些工作,这里只做简介。

参考文章

这篇参考文章建议认真阅读一下,可以结合着这篇参考文章和我的分析过程来认识了解DES。


DES是一种将64比特的明文加密成64比特的密文的对称密码算法,它的密钥长度是56比特。但从严格来说,DES的密钥长度是64比特,但由于每隔7比特会设置一个用于错误检查的比特,因此实质上其密钥长度是56比特。

DES是以64比特的明文为一个单位来进行加密的。这一个单位称为分组,一般来说以分组为单位进行处理的密码算法称为分组密码。

DES每次只能加密64bit的数据,如果要加密的明文比较长,就需要对DES加密进行迭代,而迭代的具体方式,就称为模式。

这里只对64位明文进行加密,因此不涉及迭代模式。

加密过程

DES的结构也称为Feistel网络

Feistel网络中,加密的各个步骤称为,整个加密过程就是进行若干次轮的循环

每一轮都需要使用一个不同的子密钥

轮函数的作用是根据右侧和子密钥生成对左侧进行加密的比特序列,它是密码系统的核心。

一轮的具体计算步骤:

  1. 将输入的数据等分为左右两部分
  2. 将输入的右侧直接发送到输出的右侧
  3. 将输入的右侧发送到轮函数
  4. 轮函数根据右侧数据和子密钥,计算出一串看上去是随机的比特序列
  5. 将上一步得到的比特序列与左侧数据进行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;
    }

其结果为0x1FFE0xCCF101E

而后将其结果合并组成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: huertas.dani@gmail.com
 * 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: huertas.dani@gmail.com
 * 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);

}

总结

前前后后研究了一个星期,总算写明白了,对自己的提高也很大。共勉!

点击收藏 | 0 关注 | 1
  • 动动手指,沙发就是你的了!
登录 后跟帖