Chapter 2 - LÝ THUYẾT SHANNON

- Lý thuyết thông tin trong các hệ mật".
- Có hai quan điểm cơ bản về độ an toàn của một hệ mật..
- Vấn đề là ở chỗ, không có một hệ mật thực tế đã.
- Các hệ mật loại này đôi khi gọi là ".
- Một hệ mật đợc gọi là an toàn không.
- đề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!..
- ở đâ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..
- 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.
- 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à p P (x).
- 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 đó.
- Kí hiệu xác suất để khóa K đợc chọn là p K (K).
- 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 p P (y) với y là bản mã đợc gửi đi.
- 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 p C (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):.
- Bây giờ ta có thể tính đợc xác suất có điều kiện p P (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.
- 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..
- a b K 1 1 2 K 2 2 3 K 3 2 4 Tính phân bố xác suất p C ta có:.
- 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ó.
- ý 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:.
- Một hệ mật có độ mật hoàn thiện nếu p P (x | y.
- 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 mã y là đồng nhất với xác suất tiên nghiệm để bản rõ là x..
- Định lý 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..
- 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õ..
- 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 Z 26 và p P là một phân bố xác suất.
- Trong một hệ mật bất kỳ ta phải có | C.
- ta có.
- Giả sử ( P , C, K, E, D ) là một hệ mật , trong đó | K.
- 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.
- Giả sử hệ mật đã cho có độ mật hoàn thiện.
- Giả sử P.
- Tức là khoá đợc dùng với xác suất nh nhau (chính bằng p C (y.
- 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).
- Hệ mật sử dụng khoá một lần (OTP).
- Nó đợc tính nh một hàm phân bố xác suất..
- 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).
- Phân bố xác suất là: p(mặt xấp.
- 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 .
- 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.
- 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:.
- 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.
- 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 p i ≠ 0.
- 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õ..
- Ta có: H(P.
- ở 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.
- 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..
- 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 ) ì.
- 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 2 phần tử, phần tử có xác suất nhỏ hơn sẽ đợc gán giá trị.
- Giả sử X = {a,b,c,d,e} có phân bố xác suất: p(a.
- Giả sử X là biến ngẫu nhiên có phân bố xác suất p 1 , p 2.
- tạo nên một phân bố xác suất.
- 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).
- trị có thể y.
- Giả sử( P , C , K , E , D ) là một hệ mật.
- Trớc tiên cần phải tính các xác suất xuất p(K j | j), 1.
- Giả sử ( P , C , K , E , D ) là hệ mật đang đợc sử dụng.
- 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.
- Để 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ộ.
- 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õ.
- Với các phân bố xác suất đã cho trên K và P n .
- Có thể xác định phân bố xác suất trên C n là tập các bộ n của bản mã.
- Ta có:.
- Trong trờng hợp các khoá đợc chọn đồng xác suất (Khi đó H(K) có giá.
- Giả sử ( P, C, K, E, D ) là một hệ mật trong đó | C.
- đợc chọn đồng xác suất.
- Các hệ mật mã tích.
- Giả sử S 1.
- Khoá của hệ mật tích có dạng K = (K 1 ,K 2 ) trong đó K 1 ∈ K 1 và K 2 ∈ K 2 .
- 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.
- Giả sử định nghĩa hệ mật mã nhân nh trong hình 2.2 sau..
- Hơn nữa, xác suất của một khoá trong hệ mã Affine là ì 1/26.
- tích của xác suất tơng ứng của các khoá a và K.
- 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..
- Bởi vậy, hai hệ mật là giao hoán.
- Ta gọi S n là hệ mật lặp..
- Một hệ mật S đợc gọi là luỹ đẳng nếu S 2 = S.
- Giả sử P = C = K.
- Hãy chứng minh rằng, hệ mật hình vuông Latin này có độ mật hoàn thiện..
- 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õ.
- 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õ..
- Hãy chứng tỏ rằng nếu một hệ mật có độ mật hoàn thiên và |K| .
- |P| thì mọi bản mã là đồng xác suất..
- Giả sử X = {a,b,c,d,e} có phân bố xác suất nh sau: p(a.
- Chứng minh rằng, một hệ mật có độ mật hoàn thiện khi và chỉ khi H(P|C.
- Chứng minh rằng trong một hệ mật bất kỳ H(K|C.
- Xét một hệ mật trông đó P = {a,b,c}, K = {K 1 ,K 2 ,K 3 } và C .
- 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

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt