首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 密码应用
    3. 发新帖
[分享]DES加密
发表于: 2021-9-11 11:50 24338

[分享]DES加密

Max_hhg 活跃值
2021-9-11 11:50
24338

目录

简介

  • 密码类型：对称分组密码
  • 明文：64位明文
  • 密文：64位密文

  • 密钥：64位（实际长度56位 每8位为奇偶校验位）

    DES算法为密码体制中的对称密码体制，又被称为美国数据加密标准，是1972年美国IBM公司研制的对称密码体制加密算法。

Feistel网络

feistel cipher也叫做Luby–Rackoff分组密码，是用来构建分组加密算法的对称结构。它是由德籍密码学家Horst Feistel在IBM工作的时候发明的。feistel cipher也被称为Feistel网络。
很多分组加密算法都是在feistel cipher的基础上发展起来的，比如非常有名的DES算法。在feistel cipher中，加密和解密的操作非常相似，通常需要进行多轮加密和解密操作。

Feistel加密流程

在Feistel网络中，加密的各个步骤称为轮( round),整个加密过程就是进行若干次轮的循环。DES是一种16轮循环的Feistel网络。

轮函数的作用是根据“右侧”和子密钥生成对“左侧”进行加密的比特序列

 

一轮的具体计算步骤：
(1)将输人的数据等分为左右两部分。
(2)将输人的右侧直接发送到输出的右侧。
(3)将输人的右侧发送到轮函数。
(4)轮函数根据右侧数据和子密钥，计算出一串看上去是随机的比特序列。
(5)将上一步得到的比特序列与左侧数据进行XOR运算，并将结果作为加密后的左侧。

性质

  • Feistel网络可以任意增加
  • 加密时无论使用任何函数作为轮函数都可以正确解密
  • 加密和解密可以用完全相同的结构来实现

DES加密流程

DES算法使用的是Feistel框架
DES算法采用16轮循环的加密
典型的分组大小为64位和128位

 


DES算法的加密流程：

  1. 将输入的明文进行初始置换。
  2. 将初始置换后的结果按照每组32位数据分成L、R两组。
  3. 将48位子密钥k[i]和32位R[i]组数据输入F函数进行处理，输出32位处理结果。
  4. 将32位F函数处理结果与32位的L[i]组数据按位进行异或操作。
  5. 将32位的异或处理结果赋值给R[i+1]分组，将32位的R[i]分组数据赋值给 L[i+1]。
    L[i+1] = R[i],R[i+1] = L[i]^(F(k[i], R[i]))
  6. 对3、4、5步处理进行16次循环，得到L[16]，R[16]。
  7. 将L[16]、R[16]数据进行交叉合并得到64位数据。
  8. 对得到的64位数据进行逆初始值置换，得到想要的密文Y。

明文加密

初始置换IP

IP置换目的是将输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位。
置换规则如下表所示：

 

图片描述
表中的数字代表新数据中此位置的数据在原数据中的位置，即原数据块的第58位放到新数据的第1位，第50位放到第2位，……依此类推，第7位放到第64位。置换后的数据分为L0和R0两部分，L0为新数据的左32位，R0为新数据的右32位。

 

举个栗子 置换前：
图片描述
置换后：
图片描述

 

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const unsigned 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
};
 
int IP_Substitution(const unsigned char* BitPlain, unsigned char* Bit_IP_Table) // BitPlain置换前表 Bit_IP_Table 置换后表 IP_Table 置换规则
{
    int ret = 0;
 
    for (int i = 0; i < 64; i++)
    {
        Bit_IP_Table[i] = BitPlain[IP_Table[i] - 1];
    }
 
    return ret;
}

DES算法中的F函数

流程图

F函数处理流程：

  1. 将输入的32位R组数据进行扩展置换，生成48位的数据。
  2. 将置换后的48位结果与输入的48位子密钥进行异或运算，得到48位的运算结果。
  3. 将48位运算结果分成8组，每组6Bit数据，按照组号对应相应的S盒，进行8个S盒置换，生成8个4Bit的数据。
  4. 将这8个4Bit数据合并，得到一个32位数据。
  5. 将32位进行置换P就得到最后的32位处理结果。

先讲讲扩展置换E
扩展置置换目标是IP置换后获得的右半部分R0，将32位输入扩展为48位(分为4位×8组)输出。
扩展置换目的有两个：生成与密钥相同长度的数据以进行异或运算；提供更长的结果，在后续的替代运算中可以进行压缩。

 

　　扩展置换原理如下表：
图片描述
表中的数字代表位，两列蓝底红字数据是扩展的数据，可以看出，扩展的数据是从相邻两组分别取靠近的一位，4位变为6位。靠近32位的位为1，靠近1位的位为32。表中第二行的4取自上组中的末位，9取自下组中的首位。

 

我们举个例子看一下：
　　输入数据0x1081 1001，转换为二进制就是0001 0000 1000 0001B，按照上表扩展得下表
图片描述

 

S盒置换
　压缩后的密钥与扩展分组异或以后得到48位的数据，将这个数据送人S盒，进行替代运算。替代由8个不同的S盒完成，每个S盒有6位输入4位输出。48位输入分为8个6位的分组，一个分组对应一个S盒，对应的S盒对各组进行代替操作。
图片描述
一个S盒就是一个4行16列的表，盒中的每一项都是一个4位的数。
图片描述
S盒的6个输入确定了其对应的输出在哪一行哪一列，输入的高低两位做为行数H，中间四位做为列数L，在S-BOX中查找第H行L列对应的数据(<32)。
图片描述
S盒8的输入为100101，第1位和第6位组合为11，对应于S盒8的第4行；第2位到第5位为0010，对应于S盒8的第3列。S盒8的第4行第3列的数字为7，因此用0111来代替100101。注意，S盒的行列计数都是从0开始,代替过程产生8个4位的分组，组合在一起形成32位数据。
代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//S盒置换  f函数内
const unsigned char S_Table[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
};
 
 
unsigned char Bit_Xor[8][6];          //存放异或运算的结果
unsigned char Bit_Integer[8][4];      //将整数变成Bit位
unsigned char Row;                    //S盒的行号
unsigned char Col;                    //S盒的列号
unsigned char Integer;                //从S盒中取得的32位整数
 
for (int i = 0; i < 8; i++)
{
    //计算S盒的行号和列号
    Row = (Bit_Xor[i][0] << 1) + Bit_Xor[i][5];
    Col = (Bit_Xor[i][1] << 3) + (Bit_Xor[i][2] << 2) + (Bit_Xor[i][3] << 1) + Bit_Xor[i][4];
 
    //从S盒中取得整数
    Integer = S_Table[i][Row][Col];
 
    //将取得的4Bit数转换成Bit组
    for (int j = 0; j < 4; j++)
    {
        Bit_Integer[i][j] = Integer >> (3 - j) & 1;
    }
}

P置换
S盒代替运算的32位输出按照P盒进行置换。该置换把输入的每位映射到输出位，任何一位不能被映射两次，也不能被略去，映射规则如下表：
图片描述
　　表中的数字代表原数据中此位置的数据在新数据中的位置，即原数据块的第16位放到新数据的第1位，第7位放到第2位，……依此类推，第25位放到第32位。

 

　　例如0x10A1 0001进行P盒置换后变为0x8000 0886。

 

　　0x10A1 0001表现为表的形式（第一位位于左上角）原来为
图片描述
经P盒变换后为
图片描述
即1000 0000 0000 0000 0000 1000 1000 0110B，十六进制为0x8000 0886。
代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const unsigned char reIP_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
};
 
int reIP_Substitution(const unsigned char *BitRL_Table, unsigned char *Bit_reIP_Table)
{
    int ret = 0;
 
    for (int i = 0; i < 64; i++)
    {
        Bit_reIP_Table[i] = BitRL_Table[reIP_Table[i] - 1];
    }
 
    return ret;
}

　　最后，P盒置换的结果与最初的64位分组左半部分L0异或，然后左、右半部分交换，接着开始另一轮。

逆初始置换IP-1

末置换是初始置换的逆过程，DES最后一轮后，左、右两半部分并未进行交换，而是两部分合并形成一个分组做为末置换的输入。末置换规则如下表：
图片描述
置换方法如上。

密钥生成

密钥生成流程
图片描述

PC-1置换

DES的密钥由64位减至56位，每个字节的第8位作为奇偶校验位。
图片描述
从表中观察，PC-1置换表是一个7*8矩阵。其中的内容缺少了8、16、24、32、40、48、56、64，也就是说这8个位置没有参加密钥的生成，PC-1置换表也就导致了虽然输入的密钥是64位，但实际上只有56位起着作用。
代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const unsigned char PC_1_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
};
 
int PC_1_Substitution(const unsigned char *BitKey, unsigned char *BitKey_PC_1)
{
    int ret = 0;
 
    for (int i = 0; i < 56; i++)
    {
        BitKey_PC_1[i] = BitKey[PC_1_Table[i] - 1];
    }
 
    return ret;
}

左移处理

有两个问题：怎么样左移？左移多少位？
怎么样左移？
假如将C组左移2位，就要把所有数据向左移动两位，并把前面超出范围的两位数据移动到数据的最后面。
左移多少位？
每组左移的位数也不是随意确定的，当i=1、2、9、16轮中，C、D两组向左移动一位；在其他轮中，C、D两组向左移动两位(i>=1)。注意：如果把所有移动位数加起来刚好等于每组数据的位数，也就是一共需要移动28位。也就是移动前的数据等于最后移动后的数据：C[0] = C[16]; D[0] = D[16];在这里我们就把移动的位数做成一共移位表，方便编程。
图片描述
代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const unsigned char Bit_Round[16] =
{
    1, 1, 2, 2,
    2, 2, 2, 2,
    1, 2, 2, 2,
    2, 2, 2, 1
};
 
int BitRound_L(const unsigned char* SrcBitGroup, unsigned char* DesBitGroup, int nBit)
{
    int ret = 0;
 
    memcpy(DesBitGroup,             &SrcBitGroup[nBit], 28 - nBit);
    memcpy(&DesBitGroup[28 - nBit], SrcBitGroup,        nBit);
 
    return ret;
}
 
//将C、D两组进行轮转移位操作    左移
BitRound_L(BitC_Table[i], BitC_Table[i + 1], Bit_Round[i]);
BitRound_L(BitD_Table[i], BitD_Table[i + 1], Bit_Round[i]);

PC-2置换

在进行PC-2置换前，需要将C、D两组左移后的数据进行合并，合并方法与前方类似。C、D两组合并后形成一个56Bit数据块，这个数据块经过PC-2置换后就会变成一个48Bit的子密钥。通过如此这般16轮循环处理就可以形成16个48位的子密钥。
图片描述

 

代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const unsigned char PC_2_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
};
 
int PC_2_Substitution(const unsigned char *BitKey, unsigned char *SubKey)
{
    int ret = 0;
 
    for (int i = 0; i < 48; i++)
    {
        SubKey[i] = BitKey[PC_2_Table[i] - 1];
    }
 
    return ret;
}

DES解密

DES的解密过程和DES的加密过程完全类似 只是把密钥顺序倒置。

利用python加解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/python
# -*- coding: utf-8 -*-
import binascii
from pyDes import des, CBC, PAD_PKCS5
 
 
def des_encrypt(secret_key, s):
    iv = secret_key
    k = des(secret_key, CBC, iv, pad=None, padmode=PAD_PKCS5)
    en = k.encrypt(s, padmode=PAD_PKCS5)
    return binascii.b2a_hex(en)
 
 
def des_decrypt(secret_key, s):
    iv = secret_key
    k = des(secret_key, CBC, iv, pad=None, padmode=PAD_PKCS5)
    de = k.decrypt(binascii.a2b_hex(s), padmode=PAD_PKCS5)
    return de
 
 
secret_str = des_encrypt('testtest', 'this is a test?!*')
print '密文:', secret_str
clear_str = des_decrypt('testtest', secret_str)
print '明文:', clear_str

逆向特征

  1. 密文的长度必须是0x08字节的倍数.
  2. 秘钥的长度必须是 0x08字节。
  3. 大量数据相似（例如S盒和置换表）

在2020祥云杯的某道APK逆向里，Findcrypt插件失效（可能是Findcrypt分析不了ARM框架下的文件），所以我们只能靠手动分析找到DES的特征（以下是S1到S8）：
图片描述
还有一些别的特征，都可以帮助我们快速识别DES算法：
图片描述

这方面 我没有找到具体的逆向题目 欢迎大家投题目给我

参考

逆向中常见的Hash算法和对称加密算法的分析
密码学基础：DES加密算法


[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

最后于 2021-9-11 13:19 被Max_hhg编辑 ，原因：
收藏
免费 ・3
支持
分享
最新回复 (1)
arryang
雪    币： 205
活跃值： (171)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
2 楼
写的很好。但3.3 的图是不是画的有问题？
最下边 “加密后的左侧” 同“右侧” 是不是要交换一下位置？还是我理解错误？
2022-1-23 10:09
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//