›
›

Giáo trình Lý thuyết mật mã - Chương 3: Chuẩn mã dữ liệu

pdf 48 trang ngocly 2790
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết mật mã - Chương 3: Chuẩn mã dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_ly_thuyet_mat_ma_chuong_3_chuan_ma_du_lieu.pdf

Nội dung text: Giáo trình Lý thuyết mật mã - Chương 3: Chuẩn mã dữ liệu

  1. Ch−ơng 3 Chuẩn m dữ liệu 3.1. Mở đầu. Ngày 15.5.1973. Uỷ ban tiêu chuẩn quốc gia Mỹ đ công bố một khuyến nghị cho các hệ mật trong Hồ sơ quản lý liên bang. Điều này cuối cùng đ dẫn đến sự phát triển của Chuẩn m dữ liệu (DES) và nó đ trở thành một hệ mật đ−ợc sử dụng rộng ri nhất trên thế giới. DES đ−ợc IBM phát triển và đ−ợc xem nh− một cải biên cuả hệ mật LUCIPHER. Lần đầu tiên DES đ−ợc công bố trong Hồ sơ Liên bang vào ngày 17.3.1975. Sau nhiều cuộc trânh luận công khai, DES đ đ−ợc chấp nhận chọn làm chuẩn cho các ứng dụng không đ−ợc coi là mật vào 5.1.1977. Kể từ đó cứ 5 năm một lần, DES lại đ−ợc Uỷ ban Tiêu chuẩn Quốc gia xem xét lại. Lần đổi mới gàn đây nhất của DES là vào tháng 1.1994 và tiếp tới sẽ là 1998. Ng−ời ta đoán rằng DES sẽ không còn là chuẩn sau 1998. 3.2. Mô tả DES Mô tả đầy đủ của DES đ−ợc nêu trong Công bố số 46 về các chuẩn xử lý thông tin Liên bang (Mỹ) vào 15.1.1977. DES m hoá một xâu bít x của bẳn rõ độ dài 64 bằng một khoá 54 bít. Bản m nhậ đ−ợc cũng là một xâu bít có độ dài 48. Tr−ớc hết ta mô tả ở mức cao của hệ thống. Thuật toán tiến hành theo 3 giai đoạn: 1.Với bản rõ cho tr−ớc x, một xâu bít x 0 sẽ đ−ợc xây dựng bằng cách hoán vị các bít của x theo phép hoán vị cố định ban đầu IP. Ta viết:x 0= IP(X) = L 0R0, trong đó L 0 gồm 32 bít đầu và R 0 là 32 bít cuối. 2. Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tính L iRi, 1 ≤ i ≤16 theo quy tắc sau: Li = R i-1 Ri = L i-1 ⊕ f(R i-1,K i) trong đó ⊕ kí hiệu phép hoặc loại trừ của hai xâu bít (cộng theo modulo 2). f là một hàm mà ta sẽ mô tả ở sau, còn K 1,K 2, . . . ,K 16 là các xâu bít độ dài 48 đ−ợc tính nh− hàm của khoá K. ( trên thực tế mỗi K i là một phép chọn hoán
  2. vị bít trong K). K 1, . . ., K 16 sẽ tạo thành bảng khoá. Một vòng của phép m hoá đ−ợc mô tả trên hình 3.1. -1 3. áp dụng phép hoán vị ng−ợc IP cho xâu bít R 16 L16 , ta thu đ−ợc bản -1 m y. Tức là y=IP (R 16 L16 ). Hy chú ý thứ tự đ đảo của L 16 và R 16 . Hình 3.1. Một vong của DES Li-1 Ri-1 K f i + Li Ri Hàm f có hai biến vào: biến thứ nhất A là xâu bít độ dài 32, biến thứ hai J là một xâu bít độ dài 48. Đầu ra của f là một xâu bít độ dài 32. Các b−ớc sau đ−ợc thực hiện: 1. Biến thứ nhất A đ−ợc mở rộng thành một xâu bít độ dài 48 theo một hàm mở rộng cố định E. E(A) gồm 32 bít của A (đ−ợc hoán vị theo cách cố định) với 16 bít xuất hiện hai lần. 2. Tính E(A) ⊕ J và viết kết quả thành một chuỗi 8 xâu 6 bít = B1B2B3B4B5B6B7B8. 3.B−ớc tiếp theo dùng 8 bảng S 1, S 2, ,S 8 ( đ−ợc gọi là các hộp S ). Với mỗi S i là một bảng 4 ì16 cố định có các hàng là các số nguyên từ 0 đến 15. Với xâu bít có độ dài 6 (Kí hiệu B i = b 1b2b3b4b5b6), ta tính S j(B j) nh− sau: Hai bít b 1b6 xác định biểu diễn nhị phân của hàng r của S j ( 0 ≤ r ≤ 3) và bốn bít (b 2b3b4b5) xác định biểu diễn nhị phân của cột c của S j ( 0 ≤ c ≤ 15 ). Khi đó S j(B j) sẽ xác định phần tử S j(r,c); phần tử này viết d−ới dạng nhị phân là một xâu bít có độ dài 4. ( Bởi vậy, mỗi S j có thể đ−ợc coi là một hàm m mà đầu vào là một xâu bít có độ dài 2 và một xâu bít có độ dài 4, còn đầu ra là một xâu bít có độ dài 4). Bằng cách t−ơng tự tính các C j = S j(B j), 1 ≤ j ≤ 8. 4. Xâu bít C = C 1C2 C 8 có độ dài 32 đ−ợc hoán vị theo phép hoán vị cố định P. Xâu kết quả là P(C) đ−ợc xác định là f(A,J).
  3. Hàm f đ−ợc mô tả trong hình 3.2. Chủ yếu nó gômg một phép thế ( sử dụng hộp S ), tiếp sau đó là phép hoán vị P. 16 phép lặp của f sẽ tạo nên một hệ mật tích nêu nh− ở phần 2.5. Hình 3.2. Hàm f của DES A J E E(A) + B1 B2 B3 B4 B5 B6 B7 B8 S S S S S S S S 1 2 3 4 5 6 7 8 c1 c2 c3 c4 c5 c6 c7 c8 f(A,J) Trong phần còn lại của mục này, ta sẽ mô tả hàm cụ thể đ−ợc dùng trong DES. Phép hoán vị ban đầu IP nh− sau:
  4. IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 31 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 này có nghĩa là bít thứ 58 của x là bít đầu tiên của IP(x); bít thứ 50 của x là bít thứ hai của IP(x), .v.v . . . Phép hoán vi ng−ợc IP -1 là: 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 Hàm mở rộng E đ−ợc xác đinh theo bảng sau: Bảng chọn E bít 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 Tám hộp S là:
  5. S1 14 4 13 1 2 15 11 8 3 10 3 12 5 9 1 7 1 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S1 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 5 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 12 1 10 15 9 2 6 8 0 13 3 4 14 7 15 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 11 7 6 0 8 13 S7 4 11 12 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
  6. S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 Và phép hoán vị P có dạng: P 16 7 20 29 12 28 1 15 23 5 18 31 32 27 3 19 13 30 22 11 4 Cuối cung ta cần mô tả việc tính toán bảng khoá từ khoá K. Trên thực tế, K là một xâu bít độ dài 64, trong đó 56 bít là khoá và 8 bít để kiểm tra tính chẵn lẻ nhằm phát hiện sai. Các bít ở các vị trí 8,16, . . ., 64 đ−ợc xác định sao cho mỗi byte chứa một số lẻ các số "1". Bởi vậy một sai sót đơn lẻ có thể phát hiện đ−ợc trong mỗi nhóm 8 bít. Các bít kiểm tra bị bỏ qua trong quá trình tính toán bảng khoá. 1. Với một khoá K 64 bít cho tr−ớc, ta loại bỏ các bít kiểm tra tính chẵn lẻ và hoán vị các bít còn lại của K theo phép hoán vị cố định PC-1. Ta viết: PC-1(K) = C 0D0 2. Với i thay đổi từ 1 đến 16: 3. Ci = LS i(C i-1) Di = LS i(Di-1) Việc tính bảng khoá đ−ợc mô tả trên hình 3.3 Các hoán vị PC-1 và PC-2 đ−ợc dùng trong bảng khoá là:
  7. PC-1 57 49 41 33 25 17 1 58 50 42 34 26 10 2 59 51 43 35 19 11 3 60 52 44 63 55 47 39 31 23 7 62 54 46 38 30 14 6 61 53 45 37 21 13 5 28 20 12 Hình 3.3 Tính bảng khoá DES. K PC -1 C 0 D 0 LS 1 LS 1 C 1 D 1 PC -2 K1 . . LS 16 LS 16 C 16 D 16 PC -2 K16
  8. 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 Bây giờ ta sẽ đ−a ra bảng khoá kết quả. Nh− đ nói ở trên, mỗi vòng sử dụng một khoá 48 bít gồm 48 bít nằm trong K. Các phần tử trong các bảng d−ới đây biểu thị các bít trong K trong các vòng khoá khác nhau. Vòng 1 10 51 34 60 49 17 35 57 2 9 19 42 3 35 26 25 44 58 59 1 36 27 18 41 22 28 39 54 37 4 47 30 5 53 23 29 61 21 38 63 15 20 45 14 13 62 55 31 Vòng 2 2 43 26 52 41 9 25 49 59 1 11 34 60 27 18 17 36 50 51 58 57 19 10 33 14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55 7 12 37 6 5 54 47 23 Vòng 3 51 27 10 36 25 58 9 33 43 50 60 18 44 11 2 1 49 34 35 42 41 3 59 17 61 4 15 30 13 47 23 6 12 29 62 5 37 28 14 39 54 63 21 53 20 38 31 7 Vòng 4 35 11 59 49 9 42 58 17 27 34 44 2 57 60 51 50 33 18 19 26 25 52 43 1 45 55 62 14 28 31 7 53 63 13 46 20 21 12 61 23 38 47 5 37 4 22 15 54
  9. Vòng 5 19 60 43 33 58 26 42 1 11 18 57 51 41 44 35 34 17 2 3 10 9 36 27 50 29 39 46 61 12 15 54 37 47 28 30 4 .5 63 45 7 22 31 20 21 55 6 62 38 Vòng 6 3 44 27 17 42 10 26 50 60 2 41 35 25 57 19 18 1 51 52 59 58 49 11 34 13 23 30 45 63 62 38 21 31 12 14 55 20 47 29 54 6 15 4 5 39 53 46 22 Vòng 7 52 57 11 1 26 59 10 34 44 51 25 19 9 41 3 2 50 35 36 43 42 33 60 18 28 7 14 29 47 46 22 5 15 63 61 39 4 31 13 38 53 62 55 20 23 38 30 6 Vòng 8 36 41 60 50 10 43 59 18 57 35 9 3 58 25 5251 34 19 49 27 26 17 44 2 12 54 61 13 31 30 6 20 62 47 45 23 55 15 28 22 37 46 39 4 721 14 53 Vòng 9 57 33 52 42 2 35 51 10 49 27 1 60 50 17 44 43 26 11 41 19 18 9 36 59 4 46 53 5 23 22 61 12 54 39 37 15 47 7 20 14 29 38 31 63 62 13 6 45 Vòng 10 41 17 36 26 51 19 35 59 33 11 50 44 34 1 57 27 10 60 25 3 2 58 49 43 55 30 37 20 7 6 45 63 38 23 21 62 31 54 4 61 13 22 15 47 46 28 53 29
  10. Vòng 11 25 1 49 10 35 3 19 43 17 60 34 57 18 50 41 11 59 44 9 52 51 42 33 27 39 14 21 4 54 53 29 47 22 7 5 46 15 38 55 45 28 6 62 31 30 12 37 13 Vòng 12 9 50 33 59 19 52 3 27 1 44 18 41 2 34 25 60 43 57 58 36 35 26 17 11 23 61 5 55 38 37 13 31 6 54 20 30 62 22 39 29 12 53 46 15 14 63 21 28 Vòng 13 58 34 17 43 3 36 52 11 50 57 2 25 51 18 9 44 27 41 42 49 19 10 1 60 7 45 20 39 22 21 28 15 53 38 4 14 46 6 23 13 63 37 30 62 61 47 5 12 Vòng 14 42 18 1 27 52 49 36 60 34 41 51 9 35 2 58 57 11 25 26 33 3 59 50 44 54 29 4 23 6 5 12 62 37 22 55 61 30 53 7 28 47 21 14 46 45 31 20 63 Vòng 15 26 2 50 11 36 33 49 44 18 25 35 58 19 51 42 41 60 9 10 17 52 43 34 57 38 13 55 7 53 20 63 46 21 6 39 45 14 37 54 12 31 5 61 30 29 15 4 47 Vòng 16 18 59 42 3 57 25 41 36 10 17 27 50 11 43 34 33 52 1 2 9 44 35 26 49 30 5 47 62 45 12 55 58 13 61 31 37 6 27 46 4 23 28 53 22 21 7 62 39 Phép giải m đ−ợc thực hiện nhờ dùng cùng thuật toán nh− phép m nếu đầu vào là y nh−ng dùng bảng khoá theo thứ tự ng−ợc lại K 16 , K 1. Đầu ra của thuật toán sẽ là bản rõ x.
  11. 3.2.1. Một ví dụ về DES. Sau đây là một ví dụ về phép m DES. Giả sử ta m bản rõ (ở dạng m hexa - hệ đếm 16): 0123456789ABCDEF Bằng cách dùng khoá 123457799BBCDFF1 Khoá ở dạng nhị phân ( không chứa các bít kiểm tra) là: 00010010011010010101101111001001101101111011011111111000 Sử dụng IP, ta thu đ−ợc L 0 và R 0 (ở dạng nhị phân) nh− sau: L 0 = 1100110000000000110010011111111 L1 =R 0 = 11110000101010101111000010101010 Sau đó thực hiện 16 vòng của phép m nh− sau: E(R 0) = 011110100001010101010101011110100001010101010101 K1 = 000110110000001011101111111111000111000001110010 E(R 0)⊕ K1 = 011000010001011110111010100001100110010100100111 S-box outputs 01011100100000101011010110010111 f(R 0,K 1) = 00100011010010101010100110111011 L2 = R 1 = 11101111010010100110010101000100 E(R 1) = 011101011110101001010100001100001010101000001001 K2 = 011110011010111011011001110110111100100111100101 E(R 1)⊕ K2 = 000011000100010010001101111010110110001111101100 S-box outputs 11111000110100000011101010101110 f(R 1,K 2) = 00111100101010111000011110100011 L3 = R 2 = 11001100000000010111011100001001 E(R 2) = 011101011110101001010100001100001010101000001001 K3 = 011110011010111011011001110110111100100111100101 E(R 2)⊕ K3 = 000011000100010010001101111010110110001111101100 S-box outputs 11111000110100000011101010101110 f(R 2,K 3) = 00111100101010111000011110100011 L4 = R 3 = 11001100000000010111011100001001
  12. E(R 2) = 111001011000000000000010101110101110100001010011 K 3 = 010101011111110010001010010000101100111110011001 E(R 2) ⊕K3 = 101100000111110010001000111110000010011111001010 S-box outputs 00100111000100001110000101101111 f (R 2,K 3) = 01001101000101100110111010110000 L 4 =R 3 = 10100010010111000000101111110100 E(R 3) =01010000010000101111100000000101011111111010100 K 4 = 011100101010110111010110110110110011010100011101 E(R 3) ⊕K4 = 001000101110111100101110110111100100101010110100 S-box outputs 00100001111011011001111100111010 f (R 3,K 4) = 10111011001000110111011101001100 L 5 = R 4 = 01110111001000100000000001000101 E(R 4) = 101110101110100100000100000000000000001000001010 K 5 = 011111001110110000000111111010110101001110101000 E(R 4) ⊕ K 5 = 110001100000010100000011111010110101000110100010 S-box outputs 01010000110010000011000111101011 f (R 4,K 5) = 00101000000100111010110111000011 L 6 = R 5 = 10001010010011111010011000110111 E(R 5) = 110001010100001001011111110100001100000110101111 K 6 = 011000111010010100111110010100000111101100101111 E(R 5) ⊕ K 6 =101001101110011101100001100000001011101010000000 S-box outputs 01000001111100110100110000111101 f (R 5,K 6) = 10011110010001011100110100101100 L 7 = R 6 = 11101001011001111100110101101001 E(R 6) = 111101010010101100001111111001011010101101010011 K 7 = 111011001000010010110111111101100001100010111100 E(R 6) ⊕ K 7 = 000110011010111110111000000100111011001111101111 S- box outputs 00010000011101010100000010101101 f (R 6,K 7) = 10001100000001010001110000100111 L 8 = R 7 = 00000110010010101011101000010000 E(R 7) = 000000001100001001010101010111110100000010100000 K 8 = 111101111000101000111010110000010011101111111011 E(R 7) ⊕ K 8 = 111101110100100001101111100111100111101101011011 S-box outputs 01101100000110000111110010101110 f (R 7,K 8) = 00111100000011101000011011111001 L 9 = R 8 = 11010101011010010100101110010000 E(R 8) = 011010101010101101010010101001010111110010100001 K 9 = 111000001101101111101011111011011110011110000001 E(R 8) ⊕ K 9 = 100010100111000010111001010010001001101100100000
  13. S-box outputs 00010001000011000101011101110111 f (R 8,K 9) = 00100010001101100111110001101010 L 10 = R 9 = 00100100011111001100011001111010 E(R 9) = 000100001000001111111001011000001100001111110100 K 10 = 101100011111001101000111101110100100011001001111 E(R 9) ⊕ K 10 = 101000010111000010111110110110101000010110111011 S-box outputs 11011010000001000101001001110101 f (R 9,K 10 ) = 01100010101111001001110000100010 L 11 = R 10 = 10110111110101011101011110110010 E(R 10 ) = 010110101111111010101011111010101111110110100101 K 11 = 001000010101111111010011110111101101001110000110 E(R 10 ) ⊕ K 11 = 011110111010000101111000001101000010111000100011 S-box outputs 01110011000001011101000100000001 f (R 10 ,K 11 ) = 11100001000001001111101000000010 L 12 = R 11 = 11000101011110000011110001111000 E(R 11 ) = 011000001010101111110000000111111000001111110001 K 12 = 011101010111000111110101100101000110011111101001 E(R 11 ) ⊕ K 12 = 000101011101101000000101100010111110010000011000 S-box outputs 01110011000001011101000100000001 f (R 11 ,K 12 ) = 11000010011010001100111111101010 L 13 = R 12 = 01110101101111010001100001011000 E(R 12 ) = 001110101011110111111010100011110000001011110000 K 13 = 100101111100010111010001111110101011101001000001 E(R 12 ) ⊕ K 13 = 101011010111100000101011011101011011100010110001 Sbox outputs 10011010110100011000101101001111 f (R 12 ,K 13 ) = 11011101101110110010100100100010 L 14 = R 13 = 00011000110000110001010101011010 E(R 13 ) = 000011110001011000000110100010101010101011110100 K 13 = 010111110100001110110111111100101110011100111010 E(R 13 ) ⊕ K 14 = 010100000101010110110001011110000100110111001110 S-box outputs 01100100011110011001101011110001 f (R 13 ,K 14 ) = 10110111001100011000111001010101 L 15 = R 14 = 11000010100011001001011000001101 E(R 14 ) = 111000000101010001011001010010101100000001011011 K 15 = 101111111001000110001101001111010011111100001010 E(R 14 ) ⊕ K 15 = 010111111100010111010100011101111111111101010001 S-box outputs 10110010111010001000110100111100 f (R 14 ,K 15 ) = 01011011100000010010011101101110 R 15 = 01000011010000100011001000110100 E(R 15 ) = 001000000110101000000100000110100100000110101000 K 16 = 110010110011110110001011000011100001011111110101 E(R 15 ) ⊕ K 16 = 111010110101011110001111000101000101011001011101
  14. S-box outputs 10100111100000110010010000101001 f(R 15 ,K 16 ) = 11001000110000000100111110011000 R 16 = 00001010010011001101100110010101 -1 Cuối cùng áp dụng IP vào L 16 ,R 16 ta nhận đ−ợc bản m hexa là: 8 5 E 8 1 3 5 4 0 F 0 A B 4 0 5 3.3. Tranh luận về DES. Khi DES đ−ợc đề xuất nh− một chuẩn mật m, đ có rất nhiều ý kiến phê phán. Một lý do phản đối DES có liên quan đến các hộp S. Mọi tính toán liên quan đến DES ngoại trừ các hộp S đều tuyến tính, tức việc tính phép hoặc loại trừ của hai đầu ra cũng giống nh− phép hoặc loại trừ của hai đầu vào rồi tính tóan đầu ra. Các hộp S - chứa đựng thành phần phi tuyến của hệ mật là yếu tố quan trong nhất đối với độ mật của hệ thống( Ta đ thấy trong ch−ơng 1 là các hệ mật tuyến tính - chẳng hạn nh− Hill - có thể dễ dàng bị m thám khi bị tấn công bằng bản rõ đ biết). Tuy nhiên tiêu chuẩn xây dựng các hộp S không đ−ợc biết đầy đủ. Một số ng−ời đ gợi ý là các hộp S phải chứa các "cửa sập" đ−ợc dấu kín, cho phép Cục An ninh Quốc gia Mỹ (NSA) giải m đ−ợc các thông báo nh−ng vẫn giữ đ−ợc mức độ an toàn của DES. Dĩ nhiên ta không thể bác bỏ đ−ợc khẳng định này, tuy nhiên không có một chứng cớ nào đ−ợc đ−a ra để chứng tỏ rằng trong thực tế có các cửa sập nh− vậy. Năm 1976 NSA đ khẳng định rằng, các tính chất sau của hộp S là tiêu chuẩn thiết kế: P0 Mỗi hàng trong mỗi hộp S là một hoán vị của các số nguyên 0, 1, . . . , 15. P1 Không một hộp S nào là một hàm Affine hoặc tuyến tính các đầu vào của nó. P2 Việc thay đổi một bít vào của S phải tạo nên sự thay đổi ít nhất là hai bít ra. P3 Đối với hộp S bất kì và với đầu vào x bất kì S(x) và S(x ⊕ 001100) phải khác nhau tối thiểu là hai bít ( trong đó x là xâu bít độ dài 6 ). Hai tính chất khác nhau sau đây của các hộp S có thể coi là đ−ợc rút ra từ tiêu chuẩn thiết kế của NSA. P4 Với hộp S bất kì, đầu vào x bất kì và với e, f ∈{0,1}: S(x) ≠S(x ⊕ 11ef00). P5 Với hộp S bất kì , nếu cố định một bít vào và xem xét giá trị của một bít đầu ra cố định thì các mẫu vào để bít ra này bằng 0 sẽ xấp xỉ bằng số mẫu ra để bít đó bằng 1.( Chú ý rằng, nếu cố định giá trị bít vào thứ nhất hoặc bít vào thứ 6 thì có 16 mẫu vào làm cho một bít ra cụ thể bằng 0 và có 16 mẫu
  15. vào làm cho bít này bằng 1. Với các bít vào từ bít thứ hai đến bít thứ 5 thì điều này không còn đúng nữa. Tuy nhiên phân bố kết quả vẫn gần với phân bố đều. Chính xác hơn, với một hộp S bất kì, nếu ta cố định giá trị của một bít vào bất kì thì số mẫu vào làm cho một bít ra cố định nào đó có giá trị 0 (hoặc 1) luôn nằm trong khoảng từ 13 đến 19). Ng−ời ta không biết rõ là liệu có còn một chuẩn thiết kế nào đầy đủ hơn đ−ợc dùng trong việc xây dựng hộp S hay không. Sự phản đối xác đáng nhất về DES chính là kích th−ớc của không gian khoá: 2 56 là quá nhỏ để đảm bảo an toàn thực sự. Nhiều thiết bi chuyên dụng đ đ−ợc đè xuất nhằm phục vụ cho việc tấn công với bản rõ đ biết. Phép tấn công này chủ yếu thực hiện tìm khoá theo ph−ơng pháp vét cạn. Tức với bản rõ x 64 bít và bản m y t−ơng ứng, mỗi khoá đều có thể đ−ợc kiểm tra cho tới khi tìm đ−ợc một khoá K thảo mn e K(x) = y. Cần chú ý là có thể có nhiều hơn một khoá K nh− vậy). Ngay từ năm 1977, Diffie và Hellman đ gợi ý rằng có thể xây dựng một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra đ−ợc 10 6khoá/giây. Một máy có thể tìm toàn bộ không gian khoá cỡ 10 6 trong khoảng 1 ngày. Họ −ớc tính chi phí để tạo một máy nh− vậy khoảng 2.10 7$. Trong cuộc hội thảo tại hội nghị CRYPTO'93, Michael Wiener đ đ−a ra một thiết kế rất cụ thể về máy tìm khoá. Máy này xây dựng trên một chíp tìm khoá, có khả năng thực hiện đồng thời 16 phép m và tốc độ tới 5 ì10 7 khoá/giây. Với công nghệ hiện nay, chi phí chế tạo khoảng 10,5$/chíp. Giá của một khung máy chứa 5760 chíp vào khoảng 100.000$ và nh− vậy nó có khả năng tìm ra một khoá của DES trong khoảng 1,5 ngày. Một thiết bị dùng 10 khung máy nh− vậy có giá chừng 10 6 $ sẽ giảm thời gian tìm kiếm khoá trng bình xuống còn 3,5 giờ. 3.4. DES trong thực tế. Mặc dù việc mô tả DES khá dài dòng song ng−ời ta có thể thực hiện DES rất hữa hiệu bằng cả phần cứng lẫn phần mền. Các phép toán duy nhất cần đ−ợc thực hiện là phép hoặc loại trừ các xâu bít. Hàm mở rộng E, các hộp S, các hoán vị IP và P và việc tính toán các giá tri K 1, . ,K 16 đều có thể thực hiện đ−ợc cùng lúc bằng tra bảng ( trong phần mền ) hoặc bằng cách nối cứng chúng thành một mạch.
  16. Các ứng dụng phần cứng hiện thời có thể đạt đ−ợc tốc độ m hoá cực nhanh. Công ty Digital Equipment đ thông báo tại hội nghị CRUPTO'92 rằng họ sẽ chế tạo một chíp có 50 ngàn tranzistor có thể m hoá với tốc độ 1 Gbít/s bằng cách dùng nhịp có tốc độ 250MHz. Giá của chíp này vào khoảng 300$. Tới năm 1991 đ có 45 ứng dụng phần cứng và ch−ơng trình cơ sở của DES đ−ợc Uỷ ban tiêu Chuẩn quốc gia Mỹ (NBS) chấp thuận. Một ứng dụng quan trọng của DES là trong giao dịch ngân hàng Mỹ - (ABA) DES đ−ợc dùng để m hoá các số định danh cá nhân (PIN) và việc chuyển tài khoản bằng máy thủ quỹ tự động (ATM). DES cũng đ−ợc Hệ thống chi trả giữa các nhà băng của Ngân hàng hối đoái (CHIPS) dùng để xác thực các giao dụch vào khoản trên 1,5 ì10 12 USA/tuần. DES còn đ−ợc sử dụng rộng ri trong các tổ chức chính phủ. Chẳng hạn nh− bộ năng l−ợng, Bộ T− pháp và Hệ thống dự trữ liên bang. 3.4.1. Các chế độ hoạt động của DES. Có 4 chế độ làm việc đ đ−ợc phát triển cho DES: Chế độ chuyển m điện tử (ECB), chế độ phản hồi m (CFB), chế độ liên kết khối m (CBC) và chế độ phản hồi đầu ra (OFB). Chế độ ECB t−ơng ứng với cách dùng thông th−ờng của m khối: với một dy các khối bản rõ cho tr−ớc x 1,x 2,. . .( mỗi khối có 64 bít), mỗi x i sẽ đ−ợc m hoá bằng cùng một khoá K để tạo thành một chuỗi các khối bản m y 1y2 theo quy tắc y i = e K(yi-1⊕xi) i ≥ 1. Việc sử dụng chế độ CBC đ−ợc mô tả trên hình 3.4. Hình 3.4. Chế độ CBC.
  17. x1 x2 . . . IV=y 0 + + M hoá e e Encrypt K K y1 y2 y1 y2 Giải m d d Decrypt K K . . . IV=y 0 + + x1 x2 Trong các chế độ OFB và CFB dòng khoá đ−ợc tạo ra sẽ đ−ợc cộng mod 2 với bản rõ (tức là nó hoạt động nh− một hệ m dòng, xem phần 1.1.7). OFB thực sự là một hệ m dòng đồng bộ: dòng khoá đ−ợc tạo bởi việc m lặp véc tơ khởi tạo 64 bít (véc tơ IV). Ta xác định z 0 =IV và rồi tính dòng khoá z 1z2 . . . theo quy tắc z i = e K(z i-1), i ≥1. Dy bản rõ x 1x2 . . . sau đó sẽ đ−ợc m hoá bằng cách tính y i = x i ⊕ z i,i ≥1. Trong chế độ CFB, ta bắt đầu với y 0 = IV (là một véc tơ khởi tạo 64 bít) và tạo phần tử z i của dòng khoá bằng cách m hoá khối bản m tr−ớc đó. Tức z i = e K(y i-1), i ≥1. Cũng nh− trong chế độ OFB: y i = x i ⊕ z i,i ≥1. Việc sử dụng CFB đ−ợc mô tả trên hình 3.5 (chú ý rằng hàm m DES e K đ−ợc dùng cho cả phép m và phép giải m ở các chế độ CFB và OFB). Hình 3.5. Chế độ CFB
  18. x1 x2 . . . IV=y 0 eK + eK + M hoá Encrypt y1 y2 y1 y2 . . . IV=y 0 eK + eK + Giải m Decrypt x1 x2 Cũng còn một số biến tấu của OFB và CFB đ−ợc gọi là các chế độ phản hồi K bít (1 < K < 64 ). ở đây ta đ mô tả các chế độ phản hồi 64 bít. Các chế độ phản hồi 1 bít và 8 bít th−ờng đ−ợc dùng trong thực tế cho phép m hoá đồng thời 1 bit (hoặc byte) số liệu. Bốn chế độ công tác có những −u, nh−ợc điểm khác nhau. ở chế độ ECB và OFB, sự thay đổi của một khối bản rõ x i 64 bít sẽ làm thay đổi khối bản m y i t−ơng ứng, nh−ng các khối bản m khác không bị ảnh h−ởng. Trong một số tình huống đây là một tính chất đáng mong muốn. Ví dụ, chế độ OFB th−ờng đ−ợc dùng để m khi truyền vệ tinh. Mặt khác ở các chế độ CBC và CFB, nếu một khối bản rõ x i bị thay đổi thì y i và tất cả các khối bản m tiếp theo sẽ bi ảnh h−ởng. Nh− vậy các chế độ CBC và CFB có thể đ−ợc sử dụng rất hiệu quả cho mục đích xác thực. Đặc biệt hơn, các chế độ này có thể đ−ợc dùng để tạo m xác thực bản tin ( MAC - message authentication code). MAC đ−ợc gắn thêm vào các khối bản rõ để thuyết phục Bob tin rằng, dy bản rõ đó thực sự là của Alice mà không bị Oscar giả mạo. Nh− vậy MAC đảm bảo tính toàn vẹn (hay tính xác thực) của một bản tin ( nh−ng tất nhiên là MAC không đảm bảo độ mật).
  19. Ta sẽ mô tả cáchb sử dụng chế độ BCB để tạo ra một MAC. Ta bắt đầu bằng véc tơ khởi tạ IV chứa toàn số 0. Sau đó dùng chế đô CBC để tạo các khối bản m y 1,. . . ,y n theo khoá K. Cuối cùng ta xác định MAC là y n. Alice sẽ phát đi dy các khối bản rõ x 1,x 2,. . . ,x n cùng với MAC. Khi Bob thu đ−ợc x1. . .x n anh ta sẽ khôi phục lại y 1. . .y n bằng khoá K bí mật và xác minh xem liệu y n có giống với MAC mà mình đ thu đ−ợc hay không. Nhận thấy Oscar không thể tạo ra một MAC hợp lệ do anh ta không biết khoá K mà Alice và Bob đang dùng. Hơn nữa Oscar thu chặn đ−ợc dy khối bản rõ x 1. . .x n và thay đổi ít nhiều nội dung thì thì chắc chắn là Oscar không thể thay đổi MAC để đ−ợc Bob chấp nhận. Thông th−ờng ta muốn kết hợp cả tính xác thực lẫn độ bảo mật. Điều đó có thể thực hiện nh− sau: Tr−ớc tiên Alice dùng khoá K 1 để tạo MAC cho x1. . . x n . Sau đó Alice xác định x n+1 là MAC rồi m hoá dy x1. . .x n+1 bằng khoá thứ hai K 2 để tạo ra bản m y 1. . .y n+1 . Khi Bob thu đ−ợc y1. . .y n+1 , tr−ớc tiên Bob sẽ giải m ( bằng K 2) và kiểm tra xem x n+1 có phải là MAC đối với dy x 1. . .x n dùng K 1 hay không. Ng−ợc lại, Alice có thể dùng K 1 để m hoá x 1. . .x n và tạo ra đ−ợc y1 y n , sau đó dùng K 2 để tạo MAC y n+1 đối với dy y 1. . .y n. Bob sẽ dùng K 2 để xác minh MAC và dung K 1 để giải m y 1. . .y n. 3.5. Phép tối −u hoá thời gian - bộ nhớ. Trong phần này sẽ mô tả phép tối −u hoá thời gian - bô nhớ khá lý thú khi phá DES bằng tấn công bản rõ chọn lọc. Ta nhớ lại rằng, trong phép tấn công bản rõ chọn lọc, Oscar đ thu đ−ợc cặp rõ - m đ−ợc tạo bởi khoá K (ch−a biết). Bởi vậy, Oscar có x và y, trong đó y = e K(x) và anh ta muốn xác định đ−ợc K. Một đặc điểm của phép tối −u hoá thời gian - bộ nhớ này là nó không phụ thuộc vào "cấu trúc" của DES trên mọi ph−ơng diện. Khía cạnh duy nhất của DES có quan hệ tới phép tấn công này là các bản rõ và các bản m 64 bít trong khi các khoá có 56 bít. Ta đ thảo luận về ý t−ởng tìm khoá bằng ph−ơng pháp vét cạn: với một cặp rõ - m cho tr−ớc, hy thử tất cả 2 56 khoá cụ thể. Điều này không yêu cầu bộ nhớ, nh−ng trung bình phải thử 2 55 khoá tr−ớc khi tìm đ−ợc khoá đúng. Mặt khác, với một bản rõ x cho tr−ớc, Oscar có thể tính tr−ớc y K = 56 eK(x) đối với toàn bộ 2 khoá K và xây dựng một bảng các cặp (y K,K) đ−ợc sắp xếp theo các tạo độ đầu của chúng. Sau đó khi Oscar thu đ−ợc bản m y (
  20. là kết quả của phép m bản rõ x), anh ta phải nhìn vào giá trị y trong bảng và lập tức tìm đ−ợc khoá K. Nh− vậy trong tr−ờng hợp này việc tìm đ−ợc khoá K chỉ yêu câu một thời gian cố định nh−ng ta phải có một bô nhớ có dung l−ợng lớn và cần thời gian tính toán tr−ớc lớn ( chú ý là quan điểm này không có lợi thế về thời gian tính toán tổng cộng nếu chỉ cần tìm một khoá, bởi vì việc xây dựng bảng cũng mất nhiều thời gian nh− việc tìm khóa vét cạn. Ph−ơng pháp này chỉ có lợi khi cần tìm nhiều khoá trong một khoảng thời gian vì ta chỉ cấn dùng một bảng cho tất cả các tr−ờng hợp). Phép tối −u hoá thời gian - bộ nhớ sẽ có thời gian tính toán nhỏ hơn phép tìm kiếm vét cạn và có yêu cầu bộ nhớ nhỏ hơn việc lập bangr tra cứu. Thuật toán có thể mô tả theo hai tham số m và t là các số nguyên d−ơng. Thuật toán cần một hàm rút gọn R để rút gọn một xâu bít có độ dài 64 thành một xâu bít có độ dài 56 ( chẳng hạn R phải vứt bỏ 8 trong 64 bít). Giả sử x là một xâu bản rõ cố định 64 bít. Hy xác định hàm g(K 0) =R(e Ko (x)) với một xâu bít K 0 có độ dài 56. Chú ý rằng g là một hàm thực hiện ánh xạ 56 bít sab\ng 56 bít. Trong giai đoạn tiền xử lý, Oscar chọn m xâu bít ngẫu nhiên có độ dài 56 đ−ợc kí hiệu là X(i,0), 1 ≤ i ≤ m. Oscar tính x(i,j) với 1 ≤ j ≤ t theo quan hệ truy toán sau: X(i,j) = g(X(i,j-1)), 1 ≤ i x ≤ m , 1 ≤ j ≤ t nh− chỉ trên hình 3.6. Hình 3.6. Tính X(i,j) X )0,1( →g X )1,1( →g →g X ,1( t) X )0,2( →g X )1,2( →g →g X ,2( t) . . . X (m )0, →g X (m )1, →g →g X (m,t) Sau đó Oscar xây dựng một bảng các cặp T = (X(i,t), X(i,0) đ−ợc sắp xếp theo toạ độ đầu của chúng( tức là chỉ l−u giữ cột đầu và cột cuối của X). Sau khi thu đ−ợc bản m y ( là bản m của bản rõ x đ chọn). Oscar cần phải xác định K và anh ta sẽ xác định đ−ợc nếu K nằm trong t cột đầu của bảng X, tuy nhiên anh ta chỉ làm điều này bằng cách chỉ nhìn vào bảng T.
  21. Giả sử rằng K = X(i,t-j) với j nào đó, 1 ≤ j ≤ t ( tức giả sử rằng K nằm ở t cột đầu tiên của X). Khi đó rõ ràng là g j(K) = x(i,t), trong đó g j kí hiệu hàm nhận đ−ợc bằng cách lặp g một số lần bằng j. Bây giờ ta thấy rằng: gj(K) = g j-1(g(K)) j-1 = g (R(e K(x))) = g j-1(R(y)) Giả sử tính ỵ j,1 ≤ j ≤ t, từ quan hệ truy toán R(y) nếu j = 1 yi = g(ỵ j-1) nếu 2 ≤ j ≤ t Từ đó rút ra rằng y j = X(i,t-j) nếu K = X(i,t-j). Tuy nhiên cần chú ý rằng y j = X(i,t) ch−a đủ để đảm bảo là K = X(i,t-j). Sở dĩ nh− vậy vì hàm rút gọn R không phải là một đơn ánh: miền xác định của R có lực l−ợng 2 64 và giá trị của R có lực l−ợng 2 56 , bởi vậy tính trung bình có 2 8 = 256 nghịch ảnh của một xâu bít bất kì cho tr−ớc có độ dài 56. Bởi vây cần phải kiểm tra xem y = e X(i,t-j) (x) hay không để biết liệu X(i,t-j) có thực sự là khoá hay không. Ta không l−u trữ giá trị X(i,t-j) nh−ng có thể dễ dàng tính lại nó từ X(i,0) bằng cách lặp t-j lần hàm g. Oscar sẽ thực hiện theo thuật toán đ−ợc mô tả trên hình 3.7. Hình 3.7. Phép tối −u hoá bộ nhớ - thời gian trong DES. 1. Tính y 1 = R(y) 2. for j = 1 to t do 3. if y j = X(i,t-j) với giá trị i nào đó then 4. Tính X(i,t-j) từ X(i,0) bằng cách lặp t-j lần hàm g. 5. if y = eX(I,t-j)(x) then đặt K = X(i,t-j) và QUIT
  22. 6. Tính y j+1 = g(y j) Bằng cách phân tích xác suất thành công của thuật toán, có thể chứng tỏ rằng nếu mt 2 ≈ N = 2 56 thì xác suất để K = X(i,t-j) với i, j nào đó sẽ vào khoảng 0,8môi tr−ờng/N. Thừa số 0,8 tính theo điều kiện không phải tất cả cácX(i,t) đều phân biệt . Điều này gợi ý cho ta nên lấy m ≈ t ≈ N 1/3 và xây dựng khoảng N 1/3 bảng, mỗi bảng dùng một hàm rút gọn R khác nhau. Nếu thực hiện đ−ơc điều này thì yêu cầu về bộ nhớ là 112 ìN1/3 bít ( vì ta cần l−u trữ 2 ìN2/3 số nguyên, mỗi số có 56 bít). Thời gian tiền tính toán dễ dàng thấy là cỡ O(N). Việc phân tích thời gian chạy của thuật toán có khó hơn hơn một chút: Tr−ớc hết ta thấy rằng, b−ớc 3 có thể chạy trong một thời gian không đổi (sử dụng phép m hash) hoặc trong tr−ờng hợp xấu nhất, b−ớc 3 có thể chạy với thời gian O(logm) khi dùng phép tmf kiếm nhị phân. Nếu b−ớc 3 không thoả mn (tức là phép tìm kiếm không thành công) thì thời gian chạy là O(N 2/3 ). Các phân tích chi tiết hơn chứng tỏ rằng, ngay cả khi tính cả thời gian chạy của các b−ớc 4 và5 thì thời gian chạy trung bình chỉ tăng một l−ơng là hằng số. 3.6 Thám m, vi sai (DC). Ph−ơng pháp DC do Biham và Shamir đ−a ra là một ph−ơng pháp tấn công DES rất nổi tiếng. Đây là một phép tấn công với bản rõ chọn lọc. Mặc dù ph−ơng pháp này không cho một ph−ơng pháp thực tế để phá DES 16 vòng thông dụng, nh−ng nó có thể thực hiện thành công trong việc phá DES có số vòng m hoá ít hơn. Chẳng hạn DES 8 vòng có thể phá đ−ợc trong vòng vài phút trên một máy tính cá nhân nhỏ. Bây giờ ta sẽ mô tả những ý t−ởng cơ bản dùng trong kỹ thuật này, ta có thể bỏ qua phép hoá vị ban đầu IP và phép hoán vị ng−ợc của nó ( không ảnh h−ởng tới việc phân tích m). Nh− đ nói ở trên, ta chỉ xét hạn chế DES n vòng với n ≤ 16. Bởi vậy, với các điều kiện trên, ta coi L 0R0 là bản rõ và LnRn là bản m trong DES n vòng ( cần chú ý rằng ta không cần đảo L nRn ). Ph−ơng pháp DC xoay quanh việc so sánh kết quả phép hoặc - loại trừ của hai bản rõ với kết quả của phép hoặc - loại trừ của hai bản m t−ơng ứng. * * Đại thể ta sẽ xét hai bản rõ L 0R0 vàL 0 R0 với giá trị của phép hoặc - loại trừ
  23. * * L0'R 0' = L 0R0 ⊕L0 R0 . Trong phần này ta sẽ sử dụng ký hiệu ( ' ) để chỉ phép hoặc - loại trừ (XOR) của hai xâu bít. Định nghĩa 3.1 Giả sử S j là một hộp S (1 ≤ j ≤ 8 ). Xét một cặp đ sắp xếp của các xâu * * bít độ dài 6 ( ký hiệu là B j, B j ). Ta nói rằng XOR vào (của S j ) là B j ⊕Bj và * XOR ra ( của S j ) là S j(B j) ⊕ S j(B j ). Chú ý rằng XOR vào là một xâu bít có độ dài 6 và XOR ra là một xâu bít có độ dài 4. Định nghĩa 3.2 6 Với bất kỳ B j' ⊕ (Z 2) , ta định nghĩa tập ∇(B j') gồm các cặp đ−ợc sắp * xếp (B j,B j ) có XOR vào là B j'. 6 Dễ dàng thấy rằng một tập ∇(B j') bất kỳ đều chứa 2 = 64 cặp và 6 ∇(B j') = {(B j,B j ⊕Bj' ) : B j ∈(Z 2) } Với mỗi cặp trong ∇(B j') ta có thể tính XOR ra của S j và lập bảng phân bố kết quả. Có 64 XOR ra phân bố trong 2 4 = 16 giá trị có thể. Tính không đều của các phân bố này là cơ sở cho phép tấn công. Ví dụ 3.1. Giả sử xét hộp S đầu tiên S 1 và XOR vào 110100, khi đó: ∇(110100) = {(000000,110100), (000001,110100), . . . ,(111111,110100)} Với mỗi cặp đ−ợc sắp trong tập ∇(110100) ta tính XOR ra của S 1. Ví dụ S1(000000) = E 16 = 1110 và S 1(110100) = 9 16 = 1001, bởi vậy XOR đối với cặp (000000,110100) là 0111. Nếu làm công việc này cho tất cả 64 cặp trong ∇(110100) thì ta sẽ thu đ−ợc phân bố sau của các XOR ra: 0000 0001 0010 0011 0100 0101 0110 0111 0 8 16 6 2 0 0 12 1000 1001 1010 1011 1100 1101 1110 1111 6 0 0 0 0 8 0 6
  24. Trong ví dụ 3.1 chỉ có 8 trong 16 XOR ra có thể xuất hiện trên thực tế. Ví dụ cụ thể này có phân bố rất không đều. Nói chung nếu ta cố định một hộp S là S j và một XOR vào B j' thì trung bình có khoảng 75-80% các XOR ra là có thể xuất hiện. Để mô tả và đ−a ra các phân bố này, ta cần phải có thêm mọt số khái niệm thích hợp. Sau đó là một số định nghĩa. Định nghĩa 3.3 Với 1 ≤ j ≤ 8 và với các xâu bít B j' có độ dài 6 còn C j' có độ dài 4, ta định nghĩa: 6 IN j(B j',C j') = { Bj ∈(Z 2) : S j(B j) ⊕ S j(B j ⊕ B j') = C j'} và Nj(B j',C j') = | IN j(B j',C j' ) |. Nj(B j',C j' ) là số các cặp có XOR vào bằng B j' và có XOR ra bằng C j' với hộp Sj. Các cặp thực tế có các XOR vào xác định và tạo nên các XOR ra xác định có thể nhận đ−ợc từ tập IN j(B j',C j' ). Ta thấy rằng, tập này có thể đ−ợc phân thành N j(B j',C j' )/2 cặp, mỗi cặp có số XOR vào bằng B j'. Chú ý rằng phân bố đ−ợc lập bảng ở trong ví dụ 3.1 chứa các giá trị 4 N1(110100,C 1'), C 1' ∈(Z 2) . Các tập IN 1(110100,C 1') đ−ợc liệt kê trên hình 3.8. Với mỗi hộp trong 8 hộp S có 64 XOR và có thể. Bởi vậy có thể tính đ−ợc tất cả 512 phân bố và dễ dàng dùng máy tính để lập bảng các phân bố này. Cần nhớ lại rằng, đầu vào của các hộp S ở vong thứ i là B = E ⊕J, trong đó E = E(R i-1) là một hàm mở rộng của R i-1 và J = K i là các bít khoá của vòng thứ i. Bây giờ số XOR vào (cho tất cả 8 hộp) có thể đ−ợc tính nh− sau: B ⊕ B * = (E ⊕ J) ⊕ (E * ⊕ J) = E ⊕ E * Có thể thấy môt điều rất quan trọng là XOR vao không phụ thuộc vào các bít khoá J ( tuy nhiên chắc chắn XOR ra sẽ phụ thuộc vào các bít khóa này. Hình 3.8. Các xâu vào có thể với XOR vào là 110100. Các XOR ra Các xâu vào có thể 0000
  25. 0001 000011,001111,011110,011111, 101010,101011,110111,111011 0010 000100,000101,001110,010001, 010010,010100,011010,011011, 100000,100101,010110,101110, 101111,110000,110001,111010 0011 000001,000010,010101,100001, 110101,110110 0100 010011,100111 0101 0110 0111 000000,001000,001101,010111 011000,011101,100011,101001 101100,110100,111001,111100 1000 001001,001100,011001,101101 111000,111101 1001 1010 1011 1100 1101 000110,010000,010110,011100 100010,100100,101000,110010 1110 1111 000111,001010,001011,001100 111110,111111 Ta viết các E,B, và J là một dy ghép kế tiếp 8 xâu 6 bít: B = B 1 B2 B 3 B 4 B 5 B 6 B 7 B 8 E = E 1 E 2 E 3 E 4 E 5 E 6 E 7 E 8 J = J 1 J 2 J 3 J 4 J 5 J6 J7 J 8 * * * * và viết B , E ,J theo cách t−ơng tự. Nếu biết các giá trị E j và E j với j nào đó, * 1 ≤ j ≤ 8, và giá trị XOR ra ( của S j ) là C j' = S j(B j) ⊕ S j(B j ). Khi đó chắc chắn rằng: Ej ⊕ J j ∈ IN j(E j',C j' ) * trong đó E j' = E j ⊕Ej . Giả sử ta xác định tập test j nh− sau: Định nghĩa 3.4.
  26. * Giả sử Ej và E j là các xâu bít độ dài 6 và C j' là xâu bít độ dài 4. Ta định nghĩa: * test j(E j , E j , C j' ) = {B j ⊕ E j : B j ∈IN j(E j',C j')} * trong đó E j' = E j E j Nghĩa là lấy XOR E j với mỗi phần tử của tập IN j(E j',C j'). Kết quả sau đây là một hệ quả trực tiếp rút ra từ suy luận ở trên. Định lý 3.1 * Giả sử E j và E j là hai xâu vào của hộp S j còn XOR ra của S j là C j. Kí * * hiệu E j' = E j ⊕ E j . Khi đó các bít khoá J j sẽ nằm trong tập test j (E j, E j , C j'). Nhận thấy rằng có đúng N j(E j',C j' ) xâu bít độ dài 6 trong tập * test j(E j,E j ,C j'); giá trị đúng của J j phải là một trong các khả năng này. Ví dụ 3.2. * Giả sử E 1 = 000001, E 1 = 110101 và C 1' = 1101. Vì N 1(110100,1101) = 8 nên có đúng 8 xâu bít trong tập test 1(000001,110101,1101). Từ hình 3.8 ta thấy rằng: IN 1(110100,1101) = {000110,010000,010110,011100,100010,100100,101000,110010} Bởi vậy test 1(000001,110101,1101) = {000111,010001,010111,011101,100011,100101,101001,110011}. * Nếu ta có một bộ ba E 1,E 1 ,C 1' thứ hai nh− vậy thì có thể thu đ−ợc tập test 1 thứ hai chứa các giá trị có thể chứa các bít khoá trong J 1. Giá trị đúng của J 1 phải nằm trong phần giao của hai tập này. Nếu ta có vài bộ ba nh− vậy thì có thể nhanh chóng xác định đ−ợc các bít khoá trong J 1. Ph−ơng pháp đơn giản để làm điều này là tạo một dy 64 bộ đếm biểu diễn 64 khả năng của 6 bít khoá trong J 1 . Bộ đếm sẽ đếm tăng mỗi khi các bít khoá t−ơng ứng xuất hiện trong tập test 1 với một bộ ba cụ thể. Với t bộ ba, ta tin rằng sẽ tìm đ−ợc bộ đếm duy nhất có giá trị t t−ơng ứng với giá trị đúng của các bít khoá trong J1. 3.6.1. Tấn công DES 3 vòng Bây giờ ta xét xem việc ứng dụng các ý t−ởng của phần tr−ớc trong phép tấn công bản rõ chọn lọc lên một hệ DES 3 vòng. Ta bắt đầu ằng một
  27. * * * * cặp các bản rõ và bản m t−ơng ứng L 0R0, L 0 R0 ,L 3R3, và L 3 R3 . Có thể biểu thị R 3 nh− sau: R3 = L 2 ⊕ f (R 2,K 3) = R 1 ⊕ f (R 2,K 3) = L 0 ⊕ f (R 0,K 1) ⊕ f (R 2,K 3) * Biểu diễn R 3 theo cách t−ơng tự nh− vậy * * R3' = L 0' ⊕ f (R 0,K 1) ⊕ f(R 0 ,K 1) ⊕ f (R 2,K 3) ⊕ f (R 2 ,K 3) * Bây giờ, giả sử ta đ chọn đ−ợc các bản rõ sao cho R 0 = R 0 , nghĩa là để R0' = 00. . .0 * Khi đó f (R 0,K 1) = f (R 0 ,K 1) và nh− vậy: * R3' = L 0' ⊕ f(R 2,K 3) ⊕ f(R 2 ,K 3). Lúc này R 3' đ biết vì có thể tính đ−ợc nó từ hai bản m. L 0' cũng đ biết do có thể tính đ−ợc nó từ hai bản rõ. Điều này có nghi là ta có thể tính * f(R 2,K 3)⊕f(R 2 ,K 3) từ ph−ơng trình: * f(R 2,K 3)⊕f(R 2 ,K 3) = R 3' ⊕ L 0' * * * Bây giờ ta có f(R 2,K 3) = P(C) và f(R 2 ,K 3) = P(C ), trong đó C và C ký hiệu t−ơng ứng 2 dy ra của 8 hộp S ( hy nhớ lại rằng P là một phép hoán vị cố định công khai ). Bởi vậy: * P(C) ⊕ P(C ) = R 3' ⊕ L 0' và do đó: * -1 C' = C ⊕ C = P (R 3' ⊕ L 0') (3.1) Đây là XOR ra của 8 hộp S ở vòng thứ 3. * * Bây giờ R 2 = L 3 và R 2 = L 3 cũng đ biết ( chúng là một phần của các bản m). Bởi vậy, có thể tính E = E(L 3) (3.2) * * và E = E(L 3 ) (3.3) bằng cách dùng hàm mở rộng E đ−ợc biết công khai. Đây là các mẫu vào các hột S ở vòng thứ 3. Nh− thế ta đ biết E và E * và C ' của vòng thứ 3 và có thể
  28. thực hiện ( nh− ở phần tr−ớc) để xây dựng các tệp test 1, . , test 8 chứa các giá trị có thể của các bít trong J 1,. . .,J 8 . Mô tả dạng giả m của thuật toán này đ−ợc cho ở hình 3.9. Hình 3.9. Cách tấn công DC lên DES 3 vòng. * * * * * Đầu vào L 0R0,L 0 R0 , L 3R3 và L 3 R3 , trong đó R 0 = R 0 -1 1. Tính C ' = P (R 3' ⊕ L 0') * * 2. Tính E = E(L 3) và E = E(L 3 ) 3. For j = 1 to 8 do * Tính test j(E j, E j , C j') Trong ph−ơng pháp tấn công này sẽ phải dùng một số bộ ba E, E *,C ' nh− vậy, Ta phải thiết lập 8 dy bộ đếm và nhờ vậy xác định đ−ợc 48 bít trong khoá K 3 ( khoá của vòng thứ 3). Sau đó tính 56 bít trong khóa theo cách tìm kiếm vét cạn trong 2 8 = 256 khả năng cho 8 bít khoá còn lại. Ta sẽ xem xét một ví dụ để minh hoạ. Ví dụ 3.3. Giả sử ta có 3 cặp các bản rõ và các bản m, trong đó các bản rõ có các phép XOR xác định, chúng đ−ợc m hoá bằng cùng một khoá. Để cho gọn ta sẽ biểu thị d−ới dạng m Hexa: Bản rõ Bản m 748502CD38451097 03C70306D8AO9F10 3874756438451097 78560A960E6D4CB 486911026ACDFF31 45FA285BE5ADC730 375BD31F6ACDFF31 134F7915AC253457 357418DA013FEC86 D8A31B2F28BBC5CF 12549847013FEC86 0F317AC2B23CB944 Từ cặp đầu tiên, tính các đầu vào của hộp S ( cho vòng 3 ) theo các ph−ơng trình (3.2) và (3.3). Ta có: E = 000000000111111000001110100000000110100000001100 E * = 101111110000001010101100000001010100000001010010 XOR ra của các hộp S đ−ợc tính theo ph−ơng trình (3.1) là:
  29. C' = 10010110010111010101101101100111 Từ cặp thứ hai, ta tính đ−ợc các đầu vào của các hộp S là: E = 101000001011111111110100000101010000001011110110 E * = 000001011110100110100010101111110101011000000100 và XOR ra của các hộp S là: C' = 11010101011101011101101100101011 Tiếp theo, lập bảng các giá trị trong 8 dy bộ đếm cho từng cặp. Minh hoạ thủ tục này với dy bộ đếm cho J 1 theo cặp đầu tiên. Trong cặp này ta có: E' = 101111 và C' = 1001. Khi đó tập: IN 1(101111,1001) = {000000,000111,101000,101111} vì E 1 = 000000 nê ta có: J1∈test 1(000000,101111,1001) = {000000,000111,101000,101111} Bởi vậy ta sẽ tăng các giá trị 0,7,40 và 47 trong dy bộ đếm cho J 1. Bây giờ sẽ trình bày các bảng cuối cùng. Nếu coi một xâu bít độ dài 6 nh− biểu diễn nhị phân của một số nguyên nằm giữa 0 và 63 thì 64 giá trị t−ơng ứng là 0,1,. . . ,63. Các mảng bộ đếm sẽ nh− sau: J1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 J2 0 0 0 1 0 3 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 2 0 0 0 J3
  30. 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 J4 3 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 J5 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 0 0 0 2 0 J6 1 0 0 1 1 0 0 3 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 J7 0 0 2 1 0 3 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 2 0 0 0 2 0 0 0 0 1 2 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 J8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 3 0 0 0 0 1 0 0 0 0 0 0 0 0 1 Trong số 8 mảng bộ đếm ( trong 8 mangt ở trên) có duy nhất một bộ đếm có giá trị 3, các vị trí của các bộ đếm này sẽ đ−ợc xác định các bít khoá
  31. trong J 1, ., J 8. Các vị trí này t−ơng ứng là 47,5,19,0,24,7,7,49. Đổi các số nguyên sang dạng nhị phân ta nhận đ−ợc J 1, . . .,J 8: J 1 = 101111 J2 = 000101 J3 = 010011 J4 = 000000 J5 = 011000 J6 = 000111 J7 = 000111 J8 = 110001 Bây giờ ta có thể xây dựng 48 bít của khoá bằng cách nhìn vào bảng khoá đối với vòng 3. Khi đó K có dạng: 0001101 0110001 01?01?0 1?00100 0101001 0000??0 111?11? ?100011 ở đây ta đ bỏ qua các bít kiểm tra chặn lẻ và"?" chỉ bít khoá ch−a biết. Khóa đầy đủ ( ở dạng hexa gồm cả bít kiểm tra chặn lẻ) là: 1A624C89520DEC46 3.6.2. Tấn công DES 6 vòng Trong mục này ta sẽ mở rộng các ý t−ởng ở trên cho phép tấn công xác suất đối DES 6 vòng. ý t−ởng ở đây là phải chọn cẩn thận một acặp bản rõ với một phép XOR chỉ ra tr−ớc rồi xác định các xác suất của một dy xác định các XOR qua các vong m. Bây giờ ta sẽ định nghi một khái niệm quan trọng. Định nghĩa 3.5. Cho n ≥ 1 là một số nguyên. Một đặc tr−ng n vòng là một danh sách có dạng: L 0',R 0',L 1',R 1',p 1. . . L n',R n',p n thảo mn các tính chất sau: 1. Li' = R i-1' với 1 ≤ i ≤ n. * * 2. Cho 1 ≤ i ≤ n và giả sử L i-1, R i-1 và L i-1 , R i-1 đ−ợc chọn sao cho L i- * * * * 1⊕Li-1 = L i-1' và R i-1⊕Ri-1 = R i-1'. Giả sử L i,R i và L i ,R i đ−ợc tính bằng cách * áp dụng một vòng m hoá của DES; Khi đó xác suất để L i ⊕ L i = L i' và * Ri⊕Ri = R i' đúng bằng p i ( chú ý rằng xác suất này đ−ợc tính trên mọi bộ 48 J = J 1. . . J 8 có thể).
  32. Xác suất của đặc tr−ng này sẽ đ−ợc xác định bằng tích: p = p 1ìp2ì. . . ìpn * * * * Nhận xét: Giả sử ta chọn L 0,R 0 và L 0 ,R 0 sao cho L 0⊕L0 = L 0' và R 0⊕R0 = R0'. áp dụng n vòng m hoá của DES để thu đựơc L 1,. . ., L n và R 1,. . .,R n. * * Khi đó không thể khẳng định rằng xác xuất để L i⊕Li = L i' và R i⊕Ri = R i' vơí mọi i, ( 1 ≤ i ≤ n )là p = p 1ì. . . ìpn. Sở dĩ nh− vậy vì các bộ 48 trong bảng khoá K 1. . .K n không độc lập với nhau ( nếu n bộ 48 này đ−ợc chọn ngẫu nhiên và độc lập với nhau thì khẳng định trên là đúng). Tuy vậy, ta vẫn hy vọng rằng, p 1ì . ìpn là một −ớc l−ợng khá chính xác cho xác suất này. Cũng cần phải thấy rằng, các xác suất p i ở một đặc tr−ng sẽ xác định theo một cặp bản rõ tuỳ ý ( nh−ng cố định) cho phép XOR xác định tr−ớc. Tại đây 48 bít khoá cho một vòng m DES sẽ thay đổi trên toàn bộ 2 48 khả năng. Tuy nhiên thám m lại đang cố gắng xác định một khoá cố định ( nh−ng ch−a biết). Anh ta sẽ chọn ngẫu nhiên các bản rõ ( sao cho chúng có các XOR xác định) với hy vọng rằng, các xác suất để các XOR trong n vòng m phù hợp với các XOR đ−ợc xác định trong đặc tr−ng phải khá gần với các p1,. . . ,p n t−ơng ứng. Ví dụ đơn giản trên hình 3.10 là một đặc tr−ng một vòng, nó là cơ sở cho phép tấn công lên DES 3 vòng ( cũng nh− tr−ớc kia, ta dùng biểu diễn hexa). Hình 3.11 mô tả một đặc tr−ng một vòng khác. Hình 3.10. Đặc tr−ng một vòng. L 0' = bất kì R 0' = 00000000 16 L 1' = 00000000 16 R 1' = L 0' p = 1 Hình 3.11. Một đặc tr−ng một vòng khác. L 0' = 00000000 16 R 0' = 60000000 16 L 1' = 60000000 16 R 1' = 00808200 16 Ta sẽ xem xét kỹ hơn các đặc tr−ng trong hình 3.11. Khi f(R 0,K 1) và * * f(R 0 ,K 1) đ−ợc tính, b−ớc đầu tiên là phải mở rộng R 0 và R 0 . Kết quả của phép XOR hai mở rộng này là: 001100. . .0 Bởi vậy XOR vào của S 1 là 001100 và các XOR vào của 7 hộp S khác đều là 000000. Các XOR của S 2 tới S 8 đều là 0000. XOR ra của S 1 sẽ là 1110 với
  33. xác suất bằng 14/64 ( vì có thể tính đ−ợc N 1(001100,1110)= 14). Nh− vậy ta đ−ợc: C' = 1110000000000000000000000000000 với xác suất bằng 14/64. Sử dụng P ta có : P(C) ⊕ P(C *) = 00000000100000001000001000000000 d−ới dạng hexa giá trị này là 00808200 16 . Khi giá trị này đ−ợc XOR với L 0' ta sẽ nhận đ−ợc R 1' chỉ ra với xác suất 14/64. Dĩ nhiên ta luôn có L 1' = R 0'. Việc tấn công DES 6 vòng sẽ dựa trên đặc tr−ng 3 vòng cho ở hình 3.12. Hình 3.12. Một đặc tr−ng 3 vòng. L 0' = 40080000 16 R 0' = 04000000 16 L 1' = 04000000 16 R 1' = 00000000 16 p = 1/4 L 2' = 00000000 16 R 2' = 04000000 16 p = 1 L 3' = 04000000 16 R 3' = 40080000 16 p = 1/4 * * * * Trong tấn công 6 vòng ta sẽ bắt đầu với L 0R0, L 0 R0 , L 6R6, L 6 R6 , trong đó đ chọn các bản rõ để L 0' = 40080000 16 và R 0' = 04000000 16 . Có thể biểu thị R 6 nh− sau: R6 = L 5 ⊕ f(R 5,K 6) = R 4 ⊕ f(R 5,K 6) = L 3 ⊕ f(R 3,K 4) ⊕ f(R 5,K 6) * R6 có thể biểu thị theo cách t−ơng tự và bởi vậy: * * R6' = L 3' ⊕ f(R 3,K 4) ⊕ f(R 3 ,K 4) ⊕ f(R 5,K 6) ⊕ f(R 5 ,K 6) (3.4) ( hy chú ý sự t−ơng tự với phép tấn công 3 vòng) R6' đ biết. Từ đặc tr−ng này ta thấy rằng L 3' = 04000000 16 và R 3' = 40080000 16 với xác suất1/16. Nếu đây là tr−ờng hợp thực tế thì XOR vào của cá hộp S trong vòng 4 có thể tính đ−ợc theo hàm mở rộng bằng: 001000000000000001010000. . .0
  34. Các XOR vào của S 2,S 5,S 6,S 7 và S 8 đều là 000000 và bởi vậy ở vòng 4, các XOR ra của 5 hộp này đều là 0000. Điều đó có nghĩa là có thể tính các XOR ra của 5 hộp S này ở vòng 6 theo (3.4). Bởi vậy giả sử ta tính: -1 C1'C 2'C 3'C 4'C 5'C 6'C 7'C 8' = P (R 6' ⊕ 04000000 16 ) trong đó mỗi C i' là một xâu bít có độ dài 4. Khi đó, với xác suất 1/16 các xâu bít C 2',C 5', C 6', C 7' và C 8' t−ơng ứng là các XOR ra của S 2,S 5,S 6,S 7 và S 8 ở vong 6. Các đầu ra của các hộp S ở vòng 6 có thể đ−ợc tính là E 2, E 5, E 6, E 7, E 8 và * * * * * E2 , E 5 , E 6 , E 7 và E 8 , trong đó : E 1 E 2 E3 E 4 E 5 E 6 E 7 E8 =E(R 5) = E(L 6) * * * * * * * * * * và E 1 E 2 E3 E 4 E5 E 6 E 7 E8 =E(R 5 ) = E(L 6 ) có thể đ−ợc tính theo các bản m nh− đ mô tả trên hình 3.13. Hình 3.13. DC đối với DES 6 vòng. * * * * Đầu vào L 0R0,L 0 R0 ,L 6R6,và L 6 R6 trong đó L 0' = 40080000 16 và R 0' = 04000000 16 -1 1. Tính C' = P (R 6' ⊕ 40080000 16 ) * * 2. Tính E = E(L 6) và E = E(L 6 ) 3. For ∈ j {2, 5, 6, 7, 8} do * Tính test j(E j, E j , C j') Bây giờ ta muốn xác định 30 bít khoá trong J 2, J 5, J 6, J 7 và J 8 nh− cách đ làm trong tấn công 3 vòng. Vấn đề ở đây là XOR đ−ợc giả định cho vòng 6 chỉ đúng với xác suất 1/16. Bởi vậy 15/16 thời gian ta chỉ thu đ−ợc các bít ngẫu nhiên không phải là các bít khoá có thể. Bằng một cách nào đó ta phải có khẳ năng xác định đ−ợc các khoá đúng bằng các số liệu đ cho ( trong đó có 15/16 các số liệu sai). Điều này có vẻ không sáng sủa cho lắm, song rất may mắn là viễn cảnh của ta không tối tăm nh− vậy. Định nghĩa 3.6. * * Giả sử L 0 ⊕ L 0 = L 0' và R 0 ⊕ R 0 = R 0'. Ta nói rằng cặp bản rõ L 0R0 * * * * và L 0 R0 là cặp đúng ứng với một đặc tr−ng nếu L i⊕Li = L i' và R i⊕Ri = Ri' với mọi i, 1 ≤ i ≤ n. Ng−ợc lại, cặp này đ−ợc xác định là cặp sai.
  35. Hy vọng rằng khoảng 1/16 các cặp là đúng và các cặp còn lại là sai ứng với đặc tr−ng 3 vòng. * Chiến thuật của ta là tính E j, E j và C j' ( nh− đ mô tả ở trên ) sau đó * xác định các test j(E j, E j , C j') vơi j = 2, 5, 6, 7, 8. Nếu bắt đầu bằng một cặp đúng thì các bít khoá đúng cho mỗi J j sẽ nằm trong tập test j. Nếu cặp này sai thì giá trị của C j' sẽ không đúng và giả định rằng mỗi tập test j sẽ chủ yếu là ngẫu nhiên có thể coi là có lý: Có thể nhận ra một cặp sai theo ph−ơng pháp sau: Nếu | test j | = 0 với bất kì j ∈{2, 5, 6, 7, 8} thì chắc chắn là ta có một cặp sai. Bây giờ , với một cặp sai cho tr−ớc, có thể thấy rằng xác suất để test j = 0 với giá trị j nhất định sẽ xấp xỉ bằng 1/5. Đây là một giả định hợp lý bởi vì N j(E j',C j') = | test j | và nh− đ nói ở trên, xác suất để N j(E j',C j') = 0 xấp xỉ bằng 1/5. Xác suất để tất 5 cả 5 tập test j có lực l−ợng d−ơng đ−ợc −ớc l−ợng bằng 0,8 ≈ 0,33. Bởi vậy xác suất để ít nhất một tập test j có lực l−ợng bằng 0 sẽ vào khoảng 0,67. Nh− vậy ta hy vọng loại bỏ đ−ợc 2/3 số cặp sai bằng cách quan sát đơn giản này ( ta sẽ gọi là phép lọc ). Tỷ lệ các cặp đúng còn lại sau phép lọc xấp xỉ bằng (1/16)/(1/3) = (3/16). Ví dụ 3.4. Giả sử ta có cặp m - rõ sau: Bản rõ Bản mã 86FA1C2B1F51D3BE 1E23ED7F2F553971 C6F21C2B1B51D3BE 296DE2B687AC6340 Nhận thấy rằng L 0' = 40080000 16 và R 0' = 04000000 16 . Các đầu vào và các đầu ra của các hộp S ở vòng 6 đ−ợc tính nh− sau: * j Ej Ej Cj' 2 111100 010010 1101 5 111101 111100 0001 6 011010 000101 0010 7 101111 010110 1100 8 111110 101100 1101
  36. Khi đó tập test j (2, 5, 6, 7, 8) là: j test j 2 14, 15, 26, 30, 32, 33, 48,52 5 6 7, 24, 36, 41, 54, 59 7 8 34, 35, 48, 59 Ta thấy tập test 5 và test 7 là các tập rỗng, bởi vậy cặp này là một cặp sai và sẽ bị loại bỏ bằng phép lọc. Bây giờ, giả sử rằng ta có một cặp sao cho | test j | > 0, với j = 2, 5, 6, 7, 8, để nó còn tồn tại lại sau phép lọc ( tuy nhiên vẫn ch−a biết cặp này đúng hay sai ). Ta nói rằng xâu bít J 2 J 5 J 6 J 7 J 8 có độ dài 30 là xâu bít đ−ợc gợi ý bởi cặp trên nếu J j ∈ test j với j = 2,5,6,7,8. Số các xâu bít đ−ợc gợi ý là: ∏ | test j | j∈{ 8,7,6,5,2 } Thông th−ờng số các xâu bít đ−ợc gợi ý có giá trị quá lớn ( ví dụ: > 80000). Giả sử ta đ lập bảng tất cả các xâu bít đ−ợc gợi ý thu đ−ợc từ N cặp ( không bị loại bỏ bởi phép lọc). Với một cặp đúng, xâu bít đúng J 2 J 5 J 6 J 7 J 8 sẽ là một xâu bít đ−ợc gợi ý. Xâu bít đúng này sẽ xuất hiện vào khoảng 3N/16 lần. Các xâu bít không đúng th−ờng xuất hiện ít hơn nhiều do chúng cơ bản là xuất hiện một cách ngẫu nhiên có 2 30 khả năng ( một số rất lớn). Việc lập bảng tất cả các xâu bít đ−ợc ôựi ý sẽ rất cồng kềnh, bởi vậy ta sẽ dùng một thuật toán yêu cầu ít thời gian và không gian ( bộ nhớ). Ta có thể m tập test j bất kỳ bằng véc tơ T j có độ dài 64, trong đó tạo độ thứ i của Tj đ−ợc đặt về giá trị 1 ( với 0 ≤ i ≤ 63) nếu xâu bít độ dài 6 ( là biểu diễn nhị phân của i ) nằm trong tập test j . Trong tr−ờng hợp ng−ợc lại, toạ độ thứ i đ−ợc đặt về 0 ( giống nh− cách biểu diễn mảng bộ đếm đ dùng trong phép tấn công 3 vòng). Với mỗi cặp còn lại ta xây d−ợng các véc tơ này nh− đ mô tả ở trên i về ký hiệu chúng là T j , j = 2,5,6,7,8, 1 ≤ i ≤ N. Với I ⊆ {1,. . . ,N} ta nói
  37. rằng I là tập đ−ợc phép nếu với mỗi j ∈{2,5,6,7,8} có ít nhất một toạ độ bằng | I | trong véc tơ ∑Tj (với j ∈ I). Nếu cặp thứ i là một cặp đúng với mọi i ∈ I thì I sẽ là tập đ−ợc phép. Bởi vậy ta tin rằng sẽ có một tạp đ−ợc phép với kích th−ớc xấp xỉ 3N/16 chứa các bít khoá đúng và ngoài ra không có một tập nào khác. Có thể dễ dàng xây dựng các tập đ−ợc phép I bằng một thuật toán đệ quy. Ví dụ 3.5. Một số ch−ơng trình máy tính đ đ−ợc thực hiện để kiêmr tra ph−ơng pháp này. Trong đó đ tạo ra một mẫu ngẫu nhiên gồm 120 cặp bản rõ với các XOR xác định và các bản rõ này đ đ−ợc m hoá bằng cùng một khoá ( ngẫu nhiên ). Bảng 3.1 đ−a ra 120 cặp các bản rõ và các bản m t−ơng ứng ở dạng m hexa. Khi tính các tập đ−ợc phép ta thu đ−ợc n i tập đ−ợc phép có lực l−ợng nh− sau: i ni 2 111 3 180 4 231 5 255 6 210 7 120 8 45 9 10 10 1 Tập đ−ợc phép duy nhất có lực l−ợng 10 là: {24,29,30,48,50,52,55,83,92,118} Thực tế tập đ−ợc tạo ra theo 10 cặp đúng. Chỉ có tập đ−ợc phép này mới chứa các bít khoá đúng cho J 2, J 5, J 6, J 7, J 8. Chúng có giá trị nh− sau: J2 = 011001 J5 = 110000 J6 = 001001 J7 = 101010 J8 = 100011
  38. Chú ý rằng tất cả các tập đ−ợc phép có lực l−ợng tối thiểu là 6 không kể 3 tập đ−ợc phép có lực l−ợng là 5 sinh ra từ các cặp đúng bởi vì 10  10        = 252 và   = ni 5  i  với 6 ≤ i ≤ 10. Ph−ơng pháp này sẽ cho ta biết 30 bít trong 56 bít khoá. Bằng một đặc tr−ng 3 vòng khác ( nêu ở hình 3.14 ), ta có thể tính thêm 12 bít khoá nữa ( các bít này nằm trong J 1 và J 4). Bây giờ chỉ còn lại 14 bít khoá ch−a biết. Vì 214 = 16384 là một số quá nhỏ nên có thể dùng phép tìm kiếm vét cạn để xác định nốt chúng. Hình 3.14. L 0' = 00200008 16 R 0' = 0000040016 L 1' = 00000400 16 R 1' = 00000000 16 p = 1/4 L 2' = 00000000 16 R 2' = 00000400 16 p = 1 L 3' = 00000400 16 R 3' = 00200008 16 p = 1/4 Toàn bộ khoá ( ở dạng hexa, kể cả các bít kiểm tra chẵn lẻ ) sẽ là: 34E9F71A20756231 Nh− đ nói ở trên, 120 cặp đ−ợc cho ở bảng 3.1. Trong cột thứ hai, dấu (*) kí hiệu cặp đúng, dấu ( ) kí hiệu cặp sai nhận biết đ−ợc và nó sẽ bị loại bỏ bởi phép lọc. Trong số 120 cặp, có 73 cặp đ−ợc xác định là các cặp sai nhờ quá trình lọc, bởi vậy 47 cặp còn lại sẽ là các cặp đúng có thể. 3.6.3. Các ví dụ khác về DC. Các kỹ thuật DC có thể đ−ợc sử dụng để tấn công DES có trên 6 vòng. Với DES 8 vòng cần 2 14 bản rõ chọn lọc, DES 10, 12, 14, 16 vòng có thể phá đ−ợc với t−ơng ứng là 2 24 , 2 31 , 2 39 và 2 47 bản rõ chọn lọc. Vào thời điểm hiện tại, tấn công DES có trên 10 vòng là không thực tế. Một loại m tích hoán vị - thay thế khác với DES cũng có thể dùng DC để phá ( ở mức độ khác nhau ). Trong các hệ này, có một số hệ mật hoán vị -
  39. thay thế đ đ−ợc đ−a ra trong những năm gần đây nh− FEAL,REDOC-II và LOKI. Ghi chú ( của ng−ời dịch ): theo công bố của Micheal Wiener vào 1993, với 10 7 USD có thể xây dựng thiết bị chuyên dụng để phá DES trong khoảng 21 phút. Với 10 8 USD, các bản tin DES có thể bị phá trong khoảng 2 phút. Nh− vậy, DES không còn bí mật đối với NAS. Tuy nhiên cũng không cần một thiết bị chuyên dụng đắt tiền nh− vậy để phá DES. Các thông báo đ−ợc m hoá bằng DES có thể bị phá bằng các máy tính thông th−ờng trên với điều kiẹen có vẻ siêu thực: có trên 2 43 ì 2 6 bít rõ - m với một khoá 56 bít cố định, tuy nhiên bạn phải chờ lâu hơn. Trong hội nghị CRYPTO'94 M.Matsui đ trình bày một kỹ thuật phá DES mới đ−ợc gọi là " thám m tuyến tính". Sử dụng 2 43 (8.796.093.022.208) bản m đ biết. Matsui có thể phá một khoá DES trong 50 ngày bằng một máy tính cá nhân. 3.7. Các chú giải và tài liệu dẫn. Smid và Branstad đ có một bài báo hay về lịch sử của DES [SB 92]. Các công bố về Chuẩn xử lý thông tin liên bang (FIPS) liên quan đến DES gồm: mô tả DES [NBS 77]; ứng dụng và sử dụng DES [NBS 81]; các chế độ làm việc của DES [NBS 80]; xác thực bằng DES [NBS 85]. Một số tính chất của các hộp S đ−ợc Brickell, Moore và Purtill [BMP87] nghiên cứu. Chíp giải m DES đ−ợc mô tả trong [EB 93]. Thiết bị tìm khoá của Wiener đ−ợc mô tả ở CRYPTO' 93 [Wi 94]. Phép tối −u hoá thời gian - bộ nhớ tổng quát hơn đ−ợc trình bày bởi Fiat và Naor trong [FN 91]. Kỹ thuật DC đ−ợc phát triển bởi Biham và Shamir [BS 91] ( cũng có thể xem [BS93A] và sách của họ [BS 93] trong đó cũng thảo luận thám m hệ mật khác). Cách trình bày về DC trong ch−ơng này phần lớn dựa trên [BS93]. Một ph−ơng pháp m thám mới có thể dùng để tấn công DES và các hệ mật t−ơng ứng khác là ph−ơng pháp thám m tuyến tính của Matsui [MA 94], [MA 94A]. Các mô tả về hệ mật hoán vị - thay thế khác có thể tìm trong các tài liệu sau: LUCIFER [FE 73], FEAL [MI 91], REDOC-II [CW 91] và LOKI [BKPS 90]. Bảng 3.1. Mã thám DES 6 vòng. Cặp Cặp đúng Bản rõ Bản m
  40. 1 86FA1C2B1F51D3BE 1E23ED7F2F551971 C6F21CC2B1B51D3BE 296DE2BG87AC6310 2 EDC439EC935E1ACD 0F847EFE90466588 ADCC39EC975E1ACD 93E84839E374440B 3 9468A0BE00166155 3D6A906A6566D0BF D460A0BE04166155 3BC3B23698379E1 4 D4FF2B18A5A8AACB 26B14738C2556BA4 94F72B18A1A8AAC8 15753FDE86575ABF 09D0F2CF273AE54F 15751F4F11308114 5 49D8F2CF237AF54F 6046AFC863F066AF CBC7157240D415DF 7FCDC300FB9698E5 6 8BCF157244D415DF 522185DD7E47D43A 0D4A1E84890981C1 E7C0B01E32557558 7 4D421E848D0981C1 912C6341A69DF295 8 6CE6B2A9B8194835 75B52E028A5C48A3 2CEEB2A9BC194835 6C88603B8E5A8CE 9 799F63C3C9322C1A A6DA322BBF2444B5 399763C3CD322C1A 6634AA9DF18307F4 10 1B36645FE381EDF48 1F91E295D559091B 5B3E645E3C1EDF48 B094FC12C02C17CA 11 85CA13F50B4ADBB9 ED108EE739DDE02 C5C213F50F4ADBB9 3F405F4A3E254714 12 7963A8EFD15BC4A1 BC714399715A33BA 396BA8EFD55BC4A1 C334C73CC97E4AC4 13 7BCFF7BCA455E65E 475A2D0459BCCE62 3BC7F7BCA005E65E 8E94334AEF359EF8 14 0C505CEDB499218C D3C66239E89CCD76 4C585CEDB099218C 9A316E801EE18EB1 15 6C5EA056CDC91A14 BC7EBA159BCA94E6 2C56A056C9C91A14 67DB935C21EF4A8D 16 6622A441A0D32415 35F8616FEBA62883 262AA441A4B32415 4313E1925F5B64BC 17 C0333C994AEF1C99 D46A4CF1C0221B11 803B3C994EFF1C99 D22B42DB150E2CE8 18 9E7B2974FOOE1A6E 172D286D9606E6FE DE73297BF40E1A6E 2217A91F8C427D27 19 CF592897BFD70C7E FB892B59E7BCE7EC 8F512897BBD70C7E C328B765E1CC6653 20 E976CF39124A9FA1 905BF24188509FA6 A97ECF19164A9FA1 9ADDBA0C23DD724 21 5C09696E7363675D 92D60E5C71801A99 1C01696E7763675D DD90908A4FE8168F 22 AB145AB3C1B2C7DE F68FC9F80568487B E81C5AB3C5B2C7DE 51C041B5711BB132 23 47DF6A0BB1787159 52E36C4CA23EA5A2 07D76A0BB5787159 373EAFB503F68BE4 24 * 7CE65464329B4E6D 832A9D7032015D9F 3CEE5464369B4E6D 85E2CE665571E99 Pair Rightpair Plaintext ciphertext 25 421FB6AD95791BA7 D1E730BA1DB565E7 0217B6AD91791BA7 188E61753FA4F3CE 26 C58E9A361368FFD6 795EB9D30CAE6879
  41. 85869A361768FFD6 26D37AC4867ACC61 27 DD86B6C74C8EA4E2 CC3B6915C9A348BF 9D8EB6C7488EA4E2 104C2394555645F0 28 43DB9D2F483CA585 E3E4DA503D1B9396 03D39D2F4D3CA585 4EA02C0061332443 29 * 855A309F96FEA5EA 85AD6E9E352AFAFA C552309F92FEA5EA 929D22370ACAB80D 30 * AB3CA25B02B08C8 0F7D78E9203F786 EB34A25B0BD18C8 A1313B26299D353 31 A9F7A6F4A7C00E06 F26B385E6BA057FD E9FFA6F4A3C00E02 203D83848F854D19 32 688D9ACD856D1312 C41D99C107B4EF76 28839ACD816D1312 6CC813CA025AFDAC 33 76BF0621C03D4CD9 BBE1F952FC1E052A 36B70621C43D4CD9 561F4801F2EB0C6334 34 014CF8D1F981B8EE D27091C4314CBFE8 4144F8D1FD81B8EE B7976D6A80EADB61 35 487D66EDE0405F8C 8136325C0AEB84CE 087566EDE4405F8C 8C638BC4495B69A0 36 DDCA47093A362521 51040CF16B600FAA 9DC247093E362521 7FC75515AC3CAAF9 37 45A9D34A3996F6D9 F2004B854AE6C46C 05A1D34A3D96F6D9 546825016B03D193 38 295D2FBFB00875EA A309DF027E69C264 69552FBFB40875EA 4F633FFB9530C11E 39 964C8B98D590D524 1FF1D0271D6F6C18 D6448B93D190D524 8CF2D8D401EBFC0F 40 60383D2BAF0836BC 10A82D55FC480640 20303D2BAB0836BC 602346173581EF79 41 5CF8D539A22A1CAD 92685D806FBE8738 1CF0D539A62A1CAD 17006DAB2D28081C 42 F95167CAB6565609 C52E2EB27446054E B95967CAB2565609 0C219F686840EA7A 43 49F1CA3615874122 2680C8ECDF5E51CD 09E9C83611874122 5022AFB69B4E75EF 44 ACB2EC1941B03765 D6B593460098DEC5 ECBAEC1945B03765 D3190A0200FC6B9B 45 CCCC129D5CB55EC0 3AD22B7EF59E0D52 8CC4129D58B55EC0 A48C92CBECB7E430 46 917FF8E2EE6B78D5 EF847E058DE71724 D177F8E2EA6B78D5 F243F0554A00E4C5 47 51DBCF028E96DE00 574897CA1EE73885 11C3CF028A96DE00 9F0FD0A5B2C2B5FD 48 2094942E093463CE 59F6A018C6A0D820 609C9442E0D3463CE 799FE001432346C0 Pair Rightpair Plaintext Ciphertext 49 50FB0723D7CD1081 16AF758395EA3A7D 10F30723D3CD1081 CDCB23392D144BED 50 * 740815A4F6CDCABB 4A84D2ED4D9351AB
  42. 340015A4F2CDCABB 5923D04CE94D6111 51 EDA46A1AE93735DC 0B302A51B7E5476A ADAC6A1AED3735DC 5F817F0ABC770E75 52 * 08BC39B766B2C128 DFB5F3F500BC0100 48B439B762B2C128 B7B9FED8AC93EBFA 53 A74E29BBA98F2312 A2B352B7F922E8DA E74629BBAD8F2312 D6BC4B89CED2DEAC 54 D6F50D31EE4E68AB 4D464847065C0938 96FD0D31EA4E68AB 7554D87AEDCE5634 55 * 06191AA594891CF5 649C1D084F920F9E 46111AA590891CF5 BE12A10384365E65 56 5EA7EFD557946962 15E664293F4D77EE 1EAFEFD553946962 E23396A758DC9CE6 57 41FB7704781CC88A 8ABD385C441FD6CE 01F377047C1CC88A 06DE8D55777AB65C 58 9689B9123F7C5431 E1E63120742099BB D681B9123B7C5431 1AF88A2CF6649A4A 59 6F25032B4A309BFE 48FE50DE774288D7 2F2D032B4E309BFE 47950691260D5E10 60 D8C4B02D8E8BF1E9 F34D565E6AE85683 98CCB02D8A8BF1E9 A4D2DB548622A8E8 61 F663E8CCEE86805B 51BD62C9D5D0F0BB B66BE8CCEA86805B D2ABB03CF9D26C0A 62 428B29BFDFA838DB 006D62A65761089F 028329BFDBA838DBB 9FD73EF6124B0C11 63 04BE2D22D81EDC66 26D99536D99B5707 44B62D22DC1EDC66 94144EBDA0CDEB55 64 667B779123A3EF80 5D09CBF2CE7E5A69 2673779127A3EF80 5EFF8BFCA7BAA152 65 BC86D401D6752438 E05572AAA5F6C377 FC8ED401D2572438 3C670BC455144F61 66 6FE5E9547659E401 2C465BF6F52F864C 2FEDE9547259E401 B71D106444F95F31 67 27D3BAC6453BE3DE 8F160E29000461CD 67DBBAC6413BE3DE 2A6660F46487F885 68 1D864E7642A7023A 65F91EEBFD8A9D05 5D8E4E7646A7023A 84761791B3C36661 69 5256CA6894707CBA 91527F9349ABCF15 125ECA6890707CBA 30F28F06A7B0A35A 70 C05383B8EFCD2BD7 710B6EC61BF63E9C 805B83B8EBCD2BD7 53AC029D8E0179D5 71 50EB21CA17F9A96E 26D95BA4DE4C85CF 10E321CA17F9A96E 8F01A90F638AFFF6 72 60EB1229ACD90EDC 3890EE8567782F96 20E31229A8D90EDC EE404DF7BE537589 Pair Rightpair Plaintext Ciphertext 73 8E9A17D17B173B99 885C3933627EDEF0 CE9217D17F173B99 B7ABB6DF5835E962 74 6EC5CD0802C98817 A985ADFB1FEE013C 2ECDC0806C98817 0428DE024B7E4604 75 1E81712FF1145C06 417E667A99B3CFA5 5E89712FF5145C06 5C24AA056EB1ADBA
  43. 76 DF3C5C13311AEC7C BF01675096F1C48A 9F345C13351AEC7C 243D99BCE12DB864 77 7C34472994127C2D 713915DA311A7CF4 3C3C472990127C2D E9733D11D787E20B 78 37304DABA75EAFB3 EFB5C37FA0238ADF 77384DABA35EAFB3 A728F7407AF958B3 79 D03A16E4C2D8B54B 423FC0AC24CEFEDD 903216E4C6D8B54B 047D8595DB4D372E 80 8CED882B5D91832E 0006E2DE3AF5C2B5 CCE5882B5991832E 00F6AA9ED614001B 81 1BB0E6C79EFBEC41 E9AED4363915775A 5BB8E6C79AFBEC41 655BC48F1FFB5165 82 D41B8346DA9E2252 34F5E0BCC5B042EA 94138346DE9E2252 702D2C48CDBE5173 83 * 02A9D0A0A91F6340 E2F1C10E59AF07C5 42A1D0A0AD1F6304 BDEE6AA00F25F840 84 841B3E27C8F0A561 2B288E554D712C92 C4133E27CCF0A561 FF8609C9E7301162 85 CDF0A8D6EE909185 5D661834D1C76324 8DF8A8D6EA909185 22034D57D21FFB56 86 4C31AC854F44EA34 BD016309AEBD9BB1 0C39AC854B44EA34 C72EEDC4FA1D9312 87 DB3FC0703C972930 296ABCFBF01DF991 9B37C07038972930 CA4700686F9F83A2 88 E4B362BFD6A7CFD1 20FDAF335F25B1DA A4BB62BFD2A7CFD1 008C24D75E14ACBD 89 F234232A0E0A4A28 90CFD699F2DEC5BD B23C232A0A0A4A28 2918D3DE0C1B689C 90 71265345A5874004 3052CE3CE88710AE 312E5345A1874004 38F0FC685DF30564 91 3E6364548C857110 0E8581E42C9FEC6F 7E6B645488857110 4DD1751B61EC5529 92 464FBEDBD78900A7 90F5F9ADEDED627A 0647BEDBD38900A7 2EF4C540425E339B 93 373B75F847480BB0 5408B964F8442D16 773375F843480BB0 805287D52599E9F0 94 D714E87810DE97AC 4EC4D623108FA909 971CE87814DE97AC 0AA0725CED10D6A3 95 B9B5932EF54B2C60 4B438B3CCF36DEC9 F9BD932EF14B2C60 054C6A337709280D 96 2F283C38D2D4E1DD 83515FB6DFEA90B8 6F203C38D6E4D1DD 09BCC4FF38C7BC23 Pair Rightpair Plaintext Ciphertext 97 1EB8ADAA43BBD575 21A1E04813616E42 5EB0ADAA47BBD575 D044BA3F25DFD02A 98 3164AA5454D9F991 9382C6C1883F1038 716CAA5450D9F991 5CDFED4FF2117DEC 99 D78C1C5C6F2243D2 1CCEB091E030E6A6
  44. 97841C5C6B2243D2 4DA2CD67CC449B21 100 BBE212A7D3CE3D14 2917C207B4D93E0D FBEA12A7D7CE3D14 A01D50E5A2B902D8 101 104917795E98D0FB 40916A71385C2803 504117795A98D0FB 413FD26EF671F46D 102 4DDA114D6EFEEEB4 2E2C65E1D5CBAC31 0DD2114D6AFEEEB4 A16FF03BC0913ED6 103 E0BED7B285BF0A77 5D9EFEFF0AD10490 A0B6D7B281BF0A77 4C6CA1FAC36A8E5B 104 0AE1555FA1716214 378400BCED39EB81 4AE9555FA5716214 A1E0C758BD8912C2 105 4657C26790FCB354 588BA079B2E7ED20 065FC26794FCB354 DA90827AEED7A41F 106 32BD719B0DC1B091 F3477C7552BCB05D 72B5719B09C1B091 EFF444449D66BE9E 107 0992F8C8C73A9BFE 9F3FFD0F158295F6 499AF8C8C33A9BFE C138358DCECC8FC7 108 02C3F061A237BBEB AC28B0307127EA7C 42CBF061A637BBEB 3FF1DAED9E0FCBC5 109 80E529E69EDE6827 1DF1DB7B66BA1AF1 C0ED29E69ADE6827 15700151A5804549 110 B55E84630067B8D5 88321611FF9DA421 F55684630467B8D5 90649D7EACF91F9A 111 2749C2EBC603BFF2 A62B23A7348E2C3A 6741C2EBC203BFF2 EB760A09C7FF5153 112 C4C5E14D4C5D9FF5 ABC2312FBFD94DFS 84CDE14D485D9FF5 D2BB5954E5062D53 113 1566BA21F2647E18 A247ED988457CB78 556EBA21F6647E18 5E99F231005F5249 114 2D093D426D992F92 5DF62030B9F23AE9 6D013D4269922F92 5D92DA1F3AD07BA1 115 004518468E0C96C3 F28D85FF7E84F38F 404D18468A0C96C3 52541B0443053C57 116 437B70A98AE03344 04B3FBF9823B4CF7 037370A98EE03344 14EBEC79DAD3093E 117 2D01F1073D3E375B F10B3E1EE356226C 6D09F107393E375B 6FF26DA5E3525B62 118 * 66573DD7E0D7F110 F2F26204C29FE51E 265F3DD7E4D7F110 083A4ECE57E429AC 119 0846DB9538155201 F120D0D2AE700057 484EDB953C155201 00CC914A33034782 120 ABB34FC195C820D1 5F17AE066B50FC81 EBBB4FC191C820D1 2858DD63A2FA4B51 Bài tập 3.1.h y chứng minh rằng phép giải m DES có thể thực hiện bằng cách áp dụng thuật toán m hoá DES cho bản rõ với bảng khoá đảo ng−ợc.
  45. 3.2.Cho DES(x,K) là phép m hoá DES của bản rõ x với khoá K. Giả sử y = DES(x,K) và y' = DES(c(x),c(K)) trong đó c(.) kí hiệu là phần bù theo các bít của biến. Hy chứng minh rằng y' = c(y) ( tức là nếu lấy phần bù của bản rõ và khoá thì bản m kết quả cũng là phần bù của bản m ban đầu). Chú ý rằng kết quả trên có thể chứng minh đ−ợc chỉ bằng cách sử dụng mô tả "mức cao" của DES - cấu trúc thực tế của các hộp S và các thành phần khác của hệ thống không ảnh h−ởng tới kết quả này. 3.3.M kép là một cách để làm mạnh thêm cho DES: với hai khóa K 1 và K 2 cho tr−ớc, ta xác định y = e K2 (e K1 (x)) (dĩ nhiên đây chính là tích của DES với chính nó. Nếu hàm m hoá e K2 giống nh− hàm giải m d K1 thì K 1 và K 2 đ−ợc gọi là các khoá đối ngẫu ( đây là tr−ờng hợp không mong muốn đối với phép m kép vì bản m kết quả lại trùng với bản rõ). Một khoá đ−ợc gọi là tự đối ngẫu nếu nó đối ngẫu với chính nó. a/ Hy chứng minh rằng nếu C 0 gồm toàn các số 0 hoặc gồm toàn các số 1 và D 0 cũng vậy thì K là tự đối ngẫu. b/ Hy tự chứng minh rằng các khoá sau ( cho ở dạng hexa) là tự đối ngẫu: 0101010101010101 FEEFEFEFEFEFEFE 1F1F1F1F0E0E0E0E E0E0E0E0F1F1F1F1 c/ Hy chứng tỏ rằng nếu C 0 = 0101. . . 01 hoặc 1010. . .10 ( ở dạng nhị phân) thì XOR các xâu bít C i và C 17-i là 111. . .11, vơi 1 ≤i ≤16 ( khẳng định t−ơng tự cũng đúng đối với D i). d/ Hy chứng tỏ các cặp khoá sau là đối ngẫu: E001E001F101F101 01E001E001F101F1 FE1FFE1FF0EFE0E 1FFE1FFE0EFE0EFE E01FE01FFF10FF10 1FE01FE00EF10EF1 3.4.Có thể tạo một m xác thực thông báo bằng chế độ CFB cũng nh− chế độ CBC. Cho dy các khối bản rõ x 1. . .x n , giả s− ta xác định véc tơ khởi đầu IV là x 1 . Sau đó m hoá x 2. . .x n bằng khoá K ở chế độ CFB để thu đ−ợc y1 y n-1 ( chú ý rằng chỉ có n-1 khối bản m ). Cuối cùng xác định e K(y n-1) làm MAC. Hy chứng minh rằng MAC này đòng nhất với MAC đ−ợc tạo trong phần 3.4.1. dùng chế độ CBC.
  46. 3.5.Giả sử một dy các khối bản rõ x 1. . .x n đ−ợc m hoá bằng DES, tạo ra các khối bản m y 1. . .y 2 . Giả sử rằng một khối bản m ( chẳng hạn y i) bị phát sai ( tức là có một số số 1 bị chuyển thành số 0 và ng−ợc lại). Hy chỉ ra rằng số các khối bản rõ bị giải m không đúng bằng một nếu ta dùng các chế độ ECB và OFB để m hoá; và bằng hai nếu dùng các chế độ CBC và CFB để m hoá. 3.6.Bài tập này nhằm nghiên cứu một phép tối −u hoá thời gian - bộ nhớ đơn giản đối với phép tấn công bản rõ chọn lọc. Giả sử có một hệ mật trong đó P = C = K và đạt đ−ợc độ mật hoàn thiện. Khi đó e K(x) = e K1 (x) có nghĩa là K = K1 . Kí hiệu P = Y = {y 1,. . .,y N}. Cho x là bản rõ cố định. Định nghĩa hàm g: YY theo quy tắc g(y) = e y(x). Ta xác định một đồ thì có h−ớng G chứa tập đỉnh Y, trong đó tập cạnh chứa tất cả các cạnh có h−ớng có dạng (y i,g(y i)), 1 ≤ i ≤ N. a/ Hy chứng minh rằng G gồm tất cả các chu trình có h−ớng không liên thông. b/ Cho T là một tham số thời gian mong muốn. Giả sử ta có một tập các phần tử Z = {z 1,. . .,z m} ⊆ Y sao cho với mỗi phần tử y i ∈ Y nằm trong một chu trình có độ dài tối đa là T hoặc tồn tại một phần tử z j ≠ y i sao cho khoảng cách tử y i tới z j trong G tối đa là T. Hy chứng tỏ rằng tồn tại một tập Z nh− vậy sao cho: | Z | ≤ 2N/T và nh− vậy | Z | = 0(N/T). -T T c/ Với mỗi z j ∈ Z ta xác định g (z j) là phần tử y i sao cho g (y i) = z j , trong đó g T là một hàm gồm T phép lặp của g. Hy xây dựng một bảng X -T gồm các cặp (z i,g (z j)) đ−ợc sắp xếp theo các toạ độ đầu của chúng. Một mô tả giả m của một thuật toán tìm K với y = e K(x) cho tr−ớc đ−ợc trình bày ở hình 3.15. Hy chứng tỏ thuật toán này tìm K trong tối đa là T b−ớc ( bởi vậy cỡ của phép tối −u hoá thời gian - bộ nhớ là 0(N)). Hình 3.15. Phép tối −u hoá thời gian - bộ nhớ. 1. Ystart = y
  47. 2. Backup = false 3. While g(y) ≠ y start do 4. if y = z j với mỗi j nào đó and not backup then -T 5. y = g (z j) 6. backup = true else 7. y = g(y) 8. K = y d/ Hy mô tả thuật toán giải m để xây dựng một tập Z mong muốn trong thời gian 0(NT) không dùng một mảng có kích th−ớc N. 3.7. Hy tính các xác suất của đặc tr−ng 3 vòng sau: L 0' = 00200008 16 R 0' = 00000400 16 L 1' = 00000400 16 R 1' = 00000000 16 p = ? L 2' = 00000000 16 R 2' = 00000400 16 p = ? L 3' = 00000400 16 R 3' = 00200008 16 p = ? 3.8. Sau đây là một phép tấn công vi sai đối với DES 4 vòng sử dụng đặc tr−ng sau ( đây là một tr−ờng hợp đặc biệt của đặc tr−ng đ−ợc trình bày ở hình 3.10). L 0' = 20000000 16 R 0' = 00000000 16 L 1' = 00000000 16 R 1' = 20000000 16 p = 1 a/ Giả sử rằng thuật toán sau ( đ−ợc nêu ở hình 3.16) đ−ợc dùng để tính các tập test 2,. . .,test 8. Hy chứng tỏ rằng J j ∈ test j với 2 ≤ j ≤ 8. Hình 3.16. Tấn công DC lên DES 4 vong. * * * * Vào : L 0R0, L 0 R0 , L 3R3 và L 3 R3 , trong đó
  48. L 0' = 10000000 16 và R 0' = 00000000 16 -1 1. Tính C ' = P (R 4') * * * 2. Tính E = E(L 4) và E = E (L 4 ) 3. For j =2 to 8 do * Tính testj(E j,E j ,C j') b/ Với các cặp bản rõ - m sau, hy xác định các bít khoá trong J2, ,J 8. Bản rõ Bản m 18493AC485B8D9A0 E332151312A18B4F 38493AC485B8D9A0 87391C27E5282161 482765DDD7009123 B5DDD833D82D1D1 682765DDD7009123 81F4B92BD94B6FD8 ABCD098733731FF1 93A4B42F62EA59E4 8BCD098733731FF1 ABA494072BF411E5 13578642AAEDCB FDEB526275FB9D94 33578642AAFFEDCB CC8F72AAE685FDB1 c/ Hy tính toàn bộ khoá ( 14 bít khoá còn lại cần phải xác định có thể tìm theo ph−ơng pháp tìm kiếm vét cạn).