Giáo trình Mật mã học (Phần 2)

CSDL Máy chủ xác thực (AS) Máy chủ cấp thẻ (TGS) Cơ sở dữ liệu (3) Trạm làm việc nhắc nhở ng−ời dùng đ−a vào mật khẩu để giải mã thông tin tới rồi gửi thẻ và chứng chỉ xác thực có chứa tên ng−ời sử dụng, địa chỉ mạng và thời gian tới TGS Một lần với mỗi phiên đăng nhập Server (2) AS kiểm tra quyền truy nhập của ng−ời sử dụng trong CSDL tạo thẻ cấp thẻ và khóa phiên Yêu cầu thẻ cấp thẻ Thẻ và khóa phiên Thẻ và khóa phiên Yêu cầu thẻ cấp dịch vụ Một lần với mỗi loại dịch vụ Kết quả là một khóa sử dụng đ−ợc mã phát sinh từ mật khẩu của ng−ời dùng. (2) TGS giải mã thẻ và chứng chỉ xác thực, kiểm tra yêu cầu rồi tạo thẻ cho máy chủ đ−ợc yêu cầu Một lần với mỗi phiên dịch vụ (6) Máy chủ kiểm tra sự phù hợp của thẻ và chứng chỉ xác thực rồi cấp quyền truy nhập vào dịch vụ. Nếu có yêu cầu xác thực lẫn nhau máy chủ sẽ gửi một chứng chỉ xác thực (5) Trạm làm việc gửi thẻ và chứng chỉ xác thực tới máy chủ Yêu cầu dịch vụCung cấp thẻ xác thực m áy chủ Kerberos Hình 6.4: Tóm l−ợc các trao đổi thông báo của Kv.4. a) Trao đổi dịch vụ xác thực: Để thu nhận thẻ cấp thẻ (1) C → AS : IDC//IDtgs//TS1 (Nhabx thời gian). (2) AS → C: EKc [KC, tgs // IDtgs // TS2 // LT2 (thời gian sống) // Thẻ tgs] Thẻ tgs = EKtgs [KC, tgs // IDC // ADC // IDtgs // TS2 // LT2 ] Giáo trình Mật mã học 282 b) Trao đổi dịch vụ cấp thẻ: Để thu nhận thẻ cung cấp dịch vụ (3) C → TGS : IDV Thẻ tgs // Authenticator C. (IDV : ID của dịch vụ yêu cầu) (4) TGS → C : EK,tgs [KC, V // IDV // TS2 // Thẻ V] Thẻ tgs = EKtgs [KC, tgs // IDC // ADC // IDtgs // TS2 // LT2 ] ThẻV = EKv [KC, v // IDC // ADC // IDV // TS2 // LT4 ] Authenticator C = EK,tgs [IDC // ADC // TS 3] c) Trao đổi xác thực Máy trạm/ máy chủ: Để thu nhận dịch vụ (5) C → V : Thẻ V // Authenticator C. (6) V → C : EKc,v [TS5 H] (để xác thực lẫn nhau) ThẻV = EKv [KC, v // IDC // ADC // IDV // TS2 // LT4 ] Authenticator C = EK,tgs [IDC // ADC // TS 5] Bảng trên cho ta thấy kỹ thuật phân phối khoá phiên. Tr−ớc hết khách hμng (client) gửi một thông báo tới AS yêu cầu truy nhập vμo TGS. AS trả lời bằng một thông báo đ−ợc mã bằng khóa trích xuất từ mật khẩu của ng−ời dùng (KC) có chứa thẻ. Thông báo nμy cũng chứa một bản sao của khoá phiên KC,tgs cho C vμ TGS, vì khóa phiên nμy nằm bên trong thông báo đ−ợc mã bằng KC nên chỉ có máy trạm của ng−ời dùng mới có thể đọc đ−ợc nó. Khóa phiên nμy cũng nằm trong Thẻ tgs mμ TGS có thể đọc đ−ợc. Nh− vậy khóa phiên đã đ−ợc phân phối an toμn cho C vμ TGS. Cần chú ý rằng một số thông tin phụ đã đ−ợc thêm vμo pha hội thoại đầu tiên. Thông báo (1) chứa nhãn thời gian TS 1 để AS biết rằng thông báo lμ đúng lúc. Thông báo (2) chứa một số yếu tố của thẻ ở dạng mμ C có thể truy nhập. Điều nμy cho phép C xác nhận rằng th− nμy lμ của TGS vμ biết đ−ợc thời gian hết hạn của nó. Khi có thẻ vμ khóa phiên C đã có thể truy nhập vμo TGS. Tr−ớc hết C gửi tới TGS một thông báo chứa thẻ + IDV (định danh của dịch vụ yêu cầu) (thông báo (3)). Hơn nữa, C cũng phát một thẻ xác thực Authenticator bao gồm IDC vμ ADC (địa chỉ của ng−ời dùng C) vμ một nhãn thời gian TS 3. Không giống nh− thẻ có Ch−ơng 6: Các chuẩn và áp dụng 283 thể dùng lại, thẻ xác thực chỉ dùng một lần vμ có thời gian sống ngắn. TGS có thể giải mã thẻ bằng khóa mμ nó chia sẻ với AS. Thẻ nμy báo rằng ng−ời dùng C đã đ−ợc cung cấp khóa phiên c,tgsK . Thực ra, thẻ nμy báo rằng "Ng−ời sử dụng khóa c,tgsK phải lμ C". TGS dùng khóa phiên để giải mã thẻ xác thực. Sau đó TGS có thể kiểm tra tên vμ địa chỉ từ thẻ xác thực từ nội dung của thẻ vμ từ địa chỉ mạng của thông báo tới. Nếu mọi điều lμ phù hợp thì TGS đã đ−ợc đảm bảo rằng ng−ời gửi thẻ thực sự lμ chủ nhân của thẻ. Thực ra thẻ nμy báo rằng "ở thời điểm TS3 tôi sử dụng c,tgsK ". Cần chú ý rằng thẻ không chứng minh định danh của bất cứ ai nh−ng lμ một ph−ơng pháp để phân phối các khóa một cách an toμn. Chính thẻ xác thực sẽ chứng minh định danh của client. Vì thẻ xác thực chỉ dùng một lần vμ có thời gian dùng ngắn nên đối ph−ơng khó lòng có thể ăn cắp thẻ vμ thẻ xác thực để dùng lại. TGS trả lời bằng thông báo (4) có dạng nh− thông báo (2). Thông báo đ−ợc mã bằng khóa phiên chia sẻ giữa TGS vμ C, nó chứa một khóa phiên cần chia sẻ giữa C vμ máy chủ V, định danh của V; IDV, nhãn thời gian của thẻ. Bản thân thẻ cũng chứa khóa phiên nμy. Lúc nμy C có thẻ cấp dịch vụ có thể dùng lại đối với V. Khi C trình thẻ nμy trong thông báo (5) nó cũng gửi kèm theo một thẻ xác thực (Authentication) Máy chủ V có thể giải mã thẻ, khôi phục khóa phiên vμ giải mã thẻ xác thực khi cần xác thực lẫn nhau, máy chủ có thể trả lời nh− thông báo (6). Máy chủ trả lại giá trị nhãn thời gian lấy từ thẻ xác thực đ−ợc tăng thêm 1 vμ đ−ợc mã bằng khóa phiên. C có thể giải mã thông báo nμy để khôi phục lại nhãn thời gian đã đ−ợc tăng. Vì thông báo đ−ợc mã bằng khóa phiên nên C đ−ợc đảm bảo rằng nó chỉ có thể đ−ợc tạo bởi V. Nội dung của thông báo đảm bảo với C rằng thông báo nμy không phải lμ dùng lại thông báo cũ. Cuối cùng, ở cuối quá trình, client vμ server cùng chia sẻ một khóa Giáo trình Mật mã học 284 bí mật. Khóa nμy có thể đ−ợc dùng để mã hóa các thông báo trong t−ơng lai cho hai bên hoặc để trao đổi khóa phiên ngẫu nhiên mới. Giải thích các yếu tố trong thủ tục Kv.4 a) Trao đổi dịch vụ xác thực Thông báo (1) Client yêu cầu thẻ cấp thẻ. IDC Báo cho AS định danh của ng−ời dùng từ client này IDtgs Báo cho AS biết rằng ng−ời dùng yêu cầu truy nhập TGS TS 1 Cho phép AS kiểm tra rằng đồng hồ của client đ−ợc đồng bộ với AS Thông báo (2) AS trả về thẻ cấp thẻ v,CKE Mã hóa dựa trên mật khẩu của ng−ời dùng, cho phép AS và client kiểm tra mật khẩu và bảo vệ nội dung của thông báo (2) KC, tgs Bản sao của khóa phiên đ−ợc tạo bởi AS mà client có thể sử dụng để thực hiện trao đổi bí mật giữa client và TGS (không yêu cầu chúng phải chia sẻ một khóa cố định) IDtgs Xác nhận rằng thẻ này là cho TGS TS 2 Báo cho client về thời gian mà thẻ này đệ trình. LT 2 Báo cho client về thời gian sống của thẻ này Thẻ tgs Thẻ cần đ−ợc client sử dụng để truy nhập TGS b) Trao đổi dịch vụ cấp thẻ Thông báo (3) Client yêu cầu thẻ cấp dịch vụ IDV Báo cho TGS rằng ng−ời dùng yêu cầu truy nhập tới máy chủ V. Thẻ tgs Đảm bảo cho TGS rằng ng−ời dùng này đ−ợc xác thực bởi AS. AuthenticatorC Đ−ợc tạo bởi client để xác nhận tính hợp lệ cho thẻ. Thông báo (4) TGS trả về thẻ cấp dịch vụ. tgs,CKE Khóa đ−ợc chia sẻ giữa C và TGS dùng bảo vệ nội dung của thông báo (4) tgs,CK Bản sao của khoá phiên đ−ợc tạo bởi AS. IDV Xác nhận rằng thẻ này là cho máy chủ V TS 4 Báo cho client về thời gian mà thẻ này đ−ợc đệ trình. Thẻ V Thẻ đ−ợc dùng bởi client để truy nhập vào máy chủ V. Thẻ tgs Có khả năng dùng lại để ng−ời dùng không phải vào lại mật khẩu. EKtgs Thẻ đ−ợc mã hóa bằng khóa chỉ có AS và TGS biết nhằm tránh phá rối (thu trộm) Ch−ơng 6: Các chuẩn và áp dụng 285 KC, tgs Bản sao của khóa phiên mà TGS có thể truy nhập đ−ợc dùng để giải mã thẻ xác thực nhờ đó xác thực thẻ IDC Báo chủ sở hữu hợp lệ của thẻ này ADC Tránh việc dùng thẻ từ một trạm làm việc khác với trạm đã yêu cầu thẻ IDtgs Đảm bảo cho máy chủ rằng nó đã giải mã đúng cho thẻ. TS 2 Báo cho TGS về thời gian mà thẻ này đ−ợc đệ trình. LT 2 Tránh dùng lại sau khi thẻ đã hết hạn. AuthenticatorC Đảm bảo cho TGS rằng ng−ời trình thẻ đúng là client mà thẻ đã đ−ợc trình cho nó, có thời gian sống ngắn để tránh dùng lại. CK ,tgsE Thẻ xác thực đ−ợc mã bằng khóa chỉ có client và TGS biết nhằm tránh thu trộm. ID C Phải phù hợp với ID trong thẻ để xác thực thẻ. AD C Phải phù hợp với địa chỉ trong thẻ để xác thực thẻ TS 2 Báo cho TGS về thời gian mà thẻ xác thực này đ−ợc tạo ra. c) Trao đổi xác thực Máy trạm/ máy chủ (Client/Server) Thông báo (5) Client yêu cầu dịch vụ. Thẻ V Đảm bảo với máy chủ rằng ng−ời dùng này đã đ−ợc AS xác nhận. AuthenticatorC Đ−ợc tạo bởi client để xác nhận tính hợp lệ cho thẻ. Thông báo (6) Xác thực (tùy chọn) của server đối với client. v,CKE Đảm bảo cho C rằng thông báo này là từ V. TS 5+1 Đảm bảo cho C rằng đây không phải là sự dùng lại của hồi đáp cũ. Thẻ V Có thể dùng lại để client không cần yêu cầu thẻ mới từ TGS đối với mỗi truy nhập tới cùng máy chủ. EKv Thẻ đ−ợc mã hóa bằng khóa chỉ có TGS và server biết nhằm tránh thu trộm. KC, V Bản sao của khóa phiên mà client có thể truy nhập, đ−ợc dùng để giải mã thẻ xác thực nhằm xác thực thẻ. IDC Báo chủ sở hữu hợp lệ của thẻ này. ADC Tránh việc dùng thẻ từ một trạm làm việc khác với trạm đã yêu cầu thẻ. IDV Đảm bảo cho server rằng nó đã giải mã đúng cho thẻ. TS 4 Báo cho server về thời gian mà thẻ này đ−ợc đệ trình. LT 4 Tránh dùng lại sau khi thẻ đã hết hạn. Giáo trình Mật mã học 286 AuthenticatorC Đảm bảo cho server rằng ng−ời trình thẻ đúng là client mà thẻ đã đ−ợc đ−a cho nó, có thời gian sống ngắn để tránh dùng lại. v,CKE Thẻ xác thực đ−ợc mã bằng khóa chỉ có server và client biết nhằm tránh thu trộm. IDC Phải phù hợp với ID trong thẻ để xác thực thẻ. ADC Phải phù hợp với địa chỉ trong thẻ để xác thực thẻ. TS5 Báo cho server về thời gian mà thẻ xác thực này đ−ợc tạo. Bμi tập 1. Nêu ý t−ởng thiết kế một hệ mật bảo vệ các tệp dữ liệu trên cơ sở phân tích PGP? 2. Cấu tạo của chữ ký kép? ý nghĩa của chữ ký kép trong th−ơng mại điện tử? 3. Vai trò của máy chủ xác thực trong Kenberos? 4. Hãy mô tả quá trình trao đổi dịch vụ xác thực trong K.V.4? Phần phụ lục Phần Phụ lục 289 Phụ lục 1 Lý thuyết thông tin trong các hệ mật 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 Shannon. PL 1.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 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 Giáo trình Mật mã học 290 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 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 hệ mật, ta cũng phải chỉ ra kiểu tấn công đang đ−ợc xem xét. Trong ch−ơng 3 đã 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 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 phầ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 1.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 Phần Phụ lục 291 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ị x 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ý 1.1: (Định lý Bayes) Nếu ( )p y 0> thì: ( ) ( ) ( )( ) p x p y x p x y p y = Hệ quả 1.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 độc lập. Giáo trình Mật mã học 292 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: ( ) ( ){ }KC K e x : x= ∈P ở đây C(K) biểu thị tập các bản mã có thể nếu K lμ khóa. Khi đó với mỗi y ∈ C, ta có : ( ) ( ) ( )( ) ( ){ } KK:y C K p y p K p d y ∈ = ∑C K P 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 y xC . (Tức lμ xác suất để y lμ bản mã với điều kiện bản rõ lμ x): ( ) ( ) ( ){ }KK:x d y p y x p K = = ∑C K Bây giờ ta có thể tính đ−ợc xác suất có điều kiện ( )p x yP (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: ( ) ( ) ( ) ( ){ } ( ) ( )( ) ( ){ } KK:x d y K K:y c K p x p K p y x p K p d y = ∈ = = ∑ ∑ K K P P P 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 họa việc tính toán các phân bố xác suất nμy. Ví dụ 1.1 Giả sử { }a,b=P với ( )p a 1 4=P , ( )p b 3 4=P . Cho { }1 2 3K K ,K ,K= với ( )1p K 1 2=K , ( ) ( )2 3p K p K 1 4= =K K . Giả sử Phần Phụ lục 293 { }1,2,3,4=C 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ó nghĩa 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 1.2 Một hệ mật có độ mật hoμn thiện nếu ( ) ( )p x y p x=P P với mọi x ∈ P , y ∈ C Tức xác suất hậu nghiệ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. Trong ví dụ 2.1 chỉ có bản mã 3 mới thỏa mãn 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. Giáo trình Mật mã học 294 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ý sau cho một khẳng định hình thức hóa vμ đ−ợc chứng minh theo các phân bố xác suất. Định lý 1.3 Giả sử 26 khóa 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á eK lμ ( )Ke x x K mod26= + (x ∈ 26). Tr−ớc tiên tính phân bố PC . Giả sử y ∈ Z26, khi đó: ( ) ( ) ( )( ) ( ) ( ) 26 26 26 K K Z K Z K Z p y p K p d y 1 26 p y K 1 26 p y K ∈ ∈ ∈ = = − = − ∑ ∑ ∑ C K P P P Xét thấy với y cố định, các giá trị y K mod26− 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ó: ( ) ( ) 26 26K Z K Z p y K p y 1 ∈ ∈ − = =∑ ∑P P Do đó ( )p y 1 26=C với bất kỳ y ∈ Z26. Tiếp theo ta có: ( ) ( )p y x p y x mod26 1 26= − =C K Với mọi x,y vì với mỗi cặp x,y, khóa duy nhất K (khóa đảm bảo eK(x) = y) lμ khóa K = y-x mod 26. Bây giờ sử dụng định lý Bayes, ta có thể dễ dμng tính: Phần Phụ lục 295 ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) p x p y x p x y p y p x . 1 26 1 26 p x = = = P C C C P P 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ẽ nghiê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ý 1.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 khóa 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 khóa 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: Giáo trình Mật mã học 296 ( ){ }Ke x : K= ∈ =C C K Tuy nhiên, ta giả sử rằng |C | = |K | . Bởi vậy ta phải có: ( ){ }Ke x : K∈ =C K Tức lμ ở đây không tồn tại hai khoá K1 vμ K2 khác nhau để ( ) ( )K1 K2e x e 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 khóa K để eK(x) = y. Ký hiệu n = |K | . Giả sử P = {xi: 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 (xi ) = yi, 1 ≤ i ≤ n. Sử dụng định lý Bayes ta có: ( ) ( ) ( )( ) ( ) ( )( ) ( ) i i i 1 i p y x p x p x y p y p K . p x p y = = C P P C K P C Xét điều kiện độ mật hoμn thiện ( ) ( )i ip x y p x=P P Điều kiện nμy kéo theo ( )( )ip K p y=K C với 1 ≤ i ≤ n. Tức lμ khoá đ−ợc dùng với xác suất nh− nhau (chính bằng pC(y)). Tuy nhiên vì số khoá lμ |K | nên ta có pK(K) =1/ |K | với mỗi K ∈K . Ng−ợc lại, giả sử hai điều giả định đều thoả mãn. 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 Vernam 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 đó. Phần Phụ lục 297 Mô tả về hệ mật dùng một lần nêu trên hình PL 1.1. Giả sử n ≥ 1 là số nguyên và P = C = K = (Z2)n. Với K (Z2)n , ta xác định eK(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 dãy bit t−ơng ứng). Nh− vậy, nếu x = (x1,..., xn ) và K = (K1,..., Kn ) thì: e K(x) = (x1 + K1,..., xn + Kn) mod 2. Phép mã hoá là đồng nhất với phép giải mã. Nếu y = (y1,..., yn ) thì: d K(y) = (y1 + K1,..., yn + Kn) mod 2. Hình PL 1.1: Hệ mật sử dụng khoá một lần (OTP) 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 rãi. Đáng tiếc lμ có 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 khóa để 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 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ằng phép hoặc loại trừ xâu bít bất kỳ x vμ eK(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μy tạ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 rãi 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. 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 Giáo trình Mật mã học 298 dμi (tức có thể dùng một khóa để mã nhiều bản tin) nh−ng chí ít vẫn còn giữ đ−ợ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. PL 1.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ỉ 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 đ−a 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. 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 sấ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 sấ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μ x1, x2, x3 với các xác suất t−ơng Phần Phụ lục 299 ứ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á x1 lμ 0, mã của x2 lμ 10 vμ mã của x3 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,