Giáo trình An toàn và bảo mật trong mạng máy tính

162 trang huongle 3340

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình An toàn và bảo mật trong mạng máy tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_an_toan_va_bao_mat_trong_mang_may_tinh.pdf

Nội dung text: Giáo trình An toàn và bảo mật trong mạng máy tính

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH AN TOÀN VÀ BẢO MẬT TRONG MẠNG MÁY TÍNH
Giáo trình An toàn và bảo mật trong mạng máy tính MỤC LỤC MỤC LỤC 3 LỜI NÓI ĐẦU 9 CHƯƠNG 1. NHỮNG VẤN ĐỀ CƠ BẢN VỀ AN TOÀN THÔNG TIN 11 1.1 Thông tin 11 1.1.1 Các định nghĩa về thông tin 11 1.1.2 Phương tiện truyền thông 11 1.2 Khái niệm hệ thống và tài nguyên thông tin 12 1.2.1 Khái niệm hệ thống thông tin 12 1.2.2 Tài nguyên thông tin trong hệ thống thông tin 12 1.3 An ninh hệ thống thông tin 12 1.4 An toàn bảo mật hệ thống thông tin 13 1.5 Các mối đe doạ đối với một hệ thống và các biện pháp bảo vệ 14 1.5.1 Các mối đe doạ đối với một hệ thống thông tin 14 1.5.2 Các đối tượng xâm hại hệ thống 14 1.5.3 Nguyên tắc và mục tiêu chung của an toàn bảo mật thông tin 14 1.5.4 Các biện pháp bảo vệ thông tin 14 1.5.5 Các biện pháp bảo vệ mạng 15 1.6 Các thành phần chính của an toàn tin học 16 1.6.1 An toàn mức vật lý 17 1.6.2 An toàn mức tác nghiệp 17 1.6.3 Quản trị và chính sách 19 1.7 Sự không an toàn trong các dịch vụ và các giao thức 23 1.8 An toàn đồ hình mạng 27 3
Giáo trình An toàn và bảo mật trong mạng máy tính 1.8.1 Mục đích của thiết kế 27 1.8.2 Vùng bảo mật 27 1.9 Quản lý rủi ro 28 1.10 Câu hỏi và bài tập 28 CHƯƠNG 2. MẬT MÃ HỌC 29 2.1 Sơ lược về lịch sử mật mã học 29 2.2 Những khái niệm cơ bản 30 2.3 Phân loại các thuật toán mật mã 32 2.4 Ứng dụng của mật mã học 32 2.5 Số học modulo 33 2.5.1 Định nghĩa modulo 33 2.5.2 Ước số 34 2.5.3 Các phép toán số học trên modulo 34 2.5.4 Vành Zn (vành đồng dư modulo n) 35 2.5.5 Các số nguyên tố 35 2.5.6 Ước số chung lớn nhất (Greatest Common Divisor) 36 2.5.7 Nghịch đảo a-1 modulo n 37 2.5.8 Định lý Euler 39 2.6 Mã nén dữ liệu 41 2.6.1 Khái niệm cơ bản 41 2.6.2 Các phương pháp nén dữ liệu 41 2.6.3 Nén dữ liệu theo mô hình thống kê 42 2.6.4 Mã nén Huffman 43 2.6.5 Mã RLE (Run- Length- Encoding) 46 4
Giáo trình An toàn và bảo mật trong mạng máy tính 2.6.6 Mô hình từ điển 47 2.6.7 LZ77 48 2.6.8 LZ78 52 2.7 Câu hỏi và bài tập 55 2.7.1 Câu hỏi 55 2.7.2 Bài tập 55 CHƯƠNG 3. CÁC HỆ MẬT MÃ ĐỐI XỨNG 57 3.1 Định nghĩa 57 3.2 Mật mã đối xứng cổ điển 58 3.2.1 Kỹ thuật mã hóa thay thế 58 3.2.2 Kỹ thuật mã hóa hoán vị cổ điển 63 3.2.3 Điểm yếu của mã cổ điển 64 3.3 Thám mã đối xứng cổ điển 65 3.3.1 Khái niệm 65 3.3.2 Thám mã Affine bằng phương pháp thống kê 66 3.4 Mật mã dòng hiện đại 67 3.5 Mật mã khối 68 3.5.1 Nguyên lý chung 68 3.5.2 Hệ mã hóa DES 70 3.6 Câu hỏi và bài tập 77 3.6.1 Câu hỏi 77 3.6.2 Bài tập 77 CHƯƠNG 4. CÁC HỆ MẬT MÃ KHÓA CÔNG KHAI 79 4.1 Mã hóa khóa công khai 79 5
Giáo trình An toàn và bảo mật trong mạng máy tính 4.1.1 Những hạn chế của mã hóa khóa đối xứng 79 4.1.2 Mã hóa khóa công khai 79 4.2 Mã hóa khóa công khai RSA 82 4.2.1 Nguyên tắc thực hiện của RSA 83 4.2.2 Chứng minh tính đúng của RSA 84 4.2.3 Ví dụ về mã hóa bằng RSA 85 4.3 Độ phức tạp tính toán RSA 86 4.3.1 Phép tính mã hóa/giải mã 86 4.3.2 Phép tính sinh khóa 87 4.4 Độ an toàn của RSA 87 4.5 Bảo mật, chứng thực và không chối bỏ với mã hóa khóa công khai 88 4.6 Trao đổi khóa 89 4.6.1 Trao đổi khóa công khai 89 4.6.2 Dùng mã hóa khóa công khai để trao đổi khóa bí mật 90 4.7 Phương pháp trao đổi khóa Diffie – Hellman 91 4.8 Câu hỏi và bài tập 92 4.8.1 Câu hỏi 92 4.8.2 Bài tập 93 CHƯƠNG 5. HÀM BĂM VÀ XÁC THỰC THÔNG TIN 94 5.1 Xác thực thông tin 94 5.1.1 Các khái niệm 94 5.1.2 Các yêu cầu bảo mật khi truyền văn bản trên mạng 94 5.1.3 Xác thực văn bản bằng mã hóa 95 5.1.4 Xác thực văn bản bằng Mã xác thực 95 6
Giáo trình An toàn và bảo mật trong mạng máy tính 5.1.5 Các hàm băm 97 5.1.6 Các hàm băm đơn giản 98 5.2 Các hàm băm SHA và MD5 99 5.2.1 Các hàm băm SHA 99 5.2.2 Hàm băm MD5 111 5.3 Câu hỏi và bài tập 117 5.3.1 Câu hỏi 117 5.3.2 Bài tập 117 CHƯƠNG 6. AN TOÀN VÀ BẢO MẬT HỆ THỐNG THÔNG TIN TRÊN INTERNET 118 6.1 Hạ tầng mạng và những điểm yếu 118 6.1.1 Mô hình OSI và TCP/IP 118 6.1.2 Một số điểm yếu của bộ giao thức TCP/IP 122 6.2 Phần mềm độc hại – Malware 128 6.2.1 Khái niệm 128 6.2.2 Trojan và Backdoor 128 6.2.3 Virus và Worm 132 6.3 Các hình thức tấn công WLAN 134 6.3.1 Một số khái niệm về WLAN 134 6.3.2 Tấn công giả mạo điểm truy cập 135 6.3.3 Giả mạo địa chỉ vật lý 136 6.3.4 Tấn công yêu cầu xác thực lại 137 6.3.5 Tấn công dựa trên sự cảm nhận sóng mang lớp vật lý 137 6.3.6 Tấn công ngắt kết nối 137 6.4 Firewall 138 7
Giáo trình An toàn và bảo mật trong mạng máy tính 6.4.1 Khái niệm 138 6.4.2 Nguyên lý hoạt động của tường lửa 139 6.4.3 Giải pháp tường lửa cho doanh nghiệp 140 6.5 Chính sách an toàn và bảo mật thông tin trong doanh nghiệp 141 6.5.1 Các chính sách an toàn và bảo mật 141 6.5.2 Quản lý rủi ro 143 6.6 Câu hỏi và bài tập 145 6.6.1 Câu hỏi 145 Phụ lục 1. Các hoán vị và hộp S của DES 146 Phụ lục 2. Ví dụ về hàm băm SHA512 154 TÀI LIỆU THAM KHẢO 162 8
Giáo trình An toàn và bảo mật trong mạng máy tính LỜI NÓI ĐẦU Ngày nay, thông tin đang trở thành một tài nguyên quý giá của hầu hết các quốc gia trên thế giới, đặc biệt trong bối cảnh của xu hướng toàn cầu hóa và phát triển nền kinh tế tri thức. Bảo vệ thông tin và bảo đảm môi trường làm việc với nguồn tài nguyên này là nhiệm vụ tất yếu của chúng ta. Các mạng tin học là một loại môi trường lao động mới ra đời và phát triển trong xã hội văn minh hiện đại, chúng đóng vai trò rất quan trọng vì càng ngày càng có nhiều người tham gia khai thác và cung cấp thông tin trên đó. Hiện nay, môn học về bảo mật máy tính và mạng đã được đưa vào giảng dạy tại hầu hết các khoa Công nghệ Thông tin của các trường đại học và cao đẳng. Để đáp ứng yêu cầu học tập và tự tìm hiểu của sinh viên về lĩnh vực này, bộ môn Mạng máy tính và Truyền thông, khoa Công nghệ Thông tin thuộc trường Đại học Sư phạm Kỹ thuật Hưng Yên đã tổ chức biên soạn giáo trình “An toàn và bảo mật trong mạng máy tính”. Nội dung của giáo trình được biên soạn dựa vào một số tài liệu, trong đó có cuốn sách của Giáo sư William Stallings “Cryptography and Network Security: Principles and Practice”. Đồng thời, giáo trình này cũng được hoàn thiện từng bước dựa trên các bài giảng và kinh nghiệm trong thực tế bảo vệ máy tính và mạng của các giảng viên thuộc bộ môn. Với mục đích trang bị các kiến thức cơ sở vừa đủ và giúp cho sinh viên hiểu được bản chất của bảo mật máy tính và mạng, trong giáo trình này, tập thể tác giả đã cố gắng trình bày tóm tắt các phần lý thuyết cơ bản và đưa ra các ứng dụng thực tế. Giáo trình bao gồm 6 chương. Chương đầu trình bày những vấn đề cơ bản về an toàn thông tin, chương 2 giới thiệu tổng quan về mật mã học, chương 3 trình bày về các hệ mật mã đối xứng, chương 4 giới thiệu về các hệ mật mã khóa công khai, chương 5 trình bày về hàm băm và xác thực thông tin, cuối cùng, chương 6 bàn về an toàn và bảo mật hệ thông tin trên Internet. Do lần đầu biên soạn và chưa có nhiều kinh nghiệm thực tế nên không tránh khỏi những sai sót và lỗi in ấn nhất định trong nội dung của giáo trình. Chúng tôi vui lòng tiếp nhận mọi sự đóng góp giúp cho giáo trình “An toàn và bảo mật trong mạng máy tính” ngày càng tốt hơn. 9
Giáo trình An toàn và bảo mật trong mạng máy tính Cuối cùng, chúng tôi xin trân trọng cám ơn Bộ môn Mạng máy tính và Truyền thông, khoa Công nghệ Thông tin và Trường ĐH Sư phạm Kỹ thuật Hưng Yên đã tạo điều kiện thuận lợi để chúng tôi có thể hoàn thành cuốn giáo trình này. Thay mặt nhóm biên soạn CHỦ BIÊN PGS.TS Bùi Thế Hồng Các tác giả Bùi Thế Hồng Phạm Minh Chuẩn Nguyễn Đình Hân Nguyễn Duy Tân Vi Hoài Nam Nguyễn Thị Thanh Huệ Phạm Quốc Hùng 10
Giáo trình An toàn và bảo mật trong mạng máy tính CHƯƠNG 1. NHỮNG VẤN ĐỀ CƠ BẢN VỀ AN TOÀN THÔNG TIN 1.1 Thông tin 1.1.1 Các định nghĩa về thông tin Có khá nhiều định nghĩa về thông tin. Hai định nghĩa sau đây thường được sử dụng trong các tài liệu có liên quan đến thông tin. Thông tin là những tính chất xác định của vật chất mà con người (hoặc hệ thống kỹ thuật) nhận được từ thế giới vật chất bên ngoài hoặc từ những quá trình xảy ra trong bản thân nó. Thông tin là sự phản ánh sự vật, sự việc, hiện tượng của thế giới tự nhiên và các hoạt động của con người trong đời sống xã hội. Điều cơ bản là con người thông qua việc cảm nhận thông tin làm tăng hiểu biết cho mình và tiến hành những hoạt động có ích cho cộng đồng. Thông tin được lưu trữ trên nhiều dạng vật liệu khác nhau như được khắc trên đá, được ghi lại trên giấy, trên bìa, trên băng từ, đĩa từ, đĩa cứng, thẻ nhớ, Thông tin chính là tất cả những gì mang lại hiểu biết cho con người mà con người tri thức được. Con người luôn có nhu cầu thu thập thông tin bằng nhiều cách khác nhau: đọc báo, nghe đài, xem truyền hình, truy cập mạng Internet, giao tiếp với người khác một cách trực tiếp hoặc thông qua các diễn đàn điện tử và mạng xã hội, Thông tin làm tăng hiểu biết của con người, là nguồn gốc của nhận thức và là cơ sở để đưa ra quyết định. 1.1.2 Phương tiện truyền thông Môi trường vận động thông tin là môi trường truyền tin, nó bao gồm các kênh liên lạc tự nhiên hoặc nhân tạo như sóng âm, tia sáng, dây dẫn, sóng âm thanh, sóng h́nh, sóng vô tuyến, Kênh liên lạc thường nối các thiết bị, máy móc lại với nhau hay nối với con người. Con người có hình thức liên lạc tự nhiên và cao cấp là tiếng nói, từ đó nghĩ ra chữ viết. Ngày nay nhiều công cụ hiển thị và truyền bá thông tin đã xuất hiện như bút viết, máy in, điện tín, điện thoại, phát thanh, truyền hình, phim ảnh rồi đến máy tính, mạng máy tính và đặc biệt là mạng Internet. Về nguyên tắc,bất kỳ cấu trúc vật chất nào hoặc bất kỳ dòng năng lượng nào cũng có thể mang thông tin. Các vật có thể mang thông tin được gọi là giá mang tin. Thông tin luôn mang một ý nghĩa xác định nhưng hình thức thể hiện của thông tin thì rõ ràng mang tính quy ước. Chẳng hạn ký hiệu "V" trong hệ đếm La Mã mang ý nghĩa 11
Giáo trình An toàn và bảo mật trong mạng máy tính là 5 đơn vị nhưng trong hệ thống chữ La tinh nó mang nghĩa là chữ cái V. Trong máy tính điện tử, nhóm 8 chữ số 01000001 nếu là số sẽ thể hiện số 65, còn nếu là chữ sẽ là chữ "A" theo bảng mã ASCII. Có nhiều cách phân loại thông tin nhưng cách phân loại dựa vào đặc tính liên tục hay rời rạc của tín hiệu vật lý là hay được sử dụng hơn. Tương ứng, thông tin sẽ được chia thành thông tin liên tục và thông tin rời rạc. 1.2 Khái niệm hệ thống và tài nguyên thông tin 1.2.1 Khái niệm hệ thống thông tin Hệ thống thông tin là một tập hợp các máy tính gồm phần cứng, phần mềm và dữ liệu làm việc, được tích luỹ qua thời gian. 1.2.2 Tài nguyên thông tin trong hệ thống thông tin Một hệ thống thông tin thường bao gồm những tài nguyên sau đây: Phần cứng; Phần mềm; Dữ liệu; Môi trường truyền thông; Môi trường làm việc; Con người. 1.3 An ninh hệ thống thông tin ISO (International Organization for Standardization), Tổ chức quốc tế lớn nhất về tiêu chuẩn hóa mà Việt Nam đang tham gia, đã định nghĩa: Định nghĩa: An ninh (security) là sự hạn chế khả năng lạm dụng tài nguyên (resouces) và tài sản (assets). Trong công nghệ thông tin, an ninh là việc sử dụng các công nghệ, quy trình, thiết bị, để bảo vệ thông tin (information), tài nguyên và tài sản [1]. An ninh trở nên đặc biệt phức tạp trong quản lý, vận hành những hệ thống thông tin có sử dụng các công cụ tin học. Tại đây có thể xảy ra và lan tràn nhanh chóng việc lạm dụng tài nguyên (các thông tin di chuyển vô hình trên mạng hoặc lưu trữ hữu hình trong các vật liệu) và lạm dụng tài sản (các máy tính, thiết bị mạng, thiết bị ngoại vi, các loại phần mềm của cơ quan hoặc người sở hữu hệ thống). Trong bối cảnh rộng lớn như vậy, để bao hàm ý nghĩa của các thuật ngữ tiếng Anh “information security” (thiên về mặt tài nguyên), cũng như “computer security” và “network security” (thiên về mặt tài sản), 12
Giáo trình An toàn và bảo mật trong mạng máy tính có thể định nghĩa an ninh tin học là những hoạt động nhằm hạn chế khả năng lạm dụng tài nguyên và tài sản tin học. Trong định nghĩa trên, từ "hạn chế" hàm ý rằng không thể triệt phá hết ngay việc lạm dụng, cho nên cần sẵn sàng đề phòng mọi khả năng xấu với các phương cách thích hợp và chuẩn bị xử lý các sự cố nếu có việc lạm dụngxảy ra. Mà nói đến "lạm dụng" tức là đề cập đến yếu tố con người, do đó phải áp dụng các chính sách và biện pháp tổ chức tương ứng với từng loại đối tượng có khả năng cố tình hoặc vô ý vi phạm việc sử dụng đúng đắn những tài nguyên và tài sản tin học trên toàn bộ hệ thống. 1.4 An toàn bảo mật hệ thống thông tin Định nghĩa: Sự an toàn (safety) của hệ thống thông tin thực chất là sự đảm bảo an ninh tin học ở mức độ chấp nhận được. Những hoạt động đề phòng và xử lý sự cố đòi hỏi một loạt cố gắng tinh thần với các chi phí vật chất; chúng tỷ lệ thuận với khả năng và mức độ an toàn, nhưng nếu chúng ta không ý thức đầy đủ những điều nói trên thì mối nguy hiểm vẫn có thể vượt khỏi vòng kiểm soát, gây ra tai hoạ và sự lãng phí. Muốn hệ thống thông tin an toàn thì trước hết phải có sự đảm bảo thông tin (information assurance) trên cơ sở hạ tầng mạng truyền dữ liệu thông suốt. Sau chữ an toàn thường có chữ bảo mật để mở rộng khía cạnh đảm bảo bí mật về nội dung thông tin. Như vậy, an toàn bảo mật hệ thống thông tin là đảm bảo hoạt động lưu thông và nội dung bí mật cho những thành phần của hệ thống ở mức độ chấp nhận được. Hai yếu tố an toàn và bảo mật đều rất quan trọng và gắn bó với nhau. Hệ thống mất an toàn thì không bảo mật được và ngược lại hệ thống không bảo mật được thì mất an toàn. Tuy nhiên, có thể phân biệt chúng rõ ràng hơn bằng những định nghĩa cụ thể như sau: Một hệ thống sẽ là an toàn khi các khiếm khuyết không thể làm cho các hoạt động chủ yếu của nó ngừng hẳn và các sự cố nếu xảy ra sẽ được khắc phục một cách kịp thời mà không gây thiệt hại đến mức độ nguy hiểm cho chủ sở hữu. Một hệ thống được coi là bảo mật (confident, secure) nếu tính riêng tư của nội dung thông tin được đảm bảo theo đúng các chỉ tiêu trong một thời gian xác định. Sở dĩ phải nêu những điều kiện như vậy bởi vì mọi sự việc đều chỉ có tính tương đối, thí dụ ngày nay đã có những máy tính rất mạnh và có thể giải mã được các bức điện mật trong thời gian khoảng một tuần. 13
Giáo trình An toàn và bảo mật trong mạng máy tính Phân tích theo mô hình OSI của Tổ chức ISO, sự an toàn của hệ thống thông tin được thực hiện chủ yếu ở các tầng dưới (hạ tầng mạng phải đảm bảo lưu thông an toàn), còn việc bảo mật nội dung thông tin được thực hiện ở các tầng trên (các phần mềm ứng dụng phải đảm bảo việc mật mã hoá và giải mã). Thông tin có ý nghĩa đúng hay sai và sai đến mức nào là tuỳ thuộc vào việc đánh giá của con người chứ máy móc không thể tự quyết định. 1.5 Các mối đe doạ đối với một hệ thống và các biện pháp bảo vệ 1.5.1 Các mối đe doạ đối với một hệ thống thông tin Phá hoại: phá hỏng thiết bị phần cứng hoặc phần mềm trên hệ thống; Sửa đổi: tài sản của hệ thống bị sửa đổi trái phép; Can thiệp: tài sản bị truy cập bởi những người không có thẩm quyền, bị đánh cắp mật khẩu, bị mạo danh, 1.5.2 Các đối tượng xâm hại hệ thống Các đối tượng sau đây là các mối đe dọa đối với các hệ thống thông tin. Từ bên trong hệ thống: đây là những người có quyền truy cập hợp pháp đối với hệ thống; Từ bên ngoài hệ thống: tin tặc, bẻ khóa, ; Phần mềm: virut, do thám và các lỗ hổng trong các hệ điều hành và các chương trình ứng dụng. 1.5.3 Nguyên tắc và mục tiêu chung của an toàn bảo mật thông tin Hai nguyên tắc của an toàn bảo mật thông tin là Việc thẩm định về bảo mật phải đủ khó và cần tính tới tất cả các tình huống, khả năng tấn công có thể được thực hiện. Tài sản phải được bảo vệ cho tới khi hết gía trịsử dụng hoặc hết ý nghĩa bí mật. 1.5.4 Các biện pháp bảo vệ thông tin Khi người sử dụng hệ thống thông tin thay đổi một thông tin nào đó thì sẽ trở thành chủ sở hữu (owner) của thông tin đã thay đổi. Nhưng khi trao đổi một thông tin, thông tin đó chỉ có giá trị cao nhất đối với chủ sở hữu của nó và những đối tượng được phép truy cập nó hoặc những người nhận, nếu nó đảm bảo được 4 đặc điểm có tính chất nguyên tắc sau đây: 14
Giáo trình An toàn và bảo mật trong mạng máy tính a) Tính sẵn sàng Có tính sẵn sàng, hay truy cập được (availability, accessibility), nghĩa là thông tin phải có thể lấy được vào bất cứ lúc nào theo yêu cầu của chủ sở hữu và người sử dụng. b) Tính toàn vẹn Có tính toàn vẹn (integrity) nghĩa là thông tin không bị thay đổi (thêm, bớt, xoá bỏ) ngoài ý muốn của chủ sở hữu, trước khi sang tay người sử dụng. c) Tính riêng tư Có tính riêng tư, hay bí mật (privacy, confidentiality), nghĩa là nội dung thông tin của chủ sở hữu không bị người khác (trừ người sử dụng hợp pháp) đọc trộm, nghe trộm hoặc hiểu được. d) Tính trách nhiệm Có tính trách nhiệm, hay không chối bỏ (non-repudiation), nghĩa là chủ sở hữu và người sử dụng không thể phủ nhận việc đã gửi và nhận thông tin của nhau ở các thời điểm chính xác. Bảo vệ thông tin là thực hiện mọi biện pháp cần thiết của quản trị để đảm bảo duy trì 4 tính chất vừa kể, làm cho hệ thống phục vụ được các yêu cầu chính đáng của chủ sở hữu và người sử dụng thông tin. Người quản lý tức người quản trị mạng và người quản trị việc bảo mật (nếu hệ thống nhỏ thì một nhân viên có thể kiêm cả hai nhiệm vụ này) không được vi phạm những nguyên tắc nói trên, cũng như không được lạm dụng quyền hạn và phương tiện của mình trong khi bảo vệ thông tin. 1.5.5 Các biện pháp bảo vệ mạng Người quản lý phải cố gắng đảm bảo được 4 yêu cầu có tính chất cơ bản của mạng tin học là an toàn, tin cậy, dễ mở rộng và dễ quản trị. Những yêu cầu đó được giải thích cụ thể như sau. a) Tính an toàn An toàn (Safe): các luồng giao thông (traffic) trên mạng không bị tuỳ ý thay đổi tốc độ, chiều hướng, không bị va chạm, ách tắc và nhất là không bị đứt đoạn đường truyền. Trừ những trường hợp bất khả kháng (chiến tranh, thiên tai v.v ), một mạng được gọi là an toàn phải có khả năng làm việc như thế, liên tục suốt 24 giờ mỗi ngày và 7 ngày mỗi tuần mà không có sự cố nào kéo dài quá một giới hạn quy định (thí dụ 10 phút). Hiện nay, tin tặc chủ yếu dùng kiểu tấn công từ chối phục vụ (Deny of Service – DoS) để gây nghẽn mạng và do đó phá hoại tính an toàn. 15
Giáo trình An toàn và bảo mật trong mạng máy tính b) Tính tin cậy Tin cậy (Reliable): các thông tin được truyền đi theo thời biểu chính xác trong một giới hạn cho phép, gửi đến đúng địa chỉ người nhận và bảo toàn nội dung của mình y nguyên như khi xuất phát. Phải có đầy đủ các biện pháp theo dõi, kiểm tra, xử lý, ghi chép và báo cáo để mạng vận hành được như vậy. c) Tính dễ mở rộng Dễ mở rộng (Scaleable, Extendable): chủ sở hữu mạng và người quản trị mạng có thể mở rộng phạm vi hoạt động của mạng, dễ dàng lắp đặt, nâng cấp các thiết bị và phần mềm mạng mà ít gây ảnh hưởng đến những người sử dụng và thông tin lưu truyền trên đó. d) Tính dễ quản trị Dễ quản trị (Manageable): người quản trị mạng có thể quan sát, theo dõi, can thiệp việc sử dụng các tài nguyên mạng và quyền truy cập của những người sử dụng một cách đơn giản, thuận tiện và trực tuyến (online). Thông tin (tài nguyên) và mạng tin học (tài sản) là hai bộ phận gắn bó rất chặt chẽ với nhau. Mạng tin học được hiểu như một hệ thống thông tin điện tửbao gồm những người sử dụng và quản lý, các máy tính xử lý dữ liệu, các thiết bị lưu trữ và kết nối, trao đổi dữ liệu. Dữ liệu được xử lý, lưu trữ và trao đổi qua lại giữa những thành phần trong mạng như vậy cho nên ở mọi nơi nó phải đối mặt với khả năng bị đọc trộm hoặc sao chép, thất thoát, thậm chí có thể bị thay đổi hoặc tăng thêm một cách trái phép vì nguyên nhân từ trong hoặc từ ngoài, dù vô tình hay cố ý. Như đã nói, an ninh tin học chủ yếu bao gồm các hoạt động phát hiện, nghiên cứu, phân tích, đánh giá và thực hiện các biện pháp phòng chống sự lạm dụng thông tin trên mạng, cho nên cũng gần như đồng nghĩa với công tác an ninh mạng (Network Security). Ngày nay, số lượng các mạng tin học đã tăng lên hàng triệu và đạt tổng giá trị hàng trăm tỷ đô-la, vì vậy công tác này vừa hữu ích vừa mang lại lợi nhuận đáng kể. 1.6 Các thành phần chính của an toàn tin học Một hệ thống thông tin cần phải được trang bị một hệ thống an toàn, bảo mật bao gồm ba mức sau đây. An toàn mức vật lý; An toàn mức tác nghiệp; Quản lý và chính sách. Các thành phần này tạo thành một tam giác an toàn thông tin cho hệ thống. 16
Giáo trình An toàn và bảo mật trong mạng máy tính Vật lý QL và CS Tác nghiệp Hình 1-1: Tam giác an toàn thông tin 1.6.1 An toàn mức vật lý An toàn ở mức vật lý là sự bảo vệ thông tin và tài sản của hệ thống chống lại các truy cập vật lý trái phép và không hợp lệ. Đảm bảo an toàn mức vật lý tương đối dễ thực hiện. Biện pháp bảo vệ đầu tiên là làm sao cho vị trí của tổ chức càng ít trở thành mục tiêu tấn công càng tốt. Biện pháp bảo vệ thứ hai là phát hiện và ngăn chặn các kẻ đột nhập và kẻ trộm bằng các hệ thống phát hiện từ xa như sử dụng máy quay phim và các thiết bị chống trộm cắp. Biện pháp bảo vệ thứ ba là các biện pháp trang bị các thiết bị dùng để khôi phục những dữ liệu hay hệ thống quan trọng sau khi bị trộm cắp hay mất mát. 1.6.2 An toàn mức tác nghiệp Tác nghiệp (hoặc vận hành) hệ thống một cách an toàn liên quan đến những gì mà một tổ chức cần thực hiện để đảm bảo một chính sách an toàn. Việc vận hành này bao gồm cả hệ thống máy tính, mạng, hệ thống giao tiếp và quản lý thông tin. Vì vậy, vận hành an toàn bao hàm một lĩnh vực rộng lớn và cần phải được quan tâm một cách thích đáng. a) Quy trình vận hành an toàn Những vấn đề đặt ra cho vận hành an toàn bao gồm: Kiểm soát truy cập; Xác thực; An toàn topo mạng sau khi được thiết lập. Các thao tác an toàn trên đây không liên quan đến việc bảo vệ ở mức vật lý và mức thiết kế. 17
Giáo trình An toàn và bảo mật trong mạng máy tính Quy trình thao tác an toàn là sự kết hợp của tất cả các quá trình, các chức năng và các chính sách bao gồm cả yếu tố con người và yếu tố kỹ thuật. Yếu tố con người tập trung vào các chính sách được thực thi trong tổ chức. Yếu tố kỹ thuật bao gồm các công cụ được cài đặt vào hệ thống. Quá trình an toàn này được chia thành nhiều phần và được mô tả dưới đây. Phần mềm chống virus (Antivirus) Virus máy tính là vấn đề phiền toái nhất hiện nay. Các phương thức chống virus mới ra đời cũng cần tiến kịp sự xuất hiện của chúng. Vì vậy, cần phải cài đặt và vận hành các chương trình phòng chống virus trực tuyến. Các chương trình và các tệp dữ liệu dùng để chống virus phải được cập nhật thường xuyên để đảm bảo hệ thống có thể chống lại những virus mới xuất hiện. Kiểm soát truy cập Cần phải thiết lập một cơ chế kiểm soát những kiểu truy cập sau. Kiểm soát truy cập bắt buộc (MAC – Mandatory Access Control) bằng cách sử dụng một tập các quyền truy cập được định nghĩa trước đối với các file trong hệ thống. Kiểm soát truy cập tự do (DAC – Discretionary Access Control) bằng cách thiết lập một danh sách cấp quyền truy cập và kiểm soát truy cập tự do (ACL – Access Control List ). Việc này do quản trị mạng thực hiện dưới sự chỉ đạo của lãnh đạo tổ chức. Kiểm soát truy cập theo chức năng nhiệm vụ (RBAC-Role Based Access Control) được xác định trước theo đúng chức năng, nhiệm vụ, quyền hạn của từng người sử dụng trong hệ thống. Xác thực (Authentication) Cần phải xây dựng, cài đặt và vận hành một hệ thống Định danh và Xác thực (Identification & Authentication - I&A) đối với tất cả những người sử dụng hệ thống. Có thể sử dụng ba yếu tố sau đây để tiến hành thiết lập hệ thống I&A: “Something you know” như mật mã hay số PIN (Personal Identification Number:); “Something you have” như thẻ thông minh, thiết bị chứng thực; “Something you own” như dấu vân tay, võng mạc mắt của người sử dụng. Hiện tại có thể sử dụng những phương thức xác thực thông dụng sau đây: 18
Giáo trình An toàn và bảo mật trong mạng máy tính Dùng Username/Password: Một tên truy cập và một mật khẩu là định danh duy nhất để đăng nhập. Máy chủ sẽ so sánh những thông tin này với những thông tin lưu trữ trong máy tính bằng các phương pháp xử lý bảo mật và sau đó quyết định chấp nhận hay từ chối sự đăng nhập. Giao thức chứng thực CHAP – (Challenge HandShake Authentication Protocol) Chứng chỉ (Certificate Authority - CA) Bảo mật bằng Token Phương pháp Kerberos Chứng thực bằng thẻ thông minh (Smart Card) Chứng thực bằng sinh trắc học (Biometric) b) Những vấn đề cần lưu ý khi xây dựng quy trình an toàn bảo mật Cần xây dựng một quy trình phù hợp với trình độ và năng lực của nhân viên và hệ thống. Không nên tiêu tốn quá nhiều thời gian và tiền bạc vào những hệ thống an toàn phức tạp khi chưa có một chính sách an toàn phù hợp. Hãy cẩn thận với khuynh hướng sử dụng những tên người dùng thông dụng và những mật khẩu dễ đoán như :”123” hoặc “ abcd” Sử dụng xác thực và đảm bảo an toàn đa yếu tố gồm một thẻ thông minh và một mật khẩu bí mật. 1.6.3 Quản trị và chính sách Chính sách quản trị an toàn và an ninh thông tin cần phải thỏa mãn những yêu cầu sau đây: Cung cấp những hướng dẫn, những quy tắc, và những quy trình để thiết lập một môi trường thông tin an toàn. Hỗ trợ toàn diện và triệt để từ phía các nhà quản lý trong tổ chức. Một số chính sách quan trọng sau đây cần phải được quán triệt trong toàn bộ tổ chức: Chính sách nhà quản lý và người sử dụng; Các yêu cầu thiết kế; 19
Giáo trình An toàn và bảo mật trong mạng máy tính Kế hoạch khôi phục sau một biến cố; Chính sách sử dụng thông tin; Chính sách an toàn; Chính sách về cách sử dụng. Trong những chính sách trên đây, chính sách đối với người quản lý và người sử dụng là quan trọng nhất. a) Chính sách người quản trị và người sử dụng Công tác an ninh cho một mạng tin học bao gồm từ việc duy trì hoạt động trôi chảy của mọi thành phần mạng, đến việc tự giác tuân thủ quy trình thao tác của từng người sử dụng và người quản lý, để các dữ liệu trong khi lưu thông, xử lý hoặc lưu trữ, vẫn đảm bảo được tính toàn vẹn và riêng tư đối với chủ sở hữu của chúng. Muốn đạt được những điều nói trên, người sử dụng và người quản lý trước hết phải không ngừng theo dõi và phát hiện mọi nguy cơ tiềm ẩn trong mạng cũng như sự tấn công từ bên ngoài, đồng thời học hỏi và tuyên truyền để cùng nắm vững và thi hành những phương pháp phòng ngừa, sẵn sàng khắc phục tối đa các sự cố có thể xảy ra, thậm chí đủ khả năng phản công và phát hiện vị trí hoặc kỹ thuật của tin tặc. Những nhiệm vụ như thế chỉ có thể làm tốt được bởi những con người vừa đáng tin cậy vừa có đủ tri thức cần thiết. Hơn thế nữa cần phải tạo lập được giữa họ một mối quan hệ tập thể, bao hàm cả sự phụ thuộc và giúp đỡ lẫn nhau trong tinh thần đồng đội. Bảo vệ thiết bị, dữ liệu và phần mềm mới chỉ là một phần trong những biện pháp kỹ thuật của an ninh tin học. Kinh nghiệm thực tiễn cho thấy còn cần đặc biệt chú ý tới phương pháp làm việc công nghiệp và các biện pháp tổ chức. An ninh tin học rất liên quan, thậm chí tuỳ thuộc vào ý thức và hành động của con người, nhất là trong điều kiện hiện nay của Việt Nam, nơi các phương pháp thủ công vẫn còn chiếm chỗ hàng đầu. Chương trình cải cách hành chính nhà nước giai đoạn 2001-2010 đang thay đổi các lề lối làm việc hiện hành, đa số những quy trình trong đó cần được tin học hoá và trở nên minh bạch nhằm có thể hội nhập khu vực và thế giới. Một trong những hành động cải cách là xây dựng hành lang pháp lý cho các giao dịch điện tử, chủ yếu sẽ dùng trong hành chính và thương mại. Điều này cũng tạo điều kiện và gắn liền với các nhiệm vụ đảm bảo an toàn hệ thống cho mạng thông tin. Mục đích của mạng là để chia sẻ thông tin, vì vậy, chúng ta phải làm sao để việc thực hiện an ninh tin học không bị hiểu sai, lạm dụng hoặc biến nó thành lý do cát cứ 20
Giáo trình An toàn và bảo mật trong mạng máy tính thông tin. Mặt khác lại không thể để chi phí cho nó tăng lên quá mức, giống như chi phí bảo vệ kho không thể đắt hơn giá trị hàng hóa chứa trong kho. Những người sử dụng cần tích cực giúp đỡ, nhắc nhở lẫn nhau, nghiêm túc tuân theo nội quy cơ quan và mọi hướng dẫn hợp pháp của người quản lý. Trước hết họ phải cảnh giác, tự bảo vệ phần cứng, phần mềm, mật khẩu và thông tin, dữ liệu của chính mình và của mạng; không được tự tiện cho người khác biết mật khẩu hoặc đưa vào mạng những phần mềm, dữ liệu và thiết bị không rõ nguồn gốc. Là người tham mưu và thực thi chính sách an ninh thông tin cho cơ quan hoặc chủ sở hữu mạng, người quản lý chịu trách nhiệm nắm vững tình hình cụ thể để kịp thời thông báo, nhắc nhở, quản trị, huấn luyện và phục vụ người sử dụng. Công việc quản trị bao gồm sao lưu dữ liệu, ghi nhật ký, viết báo cáo, phân loại người sử dụng, cấp phát, theo dõi hoặc cắt bỏ các chương khoản của người sử dụng và của các nhóm người sử dụng, v.v Người quản lý có quyền truy cập và phân phối mọi tài nguyên trên mạng nhưng phải tự giác không được soi mói vào các thông tin riêng của những người sử dụng hoặc tuỳ tiện cấm đoán, hạn chế những quyền lợi chính đáng của họ. b) Các yêu cầu về thiết kế để đảm bảo an toàn cho hệ thống Hệ thống cần phải được thiết kế để có thể đối phó với các rủi ro về an toàn. Những yêu cầu này là rất căn bản trong phần thiết kế ban đầu và nó có ảnh hưởng rất lớn đến các giải pháp được sử dụng. Các chính sách thiết kế phải được mô tả thật rõ ràng và phải đảm bảo được các yêu cầu bảo mật. c) Kế hoạch khôi phục sau biến cố Khôi phục lại hệ thống sau biến cố là một trong những vấn đề nhức đầu nhất mà các chuyên gia CNTT phải đối mặt. Cần phải bỏ rất nhiều công sức và tiền của để thực hiện việc kiểm tra, sao lưu, thiết lập hệ thống dự phòng sao cho có thể giữ cho hệ thống hoạt động liên tục. Hầu hết các công ty lớn đều đầu tư một số tiền lớn vào kế hoạch khôi phục bao gồm việc sao lưu dữ liệu và lập ra các địa điểm, gọi là “điểm nóng”, được thiết kế để cung cấp các dịch vụ nhanh chóng và thuận tiện nhất khi có sự cố xảy ra như hệ thống mạng bị sập hoặc bị “lụt”. d) Chính sách thông tin Cần phải xây dựng và ban hành một chính sách chi tiết về quyền truy suất, phân loại, đánh dấu và lưu trữ, chuyển giao và tiêu huỷ những thông tin nhạy cảm. Để phát triển chính sách thông tin cần phải tiến hành xem xét, đánh giá, xếp loại các mức độ an toàn và bảo mật của từng loại thông tin. 21
Giáo trình An toàn và bảo mật trong mạng máy tính e) Chính sách bảo mật Xây dựng và thực hiện một chính sách bảo mật bao gồm những biện pháp sau đây: Cấu hình hệ thống và mạng tối ưu thông qua việc cài đặt và cấu hình một cách hợp lý các phần mềm, phần cứng và các kết nối mạng. Xác định và ủy quyền một cách rõ ràng quy chế điều khiển truy cập, kiểm toán và kết nối mạng. Cài đặt các phần mềm mã hóa và chống virus để thực thi chính sách bảo mật. Thiết lập các chức năng và các phương thức dùng để lựa chọn mật mã, thay đổi khóa bí mật, ngăn ngừa các truy cập bất hợp pháp và những tấn công gây hại cho hệ thống. f) Chính sách sử dụng thông tin Xây dựng và thực hiện một chính sách sử dụng thông tin liên quan đến những vấn đề sau: Thông tin về nguồn tài nguyên được sử dụng như thế nào, với mục đích gì. Những quy định về cách sử dụng máy tính như cách thức đăng nhập, các quy định về mật khẩu, về an toàn vật lý nơi làm việc, Những quy định về sự riêng tư, quyền sở hữu và những hậu quả khi có những hành động không hợp pháp. Các quy định về việc sử dụng các chương trình truy cập Internet và Email. g) Chính sách an toàn thông tin Mục đích của an toàn thông tin rất rõ ràng và nó được lập thành một bộ khung để có thể căn cứ vào đó mà phát triển và duy trì một kết hoạch bảo vệan toàn thông tin. Mục đích của an toàn thông tin bao gồm: Phòng ngừa Ngăn chặn các hành động xâm phạm máy tính hay thông tin một cách phạm pháp. Thiết lập các chính sách và các chức năng của hệ thống an toàn nhằm giảm thiểu nguy cơ bị tấn công. Chính sách ngăn chặn càng tốt thì mức độ thành công của các cuộc tấn công càng thấp. Phát hiện Xác định các sự kiện khi nó đang thực hiện. Trong nhiều trường hợp việc phát hiện này rất khó thực hiện. 22
Giáo trình An toàn và bảo mật trong mạng máy tính Sử dụng một số công cụ đơn giản hoặc phức tạp, kiểm tra các logfile Tiến hành thường xuyên liên tục các biện pháp trên. Đáp trả Phát triển các chiến lược và kỹ thuật yếu từ đơn giản đến phức tạp để có thể đáp trả các cuộc tấn công. Tạo ra các chức năng và phương thức cho việc khôi phục lại tài nguyên sau khi bị tấn công. 1.7 Sự không an toàn trong các dịch vụ và các giao thức Mỗi dịch vụ và giao thức được sử dụng sẽ làm tăng tính dễ bị tấn công của hệ thống và làm cho xuất hiện các vấn đề tiềm năng về an ninh trong hệ thống. Hàng ngày người ta tìm được những lổ hổng mới cho các dịch vụ và giao thức được sử dụng phổ biến trong hệ thống mạng máy tính. Trong thực tiễn, để các hệ thống khác nhau từ nhiều nhà sản xuất khác nhau có thể nối kết được với nhau, thì những hệ thống này phải mở thông qua các giao diện và giao thức được chuẩn hóa. Mà chuẩn hoá cũng đồng nghĩa với việc công bố các đặc tả kỹ thuật cho mọi người đều biết. Nhưng việc công bố và áp dụng rộng rãi các tiêu chuẩn này cũng tạo ra một cơ hội cho tin tặc lợi dụng và khai thác chúng. Đối chiếu từng công nghệ của những mạng tin học cụ thể với mô hình OSI, ta có thể thấy rằng các mối nguy hiểm có thể tiềm tàng ngay trong từng bộ phận, thành phần, đặc biệt ở các giao thức được sử dụng phổ biến nhất. Bộ giao thức TCP/IP hiện đang được sử dụng rộng rãi nhất thế giới bởi mạng toàn cầu Internet và các mạng cục bộ kiểu Ethernet đều áp dụng nó. Sau đây là một số kẽ hở đã được phát hiện trong những giao thức chính thuộc họ TCP/IP. Rất may là phần lớn những kẽ hở này sau đó đã được khắc phục bởi các bản phần mềm nâng cấp. Dưới đây là một số kẽ hở bị lợi dụng đã được phát hiện trong các giao thức phổ dụng. a) Kẽ hở trong giao thức SMTP Trong giao thức chuyển thư điện tử đơn giản SMTP (Simple Mail Transfer Protocol) vốn không có cơ chế xác thực (Authentication), cho nên thư điện tử rất dễ bị kẻ xấu mạo danh (Spoofed). Nếu mail server được thiết lập để cho phép nối cổng SMTP thì bất cứ ai cũng có thể đưa đến đó những lệnh chuyển một bức thư điện tử với địa chỉ người gửi tùy ý, gây ra lẫn lộn thật giả rất tai hại (trường hợp của phần lớn các virus mới). 23
Giáo trình An toàn và bảo mật trong mạng máy tính b) Kẽ hở trong giao thức LDAP Việc kết nối trong giao thức điều khiển truy cập các cấu trúc thư mục (LDAP - Lightweight Directory Access Protocol) được máy trạm thực hiện trực tiếp qua cổng 389, trước khi yêu cầu LDAP làm những việc như tìm kiếm (Search), bổ sung (Add), Không có gì bảo đảm rằng máy trạm sẽ kết nối đến đúng máy chủ LDAP mà người dùng muốn truy cập đến bởi vì trong CSDL, tên miền (DNS) tin tặc có thể thay tên máy chủ LDAP thành máy chủ LDAP khác. Hoặc tin tặc cũng có thể cài đặt máy chủ LDAP của hắn lên máy chủ LDAP của người dùng. Mặt khác, mọi thông tin trao đổi giữa máy trạm và máy chủ LDAP đều ở dạng dữ liệu "rõ" (Plain Text), tức là chưa được mã hóa, nên tin tặc dễ dàng đọc và thay đổi được. c) Kẽ hở trong giao thức HTTP Giao thức chuyển siêu văn bản HTTP (HyperText Transfer Protocol) phiên bản 1.0 về cơ bản không cung cấp sơ đồ an toàn nào để trong phiên làm việc xác thực được những người sử dụng. Từ kẽ hở này sẽ nảy sinh ra các vấn đề sau: Thông tin ký tự ở máy chủ Web (Server Log Information) có thể bị lạm dụng và làm hại bởi những người sử dụng. Các công ty phần mềm viết các chương trình máy khách (Client) và tự đảm bảo độ an toàn của chúng. Người sử dụng đành phải tin vào sự tuyên truyền quảng cáo về năng lực của những công ty này. Thông tin chuyển tải không được an toàn mặc dù trong đó có thể chứa các nội dung cần giữ kín, thí dụ thư riêng hoặc mã số của thẻ tín dụng cá nhân, v.v d) Kẽ hở trong giao thức DHCP Giao thức cấu hình động (Dynamic Host Configuration Protocol – DHCP) cung cấp cơ chế gán các địa chỉ IP động cho những thiết bị mạng để chúng có địa chỉ IP khác nhau mỗi khi nối vào mạng. Trong giao thức này tồn tại một kẽ hở gây ra lỗi tràn bộ đệm hướng ngăn xếp (Stack-Based) và nó có thể bị khai thác bằng cách gửi một thông điệp DHCP có chứa một giá trị tên máy chủ (Hostname) lớn. e) Kẽ hở trong giao thức FTP FTP (File Transfer Protocol) là một giao thức có nhiều kẽ hở lớn, kể cả khi được tăng cường bằng các cơ chế an ninh như IPsec (IP security) và SSH (Secure Socket Shell). Nhưng dù bất ổn như thế, cho đến nay trong thực tiễn FTP vẫn rất hay được dùng để tải các tệp tin lên máy chủ ở xa. Sau đây là một số trường hợp sơ hở của FTP: Khi gửi lệnh PASV 24
Giáo trình An toàn và bảo mật trong mạng máy tính Khi nạn nhân (client FTP) gửi lệnh truyền tệp thụ động (PASV), một tin tặc có thể nhanh tay kết nối vào cổng TCP của máy chủ FTP trước nạn nhân này. Có thể so sánh địa chỉ đó với địa chỉ IP của máy khách để phát hiện tin tặc, nhưng biện pháp này sẽ vô nghĩa nếu tin tặc dùng chung (ở chế độ đa người dùng - multiuser) cùng một máy trạm hoặc máy proxy với nạn nhân (vì thế từ 1999 CERT đã khuyến nghị bỏ proxy FTP). Có thể đề phòng bằng cách thiết lập cấu hình sao cho hệ điều hành từ chối mọi tín hiệu yêu cầu SYN sau yêu cầu đầu tiên, nhưng một số hệ điều hành lại không cho thiết lập như vậy. Có thể cắt bỏ cuộc truyền nếu kiểm tra thấy có nhiều kết nối cùng được chấp nhận bằng ACK trên một cổng, nhưng biện pháp này không chắc chắn vì tín hiệu ACK cũng có khi bị mất hoặc trễ. Khi gửi lệnh PORT Khi máy khách FTP (nạn nhân) gửi lệnh PORT rồi chờ, một tin tặc có thể kịp kết nối riêng với máy chủ và được máy chủ cho truy cập vào cổng TCP của máy khách. Nạn nhân không thể phân biệt vì nó là kết nối của máy chủ hợp pháp. Khi máy chủ kết nối Một tin tặc có thể yêu cầu máy chủ FTP cho kết nối vào cổng TCP với địa chỉ IP bất kỳ và gửi một tệp được chọn bởi chính tin tặc. Đó là kẽ hở nghiêm trọng nếu máy chủ này có quyền nối kết tường lửa hoặc các cổng đặc biệt khác. f) Giao thức Telnet Bản thân giao thức Telnet không có cơ chế đảm bảo an ninh. Khi cài đặt phần mềm thực hiện giao thức Telnet thường phải bổ sung các tuỳ chọn. Trong trường hợp phổ biến nhất, như một thiết bị đầu cuối (terminal) ở chế độ truy cập từ xa qua cổng TCP số 23, phần mềm thực hiện Telnet kết nối đến máy chủ, nó yêu cầu xác thực người sử dụng bằng cách kiểm tra tên và mật khẩu ở chế độ rõ, nhưng máy chủ lại không thể tự xác thực được cho mình. Theo Microsoft, phần mềm thực hiện giao thức Telnet được cài đặt sẵn trong hệ điều hành Windows 2000 của họ, nhưng nó cũng không khắc phục được kẽ hở này của giao thức. Phần mềm Telnet trong hệ điều hành Windows 2000 thực sự đã chứa đựng tới 7 lỗi, bao gồm 4 lỗi không chống tấn công từ chối phục vụ, 2 lỗi không nâng được mức ưu tiên (Privilege Elevation) và 1 lỗi để lộ thông tin (Information Disclosure). 25
Giáo trình An toàn và bảo mật trong mạng máy tính g) Giao thức IPsec và SSH Các công nghệ an ninh lớp trên như IPsec (Internet Protocol security), SSL (Secure Socket Layer) và SSH (Secure Socket Shell) cung cấp cho các ứng dụng mạng một mức an ninh theo hướng đầu cuối (End-To-End Security), xét quan hệ giữa hai chủ thể bên gửi và bên nhận. Tuy nhiên trong thực tế, chúng phụ thuộc vào hai điều kiện sau: Một hạ tầng an toàn tương ứng, thí dụ có xác thực; Những người sử dụng có hiểu biết cao về tin học và luôn luôn thao tác đúng đắn kể cả trong những trường hợp bất thường. Điều kiện thứ nhất có thể thực hiện được (thí dụ bằng hạ tầng mã hóa khóa công khai), nhưng điều thứ hai thì hiện nay không ai dám chắc. Mức an ninh từ bên gửi đến bên nhận được xây dựng ở tầng ứng dụng trên cùng và phụ thuộc vào sự an toàn của những tầng dưới. Nếu ở dưới là một mạng vô tuyến kiểu "Wi-Fi" với chế độ phát tán (Broadcast) thì không có gì đảm bảo rằng nhóm tin tặc không thu được tín hiệu trong vùng phủ sóng và không giải mã được. h) Giao thức ICMP Giao thức điều khiển thông điệp mạng Internet ICMP (Internet Control Message Protocol) là một giao thức liên mạng IP. ICMP cung cấp một cơ chế cho các thông báo điều khiển và thông báo lỗi. Thí dụ lệnh ping sử dụng các gói tin ICMP để kiểm tra việc kết nối giữa hai địa chỉ IP. Nhưng tin tặc có thể lợi dụng các gói tin ICMP không đến đích (Unreachable) để do thám một mạng. Nói chung cần phải ngăn cản hoặc phải lọc những gói tin ICMP không đến đích và những gói tin ICMP đổi hướng (Redirect) trong bộ định tuyến (Router). i) Giao thức NTP v3 Giao thức NTP (Network Time Protocol) được dùng để đồng bộ và cập nhật thời gian trên các máy chủ và thiết bị mạng từ một số máy chủ NTP. Giao thức này có nhược điểm là tin tặc có thể tấn công bằng cách che dấu hoặc làm thay đổi giờ nhằm làm sai thời gian trong các tệp ký sự. j) Giao thức SNMP Giao thức SNMP (Simple Network Management Protocol) được dùng để quản trị, theo dõi và lập cấu hình cho việc quản trị các thiết bị mạng. Đáng tiếc là những tệp cấu hình mặc định (Default Configuration) của SNMP thường không mấy an toàn vì đã phát hiện được tin tặc có thể lợi dụng chúng để làm tê liệt tường lửa. 26
Giáo trình An toàn và bảo mật trong mạng máy tính 1.8 An toàn đồ hình mạng An toàn của đồ hình (Topology) mạng phải được xác định trong quá trình thiết kế, triển khaivà vận hành mạng. Bốn nội dung chính cần quan tâm là: Mục đích của việc thiết kế Vùng bảo mật Topology mạng Những yêu cầu kinh doanh 1.8.1 Mục đích của thiết kế Mục đích của thiết kế là đảm bảo tính bí mật, tính toàn vẹn, tính hiệu lực và khả năng chịu trách nhiệm. Tính bí mật: ngăn cản hay hạn chế truy cập trái phép hoặc tiết lộ bí mật thông tin, dữ liệu. Tính toàn vẹn: đảm bảo dữ liệu đang làm việc không bị thay đổi so với với dữ liệu gốc. Tính sẵn sàng: đảm bảo hệ thống sẵn sàng đối phó với mọi tình huống. Chịu trách nhiệm: ai chịu trách nhiệm trước mọi hoạt động của hệ thống. 1.8.2 Vùng bảo mật Cần cách ly hệ thống để bảo vệ với những hệ thống hay mạng khác và khỏi những người truy cập không hợp lệ. Đây là một yêu cầu quan trọng khi thiết kế mạng. Hình 1-2 là ví dụ về một mô hình bảo mật. Hình 1-2: Mô hình bảo mật có một khu phi quân sự (DMZ) 27
Giáo trình An toàn và bảo mật trong mạng máy tính 1.9 Quản lý rủi ro Để quản lý được các rủi ro cần phải thực hiện một qui trình bao gồm các bước sau đây: Xác định rủi ro, phát hiện các rủi ro tiềm ẩn đối với sự an toàn của hệ thống. Phân tích các mối đe dọa tiềm năng và các điểm yếu có thể gây tổn thất cho hệ thống. Đánh giá tổn thất có thể xảy ra trong quá trình sử dụng hoặc phụ thuộc vào hệ thống. Lựa chọn các giải pháp và các phương tiện tối ưu nhằm giảm thiểu rủi ro đến mức độ cho phép. Sử dụng các giải pháp bảo vệ nhằm giảm thiểu rủi ro và xác định mức độ rủi ro có thể chấp nhận được (rủi ro dư thừa) trong hệ thống. 1.10 Câu hỏi và bài tập 1.1) Thông tin là gì? Hệ thống thông tin bao gồm những thành phần nào? Một hệ thống thông tin bao gồm những tài nguyên nào? 1.2) An ninh của một hệ thống thông tin là gì? 1.3) Sự an toàn của một hệ thống thông tin là gì? 1.4) Hãy nêu các mối đe doạ đối với một hệ thống thông tin và các biện pháp bảo vệ? 1.5) Các thành phần chính của an toàn tin học là những gì? 28
Giáo trình An toàn và bảo mật trong mạng máy tính CHƯƠNG 2. MẬT MÃ HỌC 2.1 Sơ lược về lịch sử mật mã học Mật mã học cổ điển: mật mã học là một ngành khoa học có một lịch sử khoảng 4000 năm. Các cổ vật của ngành khảo cổ học thu được đã cho thấy điều này. Người Ai Cập cổ đại đã sử dụng các chữ tượng hình như là một dạng mã hóa đơn giản nhất trên các bia mộ của họ [4]. Các tài liệu viết tay khác cũng cho thấy các phương pháp mã hóa đơn giản đầu tiên mà loài người đã sử dụng. Mật mã học cổ điển hoạt động trên cơ sở bảng chữ cái (chẳng hạn các ký tự từ "A" tới "Z" trong tiếng Anh) và chúng được thực hiện bằng tay hay một số máy móc thô sơ sử dụng phương thức mã hóa cổ điển chủ yếu dựa trên mật mã hóa hoán vị và mật mã hóa thay thế. Phương thức này quá đơn giản nên vì vậy những kẻ tấn công có thể dễ dàng bẻ khóa thông qua nhiều phương thức như tấn công vét cạn (ví dụ dùng máy tính để thử hết mọi trường hợp) hay dựa trên tấn công thống kê (dựa trên tần suất xuất hiện của các chữ cái). Người Hy Lạp cổ đại cũng được biết đến là đã sử dụng các kỹ thuật mật mã (chẳng hạn như mật mã scytale). Cũng có những bằng chứng rõ ràng chứng tỏ người La Mã nắm được các kỹ thuật mật mã (mật mã Caesar và các biến thể). Thậm chí đã có những đề cập đến một cuốn sách nói về mật mã trong quân đội La Mã; tuy nhiên cuốn sách này đã thất truyền. Tại Ấn Độ, mật mã học cũng khá nổi tiếng. Trong cuốn sách Kama Sutra, mật mã học được xem là cách những người yêu nhau trao đổi thông tin mà không bị phát hiện. Trong thế chiến II, các hệ thống mật mã cơ khí và cơ điện tử được sử dụng rộng rãi mặc dù các hệ thống thủ công vẫn được dùng tại những nơi không đủ điều kiện. Các kỹ thuật phân tích mật mã đã có những đột phá trong thời kỳ này, tất cả đều diễn ra trong bí mật. Cho đến gần đây, các thông tin này mới dần được tiết lộ do thời kỳ giữ bí mật 50 năm của chính phủ Anh đã kết thúc, các bản lưu của Hoa Kỳ dần được công bố cùng với sự xuất hiện của các bài báo và hồi ký có liên quan. Các nhà mật mã học của Hải quân Mỹ (với sự hợp tác của các nhà mật mã học Anh và Hà Lan sau 1940) đã xâm nhập được vào một số hệ thống mật mã của Hải quân Nhật. Việc xâm nhập vào hệ thống JN-25 trong số chúng đã mang lại chiến thắng vẻ vang cho Mỹ trong trận Midway. Một nhóm trong quân đội Mỹ đã thành công trong 29
Giáo trình An toàn và bảo mật trong mạng máy tính việc xâm nhập hệ thống mật mã ngoại giao tối mật của Nhật (một máy cơ điện dùng "bộ chuyển mạch dịch bước" được người Mỹ gọi là Purple) ngay cả trước khi thế chiến II bắt đầu. Người Mỹ đặt tên cho những bí mật mà học tìm được từ việc thám mã, có thể đặc biệt là từ việc phá mã máy Purple, với cái tên "Magic". Người Anh sau này đặt tên cho những bí mật mà họ tìm ra trong việc thám mã, đặc biệt là từ luồng thông điệp được mã hóa bởi các máy Enigma, là "Ultra". Mật mã học hiện đại: Lịch sử của mật mã học được đánh dấu vào năm 1949 khi Claude Shannon công bố bài báo Lý thuyết truyền thông trong các hệ thống bảo mật (Communication Theory of Secrecy Systems) trên Tập san Kỹ thuật của Hệ thống Bell (Bell System Technical Journal) và một thời gian ngắn sau đó, trong cuốn Lý thuyết toán học trong truyền thông (Mathematical Theory of Communication) cùng với tác giả Warren Weaver. Những công trình này cùng với những công trình nghiên cứu khác của ông về lý thuyết thông tin và truyền thông (Information and Communication Theory), đã thiết lập một nền tảng lý thuyết cơ bản cho mật mã học và thám mã học sau này. Vào những năm đầu của thập kỷ 70 của thế kỷ trước, thế giới được chứng kiến hai công trình lớn, đó là công bố về Tiêu chuẩn mật mã hóa dữ liệu DES (Data Encryption Standard) của Mỹ năm 1975. DES là một phương thức mật mã hóa đầu tiên được một cơ quan quốc gia như NSA của Mỹ sử dụng. Nó đã khuyến khích sự quan tâm chú ý của công chúng cũng như của các tổ chức nghiên cứu về mật mã học. Tiếp theo, năm 1976 chứng kiến sự phát triển của các thuật toán mã hóa khóa công khai sau khi Whitfield Diffie và Martin Hellman công bố bài báo New Directions in Cryptography làm nền tảng cho sự ra đời của các hệ mã khóa công khai, hệ mã hóa khóa bất đối xứng (Asymmetric Key Algorithms). Tuy nhiên, do nhược điểm của các hệ mã mật khóa công khai là chậm khi mã hóa các khối dữ liệu lớn, cho nên các hệ mã khối, mã đối xứng vẫn tiếp tục được phát triển. Một số hệ mã khối mới đã được phát triển để thay thế cho DES vào cuối thế kỷ 20 như IDEA, AES hoặc 3DES. 2.2 Những khái niệm cơ bản Mã hóa: mã hóa (Encrytion) là phương pháp biến đổi dữ liệu, thông tin (văn bản, hình ảnh, video, ) từ dạng bình thường, nguyên bản sang dạng thông tin không thể đọc, không thể hiểu được trực tiếp nếu không có phương tiện giải mã. 30
Giáo trình An toàn và bảo mật trong mạng máy tính Giải mã: giải mã (Decryption) là phương pháp biến đổi dữ liệu, thông tin (văn bản, hình ảnh, video, ) từ dạng thông tin đã được mã hóa về dạng thông tin ban đầu, quá trình ngược của mã hóa. Thám mã: thám mã (Cryptanalysis) là quá trình tìm những điểm yếu hoặc không an toàn trong phương thức mã hóa để từ đó tìm ra khóa giải mã hoặc tìm ra nguyên bản. Thám mã có thể được thực hiện bởi những kẻ tấn công ác ý, nhằm làm hỏng hệ thống; hoặc bởi những người thiết kế ra hệ thống (hoặc những người khác) với ý định đánh giá độ an toàn của hệ thống. Hệ mật mã: một hệ mật mã là một bộ gồm 5 thành phần (P, C, K, E, D) thỏa mãn các điều kiện sau đây [2]: P là tập hữu hạn các bản tin rõ, nguyên bản (Plain Text) C là một tập hữu hạn các bản mã (Cipher Text) K là không gian hữu hạn các khóa (Key) E là tập các thuật toán mã hóa (Encryption Algorithm) D là tập hợp các thuật toán giải mã (Decryption Algorithm) Với mỗi khóa k K, tồn tại một thuật toán mã hóa ek E và một thuật toán giải mã dk D, trong đó ek: P C và dk: C P là các hàm sao cho dk(ek(x)) = x với mọi x P. Mô hình hệ mật mã: Mô hình hệ mật mã tổng quát được minh họa như trong Hình 2-1. khóa khóa x x Bản mã được truyền đi y = e k (x) Nguyên bản Nguyên bản Thuật toán mã hóa Thuật toán giải mã (ví vdụ: DES) (ví dụ: DES) Hình 2-1:Mô hình hệ mật mã tổng quát Mô hình trên sử dụng phương pháp mã hóa thông tin x ở dạng nguyên bản để tạo ra một văn bản được mã hoá y theo một quy luật riêng thông qua khóa k (k có thể là 31
Giáo trình An toàn và bảo mật trong mạng máy tính khóa bí mật hoặc khóa riêng, tùy theo hệ mã), y được gửi qua kênh truyền tới bên nhận, người nhận dùng thuật toán giải mã và khóa để giải mã y và thu được x. 2.3 Phân loại các thuật toán mật mã Các thuật toán mã hóa khóa bí mật: Các thuật toán mã hóa khóa bí mật được sử dụng trong các hệ mã hóa khóa đối xứng SKC (Symmetric Key Cryptosytems) do vai trò của người nhận và người gửi là như nhau. Cả hai bên đều có thể mã hóa và giải mã thông điệp bằng cùng một khoá, như Caesar, DES, AES. Do đó nó cần phải được giữ bí mật vì nếu bị lộ, hệ mã hóa không còn tác dụng mật hóa nữa. Các thuật toán mã hóa khóa công khai: Các thuật toán mã hóa khóa công khai được sử dụng trong các hệ mã hóa khóa công khai PKC (Public Key Cryptosystems). Các hệ mã này còn được gọi là các hệ mã khóa bất đối xứng (Asymmetric Key Cryptosytems). Thay vì chỉ sử dụng một khóa như các thuật toán mã hóa khóa bí mật, các thuật toán mã hóa khóa công khai dùng một cặp khoá, một khóa cho mã hóa và một khóa cho giải mã. Trong cặp khóa này, có một khóa được công bố công khai tới các đối tác giao dịch và một khóa được giữ bí mật chỉ người sở hữu nó được biết. Các thuật toán tạo chữ ký số: Các thuật toán tạo chữ ký số (Digital Signature Algorithms). Thông thường, mỗi hệ chữ ký số có cùng cơ sở lý thuyết với một hệ mật mã khóa công khai nhưng với các cách áp dụng khác nhau. Trong giáo trình này, chỉ đề cập đến hai hệ chữ ký số phổ biến là RSA và El Gammma. Các hàm băm: (Hash functions) tương ứng với các thuật toán băm thường được sử dụng trong các hệ chữ ký số hoặc các hệ mã hoá khóa công khai để tạo ra bản băm cho một tập tin. Nó chính là một thông điệp hay một khối dữ liệu để xác thực nguồn gốc hoặc tính toàn vẹn của chúng sau khi truyền đi trong môi trường công cộng. 2.4 Ứng dụng của mật mã học Ngày nay, các ứng dụng trên máy tính cá nhân hay các chương trình hệ thống như các hệ điều hành, các dịch vụ mạng hoặc các hệ cơ sở dữ liệu đều có sử dụng các thuật toán mã hóa để mã hóa mật khẩu người dùng hoặc tin nhắn bằng một hệ mật mã hoặc một hàm băm nào đó. Đặc biệt với sự phát triển mạnh mẽ của thương mại điện tử, các mô hình chữ ký số ngày càng đóng vai trò tích cực cho một môi trường an toàn cho người dùng. Tuy vậy chúng ta vẫn có thể chia các lĩnh vực ứng dụng của mật mã học thành các lĩnh vực nhỏ như sau: 32
Giáo trình An toàn và bảo mật trong mạng máy tính Bảo mật (Confidentiality): che dấu nội dung của các thông điệp được trao đổi trong một phiên truyền thông hoặc giao dịch hoặc các thông điệp trên một hệ thống máy tính (các file, dữ liệu trong một cơ sở dữ liệu ). Xác thực (Authentication): đảm bảo nguồn gốc của một thông điệp, người dùng. Toàn vẹn (Integrity): đảm bảo chỉ có các tổ chức đã được xác thực hóa mới có thể thay đổi các tài sản của hệ thống cũng như các thông tin trên đường truyền. Không thể chối bỏ (Non-Repudiation): các bên đã được xác thực không thể phủ nhận việc tham gia vào một giao dịch hợp lệ. Ngoài ra còn các dịch vụ quan trọng khác chẳng hạn như chữ ký điện tử, dịch vụ chứng thực danh tính (Identification) cho phép thay thế hình thức xác thực hóa người dùng dựa trên các mật khẩu bằng các kỹ thuật mạnh hơn hoặc dịch vụ thương mại điện tử cho phép tiến hành các giao dịch an toàn trên các kênh truyền thông không an toàn. 2.5 Số học modulo 2.5.1 Định nghĩa modulo Cho số tự nhiên n và số nguyên a (n thuộc N; a thuộc Z). Ta định nghĩa a modulo n và viết tắt là a mod n là phần dư dương khi chia a cho n, nghĩa là a= a/n *n + (a mod n) (2.7) Trong đó a/n là số nguyên lớn nhất bé hơn hoặc bằng a/n.Số n được gọi là số modulo. Hai số nguyên a và b được gọi là đồng dư modulo n, khi và chỉ khi a và b có cùng phần dư khi chia cho n. Tức là a mod n = b mod n và được ký hiệu là a ≡ b mod n (2.8) Ví dụ 2.1 100 mod 11 = 1; 34 mod 11 = 1, nên 100 ≡ 34 mod 11. Số b được gọi là đại diện của a theo modulo n nếu a ≡ b mod n, tức là(a = q.n + b) và 0 <= b < n. Ví dụ 2.2 -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7. Ở đây 2 là đại diện của -12, -5, 2 và 9 theo modulo 7. Suy rộng ra, trong modulo 7 ta có các lớp tuơng đương viết trên các hàng như sau: 33
Giáo trình An toàn và bảo mật trong mạng máy tính Bảng 2-1: Các lớp tương đương theo modulo 7 -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Các phần tử trên cùng một cột có quan hệ đồng dư với nhau. Tập các đại diện của các số nguyên theo modulo n bao gồm n phần tử cơ sở {0, 1, 2, , n-1} và được ký hiệu là tập Zn: Zn = {0, 1, 2, , n-1} 2.5.2 Ước số Số b không âm được gọi là ước số của a, nếu tồn tại một số m sao cho a = m*b, trong đó a, b, m đều là các số nguyên, dấu * là ký hiệu của phép nhân số học. Tức là a chia hết cho b và được ký hiệu là b|a. Ví dụ 2.3 1, 2, 3, 4, 6, 8, 12, 24 là các ước số của 24. 2.5.3 Các phép toán số học trên modulo Cho trước một số nguyên dương n, ta muốn thực hiện các phép toán theo modulo của n. Ta có thể thực hiện các phép toán trên các số nguyên như các phép cộng, nhân các số nguyên thông thường sau đó rút gọn lại bằng phép lấy modulo hoặc cũng có thể vừa tính toán vừa rút gọn tại bất cứ thời điểm nào: (a+b) mod n = [a mod n + b mod n] mod n (2.9) (a.b) mod n = [a mod n . b mod n] mod n (2.10) Như vậy khi thực hiện các phép toán ta có thể thay các số bằng các số tương đương theo modulo n hoặc đơn giản hơn có thể thực hiện các phép toán trên các đại diện của nó. Các chú ý về tính chất rút gọn: Nếu (a+b) ≡ (a+c) mod n, thì b ≡ c mod n. 34
Giáo trình An toàn và bảo mật trong mạng máy tính Nhưng (ab) ≡ (ac) mod n, thì b ≡ c mod n chỉ khi nếu a là nguyên tố cùng nhau với n. Ví dụ 2.4 Áp dụng các tính chất của modulo, tính giá trị của biểu thức sau: (11*19 + 1017) mod 7 = ((11*19) mod 7 + 1017 mod 7) mod 7 = ((11 mod 7* 19 mod 7) mod 7 + (10 mod 7)17 mod 7) mod 7= ((4.(-2)) mod 7 + (((32)2)2)2* 3 mod 7)mod 7= ((-1) mod 7 + ((22)2)2* 3 mod 7)mod 7 = (-1 + 5) mod 7 = 4 2.5.4 Vành Zn (vành đồng dư modulo n) Tập các số nguyên Zn = {0, 1, , n-1} trong đó n là một số tự nhiên dương với hai phép toán cộng (+) và nhân (*) được định nghĩa như sau tạo thành một vành đồng dư modulo n (hay còn gọi là tập thặng dư đầy đủ theo modulo n): Phép cộng: a, b Zn: a + b = (a + b) mod n. (2.11) Phép nhân: a, b Zn: a * b = (a * b) mod n. (2.12) Theo tính chất của modulo số học chúng ta dễ dàng nhận thấy Zn là một vành giao hoán và kết hợp. Hầu hết các tính toán trong các hệ mã mật đều được thực hiện trên một vành Zn nào đó. Trên vành Zn số 0 là phần tử trung hòa vì a + 0 = 0 + a = a, a Zn, số 1 được gọi là phần tử đơn vị vì a * 1 = 1 * a = a, a Zn. Zn với các phép toán theo modulo tạo thành vành giao hoán có đơn vị. Thực vậy tính đóng của các phép cộng và nhân dựa trên hai công thức (2.9) và (2.10). Các tính chất kết hợp, giao hoán và nghịch đảo được suy ra từ các tính chất tương ứng với các số nguyên. 2.5.5 Các số nguyên tố Như chúng ta đã biết số nguyên tố là các số nguyên dương chỉ chia hết cho 1 và chính nó, chúng không thể được viết dưới dạng tích của các số khác. Hợp số là các số nguyên dương có thể phân tích được ra thừa số. Trong các số nguyên nhỏ hơn 10, ta có các số 2, 3, 5, 7 là số nguyên tố, vì chúng không có ước số khác 1 và chính nó; còn các số 4, 6, 8, 9, 10 không phải là số nguyên tố. Số 2 là số nguyên tố chẵn duy nhất. Các số nguyên tố là trung tâm của lý thuyết số và số lượng của chúng là vô hạn. 35
Giáo trình An toàn và bảo mật trong mạng máy tính Ví dụ 2.5 Sau đây là danh sách các số nguyên tố nhỏ hơn 200: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 2.5.6 Ước số chung lớn nhất (Greatest Common Divisor) Ước số chung lớn nhất của hai số nguyên dương a và b là số nguyên lớn nhất mà cả a và b cùng chia hết, và được ký hiệu là GCD(a,b). Ví dụ 2.6 GCD(60,24) = 12 ; GCD (6, 15) = 3; GCD(8, 21) = 1. Nguyên tố cùng nhau: Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1. Ví dụ 2.7 Hai số 8 và 15 là nguyên tố cùng nhau vì GCD(8,15) = 1. Tìm ước chung lớn nhất: bây giờ chúng ta xét bài toán tìm ước số chung lớn nhất của hai số nguyên dương cho trước. Ta có các tính chất sau: GCD(a, a) = a Nếu b|a thì GCD(a, b) = b GCD(a, 0) = a vì a|0 luôn luôn đúng (0 luôn chia hết cho a) GCD(a, b) = GCD(b, a mod b) Thật vậy, với hai số nguyên dương a > b bất kỳ, có thể được biểu diễn dưới dạng: a = q*b + r hay a mod b = r trong đó, q >=1 và r>=0. Do đó, nếu d là ước số chung lớn nhất của a và b thì d cũng là ước số chung lớn nhất của b và r. Ngược lại, nếu d là ước số chung lớn nhất của b và r thì d cũng là ước số chung lớn nhất của a và b. Ví dụ 2.8 GCD(55, 22) = GCD(22, 55 mod 22) = GCD(22, 11) = 11; Như vậy để tìm ước số chung của một cặp số cho trước, ta đưa về bài toán tìm ước chung của cặp số gồm số nhỏ hơn trong hai số đó và phần dư của số lớn khi chia cho số nhỏ hơn. Thuật toán Euclide tạo nên một vòng lặp, ở mỗi bước ta áp dụng tính chất trên cho đến khi phần dư đó bằng 0. Thuật toán Euclide tìm GCD(a, b) A = a, B = b while B>0 do R = A mod B A = B, B = R return A 36
Giáo trình An toàn và bảo mật trong mạng máy tính Ví dụ 2.9 GCD(1970,1066) ; 1970 = 1 1066 + 904 GCD(1066, 904) 1066 = 1 904 + 162 GCD(904, 162) 904 = 5 162 + 94 GCD(162, 94) 162 = 1 94 + 68 GCD(94, 68) 94 = 1 68 + 26 GCD(68, 26) 68 = 2 26 + 16 GCD(26, 16) 26 = 1 16 + 10 GCD(16, 10) 16 = 1 10 + 6 GCD(10, 6) 10 = 1 6 + 4 GCD(6, 4) 6 = 1 4 + 2 GCD(4, 2) 4 = 2 2 + 0 GCD(1970, 1066) = 2 (trong đó dấu là ký hiệu của phép nhân số học) 2.5.7 Nghịch đảo a-1 modulo n Cho a và n là hai số nguyên, nguyên tố cùng nhau. Số d được gọi là nghịch đảo của a modulo n khi và chỉ khi (a*d) mod n = 1. Số d được ký kiệu là a-1. Ví dụ 2.10 11-1 mod 7 = 4-1 mod 7 = 2 vì 2*4 mod 7 = 1. Suy ra nghịch đảo của 11-1 mod 7 = 2 7-1 mod 11 = 8, vì 7*8 mod 11= 56 mod 11 = 1. Ta mở rộng thuật toán Euclide tìm ước chung lớn nhất của n và a để tính nghịch đảo trong trường hợp GCD(n, a) = 1.Giải thuật sau chỉ thực hiện với các số nguyên n a 0, biểu diễn bằng giả mã: 37
Giáo trình An toàn và bảo mật trong mạng máy tính Thuật toán tìm giá trị nghịch đảo modulo Đầu vào: a, n nguyên Đầu ra: giá trị nghịch đảo của a mod n hoặc không có Bước 1: y0=0, y1=1; r=0;q=0; y=0; Bước 2: while (a>=1) do { r = n mod a; if (r = 0) then break; q = n div a; y = y0-y1*q ; n=a ; a = r; y0 = y1; y1 = y; } Bước 3: if (a 1) then return "a không có nghịch đảo theo modulo n" Bước 5 : if (y > 0) then return y else return (n + y); Ví dụ 2.11 Tìm số nghịch đảo nếu có của 30 theo modulo 101 dựa vào thuật toán Euclid mở rộng: GCD(30,101) = 1 Bảng 2-2: Minh họa các bước tìm nghịch đảo của 30 modulo 101 Bước i n a r q y0 y1 y 1 101 30 11 3 0 1 -3 2 30 11 8 2 1 -3 7 3 11 8 3 1 -3 7 -10 4 8 3 2 2 7 -10 27 5 3 2 1 1 -10 27 -37 6 2 1 0 Kết quả tính toán trong bảng cho ta -37. Vậy 30-1 mod 101 = -37+101 = 64. 38
Giáo trình An toàn và bảo mật trong mạng máy tính Ví dụ 2.12 Tìm nghịch đảo của 550 trong GL(1759). Bảng 2-3: Minh họa các bước tìm nghịch đảo của 550 modulo 1759 Bước i n a r q y0 y1 y 1 1759 550 109 3 0 1 -3 2 550 109 5 5 1 -3 16 3 109 5 4 21 -3 16 -339 4 5 4 1 1 16 -339 355 5 4 1 0 Sau 4 bước, ta có a = 1, khi đó thuật toán dừng, GCD(1759, 550) = 1 và 550-1 mod 1759 = 355. 2.5.8 Định lý Euler Nếu n là số nguyên dương bất kỳ và a là số nguyên tố cùng nhau với n thì aФ(n)mod n = 1 (2.13) trong đó, Ф(n) là số các số nguyên Zn nguyên tố cùng nhau với n, được gọi là hàm Euler. Chẳng hạn, nếu p là một số nguyên tố thì giá tri củạ hàm Euler của p: Ф(p) = p – 1 hoặc nếu n = p*q trong đó p và q là hai số nguyên tố thì Ф(n) = (p- Ф(n) 1)*(q-1), a chính là giá trị nghịch đảo của a trên Zn. Chứng minh: Giả sử x1, x2, , xФ(n) là các số tự nhiên khác nhau, nhỏ hơn n và nguyên tố cùng nhau với n. Xét tất cả các khả năng của tích xi * a với i = 1, , Ф(n). Bởi vì a là nguyên tố cùng nhau với n và xi là nguyên tố cùng nhau với n, nên tích xi * a cũng nguyên tố cùng nhau với n, do đó có xi * a  xi mod n. (2.14) Chú ý rằng các phần dư của phép chia xi * a cho n là khác nhau. Nếu điều này không đúng, có nghĩa là tồn tại i1 ≠ i2, sao cho: xi1 * a  xi2 mod n. Cho nên (xi1 -xi2) 0 mod n. Bởi vì a nguyên tố cùng nhau với n, nên biểu thức cuối cùng tương đương với: xi1 -xi2  0 mod n Điều này là mâu thuẫn, bởi các số x1, x2, , xФ(n) là các cặp khác nhau theo modulo n. 39
Giáo trình An toàn và bảo mật trong mạng máy tính Hãy nhân tất cả các đẳng thức xi * a  xj mod n lại với nhau, ta thu được Ф(n) Ф(n) x1 xФ(n)a x1 x mod n. Ф(n) Hay: x1 xФ(n)(a -1)  0 mod n Bởi vì số x1 xФ(n) mod n là nguyên tố cùng nhau với n nên đẳng thức cuối cùng tương đương với: aФ(n) -1  0 mod n hay aФ(n) 1 mod n. Ví dụ 2.13 Cho a = 3; n = 10 : chỉ có 4 số nhỏ hơn 10 là 1, 3, 7, 9 nguyên tố cùng nhau với 10 nên suy ra Ф(10) = 4; Do 34 = 81 = 1 mod 10 tức là 3Ф(10) = 1 mod 10, đúng như khẳng định của định lý Euler Cho a = 2; n = 11: vì 11 là số nguyên tố nên Ф(11) = 11-1=10; Do 210 = 1024 = 1 mod 11 tức là 2Ф(10) = 1 mod 11. Ví dụ 2.14 Với n = 10: Tập đầy đủ các phần dư là: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Tập rút gọn các phần dư nguyên tố cùng nhau với 10 là: {1, 3, 7, 9} Số các phần tử của tập rút gọn trên được gọi là giá trị của hàm Euler và được ký hiệu là Ф(n). Trong ví dụ trên thì Ф(10) = 4. Muốn tính Ф(n) cần phải đếm được số các số nguyên tố cùng nhau với n và nhỏ hơn n. Đây là một bài toán khó. Nói chung có thể tính hàm Euler của một số dựa trên biểu thức phân tích ra thừa số của số đó. Ф(1) = 1 Nếu p là số nguyên tố thì Ф(p) = p - 1. Nếu p và q là hai số nguyên tố khác nhau thì: Ф(p*q) = (p - 1)(q - 1). Nếu p là số nguyên tố, thì Ф(pn) = pn - pn-1 Nếu s và t là hai số nguyên tố cùng nhau, thì Ф(s.t) = Ф(s)*Ф(t) Ví dụ 2.15 Ф(37) = 37 – 1 = 36S Ф(21) = (3–1)×(7–1) = 2×6 = 12 40
Giáo trình An toàn và bảo mật trong mạng máy tính Ф(72) = Ф(8.9) = Ф(8). Ф(9) = Ф(23).Ф(32) = = (23-22)(32-31) = 4.6 = 24 Định lý Euler là tổng quát hoá của định lý Ferma. Ví dụ 2.16: Các số 5 và 7 là các số nguyên tố, 2 và 3 không là bội tương ứng của 7 và 5, nên theo định lý Ferma ta có: 27-1 mod 7 = 1 (= 26 mod 7 = 64 mod 7= 1) 35-1 mod 5 = 1 (= 34 mod 5 = 81 mod 5= 1) (-2)11-1 mod 11 = 1 (= 210 mod 11 = 1024 mod11 = 1) Ví dụ 2.17 Một số giá trị của hàm Euler Ф(n) n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Ф(n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 Hàm Euler được dùng trong các hệ mã hóa khoá công khai. Nó cũng được sử dụng để kiểm tra tính nguyên tố của một số nguyên p nào đó, bằng cách lấy ngẫu nhiên các số a và kiểm tra xem có tính chất nêu trên không, kết luận p là nguyên tố sẽ càng thuyết phục nếu phép thử trên đúng với nhiều lần chọn ngẫu nhiên các số a. 2.6 Mã nén dữ liệu 2.6.1 Khái niệm cơ bản Nén dữ liệu là quá trình biến đổi dữ liệu từ dạng có dung lượng lớn trở thành dạng dữ liệu có dung lượng nhỏ hơn: từ X->X’ mà X’ có dung lượng nhỏ hơn dung lượng của X. Giải nén là quá trình làm ngược lại của quá trình nén dữ liệu, nghĩa là từ X’ X (trở về dạng dữ liệu nguyên thủy) Nén dữ liệu rất có lợi cho việc truyền thông trên mạng, vấn đề bảo mật thông tin, tiết kiệm dung lượng bộ nhớ lưu trữ, 2.6.2 Các phương pháp nén dữ liệu a) Nén bảo toàn Đó là mô hình nén dữ liệu cho phép người sử dụng bảo toàn (không mất) thông tin khi giải nén. Điều này được giải thích như sau: Với D là dữ liệu ban đầu, Z là hàm nén, U là hàm giải nén: D’ = Z(D) và D’’ = U(D’) thì D’’= D 41
Giáo trình An toàn và bảo mật trong mạng máy tính Thông thường phương pháp này được áp dụng với dữ liệu văn bản. Nén bảo toàn dựa trên hai mô hình khác nhau: Mô hình thống kê: Nén dựa vào xác suất xuất hiện của các ký hiệu trong tệp cần nén. Mô hình từ điển: Mã hoá một chuỗi ký hiệu chỉ bằng một từ mã b) Nén không bảo toàn Nén không bảo toàn là mô hình nén dữ liệu mà tính bảo toàn của dữ liệu không được coi trọng. D’ = Z(D) và D’’ = U(D’) nhưng có thể D’’<> D Kỹ thuật này thường áp dụng cho việc nén dữ liệu là các tệp ảnh vì nói chung nó cũng không ảnh hưởng gì nhiều đến chất lượng ảnh. Hầu hết các kỹ thuật nén không bảo toàn thường được dùng để điều chỉnh sự cân bằng giữa độ chính xác của quá trình nén và hiệu quả nén. Các phương pháp nén ảnh: CompuSever GIF (Graphics Interchange Format) và JPEG (Join Photographic Experts Group). Ngoài ra còn có nén MPEG (The Moving Picture Experts Group). Các phương pháp nén âm thanh: hai thông số quan trọng nhất của âm thanh số hoá là tốc độ lấy mẫu và độ phân giải mẫu. Tốc độ lấy mẫu thường là 8 KHz, độ phân giải mẫu thường là 8 bit. Nén âm thanh cũng gồm cả nén bảo toàn và nén không bảo toàn, tuy nhiên nén bảo toàn không hiệu quả bằng nén không bảo toàn. Tốc độ lấy mẫu và độ phân giải mẫu xác định hệ số mất mát cho phép của phương pháp nén không bảo toàn để tín hiệu sau quá trình nén - giải không bị méo dạng. Phương pháp mã hoá phổ biến để nén tiếng nói là phương pháp mã hoá dự đo án tuyến tính (LPC- Linear Predictive Coding). LPC dựa trên các phương pháp ước tính bình phương bé nhất cổ điển và sự tương hợp ngẫu nhiên giữa một mô hình toán học lý tưởng (mô hình dự đoán tuyến tính) với các đặc trưng riêng của tiếng nói con người. Một hệ thống LPC hoàn chỉnh bao gồm hai khâu là phân tích và tổng hợp. Một cải tiến rất quan trọng của LPC là thuật toán nén tổn hao thông dụng ADPCM (Adaptive Diffirence Pulse Code Modulation). 2.6.3 Nén dữ liệu theo mô hình thống kê a) Mô hình thống kê tĩnh 42
Giáo trình An toàn và bảo mật trong mạng máy tính Dạng đơn giản nhất của mô hình thống kê tĩnh là một bảng tĩnh liệt kê các giá trị xác suất theo cách tính thông thường. Trước đây, do việc phân tích và xây dựng mã Huffman rất tốn thời gian, nên người ta chỉ phân tích một lần đối với các dữ liệu điển hình để có được một bảng đếm số lần xuất hiện của từng ký hiệu. Dựa vào kết quả đó, một cây mã Huffman tĩnh được xây dựng và lưu trữ để có thể sử dụng nhiều lần. Mô hình như vậy được gọi là mô hình thống kê tĩnh (Static Statiscal Model). Việc sử dụng một mô hình tĩnh vạn năng cho nhiều kiểu dữ liệu rõ ràng có nhiều hạn chế. Nếu dữ liệu vào không thích hợp với mô hình thì hiệu quả nén sẽ giảm, thậm chí sẽ có kích thước lớn hơn dữ liệu vào (gọi là nở đầu vào). Do đó một cải tiến tiếp theo là xây dựng mô hình tĩnh cho nhiều kiểu dữ liệu. Việc xây dựng mô hình tĩnh riêng sẽ có thuận lợi là mang lại hiệu suất nén cao. Nhưng nhược điểm là lại cần lưu trữ thêm một lượng dữ liệu nhất định (cấu trúc của cây mã) trước khi lưu trữ bản mã. Nếu cấu trúc của cây mã vào không lớn lắm vào khoảng 256B so với lượng số lượng dữ liệu cần nén vài trăm KB thì mô hình tĩnh riêng là hiệu quả. Nhưng nếu cấu trúc của cây mã tăng lên mức không thể chấp nhận được so với mục tiêu nén dữ liệu (cỡ khoảng 64KB) thì mô hình tĩnh riêng không phù hợp. b) Mô hình thống kê động Để khắc phục những nhược điểm của mô hình thống kê tĩnh, mô hình thống kê động ra đời với số liệu thống kê đối với dữ liệu cần mã hoá không phải lưu trữ trước mà liên tục được tích luỹ và sửa đổi trong suốt quá trình mã hoá và giải mã. Điểm đáng chú ý trong mô hình thống kê động là sau khi một ký hiệu hoặc một nhóm ký hiệu đọc vào, nó sẽ được mã hoá dựa trên mô hình hiện thời, sau đó mô hình mới được cập nhật dựa trên ký hiệu hoặc nhóm ký hiệu đó. Tương tự như vậy, sau khi một từ mã được đọc vào nó sẽ được giải mã theo mô hình hiện thời rồi sau đó mô hình mới được cập nhật theo ký hiệu đã được giải mã. Với mô hình thống kê động, ban đầu nó chưa biết gì về dữ liệu cần được mã hoá cho nên hiệu ứng nén chưa thể xuất hiện ngay. Hiệu ứng nén chỉ xuất hiện rõ rệt khi làm việc với cỡ vài nghìn ký hiệu. Ưu điểm của mô hình động ở chỗ nó có khả năng thích ứng với nhiều kiểu dữ liệu khác nhau. 2.6.4 Mã nén Huffman Thực chất thuật toán Huffman (giống với Fano- Shannon) là phương pháp mã hoá dựa trên cơ sở thống kê tần suất xuất hiện của từng ký hiệu trong nguồn dữ liệu. 43
Giáo trình An toàn và bảo mật trong mạng máy tính Mã Huffman có một tính chất quan trọng là thỏa mãn tính phân tách.  Thuật toán tạo mã Huffman Đầu vào: tệp tin nguồn chưa nén fn Đầu ra: tệp tin nén fg Bắt đầu: + Mở tệp tin nguồn để đọc + Mở tệp tin nén để ghi Bước 1: Thống kê tạo ra bảng tần suất xuất hiện của các ký hiệu có trong nguồn. Bước 2: Sắp xếp các ký hiệu trong bảng theo chiều không giảm hoặc không tăng. Bước 3: Coi mỗi ký tự trong bảng là 1 cây, tìm hai cây có trọng số nhỏ nhất ghép lại thành một cây; trọng số của cây mới bằng tổng trọng số của hai cây con đem ghép. Bước 4: Tiếp tục ghép cây cho đến khi trong danh sách còn 1 cây. Bước 5: Đánh số các nhánh trên cây với quy ước nhánh bên trái ghi mã 0, bên phải ghi mã 1. Bước 6: Gán mã cho các ký tự bằng cách ghép các số trên nhánh từ gốc đến lá. Bước 7: Thay thế ký tự trong file fn bằng mã tương ứng và ghi ra file fg. Ví dụ 2.17 Áp dụng thuật toán Huffman, nén xâu “go go gophers”. Chúng ta thực hiện các bước sau. Bước 1: Kí tự Tần xuất Từ mã G 3/13 00 O 3/13 01 ‘ ‘ 2/13 100 P 1/13 101 H 1/13 1100 E 1/13 1101 R 1/13 1110 S 1/13 1111 Bước 2,3, 4: Ta có cây như hình 2.2 dưới Bước 5: Xuất phát từ gốc đi tới các nút lá trên cây và tạo cây nhị phân với qui ước đi sang trái ghi mã 0, đi bên phải ghi mã 1 ta được cây như hình 2-2. 44
Giáo trình An toàn và bảo mật trong mạng máy tính Hình 2-2: Các bước xây dựng cây mã Huffman Bước 6: Xâu “go go gophers” sẽ được mã hoá như sau (dấu - cho dễ đọc) 00-01-100-00-01-100-00-01-1110-1101-101-1111-1100 Mã Huffman được tạo ra theo thuật toán trên là mã có tính phân tách, có độ dài từ mã tối ưu và thoả mãn các tính chất sau: Chữ cái với xác suất lớn hơn thì có độ dài từ mã nhỏ hơn Từ mã của hai chữ cái có xác suất nhỏ nhất có cùng độ dài và chỉ khác nhau bít cuối cùng. So với mã Fano Shannon thì mã Huffman có hiệu suất nén cao hơn một chút nên trong thực tế nó được sử dụng nhiều hơn Phương pháp này từ khi mới ra đời được sử dụng rộng rãi, nhất là trong lĩnh vực cơ sở lý thuyết thông tin. Nó là cơ sở để sản sinh ra nhiều phương pháp nén khác tốt hơn. Tuy nhiên phương pháp này lại trở nên cồng kềnh khi số chữ cái quá lớn. Để giải quyết vấn đề này phải dùng một biện pháp khắc phục để giảm nhẹ quá trình mã hoá như sau: Liệt kê các chữ cái của văn bản nguồn theo thứ tự xác suất giảm dần. Sau đó ghép thành nhiều nhóm chữ cái có xác suất xấp xỉ nhau. Dùng một mã đều để mã hoá các chữ cái trong cùng một nhóm. Sau đó xem các nhóm chữ cái như là một khối chữ cái và dùng phương pháp Huffman để mã hoá các khối chữ cái. Từ mã cuối cùng 45
Giáo trình An toàn và bảo mật trong mạng máy tính tương ứng với mỗi chữ cái của văn bản gồm hai phần: một phần là mã Huffman, một phần là mã đều. 2.6.5 Mã RLE (Run- Length- Encoding) Đây là một phương pháp nén ảnh phổ biến hiện nay. Nguyên tắc của mã RLE rất đơn giản là thay thế một chuỗi kí tự lặp lại bằng một kí tự duy nhất của chuỗi lặp lại cùng với một biến đếm số lần kí tự đó được lặp lại. a) Thuật toán mã hoá Trong văn bản nguồn có thể có một số kí tự giống nhau, thuật toán sẽ nhóm lại thành một nhóm 2 thành phần (L, C), trong đó C là kí tự được lặp lại L lần.  Thuật toán nén RLE như sau: Đầu vào: Tệp tin nguồn f Đầu ra: Tệp tin nén fn Các biến: C1, C2 là hai kí tự, L là một số nguyên Bước 1: + Mở tệp tin nguồn f (để đọc) + Mở tệp tin nén fn (để ghi) Bước 2: + Đặt L=1; + Đọc kí tự trong f gán vào C1; Bước 3: Thực hiện khi C1 <> end of file(f)) b1. Đọc kí tự tiếp theo trong f gán vào C2 b2. Kiểm tra, nếu C1 = C2 thì + Tăng L lên 1; + Quay lên thực hiện tiếp b1; Ngược lại thì: + Ghi cặp (L, C1) ra tệp nén fn. + Quay lên thực hiện tiếp Bước 2: Ngược lại, (nếu C1 là ký tự cuối cùng trong tệp f) thì thực hiện Bước 4. Bước 4: Kết thúc. Ví dụ 2.18: Có một văn bản sau: aaaabbbaabbbbbccccccccdabcbaaabbbbcccd. Theo phương pháp mã RLE thì văn bản này được mã hoá như sau: 46
Giáo trình An toàn và bảo mật trong mạng máy tính 4a3b2a5b8c1d1a1b1c1b3a4b3c1d b) Thuật toán giải mã RLE như sau: Đầu vào: Tệp tin nén fn Đầu ra: Tệp tin giải nén fg Bước 1: + Mở tệp tin nén fn (để đọc) + Mở tệp tin giải nén fg (để ghi) Bước 2: Khi nào cặp (L, C) không phải là ký tự cuối cùng trong tệp fn thì thực hiện: b1. Đọc cặp (L, C) trong tệp nén fn b2. + For i=1 to L do ghi ký tự C ra tệp giải nén fg + Quay lên thực hiện tiếp Bước 2: Ngược lại, (L, C là cặp ký tự cuối cùng trong tệp nén fc) thì thực hiện Bước 3: Kết thúc. Ví dụ 2.19: Cho bản mã kết quả của Ví dụ 2.18: 4a3b2a5b8c1d1a1b1c1b3a4b3c1d. Quá trình giải mã như sau: Đọc cặp mã đầu tiên là 4a thì ta viết aaaa, tiếp theo là cặp mã 3b thì ta viết ra tiếp bbb. Cứ lặp lại như vậy cho đến khi đọc hết các cặp mã ta được văn bản ban đầu là aaaabbbaabbbbbccccccccdabcbaaabbbbcccd. Nhận xét: Thuật toán trên có hạn chế là nếu kí tự không lặp lại thì lại tốn ít nhất 2B (1B số, 1B kí tự) để mô tả một kí tự 1B. Lúc này thuật toán không “nén” mà là “bung”. 2.6.6 Mô hình từ điển a) Tổng quát Kỹ thuật từ điển là kỹ thuật sử dụng phương pháp phân đoạn văn bản thành các đoạn nhỏ hơn sao cho nó đạt được độ dài nhất có thể được mà nó đã xuất hiện ở trong quá khứ. Giả sử chúng ta có từ điển D thì tồn tại một ánh xạ f: D -> trong đó  là tập các đoạn bit 0/1. Việc nén sẽ tối ưu khi chúng ta phân được đoạn văn bản có độ dài lớn nhất mà sao cho khi đi tìm trong quá khứ thì chúng ta được đoạn 0/1 trong  là nhỏ nhất. 47
Giáo trình An toàn và bảo mật trong mạng máy tính Trong kỹ thuật từ điển, tương tự như kỹ thuật thống kê, ta cũng có hai phương án sau: b) Từ điển tĩnh Mã có từ điển cố định được gọi là mã tĩnh hay nói cách khác là từ điển tĩnh. Nhược điểm của từ điển tĩnh: Kích thước của từ điển tĩnh không thể mở rộng ra, để cập nhật các thông tin mới so với các loại dữ liệu khác. Quá trình nghiên cứu thiết kế từ điển đòi hỏi nhiều công sức. Các thuật toán sử dụng từ điển tĩnh chạy tương đối chậm. Tốn không gian lưu trữ dữ liệu. Tuy nhiên bên cạnh những nhược điểm này thì từ điển tĩnh cũng có ưu điểm là: Thiết kế các thuật toán áp dụng cho việc tìm kiếm trên từ điển tĩnh đơn giản tốn ít thời gian. Do những đặc tính hạn chế của từ điển tĩnh, kết hợp với những đặc điểm nổi bật của thuật toán nén là "sự cứng nhắc" đã làm cho người dùng chương trình để tiết kiệm bộ nhớ nhàm chán không thích sử dụng các chương trình nén nữa. Vậy phải có cách để khắc phục những hạn chế đó và làm cho chương trình nén dữ liệu trở nên mềm dẻo hơn. Chính vì vậy những thuật toán nén chỉ đạt hiệu quả cao nếu chúng ta xử lý tốt "từ điển" được sử dụng trong các thuật toán nói chung. c) Từ điển động Để khắc phục những hạn chế của từ điển tĩnh, biện pháp được xét đến là: Chúng ta không thiết kế một từ điển sẵn mà " từ điển" đó được xây dựng trong quá trình chạy chương trình. Một từ điển như vậy người ta gọi là từ điển động. Đặc điểm chính của từ điển động: Kích thước của từ điển có thể thay đổi tuỳ theo kích thước của tập tin. Không tốn thời gian lưu trữ từ điển. Thời gian thực hiên quá trình nén nhanh. Từ điển không phụ thuộc vào kiểu dữ liệu. Thời gian thực hiện quá trình giải nén chậm. 2.6.7 LZ77 Ý tưởng của phương pháp này là sử dụng phần đã xét trước đó như là một từ điển. Mã hóa duy trì một cửa số gắn với luồng vào và dịch đầu vào trong cửa sổ từ 48
Giáo trình An toàn và bảo mật trong mạng máy tính phải sang trái theo đúng cách các chuỗi ký tự được mã hóa. Phương thức này dựa trên một cửa sổ trượt. Cửa sổ dưới được chia làm hai phần: - Phần bên trái gọi là bộ đệm tìm kiếm – search buffer. Đây là từ điển hiện hành và nó bao gồm các ký hiệu mới được duyệt ở đầu vào và được mã hóa. - Phần bên phải là bộ đệm nhìn trước - look-ahead buffer, chứa văn bản chưa được mã hóa. Thực tế, bộ đệm search dài hàng nghìn byte trong khi bộ đệm look-ahead chỉ dài khoảng 10 byte. Thanh dọc ở giữa t và e bên dưới biểu diễn dòng phân chia hiện hành giữa hai bộ đệm. Bởi vậy ta thấy văn bản “sir sid eastman easily t” đã được nén, trong khi văn bản “eases sea sick seals” cần được nén. search buffer look-ahead buffer sir sid eastman easily t eases sea sick seals Mã hóa quét quay lui bộ đệm search (từ phải sang trái) để tìm ký tự trùng với ký tự e đầu tiên trong bộ đệm look-ahead. Nó tìm thấy một ký tự e trong từ easily. Từ e này nằm tại offset 8 tính từ phần cuối của bộ đệm search. Sau đó, mã hóa tìm ký tự e tiếp theo có thể có. Ba ký tự eas trùng nhau trong trường hợp này, vì vậy độ dài của chuỗi hợp là 3. Mã hóa tiếp tục quay lui quét, cố gắng tìm thấy các chuỗi hợp dài hơn. Trong trường hợp này chỉ có ký tự e trong từ eastman, tại offset 16 và có độ dài như vậy. Mã hóa chọn chuỗi hợp dài nhất hoặc nếu chúng có độ dài như nhau, chuỗi hợp cuối cùng được tìm thấy và chuẩn bị xâu (16,3, “e”). Việc chọn chuỗi hợp cuối cùng hơn là chuỗi hợp đầu tiên làm đơn giản hóa bộ mã hóa, khi nó chỉ phải theo dõi chuỗi hợp cuối cùng được tìm thấy. Thú vị để ghi nhớ việc chọn lựa chuỗi hợp đầu tiên trong khi làm chương trình có phần phức tạp hơn cũng là một lợi thế. Nó chọn lựa offset nhỏ nhất. Dường như điều này không lợi thế khi một xâu nên có chỗ cho offset có thể lớn nhất. Tuy nhiên, đi theo LZ77 với Huffman, hoặc mã thống kê khác của các xâu mà các offset nhỏ được gán các mã ngắn hơn. Phương thức này, được đề xướng bởi Bernd Herd, gọi là LZH. Một câu hỏi mà có thể xảy ra tại điểm này là việc giải mã bằng cách nào trong khi mã hoá chọn chuỗi hợp đầu tiên hoặc cuối cùng? Câu trả lời dễ hiểu là việc giải mã không được biết nhưng nó không cần để biết. Giải mã đơn giản là đọc các xâu và sử dụng mỗi offset để tìm chuỗi văn bản mà không cần biết chuỗi là chuỗi hợp đầu tiên hay cuối cùng. Cấu tạo một xâu LZ77: gồm có 3 phần: 49
Giáo trình An toàn và bảo mật trong mạng máy tính Offset: vị trí của xâu trong bộ đệm search. Length: độ dài xâu. Ký hiệu kế tiếp trong bộ đệm look-ahead. Trong ví dụ trên, xâu được ghi là (16,3, “e”) (e – ký tự e thứ hai trong từ teases). Xâu này được ghi trên luồng ra và cửa sổ được dịch sang phải (hay nói cách khác, luồng vào được dịch sang trái) bốn vị trí: ba vị trí cho chuỗi hợp và một vị trí cho ký tự kế tiếp. Nếu khi quay lui, không tìm được ký tự trùng thì một xâu LZ77 có trường offset và length là bằng 0 và trường thứ ba là ký tự không được hợp. Đây cũng là nguyên nhân một xâu phải có ba thành phần. Các xâu với trường offset và length bằng 0 phổ biến tại phần bắt đầu công việc nén, khi mà bộ đệm search là rỗng hoặc hầu như rỗng. Ví dụ 2.20: sir sid eastman (0,0, “s”) S sir sid eastman (0,0, “i”) Si r sid eastman ea (0,0, “r”) Sir sid eastman eas (0,0, “ ”) Sir sid eastman easi (4,2,“d”) a) Thuật toán nén Giả sử cửa sổ có: bộ đệm search có kích thước N byte và bộ đệm look-ahead có kích thước là F byte. Bước 1: Đọc 1 ký tự đầu tiên giữ nguyên. Bước 2: Cho cửa sổ dịch sang phải. Mỗi lần đếm số ký tự trùng nhau liên tiếp kể từ đầu của bộ đệm look-ahead về bộ đệm search và ghi nhớ con số tương ứng với vị trí offset của nó. Tìm số lớn nhất trong tất cả các con số ấy. Bước 3: Ghi ra mã [i, j, w] trong đó: - i: khoảng cách từ vị trí hiện tại đến vị trí tương ứng với số lớn nhất vừa tìm được. - j: số các ký tự trùng nhau hay chính là số lớn nhất vừa tìm được. - w: ký tự ở vị trí thứ j + 1 trong bộ đệm look-ahead. Bước 4: Lặp lại bước 2 cho đến khi hết văn bản. Bước 5: Kết thúc. 50
Giáo trình An toàn và bảo mật trong mạng máy tính Ví dụ 2.21: Cho văn bản sau: “sire sire eastman easily” với N = 24, F =16. Bảng 2-4: Quá trình nén văn bản “sire sire eastman easily” dùng LZ77 STT Search buffer vị trí hiện tại Look-ahead buffer Ghi ra 1 1 sire sire eastma (0,0, “s”) 2 s 2 ire sire eastman (0,0, “i”) 3 si 3 re sire eastman_ (0,0, “r”) 4 sir 4 e sire eastman e (0,0, “e”) 5 sire 5 _sire eastman ea (0,0, “_”) 6 sire_ 6 sire eastman eas (5,5, “e”) 7 sire sire_e 12 astman easily (0,0, “a”) 8 sire sire ea 13 stman easily (7,1, “t”) 9 sire sire east 15 man easily (0, 0, “m”) 10 sire sire eastm 16 an easily (4, 1, “n”) 11 sire sire eastman 18 _easily (8,4, “i”) 12 sire sire eastman 23 ly (0,0, “l”) easi 13 sire sire eastman 24 y (0,0, “y”) easil Vậy bản nén là: (0,0,“s”)(0,0,“i”)(0,0,“r”)(0,0,“e”)(0,0,“_”)(5,5,”e”)(2,1,”a”)(7,1,”t”)(0,0,”m”) (4,1,“n”)(8,4,“i”)(0,0, “l”)(0,0,“y”) b) Thuật toán giải nén Bước 1: Đọc bộ đệm look-ahead, 1 ký tự đầu tiên của bản mã ghi ra bản giải mã. Bước 2: Đọc một bộ mã [i, j, w]. Lùi về đoạn văn bản đã giải mã i vị trí và copy j ký tự từ vị trí thứ i đó để ghi ra bản giải mã, sau đó ghi tiếp w ra. Bước 3: Nếu còn bộ mã thì quay lại bước 2. Nếu không còn thì sang bước 4 Bước 4: Kết thúc Ví dụ 2.32 Bảng 2-5: Quá trình giải nén văn bản dùng LZ77 STT Bộ mã đọc vào Ghi ra Bản giải mã 51
Giáo trình An toàn và bảo mật trong mạng máy tính 1 (0,0,“s”) s s 2 (0,0,“i”) i si 3 (0,0,“r”) r sir 4 (0,0,“e”) e sire 5 (0,0,“_”) _ sire_ 6 (5,5,”e”) sire_e sire sire_e 7 (0,0,”a”) a sire sire ea 8 (7,1,”t”) st sire sire east 9 (0,0,”m”) m sire sire eastm 10 (4,1,“n”) an sire sire eastman 11 (8,4,“i”) _easi sire sire eastman easi 12 (0,0, “l”) l sire sire eastman easil 13 (0,0,“y”) y sire sire eastman easily Văn bản đã giải nén: “sire sire eastman easily”. Sang 8/3 2.6.8 LZ78 LZ78 được phát minh và sử dụng trong những năm 1978. LZ78 sử dụng một từ điển gồm các chuỗi đã xem trước đó. Từ điển này được khởi tạo là rỗng và kích thước của nó chỉ bị giới hạn bởi số lượng bộ nhớ sẵn có. Một xâu LZ78 được tạo ra gồm hai trường có dạng (W, C): - W: chỉ số của chuỗi ký hiệu trong từ điển. - C: mã ký hiệu kế tiếp. Xâu LZ78 không chứa kích thước của chuỗi khi nó đã được bao hàm trong từ điển. Mỗi xâu tương ứng với một chuỗi các ký hiệu vào và chuỗi đó được thêm vào từ điển sau khi xâu được ghi vào luồng nén. Không có xâu nào bị xóa khỏi từ điển, đây là cả lợi thế (các chuỗi tương lai có thể được nén bởi chính những chuỗi đã được xét từ lâu) và bất lợi (từ điển phát triển nhanh và đầy bộ nhớ sẵn có) so với LZ77. Từ điển được khởi tạo với một chuỗi rỗng bắt đầu tại vị trí 0. Khi các ký tự được nhập vào và được mã hóa thì các chuỗi được thêm vào tại vị trí 1, 2, Khi một ký tự tiếp được đọc từ luồng vào, từ điển tìm kiếm một mục với chuỗi đơn x. Nếu không tìm thấy, x được thêm vào từ điển tại vị trí kế tiếp, và xâu (0, x) được ghi ra. Xâu này cho biết chuỗi “null x” (chuỗi rỗng kết hợp với x). Nếu một mục 52
Giáo trình An toàn và bảo mật trong mạng máy tính với x được tìm thấy (ví dụ tại vị trí 37), ký tự kế tiếp y được đọc và từ điển tìm kiếm mục chứa chuỗi hai ký tự xy. Nếu không có trong từ điển, thì chuỗi xy được thêm vào tại vị trí tiếp theo trong từ điển, và xâu (37, y) được ghi ra. Xâu này cho biết chuỗi xy với 37 là vị trí của chuỗi x trong từ điển. Quá trình tiếp tục đến khi gặp ký tự kết thúc luồng vào. Từ điển được xây dựng trong quá trình nén và giải nén là hoàn toàn động, do đó không cần lưu từ điển cùng với file nén. Điều này tạo kích thước file nén giảm đáng kể. a) Thuật toán Đầu vào: Tệp tin nguồn f Đầu ra: Tệp tin nén fn Bước 1:+ Khởi tạo từ điển = xâu rỗng có chỉ số 0. + Đặt xâu trung gian P = rỗng. Bước 2: Đọc ký tự tiếp theo trong tệp văn bản nguồn f gán vào C. Bước 3: Kiểm tra: Nếu xâu (P + C) đã có trong từ điển thì: + Đặt P = P + C + Quay lại bước 2; Ngược lại thì: + Cập nhật P + C vào trong từ điển; + Gán W = P chỉ số trong từ điển; + Ghi cặp (W,C) ra tệp tin nén fn. + Đặt lại P = rỗng Bước 4: Kiểm tra: Nếu còn ký tự trong văn bản thì: + Quay lại bước 2. Ngược lại thì: + Ghi ra cặp (W, C) với C là rỗng ra tệp nén fn; + Sang bước 5; Bước 5:Kết thúc Ví dụ 2.23 53
Giáo trình An toàn và bảo mật trong mạng máy tính Nén văn bản “sir sid eastman” STT P C Từ điển W Ghi ra 1 S 1 – s 0 (0, “s”) 2 I 2 – i 0 (0, “i”) 3 R 3 – r 0 (0, “r”) 4 _ 4 - _ 0 (0, “_”) 5 S 6 s I 5 – si 1 (1, “i”) 7 D 6 – d 0 (0, “d”) 8 _ 9 _ E 7 - _e 4 (4, “e”) 10 A 8 – a 0 (0, “a”) 11 S 12 s T 9 - st 1 (1, “t”) 13 M 10 - m 0 (0, “m”) 14 A 15 a N 11 - an 8 (8, “n”) Vậy bản nén là: (0,“s”)(0,“i”)(0,“r”)(0,“_”)(1,“i”)(0,“d”)(4,“e”)(0,“a”)(1,“t”)(0,“m”)(8,“n”) b) Thuật toán giải nén Với mỗi cặp (W,C) ta ký hiệu. W nội dung của đoạn copy thứ W trong từ điển. Nếu W=0 thì W là rỗng. Đầu vào:Tệp tin nguồn nén fn Đầu ra: Tệp tin giải nén fg; Bước 1: + Mở tệp tin nguồn fn (để đọc) + Mở tệp tin giải nén fg (để ghi) Bước 2: Khởi tạo từ điển = xâu rỗng có chỉ số 0 Bước 3: Đọc một cặp (W,C). Bước 4: + Ghi xâu (W +C) ra file giải nén fg. + Cập nhật xâu này vào từ điển 54
Giáo trình An toàn và bảo mật trong mạng máy tính Bước 5: Kiểm tra: nếu còn ký tự trong file mã fn thì quay lại bước 3. Ngược lại sang bước 6; Bước 6: Kết thúc. Ví dụ 2.24 Giải nén STT Cặp mã đọc vào Ghi ra Từ điển 1 (0,“s”) s 1 – s 2 (0,“i”) i 2 – i 3 (0,“r”) r 3 – r 4 (0,“_”) _ 4 - _ 5 (1,“i”) si 5 – si 6 (0,“d”) d 6 – d 7 (4,“e”) _e 7 - _e 8 (0,“a”) a 8 – a 9 (1,“t”) st 9 – st 10 (0,“m”) m 10 – m 11 (8,“n”) an 11 – an 2.7 Câu hỏi và bài tập 2.7.1 Câu hỏi 2.1) Mã hóa, giải mã, phá mã và mật mã học là gì? 2.2) Cho số tự nhiên n và số nguyên a. Hãy định nghĩa phép toán a modulo n. 2.3) Hãy giải thích biểu thức a  b mod n. 2.4) Tập đại diện của các số nguyên theo modulo n gồm những số nào? Hãy định nghĩa vành đồng dư modulo n: Zn . 2.5) Cho số tự nhiên n và số nguyên a với điều kiện GCD(a,n) = 1. Hãy định nghĩa nghịch đảo của a theo modulo n. 2.7.2 Bài tập 2.1) Tính giá trị các biểu thức theo modulo sau: 8 mod 9 + 7 mod 9 53 mod 7 8 mod 9 * 7 mod 9 520 mod 7 5 mod 11 – 9 mod 11 5/6 mod 7 55
2.2) Tính giá trị các biểu thức theo modulo sau (-546) mod 13 - 347 mod 11 1435 mod 11 (1234 + 2345) mod 17 (235*126/13) mod 19 (213 * 345) mod 19 31130 mod 23 15-1 mod 101 (23525 /17 + 12619 - 397 /13) mod 29 41-1 mod 100 2.3) Tính hàm Ơle của các số nguyên sau: 12, 17, 21, 32, 36, 40, 72, 256 2.4) Sử dụng thuật toán Huffman để nén các chuỗi sau và tính tỷ số nén đối với mỗi chuỗi: ABBCDGHKUABBABAGGG KBBCDKHKUABBABAKGG KBBCDKHKUABBABAKKG ABBCDGHKUABBABADDD 2.5) Hãy sử dụng thuật toán LZ77 để nén và giải nén các chuỗi sau: S1 ="hai hai ba bon nam sau bay tam". S2 ="hai hai ba bon tam ba tam bon" 2.6) Hãy sử dụng thuật toán LZ78 để nén và giải nén các chuỗi S1 và S2 trong bài 2.5).
Giáo trình An toàn và bảo mật trong mạng máy tính CHƯƠNG 3. CÁC HỆ MẬT MÃ ĐỐI XỨNG 3.1 Định nghĩa Phần này ta xem xét định nghĩa của hệ mật mã đối xứng. Trong thực tế, có nhiều hệ mật mã đối xứng khác nhau được tạo ra phục vụ nhu cầu sử dụng của con người. Tuy nhiên, ta có thể biểu diễn các hệ mật mã đối xứng bằng mô hình tổng quát sau đây: Khóa k Khóa k Bản tin rõ Bản tin đã mã hóa Bản tin rõ E D x y = Ek(x) x = Dk(y) Hình 3-1: Mô hình tổng quát của các hệ mật mã đối xứng Trong mô hình nói trên, E và D lần lượt là các thuật toán mã hóa và giải mã tương ứng. Thuật toán mã hóa E sẽ mã hóa một bản tin rõ x thành một bản mã y sử dụng một khóa bí mật k nào đó. Ngược lại, thuật toán giải mã D sẽ dựa trên khóa bí mật k để giải mã bản mã y thành bản tin rõ x ban đầu. Để thuận tiện trong việc biểu diễn và trình bày các hệ mật mã ở phần tiếp theo, ta đưa vào định nghĩa hình thức về hệ mật mã như sau: Định nghĩa 3.1 [2] Một hệ mật mã là một bộ gồm 5 thành phần, (P, C, K, E,D), thỏa mãn các điều kiện sau đây: P là tập hữu hạn các bản (tin) rõ C là một tập hữu hạn các bản mã K là một tập hữu hạn các khóa E là quy tắc mã hóa bản tin rõ thành bản mã D là quy tắc giải bản mã thành bản tin rõ Đối với mỗi khóa k K, có một thuật toán mã hoá Ek E ánh xạ từ P vào C và một thuật toán giải mã tương ứng Dk D ánh xạ từ C vào D. Thuật toán giải mã Dk() chính là ánh xạ ngược của thuật toán mã hóa Ek(), nghĩa là Dk(Ek(x)) = x với mọi x P. Trong giáo trình này, chúng ta quy ước dùng chữ thường để biểu diễn nội dung các bản tin rõ và dùng chữ hoa để biểu diễn nội dung bản mã. 57
Giáo trình An toàn và bảo mật trong mạng máy tính 3.2 Mật mã đối xứng cổ điển Có hai kỹ thuật cơ bản được sử dụng trong các hệ mật mã đối xứng nói chung và mật mã cổ điển nói riêng, đó là kỹ thuật thay thế và kỹ thuật hoán vị. Mã thay thế là phương pháp mà từng kí tự hoặc một nhóm kí tự trong bản rõ được thay thế bằng một kí tự hoặc một nhóm kí tự khác để tạo ra bản mã. Bên nhận chỉ cần thay thế ngược lại trên bản mã để có được bản rõ ban đầu. Trong phương pháp mã hoán vị, các kí tự trong bản rõ vẫn được giữ nguyên, chúng chỉ được sắp xếp lại vị trí để tạo ra bản mã. Tức là các kí tự trong bản rõ hoàn toàn không bị thay đổi bằng kí tự khác mà chỉ đảo chỗ của chúng để tạo thành bản mã. 3.2.1 Kỹ thuật mã hóa thay thế a) Hệ mật mã thay thế đơn Ceasar Ðây là hệ mật mã thay thế sớm nhất được Julius Ceasar đưa ra. Việc mã hoá được thực hiện đơn giản là thay mỗi chữ trong bản rõ bằng chữ thứ ba tiếp theo trong bảng chữ cái tiếng Anh gồm 26 ký tự (a, b, , z). Ví dụ 3.1: Bản rõ: mat khau la ngay mai tuoi sang Bản mã: PDW NKDX OD QJDB PDL WXRL VDQJ Có thể định nghĩa việc mã hoá này qua ánh xạ trên hai bảng chữ cái, bảng các chữ ở dòng dưới là mã của bảng các chữ tương ứng ở dòng trên. a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Về toán học, có thể gán số thứ tự cho mỗi chữ trong bảng chữ cái bắt đầu từ số 0 như trong bảng sau: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Khi đó, hệ mật mã Caesar được định nghĩa một cách hình thức như sau: Cho P = C = Z 26 , k = 3, quy tắc mã hóa và giải mã Caesar được định nghĩa như sau: ( 3.1) y = ek(x) = (x + k) mod 26 và 58
Giáo trình An toàn và bảo mật trong mạng máy tính x = dx(y) = (y – k) mod 26 ,  x, y Z26 ( 3.2) Theo định nghĩa này thì chỉ có 26 giá trị khác nhau của k, nên có 26 khoá khác nhau nhưng độ dài khoá ở đây chỉ là 1 vì mọi chữ đều tịnh tiến đi một khoảng như nhau. Việc thám mã đối với hệ mật Caesar là việc làm đơn giản do số lượng khóa khác nhau là rất nhỏ. Chỉ có 26 khoá có thể, vì A chỉ có thể ánh xạ vào một trong số 26 chữ cái của bảng chữ cái tiếng Anh A, B, C, Các chữ khác sẽ được xác định bằng số bước tịnh tiến tương ứng của A. Kẻ thám mã có thể thử lần lượt từng khoá một, tức là sử dụng phương pháp tìm duyệt tổng thể. Vì số khoá ít nên việc tìm duyệt là khả thi. Cho trước bản mã, thử 26 cách dịch chuyển khác nhau, ta sẽ đoán nhận thông qua nội dung các bản rõ nhận được. Để khắc phục nhược điểm này của mã Caesar, người ta tìm cách thay hàm mã hóa x + k bằng hàm ax + k, với a nguyên tố cùng nhau với 26, để mã của bảng chữ cái không còn theo thứ tự alphabet nữa. Kỹ thuật này có tên là Affine. b) Hệ mật mã Affine – một phiên bản nâng cấp của Caesar Hệ mã hoá Affine được xác định bởi hai số nguyên a và b, với điều kiện là 0 a, b 25 (tức a, b thuộc bảng chữ cái tiếng Anh gồm 26 ký tự) và a nguyên tố cùng nhau với 26. Ở đây, chúng ta xem xét hệ mật mã trên các số tự nhiên thay cho các ký tự như đã nói ở phần trên, các phép toán số học được thực hiện theo modulo 26. Đặt P = C = Z26 và đặt K={(a, b) Z26 Z26: gcd(a, 26) = 1}. với k = (a, b) K, các hàm mã hóa và giải mã được định nghĩa như sau: Ek(x) = (ax + b) mod 26 -1 và Dk(y) = a (y - b) mod 26 Từ công thức mã hóa của Affine ta thấy ngay là khi a = 1 thì hệ mã hoá này chính là hệ mã Caesar. Ví dụ 3.2: Nếu a = 3 và b = 5 thì ta có bảng mã hóa của các số tự nhiên tương ứng với bảng chữ cái gốc như sau: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 5 8 11 14 17 20 23 0 3 6 9 12 15 18 21 24 1 4 7 10 13 16 19 22 25 2 59
Giáo trình An toàn và bảo mật trong mạng máy tính Tương ứng, ta có mã của bảng chữ cái gốc: a b c d e f g h i j k l m n o p q r s t u v w x y z F I L O R U X A D G J M P S V Y B E H K N Q T W Z C Từ bảng này, ta có thể dễ dàng mã hóa và giải mã bằng cách tra xuôi và tra ngược. Ví dụ 3.3 Cho bản rõ “not every steam bath is sauna”. Sử dụng bảng mã hóa trên đây, lần lượt tra các chữ cái của bản rõ, ta sẽ có bản mã sau: “SVK RQREZ HKRFP IFKA DH HFNSF”. c) Hệ mật mã thay thế sử dụng một bảng chữ Ngoài việc thay đổi hệ số tịnh tiến như đã làm trong kỹ thuật Affine, ta còn có thể khắc phục nhược điểm của mã Caesar bằng cách mã hoá các chữ không chỉ là dịch chuyển bảng chữ, mà có thể tạo ra các bước nhảy khác nhau cho các chữ. Trong một mã, mỗi chữ của bản rõ được ánh xạ đến một chữ khác nhau của bản mã. Do đó, mỗi cách mã như vậy sẽ tương ứng với một hoán vị của bảng chữ và hoán vị đó chính là khoá của mã đã cho. Như vậy độ dài khoá ở đây là 26 và số khoá có thể có là 26!. Ví dụ 3.4: Cho bản mã tương ứng với bản rõ trong mã hóa bảng chữ đơn: a b c d e f g H i j k l m n O p q r s t u v w x y z D K V Q F I B J W P E S C X H T M Y A U O L R G Z N Hãy mã hóa bản rõ “help we are being attacked”. Sử dụng bảng mã trên để mã hóa, ta sẽ có bản mã như sau: JFST RF DYF KFWXB DUUDVEFQ Tính an toàn của mật mã bảng chữ đơn cao hơn mật mã chữ đơn. Ở bảng chữ đơn, tổng cộng có 26! (khoảng 4*1026) khoá. Với khá nhiều khoá như vậy, nhiều người nghĩ là mã trên bảng chữ đơn sẽ an toàn. Nhưng không phải như vậy. Vấn đề ở đây là do các đặc trưng về ngôn ngữ. Tuy có số lượng khoá lớn, nhưng do các đặc trưng về tần suất xuất hiện của các chữ trong bản rõ và mã của chúng trong bản mã là như nhau, nên có thể đoán được ánh xạ của một số chữ và từ đó mò tìm ra chữ mã cho các chữ khác. d) Hệ mật mã Vigenere – mã thay thế sử dụng nhiều bảng chữ Một hướng khác làm tăng độ an toàn cho mã trên bảng chữ là sử dụng nhiều bảng chữ để mã. Ta sẽ gọi chúng là các mã thay thế nhiều bảng. Ở đây mỗi chữ có thể được 60
Giáo trình An toàn và bảo mật trong mạng máy tính mã bằng bất kỳ chữ nào trong bản mã tùy thuộc vào ngữ cảnh khi mã hoá. Làm như vậy để trải bằng tần suất các chữ xuất hiện trong bản mã và giảm bớt tính cấu trúc của bản rõ được thể hiện trên bản mã. Ta sử dụng từ khoá để chỉ rõ chọn bảng nào được dùng cho từng chữ trong bản tin. Sử dụng lần lượt các bảng theo từ khóa đó và lặp lại từ đầu sau khi kết thúc từ khoá. Độ dài khoá là chu kỳ lặp của các bảng chữ. Độ dài càng lớn và nhiều chữ khác nhau được sử dụng trong từ khoá thì càng khó thám mã. Một trong những mã thay thế nhiều bảng chữ đơn giản đó là mã Vigenere. Thực chất quá trình mã hoá Vigenere là việc tiến hành đồng thời nhiều mã Caesar cùng một lúc trên bản rõ với nhiều khoá khác nhau. Khoá cho mỗi chữ dùng để mã phụ thuộc vào vị trí của chữ đó trong bản rõ và được lấy trong từ khoá theo thứ tự tương ứng. Hệ Vigenere được định nghĩa một cách hình thức như sau: m Cho m là một số nguyên dương và P = C = K = (Z 26) . Với một khóa K= ( k1,k2 , ,km ), hàm mã hóa và giải mã được xác định bằng các công thức sau: e (x , x , , x ) (x k , x k , , x k ) K 1 2 m 1 1 2 2 m m và d (y , y , , y ) (y k , y k , , y k ) K 1 2 m 1 1 2 2 m m trong đó các phép +, được thực hiện trên vành Z 26 . Ví dụ 3.5 Để sử dụng mã Vigenere với từ khóa và bản rõ cho trước, ta có thể làm như sau: Viết ra các chữ của bản rõ. Sau đó viết các chữ của từ khoá ở dòng trên tương ứng với các chữ của bản rõ. Lặp lại từ khóa cho đến khi hết bản rõ. Sử dụng mỗi chữ của từ khoá như khoá của mã Caesar. Mã chữ của bản rõ với bước nhảy tương ứng. Giả sử ta có khóa là “deceptive“ và bản rõ là “wearediscoveredsaveyourself“, quá trình mã hóa sẽ thực hiện như sau: Để mã chữ w, ta tìm chữ tương ứng với nó ở hàng khóa. Đó là chữ d (có số thứ tự là 3), như vậy w sẽ được mã trên bảng chữ tịnh tiến 3, tức là chữ w được tịnh tiến thành chữ Z. Chữ thứ hai trong bản rõ tương ứng với chữ mã là e (có số thứ tự là 4), có nghĩa là chữ thứ hai trong bản rõ sẽ được tịnh tiến 4, tức là chữ rõ e được mã thành chữ I. Tương tự như vậy cho đến hết bản rõ, ta sẽ có bản mã sau: 61
Giáo trình An toàn và bảo mật trong mạng máy tính Khóa: deceptivedeceptivedeceptive Bản rõ: wearediscoveredsaveyourself Bản mã: ZICVTWQNGRZGVTWAVZHCQYGLMGI Trên thực tế, để hỗ trợ mã Vigenere, người ta đã tạo ra một bảng được gọi là bảng Saint Cyr trợ giúp cho việc mã và giải mã thủ công. Đó là một bảng cỡ 26 26, được lập ra như sau: Đầu tiên, viết một dòng các chữ cái từ A đến Z. Sau đó, ở dòng tiếp theo ta dịch vòng dòng trên một ký tự sang trái cho đến khi đủ 26 dòng. Viết thêm một dòng chữ cái từ A đến Z ở trên cùng để làm các chữ của từ khóa. Viết thêm một cột chữ cái cũng từ A đến Z ở bên trái để làm các chữ bản rõ khi mã hoá và làm các chữ bản mã khi giải mã. Sử dụng bảng Saint Cyr để mã hóa và gải mã: Để mã hoá thì bản rõ được đọc từ các hàng và khoá được đọc từ các cột. Ví dụ để mã hóa bản rõ PURPLE với từ khoá CRYPTO, đầu tiên ta tìm điểm giao nhau của hàng P và cột C, ta được R. Cứ như vậy ta được bản mã RLPEES. Ta sẽ thu được bản mã tương tự nếu ta thay đổi vai trò của hàng và cột trong khi mã hoá. Để giải mã bản mã RLPEES vừa mã hoá, ta nhìn vào hàng nào có chứa R trong cột C, theo cách này ta sẽ tìm được P. Và như vậy ta tìm được bản rõ là PURPLE. Bảng 3-1: Bảng Saint Cyr ABCDEFGHIJKLMNOPQRSTUVWXYZ A ABCDEFGHIJKLMNOPQRSTUVWXYZ B BCDEFGHIJKLMNOPQRSTUVWXYZA C CDEFGHIJKLMNOPQRSTUVWXYZAB D DEFGHIJKLMNOPQRSTUVWXYZABC E EFGHIJKLMNOPQRSTUVWXYZABCD F FGHIJKLMNOPQRSTUVWXYZABCDE G GHIJKLMNOPQRSTUVWXYZABCDEF H HIJKLMNOPQRSTUVWXYZABCDEFG I IJKLMNOPQRSTUVWXYZABCDEFGH J JKLMNOPQRSTUVWXYZABCDEFGHI K KLMNOPQRSTUVWXYZABCDEFGHIJ L LMNOPQRSTUVWXYZABCDEFGHIJK M MNOPQRSTUVWXYZABCDEFGHIJKL N NOPQRSTUVWXYZABCDEFGHIJKLM O OPQRSTUVWXYZABCDEFGHIJKLMN P PQRSTUVWXYZABCDEFGHIJKLMNO Q QRSTUVWXYZABCDEFGHIJKLMNOP 62
Giáo trình An toàn và bảo mật trong mạng máy tính R RSTUVWXYZABCDEFGHIJKLMNOPQ S STUVWXYZABCDEFGHIJKLMNOPQR T TUVWXYZABCDEFGHIJKLMNOPQRS U UVWXYZABCDEFGHIJKLMNOPQRST V VWXYZABCDEFGHIJKLMNOPQRSTU W WXYZABCDEFGHIJKLMNOPQRSTUV X XYZABCDEFGHIJKLMNOPQRSTUVW Y YZABCDEFGHIJKLMNOPQRSTUVWX Z ZABCDEFGHIJKLMNOPQRSTUVWXY  An toàn của mã Vigenere Như vậy có thể có các chữ mã khác nhau cho cùng một chữ của bản rõ. Suy ra tần suất của các chữ bị là phẳng, nghĩa là tần suất xuất hiện các chữ trên bản mã tương đối đều nhau. Tuy nhiên chưa mất hoàn toàn, do độ dài của khoá có hạn, nên có thể tạo nên chu kỳ vòng lặp. Kẻ thám mã bắt đầu từ tần suất của chữ để xem có phải đây là mã đơn bảng chữ hay không. Giả sử đây là mã đa bảng chữ, sau đó xác định số bảng chữ trong từ khoá và lần tìm từng chữ. Như vậy cần tăng độ dài từ khoá để tăng số bảng chữ dùng khi mã để “là” tần suất của các chữ. 3.2.2 Kỹ thuật mã hóa hoán vị cổ điển Trong mật mã thay thế, các chữ của bản rõ được thay thế bằng các chữ khác của bản mã. Nhưng trong mật mã hoán vị thì khác. Các chữ trong bản rõ không được thay thế bằng các chữ khác mà chỉ thay đổi vị trí, tức là việc mã hoá chỉ dịch chuyển vị trí tương đối giữa các chữ trong bản rõ. Như vậy, nó dấu bản rõ bằng cách thay đổi thứ tự các chữ, nó không thay đổi các chữ thực tế được dùng. Trong mục này chúng ta sẽ tìm hiểu hai kỹ thuật mã hóa hoán vị. a) Mã Rail Fence Đây là mã hoán vị đơn giản, nó viết các chữ của bản rõ theo đường chéo trên một số dòng sau đó đọc các chữ theo theo từng dòng sẽ nhận được bản mã. Số dòng chính là khoá của mã. Vì khi biết số dòng ta sẽ tính được số chữ trên mỗi dòng và lại viết bản mã theo các dòng sau đó lấy bản rõ bằng cách viết lại theo các cột. Ví dụ 3.6 Viết bản tin “meet me after the toga party” lần lượt trên hai dòng như sau m e m a t r h t g p r y e t e f e t e o a a t Sau đó ghép các chữ ở dòng thứ nhất với các chữ ở dòng thứ hai ta có bản mã: 63