Mật mã cổ điển- Chương 2

Tham khảo tài liệu mật mã cổ điển- chương 2, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Mật mã cổ điển- Chương 2 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 TechnicalJournal. Bài báo đã có ảnh hưởng lớn đến việc nghiên cứu khoa học mậtmã. Trong chương này ta sẽ thảo luận một vài ý tưởng trong lý thuyết củaShannan.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ậttoá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ể đượcchứ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 độ antoà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ánnà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ứngminh được. Tuy nhiên cần phải hiểu rằng, quan điểm này chỉ cung cấpmộ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àycũ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áncủ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 đượcphép thực 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ểutấn công đang được xem xét. Trong chương 1 đã cho thấy rằng, khôngmộ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ớibả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 antoàn vô điều kiện chỉ khi mỗi pkần tử của bản rõ được mã hoá bằng mộtkhoá 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ínhtoán cho phép không hạn chế. ở đây lý thuyết xác suất là nền tảng thíchhợp để nghiên cứu về độ an toàn không điều kiện. Tuy nhiên ta chỉ cầnmột số kiến thức sơ đẳng trong xác suất; các định nghĩa chính sẽ đượcnê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ậngiá 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ếnngẫ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 đượcbiể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)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ộtbả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ệuxá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 địnhnào đó. ( Thông thường khoá được chọn ngẫu nhiên, bởi vậy tất cả cáckhoá 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 đượcchọ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ấttrê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ácsuấ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ệnbản rõ là x): pC (y | x ) = ∑ pK(K) {K:x= dK(y)} Bây giờ ta có thể tính được xác suất có điều kiện pP (x | y ) ( tứcxá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= dK(y)} pP(y | x ) = ∑ pK(K) pP(dK (y))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ácsuất. Sau đây sẽ trình bày một ví dụ đơn giản để minh hoạ ...