Cơ sở mật mã học - Chương 3: Chuẩn mã dữ liệu

 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 ni tập được phép có lực lượng như sau:
i
ni
2
3
4
5
6
7
8
9
10
111
180
231
255
210
120
45
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 J2, J5, J6, J7, J8. Chúng có giá trị như sau:
J2 = 011001
J5 = 110000
J6 = 001001
J7 = 101010
J8 = 100011
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ì
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 J1 và J4). 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. 
 L0' = 0020000816 R0' = 0000040016 
 L1' = 0000040016 R1' = 0000000016 p = 1/4
 L2' = 0000000016 R2' = 0000040016 p = 1
 L3' = 0000040016 R3' = 0020000816 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 214 bản rõ chọn lọc, DES 10, 12, 14, 16 vòng có thể phá được với tương ứng là 224, 231, 239 và 247 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ị - 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 107 USD có thể xây dựng thiết bị chuyên dụng để phá DES trong khoảng 21 phút. Với 108 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 243 ´ 26 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 243 (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ã
1
**
86FA1C2B1F51D3BE
C6F21CC2B1B51D3BE
1E23ED7F2F551971
296DE2BG87AC6310
2
**
EDC439EC935E1ACD
ADCC39EC975E1ACD
0F847EFE90466588
93E84839E374440B
3
**
9468A0BE00166155
D460A0BE04166155
3D6A906A6566D0BF
3BC3B23698379E1
4
**
D4FF2B18A5A8AACB
94F72B18A1A8AAC8
26B14738C2556BA4
15753FDE86575ABF
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.
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. Hãy 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 K1 và K2 cho trước, ta xác định y = eK2(eK1(x)) (dĩ nhiên đây chính là tích của DES với chính nó. Nếu hàm mã hoá eK2 giống như hàm giải mã dK1 thì K1 và K2 đượ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/ Hãy chứng minh rằng nếu C0 gồm toàn các số 0 hoặc gồm toàn các số 1 và D0 cũng vậy thì K là tự đối ngẫu.
	b/ Hãy tự chứng minh rằng các khoá sau ( cho ở dạng hexa) là tự đối ngẫu:
0101010101010101
FEEFEFEFEFEFEFE
1F1F1F1F0E0E0E0E
E0E0E0E0F1F1F1F1
	c/ Hãy chứng tỏ rằng nếu C0 = 0101. . . 01 hoặc 1010. . .10 ( ở dạng nhị phân) thì XOR các xâu bít Ci và C17-i là 111. . .11, vơi 1 £i £16 ( khẳng định tương tự cũng đúng đối với Di).
	d/ Hãy 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 dãy các khối bản rõ x1. . .xn , giả sư ta xác định véc tơ khởi đầu IV là x1 . Sau đó mã hoá x2. . .xn bằng khoá K ở chế độ CFB để thu được y1...yn-1 ( chú ý rằng chỉ có n-1 khối bản mã ). Cuối cùng xác định eK(yn-1) làm MAC. Hãy 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.
3.5.Giả sử một dãy các khối bản rõ x1. . .xn được mã hoá bằng DES, tạo ra các khối bản mã y1. . .y2 . Giả sử rằng một khối bản mã ( chẳng hạn yi) 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). Hãy 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 đó eK(x) = eK1(x) có nghĩa là K = K1 . Kí hiệu P = Y = {y1,. . .,yN}. Cho x là bản rõ cố định. Định nghĩa hàm g: YàY theo quy tắc g(y) = ey(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 (yi,g(yi)), 1 £ i £ N.
	a/ Hãy 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 = {z1,. . .,zm} Í Y sao cho với mỗi phần tử yi Î 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ử zj ¹ yi sao cho khoảng cách tử yi tới zj trong G tối đa là T. Hãy 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).
	c/ Với mỗi zj Î Z ta xác định g-T(zj) là phần tử yi sao cho gT(yi) = zj , trong đó gT là một hàm gồm T phép lặp của g. Hãy xây dựng một bảng X gồm các cặp (zi,g-T(zj)) đượ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 = eK(x) cho trước được trình bày ở hình 3.15. Hãy 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ớ.
Ystart = y
Backup = false
While g(y) ¹ ystart do
 if y = zj với mỗi j nào đó and not backup then 
 y = g-T(zj)
 backup = true
 else
y = g(y)
K = y
	d/ Hãy 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. Hãy tính các xác suất của đặc trưng 3 vòng sau:
 L0' = 0020000816 R0' = 0000040016 
 L1' = 0000040016 R1' = 0000000016 p = ?
 L2' = 0000000016 R2' = 0000040016 p = ?
 L3' = 0000040016 R3' = 0020000816 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).
 L0' = 2000000016 R0' = 0000000016 
 L1' = 0000000016 R1' = 2000000016 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 test2,. . .,test8. Hãy chứng tỏ rằng Jj Î testj với 2 £ j £ 8.
Hình 3.16. Tấn công DC lên DES 4 vong.
 Vào : L0R0, L0*R0*, L3R3 và L3*R3*, trong đó
 L0' = 1000000016 và R0' = 0000000016 
Tính C ' = P-1(R4') 
Tính E = E(L4) và E* = E*(L4*)
For j =2 to 8 do 
 Tính testj(Ej,Ej*,Cj') 
	b/ Với các cặp bản rõ - mã sau, hãy xác định các bít khoá trong J2,...,J8.
Bản rõ Bản mã
18493AC485B8D9A0 E332151312A18B4F
38493AC485B8D9A0 87391C27E5282161
482765DDD7009123 B5DDD833D82D1D1
682765DDD7009123 81F4B92BD94B6FD8
ABCD098733731FF1 93A4B42F62EA59E4
8BCD098733731FF1 ABA494072BF411E5
13578642AAEDCB FDEB526275FB9D94
33578642AAFFEDCB CC8F72AAE685FDB1
	c/ Hãy 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).