Cơ sở mật mã học - Chương 2: Lý thuyết Shannon

rị của n mà ứng với giá trị này, số khoá giả trung bình bằng 0 (kí hiệu giá trị này là n0). Điều đó có nghĩa là n0 là độ dài trung bình cần thiết của bản mã để thám mã có thể tính toán khoá một cách duy nhất với thời gian đủ lớn.
	Nếu đặt sn =0 trong định lý 2.11 và giải theo n ta sẽ nhận được ước lượng cho khoảng duy nhất:
n0 » log2|K| / RL log2 |P|
	Ví dụ với MTT, ta có |P| = 26 và |K| =26 !. Nếu lấy RL =0,75 thì ta nhận được ước lượng cho khoảng duy nhất bằng:
n0 » 88,4/ (0,75 ´4,7) » 25
Điều đó có nghĩa là thông thường nếu mã thám có được xâu bản mã với độ dài tối thiểu là 25, anh ta có thể nhận được bản giải mã duy nhất.
2.5. Các hệ mật mã tích 
	Một phát minh khác do Shannon đưa ra trong bài báo của mình năm 1949 là ý tưởng kết hợp các hệ mật bằng cách tạo tích của chúng. ý tưởng này có tầm quan trọng to lớn trong việc thiết kế các hệ mật hiện nay ( chẳng hạn chuẩn mã dữ liệu -DES ).
	Để đơn giản, trong phần này chỉ hạn chế xét các hệ mật trong đó C=P: các hệ mật loại này được gọi là tự đồng cấu. Giả sử S1= (P, P, K1, E1, D1) và S2= (P, P, K2, E2, D2) là hai hệ mật tự đồng cấu có cùng các không gian bản mã và rõ. Khi đó, tích của S1 và S2 (kí hiệu là S1 ´ S2) được xác định là hệ mật sau:
(P, P, K1 ´ K2, E, D)
Khoá của hệ mật tích có dạng K = (K1,K2) trong đó K1 Î K1 và K2 Î K2. Các quy tắc mã và giải mã của hệ mật tích được xác định như sau: Với mỗi K = (K1,K2), ta có một quy tắc mã EK xác định theo công thức:
và quy tắc giải mã:
Nghĩa là trước tiên ta mã hoá x bằng eK1 rồi mã lại bản kết quả bằng eK2. Quá trình giải mã tương tự nhưng thực hiện theo thứ tự ngược lại:
	Ta biết rằng, các hệ mật đều có các phân bố xác suất ứng với các không gian khoá của chúng. Bởi vậy, cần phải xác định phân bố xác suất cho không gian khoá K của hệ mật tích. Hiển nhiên ta có thể viết:
pK(K1,K2)= pK1(K1) ´ pK2=(K2)
Nói một cách khác, ta chọn K1 có phân bố pK1 rồi chọn một cách độc lập K2 có phân bố pK2(K2).
	Sau đây là một ví dụ đơn giản để minh hoạ khái niệm hệ mật tích. Giả sử định nghĩa hệ mật mã nhân như trong hình 2.2 sau.
Hình 2.2. Mã nhân
 Giử sử P = C = Z26 và giả sử:
 K = {a Z26: UCLN(a,26) = 1}
 Với a Î K, ta xác định: ea(x) = ax mod 26
 và	 da(y) = a-1y mod 26
 (x,y) Î Z26.
	Cho M là một hệ mã nhân ( Với các khoá được chọn đồng xác suất) và S là MDV ( với các khoá chọn đồng xác suất). Khi đó dễ dàng thấy rằng M´S chính là hệ mã Affine ( cùng với các khoá được chọn đồng xác suất). Tuy nhiên việc chướng tỏ S ´M cũng là hệ mã Affine khó hơn một chút ( cũng với các khóa đồng xác suất).
	Ta sẽ chứng minh các khẳng định này. Một khoá dịch vòng là phần tử K ÎZ26 và quy tắc giải mã tương ứng là eK(x) = x + K mod 26. Còn khoá trong hệ mã nhân là phần tử a ÎZ26 sao cho UCLN(a,26) = 1. Quy tắc mã tương ứng là ea(x) = a mod 26. Bởi vậy, một khoá trong mã tích M ´ S có dạng (a,K), trong đó
e(a,K)(x) =a x + K mod 26
Đây chính là định nghĩa về khoá trong hệ mã Affine. Hơn nữa, xác suất của một khoá trong hệ mã Affine là:1/312 = 1/12 ´ 1/26. Đó là tích của xác suất tương ứng của các khoá a và K. Bởi vậy M ´S là hệ mã A ffine.
	Bây giờ ta sẽ xét S ´M. Một khoá này trong hệ mã này có dạng (K ,a) trong đó:
e(K,a)(x) = a(x+K) = a x + aK mod 26
Như vậy khoá (K,a) của mã tích S´M đồng nhất với khoá (a, aK) của hệ mã Affine. Vấn đề còn lại là phải chứng tỏ rằng mỗi khoá của mã Affine xuất hiện với cùng xác suất 1/312 như trong mã tích S´M. Nhận thấy rằng, aK = K1 khi và chỉ khi K = a-1K1, ( hãy nhớ lại rằng UCLN(a,26) =1, bởi vậy a có phần tử nghịch đảo). Nói cách khác, khoá (a, K1) của hệ mã Affine tương đương với khoá (a-1K1,a) của mã tích S´M. Bởi vậy, ta có một song ánh giữa hai không gian khoá. Vì mỗi khoá là đồng xác suất nên có thể thấy rằng S´M thực sự là mã Affine.
	Ta chứng minh rằng M ´S = S ´ M. Bởi vậy, hai hệ mật là giao hoán. Tuy nhiên không phải mọi cặp hệ mật đều giao hoán; có thể tìm ta được các cặp phản ví dụ, Mặt khác ta thấy rằng phép tích luôn kết hợp:
(S1 ´ S2) ´ S3 = S1 ´ (S2 ´ S3)
	Nếu lấy tích của một hệ mật tự đồng cấu với chính nó thì ta thu được hệ mật S´S (kí hiệu là S2). Nếu lấy tích n lần thì hệ mật kết quả là Sn. Ta gọi Sn là hệ mật lặp.
	Một hệ mật S được gọi là luỹ đẳng nếu S2 = S. Có nhiều hệ mật đã nghiên cứu trong chương 1 là hê mật luỹ đẳng. Chẳng hạn các hệ MDV, MTT, Affine, Hill, Vigenère và hoán vị đều là luỹ đẳng. Hiển nhiên là nếu hệ mật S là luỹ đẳng thì không nên sử dụng hệ mâth tích S2 vì nó yêu cầu lượng khoá cực lớn mà không có độ bảo mật cao hơn.
	Nếu một hệ mật không phải là luỹ đẳng thì có khả năng làm tăng độ mật bằng cách lặp nhiều lần. ý tưởng này đã được dùng trong chuẩn mã dữ liệu (DES). Trong DES dùng 16 phép lặp, tất nhiên hệ mật ban đầu phải là hệ mật không luỹ đẳng. Một phương pháp có thể xây dựng các hệ mật không luỹ đẳng đơn giản là lấy tích của hai hệ mật đơn giản khác nhau.
Nhận xét:
	Có thể dễ dàng chứng tỏ rằng, nếu cả hai hệ mật S1 và S2 là luỹ đẳng và giao hoán thì S1 và S2 cũng là luỹ đẳng. Điều này rút ra từ các phép toán đại số sau:
	(S1 ´ S2) ´(S1 ´ S2) = S1 ´ (S2 ´ S1) ´ S2
	=S1 ´ (S1 ´ S2) ´ S2
	=(S1 ´ S1) ´ (S2 ´ S2)
	= S1 ´ S2.
( Chú ý dùng tính chất kết hợp trong chứng minh trên)
	Bởi vậy, nếu cả S1 và S2 đều là luỹ đẳng và ta muốn S1 ´ S2 là không luỹ đẳng thì điều kiện cần là S1 và S2 không giao hoán.
Rất may mắn là nhiều hệ mật đơn giản thoả mãn điều kiện trên. Kỹ thuật thường được sử dụng trong thực tế là lấy tích các hệ mã kiểu thay thế và các hệ mã kiểu hoán vị. Trong chương sau ta sẽ xét một thể hiện cụ thể của kỹ thuật này.
Các chú giải.
Khái niệm độ mật hoàn thiện và việc sử dụng các kỹ thuật entropi trong các hệ mật lần đầu tiên do Shannon đưa ra trong [SH49]. Các hệ mật tích cũng được thảo luận trong bài báo này. Khái niệm entropi cũng do Shannon đưa ra trong [SH48]. Các sách nhập môn tốt về entropi, mã Huffman và các vấn đề có liên quan có trong các tài liệu của Welsh [WE88] và Goldie, Pinch [GP91]. Các kết quả trong phần 2.4 được lấy theo Beauchemin và Brassard [BB88], các tác giả này đã tổng quát hoá các kết quả ban đầu của Shannon.
Bài tập
2.1. Cho n là một số nguyên dương. Một hình vuông Latin cấp n (L) là một bảng n ´ n các số nguyên 1, . . . , n sao cho mỗi một số trong n số nguyên này chỉ xuất hiện đúng một lần ở mỗi hàng và mỗi cột của L. Ví dụ hình vuông Latin cấp 3 có dạng:
1
2
3
3
1
2
2
3
1
Với một hình vuông Latin L bất kỳ cấp n, ta có thể xác định một hệ mã tương ứng. Giả sử P = C = K = { 1, . . ., n}. Với 1 £ i £ n, quy tắc mã hoá ei được xác định là ei(j) = L(i,j). Do đó mỗi hàng của L sẽ cho một quy tắc mã hoá).
	Hãy chứng minh rằng, hệ mật hình vuông Latin này có độ mật hoàn thiện.
2.2. Hãy chứng tỏ rằng mã Affine có độ mật hoàn thiện
2.3. Giả sử một hệ mật đạt được độ mật hoàn thiện với phân bố xác suất p0 nào đó của bản rõ. Hãy chứng tỏ rằng độ mật hoàn thiện vẫn còn dữ được đối với một phân bố xác suất bất kì của bản rõ.
2.4. Hãy chứng tỏ rằng nếu một hệ mật có độ mật hoàn thiên và |K| = |C| = |P| thì mọi bản mã là đồng xác suất.
2.5. Giả sử X là tập có lực lượng n, trong đó 2k £ n £ 2k+1 và p(x) =1/n với mọi x ÎX.
a/ Hãy tìm một phép mã hoá có tiền tố độc lập của X (kí hiệu là f) sao cho l(f) = k+2 - 2k+1/n
Chỉ dẫn: Hãy mã hoá 2k+1-n các phần tử của X bằng các xâu có độ dài k và mã hoá các phần tử còn lại bằng các xâu có độ dài k+1.
	b/ Hãy minh hoạ cấu trúc của bạn khi n = 6. Tính l(f) và H(X) trong trường hợp này.
2.6. Giả sử X = {a,b,c,d,e} có phân bố xác suất như sau: p(a) = 0,32, p(b) = 0,23 p(c) = 0,20, p(d) = 0,15, p(e) = 0,10. Hãy dùng thuật toán Huffman để tìm phép mã hoá tối ưu có tiền tố độc lập của X. So sánh độ dài của phép mã này với H(X).
2.7. Hãy chứng tỏ rằng H(X,Y) = H(Y) +H(X|Y). Sau đó chứng minh bổ đề là H(X|Y) £ H(X), đẳng thức chỉ xảy ra khi và chỉ khi X và Y độc lập.
 2.8. Chứng minh rằng, một hệ mật có độ mật hoàn thiện khi và chỉ khi H(P|C) = H(P).
2.9. Chứng minh rằng trong một hệ mật bất kỳ H(K|C) ³H(P C) ( về mặt trực giác, kết quả này nói rằng với bản mã cho trước, độ bất định của thám mã về khoá ít nhất cũng lớn bằng độ bất định khi thám mã bản rõ).
2.10. Xét một hệ mật trông đó P = {a,b,c}, K = {K1,K2,K3} và C = {1,2,3,4}. Giả sử ma trận mã hoá như sau:
a
B
c
K1
1
2
3
K2
2
3
4
K3
3
4
1
	Giả sử các khoá được chọn đồng xác suất và phần bố xác suất của bản rõ là pP(a) = 1/2, pP(b) = 1/3, pP(c) = 1/6. Hãy tính H(P), H(C), H(K), H(K|C) và H(P|C).
2.11. Hãy tính H(K|C) và H(K|P,C) của hệ mã Affine.
2.12. Xét hệ mã Vigenère có độ dài từ khoá là m. Hãy chứng tỏ khoảng duy nhất là 1/RL, trong đó RL là độ dư của ngôn ngữ đang xét. (kết quả này được hiểu như sau: Nếu n0 là số kí tự cần mã hoá thì độ dài của bản rõ là n0/m vì mỗi phần tử của bản rõ gồm m kí tư. Bởi vậy, khoảng duy nhất 1/RL ứng với một bản rõ gồm m/RL kí tự).
2.13. Hãy chỉ ra rằng, khoảng duy nhất của hệ mã Hill ( với ma trận mã hoá m´m) là nhỏ hơn m/RL ( hãy chú ý rằng số kí tự trong môt bản rõ có độ dài là m2/RL).
2.14. MTT trên không gian rõ ( có kích thước n) sẽ có |K| = n!. Công thức Stirling cho ước lượng sau đối với n:
	a/ Dùng công thức Stirling, đưa ra một khoảng ước lượng cho khoảng duy nhất của MTT.
	b/ Cho m ³1 là một số nguyên. MTT bộ m là hệ mã thay thế trong đó các không gian rõ ( và bản mã) chứa tất cả 26m các bộ m. Hãy đánh giá khoảng duy nhất của MTT bộ m nếu RL = 0,75.
2.15. Hãy chứng minh rằng MDV là luỹ đẳng.
2.16. Giả sử S1 là MDV ( với các khoá đồng xác suất) và S2 là MDV trong đó các khoá được chọn theo một phân bố xác suất pK nào đó ( không đồng xác suất). Hãy chứng tỏ rằng S1´S2 = S1.
2.17. Giả sử S1 và S2 là các hệ mã Vigenère có độ dài từ khoá tương ứng là m1 và m2 trong đó m1 ³ m2.
	a/ Nếu m1 | m2 thì chỉ ra rằng S1 ´ S2 = S1.
	b/ Ta thử tổng quát hoá kết quả trên bằng giả định rằng S2´S1 = S3, S3 là hệ mã Vigenère có độ dài từ khoá là BCNN(m1,m2) ( BCNN - bội chung nhỏ nhất). Hãy chứng tỏ rằng giả định này là không đúng.
Chỉ dẫn: Nếu m1 ¹0 mod m2 thì số các khoá trong hệ mã tích S1´S 2 nhỏ hơn số khoá trong S3.