Ở bài viết này, mình sẽ không thảo luận về lý thuyết của tiêu chuẩn mã hóa dữ liệu (Data Encryption Standard - DES), hay cụ thể là Simplified DES. Thay vào đó, mình sẽ thực hành mã hóa bằng tay từng bước thuật toán Simplified DES để tìm ciphertext và thực hiện giải mã ciphertext đó thông qua công cụ SageMath để kiểm tra xem kết quả nhận được có trùng khớp với plaintext trước đó hay không.
Cùng bắt tay thực hiện nào!
Task 1: Thực hiện mã hóa Simplified DES (Encryption) bằng tay để tìm ciphertext
Mình sẽ sử dụng các chữ cái đầu của chữ lót và tên cá nhân để phục vụ cho việc khởi tạo input, cụ thể như sau:
Tên: Minh Khanh
M = 4d = 0100 1101, lấy đây là giá trị Plaintext 8 bits
K = 4b = 0100 1011, thêm 10 vào sau làm giá trị Key 10 bits
Vậy, input của mình bao gồm:
- Plaintext =
0100 1101 - Key =
0100 1011 10
1.1. Initial permutation
Đánh thứ tự các bits của plaintext:
| b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
Hoán vị theo quy tắc sau:
(b0, b1, b2, b3, b4, b5, b6, b7) → (b1, b5, b2, b0, b3, b7, b4, b6)
| b1 | b5 | b2 | b0 | b3 | b7 | b4 | b6 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
Vậy, initial permutation = 1100 0110
1.2. Subkeys
Đánh thứ tự các bits của key:
| b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7 | b8 | b9 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
a. Đầu tiên, 10 bits của key sẽ được hoán vị theo quy tắc:
(b0, b1, b2, b3, b4, b5, b6, b7, b8, b9) → (b2, b4, b1, b6, b3, b9, b0, b8, b7, b5)
| b2 | b4 | b1 | b6 | b3 | b9 | b0 | b8 | b7 | b5 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
b. Chia làm hai nửa, mỗi bên 5 bits: (0, 1, 1, 1, 0), (0, 0, 1, 1, 0)
c. Với lượt 1, mỗi bên sẽ dịch 1 bit sang trái theo vòng theo quy luật:
(a, b, c, d, e), (f, g, h, i, j) → (b, c, d, e, a), (g, h, i, j, f)
Ta được,
(0, 1, 1, 1, 0), (0, 0, 1, 1, 0) → (1, 1, 1, 0, 0), (0, 1, 1, 0, 0)
| b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7 | b8 | b9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
d. Ta được subkey đầu tiên bằng cách lấy các bit ở vị trí (5, 2, 6, 3, 7, 4, 9, 8) là
K1 = 01101000
e. Với lượt 2, kết quả của bước 3 sẽ được dịch 2 bits sang trái:
(b, c, d, e, a), (g, h, i, j, f) → (d, e, a, b, c), (i, j, f, g, h)
Ta được,
(1, 1, 1, 0, 0), (0, 1, 1, 0, 0) → (1, 0, 0, 1, 1), (1, 0, 0, 0, 1)
| b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7 | b8 | b9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
Ta được subkey 2 bằng cách lấy các bits ở các vị trí tương tự như subkey 1:
K2 = 10010110
Quy tắc:
Nếu key là k0 k1 k2 k3 k4 k5 k6 k7 k8 k9 thì 2 subkey sẽ là:
K1 = k0 k6 k8 k3 k7 k2 k9 k5K2 = k7 k2 k5 k4 k9 k1 k8 k0
The Feistel step
- Initial permutation =
11000110 - Chia làm 2 nửa, nửa bên phải là
0110được mix với subkeyK1.
Trước tiên, 4 bits 0110 được mở rộng thành 8 bits theo quy tắc sau:
Hay
b0 b1 b2 b3 → b3 b0 b1 b2 b1 b2 b3 b0
Ta được kết quả là: 0 1 1 0 → 0 0 1 1 1 1 0 0
Sau đó mang 8 bits này XOR với K1:
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | |
|---|---|---|---|---|---|---|---|---|
| ⊕ | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| = | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
4 bits đầu tiên 0101 được dùng làm input cho S0, và 4 bits tiếp theo 0100 được dùng làm input cho S1:
-
2 bits ngoài cùng là
01dùng làm hàng, tức là hàng thứ 1, 2 bits trong cùng là10dùng làm cột, tức là cột thứ 2. Lấy giá trị ở hàng 1 cột 2 của bảngS0ta được01. -
2 bits ngoài cùng là
00dùng làm hàng, tức là hàng thứ 0, 2 bits trong cùng là10dùng làm cột, tức là cột thứ 2. Lấy giá trị ở hàng 0 cột 2 của bảngS1ta được10.
Kết hợp lại ta được 0110
Permuted:
Công thức:
(b0, b1, b2, b3) → (b1, b3, b2, b0)
Suy ra, kết quả permuted là 1010
Kết quả này XOR với nửa bên trái:
1010 ⊕ 1100 = 0110 và ghép với nửa bên phải 0110 tạo thành 0110 0110
- Đảo vị trí 2 nửa:
0110 0110 - Nửa trái hiện tại là
0110và nửa phải là0110, vớiK2 = 10010110.
Mở rộng nửa bên phải: 0 1 1 0 → 0 0 1 1 1 1 0 0
XOR với K2:
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | |
|---|---|---|---|---|---|---|---|---|
| ⊕ | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| = | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Đặt 2 nửa 1010 và 1010 vào S0 và S1 như trên ta được:
-
2 bits ngoài cùng là
10dùng làm hàng, tức là hàng thứ 2, 2 bits trong cùng là01dùng làm cột, tức là cột thứ 1. Lấy giá trị ở hàng 2 cột 1 của bảngS0ta được10 -
2 bits ngoài cùng là
10dùng làm hàng, tức là hàng thứ 2, 2 bits trong cùng là01dùng làm cột, tức là cột thứ 1. Lấy giá trị ở hàng 2 cột 1 của bảngS1ta được00
Kết hợp lại ta được 1000
Theo công thức phía trên, kết quả permuted là 0001
Kết quả này XOR với nửa bên trái:
0001 ⊕ 0110 = 0111 và ghép với nửa bên phải 0110 tạo thành 0111 0110
- Hoán vị đảo cuối cùng:
0111 0110 → 1010 1101
Vậy, ciphertext = 1010 1101
Task 2: Thực hiện mã hóa và giải mã Simplified DES (Decryption) để tìm ngược lại Plaintext thông qua công cụ SageMath
a. Thực hiện mã hóa plaintext với P và K lấy từ bài 1:
P = 0100 1101K = 0100 1011 10
Code mẫu minh họa:
from sage.crypto.block_cipher.sdes import SimplifiedDES
sdes = SimplifiedDES();
P = [0, 1, 0, 0, 1, 1, 0, 1] # Plaintext
K = [0, 1, 0, 0, 1, 0, 1, 1, 1, 0] # Key
C = sdes.encrypt(P, K)
print(C)
Kết quả thực thi đoạn code trên SageMath:
Kết quả ciphertext khi chạy trên Sage hoàn toàn trùng khớp với kết quả mà mình đã thực hành bằng tay ở Task 1.
b. Thực hiện giải mã ciphertext với C lấy từ kết quả trên:
C = 1010 1101
Code mẫu minh họa:
from sage.crypto.block_cipher.sdes import SimplifiedDES
sdes = SimplifiedDES();
C = [1, 0, 1, 0, 1, 1, 0, 1] # Ciphertext
K = [0, 1, 0, 0, 1, 0, 1, 1, 1, 0] # Key
P = sdes.decrypt(C, K)
print(P)
Kết quả thực thi đoạn code trên SageMath:
Kết luận: Plaintext nhận được khi chạy trên Sage hoàn toàn trùng khớp với plaintext ban đầu.