DES (Data Encryption Standard) – Bài tập ứng dụng tổng hợp

Ta có X = 0123456789ABCDEF và một khóa K = 13345799BBCDDFF1 với X, K được định dạng dưới dạng hệ thập lục phân, ta tiến hành mã hóa và giải mã theo giải thuật DES theo các bước sau.

Giai đoạn 1:

Ta viết lại X, K dưới dạng nhị phân, chúng ta nhận được khối 64bit của X và khóa K: 

 -> X = 0000 0001, 0010 0011, 0100 0101, 0110 0111, 1000 1001, 1010 1011 1100 1101 1110 1111

X₀ = IP(X) = L₀R₀

Hoán vị X qua bộ hoán vị 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

Được xâu X₀ = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

1	1	0	0	1	1	0	0
0	0	0	0	0	0	0	0
1	1	0	0	1	1	0	0
1	1	1	1	1	1	1	1
1	1	1	1	0	0	0	0
1	0	1	0	1	0	1	0
1	1	1	1	0	0	0	0
1	0	1	0	1	0	1	0

Chia X₀ thành 1 nửa trái L₀ 32 bit và một nửa phải R₀ 32bit, từ IP ta nhận được:

 L₀ = 1100 1100 0000 0000 1100 1100 1111 1111

 R₀ = 1111 0000 1010 1010 1111 0000 1010 1010

Giai đoạn 2:

Sinh khóa K

DES hoạt động trên các khối 64-bit sử dụng kích thước chính của 56- bit. Các khóa thực sự được lưu trữ dài 64 bit, nhưng mỗi bit thứ 8 trong khóa không được sử dụng (tức là bit số 8, 16, 24, 32, 40, 48, 56, và 64). 

Đưa K về dạng nhị phân:

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

Thuật toán G sinh các khóa K₁, …, K₁₆ từ K ban đầu:

Tạo 16 khóa con, mỗi khóa có chiều dài 48 bit Khóa 64 bit được hoán vị theo bảng dưới đây, PC-1. Chỉ có 56 bit của khóa ban đầu xuất hiện trong khóa hoán vị PC-1: 

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

Chúng ta nhận được hoán vị 56 bit: 

K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111 

Tiếp theo, chia khóa này thành 2 nửa trái và phải, C0 và D0, mỗi nửa 28 bit, ta được: 

C₀ = 1111000 0110011 0010101 0101111 

D₀ = 0101010 1011001 1001111 0001111 

Với C0 và D0 đã được xác định, bây giờ chúng ta tạo ra 16 khối CnDn 1<=n<=16. 

Mỗi cặp CnDn được hình thành từ các cặp trước nó Cn-1Dn-1 bằng cách sử dụng quy luật sau đối với khối trước nó

Vòng lặp	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

Từ bảng quy luật trên ta thấy, C₁D₁ được sinh ra khi thực hiện dịch trái 1 lần đối với C₀D₀ ta thu được:

 C₁ = 111000 0110011 0010101 01011111

 D₁ = 101010 1011001 1001111 00011110 

Tương tự ứng với bảng quy luật trên ta thu được các khối CnDn (1<=n<=16) như sau:

n	Cn	Dn
1
2	1100001100110010101010111111	0101010110011001111000111101
3	0000110011001010101011111111	0101011001100111100011110101
4	0011001100101010101111111100	0101100110011110001111010101
5	1100110010101010111111110000	0110011001111000111101010101
6	0011001010101011111111000011	1001100111100011110101010101
7	1100101010101111111100001100	0110011110001111010101010110
8	0010101010111111110000110011	1001111000111101010101011001
9	0101010101111111100001100110	0011110001111010101010110011
10	0101010111111110000110011001	1111000111101010101011001100
11	0101011111111000011001100101	1100011110101010101100110011
12	0101111111100001100110010101	0001111010101010110011001111
13	0111111110000110011001010101	0111101010101011001100111100
14	1111111000011001100101010101	1110101010101100110011110001
15	1111100001100110010101010111	1010101010110011001111000111
16	1111000011001100101010101111	0101010101100110011110001111

Bây giờ chúng ta xây dựng các khóa Kn (1<=k<=16) bằng cách áp dụng bảng hoán vị sau cho mỗi cặp CnDn. Mỗi cặp có 56 bit, nhưng PC-2 chỉ sử dụng 48 trong số này. PC-2

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

Từ

 C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110 Từ bảng trên ta suy ra:  

K1 = 000110 110000 001011 101111 111111 000111 000001 110010 

Tương tự cho các khóa khác, ta có:

K2  = 011110 011010 111011 011001 110110 111100 100111 100101

K3  = 010101 011111 110010 001010 010000 101100 111110 011001

K4  = 011100 101010 110111 010110 110110 110011 010100 011101 

K5  = 011111 001110 110000 000111 111010 110101 001110 101000

K6  = 011000 111010 010100 111110 010100 000111 101100 101111

K7  = 111011 001000 010010 110111 111101 100001 100010 111100

K8  = 111101 111000 101000 111010 110000 010011 101111 111011

K9  = 111000 001101 101111 101011 111011 011110 011110 000001

K10= 101100 011111 001101 000111 101110 100100 011001 001111

K11= 001000 010101 111111 010011 110111 101101 001110 000110

K12= 011101 010111 000111 110101 100101 000110 011111 101001 

K13= 100101 111100 010111 010001 111110 101011 101001 000001

K14= 010111 110100 001110 110111 111100 101110 011100 111010

K15= 101111 111001 000110 001101 001111 010011 111100 001010

K16= 110010 110011 110110 001011 000011 100001 011111 110101

16 vòng lặp:

L0 = 1100 1100 0000 0000 1100 1100 1111 1111

 R0 = 1111 0000 1010 1010 1111 0000 1010 1010

 Bây giờ chúng ta tiến hành thông qua 16 vòng lặp, sử dụng một hàm f mà hoạt động trên 2 khối – một khối dữ liệu 32bit và 1 khóa Kn 48bit để sinh ra một khối 32bit Ln = Rn-1 Rn = Ln-1 f(Rn-1, Kn)

Với n = 1, ta có 

K1 = 000110 110000 001011 101111 111111 000111 000001 110010 

L1 = R0= 1111 0000 1010 1010 1111 0000 1010 1010 R1 = L0 f(R0,K1)

 Để tính hàm f, chúng ta mở rộng mỗi khối Rn-1 từ 32bit lên 48bit bằng cách sử dụng một bảng một bảng lựa chọn mà lặp đi lặp lại một số bit trong Rn-1. Ta gọi việc sử dụng mỗi lựa chọn bảng này là hàm E. Vì vậy, E(Rn-1) có khối đầu vào 32bit và một khối đầu ra 48bit 48bit đầu ra được viết như 8 khối 6bit thu được bằng cách chọn các các bit trong đầu vào của nó theo theo bảng sau: E BIT-SELECTION TABLE

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

Ta tính E(R0) từ R0 như sau:

 R0 = 1111 0000 1010 1010 1111 0000 1010 1010 E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101

 Ta thấy mỗi khối 4bit ban đầu đã được mở rộng đến một khối 6 bit đầu ra. Tiếp theo để tính f, ta XOR đầu ra E(Rn-1) với khóa Kn: Kn E(Rn-1) .

Cho K1, E(R0) ta có K1= = 000110 110000 001011 101111 111111 000111 000001 110010 E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101 K1 E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111 

Tiếp theo ta sẽ sử dụng mỗi nhóm 6bit như các địa chỉ trong bảng gọi lại “S boxes”. Mỗi nhóm 6bit sẽ cung cấp 1 địa chỉ trong một S box khác nhau. Nằm tại địa chỉ đó sẽ có 1 số 4bit. Số 4bit này sẽ thay thế 6bit ban đầu . Kết quả cuối cùng là 8 nhóm 6bit được chuyển thành 8 nhóm 4bit, tổng số sẽ là 32 bit. Viết kết quả trước đó với 48bit dưới dạng sau: 

Kn E(Rn-1) = B1B2B3B4B5B6B7B8

 Trong đó mỗi Bi là một nhóm 6 bit như ta đã xã định với trường hợp K1 E(R0) ở trên. Bây giờ ta phải tính S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) Với Si(Bi) tương ứng là đầu ra của hộp thứ i S box Mỗi hàm S1, S2,…, S8 có một khối 6bit là đầu vào và một khối 4bit là đầu ra. Bảng xác định S1:

S1 là hàm được xác định trong bảng này và B là một khối 6 bit đầu vào, S1(B) được xác định như sau: xác định bit đầu tiên và cuối cùng của B: nó là một số nhị phân có dạng 00,01, 10 hoặc 11, tức là có giá trị từ 0-3 dạng thập phân. Đặt giá trị này là i. còn lại 4 bit giữa của B sẽ có giá trị trong khoảng từ 0 đến 15 dạng thập phân (vì dạng nhị phân của B nằm trong khoảng 0000-1111). Đặt giá trị này là j. Tra trong bảng số S1 ở trên hàng thứ i và cột thứ j. Đó là một số trong khoảng từ 0 đến 15 và biểu diễn nó bởi một khối 4 bit. Khối đó là đầu ra S1(B) của S1 cho đầu vào B. Ví dụ, khối đầu vào B1 = 011000, bit đầu tiên là “0” và bit cuối cùng “0” 00= 0 => i=0. Đây là hàng 0. bốn bit giữa là “1100”, 1101 = 12=> j=12. vì vậy cột là cột số 12. Tìm tới hàng 0 cột 12 (0,12) = 5, 5 nhị phân là 0101. Do đó S1(B1) = 0101. Ta có các bảng xác định S2, S3, …S8 như sau: 

Đối với vòng đầu tiên, đã đã tính toán và có: K1 E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111 Từ các bảng trên với B1, B2, …, B8 đã xác định ta tính được: S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111 Cuối cùng trong việc tính toán f là làm một hàm hoán vị P của các đầu ra S-box để có được giá trị cuối cùng của f: f(R0,K1) = P(S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) ) Hoán vị P được xác định trong bảng dưới đây: 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

Từ đầu ra của 8 boxes: S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111 Ta có: f(R0,K1) = 0010 0011 0100 1010 1010 1001 1011 1011 R1 = L0 f(R0,K1) = 1100 1100 0000 0000 1100 1100 1111 1111 0010 0011 0100 1010 1010 1001 1011 1011 = 1110 1111 0100 1010 0110 0101 0100 0100

Vòng lặp tiếp theo, sẽ có L2 = R1, R2 = L1 f(R1, K2) cứ làm tương tự trên cho 16 vòng lặp.

Vòng cuối cùng ta có các khối L16R16. Ta đảo ngược thứ tự của 2 khối và áp dụng một hoán vị IP­-1 được xác định bởi bảng sau: IP-1

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

Xử lý tất cả 16 khối sử dụng phương pháp xác định như trên, tới vòng lặp thứ 16 ta có được: L16 = 0100 0011 0100 0010 0011 0010 0011 0100 R16 = 0000 1010 0100 1100 1101 1001 1001 0101 Chúng ta đảo ngược thứ tự của 2 khối này và áp dụng hoán vị cuối cùng R16L16 = 0000 1010 0100 1100 1101 1001 1001 01010100 0011 0100 0010 0011 0010 0011 0100 IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101 Chuyển đổi IP-1 về dạng thập lục phân ta được: 85E813540F0AB405 

Kết luận: Vậy dạng mã hóa của X = 0123456789ABCDEF là

 C = 85E813540F0AB405