I. Thuật toán DES

1. Giới thiệu về thuật toán DES

DES (Data Encryption Standard) là thuật toán mã hóa đối xứng, được chuẩn hóa vào năm 1977 bởi Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (NIST) với sự hỗ trợ của Cơ quan An ninh Quốc gia (NSA). Được phát triển bởi IBM vào đầu những năm 1970 với tên gọi ban đầu là “Lucifer”, DES sử dụng khóa 56-bit để mã hóa dữ liệu theo khối 64-bit, trở thành tiêu chuẩn vàng trong bảo mật thông tin suốt nhiều thập kỷ. Sự ra đời của DES đã đặt nền móng cho các thuật toán mã hóa hiện đại, mặc dù ngày nay nó đã được thay thế bởi các giải pháp tiên tiến hơn như AES.

2. Cấu trúc và nguyên lý hoạt động của DES

DES sử dụng cấu trúc mạng Feistel, một thiết kế phổ biến cho các thuật toán mã hóa khối, giúp tăng tính bảo mật qua các phép biến đổi lặp. Dữ liệu 64-bit được chia thành hai nửa (trái và phải). Trong mỗi vòng mã hóa, nửa bên phải được xử lý qua hàm F, kết quả được kết hợp (XOR) với nửa bên trái, rồi hai nửa đổi chỗ. Hàm F sử dụng các kỹ thuật như mở rộng bit, hoán vị (P-box), và hộp thay thế (S-box) để tăng độ phức tạp. Mỗi vòng dùng một khóa con 48-bit, tạo từ khóa chính 56-bit qua hoán vị và dịch vòng. DES thực hiện 16 vòng mã hóa để đảm bảo dữ liệu được bảo vệ mạnh mẽ.

Hình 1: Sơ đồ quy trình thuật toán DES

2.1. Bảng hoán vị khởi tạo (IP)

Bước hoán vị khởi tạo (IP) của DES sắp xếp lại vị trí 64 bit dữ liệu đầu vào theo bảng IP, giữ nguyên giá trị các bit. Quá trình này tăng độ phức tạp và chuẩn bị dữ liệu cho các vòng mã hóa tiếp theo.

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

Bảng hoán vị khởi tạo (IP)

2.2. Hàm F

Hình 2: Sơ đồ quy trình hàm F

Hàm F là lõi xử lý chính trong mỗi vòng mã hóa của DES, chịu trách nhiệm biến đổi dữ liệu để tăng tính bảo mật trong cấu trúc mạng Feistel. Hàm F nhận nửa bên phải 32 bit của dữ liệu, kết hợp với khóa con, và tạo ra một chuỗi 32 bit mới để kết hợp (XOR) với nửa bên trái. Quy trình này bao gồm các bước phức tạp nhằm làm rối dữ liệu và tăng tính không tuyến tính, khiến việc giải mã mà không có khóa trở nên cực kỳ khó khăn. Cụ thể, hàm F thực hiện như sau:

Mở rộng bit (bảng E): Hàm F nhận 32 bit đầu vào và mở rộng thành 48 bit bằng bảng mở rộng E. Bảng E lặp lại một số bit và sắp xếp lại vị trí các bit theo thứ tự cố định, tạo ra chuỗi 48 bit để khớp với kích thước của khóa con.

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

Bảng mở rộng E

Phép XOR với khóa con: Chuỗi 48 bit được kết hợp (XOR) với một khóa con 48 bit, được tạo từ khóa chính 56 bit qua quá trình hoán vị và dịch vòng. Phép XOR đảm bảo dữ liệu bị biến đổi phụ thuộc vào khóa, tăng tính bảo mật.
Thay thế qua S-box: Chuỗi 48 bit được chia thành 8 nhóm, mỗi nhóm 6 bit. Mỗi nhóm được đưa vào một trong 8 hộp thay thế (S-box), thay thế 6 bit thành 4 bit theo bảng tra cứu cố định. Các S-box tạo ra tính không tuyến tính, làm rối mối quan hệ giữa dữ liệu và khóa, kết quả là 32 bit (8 nhóm × 4 bit).

S-box 1

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

S-box 2

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9

S-box 3

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12

S-box 4

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14

S-box 5

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

S-box 6

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13

S-box 7

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12

S-box 8

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

Tám bảng S-box (S1 đến S8)

Hoán vị P: Cuối cùng, 32 bit từ S-box được sắp xếp lại vị trí theo bảng hoán vị P. Bước này tăng độ khuếch tán, đảm bảo mỗi bit đầu ra ảnh hưởng đến nhiều vị trí trong dữ liệu, nâng cao tính phức tạp của mã hóa.

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

Bảng hoán vị P

Nhờ các bước trên, hàm F biến đổi dữ liệu một cách phức tạp, đảm bảo DES đạt được mức bảo mật cao qua 16 vòng mã hóa.

2.3. Khóa con (Subkeys)

Hình 3: Sơ đồ quy trình tạo khóa con

Trong DES, khóa con (subkeys) là các chuỗi bit được tạo từ khóa chính 64-bit để sử dụng trong 16 vòng mã hóa của hàm F. Mỗi vòng yêu cầu một khóa con 48-bit khác nhau, được tạo qua một quy trình gồm hoán vị, chia nửa, dịch vòng trái, và chọn bit. Quy trình này đảm bảo các khóa con đủ đa dạng và phức tạp, tăng tính bảo mật của thuật toán. Cụ thể, quá trình tạo khóa con bao gồm các bước sau:

Hoán vị PC-1: Khóa chính 64-bit được sắp xếp lại theo bảng PC-1, loại bỏ 8 bit kiểm tra chẵn lẻ (parity bits) để còn 56 bit. Chuỗi 56 bit này được chia thành hai nửa bằng nhau: C (28 bit) và D (28 bit).

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

Bảng hoán vị PC-1

Dịch vòng trái: Hai nửa C và D được dịch vòng trái (left shift) độc lập theo số lần cố định cho mỗi vòng mã hóa, từ 1 hoặc 2 bit, theo bảng số lần dịch bit. Quá trình này tạo ra các phiên bản khác nhau của C và D cho mỗi vòng, đảm bảo các khóa con không lặp lại.

Vòng	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Số lần dịch trái	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

Bảng số lần dịch bit (Shift Schedule)

Hoán vị PC-2: Sau mỗi lần dịch vòng trái, hai nửa C và D (tổng 56 bit) được kết hợp và hoán vị qua bảng PC-2 để chọn 48 bit, tạo ra một khóa con 48-bit cho mỗi vòng mã hóa. Quá trình này lặp lại 16 lần để tạo 16 khóa con khác nhau.

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

Bảng hoán vị PC-2

2.4: Hoán vị cuối (IP-1)

Sau 16 vòng mã hóa, hai nửa dữ liệu L (trái) và R (phải) được kết hợp thành một chuỗi 64-bit. Chuỗi này được sắp xếp lại vị trí các bit theo bảng hoán vị cuối (FP) để tạo ra bản mã hoàn chỉnh. Bảng FP là nghịch đảo của bảng hoán vị ban đầu (IP), nghĩa là nó đảo ngược quá trình sắp xếp của IP, đảm bảo tính đối xứng giữa mã hóa và giải mã. Mỗi bit trong chuỗi 64-bit được ánh xạ sang một vị trí mới theo bảng FP, giữ nguyên giá trị bit.

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

Bảng 2.4.1: Bảng hoán vị cuối (IP-1)

Quay lại trang chủ

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

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

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

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

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

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

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

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

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12

Hàng\Cột	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11