首页
论坛
课程
招聘
[分享]DES加密
2021-9-11 11:50 10622

[分享]DES加密

2021-9-11 11:50
10622

目录

简介

  • 密码类型:对称分组密码
  • 明文: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, 179, 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, 413, 1215, 11, 8310, 612, 5907,
    015, 7414, 213, 110, 612, 11, 9538,
    4114, 813, 6211, 15, 12, 97310, 50,
    15, 12, 824917511, 314, 10, 0613,
 
    //S2盒
    15, 1814, 611, 3497213, 12, 0510,
    313, 4715, 2814, 12, 0110, 6911, 5,
    014, 711, 10, 413, 15812, 693215,
    13, 810, 1315, 4211, 6712, 0514, 9,
 
    //S3盒
    10, 0914, 6315, 5113, 12, 711, 428,
    13, 70934610, 28514, 12, 11, 15, 1,
    13, 649815, 3011, 1212, 510, 14, 7,
    110, 13, 06987415, 14, 311, 5212,
 
    //S4盒
    713, 14, 306910, 128511, 12, 415,
    13, 811, 5615, 0347212, 110, 14, 9,
    10, 69012, 11, 713, 15, 1314, 5284,
    315, 0610, 113, 894511, 12, 7214,
 
    //S5盒
    212, 41710, 11, 685315, 13, 014, 9,
    14, 11, 212, 4713, 15015, 10, 3986,
    42111, 10, 13, 7815, 912, 563014,
    11, 812, 7114, 213, 615, 0910, 453,
 
    //S6盒
    12, 110, 15, 9268013, 3414, 7511,
    10, 15, 42712, 956113, 14, 011, 38,
    914, 15, 52812, 370410, 113, 11, 6,
    43212, 9515, 10, 11, 14, 1760813,
 
    //S7盒
    411, 214, 15, 0813, 312, 97510, 61,
    13, 011, 749110, 14, 3512, 215, 86,
    1411, 13, 12, 3714, 10, 15, 680592,
    611, 13, 81410, 795015, 14, 2312,
 
    //S8盒
    13, 284615, 11, 110, 9314, 5012, 7,
    115, 13, 810, 37412, 5611, 014, 92,
    711, 41912, 14, 20610, 13, 15, 358,
    2114, 7410, 813, 15, 12, 9035611
};
 
 
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, 419, 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, 91,
    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, 762, 54, 46, 38,
    30, 22, 14, 661, 53, 45, 37,
    29, 21, 13, 528, 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, 15328,
    15, 621, 10, 23, 19, 12, 4,
    26, 816, 727, 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加密算法


【看雪培训】目录重大更新!《安卓高级研修班》2022年春季班开始招生!

最后于 2021-9-11 13:19 被Max_hhg编辑 ,原因:
收藏
点赞2
打赏
分享
最新回复 (1)
雪    币: 133
活跃值: 活跃值 (79)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
arryang 活跃值 1 2022-1-23 10:09
2
0
写的很好。但3.3 的图是不是画的有问题?
最下边 “加密后的左侧” 同“右侧” 是不是要交换一下位置?还是我理解错误?
游客
登录 | 注册 方可回帖
返回