DES Key Schedule sinh 16 round key 48-bit từ khóa master 56-bit (64-bit input với 8 parity bit). Quá trình:
Đầu vào
- 64-bit key: bit 1..64 (MSB first). Bit 8, 16, 24, 32, 40, 48, 56, 64 là parity bit (odd parity).
- Loại bỏ parity → 56-bit effective key.
Bước 1: Permuted Choice 1 (PC-1) — 64→56 bit, permute + split
Bảng PC-1 (56 entry, index 1-based từ key 64-bit sau khi drop parity):
PC-1 Table (output 56-bit: C₀[28] || D₀[28]):
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
# Left 28-bit (C₀): 57,49,41,33,25,17,9,1, 58,50,42,34,26,18,10,2, 59,51,43,35,27,19,11,3
# Right 28-bit (D₀): 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
Kết quả: 2 nửa C₀ (28-bit) và D₀ (28-bit).
Bước 2: Left Circular Shift (Rotation) mỗi vòng
| Vòng (Round) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Shift count | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
Mỗi vòng: Cᵢ = ROTL(Cᵢ₋₁, shift), Dᵢ = ROTL(Dᵢ₋₁, shift). Tổng shift = 28 bit → sau 16 vòng quay về C₀,D₀.
Bước 3: Permuted Choice 2 (PC-2) — 56→48 bit (Compression D-box)
Từ (Cᵢ, Dᵢ) 56-bit → chọn 48-bit làm Round Key Kᵢ:
PC-2 Table (48 entry):
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
# Input indexing: Cᵢ[1..28] = positions 1..28, Dᵢ[1..28] = positions 29..56
# Output: Kᵢ[1..48] = PC-2(Cᵢ||Dᵢ)
Mỗi vòng dùng Kᵢ khác nhau. Giải mã: dùng K₁₆, K₁₅, ..., K₁ (thứ tự ngược).
Đặc điểm Key Schedule DES
- Weak Keys (4): C₀/D₀ all-0 hoặc all-1 → mọi round key giống nhau (self-inverse). Key: 0x0101010101010101, 0xFEFEFEFEFEFEFEFE, 0x1F1F1F1F0E0E0E0E, 0xE0E0E0E0F1F1F1F1 (with parity).
- Semi-weak Keys (6 pairs): K₁, K₂: E(K₁, E(K₂, P)) = P. Key schedule đối xứng.
- Complement Property: E(K, P) = C ⇒ E(K̅, P̅) = C̅. Giảm brute-force 1 bit.
- Related-key weakness: Key schedule tuyến tính, rotation đơn giản → related-key attack khả thi (nhưng không thực tế).
Triển khai an toàn (nếu buộc dùng DES/3DES legacy)
- Kiểm tra weak/semi-weak key → reject.
- Dùng 3-key 3DES (K1, K2, K3 độc lập) — 112-bit security.
- Constant-time implementation (no table lookup branch trên key bits).
- HSM/KMS quản lý key, không bao giờ export plaintext key.
- Migration plan sang AES-256-GCM / ChaCha20-Poly1305.
Lưu ý: DES đã deprecated hoàn toàn (NIST SP 800-131A Rev 2, 2023). Chỉ tồn tại trong hệ thống legacy (banking mainframe, HSM cũ, một số protocol cũ). Học tập mục đích hiểu lịch sử và thiết kế Feistel.