Tài liệu Phương pháp lập mã tối ưu an toàn

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN VĂN MẠNH PHƯƠNG PHÁP LẬP Mà TỐI ƯU AN TOÀN Ngành Chuyên ngành Mã số : Công nghệ thông tin : Công nghệ phần mềm : 60 48 10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ PHÊ ĐÔ Hà Nội - 2011 5 BẢNG CHỮ VIẾT TẮT Viết tắt CNTT ĐHCN ĐHQGHN CSDL CNPM RSA ASCII MIT DES NIST AES GCD Tên đầy đủ Công nghệ thông tin Đại Học Công Nghệ Đại Học Quốc Gia Hà Nội Cơ sở dữ liệu Công nghệ phần mềm Ronald Rivest, Adi Shamir và Leonard Adleman American Standard Code for Information Interchange Massachusetts Institute of Technology Data Encryption Standard National Institute of Standards and Technology Advanced Encryption Standard Greatest Common Divisor Phương pháp lập mã tối ưu an toàn 6 MỤC LỤC LỜI CÁM ƠN ................................................................................................................................ 3 LỜI CAM ĐOAN .......................................................................................................................... 4 BẢNG CHỮ VIẾT TẮT ................................................................................................................ 5 MỤC LỤC...................................................................................................................................... 6 DANH SÁCH HÌNH VẼ ............................................................................................................... 8 DANH SÁCH BẢNG BIỂU .......................................................................................................... 9 MỞ ĐẦU...................................................................................................................................... 10 1. Lý do chọn đề tài và tên đề tài .............................................................................................10 2. Mục đích và nhiệm vụ .........................................................................................................10 3. Đối tượng và phạm vi nghiên cứu.......................................................................................11 4. Phương pháp nghiên cứu .....................................................................................................11 5. Ý nghĩa khoa học và thực tiễn của luận văn ........................................................................12 6. Bố cục luận văn ...................................................................................................................12 Chương I - GIỚI THIỆU CHUNG VỀ MẬT Mà HỌC .............................................................. 13 1.1 Sơ đồ khối đơn giản của hệ thống thông tin ......................................................................13 1.2 Sơ lược về mật mã học ......................................................................................................14 1.3 Hệ mật mã ..........................................................................................................................15 1.4 Hệ mật mã khóa đối xứng ..................................................................................................16 1.5 Hệ mật mã khóa công khai ................................................................................................17 1.6 Hệ mật mã tích hợp ............................................................................................................17 1.7 Các bài toán về an toàn thông tin .......................................................................................17 Chương II - CƠ SỞ TOÁN HỌC CỦA LÝ THUYẾT MẬT Mà ............................................... 19 2.1 Lý thuyết thông tin.............................................................................................................19 2.1.1 Entropy .......................................................................................................................19 2.1.2 Tốc độ của ngôn ngữ ..................................................................................................20 2.1.3 Tính an toàn của hệ mật mã ........................................................................................21 2.1.4 Kỹ thuật lộn xộn và rườm rà ......................................................................................22 2.2 Lý thuyết độ phức tạp ........................................................................................................22 2.2.1 Khái niệm ...................................................................................................................23 2.2.2 Độ mật hoàn thiện ......................................................................................................25 2.2.3 Hàm một phía và cửa sập một phía ............................................................................26 2.3 Lý thuyết số học.................................................................................................................27 2.3.1 Tính chất chia hết của các số nguyên .........................................................................28 2.3.2 Số nguyên tố ...............................................................................................................30 2.3.3 Các số nguyên modulo n ............................................................................................31 2.3.4 Đồng dư và phương trình đồng dư tuyến tính ............................................................32 2.3.5 Thặng dư rút gọn và phần tử nguyên thủy ..................................................................33 2.3.6 Phương trình đồng dư bậc hai và thặng dư bậc hai ....................................................35 Chương III - CÁC HỆ MẬT Mà ................................................................................................. 38 Phương pháp lập mã tối ưu an toàn 7 3. 1 Hệ mật mã khóa đối xứng .................................................................................................38 3.1.1 Hệ mật mã hóa dịch chuyển .......................................................................................39 3.1.2 Hệ mật mã hóa thay thế ..............................................................................................40 3.1.3 Hệ mật mã Affine .......................................................................................................42 3.1.4 Hệ mật mã Vigenere ...................................................................................................45 3.2. Hệ mật mã khóa công khai ...............................................................................................46 3.2.1 Hệ mật mã RSA .........................................................................................................48 3.2.2 Hệ mật mã Elgamal ....................................................................................................55 3.4 Hệ mật mã tích hợp ............................................................................................................58 3.4.1 Giới thiệu ....................................................................................................................58 3.4.2 Hệ mật mã Vigenere-RSA ..........................................................................................62 3.4.3 Hệ mật mã Vigenere-Elgamal ....................................................................................63 3.4.4 Đánh giá hệ mật mã tích hợp với các hệ mật mã đối xứng và hệ mật mã khóa công khai ......................................................................................................................................64 3.4.5 So sánh độ phức tạp của Vigenere-RSA và Vigenere-Elgamal ..................................65 KẾT LUẬN .................................................................................................................................. 68 BẢNG THUẬT NGỮ ANH – VIỆT ........................................................................................... 70 TÀI LIỆU THAM KHẢO ............................................................................................................ 71 PHỤ LỤC ..................................................................................................................................... 72 Phương pháp lập mã tối ưu an toàn 8 DANH SÁCH HÌNH VẼ Hình 1.1. Sơ đồ khối của một hệ thống thông tin số [1]. ..............................................13  Hình 3.1. Mô hình hệ mật mã khóa đối xứng. ...............................................................39  Hình 3.2. Mô hình hệ mật mã khóa công khai. .............................................................48  Hình 3.3. Trong một hệ mật mã tích hợp, khóa bất đối xứng được sử dụng để mã hóa khóa bí mật và khóa bí mật sử dụng để mã hóa thông điệp [4].....................................60  Hình 3.4. Bill sử dụng mật mã khóa công khai để gửi cho Paul một thông điệp [4]. ...61  Hình 3.5. Sơ đồ mã hóa và giải mã của hệ mật tích hợp Vigenere-RSA. .....................63  Hình 3.6. Sơ đồ mã hóa và giải mã hệ mật tích hợp Vigenere-Elgamal. ......................64  Hình 3.7. Hiệu năng của Vigenere-RSA và Vigenere-Elgamal. ...................................67  Phương pháp lập mã tối ưu an toàn 9 DANH SÁCH BẢNG BIỂU Bảng 1.1. Các ký tự tiếng Anh và các thặng dư modulo 26. .........................................16  Bảng 2.1. Thời gian để phân tích một số nguyên n ra thừa số nguyên tố. ....................25  Bảng 2.2. Các bước chạy thuật toán Euclide. ................................................................29  Bảng 2.3. Các bước chạy thuật toán Euclide mở rộng. .................................................30  Bảng 3.1. Đặc điểm khác nhau giữa hệ thống đối xứng và bất đối xứng......................61  Bảng 3.2. Hiệu năng của thuật toán Vigenere-RSA. .....................................................66  Bảng 3.3. Hiệu năng của thuật toán Vigenere-Elgamal. ...............................................66  Bảng 3.4. Hiệu năng của thuật toán Vigenere-RSA bỏ “salt”. ......................................66  Phương pháp lập mã tối ưu an toàn 10 MỞ ĐẦU 1. Lý do chọn đề tài và tên đề tài Hiện nay trong giai đoạn CNTT phát triển rất mạnh, hàng loạt những kỹ thuật, công nghệ mới ra đời, nhu cầu sử dụng thông tin và bảo mật thông tin là rất lớn. Thách thức lớn đối với giới tin học ngày càng tăng khi nhu cầu bảo mật của người dùng hơn bao giờ hết phải được đảm bảo tuyệt đối an toàn. Các hệ mật mã khóa đối xứng có ưu điểm là mã hóa /giải mã nhanh nhưng nhược điểm lớn nhất là khả năng trao đổi khóa kém an toàn. Đây là lý do dẫn đến việc các hệ mật mã khóa đối xứng không được ứng dụng cao cho lắm. Với các hệ mật mã khóa công khai thì lại khắc phục được nhược điểm trên của hệ mật mã khóa đối xứng nhưng nó lại có nhược điểm là tốc độ mã hóa/giải mã rất chậm so với hệ mật mã khóa đối xứng. Hiện nay các dịch vụ chữ ký số, thanh toán điện tử, và sắp tới là công nghệ điện toán đám mây được áp dụng nhiều trong đời sống hàng ngày thì vấn đề bảo mật thông tin càng trở nên hết sức cấp bách. Làm sao để người sử dụng sản phẩm yên tâm với khâu bảo mật và an toàn dữ liệu của họ, đặc biệt là những thông tin nhạy cảm. Các nhà mật mã học trên thế giới không ngừng nghiên cứu, cải tiến để đưa ra những phương pháp lập mã được cho là tốt nhất theo cả khía cạnh kỹ thuật lẫn kinh tế. Không nằm ngoài nghiên cứu chung, thầy trò chúng tôi cũng suy nghĩ rất nhiều về điều này. Sau nhiều ngày suy nghĩ, thảo luận và cân nhắc cộng với sự hướng dẫn và gợi ý của TS Lê Phê Đô, đề tài cho luận văn tốt nghiệp Cao học ngành CNPM đã chính thức được tôi chọn với tên là: Phương pháp lập mã tối ưu an toàn. Luận văn được hoàn thành dưới sự hỗ trợ của Đề tài “NGHIÊN CỨU CÁC MÔ HÌNH TOÁN HỌC VÀ ỨNG DỤNG VÀO VIỆC PHÂN TÍCH CÁC HỆ THỐNG TRONG TỰ NHIÊN VÀ Xà HỘI”, Mã số: CN 10.03, do TS. Lê Phê Đô làm Chủ nhiệm. 2. Mục đích và nhiệm vụ ™ Mục đích • Về học thuật: Đề tài tập trung vào việc xây dựng một số phương pháp lập mã tích hợp giữa hệ mật mã khóa đối xứng và hệ mật mã khóa công khai. Nhằm đưa ra những hệ mật mã hóa tích hợp, tối ưu và an toàn theo nghĩa nào đó cả về mặt kỹ thuật lẫn kinh tế. • Về phát triển và triển khai ứng dụng: Các kết quả nghiên cứu của đề tài sẽ là tiền đề cho các ứng dụng tiếp theo về mã hóa / giải mã như trong chữ ký số, xác thực người dùng,… Đây là những thuật toán “tối ưu” và “an Phương pháp lập mã tối ưu an toàn 11 toàn” cả về mặt tốc độ lẫn thời gian chạy, nhằm tăng tính bảo mật của hệ mật mã tích hợp. ™ Nhiệm vụ • Nghiên cứu hệ mật mã khóa đối xứng, đặc biệt chú trọng đến hệ mật mã Vigenere. • Nghiên cứu hệ mật mã khóa công khai. Tiêu biểu nhất là hai hệ mật mã RSA và Elgamal. • Từ đó đưa ra hai hệ mật mã tích hợp kết hợp giữa hệ mật mã Vigenere với RSA và Vigenere với Elgamal nhằm đảm bảo kết quả các hệ mật mã tích hợp đưa ra là tối ưu và an toàn theo khía cạnh kỹ thuật cũng như kinh tế nào đó. • Viết chương trình thử nghiệm cho hệ mật mã tích hợp trên. • Sau đó so sánh kết quả thực thi chương trình hai hệ mật mã tích hợp Vigenere-RSA và Vigenere-Elgamal. Cuối cùng kết luận rằng VigenereRSA có tốc độ mã hóa/giải mã nhanh hơn Vigenere-Elgamal. 3. Đối tượng và phạm vi nghiên cứu ™ Đối tượng nghiên cứu: Nghiên cứu chung về mật mã học, cơ sở toán học của lý thuyết mật mã, các hệ mật mã bao gồm: hệ mật mã khóa đối xứng, hệ mật mã khóa công khai. Hệ mật mã khóa đối xứng thì tập trung kỹ hơn về hệ mật Vigenere, còn hệ mật mã khóa công khai thì tập trung vào hai hệ mật RSA và Elgamal. Từ đó nghiêu cứu và đề xuất ra phương pháp mã hóa tích hợp, phương pháp này tối ưu những ưu điểm của hệ mật mã khóa đối xứng và khóa công khai. ™ Phạm vi nghiên cứu: Đề tài tập trung vào nghiên cứu phương pháp lập mã tích hợp, là sự kết hợp những ưu điểm của hệ mật mã khóa đối xứng và hệ mật mã khóa công khai. Đề tài cũng đưa ra thuật toán, phân tích độ phức tạp của thuật toán và cài đặt cụ thể cho các phương pháp tích hợp trên. Sau đó có so sánh hiệu năng của hai phương pháp đã đưa ra. Còn về việc triển khai ứng dụng thực tế thiết nghĩ cần có thêm các điều kiện về thời gian cũng như quy mô. 4. Phương pháp nghiên cứu • Dựa trên các giải thuật của hệ mật mã Vigenere và hệ mật mã khóa công khai RSA và Elgamal. Phân tích những ưu nhược điểm của từng hệ mật mã trên từ đó đề xuất ra phương pháp tích hợp. • Thu thập các bài báo, tài liệu đã xuất bản trên các tạp chí khoa học và các tài liệu trên mạng Internet có liên quan đến vấn đề đang nghiên cứu của đề tài. Phương pháp lập mã tối ưu an toàn 12 • Tìm hiểu, phân tích, kế thừa các thuật toán và quy trình mã đã công bố kết quả. Từ đó đề xuất ra hai thuật toán lập mã tích hợp, cài đặt thử nghiệm thuật toán để minh họa cho các vấn đề nghiên cứu trong phạm vi đề tài. 5. Ý nghĩa khoa học và thực tiễn của luận văn ™ Ý nghĩa khoa học • Trình bày giới thiệu chung về mật mã học, các kiến thức cơ sở toán học của lý thuyết mật mã. • Trình bày các hệ mật mã: bao gồm hệ mật mã khóa đối xứng và hệ mật mã khóa công khai. • Từ đó phân tích, so sánh ưu nhược điểm của hai hệ mật trên sau đó đưa ra hệ mật mã tích hợp là sự kết hợp giữa hệ mật mã khóa đối xứng và hệ mật mã khóa công khai. ™ Ý nghĩa thực tiễn • Đã đưa ra hai hệ mật mã tích hợp là Vigenere-RSA và VigenereElgamal được đánh giá là tối ưu và an toàn dựa trên sự kết hợp ưu điểm của hệ mật mã hóa khóa đối xứng và khóa công khai. • Phân tích độ phức tạp thuật toán của hai hệ mật mã trên. • Cài đặt thử nghiệm thành công hai thuật toán trên bằng ngôn ngữ Java. • Đưa ra những so sánh về tốc độ cũng như tính bảo mật của hai hệ mật mã hóa tích hợp và kết luận rằng hệ mật Vigenere-RSA có tốc độ mã hóa/giải mã nhanh hơn Vigenere-Elgamal. 6. Bố cục luận văn Nội dung chính của luận văn gồm 3 chương: Chương 1: Tập trung tìm hiểu cũng như giới thiệu chung về mật mã học. Chương 2: Tìm hiểu cơ sở toán học của lý thuyết mật mã. Chương 3: Tìm hiểu các hệ mật mã bao gồm hệ mật mã khóa đối xứng, hệ mật mã khóa công khai từ đó so sánh ưu nhược điểm của nó. Sau đó đề xuất ra hệ mật mã tích hợp. Phần cuối cùng là Kết luận: Trình bày những khó khăn trong quá trình thực hiện, các kết quả đạt được và hướng phát triển/nghiên cứu tiếp theo của đề tài. Phương pháp lập mã tối ưu an toàn 13 Chương I GIỚI THIỆU CHUNG VỀ MẬT Mà HỌC Nội dung của chương 1 giới thiệu tổng quan các khái niệm cơ bản về mật mã học và hệ thống mã hóa, đồng thời giới thiệu sơ lược về hệ mật mã khóa đối xứng, hệ mật mã khóa công khai và hệ mật mã tích hợp. Cuối cùng là các bài toán về an toàn thông tin. Chúng ta sẽ có cái nhìn tổng quan chung về mật mã học. 1.1 Sơ đồ khối đơn giản của hệ thống thông tin Bản rõ Đầu vào rõ Biến đổi A/D (tương tự - số) Bản mã Mã bảo mật Mã nguồn Mã kênh Nguồn tin tương tự Từ mã được truyền Kênh truyền (tạp âm, đa đường, giao thoa, nhiễu, nghe trộm, …) Biến đổi D/A ( số - tương tự) Giải mã mật Giải mã nguồn Giải mã kênh Nhận tin Đầu ra số Bản rõ Bản mã Hình 1.1. Sơ đồ khối của một hệ thống thông tin số [1]. Trường hợp nguồn tin đầu vào là nguồn tin số thì không cần bộ biến đổi A/D ở đầu vào và bộ biến đổi D/A ở đầu ra. Trong hệ thống này khối mã bảo mật có chức năng bảo vệ cho thông tin không bị khai thác bất hợp pháp, chống lại các tấn công sau: a. Thám mã thụ động: bao gồm các hoạt động: - Thu chặn - Dò tìm - So sánh tương quan - Suy diễn Phương pháp lập mã tối ưu an toàn 14 b. Thám mã tích cực: bao gồm các hoạt động: - Giả mạo - Ngụy trang - Sử dụng lại - Sửa đổi 1.2 Sơ lược về mật mã học Mật mã học là ngành khoa học ứng dụng toán học vào việc biến đổi thông tin thành một dạng khác với mục đích che dấu nội dung, ý nghĩa thông tin cần mã hóa. Đây là một ngành quan trọng có nhiều ứng dụng trong đời sống xã hội. Ngày nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử dụng ngày càng phổ biến hơn trong các lĩnh vực khác nhau trên thế giới, từ các lĩnh vự an ninh, quân sự, quốc phòng,…, cho đến các lĩnh vực dân sự như thương mại điện tử, ngân hàng,… Cùng với sự phát triển CNTT nói chung, khoa học máy tính và internet nói riêng, các nghiên cứu và ứng dụng của khoa học mật mã ngày càng trở lên đa dạng hơn, mở ra nhiều hướng nghiên cứu chuyên sâu vào lĩnh vực ứng dụng đặc thù với những đặc trưng riêng. Ứng dụng khoa học mật mã không chỉ đơn thuần là mã hóa và giải mã thông tin mà còn bao gồm nhiều vấn đề khác nhau cần nghiên cứu và giải quyết: chứng thực nguồn gốc nội dung thông tin (kỹ thuật chữ ký số), chứng nhận tính xác thực về người sở hữu mã khóa (chứng nhận khóa công khai), các quy trình giúp trao đổi thông tin và thực hiện giao dịch điện tử an toàn trên mạng. Những kết quả nghiên cứu về mật mã cũng đã được đưa vào trong các hệ thống phức tạp hơn, kết hợp với những kỹ thuật khác để đáp ứng các yêu cầu đa dạng của các hệ thống ứng dụng khác trong thực tế, ví dụ như hệ thống bỏ phiếu bầu cử qua mạng, hệ thống đào tạo từ xa, hệ thống quản lý an ninh của các đơn vị với hướng tiếp cận sinh trắc học, hệ thống cung cấp dịch vụ multimedia trên mạng với yêu cầu cung cấp dịch vụ và bảo vệ bản quyền sở hữu trí tuệ đối với thông tin số. Khoa học về mật mã bao gồm: - Mật mã học Phân tích mật mã Mật mã học là khoa học nghiên cứu cách ghi bí mật thông tin nhằm biến bản tin rõ thành các bản mã. Phương pháp lập mã tối ưu an toàn 15 Phân tích mã là khoa học nghiên cứu cách phá mã các hệ mật nhằm phục hồi bản rõ ban đầu từ bản mã. Việc tìm hiểu các thông tin về khóa và các phương pháp biến đổi thông tin cũng là một nhiệm vụ quan trọng của phân tích mật mã. Có ba phương pháp tấn công cơ bản của thám mã: - Tìm khóa vét cạn Phân tích thống kê Phân tích toán học Việc tấn công của thám mã có thể được thực hiện với các giả định: - Tấn công chỉ với bản mã Tấn công với bản rõ đã biết Tấn công với các bản rõ được chọn Tấn công với các bản mã được chọn Chú ý: - Một hệ mật có thể bị phá chỉ với bản mã thường là hệ mật có độ an toàn thấp Một hệ mật là an toàn với kiểu tấn công có các bản rõ được chọn thường là một hệ mật có độ an toàn cao Có bốn loại hệ mật mã sau: - Hệ mật mã dòng Hệ mật mã khóa đối xứng Hệ mật mã có hồi tiếp mật mã Hệ mật mã khóa công khai Khi xây dựng một hệ mật người ta thường xem xét tới các tiêu chuẩn sau: - Độ mật cần thiết Kích thước không gian khóa Tính đơn giản và tốc độ mã hóa/giải mã Tính lan truyền sai Tính mở rộng bản tin 1.3 Hệ mật mã Định nghĩa 1.1: Một hệ mật mã là một bộ năm (P, C, K, E, D) thỏa mãn các điều kiện sau: 1. Tập nguồn P là tập hữu hạn tất cả các mẫu tin nguồn cần mã hóa có thể có (ký tự bản rõ) Phương pháp lập mã tối ưu an toàn 16 2. Tập đích C là tập hữu hạn tất cả các mẫu tin có thể có sau khi mã hóa (kỹ tự bản mã) 3. Tập khóa K là tập hữu hạn các khóa có thể được sử dụng 4. E và D lần lượt là tập luật mã hóa và giải mã với mỗi khóa k K, tồn tại một luật mã hóa ek E và một luật giải mã dk D tương ứng. Luật mã hóa ek: P C và luật giải mã dk: C P là hai ánh xạ thỏa mãn điều kiện dk (ek(x)) = x, x P. Trong định nghĩa này phép lập mã/giải mã được định nghĩa cho từng ký tự bản rõ/bản mã. Trong thực tế, bản rõ của một thông báo thường là một dãy ký tự bản rõ, tức là phần tử của tập P*, và bản mật cũng là một dãy các ký tự bản mã, tức là phần tử của tập C*. Tập các ký tự bản rõ và bản mã thường dùng là tập các ký tự của ngôn ngữ thông thường như tiếng Việt, tiếng Anh (ta ký hiệu tập ký tự tiếng Anh là A tức là A = {A, B, …, Z} gồm 26 ký tự; tập ký tự nhị phân B chỉ gồm hai ký tự 0 và 1; tập các số nguyên không âm bé hơn một số n nào đó (Ta ký hiệu tập Zn tức Zn = {0, 1, 2,…, n1}). Chú ý rằng có thể xem B = Z2. Để thuận tiện, ta thường đồng nhất tập các ký tự tiếng Anh A và các thặng dư theo modulo 26 như sau: Bảng 1.1. Các ký tự tiếng Anh và các thặng dư modulo 26. A B C D E F G H I J … … R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 … … 17 18 19 20 21 22 23 24 25 Tính chất 4 là tính chất chính và quan trọng của một hệ thống mã hóa. Tính chất này đảm bảo một mẫu tin x P được mã hóa bằng một luật ek E và được giải mã chính xác bằng luật dk D. 1.4 Hệ mật mã khóa đối xứng Trong hệ mật mã khóa đối xứng, quá trình mã hóa và giải mã một thông điệp/văn bản sử dụng cùng một mã khóa gọi là khóa bí mật hay khóa đối xứng. Do đó, vấn đề bảo mật thông tin đã mã hóa hoàn toàn phụ thuộc vào việc giữ bí mật nội dung của khóa đã được sử dụng. Với tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ xử lý hiện nay, phương pháp mã hóa chuẩn (DES) đã trở nên không an toàn trong bảo mật thông tin. Do đó Viện Tiêu Chuẩn và Công Nghệ Quốc Gia Hoa Kỳ (NIST) đã quyết định một chuẩn mã hóa mới với độ an toàn cao nhằm phục vụ nhu cầu bảo mật thông tin liên lạc của chính phủ Hoa Kỳ cũng như các ứng dụng dân sự. Thuật toán Rijndael do Phương pháp lập mã tối ưu an toàn 17 Vincent Rijmen và Joan Daeman đã được chính thức chọn trở thành chuẩn mã hóa nâng cao (AES) từ 02 tháng 10 năm 2000. 1.5 Hệ mật mã khóa công khai Nếu như vấn đề khó khăn đặt ra đối với hệ mật mã khóa đối xứng chính là bài toán trao đổi mã khóa thì ngược lại, các hệ mật mã khóa công khai giúp cho việc trao đổi mã khóa trở nên dễ dàng hơn. Nội dung của khóa công khai không cần phải giữ bí mật như đối với khóa bí mật trong hệ mật mã khóa đối xứng. Sử dụng khóa công khai, chúng ta có thể thiết lập một quy trình an toàn để truy đổi khóa bí mật được sử dụng trong hệ mật mã khóa đối xứng. Những năm gần đây, các phương pháp mã hóa khóa công khai, đặc biệt là phương pháp RSA, được sử dụng ngày càng nhiều trong các ứng dụng mã hóa trên thế giới và có thể xem như đây là phương pháp chuẩn được sử dụng phổ biến nhất trên Internet, ứng dụng trong việc bảo mật thông tin liên lạc cũng như trong lĩnh vực thương mại điện tử. 1.6 Hệ mật mã tích hợp Các hệ mật mã khóa đối xứng có ưu điểm xử lý rất nhanh và khả năng bảo mật cao so với các hệ mật mã khóa công khai nhưng lại gặp phải vấn đề khó khăn trong việc trao đổi khóa. Ngược lại, các hệ mật mã khóa công khai tuy xử lý thông tin chậm hơn nhưng lại cho phép người sử dụng trao đổi mã khóa dễ dàng hơn. Do đó, trong các ứng dụng thực tế, chúng ta cần phối hợp được các ưu điểm của mỗi hệ mật mã hóa để xây dựng hệ thống mã hóa và bảo mật thông tin hiệu quả và an toàn. 1.7 Các bài toán về an toàn thông tin Nhu cầu trao đổi thông tin và các phương tiện truyền đưa thông tin phát triển một cách nhanh chóng. Cùng với sự phát triển đó, đòi hỏi bảo vệ tính bí mật an toàn của thông tin cũng càng ngày càng to lớn và có tính phổ biến. Có nhiều bài toán khác nhau về yêu cầu an toàn thông tin tùy theo những tình huống khác nhau, nhưng tựu trung có một số bài toán chung nhất mà ta thường gặp trong thực tiễn là các bài toán sau đây: - Bảo mật: giữ thông tin được bí mật đối với tất cả mọi người, trừ một số ít người có thẩm quyền được đọc, biết thông tin. Toàn vẹn thông tin: đảm bảo thông tin không bị thay đổi hay xuyên tạc bởi những kẻ không có thẩm quyền hoặc bằng những phương tiện không được phép. Phương pháp lập mã tối ưu an toàn 18 - - Nhận thực một thực thể: xác nhận danh tính của một thực thể, chẳng hạn như một người, một máy tính cuối trong mạng, một thẻ tín dụng,… Nhận thực một thông báo: xác định nguồn gốc của một thông báo gửi được đến. Chữ ký: một cách để gắn kết một thông tin với một thực thể, thường dùng trong bài toán nhận thực một thông báo cũng như trong nhiều bài toán nhận thực khác. Ủy quyền: chuyển cho một thực thể khác quyền được đại diện hoặc được làm một việc gì đó. Cấp chứng chỉ: cấp một sự xác nhận thông tin bởi một thực thể được tín nhiệm. Báo nhận: xác nhận một thông báo đã được nhận hay một dịch vụ đã được thực hiện. Làm chứng: kiểm thử việc tồn tại một thông tin ở một thực thể khác với người sở hữu thông tin đó. Không chối bỏ được: ngăn ngừa việc chối bỏ trách nhiệm đối với một cam kết đã có (ví dụ như đã ký vào một văn bản). Ẩn danh: che giấu danh tính của một thực thể tham gia trong một tiến trình nào đó (thường dùng trong giao dịch tiền điện tử) Thu hồi: rút lại một giấy chứng chỉ hay ủy quyền đã cấp. Vân vân … Cơ sở của các phương pháp cho các bài toán kể trên là các phương pháp mật mã, đặc biệt là mật mã khóa công khai. Phương pháp lập mã tối ưu an toàn 19 Chương II CƠ SỞ TOÁN HỌC CỦA LÝ THUYẾT MẬT Mà Để tìm hiểu được những thuật toán sử dụng trong các hệ mật mã, trong các hệ chữ ký điện tử cũng như các giao thức mật mã, chúng ta phải có những kiến thức nền tảng cơ bản về toán học, lý thuyết thông tin, … được sử dụng trong mật mã học. Chương này sẽ trình bày những khái niệm cơ bản về lý thuyết thông tin như Entropy, tốc độ của ngôn ngữ, độ phức tạp và an toàn của thuật toán, và một số kiến thức toán học như đồng dư học (modulo), số nguyên tố, định lý phần dư Trung hoa, định lý Fermat, … và các thuật toán kiểm tra số nguyên tố. Vì vậy, vấn đề chính trình bày trong chương này gồm: • Lý thuyết thông tin • Lý thuyết độ phức tạp • Lý thuyết số học 2.1 Lý thuyết thông tin Những khái niệm mở đầu của lý thuyết thông tin được đưa ra lần đầu tiên vào năm 1949 bởi Claude Elwood Shannon (một nhà khoa học được coi là cha đẻ của lý thuyết thông tin). Trong phần này chúng ta chỉ đề cập tới một số chủ đề quan trọng của lý thuyết thông tin. 2.1.1 Entropy Lý thuyết thông tin định nghĩa khối lượng thông tin trong một thông báo là số bít nhỏ nhất cần thiết để mã hóa tất cả những nghĩa có thể của thông báo đó. Vi dụ 2.1: Giả sử trường ngay_thang trong một CSDL chứa không quá 3 bít thông tin, bởi vì thông tin ngày có thể mã hóa với 3 bít dữ liệu: 000 = Sunday 001 = Monday 010 = Tuesday 011 = Wednesday 100 = Thursday 101 = Friday 110 = Saturday 111 is unused Phương pháp lập mã tối ưu an toàn 20 Nếu thông tin này được biểu diễn bởi chuỗi ký tự ASCII tương ứng, nó sẽ chiếm nhiều không gian nhớ, nhưng cũng không chưa nhiều thông tin hơn. Tương tự như trường gioi_tinh của CSDL chỉ chứa 1 bít thông tin, nó có thể lưu trữ như một trong hai xâu ký tự ASCII: Nam, Nữ. Khối lượng thông tin trong một thông báo M đo bởi Entropy của thông báo đó, ký hiệu là H(M). Entropy của thông báo gioi_tinh là 1 bít, ký hiệu H(gioi_tinh) = 1, Entropy của thông báo số ngày trong tuần nhỏ hơn 3 bít. Trong trường hợp tổng quát, Entropy của một thông báo là log2n, với n là số khả năng có thể (ý nghĩa) của thông báo. H(M) = log2n 2.1.2 Tốc độ của ngôn ngữ Đối với một ngôn ngữ, tốc độ thực tế của ngôn ngữ ký hiệu là r = H(M)/N. Trong trường hợp này N là độ dài của thông báo, và M là một thông điệp có độ dài N. Tốc độ của tiếng Anh bình thường là 0.28 do đó mỗi chữ tiếng Anh có 1.3 bít nghĩa. Tốc độ tuyệt đối của một ngôn ngữ là số bít lớn nhất cần thiết để mã hóa các kỹ tự của ngôn ngữ nào đó. Nếu có L ký tự trong một ngôn ngữ, thì tốc độ tuyệt đối là R = log2L. Đây là số Entropy lớn nhất của mỗi ký tự đơn lẻ. Đối với tiếng Anh gồm 26 chữ cái, đốc độ tuyệt đối là log226 = 4.7 bít/ chữ cái. Sẽ không có điều gì là ngạc nhiên đối với tất cả mọi người rằng thực tế tốc độ của tiếng Anh nhỏ hơn nhiều so với tốc độ tuyệt đối, và chúng ta vẫn thấy rằng đối với một thông báo bằng tiếng Anh có thể loại bỏ một số chữ cái nhưng người đọc vẫn có thể hiểu được. Hiện tượng này được gọi là độ dư thừa của ngôn ngữ tự nhiên. Không chỉ đối với tiếng Anh mà với hầu hết các ngôn ngữ tự nhiên, do cấu trúc của ngôn ngữ, do việc sử dụng ngôn ngữ dẫn tới có một số chữ cái được sử dụng với tần suất không đồng đều hoặc chỉ có thể xuất hiện với một cấu trúc nào đó làm cho chúng ta vẫn có thể đoán được nghĩa của các thông báo nếu loại bỏ các chữ cái này. Độ dư thừa của một ngôn ngữ ký hiệu là D và D = R – r. Đối với tiếng Anh: D = 1 – 0.28 = 0.72 letters/letter D = 4.7 – 3.1 = 3.4 letters/letter Như vậy mỗi chữ cái có 1.3 bít nghĩa và 3.4 bít dư thừa (xấp xỉ 72%). Phương pháp lập mã tối ưu an toàn 21 2.1.3 Tính an toàn của hệ mật mã Shannon định nghĩa rất rõ ràng, tỉ mỉ các mô hình toán học để đánh giá độ an toàn của các hệ mật mã sử dụng. Mục đích của người thám mã là phát hiện ra khóa sử dụng của hệ mật mã K, bản rõ P, hoặc cả hai. Hơn nữa họ có thể hài lòng với vài thông tin có khả năng về bản rõ P, chẳng hạn như đó là âm thanh dạng số, hoặc là một văn bản tiếng Đức, hoặc là một bảng tính dữ liệu, v.v… Trong hầu hết các lần thám mã, người thám mã cố gắng thu thập một số thông tin có khả năng về bản rõ P trước khi bắt đầu. Họ có thể biết được ngôn ngữ đã được sử dụng để mã hóa. Ngôn ngữ này chắc chắn có sự dư thừa kết hợp với chính ngôn ngữ đó. Nếu nó là một thông báo gửi tới B (Bob), nó có thể bắt đầu với “Dear Bob”. Đoạn văn bản “Dear Bob” sẽ là một khả năng có thể hơn là một chuỗi không mang ý nghĩa gì chẳng hạn “abcd”. Mục đích của việc thám mã là sửa những tập hợp khả năng có thể có của bản mã C với mỗi khả năng có thể của bản rõ. Shannon phát triển lý thuyết cho rằng, hệ mật mã chỉ an toàn tuyệt đối nếu số khóa có thể sử dụng ít nhất phải bằng số thông báo có thể. Hiểu theo một nghĩa khác, khóa tối thiểu của hệ mật mã phải dài bằng thông báo của hệ mật mã đó. Ngoại trừ các hệ mật mã an toàn tuyệt đối, các bản mã thường chứa một số thông tin đúng với bản rõ, điều này là không thể tránh được. Một thuật toán mật mã tốt giữ cho thông tin bị tiết lộ ở mức nhỏ nhất và một người thám mã giỏi sẽ khai thác tốt những thông tin này để phát hiện ra bản rõ. Người thám mã sử dụng sự dư thừa tự nhiên của ngôn ngữ để làm giảm số khả năng có thể có của bản rõ. Nhiều thông tin dư thừa của ngôn ngữ, sẽ dễ dàng hơn cho quá trình thám mã. Chính vì lý do này mà nhiều mô hình mã hóa sử dụng thuật toán nén bản rõ để giảm kích thước văn bản trước khi mã hóa chúng. Vì quá trình nén làm giảm sự dư thừa của thông báo. Entropy của một hệ mật mã là kích thước của không gian khóa. H(K) = log2( number of keys) Shannon cũng đưa ra một khái niệm gọi là Unicity Distance (ký hiệu là U) để đánh giá độ an toàn của một hệ mật mã. Đối với một hệ mật mã U của nó là: U = H(K)/D Đây là số nhỏ nhất các bản mã cần thiết để có thể tiến hành thám mã theo cách thử tất cả các khóa có thể (brute-force attack) thành công. Chẳng hạn đối với hệ mã thay thế đơn âm (như Caesar) trên bảng chữ cái tiếng Anh ta sẽ có: Phương pháp lập mã tối ưu an toàn 22 H(K) = log226! = 27 × D = 3.4 ⇒ U = 25.5 Điều này có nghĩa là nếu chúng ta có khoảng 25 chữ cái bản mã chúng ta chỉ có thể thử để khớp với một bản rõ. Khái niệm Unicity Distance là một khái niệm mang tính xác suất nó cho chúng ta biết được số lượng ít nhất các bản mã cần có để xác định duy nhất một bản mã chứ không phải là số bản mã đủ để tiến hành thám mã (chắc chắn thành công). Nếu chúng ta có số bản mã ít hơn số U thì không thể nói là dự đoán (phép thử) của chúng ta đã đúng. Dựa vào công thức này chúng ta thấy nếu như độ dư thừa của một ngôn ngữ càng gần 0 thì càng khó thám mã mặc dù đó có thể là một hệ mật mã rất đơn giản. Cũng dựa vào công thức này suy ra để tăng tính an toàn của hệ mật mã có thể tăng không gian khóa của nó. 2.1.4 Kỹ thuật lộn xộn và rườm rà Theo Shannon, có hai kỹ thuật cơ bản để che dấu sự dư thừa thông tin trong thông báo gốc, đó là: sự lộn xộn và rườm rà. • Kỹ thuật lộn xộn (Confusion): che dấu mối quan hệ giữa bản rõ và bản gốc. Kỹ thuật này làm thất bại các cố gắng nghiên cứu bản mã để tìm kiếm thông tin dư thừa và thống kê mẫu. Phương pháp dễ nhất để thực hiện điều này là thông qua kỹ thuật thay thế. Một hệ mã hóa thay thế đơn giản, chẳng hạn như hệ mã dịch vòng Caesar, dựa trên nền tảng của sự thay thế các chữ cái của bản rõ, nghĩa là chữ cái này được thay thế bằng chữ cái khác. • Kỹ thuật rườm rà (Diffusion): làm mất đi sự dư thừa của bản rõ bằng cách tăng sự phụ thuộc bản mã vào bản rõ (và khóa). Công việc tìm kiếm sự dư thừa của người thám mã sẽ rất mất thời gian và phức tạp. Cách đơn giản nhất tạo ra sự rườm rà là thông qua việc đổi chỗ (hay còn gọi là kỹ thuật hoán vị). Thông thường các hệ mã hiện đại thường kết hợp cả hai kỹ thuật thay thế và hoán vị để tạo ra các đoạn mã có độ an toàn cao hơn. 2.2 Lý thuyết độ phức tạp Lý thuyết độ phức tạp cung cấp một phương pháp để phân tích độ phức tạp tính toán của thuật toán và các kỹ thuật mã hóa khác nhau. Nó so sánh các thuật toán mã hóa, kỹ thuật và phát hiện ra độ an toàn của các thuật toán đó. Lý thuyết thông tin đã cho chúng ta biết rằng một thuật toán mã hóa có thể bị bại lộ. Còn lý thuyết độ phức tạp cho biết khả năng bị thám mã của một hệ mật mã. Phương pháp lập mã tối ưu an toàn 23 2.2.1 Khái niệm Thời gian làm việc của máy tính khi chạy một thuật toán nào đó không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào máy tính được sử dụng. Vì thế, để có một tiêu chuẩn chung, ta sẽ đo độ phức tạp của thuật toán bằng số các phép tính phải làm khi thực hiện thuật toán. Khi thực hiện cùng một thuật toán, số các phép tính phải thực hiện còn phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này chỉ cần biết “cỡ” của chúng, tức là cần có một ước lượng đủ tốt của chúng. Trong khi làm việc, máy tính thường ghi các chữ số bằng bóng đèn “sáng/tắt”, bóng đèn sáng chỉ 1, bóng đèn tối chỉ số 0. Vì thế để thuận tiện nhất là dùng hệ đếm cơ số 2, trong đó để biểu diễn một số, ta chỉ cần dùng hai ký hiệu 0 và 1. Một ký hiệu 0 hoặc 1 được gọi là 1 bít “viết tắt của binary digit”. Một số nguyên n biểu diễn bởi k chữ số 1 và 0 được gọi là một số k-bít. Độ phức tạp của một thuật toán được đo bằng số các phép tính bít. Phép tính bít là một phép tính logic hay số học thực hiện trên các bít 0 và 1. Để ước lượng độ phức tạp của thuật toán ta dùng khái niệm bậc O lớn. Định nghĩa 2.1: Giả sử f [ n ] và g [ n ] là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f [ n ] có bậc O-lớn của g [ n ] và ta viết f [ n ] = O ( g [ n ]) , nếu tồn tại một số C > 0 sao cho với n đủ lớn. Các hàm f [ n ] và g [ n ] đều dương thì f [ n] < C g [ n] . Vi dụ 2.2: Giả sử f [ n ] là đa thức f ⎡⎣ n ⎤⎦ = a d n d + a d −1n d −1 + ... + a1n + a 0 , trong đó a d > 0 . Dễ ( ) chứng mình f [ n ] = O n d . ( ) ( ) Nếu f ⎡⎣ n ⎤⎦ = O g ⎡⎣ n ⎤⎦ , f2 ⎡⎣ n ⎤⎦ = O g ⎡⎣ n ⎤⎦ thì f1 + f2 = O ( g ) . Nếu f1 = O ( g1 ) , f2 = O ( g2 ) thì f1 f2 = O ( g1g2 ) . f ⎡⎣ n ⎤⎦ thì f = O ( g ) . n →∞ g ⎡⎣ n ⎤⎦ Nếu tồn tại giới hạn hữu hạn: lim Phương pháp lập mã tối ưu an toàn