DES

简介

DES加密是经典的基于Feistel网络结构的块加密，DES标准中字节的处理方式为大端序，DES接受一个64位（64bit）的明文和一个64位的key，返回64位的密文
在DES流程的开始，64位的key被传入PC1函数生成56位的真正密钥，因为原密钥中有8位是校验位
而这56位的密钥会再被拆分成左右两个各28位的密钥

pair<uint32_t, uint32_t> PC1(uint64_t key)
{
    uint8_t pc1L[] = {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};
    uint8_t pc1R[] = {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};
    pair<uint32_t, uint32_t> keyPair{0, 0};
    for (int i = 0; i < 28; i++)
    {
        keyPair.first |= ((key >> (64 - pc1L[i])) & 1) << (27 - i);
        keyPair.second |= ((key >> (64 - pc1R[i])) & 1) << (27 - i);
    }
    return keyPair;
}

两个28位密钥分别左旋特定位数后进入PC2用于生成16个48位子密钥，PC2中有一个盒用于决定选择哪48位来作为密钥

void keyGen(pair<uint32_t, uint32_t> keyPair)
{
    uint8_t offsets[] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
    for (int i = 0; i < 16; i++)
    {
        keyPair.first = leftRotate(keyPair.first, offsets[i]);
        keyPair.second = leftRotate(keyPair.second, offsets[i]);
        Keys[i] = PC2(((uint64_t)keyPair.first << 28) | keyPair.second);
    }
}
uint64_t PC2(uint64_t key)
{
    uint8_t 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};
    uint64_t subKey = 0;
    for (int i = 0; i < 48; i++)
    {
        subKey |= ((key >> (56 - pc2[i])) & 1) << (47 - i);
    }
    return subKey;
}

至此为止密钥全部准备完毕，明文被分为左右各32位进入Feistel网络循环流程

void desEncrypt(uint64_t *plain, uint64_t key)
{
    keyGen(PC1(key));
    uint64_t afterIP = IP(*plain);
    uint32_t l = afterIP >> 32, r = afterIP & 0xFFFFFFFF;
    for (int i = 0; i < 16; i++)
    {
        pair<uint32_t, uint32_t> lr = goRound(l, r, Keys[i]);
        l = lr.first;
        r = lr.second;
    }
    *plain = ((uint64_t)r << 32) | l;
    *plain = FP(*plain);
}

明文在进入和结束加密时还要经历IP,FP两次置换，这两次置换只是简单映射

uint64_t IP(uint64_t messagge)
{
    uint64_t afterIP = 0;
    uint8_t 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};
    for (int i = 0; i < 64; i++)
    {
        afterIP |= ((messagge >> (64 - ip[i])) & 1) << (63 - i);
    }
    return afterIP;
}
uint64_t FP(uint64_t messagge)
{
    uint64_t afterFP = 0;
    uint8_t fp[] = {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};
    for (int i = 0; i < 64; i++)
    {
        afterFP |= ((messagge >> (64 - fp[i])) & 1) << (63 - i);
    }
    return afterFP;
}

Feistel轮函数如下所示

uint32_t feistel(uint32_t a, uint64_t key)
{
    uint64_t t = expand(a) ^ key;
    uint32_t afterS = S(t);
    afterS = P(afterS);
    return afterS;
}
pair<uint32_t, uint32_t> goRound(uint32_t l, uint32_t r, uint64_t key)
{
    return {r, l ^ feistel(r, key)};
}

数据先经过E盒拓展为48位后与48位密钥异或，然后进入S盒重新映射为32位，最后由P盒再进行一轮置换后输出

uint64_t expand(uint32_t a)
{
    uint8_t 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};
    uint64_t afterE = 0;
    for (int i = 0; i < 48; i++)
    {
        afterE |= ((a >> (32 - e[i])) & 1) << (47 - i);
    }
    return afterE;
}

S盒有8个，每个S盒是一个4*16的结构，48位的输出被分为8个6位的块分别进入对应的S盒，每块的第1和第6个位用于索引行(0x00 ~ 0x11)，其余四位用于索引列(0x0000 ~ 0x1111)，S盒中的数都是4位的，最后合起来得到一个32位的输出

uint64_t S(uint64_t a)
{
    uint32_t res = 0;
    for (int i = 0; i < 8; i++)
    {
        uint8_t row = ((((a >> (i * 6)) & 0x20)) >> 4) | ((a >> (i * 6)) & 1);
        uint8_t col = ((a >> (i * 6)) & 0x1E) >> 1;
        res |= S_box[i][row * 16 + col] << (i * 4);
    }
    return res;
}

P置换就是再次打乱S盒的输出

uint32_t P(uint64_t a)
{
    uint8_t 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};
    uint32_t afterP = 0;
    for (int i = 0; i < 32; i++)
    {
        afterP |= ((a >> (32 - p[i])) & 1) << (31 - i);
    }
    return afterP;
}

至此DES的流程全部结束，按照图例的话如下图所示

特征

因为DES的代码过于庞大，且涉及大量位操作，在反编译器中观察DES的特征非常困难，但是DES有非常多的盒，其中部分盒是精心设计的，修改这部分盒会严重影响DES在对抗暴力破解时的安全性，所以我们可以通过这些一般不会修改的盒识别DES

S盒

S盒引入了非线性操作，且S盒的每一位都设计过用以抵抗差分和线性密码分析，一般不会修改S盒

uint8_t S_box[8][64] = 
{{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},
{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},
{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},
{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},
{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},
{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},
{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},
{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}};

P盒

P盒的特殊设计使得每一轮由同一个S盒输出的4个bit在下一轮都被分散到另外4个不同S盒中进行处理（增强扩散性）

uint8_t 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};

E盒

E盒负责将32位的输入扩展到48位，对混淆能力由很大影响

uint8_t 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};

实现

考虑到DES现在已经被证明不安全，且其加密过程严重依赖系统端序，DES标准为大端序，而现代计算机大多数为小端序，故不给出完整实现，如果遇到需要手动解密的DES，只需要根据Feistel网络的性质，将16个子密钥倒着使用即可解密

reference

DES-wikipedia