Bài giảng Lý thuyết Shannon

Nội dung text: Bài giảng Lý thuyết Shannon

1. Ch−ơng 2 Lý thuyết shannon Năm 1949, Claude shannon đ công bố một bài báo có nhan đề " Lý thuyết thông tin trong các hệ mật" trên tạp chí " The Bell System Technical Journal". Bài báo đ có ảnh h−ởng lớn đến việc nghiên cứu khoa học mật m. Trong ch−ơng này ta sẽ thảo luận một vài ý t−ởng trong lý thuyết của Shannan. 2.1 độ mật hoàn thiện. Có hai quan điểm cơ bản về độ an toàn của một hệ mật. Độ an toàn tính toán: Đo độ này liên quan đến những nỗ lực tính toán cần thiết để phá một hệ mật. Một hệ mật là an toàn về mặt tính toán nếu có một thuật toán tốt nhất để phá nó cần ít nhất N phép toán, N là số rất lớn nào đó. Vấn đề là ở chỗ, không có một hệ mật thực tế đ biết nào có thể đ−ợc chứng tỏ là an toàn theo định nghĩa này. Trên thực tế, ng−ời ta gọi một hệ mật là "an toàn về mặt tính toán" nếu có một ph−ơng pháp tốt nhất phá hệ này nh−ng yêu cầu thời gian lớn đến mức không chấp nhận đ−ợc.(Điều này tất nhiên là rất khác với việc chứng minh về độ an toàn). Một quan điểm chứng minh về độ an toàn tính toán là quy độ an toàn của một hệ mật về một bài toán đ đ−ợc nghiên cứu kỹ và bài toán này đ−ợc coi là khó. Ví dụ, ta có thể chứng minh một khẳng định có dạng " Một hệ mật đ cho là an toàn nếu không thể phân tích ra thừa số một số nguyên n cho tr−ớc". Các hệ mật loại này đôi khi gọi là " an toàn chứng minh đ−ợc". Tuy nhiên cần phải hiểu rằng, quan điểm này chỉ cung cấp một chứng minh về độ an toàn có liên quan đế một bài toán khác chứ không phải là một chứng minh hoàn chỉnh về ọ an toàn. ( Tình hình này cũng t−ơng tự nh− việc chứng minh một bài toán là NP đầy đủ: Có thể chứng tỏ bài toán đ cho chí ít cũng khó nh− một bài toán NP đầy đủ khác , song không phải là một chứng minh hoàn chỉnh về độ khó tính toán của bài toán). Độ an toàn không điều kiện. Độ đo này liện quan đến độ an toàn của các hệ mật khi không có một hạn chế nào đ−ợc đặt ra về khối l−ợng tính toán mà Oscar đ−ợc phép thực
2. hiện. Một hệ mật đ−ợc gọi là an toàn không điều kiện nếu nó không thể bị phá thậm chí với khả năng tính toán không hạn chế. Khi thảo luận về độ an toàn của một mật, ta cũng phải chỉ ra kiểu tấn công đang đ−ợc xem xét. Trong ch−ơng 1 đ cho thấy rằng, không một hệ mật nào trong các hệ m dịch vòng, m thay thế và m Vigenère đ−ợc coi là an toàn về mặt tính toán với ph−ơng pháp tấn công chỉ với bản m ( Với khối l−ợng bản m thích hợp). Điều này mà ta sẽ làm trong phần này là để phát triển lý thuyết về các hệ mật có độ an toàn không điều kiện với ph−ơng pháp tấn công chỉ với bản m. Nhận thấy rằng, cả ba hệ mật nêu trên đều là các hệ mật an toàn vô điều kiện chỉ khi mỗi pkần tử của bản rõ đ−ợc m hoá bằng một khoá cho tr−ớc!. Rõ ràng là độ an toàn không điều kiện của một hệ mật không thể đ−ợc nghiên cứu theo quan điểm độ phức tạp tính toán vì thời gian tính toán cho phép không hạn chế. ở đây lý thuyết xác suất là nền tảng thích hợp để nghiên cứu về độ an toàn không điều kiện. Tuy nhiên ta chỉ cần một số kiến thức sơ đẳng trong xác suất; các định nghĩa chính sẽ đ−ợc nêu d−ới đây. Định nghĩa 2.1. Giả sử X và Y là các biến ngẫu nhiên. Kí hiệu xác suất để X nhận giá trị x là p(x) và để Y nhận giá trị y là p(y). Xác suất đồng thời p(x,y) là xác suất để X nhận giá trị x và Y nhận giá trị y. Xác suất có điều kiện p(x | y) là xác suất để X nhận giá trị với điều kiện Y nhận giá trị y. Các biến ngẫu nhiên X và Y đ−ợc gọi là độc lập nếu p(x,y) = p(x) p(y) với mọi giá trị có thể x của X và y của Y. Quan hệ giữa xác suất đồng thời và xác suất có điều kiện đ−ợc biểu thị theo công thức: p(x,y) = p(x | y) p(y) Đổi chỗ x và y ta có : p(x,y) = p(y | x) p(x) Từ hai biểu thức trên ta có thể rút ra kết quả sau:(đ−ợc gọi là định lý Bayes) Định lý 2.1: (Định lý Bayes). Nếu p(y) > 0 thì: p(x) p(y | x) p(x | y) = p(y)
3. Hệ quả 2.2. X và Y là các biến độc lập khi và chỉ khi: p(x | y) = p(x) với mọi x,y. Trong phần này ta giả sử rằng, một khoá cụ thể chỉ dùng cho một bản m. Giả sử có một phân bố xác suất trên không gian bản rõ P. Kí hiệu xác suất tiên nghiệm để bản rõ xuất hiện là pP (x). Cũng giả sử rằng, khóa K đ−ợc chọn ( bởi Alice và Bob ) theo một phân bố xác suất xác định nào đó. ( Thông th−ờng khoá đ−ợc chọn ngẫu nhiên, bởi vậy tất cả các khoá sẽ đồng khả năng, tuy nhiên đây không phải là điều bắt buộc). Kí hiệu xác suất để khóa K đ−ợc chọn là pK(K). Cần nhớ rằng khóa đ−ợc chọn tr−ớc khi Alice biết bản rõ. Bởi vậy có thể giả định rằng khoá K và bản rõ x là các sự kiện độclập. Hai phân bố xác suất trên P và K sẽ tạo ra một phân bố xác suất trên C. Thật vậy, có thể dễ dàng tính đ−ợc xác suất pP(y) với y là bản m đ−ợc gửi đi. Với một khoá K ∈ K, ta xác định: C(K) = { eK (x) : x ∈P } ở đây C(K) biểu thị tập các bản m có thể K là khóa. Khi đó với mỗi y ∈ C, ta có : pC (y) = ∑ pK(K) pP(dK (y)) {K:y ∈C(K)} Nhận thấy rằng, với bất kì y ∈ C và x ∈ P, có thể tính đ−ợc xác suất có điều kiện pC(y | x).(Tức là xác suất để y là bản m với điều kiện bản rõ là x): pC (y | x ) = ∑ pK(K) {K:x= d K(y)} Bây giờ ta có thể tính đ−ợc xác suất có điều kiện pP (x | y ) ( tức xác suất để x là bản rõ với điều kiện y là bản m) bằng cách dùng định lý Bayes. Ta thu đ−ợc công thức sau: pP (x) = ∑ pK(K) {K:x= d (y)} K pP(y | x ) = ∑ pK(K) pP(dK (y)) {k,U:y ∈c(k)} Các phép tính này có thể thực hiện đ−ợc nếu biết đ−ợc các phân bố xác suất. Sau đây sẽ trình bày một ví dụ đơn giản để minh hoạ việc tính toán các phân bố xác suất này.
4. Ví dụ 2.1. Giả sử P = {a,b} với pP(a) = 1/4, pP(b) = 3/4. Cho K = { K 1, K 2, K3} với pK(K1) = 1/2, pK(K2) = pK(K3) = 1/4. Giả sử C = {1,2,3,4} và các hàm m đ−ợc xác định là eK1 (a) = 1, eK2 (b) = 2, eK2 (a) = 2, eK2 (b) = 3, eK3 (a) = 3, eK3 (a) = 4. Hệ mật này đ−ợc biểu thị bằng ma trận m hoá sau: a b K1 1 2 K2 2 3 K3 2 4 Tính phân bố xác suất pC ta có: pC (1) = 1/8 pC (2) = 3/8 + 1/16 = 7/16 pC (3) = 3/16 + 1/16 = 1/4 pC (4) = 3/16 Bây giờ ta đ có thể các phân bố xác suất có điều kiện trên bản rõ với điều kiện đ biết bản m. Ta có : pP(a | 1) = 1 pP(b | 1) = 0 pP(a | 2) = 1/7 pP(b | 2) = 6/7 pP(a | 3) = 1/4 pP(b | 3) = 3/4 pP(a | 4) = 0 pP(b | 4) = 1 Bây giờ ta đ có đủ điều kiện để xác định khái niệm về độ mật hoàn thiện. Một cách không hình thức, độ mật hoàn thiện có nghi là Oscar với bản m trong tay không thể thu đ−ợc thông tin gì về bản rõ. ý t−ởng này sẽ đ−ợc làm chính xác bằng cách phát biểu nó theo các thuật ngữ của các phân bố xác suất định nghĩa ở trên nh− sau: Định nghĩa 2.2. Một hệ mật có độ mật hoàn thiện nếu pP(x | y) = pP(x) với mọi x ∈ P , y ∈ C . Tức xác suất hậu nghệm để bản rõ là x với điều kiện đả thu đ−ợc bản mG y là đồng nhất với xác suất tiên nghiệm để bản rõ là x. Trong ví dụ 2.1 chỉ có bản m 3 mới thoả mn tính chất độ mật hoàn thiện, các bản m khác không có tính chất này. Sau đây sẽ chứng tỏ rằng, MDV có độ mật hoàn thiện. Về mặt trực giác, điều này d−ờng nh− quá hiển nhiên. Với m dịch vòng, nếu đ biết một phần tử bất kỳ của bản m y ∈ Z26 , thì một phần tử bất kỳ của bản rõ x ∈ Z26 cũng có thể là bản m đả giải của y tuỳ thuộc vào giá trị của khoá. Định lý
5. sau cho một khẳng định hình thức hoá và đ−ợc chứng minh theo các phân bố xác suất. Định lý 2.3. Giả sử 26 khoá trong MDV có xác suất nh− nhau và bằng1/26 khi đó MDV sẽ có độ mật hoàn thiện với mọi phân bố xác suất của bản rõ. Chứng minh: Ta có P = C = K = Z26 và với 0 ≤ K ≤ 25, quy tắc m hoá eKlà eK(x) =x +K mod 26 (x ∈ 26). Tr−ớc tiên tính phân bố PC . Giả sử y ∈ Z26 , khi đó: pC (y) = ∑ pK(K) pP(dK (y)) K∈ Z 26 = ∑ 1/26 pP(y -K) K∈ Z 26 = 1/26 ∑ pP(y -K) K∈ Z 26 Xét thấy với y cố định, các giá trị y -K mod 26 sẽ tạo thành một hoán vị của Z26 và pP là một phân bố xác suất. Bởi vậy ta có: ∑ pP(y -K) = ∑ pP(y) K∈ Z 26 y∈ Z 26 = 1 Do đó pC (y) = 1/26 với bất kỳ y ∈ Z26 . Tiếp theo ta có: pC (y|x) = pK(y -x mod 26) = 1/26 Vơi mọi x,y vì với mỗi cặp x,y, khóa duy nhất K (khoá đảm bảo eK(x) = y ) là khoá K = y-x mod 26. Bây giờ sử dụng định lý Bayes, ta có thể dễ dàng tính: p (x) p (y|x) p (x|y) = P C P p (y) C = pP(x) . (1/26) (1/26) = p P(x)
6. Bởi vậy, MDV có độ mật hoàn thiện. Nh− vậy, m dịch vòng là hệ mật không phá đ−ợc miễn là chỉ dùng một khoá ngẫu nhiên để m hoá mỗi ký tự của bản rõ. Sau đây sẽ ngiên cứu độ mật hoàn thiện trong tr−ờng hợp chung. Tr−ớc tiên thấy rằng,(sử dụng định lý Bayes) điều kiện để pP (x | y) = pP (x) với mọi x ∈P , y ∈P là t−ơng đ−ơng với pC (y | x) = pC (y) với mọi x ∈P , y ∈P . Giả sử rằng pC (y) > 0 với mọi y ∈C (pC (y) = 0 thì bản m sẽ không đ−ợc dùng và có thể loại khỏi C ). Cố định một giá trị nào đó x ∈P. Với mỗi y∈C ta có pC (y | x) = pC (y) > 0. Bởi vậy, với mỗi y ∈C phải có ít nhất một khoá K sao cho eK(x) = y. Điều này dẫn đến |K | ≥ | C | . Trong một hệ mật bất kỳ ta phải có |C | ≥ | P | vì mỗi quy tắc m hoá là một đơn ánh. Trong tr−ờng hợp giới hạn, |K | = | C | = | P |, ta có định lý sau (Theo Shannon). Định lý 2.4 Giả sử ( P,C, K, E, D ) là một hệ mật , trong đó |K | = | C | = | P | . Khi đó, hệ mật có độ mật hoàn thiện khi và mỗi khi khoá K đ−ợc dùng với xác suất nh− nhau bằng 1/ |K | , và mỗi x ∈P,mỗi y ∈C có một khoá duy nhất K sao cho eK(x) = y. Chứng minh Giả sử hệ mật đ cho có độ mật hoàn thiện. Nh− đ thấy ở trên, với mỗi x ∈P và y ∈C , phải có ít nhất một khoá K sao cho eK(x) = y. Bởi vậy ta có bất đẳng thức: | C | = |{e K(x) :K ∈C } | ≤ | K | Tuy nhiên, ta giả sử rằng | C | = |K | . Bởi vậy ta phải có: |{e K(x) :K ∈C } | = | K | Tức là ở đây không tồn tại hai khoá K1 và K2 khác nhau để eK1 (x) = eK2 (x) = y. Nh− vậy ta đ chứng tỏ đ−ợc rằng, với bất kỳ x ∈P và y ∈C có đúng một khoá K để eK(x)=y.
7. Ký hiệu n = | K | . Giả sử P = { x i: 1 ≤ i ≤ n } và cố định một giá trị y ∈C. Ta có thể ký hiệu các khoá K1,K2,. . .,Kn sao cho eKi (x i ) = yi, 1 ≤ i ≤ n. Sử dụng định lý Bayes ta có: p (y| x ) p (x ) p (x |y) = C i P i P i p (y) C = pK(K1). (pP (x i)) pC (y) Xét điều kiện độ mật hoàn thiện p P(xi|y) = p P (x i). Điều kiện này kéo theo pK(K i) = pC (y) với 1 ≤ i ≤ n. Tức là khoá đ−ợc dùng với xác suất nh− nhau (chính bằng p C(y)). Tuy nhiên vì số khoá là | K | nên ta có p K(K) =1/ |K | với mỗi K ∈K . Ng−ợc lại, giả sử hai điều giả định đều thảo mn. Khi đó dễ dàng thấy đ−ợc hệ mật có độ mật hoàn thiện với mọi phân bố xác suất bất kỳ của bản rõ ( t−ơng tự nh− ch−ớng minh định lý 2.3). Các chi tiết dành cho bạn đọc xem xét. Mật m khoá sử dụng một lần của Vernam (One-Time-Pad:OTP) là một ví dụ quen thuộc về hệ mật có độ mật hoàn thiện. Gillbert Verman lần đầu tiên mô tả hệ mật này vào năm 1917. Hệ OTP dùng để m và giải m tự động các bản tin điện báo. Điều thú vị là trong nhiều năm OTP đ−ợc coi là một hệ mật không thể bị phá nh−ng không thể ch−ớng minh cho tới khi Shannon xây dựng đ−ợc khái niệm về độ mật hoàn thiện hơn 30 năm sau đó. Mô tả về hệ mật dùng một lần nêu trên hình 2.1. Sử dụng định lý 2.4, dễ dàng thấy rằng OTP có độ mật hoàn thiện. Hệ thống này rất hấp dẫn do dễ thực hiện m và giải m. Vernam đ đăng ký phát minh của mình với hy vọng rằng nó sẽ có ứng dụng th−ơng mại rộng ri. Đáng tiếc là có nh−ỡng những nh−ợc điểm quan trọng đối với các hệ mật an toàn không điều kiện, chẳng hạn nh− OTP. Điều kiện |K | ≥ | P | có nghĩa là l−ợng khóa (cần đ−ợc thông báo một cách bí mật) cũng lớn nh− bản rõ. Ví dụ , trong tr−ờng hợp hệ OTP, ta cần n bit khoá để m hoá n bit của bản rõ. Vấn đề này sẽ không quan trọng nếu có thể dùng cùng một khoá để m hoá các bản tin khác nhau; tuy nhiên, độ an toàn của các hệ mật an toàn không điều kiện lại phụ thuộc vào một thực tế là mỗi
8. khoá chỉ đ−ợc dùng cho một lần m. Ví dụ OTP không thể đứng vững tr−ớc tấn công chỉ với bản rõ đ biết vì ta có thể tính đ−ợc K băngf phép hoặc loại trừ xâu bít bất kỳ x và e K(x). Bởi vậy, cần phải tạo một khóa mới và thông báo nó trên một kênh bảo mật đối với mỗi bản tin tr−ớc khi gửi đi. Điều nàytạo ra khó khăn cho vấn đề quản lý khoá và gây hạn chế cho việc sử dụng rộng ri OTP. Tuy nhiên OTP vẫn đ−ợc áp dụng trong lĩnh vực quân sự và ngoại giao, ở những lĩnh vực này độ an toàn không điều kiện có tầm quan trọng rất lớn. Hình 2.1. Hệ mật sử dụng khoá một lần (OTP) n n Giả sử n ≥1 là số nguyên và P = C = K = (Z 2) . Với K (Z 2) , ta xác định e K(x) là tổng véc tơ theo modulo 2 của K và x (hay t−ơng đ−ơng với phép hoặc loại trừ của hai dy bit t−ơng ứng). Nh− vậy, nếu x = (x 1, , x n ) và K = (K 1, , K n ) thì: eK(x) = (x 1 + K 1, , x n + K n) mod 2. Phép m hoá là đồng nhất với phép giải m. Nếu y = (y 1, , y n ) thì: dK(y) = (y 1 + K 1, , y n + K n) mod 2. Lịch sử phát triển của mật m học là quá trình cố gắng tạo các hệ mật có thể dùng một khoá để tạo một xâu bản m t−ơng đối dài (tức có thể dung một khoá để m nhiều bản tin) nh−ng chí ít vẫn còn dữ đ−ợc độ an toàn tính toán. Chuẩn m dữ liệu (DES) là một hệ mật thuộc loại này (ta sẽ nghiên cứu vấn đề này trong ch−ơng 2). 2.2. ENTROPI Trong phần tr−ớc ta đ thảo luận về khái niệm độ mật hoàn thiện và đặt mối quan tâm vào một tr−ờng hợp đặc biệt, khi một khoá chỉ đ−ợc dùng cho một lần m. Bây giờ ta sẽ xét điều sẽ xẩy ra khi có nhiều bản rõ đ−ợc m bằng cùng một khoá và bằng cách nào mà thám m có thể thực hiện có kết quả phép tấn công chỉ chỉ với bản m trong thời gian đủ lớn. Công cụ cơ bản trong nghiên cứu bài toán này là khái niệm entropi. Đây là khái niệm trong lý thuyết thông tin do Shannon đ−u ra vào năm 1948. Có thể coi entropi là đại l−ợng đo thông tin hay còn gọi là độ bất định. Nó đ−ợc tính nh− một hàm phân bố xác suất.
9. Giả sử ta có một biến ngẫu nhiên X nhận các giá trị trên một tập hữu hạn theo một phân bố xác suất p(X). Thông tin thu nhận đ−ợc bởi một sự kiện xảy ra tuân theo một phân bố p(X) là gì?. T−ơng tự, nếu sự kiện còn ch−a xảy ra thì cái gì là độ bất định và kết quả?. Đại l−ợng này đ−ợc gọi là entropi của X và đ−ợc kí hiệu là H(X). Các ý t−ởng này có vẻ nh− khá trìu t−ợng, bởi vậy ta sẽ xét một ví dụ cụ thể hơn. Giả sử biến ngẫu nhiên X biểu thị phép tung đồng xu. Phân bố xác suất là: p(mặt xấp) = p(mặt ngữa) = 1/2. Có thể nói rằng, thông tin (hay entropi) của phép tung đồng xu là một bit vì ta có thể m hoá mặt xấp bằng 1 và mặt ngữa bằng 0. T−ơng tự entropi của n phép tung đồng tiền có thể m hoá bằng một xâu bít có độ dài n. Xét một ví dụ phức tạp hơn một chút. Giả sử ta có một biến ngẫu nhiên X có 3 giá trị có thể là x 1, x 2, x 3 với xác suất t−ơng ứng bằng 1/2, 1/4, 1/4. Cách m hiệu quả nhất của 3 biến cố này là m hoá x 1 là 0, m của x 2 là 10 và m của x 3 là 11. Khi đó số bít trung bình trong phép m hoá này là: 1/2 ì 1 +1/4 ì 2 + 1/4 ì 2 = 3/2. Các ví dụ trên cho thấy rằng, một biến cố xảy ra với xác suất 2 -n có thể m hoá đ−ợc bằng một xâu bít có độ dài n. Tổng quát hơn, có thể coi rằng, một biến cố xảy ra với xác suất p có thể m hoá bằng một xâu bít có độ dài xấp xỉ -log 2 p. Nếu cho tr−ớc phân bố xác suất tuỳ ý p 1, p 2,. . ., p n của biến ngẫu nhiên X, khi đó độ đo thông tin là trọng số trung bình của các l−ợng -log 2pi. Điều này dẫn tới định nghĩa hình thức hoá sau. Định nghĩa 2.3 Giả sử X là một biến ngẫu nhiên lấy các giá trị trên một tập hữu hạn theo phân bố xác suất p(X). Khi đó entropy của phân bố xác suất này đ−ợc định nghĩa là l−ợng: n H(X) = - ∑ p i log 2 pi i=1 Nếu các giá trị có thể của X là x i ,1 ≤ i ≤ n thì ta có: n H(X) = - ∑ p(X=x i )log 2 p(X= x i) i=1 Nhận xét
10. Nhận thấy rằng, log 2 pi không xác định nếu p i =0. Bởi vậy đôi khi entropy đ−ợc định nghĩa là tổng t−ơng ứng trên tất cả các xác suất khác 0. Vì lim x→0xlog 2x = 0 nên trên thực tế cũng không có trở ngại gì nếu cho p i = 0 với giá trị i nào đó. Tuy nhiên ta sẽ tuân theo giả định là khi tính entropy của một phân bố xác suất p i , tổng trên sẽ đ−ợc lấy trên các chỉ số i sao cho pi≠0. Ta cũng thấy rằng việc chọn cơ số của logarit là tuỳ ý; cơ số này không nhất thiết phải là 2. Một cơ số khác sẽ chỉ làm thay đổi giá trị của entropy đi một hằng số. Chú ý rằng, nếu p i = 1/n với 1 ≤ i ≤ n thì H(X) = log 2n. Cũng dễ dàng thấy rằng H(X) ≥ 0 và H(X) = 0 khi và chỉ khi p i = 1 với một giá trị i nào đó và p j = 0 với mọi j ≠ i. Xét entropy của các thành phần khác nhau của một hệ mật. Ta có thể coi khoá là một biến ngẫu nhiên K nhận các giá trị tuân theo phân bố xác suất p K và bởi vậy có thể tính đ−ợc H(K). T−ơng tự ta có thể tính các entropy H(P) và H(C) theo các phân bố xác suất t−ơng ứng của bản m và bản rõ. Ví dụ 2.1: (tiếp) Ta có: H(P) = -1/4log 21/4 - 3/4log 23/4 = -1/4(-2) - 3/4(log 23-2) =2 - 3/4log 23 ≈0,81 bằng các tính toán t−ơng tự, ta có H(K) = 1,5 và H(C) ≈1,85. 2.2.1. M, huffman và entropy Trong phần này ta sẽ thảo luận sơ qua về quan hệ giữa entropy và m Huffman. Vì các kết quả trong phần này không liên quan đến các ứng dụng trong mật m của entropy nên ta có thể bỏ qua mà không làm mất tính liên tục. Tuy nhiên các hệ quả ở đây có thể dùng để nghiên cứu sâu hơn về khái niệm entropy. ở trên đ đ−a ra entropy trong bối cảnh m hoá các biến cố ngẫu nhiên xảy ra theo một phân bố xác suất đ định. Tr−ớc tiên ta chính xác hoá thêm những ý t−ởng này. Cũng nh− trên, coi X là biến ngẫu nhiên nhận các giá trị trên một tập hữu hạn và p(X) là phân bố xác suất t−ơng ứng. Một phép m hoá X là một ánh xạ bất kỳ: f:X →{0,1} *
11. trong đó {0,1} * kí hiệu tập tất cả các xâu hữu hạn các số 0 và 1. Với một danh sách hữu hạn (hoặc một xâu) các biến cố x 1, x 2, . . . , x n, ta có thể mở rộng phép m hoá f nhờ sử dụng định nghĩa sau: f(x 1x2 x n ) = f(x 1)   f(x n) trong đó kí hiệu phép ghép. Khi đó có thể coi f là ánh xạ: f:X * →{0,1} * Bây giờ giả sử xâu x 1 x n đ−ợc tạo từ một nguồn không nhớ sao cho mỗi x i xảy ra đều tuân theo phân bố xác suất trên X. Điều đó nghĩa là xác suất của một xâu bất kì x 1 x n đ−ợc tính bằng p(x 1) ì ì p(x n) (Để ý rằng xâu này không nhất thiết phải gồm các giá trị phân biệt vì nguồn là không nhớ). Ta có thể coi dy n phép tung đồng xu là một ví dụ. Bây giờ giả sử ta chuẩn bị dùng ánh xạ f để m hoá các xâu. Điều quan trọng ở đây là giải m đ−ợc theo một cách duy nhất. Bởi vậy phép m f nhất thiết phải là một đơn ánh. Ví dụ 2.2. Giả sử X = {a,b,c,d} , xét 3 phép m hoá sau: f(a) = 1 f(b) = 10 f(c) = 100 f(d) = 1000 g(a) = 0 g(b) = 10 g(c) = 110 g(d) = 111 h(a) = 0 h(b) = 01 h(c) = 10 h(d) = 11 Có thể thấy rằng, f và g là các phép m đơn ánh, còn h không phải là một đơn ánh. Một phép m hoá bất kỳ dùng f có thể đ−ợc giải m bằng cách bắt đầu ở điểm cuối và giải m ng−ợc trở lại: Mỗi lần gặp số một ta sẽ biết vị trí kết thúc của phần tử hiện thời. Phép m dùng g có thể đ−ợc giải m bằng cách bắt đầu ở điểm đầu và xử lý liên tiếp. Tại thời điểm bất kì mà ở đó có một dy con là các kí tự m của a ,b,c hoặc d thì có thể giải m nó và có thể cắt ra khỏi dy con. Ví dụ, với xâu10101110, ta sẽ giải m 10 là b, tiếp theo 10 là b, rồi đến 111 là d và cuối cùng 0 là a. Bởi vậy xâu đ giải m là bbda. Để thấy rằng h không phải là một đơn ánh, chỉ cần xét ví dụ sau: h(ac) = h(bc) = 010 Theo quan điểm dễ dàng giải m, phép m g tốt hơn f. Sở dĩ nh− vậy vì nếu dùng g thì việc giải m có thể đ−ợc làm liên tiếp từ đầu đến cuối và bởi vậy không cần phải có bộ nhớ. Tính chất cho phép giải m liên tiếp đơn giản của g đ−ợc gọi là tính chất tiền tố độclập ( một phép m g đ−ợc gọi là có tiền
12. tố độc lập nếu không tồn tại 2 phần tử x,y ∈ X và một xâu z ∈{0,1} * sao cho g(x) = g(y)  z). Thảo luận ở trên không liên hệ gì đến entropy. Tuy nhiên không có gì đáng ngạc nhiên khi entropy lại có liên quan đến tính hiệu quả của phép m. Ta sẽ đo tính hiệu quả của phép m f nh− đ làm ở trên: đó là độ dài trung bình trọng số ( đ−ợc kí hiệu là l (f) ) của phép m một phần tử của X. Bởi vậy ta có định nghĩa sau: l( f ) = ∑ p(x |) f (x |) x∈X Trong đó |y| kí hiệu là độ dài của xâu y. Bây giờ nhiệm vụ chủ yếu của ta là phải tìm một phép m hoá đơn ánh sao cho tối thiểu hoá đ−ợc l(f) . Thuật toán Huffman là một thuật toán nổi tiếng thực hiện đ−ợc mục đích này. Hơn nữa, phép m f tạo bởi thuật toán Huffman là một phép m có tiền tố độc lập và H(X) ≤ l(f) ≤ H(X) +1 Nh− vậy, giá trị của entropy cho ta đánh giá khá chính xác về độ dài trung bình của một phép m đơn ánh tối −u. Ta sẽ không chứng minh các kết quả đ nêu mà chỉ đ−a ra một mô tả ngắn gọn hình thức hoá về thuật toán Huffman. Thuật toán Huffman bắt đầu với phân bố xác suất trên tập X và m mỗi phần tử ban đầu là trống. Trong mỗi b−ớc lặp, 2 phần tử có xác suất thấp nhất sẽ đ−ợc kết hợp thành một phần tử có xác suất bằng tổng của hai xác suất này. Trong 2 phần tử, phần tử có xác suất nhỏ hơn sẽ đ−ợc gán giá trị "0", phần tử có giá trị lớn hơn sẽ đ−ợc gán giá trị "1". Khi chỉ còn lại một phần tử thì m của x ∈ X sẽ đ−ợc cấu trúc bằng dy các phần tử ng−ợc từ phần tử cuối cùng tới phần tử ban đầu x. Ta sẽ minh hoạ thuật toán này qua ví dụ sau. Ví dụ 2.3. Giả sử X = {a,b,c,d,e} có phân bố xác suất: p(a) = 0,05; p(b) = 0,10; p(c) = 0,12; p(d) = 0,13 và p(e) = 0,60. Thuật toán Huffman đ−ợc thực hiện nh− trong bảng sau:
13. A B c d e 0,05 0,10 0,12 0,13 0,60 0 1 0,15 0,12 0,13 0,60 0 1 0,15 0,25 0.60 0 1 0,40 0,60 0 1 1,0 Điều này dẫn đến phép m hoá sau: x f(x) a 000 b 001 c 010 d 011 e 1 Bởi vậy độ dài trung bình của phép m hoá là: l(f) = 0,05 ì 3 + 0,10 ì 3 + 0,12 ì 3 + 0,13 ì 3 + 0,60 ì 1 = 1,8 So sánh giá trị này với entropy: H(X) = 0,2161 + 0,3322 + 0,3671 + 0,3842 + 0,4422 = 1,7402. 2.3. Các tính chất của entropi Trong phần này sẽ chứng minh một số kết quả quan trọng liên quan đến entropi. Tr−ớc tiên ta sẽ phát biểu bất đẳng thức Jensen. Đây là
14. một kết quả cơ bản và rất hữu ích. Bất đẳng thức Jensen có liên quan đến hàm lồi có định nghĩa nh− sau. Định nghĩa 2.4. Một hàm có giá trị thực f là lồi trên khoảng I nếu:  x + y  f (x) + f (y) f   ≥  2  2 với mọi x,y ∈I. f là hàm lồi thực sự trên khoảng I nếu:  x + y  f (x) + f (y) f   >  2  2 với mọi x,y ∈ I,x ≠ y. Sau đây ta sẽ phát biểu mà không chứng minh bất đẳng thức Jensen. Định lý 2.5.(Bất đẳng thức Jensen). Giả sử h là một hàm lồi thực sự và liên tục trên khoảng l, n ∑ai = 1 i=1 và a i >0,1 ≤ i ≤ n. Khi đó: n n ∑ ai f (xi ) ≤ f (∑ ai xi ) i=1 i=1 trong đó x i ∈ I,1 ≤ i ≤ n. Ngoài ra dấu "=" chỉ xảy ra khi và chỉ khi x1=. . . = xn. Bây giờ ta sẽ đ−a ra một số kết quả về entropi. Trong định lý sau sẽ sử dụng khẳng định: hàm log 2x là một hàm lồi thực sự trong khoảng (0, ∞) (Điều này dễ dàng thấy đ−ợc từ những tính toán sơ cấp vì đạo hàm cấp 2 của hàm logarith là âm trên khoảng (0, ∞)). Định lý 2.6. Giả sử X là biến ngẫu nhiên có phân bố xác suất p 1, p 2, , p n, trong đó p i >0,1 ≤ i ≤ n. Khi đó H(X) ≤ log 2n. Dờu "=" chỉ xảy ra khi và chỉ khi p i = 1/n, 1 ≤ i ≤ n. Chứng minh: áp dụng bất đẳng thức Jensen, ta có: = logn 2n n H (X ) = −∑ pi log 2 pi = ∑ pi log 2 /1( pi ) i=1 i=1 n ≤ log 2 ∑( pi ì /1 pi ) i=1
15. Ngoài ra, dấu "=" chỉ xảy ra khi và chỉ khi p i = 1/n, 1 ≤ i ≤ n. Định lý 2.7. H(X,Y) ≤ H(X) +H(Y) Đẳng thức (dấu "=") chỉ xảy ra khi và chỉ khi X và Y là các biến cố độc lập Chứng minh. Giả sử X nhận các giá trị x i,1 ≤ i ≤ m;Y nhận các giá trị y j,1 ≤ j ≤ n. Kí hiệu: p i = p(X= x i), 1 ≤ i ≤ m và q j = p(Y = y j ), 1 ≤ j ≤ n. Kí hiệu ri j = p(X = x i ,Y = y j ), 1 ≤ i ≤ m, 1 ≤ j ≤ n. (Đây là phân bố xác suất hợp). Nhận thấy rằng n pi = ∑rij j =1 (1 ≤ i ≤ m) và m q j = ∑rij i=1 (1 ≤ j ≤ n). Ta có m n H(X ) + H (Y) = −(∑pi log 2 pi + ∑q j log 2 q j ) i=1j = 1 m n n m = −(∑∑rij log 2 pi + ∑∑rij log 2 q j ) i=1j = 1j = 1i = 1 m n = −∑∑rij log 2 piq j i=1j = 1 Mặt khác m n H(X ,Y ) = −∑∑rij log 2 rij i=1j = 1 Kết hợp lại ta thu đ−ợc kết quả sau: m n m n H(X ,Y ) − H(X ) − H(Y ) = ∑∑rij log 2 /1( rij ) + ∑∑rij log 2 piq j i=1j = 1i = 1j = 1
16. (ở đây đ áp dụng bất đẳng thức Jensen khi biết rằng các r jj tạo nên một phân bố xác suất ). m n = ∑∑rij log 2 ( piq j / rij ) i=1j = 1 m n = log 2 ∑∑ piq j i=1j = 1 = log 2 1 = 0 Khi đẳng thức xảy ra, có thể thấy rằng phải có một hằng số c sao cho p jj / r jj = c với mọi i,j. Sử dụng đẳng thức sau: n m n m ∑∑rij = ∑∑ piq j = 1 j=1i = 1j = 1i = 1 Điều này dẫn đến c=1. Bởi vậy đâửng thức (dấu "=") sẽ xảy ra khi và chỉ khi r jj = p jqj, nghĩa là: p(X = x j, Y = y j ) = p(X = x j )p(Y = y j ) với 1 ≤ i ≤ m, 1 ≤ j ≤ n. Điều này có nghĩa là X và Y độc lập. Tiếp theo ta sẽ đ−a ra khái niệm entropi có điều kiện Định nghĩa 2.5. Giả sử X và Y là hai biến ngẫu nhiên. Khi đó với giá trị xác định bất kỳ y của Y, ta có một phân bố xác suất có điều kiện p(X|y). Rõ ràng là : H (X | y) = −∑ p(x | y)log 2 p(x | y) x Ta định nghĩa entropi có điều kiện H(X|Y) là trung bình trọng số (ứng với các xác suất p(y) của entropi H(X|y) trên mọi giá trị có thể y. H(X|y) đ−ợc tính bằng: H (X | Y ) = −∑ ∑ p(y) p(x | y)log 2 p(x | y) y x Entropi có điều kiện đo l−ợng thông tin trung bình về X do Y mang lại. Sau đây là hai kết quả trực tiếp ( Bạn đọc có thể tự chứng minh)
17. Định lý 2.8. H(X,Y) = H(Y) + H(X | Y) Hệ quả 2.9. H(X |Y) ≤ H(X) Dấu bằng chỉ xảy ra khi và chỉ khi X và Y độc lập. 2.4. Các khoá giả và khoảng duy nhất Trong phần này chúng ta sẽ áp dụng các kết quả về entropi ở trên cho các hệ mật. Tr−ớc tiên sẽ chỉ ra một quan hệ cơ bản giữa các entropi của các thành phần trong hệ mật. Entropi có điều kiện H(K|C) đ−ợc gọi là độ bất định về khoá. Nó cho ta biết về l−ợng thông tin về khoá thu đ−ợc từ bản m. Định lý 2.10. Giả sử( P, C, K, E, D) là một hệ mật. Khi đó: H(K|C) = H(K) + H(P) - H(C) Chứng minh: Tr−ớc tiên ta thấy rằng H(K,P,C) = H(C | K,P) + H(K,P). Do y = e K(x) nên khoá và bản rõ sẽ xác định bản m duy nhất. Điều này có nghĩa là H(C|K,C) = 0. Bởi vậy H(K,P,C) = H(K,P). Nh−ng K và P độc lập nên H(K,P) = H(K) + H(P). Vì thế: H(K,P,C) + H(K,P) = H(K) + H(P) T−ơng tự vì khoá và bản m xác định duy nhất bản rõ (tức x = d K(y)) nên ta có H(P | K,C) = 0 và bởi vậy H(K,P,C) = H(K,P). Bây giờ ta sẽ tính nh− sau: H(K | C) = H(K,C) - H(C) = H(K,P,C) - H(C) = H(K) + H(P) - H(C) Đây là nội dung của định lý. Ta sẽ quay lại ví dụ 2.1 để minh hoạ kết quả này. Ví dụ 2.1 (tiếp) Ta đ tính đ−ợc H(P) ≈ 0,81, H(K) = 1,5 và H(C) ≈1,85. Theo định lý 2.10 ta có H(K | C) ≈ 1,5 + 0,85 - 1,85 ≈ 0,46. Có thể kiểm tra lại kết quả này bằng cách áp dụng định nghĩa về entropi có điều kiện nh− sau. Tr−ớc tiên cần phải tính các xác suất xuất p(K j | j), 1 ≤ i ≤ 3, 1 ≤ j ≤ 4. Để thực hiện điều này có thể áp dụng định lý Bayes và nhận đ−ợc kết quả nh− sau:
18. P(K 1 | 1) = 1 p(K 2 | 1) = 0 p(K 3 | 1) = 0 ` P(K 1 | 2) = 6/7 p(K 2 | 2) = 1/7 p(K 3 | 2) = 0 P(K 1 | 3) = 0 p(K 2 | 3) = 3/4 p(K 3 | 3) = 1/4 P(K 1 | 4) = 0 p(K 2 | 4) = 0 p(K 3 | 4) = 1 Bây giờ ta tính: H(K | C) = 1/8 ì 0 +7/16 ì 0,59 + 1/4 ì 0,81 + 3/16 ì 0 = 0,46 Giá trị này bằng giá trị đ−ợc tính theo định lý 2.10. Giả sử ( P, C , K , E , D ) là hệ mật đang đ−ợc sử dụng. Một xâu của bản rõ x 1x2 . . .x n sẽ đ−ợc m hoá bằng một khoá để tạo ra bản m y 1y2 . . .y n. Nhớ lại rằng, mục đích cơ bản của thám m là phải xác định đ−ợc khoá. Ta xem xét các ph−ơng pháp tấn công chỉ với bản m và coi Oscar có khả năng tính toán vô hạn. Ta cũng giả sử Oscar biết bản rõ là một văn bản theo ngôn ngữ tự nhiên (chẳng hạn văn bản tiếng Anh). Nói chung Oscar có khả năng rút ra một số khoá nhất định ( các khoá có thể hay các khoá chấp nhận đ−ợc) nh−ng trong đó chỉ có một khoá đúng, các khoá có thể còn lại (các khoá không đúng) đ−ợc gọi là các khoá giả. Ví dụ, giả sử Oscar thu đ−ợc một xâu bản m WNAJW m bằng ph−ơng pháp m dịch vòng. Dễ dàng thấy rằng, chỉ có hai xâu bản rõ có ý nghĩa là river và arena t−ơng ứng với các khoá F( = 5) và W( = 22). Trong hai khoá này chỉ có một khoá đúng, khoá còn lại là khoá giả. (Trên thực tế, việc tìm một bản m của MDV có độ dài 5 và 2 bản giải m có nghĩa không phải quá khó khăn, bạn đọc có thể tìm ra nhiều ví dụ khác). Mục đích của ta là phải tìm ra giới hạn cho số trung bình các khoá giả. Tr−ớc tiên, phải xác định giá trị này theo entropi (cho một kí tự) của một ngôn ngữ tự nhiên L ( kí hiệu là H L ). H L là l−ợng thông tin trung bình trên một kí tự trong một xâu có nghĩa của bản rõ. (Chú ý rằng, một xâu ngẫu nhiên các kí tự của bảng chữ cái sẽ có entropi trên một kí tự bằng log 2 26 ≈ 4,76). Ta có thể lấy H(P) là xấp xỉ bậc nhất cho H L. Trong tr−ờng hợp L là Anh ngữ, sử dụng phân bố xác suất trên bảng 1.1, ta tính đ−ợc H(P) ≈ 4,19. Dĩ nhiên các kí tự liên tiếp trong một ngôn ngữ không độc lập với nhau và sự t−ơng quan giữa các kí tự liên tiếp sẽ làm giảm entropi. Ví dụ, trong Anh ngữ, chữ Q luôn kéo theo sau là chữ U. Để làm xấp xỉ bậc hai, tính entropi của phân bố xác suất của tất cả các bộ đôi rồi chia cho 2. Một cách tông quát, ta định nghĩa P n là biến ngẫu nhiên có phân bố xác suất của tất cả các bộ n của bản rõ. Ta sẽ sử dụng tất cả các định nghĩa sau:
19. Định nghĩa 2.6 Giả sử L là một ngôn ngữ tự nhiên. Entropi của L đ−ợc xác định là l−ợng sau: H (Pn ) H = L lim n→∞ n Độ d− của L là: RL =l - (H L / log 2 | P | ) Nhận xét : H L đo entropi trên mỗi kí tự của ngôn ngữ L. Một ngôn ngữ ngẫu nhiên sẽ có entropi là log 2 | P | . Bởi vậy đại l−ợng R L đo phần "kí tự v−ợt trội" là phần d−. Trong tr−ờng hợp Anh ngữ, dựa trên bảng chứa một số lớn các bộ đôi và các tần số, ta có thể tính đ−ợc H(P 2). Ước l−ợng theo cách này, ta tính đ−ợc H(P 2) ≈3,90. Cứ tiếp tục nh− vậy bằng cách lập bảng các bộ ba .v.v ta thu đ−ợc −ớc l−ợng cho H L. Trên thực tế, bằng nhiều thực nghiệm khác nhau, ta có thể đi tới kết quả sau 1,0 ≤ H L ≤1,5. Tức là l−ợng thông tin trung bình trong tiếng Anh vào khoảng 1 bít tới 1,5 bít trên mỗi kí tự!. Giả sử lấy 1,25 là giá trị −ớc l−ợng của giá trị của H L. Khi đó độ d− vào khoảng 0,75. Tức là tiếng Anh có độ d− vào khoảng 75%! (Điều này không có nghĩa loại bỏ tuỳ ý 3 trên 4 kíb tự của một văn bản tiếng Anh mà vẫn có khả năng đọc đ−ợc nó. Nó chỉ có nghĩa là tìm đ−ợc một phép m Huffman cho các bộ n với n đủ lớn, phép m này sẽ nén văn bản tiếng Anh xuống còn 1/4 độ dài của bản gốc). Với các phân bố xác suất đ cho trên K và Pn. Có thể xác định phân bố xác suất trên Cn là tập các bộ n của bản m. (Ta đ làm điều này trong tr−ờng hợp n =1). Ta đ xác định P n là biến ngẫu nhiên biểu diễn bộ n của bản rõ. T−ơng tự C n là biến ngẫu nhiên biểu thị bộ n của bản m. Với y ∈ C n, định nghĩa: n K(y) = { K ∈ K: ∃ x ∈ P , p Pn(x) > 0, e K(x) =y} nghĩa là K(y) là tập các khoá K sao cho y là bản m của một xâu bản rõ độ dài n có nghĩa, tức là tập các khoá "có thể" với y là bản m đ cho. Nếu y là dy quan sát đ−ợc của bản m thì số khoá giả sẽ là | K(y) | -1 vì chỉ có một khoá là khoá đúng trong số các khoá có thể. Số trung bình các khoá giả (trên tất cả các xâu bản m có thể độ dài n) đ−ợc kí hiệu là s n và nó đ−ợc tính nh− sau:
20. sn = p(y (|) K(y |) − )1 ∑ y∈C n = p(y |) K(y |) − p(y) ∑y∈C n ∑ y ∈ C n = p(y |) K(y |) −1 ∑ y∈C n Từ định lý 2.10 ta có: H(K| C n) =H(K) + H(P n) - H(C n). Có thể dùng −ớc l−ợng sau: n H(P ) ≈ nH L =n(1 - R L)log 2| P | với điều kiện n đủ lớn. Hiển nhiên là: n H(C ) ≤ nlog 2| C |. Khi đó nếu | P | = | C | thì: n H(K| C ) ≥ H(K) - nR Llog 2 | P | (2.1) n Tiếp theo xét quan hệ của l−ợng H(K | C ) với số khoá giả s n. Ta có: H(K | C n ) = p(y)H (K | y) ∑ y∈C n ≤ p(y)log | K(y |) ∑ y∈C n 2 ≤ log p(y |) K(y |) 2 ∑ y∈C n = log 2 (sn + )1 ở đây ta áp dụng bất đâửng thức Jensen (định lý 2.5) với f(x) = log 2x. Bởi vậy ta có bất đẳng thức sau: n H (K | C ) ≤ log 2 (sn + )1 (2.2) Kết hợp hai bất đẳng thức (2.1) và (2.2), ta có : log 2 (sn + )1 ≥ H (K) − nR L log 2 | P | Trong tr−ờng hợp các khoá đ−ợc chọn đồng xác suất (Khi đó H(K) có giá trị lớn nhất) ta có kết quả sau. Định lý 2.11 Giả sử ( P, C, K, E, D ) là một hệ mật trong đó | C | = | P | và các khoá đ−ợc chọn đồng xác suất. Giả sử R L là độ d− của ngôn ngữ gốc. Khi đó với một
21. xâu bản mG độ dài n cho tr−ớc ( n là số đủ lớn), số trung bình các khoá giả sn thoả mGn bất đẳng thức nh− sau: sn ≥ {| K | /(| P | nR L )} −1 L−ợng |K| / |P|nR L-1 tiến tới 0 theo hàm mũ khi n tăng. Ước l−ợng này có thể không chính xác với các giá trị n nhỏ. Đó là do H(P n)/ n không phải là một −ớc l−ợng tốt cho H L nếu n nhỏ. Ta đ−a ra đây một khái niệm nữa Định nghĩa 2.7. Khoảng duy nhất của một hệ mật đ−ợc định nghĩa là giá trị 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à n 0). Điều đó có nghĩa là n 0 là độ dài trung bình cần thiết của bản mG để thám mG có thể tính toán khoá một cách duy nhất với thời gian đủ lớn. Nếu đặt s n =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 ≈ log 2|K| / R L log 2 | P| Ví dụ với MTT, ta có | P| = 26 và | K| =26 !. Nếu lấy R L =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ử S 1= ( P, P, K 1, E 1, D 1) và S2= ( P, P, K 2, E 2, D 2) 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 S 1 và S 2 (kí hiệu là S 1 ì S 2) đ−ợc xác định là hệ mật sau: (P, P, K 1 ì K 2, E, D )
22. Khoá của hệ mật tích có dạng K = (K 1,K 2) trong đó K 1 ∈ K1 và K 2 ∈ 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 E K xác định theo công thức: e (x) = e (e (x)) (K1 ,K 2 ) K 2 K1 và quy tắc giải m: d (y) = d (d (y)) (K1 ,K 2 ) K1 K 2 Nghĩa là tr−ớc tiên ta m hoá x bằng e K1 rồi m lại bản kết quả bằng e K2 . Quá trình giải m t−ơng tự nh−ng thực hiện theo thứ tự ng−ợc lại: d (e (x) = d (e (e (x))) (K1 ,K 2 ) (K1 ,K 2 ) (K1 ,K 2 ) K 2 K1 = d (d (e (e (x))) K1 K 2 K 2 K1 = d (e (x))) K1 K1 = x. 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(K 1,K 2)= p K1 (K 1) ì p K2 =(K 2) Nói một cách khác, ta chọn K 1 có phân bố p K1 rồi chọn một cách độc lập K 2 có phân bố p K2 (K 2). 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 = Z 26 và giả sử: K = {a Z 26 : UCLN(a,26) = 1} Với a ∈ K, ta xác định: e a(x) = ax mod 26 -1 và d a(y) = a y mod 26 (x,y) ∈ Z 26 . 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).
23. 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à e K(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à e a(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 = -1 K1 khi và chỉ khi K = a K1, ( hy 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, K 1) của hệ m Affine t−ơng -1 đ−ơng với khoá (a K1,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: (S 1 ì S 2) ì S 3 = S 1 ì (S 2 ì S 3) 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à S 2). Nếu lấy tích n lần thì hệ mật kết quả là S n. Ta gọi Sn là hệ mật lặp. Một hệ mật S đ−ợc gọi là luỹ đẳng nếu S 2 = 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 S 2 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à
24. 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 S 1 và S 2 là luỹ đẳng và giao hoán thì S 1 và S 2 cũng là luỹ đẳng. Điều này rút ra từ các phép toán đại số sau: (S 1 ì S 2) ì(S 1 ì S 2) = S 1 ì (S 2 ì S 1) ì S 2 =S 1 ì (S 1 ì S 2) ì S 2 =(S 1 ì S 1) ì (S 2 ì S 2) = S 1 ì S 2. ( Chú ý dùng tính chất kết hợp trong chứng minh trên) Bởi vậy, nếu cả S 1 và S 2 đều là luỹ đẳng và ta muốn S 1 ì S 2 là không luỹ đẳng thì điều kiện cần là S 1 và S 2 không giao hoán. Rất may mắn là nhiều hệ mật đơn giản thoả mn đ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. 2.5. 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:
25. 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á e i đ−ợc xác định là e i(j) = L(i,j). Do đó mỗi hàng của L sẽ cho một quy tắc m hoá). Hy chứng minh rằng, hệ mật hình vuông Latin này có độ mật hoàn thiện. 2.2. Hy 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 p 0 nào đó của bản rõ. Hy 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. Hy 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 đó 2 k ≤ n ≤ 2 k+1 và p(x) =1/n với mọi x ∈X. a/ Hy 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 - 2 k+1 /n Chỉ dẫn: Hy m hoá 2 k+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/ Hy 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. Hy 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. Hy 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 = {K 1,K 2,K 3} và C = {1,2,3,4}. Giả sử ma trận m hoá nh− sau:
26. 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à p P(a) = 1/2, p P(b) = 1/3, p P(c) = 1/6. Hy tính H(P), H(C), H(K), H(K|C) và H(P|C). 2.11. Hy 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. Hy chứng tỏ khoảng duy nhất là 1/R L, trong đó R L là độ d− của ngôn ngữ đang xét. (kết quả này đ−ợc hiểu nh− sau: Nếu n 0 là số kí tự cần m hoá thì độ dài của bản rõ là n 0/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/R L ứng với một bản rõ gồm m/R L kí tự). 2.13. Hy 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/R L ( hy chú ý rằng số kí tự trong môt bản rõ có độ dài 2 là m /R L). 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: n ≈ 2πn(n / e)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ả 26 m các bộ m. Hy đánh giá khoảng duy nhất của MTT bộ m nếu R L = 0,75. 2.15. Hy chứng minh rằng MDV là luỹ đẳng. 2.16. Giả sử S 1 là MDV ( với các khoá đồng xác suất) và S 2 là MDV trong đó các khoá đ−ợc chọn theo một phân bố xác suất p K nào đó ( không đồng xác suất). Hy chứng tỏ rằng S 1ìS2 = S 1. 2.17. Giả sử S 1 và S 2 là các hệ m Vigenère có độ dài từ khoá t−ơng ứng là m1 và m 2 trong đó m 1 ≥ m 2. a/ Nếu m 1 | m 2 thì chỉ ra rằng S 1 ì S 2 = S 1. b/ Ta thử tổng quát hoá kết quả trên bằng giả định rằng S 2ìS1 = S 3, S 3 là hệ m Vigenère có độ dài từ khoá là BCNN(m 1,m 2) ( BCNN - bội chung nhỏ nhất). Hy chứng tỏ rằng giả định này là không đúng. Chỉ dẫn: Nếu m 1 ≠0 mod m 2 thì số các khoá trong hệ m tích S 1ìS 2 nhỏ hơn số khoá trong S 3.