Giáo trình môn An toàn và bảo mật Thông tin

145 trang phuongnguyen 2560

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình môn An toàn và bảo mật Thông tin", để 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_mon_an_toan_va_bao_mat_thong_tin.pdf

Nội dung text: Giáo trình môn An toàn và bảo mật Thông tin

BỘ GIAO THÔNG VẬN TẢI TRƯỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN: KHOA HOC̣ MÁ Y TÍNH KHOA: CÔNG NGHỆ THÔNG TIN Giáo trình AN TOÀN VÀ BẢO MẬT THÔNG TIN TÊN HỌC PHẦN : An toàn và bảo mật Thông tin MÃ HỌC PHẦN : 17212 TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN HẢI PHÒNG - 2008
Tên học phần: An toàn bảo mâṭ thông tin Loại học phần: II Bộ môn phụ trách giảng dạy: Khoa học máy tính. Khoa phụ trách: Công nghệ thông tin Mã học phần: Tổng số TC: 3 TS tiết Lý thuyết Thực hành/ Xemina Tự học Bài tập lớn Đồ án môn học 75 45 30 0 0 0 Điều kiện tiên quyết: Sinh viên cần hoc̣ xong các hoc̣ phần: - Lâp̣ trình hướ ng đối tương̣ - Cấu trúc dữ liêụ - Phân tích, thiết kế và đánh giá thuâṭ toán. Mục đích của học phần: Truyền đạt cho sinh viên những kiến thức cơ bản về các lĩnh vực riêng trong an toàn bảo mật máy tính: - Các giải thuật mã hóa trong truyền tin. - Các thuật toán tạo hàm băm và chữ ký điện tử. - Các mô hình trao chuyển khóa. - Các mô hình chứng thực và các giao thức mật mã. Nội dung chủ yếu: Gồm 2 phần: - Phần lý thuyết: cung cấp các lý thuyết về thuâṭ toán ma ̃ hóa, các giao thức. - Phần lâp̣ trình: cài đặt các hệ mã, viết các ứ ng duṇ g sử duṇ g các hê ̣ma ̃ mâṭ Nội dung chi tiết của học phần: Phân phối số tiết Tên chương mục TS LT Xemine BT KT Chương I. Giới thiệu nhiệm vụ của an toàn và bảo 4 3 1 0 0 mật thông tin. 1.1. Các khái niệm mở đầu. 1 1.1.1. Thành phần của một hệ thống thông tin 1.1.2. Những mối đe dọa và thiệt hại đối với hệ thống thông tin. 1.1.3. Giải pháp điều khiển kiểm soát an toàn bảo mật 1.2. Mục tiêu và nguyên tắc chung của ATBM. 1.2.1. Ba mục tiêu. 1.2.2. Hai nguyên tắc 1.3. Giới thiệu chung về các mô hình mật mã. 1 1.3.1. Mô hình cơ bản trong truyền tin và luật Kirchoff. 1.3.2. Những giai đoạn phát triển của lý thuyết mã hóa. 1 1
Chương II. Một số phương pháp mã hóa cổ điển. 13 5 5 2 1 2.1. Phương pháp mã đơn giản. 2 2 1 2.1.1. Mã hoán vị trong bảng Alphabet. 2.1.2. Mật mã cộng tính. 2.2.3. Mật mã nhân tính. 2.1.4. Phân tích mã theo phương pháp thống kê. 2.2. Phương pháp mã bằng phẳng đồ thị tần xuất. 2.2.1. Mã với bảng thế đồng âm. 3 3 1 2.2.2. Mã đa bảng thế: giải thuật mã Vigenre và One time pad. 2.2.3. Lý thuyết về sự bí mật tuyệt đối. 2.2.4. Đánh giá mức độ bảo mật của một phương pháp mã hóa. Kiểm tra 1 Chương III. Mật mã khối. 16 8 7 1 0 3.1. Khái niệm. 1 3.1.1. Điều kiện an toàn cho mật mã khối 3.1.2. Nguyên tắc thiết kế. 3.2. Chuẩn ma ̃ hóa dữ liêụ DES 3 3 0,5 3.2.1. Lịch sử của DES 3.2.2. Cấu trúc vòng lặp DES. 3.2.3. Thuật toán sinh khóa con 3.2.4. Cấu trúc hàm lặp. 3.2.5. Thuật toán giải mã DES. 3.2.6. Đánh giá mức độ an toàn bảo mật của DES. 3.2.7. TripleDES 3.3. Chuẩn ma ̃ hóa cao cấp AES 3 3 0,5 3.3.1. Giớ i thiêụ về AES 3.3.2. Thuâṭ toán ma ̃ hóa 3.3.3. Thuâṭ toán giải mã 3.3.4. Cài đặt AES 3.4 Một số chế độ sử dụng mã khối. 1 1 3.4.1. Chế độ bảng tra mã điện tử 3.4.2. Chế độ mã móc xích 3.4.3. Chế độ mã phản hồi Chương IV. Hệ thống mã với khóa công khai. 16 6 7 2 1 4.1. Khái niệm khóa công khai. 1 4.1.1. Đặc trưng và ứng dụng của hệ mã khóa công khai. 4.1.2. Nguyên tắc cấu tạo hệ khóa công khai 4.2. Giới thiệu một số giải thuật PKC phổ biến. 2 4.1.1. Hệ mã Trapdoor Knapsack. 1 1 4.1.2. Hệ mã RSA 2 3
4.1.3. Hệ mã ElGamal 2 3 Kiểm tra 1 Chương V. Chữ ký điện tử và hàm băm. 12 7 5 0 0 5.1. Chữ ký điện tử. 0,5 5.1.1. Định nghĩa. 5.1.2. Ứng dụng của chữ ký điện tử 5.2. Giớ i thiêụ môṭ số hê ̣chữ ký điêṇ tử 3 5.2.1. Hê ̣chữ ký điêṇ tử RSA 2 5.2.2. Hê ̣chữ ký điêṇ tử ElGamal 5.2.3. Chuẩn chữ ký điêṇ tử DSA 5.3. Hàm băm. 0,5 5.3.1. Định nghĩa. 5.3.2. Sinh chữ ký điện tử với hàm băm 5.4. Môṭ số hàm băm thông duṇ g 3 5.4.1. Hàm băm MD5 1,5 5.4.2. Hàm băm SHA1 1,5 Chương VI. Quản lý khóa trong hệ thống mật mã 8 5 3 0 0 6.1. Quản lý khóa đối với hệ SKC 1 6.1.1. Giới thiệu phương pháp quản lý khóa. 6.2. Quản lý khóa trong các hệ PKC 1 6.2.1. Giao thức trao chuyển khóa Needham – Schoeder 1 6.2.2. Giao thứ c trao đổi khóa Diffie-Hellman 1 1 6.2.3. Giao thứ c Kerberos 1 2 Chương VII. Giao thức mật mã 6 3 2 0 1 7.1. Khái niệm giao thức mật mã 1 7.1.1. Định nghĩa giao thức mật mã 7.1.2. Mục đích giao thức mật mã. 7.1.3. Các bên tham gia vào giao thức mật mã 7.2. Tìm hiểu thiết kế các giao thức mật mã điển hình 2 2 7.2.1. Một số dạng tấn công đối với giao thức mật mã. 7.2.2. Giới thiệu một số giao thức mật mã. 7.3. Kiểm tra. 1 Nhiệm vụ của sinh viên: Lên lớp đầy đủ và chấp hành mọi quy định của Nhà trường. Tài liệu học tập: 1. Phan Đình Diệu. Lý thuyết mật mã và An toàn thông tin. Đại học Quốc Gia Hà Nội. 2. Douglas R. Stinson. Cryptography Theory and practice. CRC Press. 1995. 3. A. Menezes, P. VanOorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press. 1996.
4. William Stallings. Cryptography and Network Security Principles and Practices, Fourth Edition. Prentice Hall. 2005. 5. MichaelWelschenbach. Cryptography in C and C++. Apress. 2005. Hình thức và tiêu chuẩn đánh giá sinh viên: - Sinh viên phải làm các bài kiểm tra trong quá trình học và thực hành. Thi vấn đáp. - Sinh viên phải bảo đảm các điều kiện theo Quy chế của Nhà trường và của Bộ. Thang điểm : Thang điểm 10. Điểm đánh giá học phần: Z = 0,3 X + 0,7 Y.
MỤC LỤC LỜ I NÓ I ĐẦ U 1 CHƢƠNG I: GIỚ I THIÊỤ 2 1. An toà n bả o mâṭ thông tin và mâṭ mã hoc̣ 2 2. Khái niêṃ hê ̣ thố ng và tà i sả n củ a hê ̣ thố ng 2 3. Các mối đe doạ đối với một hệ thống và các biện pháp ngăn chặn 2 4. Mục tiêu và nguyên tắc chung của an toàn bảo mật thông tin 3 5. Mâṭ mã hoc̣ (cryptology) 4 6. Khái niệm hệ mã mật (CryptoSystem) 4 7. Mô hình truyề n tin cơ bả n củ a mâṭ mã hoc̣ và luâṭ Kirchoff 5 8. Sơ lƣợc về lic̣ h sƣ̉ mâṭ mã hoc̣ 6 9. Phân loaị cá c thuâṭ toá n mâṭ mã hoc̣ 8 10. Môṭ số ƣ́ ng duṇ g củ a mâṭ mã hoc̣ 8 CHƢƠNG II: CƠ SỞ TOÁN HỌC 10 1. Lý thuyết thông tin 10 1.1. Entropy 10 1.2. Tố c đô ̣ củ a ngôn ngƣ̃. (Rate of Language) 11 1.3. Tính an toàn của hệ thống mã hoá 11 1.4. Kỹ thuật lộn xôṇ và rƣờ m rà (Confusion and Diffusion) 12 2. Lý thuyết độ phức tạp 13 2.1. Độ an toàn tính toán 14 2.2. Độ an toàn không điều kiện 14 3.3. Hệ mật tích 16 3. Lý thuyết toán học 17 3.1. Modulo số hoc̣ 17 3.2. Số nguyên tố 17 3.3. Ƣớc số chung lớn nhất 17 3.4. Vành ZN (vành đồng dƣ module N) 18 3.5. Phầ n tƣ̉ nghic̣ h đả o 18 3.6. Hàm phi Ơle 19 3.7. Thăṇ g dƣ bâc̣ hai 19 3.8. Thuâṭ toá n lũy thƣ̀ a nhanh 20 3.9. Thuâṭ toá n Ơclit mở rôṇ g 21 3.10. Phƣơng trình đồ ng dƣ bâc̣ nhấ t 1 ẩn 22 3.11. Điṇ h lý phầ n dƣ Trung Hoa. 22 4. Các thuật toán kiểm tra số nguyên tố. 23 4.1. Môṭ số ký hiêụ toá n hoc̣ 23 4.2. Thuâṭ toá n Soloway-Strassen 25 4.3. Thuâṭ toá n Rabin-Miller 26 4.4. Thuâṭ toá n Lehmann. 26 5. Bài tập 26 CHƢƠNG III: CÁC HỆ MÃ KHÓA BÍ MẬT 28 1. Các hệ mã cổ điển 28 1.1. Hê ̣ mã hoá thay thế (substitution cipher) 28 1.2. Hê ̣ mã Caesar 28 1.3. Hê ̣ mã Affine 29 1.4. Hê ̣ mã Vigenere 30 1.5. Hê ̣ mã Hill 30 1.6. Hê ̣ mã đổ i chỗ (transposition cipher) 32 2. Các hệ mã khối 34 2.1. Mật mã khối 34 2.2. Chuẩn mã hoá dữ liệu DES (Data Encryption Standard) 35 2.3. Các yếu điểm của DES 51
2.4. Triple DES (3DES) 52 2.5. Chuẩ n mã hó a cao cấ p AES 54 2.6. Các cơ chế, hình thức sử dụng của mã hóa khối (Mode of Operation) 68 3. Bài tập 72 CHƢƠNG IV: CÁC HỆ MÃ MẬT KHÓA CÔNG KHAI 77 1. Khái niệm hệ mã mật khóa công khai 77 2. Nguyên tắ c cấ u taọ củ a cá c hê ̣ mã mâṭ khó a công khai 78 3. Môṭ số hê ̣ mã khó a công khai 78 3.1. Hê ̣ mã knapsack 78 3.2. Hê ̣ mã RSA 79 3.3. Hê ̣ mã El Gamal 83 3.4. Các hệ mã mật dựa trên các đƣờng cong Elliptic 85 4. Bài tập 96 CHƢƠNG V: CHƢ̃ KÝ ĐIÊṆ TƢ̉ VÀ HÀ M BĂM 101 1. Chƣ̃ ký điêṇ tƣ̉ 101 1.1. Khái niệm về chữ ký điện tử 101 1.2. Hệ chữ ký RSA 102 1.3. Hệ chữ ký ElGammal 103 1.4. Chuẩn chữ ký điện tử (Digital Signature Standard) 106 1.5. Mô hình ƣ́ ng duṇ g củ a chƣ̃ ký điêṇ tƣ̉ 108 2. Hàm Băm (Hash Function) 109 2.1. Khái niệm 109 2.2. Đặc tính của hàm Băm 109 2.3. Birthday attack 110 2.4. Một số hàm Băm nổi tiếng 111 2.5. Một số ƣ́ ng duṇ g củ a hàm Băm 118 3. Bài tập 119 CHƢƠNG VI: QUẢN LÝ KHÓA 120 1. Quản lý khoá trong các mạng truyền tin 120 2. Một số hệ phân phốikhoá 120 2.1. Sơ đồ phân phối khoá Blom 120 2.2. Hệ phân phối khoá Kerberos 122 2.3. Hệ phân phối khó a Diffe-Hellman 123 3. Trao đổi khoá và thoả thuận khoá 124 3.1. Giao thức trao đổi khoá Diffie-Hellman 124 3.2. Giao thức trao đổi khoá Diffie-Hellman có chứng chỉ xác nhận 125 3.3. Giao thức trao đổi khoá Matsumoto-Takashima-Imai 126 3.4. Giao thức Girault trao đổi khoá không chứng chỉ 127 4.Bài tập 128 CHƢƠNG VII: GIAO THƢ́ C MẬT MÃ 130 1. Giao thức 130 2. Mục đích của các giao thức 130 3. Các bên tham gia vào giao thức (the players in protocol) 131 4. Các dạng giao thức 132 4.1. Giao thức có trọng tài 132 4.2. Giao thức có ngƣời phân xử 133 4.3. Giao thức tƣ̣ phân xƣ̉ 134 5. Các dạng tấn công đối với giao thức 134 TÀI LIỆU THAM KHẢO 136
Danh mục hình vẽ DANH MỤC HÌNH VẼ Hình 1.1: Mô hình cơ bản của truyền tin bảo mật 5 Hình 3.1: Chuẩ n mã hó a dƣ̃ liêụ DES 35 Hình 3.2: Sơ đồ mã hoá DES 38 Hình 3.3: Sơ đồ một vòng DES 39 Hình 3.4: Sơ đồ tạo khoá con củ a DES 41 Hình 3.5: Sơ đồ hàm f 43 Hình 3.6: Sơ đồ hàm mở rộng (E) 44 Hình 3.7: Triple DES 53 Hình 3.8: Các trạng thái của AES 56 Hình 3.9: Thuâṭ toán mã hóa và giải mã của AES 59 Hình 3.10: Hàm ShifftRows() 62 Hình 3.11: Hàm MixColumns của AES 63 Hình 3.12: Hàm AddRoundKey của AES 63 Hình 3.13: Hàm InvShiftRows() của AES 66 Hình 3.14: Cơ chế ECB 69 Hình 3.15: Chế đô ̣ CBC 70 Hình 3.16: Chế độ CFB 71 Hình 4.1: Mô hình sƣ̉ duṇ g 1 của các hệ mã khóa công khai PKC 78 Hình 4.2: Mô hình sƣ̉ duṇ g 2 của các hệ mã khóa công khai PKC 78 Hình 4.3: Mô hình ƣ́ ng duṇ g lai ghé p RSA vớ i cá c hê ̣ mã khố i 83 Hình 4.4: Các đƣờng cong Elliptic trên trƣờng số thực 87 4 4 Hình 4.5: Hình biểu diễn E2 (g , 1) 92 Hình 4.6: Phƣơng phá p trao đổ i khó a Diffie-Hellman dƣ̣a trên ECC 94 Hình 5.1: Mô hình ƣ́ ng duṇ g củ a chƣ̃ ký điêṇ tƣ̉ 108 Hình 5.2: Sơ đồ chữ ký sử dụng hàm Băm 109 Hình 5.3: Sơ đồ vòng lặp chính của MD5 112 Hình 5.4: Sơ đồ một vòng lặp MD5 113 Hình 5.5: Sơ đồ một vòng lặp của SHA 117
Danh mục bảng DANH MỤC BẢ NG * Bảng 2.1: Bảng bậc của các phần tử trên Z 21 19 Bảng 2.2: Bảng lũy thừa trên Z13 20 Bảng 3.1: Bảng đá nh số cá c chƣ̃ cá i tiế ng Anh 29 Bảng 3.2: Mã hoá thay đổi vị trí cột 32 Bảng 3.3: Mã hóa theo mẫu hình học 32 Bảng 3.4: Ví dụ mã hóa theo mẫu hình học 33 Bảng 3.5: Mã hóa hoán vị theo chu kỳ 33 Bảng 3.6: Bảng hoán vị IP 39 Bảng 3.7: Bảng hoán vị ngƣợc IP-1 39 Bảng 3.8: Bảng PC-1 41 Bảng 3.9: Bảng dịch bit tại các vòng lặp của DES 42 Bảng 3.10: Bảng PC-2 42 Bảng 3.11: Bảng mô tả hàm mở rộng E 44 Bảng 3.12: Hộp 1S 45 Bảng 3.13: Hộp 2S 45 Bảng 3.14: Hộp 3S 45 Bảng 3.15: Hộp 4S 46 Bảng 3.16: Hộp 5S 46 Bảng 3.17: Hộp 6S 46 Bảng 3.18: Hộp 7S 46 Bảng 3.19: Hộp 8S 46 Bảng 3.20: Bảng hoán vị P 47 Bảng 3.21: Ví dụ về các bƣớc thực hiện của DES 50 Bảng 3.22: Các khóa yếu của DES 51 Bảng 3.23: Các khóa nửa yếu của DES 51 Bảng 3.24: Qui ƣớ c môṭ số tƣ̀ viế t tắ t và thuâṭ ngƣ̃ củ a AES 54 Bảng 3.25: Bảng biểu diễn các xâu 4 bit 56 Bảng 3.26: Bảng độ dài khóa của AES 57 Bảng 3.27: Bảng thế S-Box củ a AES 61 Bảng 3.28: Bảng thế cho hàm InvSubBytes() 66 Bảng 4.1: Tố c đô ̣ củ a thuâṭ toá n Brent-Pollard 81 Bảng 4.2: Biể u diễn củ a tâp̣ E23(1, 1) 89 Bảng 4.3: Bảng so sánh các hệ mã ECC với hệ mã RSA 95
Lờ i nói đầu LỜ I NÓ I ĐẦ U Từ trƣớc công nguyên con ngƣời đã phải quan tâm tới việc làm thế nào đểđảm bảo an toàn bí mật cho các tài liệu, văn bản quan trọng, đặc biệt là trong lĩnh vực quân sự, ngoại giao. Ngày nay với sự xuất hiện của máy tính, các tài liệu văn bản giấy tờvà các thông tin quan trọng đều đƣợc số hóa và xử lý trên máy tính, đƣợc truyền đi trong một môi trƣờng mà mặc định là không antoàn. Do đó yêu cầu về việc có một cơ chế, giải pháp để bảo vệ sự an toàn và bí mật của các thông tin nhạy cảm, quan troṇ g ngày càng trở nên cấp thiết. Mật mã học chính là ngành khoa học đảm bảo cho mục đích này.Khó có thể thấy một ứng dụng Tin hoc̣ có ích nào lại không sử dụng các thuật toán mã hóa thông tin. Tài liệu này dựa trên những kinh nghiệm và nghiên cứu mà tác giả đã đúcrút, thu thập trong quá trình giảng dạy môn học An toàn và Bảo mậtThông tin tại khoa Công nghệ Thông tin, Đại học Hàng hải Việt nam. Với bảy chƣơng đƣợc chia thành các chủđề khác nhau từ cơ sở toán học của mật mã học cho tới các hệ mã, các giao thức mậtmã, hy vọng sẽ cung cấp cho các em sinh viên, các bạn độc giả một tài liệu bổ ích. Mặc dù đã rất cố gắng song vẫn không tránh khỏi một số thiếu sót, hy vọng sẽ đƣợc cácbạnbè đồng nghiệp, các em sinh viên, các bạn độc giả góp ý chân thành để tôi có thể hoàn thiện hơn nữa cuố n sá ch này. Xin gửi lời cảm ơn chân thành tới các bạn bè đồng nghiệp , nhƣ̃ ng ngƣờ i thân đã luôn đôṇ g viên , góp ý cho tôi trong quá trình biên soạn . Xin gƣ̉ i lờ i cả m ơn tớ i Thac̣ sy ̃ Nguyễn Đình Dƣơng , ngƣờ i đã đoc̣ và cho nhƣ̃ ng nhâṇ xé t , góp ý quí báu cho phần viết về hê ̣ mã khó a công khai dƣ̣a trên cá c đƣờ ng cong Elliptic. Xin gƣ̉ i lờ i cả m ơn sâu sắ c tớ i Thạc sỹ Phạm Tuấn Đaṭ , ngƣờ i đã hiêụ đính môṭ cá ch ky ̃ cà ng và cho rấ t nhiề u nhâṇ xé t có giá trị cho bản thảo của cuốn sách này . Cuố i cù ng xin gƣ̉ i lờ i cả m ơn tớ i Ban chủ nhiệm khoa Công nghệ Thông tin, đăc̣ biêṭ là Tiế n sy ̃ Lê Quố c Điṇ h – chủ nhiệm khoa, đã luôn tạo điều kiện tố t nhấ t, giúp đỡ để cuố n sá ch này có thể hoàn thành. Hải phòng, tháng 12 năm 2007 Tác giả Nguyễn Hữu Tuân 1
Chƣơng I: Giớ i thiêụ CHƢƠNG I: GIỚ I THIÊỤ 1. An toà n bả o mâṭ thông tin và mâṭ mã hoc̣ Trải qua nhiều thế kỷ hàng loạt các giao thức (protocol) và các cơ chế (mechanism) đã đƣợc taọ ra để đá p ƣ́ ng nhu cầ u an toà n bả o mâṭ thông tin kh i mà nó đƣợc truyề n tả i trên cá c phƣơng tiêṇ vâṭ lý (giấ y, sách, báo ). Thƣờ ng thì cá c muc̣ tiêu củ a an toà n bả o mâṭ thông tin không thể đaṭ đƣợc nế u chi ̉ đơn thuầ n dƣ̣a và o cá c thuâṭ toá n toá n hoc̣ và các giao thức, mà để đaṭ đƣợc điề u nà y đò i hỏ i cầ n có cá c ky ̃ thuâṭ mang tính thủ tuc̣ và sƣ̣ tôn troṇ g cá c điề u luâṭ . Chẳ ng haṇ sƣ̣ bí mâṭ củ a cá c bƣ́ c thƣ tay là do sƣ̣ phân phá t các lá thƣ đã có đóng dấu bởi một dịch vụ thƣ tín đã đƣợ c chấ p nhâṇ . Tính an toàn về măṭ vâṭ lý củ a cá c lá thƣ là haṇ chế (nó có thể bị xem trộm ) nên để đả m bả o sƣ̣ bí mâṭ của bức thƣ pháp luật đã đƣa ra qui định : viêc̣ xem thƣ mà không đƣợc sƣ̣ đồ ng ý củ a chủ nhân hoặc nhữ ng ngƣờ i có thẩ m quyề n là phaṃ phá p và sẽ bi ̣trƣ̀ ng phaṭ . Đôi khi mục đích của an toàn bảo mật thô ng tin laị đaṭ đƣợc nhờ chí nh phƣơng tiêṇ vâṭ lý mang chúng, chẳ ng haṇ nhƣ tiề n giấ y đò i hỏ i phả i đƣợc in bằ ng loaị mƣ̣c và giấ y tố t để không bị làm giả. Về măṭ ý tƣở ng viêc̣ lƣu giƣ̃ thông tin là không có nhiề u thay đổ i đá ng kể qua thờ i gian. Ngày xƣa thông tin thƣờng đƣợc lƣu và vận chuyển trên giấy tờ , trong khi giờ đây chúng đƣợc lƣu dƣới dạn g số hó a và đƣợc vâṇ chuyể n bằ ng cá c hê ̣ thố ng viễn thông hoăc̣ cá c hê ̣ thố ng không dây . Tuy nhiên sƣ̣ thay đổ i đá ng kể đế n ở đây chính là khả năng sao ché p và thay đổ i thông tin. Ngƣờ i ta có thể taọ ra hà ng ngà n mẩ u tin giố ng nhau và không thể phân biệt đƣợc nó với bản gốc . Vớ i cá c tà i liêụ lƣu trƣ̃ và vâṇ chuyể n trên giấ y điề u nà y khó khăn hơn nhiề u . Và điều cần thiết đối với một xã hội mà thông tin hầu hế t đƣợc lƣu trƣ̃ và vâṇ chuyể n trên các phƣơng tiện điện tử chính là các phƣơng tiện đả m bả o an toà n bả o mâṭ thông tin đôc̣ lâp̣ vớ i cá c phƣơng tiêṇ lƣu trƣ̃ và vâṇ chuyể n vâṭ lý của nó . Phƣơng tiêṇ đó chính là mâṭ mã hoc̣ , môṭ ngà nh khoa hoc̣ có lic̣ h sƣ̉ lâ u đờ i dƣ̣a trên nề n tả ng cá c thuâṭ toá n toá n hoc̣ , số hoc̣ , xác suất và các môn khoa học khác. 2. Khái niệm hệ thống và tài sản của hệ thống Khái niệm hệ thống : Hê ̣ thố ng là môṭ tâp̣ hợp cá c má y tính gồ m cá c thà nh phầ n phấ n cƣ́ ng, phầ n mề m và dƣ̃ liêụ là m viêc̣ đƣợc tích luy ̃ qua thờ i gian. Tài sản của hệ thống bao gồm: Phầ n cƣ́ ng Phầ n mề m Dƣ̃ liêụ Các truyền thông giữa các máy tính của hệ thống Môi trƣờ ng là m viêc̣ Con ngƣờ i 3. Các mối đe doa ̣ đố i vớ i môṭ hê ̣ thố ng và cá c biêṇ phá p ngăn chăṇ Có 3 hình thức chủ yếu đe dọa đối với hệ thống: 2
Chƣơng I: Giớ i thiêụ Phá hoại: kẻ thù phá hỏng thiết bị phần cứng hoặc phần mềm hoạt động trên hệ thố ng. Sƣ̉ a đổ i: Tài sản của hệ thố ng bi ̣sƣ̉ a đổ i trá i phé p. Điề u nà y thƣờ ng là m cho hê ̣ thố ng không là m đú ng chƣ́ c năng củ a nó . Chẳ ng haṇ nhƣ thay đổ i mâṭ khẩ u , quyề n ngƣờ i dù ng trong hê ̣ thố ng là m ho ̣ không thể truy câp̣ và o hê ̣ thố ng để làm việc. Can thiệ p: Tài sản bị truy cập bởi những ngƣời không có thẩm quyền . Các truyề n thông thƣ̣c hiêṇ trên hê ̣ thố ng bi ̣ngăn chăṇ , sƣ̉ a đổ i. Các đe dọa đối với một hệ thống thông tin có thể đến từ nhiều nguồn và đƣợc thực hiêṇ bở i cá c đố i tƣợng khá c nhau . Chúng ta có thể chia thành 3 loại đối tƣợng nhƣ sau : các đối tƣợng từ ngay bên trong hệ thống (insider), đây là nhƣ̃ ng ngƣờ i có quyề n truy câp̣ hợp phá p đố i vớ i hê ̣ thố ng , nhƣ̃ ng đố i tƣợng bên ngoà i hê ̣ th ống (hacker, cracker), thƣờ ng cá c đố i tƣợng nà y tấ n công qua nhƣ̃ ng đƣờ ng kế t nố i vớ i hê ̣ thố ng nhƣ Internet chẳ ng haṇ , và thứ ba là các phần mềm (chẳ ng haṇ nhƣ spyware, adware ) chạy trên hệ thố ng. Các biện pháp ngăn chặn: Thƣờng có 3 biêṇ phá p ngăn chăṇ : Điề u khiể n thông qua phầ n mề m : dƣ̣a và o cá c cơ chế an toà n bả o mâṭ củ a hê ̣ thố ng nề n (hê ̣ điề u hà nh), các thuật toán mật mã học Điề u khiể n thông qua phầ n cƣ́ ng : các cơ chế bảo mật , các thuật toán mật mã học đƣợc cứng hóa để sử dụng Điề u khiể n thông qua cá c chính sá ch củ a tổ chƣ́ c : ban hà nh cá c qui điṇ h củ a tổ chƣ́ c nhằ m đả m bả o tính an toà n bả o mâṭ củ a hê ̣ thố ng. Trong môn hoc̣ nà y chú ng ta tâp̣ trung xem xé t các thuật toán mật mã học nhƣ là môṭ phƣơng tiêṇ cơ bả n, chủ yếu để đảm bảo an toàn cho hệ thống. 4. Mục tiêu và nguyên tắc chung của an toàn bảo mật thông tin Ba muc̣ tiêu củ a an toà n bả o mâṭ thông tin: Tính bí mật: Tài sản của hệ thống chỉ đƣợc truy cập bởi những ngƣời có thẩm quyề n. Các loại truy cập gồm có : đoc̣ (reading), xem (viewing), in ấ n (printing), sƣ̉ duṇ g chƣơng trình, hoăc̣ hiể u biế t về sƣ̣ tồ n taị củ a môṭ đố i tƣợng trong tổ chƣ́ c.Tính bí mật có thể đƣợc bả o vê ̣ nhờ viêc̣ kiể m soá t truy câp̣ (theo nhiề u kiể u khá c nhau ) hoăc̣ nhờ cá c thuâṭ toá n mã hó a dƣ̃ liêụ . Kiế m soá t truy câp̣ chi ̉ có thể đƣợc thƣ̣c hiêṇ vớ i cá c hê ̣ thố ng phầ n cƣ́ ng vâṭ lý . Còn đố i vớ i cá c dƣ̃ liêụ công côṇ g thì thƣờ ng phƣơng phá p hiêụ quả là các phƣơng pháp của mật mã học. Tính toàn vẹn dữ liệu: tài sản của hệ thống chỉ đƣợc thay đổi bởi những ngƣời có thẩm quyền. Tính sẵn dùng: tài sản luôn sẵn sà ng đƣợc sƣ̉ duṇ g bở i nhƣ̃ ng ngƣờ i có thẩ m quyề n. Hai nguyên tắ c củ a an toà n bả o mâṭ thông tin: 3
Chƣơng I: Giớ i thiêụ Viêc̣ thẩ m điṇ h về bả o mâṭ phả i là khó và cầ n tính tớ i tấ t cả cá c tình huố ng , khả năng tấn công có thể đƣợc thực hiện. Tài sản đƣợc bảo vệ cho tới khi hết gía trị sử dụng hoặc hết ý nghĩa bí mật. 5. Mâṭ mã hoc̣ (cryptology) Mâṭ mã hoc̣ bao gồ m hai liñ h vƣ̣c : mã hóa (cryptography) và thám mã (cryptanalysis-codebreaking) trong đó : Mã hóa: nghiên cƣ́ u cá c thuâṭ toá n và phƣơng thƣ́ c để đả m bả o tính bí mâṭ và xác thực của thông tin (thƣờ ng là dƣớ i daṇ g cá c văn bả n lƣu trƣ̃ trên má y tính ). Các sản phẩ m củ a liñ h vƣ̣c nà y là cá c hê ̣ mã mâṭ , các hàm băm , các hệ chƣ̃ ký điêṇ tƣ̉ , các cơ chế phân phố i, quản lý khóa và các giao thức mật mã. Thám mã: Nghiên cƣ́ u cá c phƣơng phá p phá mã hoăc̣ taọ mã giả . Sản phẩm của lĩnh vực này là các phƣơng pháp thám mã , các phƣơng pháp giả mạo c hƣ̃ ký , các phƣơng phá p tấ n công cá c hà m băm và cá c giao thƣ́ c mâṭ ma.̃ Trong giớ i haṇ củ a môn hoc̣ nà y chú ng ta chủ yế u tâp̣ trung và o tìm hiể u cá c vấ n đề mã hóa với các hệ mã mật, các hàm băm, các hệ chữ ký điện tử, các giao thức mật mã. Mã hóa (cryptography) là một ngành khoa học của các phương pháp truyền tin bảo mật. Trong tiếng Hy Lạp, “Crypto” (krypte) có nghĩa là che dấu hay đảo lộn, còn “Graphy” (grafik) có nghĩa là từ. [3] Ngƣời ta quan niệm rằng: những từ, những ký tự của bản văn bả n gốc có thể hiểu đƣợc sẽ cấu thành nên bản rõ (P-Plaintext), thƣờ ng thì đây là cá c đoaṇ văn bả n trong môṭ ngôn ngƣ̃ nà o đó ; còn những từ, những ký tự ở dạng bí mật không thể hiểu đƣợc thì đƣợc gọi là bản mã (C-Ciphertext). Có 2 phƣơng thức mã hoá cơ bản: thay thế và hoán vị: Phƣơng thức mã hoá thay thế là phƣơng thức mã hoá mà từng ký tự gốchay một nhóm ký tự gốc của bản rõ đƣợc thay thế bởi các từ, các ký hiệu khác haykếthợp với nhau cho phù hợp với một phƣơng thức nhất định và khoá. Phƣơng thức mã hoá hoán vị là phƣơng thức mã hoá mà các từ mãcủabản rõ đƣợc sắp xếp lại theo một phƣơng thức nhất định. Các hệ mã mâṭ thƣờ ng sƣ̉ duṇ g kế t hợp cả hai ky ̃ thuâṭ nà y. 6. Khái niệm hệ mã mật (CryptoSystem) Một hệ mã mật là bộ 5 (P, C, K, E, D) thoả mãn các điều kiện sau: 1) P là không gian bản rõ: là tập hữu hạn các bản rõ có thể có. 2) C là không gian bản mã: là tập hữu hạn các bản mã có thể có. 3) K là kkhông gian khoá: là tập hữu hạn các khoá có thể có. 4) Đối với mỗi k K, có một quy tắc mã hoá ek E và một quy tắc giải mã tương ứng dk D. Với mỗi ek: P →C và dk: C →P là những hàm mà dk(ek(x)) = x cho mọi bản rõ x P. Hàm giải mã dk chính là ánh xạ ngược của hàm mã hóa ek [5] 4
Chƣơng I: Giớ i thiêụ Thƣờ ng thì không gian cá c bả n rõ và không gian cá c bả n mã là cá c văn bả n đƣợc tạo thành từ một bộ chữ cái A nào đó. Đó có thể là bô ̣ chƣ̃ cá i tiế ng Anh, bô ̣ mã ASCII, bô ̣ mã Unicode hoặc đơn giản nhất là các bit 0 và 1. Tính chất 4 là tính chất quan trọng nhất của mã hoá. Nội dung của nó nói rằngnếu mã hoá bằngk e và bản mã nhận đƣợc sau đó đƣợc giải mã bằng hàm dk thì kết quả nhận đƣợc phải là bản rõ ban đầu x. Rõ ràng trong trƣờng hợp này, hàmek(x) phải là một đơn ánh, nếu không thì ta sẽ không giải mã đƣợc. Vì nếu tồn tạix1 và x2 sao cho y = ek(x1) = ek(x2) thì khi nhận đƣợc bản mã y ta không biết nó đƣợc mã từx1 hay x2. Trong một hệ mật bất kỳ ta luôn có |C| ≥ |P| vì mỗi quy tắc mã hoá là một đơn ánh. Khi |C| = |P| thì mỗi hàm mã hoá là một hoán vị. 7. Mô hình truyề n tin cơ bả n củ a mâṭ mã hoc̣ và luật Kirchoff Mô hình truyề n tin thông thƣờ ng : Trong mô hình truyề n tin thông thƣờ ng thông tin đƣợc truyề n (vâṇ chuyể n) tƣ̀ ngƣờ i gƣ̉ i đế n ngƣờ i nhâṇ đƣợc thƣ̣c hiêṇ nhờ môṭ kênh vâṭ lý (chẳ ng haṇ nhƣ viêc̣ gƣ̉ i thƣ) đƣợc coi là an toà n. Mô hình truyề n tin cơ bản củ a mâṭ mã hoc̣ : K1 K2 Insecured Sender Encrypt Decrypt Receiver X Y Channel Y X Enemy Hình 1.1: Mô hình cơ bản của truyền tin bảo mật Đây là mô hình cơ bản của truyền tin bảo mật. Khác với truyền tin thông thƣờng, có các yếu tố mới đƣợc thêm vào nhƣ khái niệm kẻđịch (E-Enemy), các khoá mã hoá và giải mã K đểđ ảm bảo tính bả o mậtc ủa thông tin cần truyền đi. Trong mô hình nà y ngƣời gƣ̉ i S (Sender) muốn gửi một thông điêp̣ X (Message – là môṭ bả n rõ ) tới ngƣời nhận R (Receiver) qua một kênh truyền không an toà n (Insecured Channel), kẻ địch E (Enemy) có thể nghe trộm, hay sửa đổi thông tin X. Vì vậy, S sử dụng phép biến đổi, tức mã hoá (E-Encryption) lên thông tin X ở dạng đọc đƣợc (Plaintext) để tạo ra một đoạn văn bả n đƣợc mã hoá Y (C-Ciphertext) không thể hiể u đƣợc theo một quy luật thông thƣờ ng sƣ̉ duṇ g môṭ thông tin bí mâṭ đƣợc gọi là khoá K1 (Key), khoá K1 chính là thông số điều khiển cho phép biến đổi từ bả n rõ X sang bả n mã Y (chỉ các bên tham gia truyền tin S và R mớ i có thể biế t khó a nà y). Giải mã (D-Decryption) là quá trình ngƣợc lại cho phép ngƣời nhận thu đƣợc thông tin X banđầu từ đoạn mã hoá Y sƣ̉ duṇ g khóa giải mã K2 (chú ý là khóa giải mã và khóa mã hóa có thể khác nhau hoăc̣ là môṭ tùy thuôc̣ và o hê ̣ mã sƣ̉ duṇ g). Các phép biến đổi đƣợc sử dụng trong mô hình truyền tin trên thuộc về một hệ mã mâṭ (Cryptosytem) nào đó. 5
Chƣơng I: Giớ i thiêụ Quá trình mã hóa và giải mã yêu cầu các quá trình biến đổi dữ liệu từ dạng nguyên thuỷ thành in put cho việc mã hóa và chuyển output của q uá trình giải mã thành bản rõ . Các quá trình này là các quá trình biến đổi không khóa và đƣợc gọi là các quá trình encode và decode. Theo luâṭ Kirchoff (1835 - 1903) (một nguyên tắ c cơ bản trong mã hoá ) thì: toàn bộ cơ chế mã/giải mã trừ khoá là không bí mật đối với kẻ địch [5]. Rõ ràng khi đối phƣơng không biết đƣợc hệ mã mật đang sử dụng thuâṭ toá n mã hó a gì thì việc thá m mã sẽ rất khó khăn. Nhƣng chúng ta không thể tin vào độ an toàn của hệ mã mật chỉ dựa vào một giả thiết không chắc chắn là đối phƣơng không biết thuâṭ toá n đang sử dụng . Vì vậy, khi trình bày một hệ mật bất kỳ , chúng ta đều giả thiết hệ mật đó đƣợc trình bày dƣới luâṭ Kirchoff. Ý nghĩa của luật Kirchoff : sƣ̣ an toà n củ a cá c hê ̣ mã mâṭ không phải dựa vào sự phƣ́ c tap̣ củ a thuâṭ toá n mã hó a sƣ̉ duṇ g. 8. Sơ lƣợc về lic̣ h sƣ̉ mâṭ mã hoc̣ Mâṭ mã hoc̣ là môṭ ngà nh khoa hoc̣ có môṭ lic̣ h sƣ̉ khoả ng 4000 năm. Các cổ vật của ngành khảo cổ học thu đƣợc đã cho thấ y điề u nà y. Nhƣ̃ ng ngƣờ i Ai câp̣ cổ đaị đã sƣ̉ dụng các chữ tƣợng hình nhƣ là một dạng mã hóa đơn giản nhất trên các bia mộ của họ . Các tài liệu viết tay khác cũng cho thấy các phƣơng pháp mã hóa đơn giản đầu tiên mà loài ngƣời đã sử dụng là của ngƣời Ba Tƣ cổ và ngƣời Do Thái cổ. Tuy vâỵ có thể chia lic̣ h sƣ̉ mâṭ mã hoc̣ thà nh hai thờ i kỳ nhƣ sau: Thờ i kỳ tiề n khoa hoc̣ : Tƣ̀ trƣớ c công nguyên cho tớ i năm 1949. Trong giai đoaṇ này mật mã học đƣợc coi là môṭ nghê ̣ thuâṭ nhiề u hơn là môṭ môn khoa hoc̣ măc̣ dù đã đƣợc ƣ́ ng duṇ g trong thƣ̣c tế. Lịch sử của mật mã học đƣợc đánh dấu vào năm 1949 khi Claude Shannon đƣa ra lý thuyết thông tin . Sau thờ i kỳ nà y môṭ loaṭ cá c nghi ên cƣ́ u quan troṇ g củ a nghà nh mâṭ mã học đã đƣợc thực hiện chẳng hạn nhƣ các nghiên cứu về mã khối , sƣ̣ ra đờ i củ a cá c hê ̣ mã mâṭ khó a công khai và chƣ̃ ký điêṇ tƣ̉ . Qua nhiề u thế kỷ phá t triể n củ a mâṭ mã hoc̣ chủ yế u đƣ ợc phục vụ cho các mục đích quân sƣ̣ (gián điệp , ngoại giao , chiế n tranh ). Môṭ ví du ̣ điể n hình là 2000 năm trƣớ c đây hoà ng đế La mã Julius Caesar đã tƣ̀ ng sƣ̉ duṇ g môṭ thuâṭ toá n thay thế đơn giản mà ngày nay đƣợc mang tên ông trong cuôc̣ chiế n tranh Gallic. Tác phẩm “A manuscript on Deciphering Cryptography Messages” của Abu al -Kindi đƣợc viết vào thế kỷ9 thứ đƣợc tìm thấ y taị Istabul và o năm 1987 đã cho thấ y nhƣ̃ ng nhà khoa hoc̣ Ả râp̣ là nhƣ̃ ng ngƣờ i đầ u tiên đã phá t triể n cá c phƣơng phá p thá m mã dƣ̣a và o phân tích tầ n số xuấ t hiêṇ củ a cá c ký tƣ̣ đố i vớ i cá c hê ̣ mã thay thế đơn âm (môṭ phƣơng pháp đƣợc sử dụng rộng rãi trong thời kỳ Trung cổ do đơn giản và khá hiệu quả). Ở châu Âu thờ i kỳ Trung cổ là môṭ khoả ng thờ i gian u á m và tăm tố i củ a lic̣ h sƣ̉ nên không có nhiề u phá t triể n maṇ h về văn hó a nó i chung và mâṭ mã hoc̣ nó i riêng . Một vài sự kiện đƣợc ghi lại bởi các vị linh mục nhƣng chỉ có Roger Bacon là ngƣời thực sự đã viết về mật mã học trong tác phẩm “Secret Work of Art and the Nullity of Magic” vào giữa những năm 1200. Vào thời Trung cổ một trong những cái tên nổi tiếng nhất là Chaucer, ngƣờ i đã đƣa ra các công trình nghiên cứu nghiêm túc đầu tiên về mật mã học trong các 6
Chƣơng I: Giớ i thiêụ tác phẩm của mình chẳng hạn nhƣ “Treatise on the Astrolabe”. Trong thờ i kỳ Trung cổ ở phƣơng Tây cuốn sách của Blaise De Vegenere (ngƣờ i phá t minh ra thuâṭ toá n mã hó a thay thế đa âm tiế t ) đƣợc xem nhƣ là môṭ tổng kết các kiến thức về mật mã học cho tới thời điểm bấy giờ, bao gồm cả thuật toán thay thế đa âm tiết và một vài sơ đồkhóatự động. Blaise De Vegenere cũng là tá c giả củ a hê ̣ mã mang tên ông , hê ̣ mã nà y đã tƣ̀ ng đƣợc xem là an toà n tuyêṭ đố i và đƣợc sƣ̉ duṇ g trong môṭ thờ i gian dà i, tuy nhiên Charles Babbages đã thực hiện thám mã thành công vào năm 1854 nhƣng điều này đƣợc giữ bí mật. Môṭ thuật toán thám mã đƣợc phát hiện độc lậ p bởi một nhà khoa học ngƣời Phổ (thuôc̣ nƣớ c Đƣ́ c ngà y nay) có tên là Friedrich Kasiski . Tuy vâỵ do việc thiếu các thiết bị cải tiến nên các biến thể của thuật toán mã hóa này vẫn còn đƣợc sử dụng trongnhững năm đầu của thế kỷ 20 mà tiêu biểu nhất là việc thám mã thành công máy điện tín Zimmermann củ a quâ n Đƣ́ c (môṭ trong cá c sƣ̣ kiêṇ tiêu biể u củ a mâṭ mã hoc̣ ) trong thế chiến thứ nhất và kết quả là sự tham gia của Mỹ vào cuộc chiến. Vớ i sƣ̣ xuấ t hiêṇ củ a cá c hê ̣ thố ng má y tính cá nhân và maṇ g má y tính cá c thông tin văn bả n ngà y cà ng đƣợc lƣu trƣ̃ và xƣ̉ lý nhiề u hơn trên cá c má y tính do đó nả y sinh yêu cầ u về an toà n bả o mâṭ đố i vớ i cá c thông tin đƣợc lƣu trƣ̃ , xƣ̉ lý và truyề n giƣ̃ a cá c má y tính. Vào đầu những năm 1970 là sự phát triển của các thuật toán mã hóa khối đầu tiên: Lucipher và DES . DES sau đó đã có môṭ sƣ̣ phá t triể n ƣ́ ng duṇ g rƣ̣c rỡ cho tớ i đầ u nhƣ̃ ng năm 90. Vào cuối những năm 1970 chứng kiến sự phát triển của các thuật toánmãhóa khóa công khai sau khi Whitfield Diffie và Martin Hellman công bố bà i bá o “New Directions in Cryptography” làm nền tảng cho sự ra đời của các hệ mã khóa công khai và các hệ chƣ̃ ký điêṇ tƣ̉ . Do nhƣợc điể m củ a cá c hê ̣ mã mâṭ khó a công khai là châṃ nên cá c hê ̣ mã khố i vẫn tiế p tục đƣợc phát triển với các hệ mã khối mới ra đời để thay thế cho DES và o cuố i thế kỷ 20 nhƣ IDEA, AES hoăc̣ 3DES (môṭ cả i tiế n của DES). Gầ n đây nhấ t là các sự kiện liên quan tới các hàm băm MD5 (môṭ hà m băm thuôc̣ họ MD d o Ron Rivest phá t triể n ) và SHA 1. Môṭ nhó m cá c nhà khoa học ngƣời Trung Quố c (Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu) đã phá t triể n các phƣơng pháp cho phép phát hiện ra các đụng độ của các hàm băm đƣợc sử dụng rộng rãi nhất trong số cá c hàm băm này. Đây là môṭ sƣ̣ kiêṇ lớ n đố i vớ i ngà nh mâṭ mã hoc̣ do sƣ̣ ƣ́ ng duṇ g rôṇ g rãi và có thể xem là còn quan trọng hơn bản thân các hệ mã mật của các hàm băm . Do sƣ̣ kiêṇ nà y cá c hãng viế t phầ n mề m lớ n (nhƣ Microsoft) và các nhà mật mã học đã khuyến cáo các lập trình viên sử dụng các hàm băm mạnh hơn (nhƣ SHA-256, SHA-512) trong các ứng dụng. Bruce Schneier (môṭ trong nhƣ̃ ng nhà mâṭ mã hoc̣ hà ng đầ u , tác giả của hệ mã Blowfish) đã tƣ̀ ng nó i rằ ng cá c hình thƣ́ c tấ n công đố i vớ i cá c hê ̣ mã mâṭ nó i riêng và tấ n công đố i vớ i cá c hê ̣ thố ng má y tính nó i chung sẽ ngà y cà ng trở nên hoà n thiêṇ hơn “Attacks always get better ; they never get worse .” và li c̣ h sƣ̉ phá t triể n củ a mâṭ mã hoc̣ chính là lịch sử phát triển của các hình thức tấn công đối với các hệ mã mật đang đƣợc sƣ̉ duṇ g. 7
Chƣơng I: Giớ i thiêụ 9. Phân loaị cá c thuâṭ toá n mâṭ mã hoc̣ Có nhiều cách khác nhau để chúng ta có thể phâ n loaị cá c thuâṭ toá n mâṭ mã hoc̣ sẽ đƣợc học trong chƣơng trình. Ở đây chúng ta sẽ phân loại các thuật toán mật mã học dƣ̣a và o hai loaị tiêu chí. Tiêu chí thƣ́ nhấ t là dƣ̣a và o cá c dic̣ h vu ̣ an toà n bả o mâṭ mà cá c thuâṭ toán cung cấ p, dƣ̣a và o số lƣợng khó a sƣ̉ duṇ g (0, 1, 2) chúng ta có các thuật toán mã hóa sau: 1. Các thuật toán mã hóa khóa bí mật tƣơng ứng với các hệ mã mật khóa bí mật hay khó a đố i xƣ́ ng SKC (Symmetric Key Cryptosytems), do vai trò củ a ngƣờ i nhâṇ và ngƣờ i gƣ̉ i là nhƣ nhau , cả hai đều có thể mã hóa và giải mã thông điệp , nhƣ Caesar, DES, AES Khó a sƣ̉ duṇ g cho cá c thuâṭ toá n nà y là 1 khóa cho cả việc mã hóa và giải mã. 2. Các thuật toán mã hóa khóa công khai tƣơng ứng với các hệ mã khóa công khai PKC (Public Key Cryptosystems). Đôi khi cá c hê ̣ mã nà y cò n đƣợc goị là cá c hê ̣ mã khóa bất đối xứng (Asymmetric Key Cryptosytems). Khóa sử dụng cho các thuật toán này là 2 khóa, môṭ cho viêc̣ mã hó a và môṭ cho viêc̣ giả i mã , khóa mã hóa đƣợc công khai hóa. 3. Các thuật toán tạo chữ ký điện tử (Digital Signature Algorithms). Các thuật toán tạo chữ ký điện tử tạo thành các hệ chữ ký điện tử . Thông thƣờ ng mỗi hê ̣ chƣ̃ ký điêṇ tƣ̉ có cù ng cơ sở lý thuyế t vớ i môṭ hê ̣ mã mâṭ khó a công khai nhƣng vớ i cá ch á p dụng khác nhau. Trong chƣơng trình hoc̣ chú ng ta sẽ hoc̣ môṭ số hê ̣ chƣ̃ ký điêṇ tƣ̉ phổ biế n là RSA, ElGammma 4. Các hàm băm (Hash functions). Các hàm băm là các thuật toán mã hóa không khóa hoặc có khóa và thƣờng đƣợc sử dụng trong các hệ chữ ký điện tử hoặc các hệ mã khóa công khai. Tiêu chí thƣ́ hai phân loaị cá c thuâṭ toá n mã hóa dựa trên cách thức xử lý input của thuâṭ toá n (tƣ́ c là bả n rõ ), dƣ̣a trên tiêu chí nà y chú ng ta có hai loaị thuâṭ toá n mã hó a sau: 1. Các thuật toán mã hóa khối (chẳ ng haṇ nhƣ DES , AES ) xƣ̉ lý bả n rõ dƣớ i các đơn vị cơ bản là các khối có kích thƣớc giống nhau. 2. Các thuật toán mã hóa dòng (RC4 ) coi bả n rõ là môṭ luồ ng bit, byte liên tuc̣ . 10. Môṭ số ƣ́ ng duṇ g củ a mâṭ mã hoc̣ Ngày nay khó có thể tìm thấy các ứng dụng trên máy tính lại không sƣ̉ duṇ g tớ i cá c thuâṭ toá n và cá c giao thƣ́ c mâṭ mã hoc̣ . Tƣ̀ cá c ƣ́ ng duṇ g cho cá c má y tính cá nhân (Desktop Applications ) cho tớ i cá c chƣơng trình hê ̣ thố ng nhƣ cá c hê ̣ điề u hà nh (Operating Systems) hoăc̣ cá c ƣ́ ng duṇ g mang̣ nhƣ Yahoo Messenger hoăc̣ cá c hê ̣ cơ sở dƣ̃ liêụ đề u có sƣ̉ duṇ g cá c thuâṭ toá n mã hó a mâṭ khẩ u ngƣờ i dù ng bằ ng môṭ hê ̣ mã hoăc̣ môṭ hà m băm nà o đó . Đặc biệt với sự phát triển mạnh mẽ của thƣơng mại điện tử các mô hình chƣ̃ ký điêṇ tƣ̉ ngà y cà ng đó ng vai trò tích cƣ̣c cho môṭ môi trƣờ ng an toà n cho ngƣờ i dù ng. Tuy vâỵ chú ng ta vẫn có thể chia cá c liñ h vực ứng dụng của mật mã học thành các lĩnh vực nhỏ nhƣ sau: 8
Chƣơng I: Giớ i thiêụ Bảo mật (Confidentiality): che dấ u nôị dung củ a cá c thông điêp̣ đƣợc trao đổ i trong môṭ phiên truyề n thông hoăc̣ giao dic̣ h hoăc̣ cá c thông điêp̣ trên môṭ hê ̣ thố ng má y tính (các file, các dữ liệu trong một cơ sở dữ liệu ). Xác thực hóa (Authentication): đả m bả o nguồ n gố c củ a môṭ thông điêp̣ , ngƣờ i dùng. Toàn vẹn (Integrity): đả m bả o chi ̉ có cá c tổ chƣ́ c đã đƣợc xá c thƣ̣c hó a mớ i có thể thay đổ i cá c tà i sả n củ a hê ̣ thố ng cũng nhƣ cá c thông tin trên đƣờ ng truyề n. Dịch vụ khôn g thể chố i tƣ̀ (Non-Repudiation): Các bên đã đƣợc xác thực không thể phủ nhâṇ viêc̣ tham gia và o môṭ giao dic̣ h hợp lê.̣ Ngoài ra còn các dịch vụ quan trọng khác chẳng hạn nhƣ chữ ký điện tử , dịch vụ chứng thực danh tính (Identification) cho phé p thay thế hình thƣ́ c xá c thƣ̣c hó a ngƣờ i dùng dựa trên các mật khẩu bằng các kỹ thuật mạnh hơn hoăc̣ dic̣ h vu ̣ thƣơng maị điêṇ tƣ̉ cho phé p tiế n hà nh cá c giao dic̣ h an toà n trên cá c kênh truyề n thông không an t oàn nhƣ Internet. 9
Chƣơng II: Cơ sở toán học CHƢƠNG II: CƠ SỞ TOÁN HỌC Để hiể u đƣợc nhƣ̃ ng thuâṭ toá n sƣ̉ duṇ g trong cá c hê ̣ mã mâṭ , trong cá c hê ̣ chƣ̃ ký điêṇ tƣ̉ cũng nhƣ cá c giao thƣ́ c mâṭ mã , chúng ta phải có những kiến thức nề n tả ng cơ bản về toán hoc̣ , lý thuyết thông tin đƣợc sƣ̉ duṇ g trong mâṭ mã hoc̣ . Chƣơng nà y trình bày nhƣ̃ ng khá i niêṃ cơ bả n về lý thuyế t thông tin nhƣ Entropy , tố c đô ̣ củ a ngôn ngƣ̃ (Rate of Language), đô ̣ phƣ́ c tap̣ củ a thuâṭ toá n , đô ̣ an toà n củ a thuâṭ toá n, và một số kiế n thƣ́ c toán học: đồ ng dƣ số hoc̣ (modulo), số nguyên tố , điṇ h lý phầ n dƣ trung hoa , điṇ h lý Fermat . . . và các thuật toán kiể m tra số nguyên tố . Nhƣ̃ ng vấ n đề chính sẽ đƣợc trình bày trong chƣơng này gồ m : Lý thuyết thông tin Lý thuyết độ phức tạp Lý thuyết số học. 1. Lý thuyết thông tin Nhƣ̃ ng khá i niêṃ mở đầ u củ a lý thuyết thông tin đƣợc đƣa ra lầ n đầ u tiên và o năm 1948 bở i Claude Elmwood Shannon (môṭ nhà khoa hoc̣ đƣ ợc coi là cha để của lý thuyết thông tin). Trong phầ n nà y chú ng ta chi ̉ đề câp̣ tớ i môṭ số chủ đề quan troṇ g củ a lý thuyế t thông tin. 1.1. Entropy Lý thuyết thông tin định nghĩa khố i lƣợng thông tin trong môṭ thông bá o là số bít nhỏ nhấ t cầ n thiế t để mã hoá tấ t cả nhƣ̃ ng nghiã có thể củ a thông bá o đó . Ví dụ, trƣờ ng ngay_thang trong môṭ cơ sở dƣ̃ liêụ chƣ́ a không quá 3 bít thông tin, bở i vì thông tin ngà y có thể mã hoá với 3 bít dữ liệu: 000 = Sunday 001 = Monday 010 = Tuesday 011 = Wednesday 100 = Thursday 101 = Friday 110 = Saturday 111 is unused Nế u thông tin nà y đƣợc biể u diễn bở i chuỗi ký tƣ̣ ASCII tƣơng ƣ́ ng , nó sẽ chiếm nhiề u không gian nhớ hơn , nhƣng cũng không chƣ́ a nhiề u thông tin hơn . Tƣơng tƣ̣ nhƣ trƣờ ng gioi_tinh củ a môṭ cơ sở dƣ̃ liêụ chỉ chứa 1 bít thông tin, nó có thể lƣu trữ nhƣ một trong hai xâu ký tƣ̣ ASCII : Nam, Nƣ̃. Khố i lƣợng thông tin trong môṭ thông bá o M đo bở i Entropy củ a thông bá o đó , ký hiêụ là H(M). Entropy củ a thông bá o gioi _tinh là 1 bít, ký hiệu H (gioi_tinh) = 1, Entropy của thông báo số ngày trong tuần là nhỏ hơn 3 bits. 10
Chƣơng II: Cơ sở toán học Trong trƣờ ng hợp tổ ng quát, Entropy của một thông báo là log 2n, vớ i n là số khả năng có thể (ý nghĩa) của thông báo. H(M) = log2n 1.2. Tố c đô ̣ củ a ngôn ngƣ̃. (Rate of Language) Đối với một ngôn ngữ, tố c đô ̣ thƣ̣c tế (actual rate) của ngôn ngữ là: r = H(M)/N trong trƣờ ng hợp nà y N là đô ̣ dà i củ a thông bá o và M là một thông điệp có độ dài N. Tố c đô ̣ củ a tiế ng Anh bình thƣờ ng là 0.28 do đó mỗi chƣ̃ cá i tiế ng Anh có 1.3 bit nghĩa. Tố c đô ̣ tuyêṭ đố i (absolute rate) của môṭ ngôn ngƣ̃ là số bits lớ n nhấ t cầ n thiế t để mã hóa các ký tƣ̣ củ a ngôn ngƣ̃ đó . Nế u có L ký tƣ̣ trong môṭ ngôn ngƣ̃ , thì tốc độ tuyệt đố i là : R = log2L Đây là số Entropy lớ n nhấ t củ a mỗi ký tƣ̣ đơn lẻ . Đối với tiếng Anh gồm 26 chƣ̃ cá i, tố c đô ̣ tuyêṭ đố i là log 226 = 4.7bits/chƣ̃ cái. Sẽ không có điều gì là ngạc nhiên đối với tất cả mọi ngƣời rằng thực tế tốc độ của tiếng Anh nhỏ hơn nhiề u so vớ i tố c đô ̣ tuyêṭ đố i , và chúng ta vẫn thấy rằng đối với một thông báo bằng tiếng Anh có thể loại bỏ môṭ số chƣ̃ cái nhƣng ngƣời đọc vẫn có thể hiểu đƣợc . Hiêṇ tƣợng nà y đƣợc goị là đô ̣ dƣ thƣ̀ a củ a ngôn ngƣ̃ (Redundancy) tƣ̣ nhiên. Không chi ̉ đố i vớ i tiế ng Anh mà vớ i hầ u hế t cá c ngôn ngƣ̃ tƣ̣ nhiên , do cấ u trú c củ a ngôn ngƣ̃ , do viêc̣ sƣ̉ duṇ g ngôn ngƣ̃ dẫn tớ i có môṭ số chƣ̃ cá i đƣợc sƣ̉ duṇ g vớ i tầ n suấ t không đồ ng đề u hoăc̣ chi ̉ có thể xuấ t hiêṇ vớ i môṭ cấ u trú c nà o đó là m cho chú ng ta vẫn có thể đoá n đƣợc nghiã củ a cá c thông bá o nế u loại bỏ cá c chƣ̃ cá i nà y. Độ dƣ thừa (Redundancy) của một ngôn ngữ ký hiệu là D và D = R – r. Đối với tiế ng Anh: D = 1 - .28 = .72 letters/letter D = 4.7 – 1.3 = 3.4 bits/letter Nhƣ vâỵ mỗi chƣ̃ cá i có 1.3 bit nghiã và 3.4 bit dƣ thƣ̀ a (xấ p xi ̉ 72%). 1.3. Tính an toà n củ a hê ̣ thố ng mã hoá Shannon điṇ h nghiã rấ t rõ rà ng , tỉ mỉ các mô hình toán học để đánh giá độ an toà n của các hệ mã mật sử dụng . Mục đích của ngƣời thám mã là phát hiện ra khoá sƣ̉ dụng của hệ mã (K-Key), bản rõ (P-PlainText), hoăc̣ cả hai . Hơn nƣ̃ a ho ̣ có thể hà i lò ng vớ i môṭ và i thông tin có khả năng về bả n rõ P chẳ ng haṇ nhƣ đó là âm thanh dạng số , hoăc̣ là một văn bả n tiế ng Đƣ́ c, hoăc̣ là môṭ bảng tính dữ liệu, v. v . . . Trong hầ u hế t cá c lầ n thám mã, ngƣờ i thám mã thƣờ ng cố gắ ng thu thâp̣ môṭ số thông tin có khả năng về bản rõ P trƣớ c khi bắ t đầ u. Họ có thể biết ngôn ngữ đã đƣợc sƣ̉ dụng để mã hoá. Ngôn ngƣ̃ nà y chắ c chắ n có sƣ̣ dƣ thƣ̀ a kế t hợp vớ i chính ngôn ngƣ̃ đó . Nế u nó là môṭ thông bá o gƣ̉ i tớ i Bob, nó có thể bắt đầu với "Dear Bob". Đoaṇ văn bả n 11
Chƣơng II: Cơ sở toán học "Dear Bob" sẽ là một khả năng có thể hơn là môṭ chuỗi không mang ý nghiã gì chẳng hạn "tm*h&rf". Mục đích của việc thám mã là sửa những tập hợp khả năng có thể có của bản mã (C-CipherText) vớ i mỗi khả năng có thể củ a bả n rõ. Shannon phá t triể n lý thuyế t cho rằ ng , hê ̣ thố ng mã hoá chi ̉ an toà n tuy ệt đối nếu nế u số khoá có thể sƣ̉ duṇ g ít nhất phải bằ ng số thông bá o có thể . Hiể u theo môṭ nghiã khác, khoá tối thiểu của hệ mã phải dài bằng thông báo của hê ̣ mã đó . Ngoại trừ các hệ mã an toà n tuyêṭ đố i , các bản mã thƣờ ng chƣ́ a môṭ số thông tin đú ng vớ i bả n rõ , điề u nà y là không thể trá nh đƣợc . Môṭ thuâṭ toá n mâṭ mã tố t giƣ̃ cho thông tin bị tiết lộ ở mức nhỏ nhất và môṭ ngƣờ i thá m mã giỏ i sẽ khai thá c tố t nhƣ̃ ng thông tin nà y để phá t hiêṇ ra bả n rõ. Ngƣờ i thám mã sử dụng sự dƣ thừa tự nhiên của ngôn ngữ để làm giảm số khả năng có thể có của bản rõ . Nhiề u thông tin dƣ thƣ̀ a củ a ngôn ngƣ̃ , sẽ dễ dàng hơn cho quá trình thám mã. Chính vì lý do nà y mà nhiề u mô hình mã hó a sƣ̉ duṇ g thuâṭ toá n nén bản rõ để giảm kích thƣớc văn bản trƣớc khi mã hoá chúng. Vì quá trình nén làm giảm sự dƣ thƣ̀ a củ a thông bá o . Entropy của môṭ hê ̣ mã mật là kích thƣớc của không g ian khoá (Keyspace). H(K) = log2(number of keys ) Shannon cũng đƣa ra môṭ khá i niêṃ goị là Unicity Distance (ký hiệu là U ) để đánh giá độ an toàn của một hệ mã mật. Đối với một hệ mã mật U của nó là: U = H(K)/D Đây là số nhỏ nhấ t cá c bả n mã cầ n thiế t để có thể tiế n hà nh thá m mã theo cá ch thƣ̉ tấ t cả cá c khó a có thể (brute-force attack) thành công. Chẳ ng haṇ đố i vớ i hê ̣ mã thay thế đơn âm (nhƣ Caesar) trên bả ng chƣ̃ cá i tiế ng Anh ta sẽ có : H(K)= log226! = 87. D = 3.4 suy ra U = 25.5. Điề u nà y có nghiã là nế u chú ng ta có khoả ng 25 chƣ̃ cá i bả n mã chú ng ta chi ̉ có thể thƣ̉ để khớ p vớ i môṭ bả n ro.̃ Khái niệm Unicity Distance là một khái niệm mang tính xác suất nó cho ch úng ta biế t số lƣợng ít nhấ t cá c bả n mã cầ n có để có thể xá c điṇ h duy nhấ t 1 bản mã chứ không phải là số bản mã đủ để tiến hành thám mã (chắ c chắ n thà nh công ). Nế u chú ng ta có số bản mã ít hơn số U thì không thể nói là dự đoán (phép thử) của chúng ta là đúng . Dƣ̣a vào công thức này chúng ta thấy nếu nhƣ độ dƣ thừa của ngôn ngữ càng gần 0 thì càng khó thám mã mặc dù đó có thể là một hệ mã rất đơn giản . Cũng dựa vào công thứ c nà y suy ra để tăng tính an toà n củ a hê ̣ mã có thể tăng không gian khó a củ a nó . 1.4. Kỹ thuật lôṇ xôṇ và rƣờ m rà (Confusion and Diffusion) Theo Shannon, có hai kỹ thuật cơ bản để che dấu sự dƣ thừa thông tin trong thông báo gốc, đó là : sƣ̣ lôṇ xôṇ và sƣ̣ rƣờ m rà. Kỹ thuật lộn xộn (Confusion): che dấ u mố i quan hê ̣ giƣ̃ a bả n rõ và bả n gố c . Kỹ thuâṭ nà y là m thấ t baị các cố gắ ng nghiên cƣ́ u bả n mã để tìm kiếm thông tin dƣ thừa và thố ng kê mẫu . Phƣơng phá p dễ nhấ t để thƣ̣c hiêṇ điề u nà y là thông qua kỹ thuật thay thế . Môṭ hê ̣ mã hoá thay thế đơn giả n , chẳ ng haṇ hê ̣ mã dic̣ h vò ng Caesar , dƣ̣a trên nề n 12
Chƣơng II: Cơ sở toán học tảng của sự thay thế các chƣ̃ cá i của bản ,rõ nghĩa là chữ cái này đƣ ợc thay thế bằng chƣ̃ cá i khá c Kỹ thuật rƣờm rà (Diffusion): làm mất đi sự dƣ thừa của bản rõ bằng cách tăng sự phụ bản mã vào bản rõ (và khóa). Công viêc̣ tìm kiế m sƣ̣ dƣ thƣ̀ a củ a ngƣờ i thá m mã sẽ rất mất thời gian và phức tạp. Cách đơn giản nhất tạo ra sự rƣờm rà là thông qua việc đổ i chỗ (hay cò n goị là kỹ thuật hoán vị). Thông thƣờ ng cá c hê ̣ mã hiêṇ đaị thƣờ ng kế t hợp cả hai ky ̃ thuâṭ thay thế và hoá n vị để tạo ra các thuật toán mã hóa có độ an toàn cao hơn. 2. Lý thuyết độ phức tạp Lý thuyết độ phức tạp cung cấp một phƣơng pháp để phân tích độ phức tạp tính toán của thuật toán và các kỹ thuật mã hoá khác nhau . Nó so sánh các thuật toán mã hoá, kỹ thuật và phát hiện ra độ an toàn của các thuật toán đó . Lý thuyết thông tin đã cho chúng ta biết rằng một thuật toán mã hoá có thể bị bại lộ . Còn lý thuyết độ phứ c tap̣ cho biế t khả năng bi ̣thá m mã củ a môṭ hê ̣ mã mật. Độ phức tạp thời gian của thuật toán là môṭ hà m củ a kích thƣớ c dƣ̃ liêụ input củ a thuâṭ toá n đó . Thuâṭ toá n có đô ̣ phƣ́ c tap̣ thờ i gian f (n) đố i vớ i moị n và kích thƣớc input n, nghĩa là số bƣớc thƣ̣c hiêṇ củ a thuật toán lớn hơn f(n) bƣớ c. Độ phức tạp thời gian thuật toán phụ thuộc vào mô hình của các thuật toán , số cá c bƣớ c nhỏ hơn nế u cá c hoaṭ đôṇ g đƣợc tâp̣ trung trong môṭ bƣớ c (chẳ ng haṇ nhƣ cá c vòng lặp, các lời gọi hàm ). Các lớp của thuật toán, vớ i đô ̣ phƣ́ c tap̣ thờ i gian là một hàm mũ đố i vớ i kích thƣớ c input đƣợc coi là "không có khả năng thƣ̣c hiêṇ ". Các thuật toán có độ phức tạp giống nhau đƣợc phân loaị và o trong cá c lớ p tƣơng đƣơn g. Ví dụ tất cả các thuật toán có độ 3 3 3 phƣ́ c tap̣ là n đƣợc phân và o trong lớ p n và ký hiệu bởi O(n ). Có hai lớp tổng quát sẽ đƣợc là lớ p P (Polynomial) và lớp NP (NonPolynomial). Các thuật toán thuộc lớp P có độ phức tạ p là hà m đa thƣ́ c củ a kích thƣớc input . Nế u mỗi bƣớ c tiế p theo củ a thuâṭ toá n là duy nhấ t thì thuâṭ toá n goị là đơn điṇ h . Tấ t cả thuâṭ toá n thuôc̣ lớ p P đơn điṇ h có thờ i gian giớ i haṇ là P _time, điề u nà y cho biế t chú ng sẽ thực hiện trong thời gian đa thức , tƣơng đƣơng vớ i đô ̣ phƣ́ c tap̣ đa thƣ́ c của kích thƣớ c input. Thuâṭ toán mà ở bƣớc tiếp theo việc tính toán phải lựa chọn giải pháp từ những giớ i haṇ giá tri ̣củ a hoaṭ đôṇ g goị là không đơn điṇ h. Lý thuyết độ phức tạp sử dụng các máy đặc biệt mô tả đặc điểm bằng cách đƣa ra kết luận bởi các chuẩn . Máy Turing là môṭ má y đăc̣ biêṭ , máy hoạt động trong thời gian rời rạc , tại một thời điểm nó nằm trong khoảng trạng thái đầy đủ số của tất cả các trạng thái có thể là hữu hạn . Chúng ta có thể điṇ h nghiã hà m đô ̣ phƣ́ c tap̣ thờ i gian kế t hợp vớ i má y Turing A. 3 fA(n) = max{m/A kế t thú c sau m bƣớ c vớ i đầ u và o w = n } Ở đây chúng ta giả sử rằng A là trạng thái kết thúc đối với tất cả các đầu vào , vấ n đề sẽ trở nên khó khăn hơn nếu các trạng thái không nằm trong P . Máy Turing k hông đơn điṇ h hoaṭ đôṇ g vớ i thuâṭ toá n NP. Máy Turing không đơn định có thể có môṭ và i traṇ g 13
Chƣơng II: Cơ sở toán học thái chính xác. S(w) là trạng thái đo sự thành công ngắn nhất của thuật toán, (Nghĩa là sự tính toán dẫn đến trạng thái cuối cùng) Hàm số độ phức tạp thời gian của máy Turing không đơn định A đƣợc điṇ h nghiã : fA(n)=max{1,m/s(w) có m bƣớc đối với w/w=n} ở mỗi bƣớc máy Turing không đơn định bố trí nhiều bản sao của chính nó nhƣ có môṭ và i giả i phá p và tính toá n đôc̣ lâp̣ vớ i moị lờ i giả i. Các thuật toán thuộc lớ p NP là không đơn điṇ h và có thể tính toá n trên má y Turing không đơn điṇ h trong thờ i gian P. Tuy nhiên không phả i thuâṭ toá n mã hó a cà ng có đô ̣ phƣ́ c tap̣ lớ n thì hê ̣ mã mâṭ sƣ̉ dụng thuật toán đó sẽ càng an toà n theo nhƣ phát biểu của luật Kierchoff. Vâỵ có thể đá nh giá đô ̣ an toà n củ a môṭ hê ̣ mã mâṭ nhƣ thế nà o ? Vấ n đề này đã đƣợc Claude Shannon trả lờ i vớ i cá c khá i niêṃ về đô ̣ an toà n củ a cá c hê ̣ mã mâṭ trong môṭ bài báo có tiêu đề “Lý thuyết thông tin của các hệ thống bảo mật” (1949). 2.1. Độ an toàn tính toán Định nghĩa: Một hệ mật được gọi là an toàn về mặt tính toán nếu có một thuật toán tốt nhất để phá nó thì cần ít nhất N phép toán, với N là một số rất lớn nào đó. [10] Tuy nhiên trong thực tế, không có một hệ mật nào chứng tỏ là an toàn theo định nghĩa trên. Vì vậy, trên thực tế, ngƣời ta gọi hệ mật là “an toàn tính toán” nếu cómột thuật toán để phá nó nhƣng đòi hỏi thời gian lớn đến mức không chấp nhận đƣợc (thuâṭ toán có độ phƣ́ c tap̣ hà m mũ hoăc̣ thuôc̣ lớ p cá c bà i toá n có đô ̣ phƣ́ c tap̣ NP). Một cách tiếp cận khác về độ “an toàn tính toán” là quy nó về một bài toán đãđƣợc nghiên cứu kỹ và đƣợc coi là khó. Ví dụ nhƣ bài toán “phân tích ra thừa số nguyên tốcủa một số n cho trƣớc” đƣợc coi là bài toán khó với n lớn, vì vậy ta có thể coi một hệmật dựa trên bài toán “phân tích ra thừa số nguyên tố” là an toàn (tất nhiên đây chỉ làđộan toàn dựa vào chứng minh một bài toán khác chứ không phải chứng minh hoàn chỉnhvề độ an toàn của hệ mật). 2.2. Độ an toàn không điều kiện Định nghĩa 1: Một hệ mật được coi là an toàn không điều kiện khi nó không thể bị phá ngay cả với khả năng tính toán không hạn chế. [10] Rõ ràng là “độ an toàn không điều kiện” không thể nghiên cứu theoquan điểm độ phức tạp tính toán vì thời gian tính toán là không hạn chế. Vì vậy, ở đây lý thuyết xácsuất sẽ đƣợc đề cập để nghiên cứu về “an toàn không điều kiện”. Định nghĩa 2: Giả sử biến X và Y là các biến ngẫu nhiên. Ký hiệu xác suất để Xnhậngiátrị x là p(x) và để Y nhận giá trị y là p(y). Xác suất đồng thời p(x, y) là xác suất để đồngthờiX nhận giá trị x và Y nhận giá trị y. Xác suất có điều kiện p(x/y) là xác suất để X nhậngiátrị 14
Chƣơng II: Cơ sở toán học x với điều kiện Y nhận giá trị y. Các biến X và Y đƣợc gọilà độc lập nếu p(x, y) = p(x)p(y) với mọi giá trị có thể có của X vàY. Định lý Bayes: Nếu p(y) ≠ 0 thì ta có: p()(/) x p y x p(/) x y py() Hệ quả: X, Y là biến độc lập khi và chỉ khi p(x/y) = p(x) với mọi x, y. [5] Ở đây, ta giả thiết rằng một khoá cụ thể chỉ đƣợc dùng cho một bản mã. Ký hiệu xác suất tiên nghiệm để bản rõ xuất hiện làp (x). Cũng giả thiết rằng khoá K đƣợc chọn theo một phân bố xác suất nào đó (thông thƣờng khoá K đƣợc chọn ngẫu nhiên nêncác khoá sẽ đồng khả năng). Ký hiệu xác suất khoá Kđƣợc chọn làk p (K). Giả thiết rằng khoá K và bản rõ x là các biến độc lập. Hai phân bố xác suấttrênP và K sẽ tạo ra một phân bố xác suất trên C . Ký hiệu C(K) là tập các bản mã có thể nếu K là khoá. C (K) = { eK(x): x P } Khi đó với mỗi y C, ta có: pC ( y )  pK ( K ). p p ( d K ( y )) K,() y C K Và xác suất có điều kiện pC(y/x) là xác suất để y là bản mã với điều kiện bản rõlàx đƣợc tính theo công thức sau: pC (y / x)  pK (K) K,x dK ( y) Bây giờ ta có thể tính xác suất có điều kiện pP(x/y) là xác suất để x là bản rõ khi bản mã là y theo định lý Bayes: pPK()() x p K pP ()(/) x pC y x K,() x dK y pP (/) x y pCKPK( y ) p ( K ) p ( d ( y )) K,() y C K Lúc này, ta có thể định nghĩa khái niệm về độ mật hoàn thiện. Nói một cách không hình thức, độ mật hoàn thiện nghĩa là đối phƣơng với bản mã trong taycũng không thể thu nhận đƣợc thông tin gì về bản rõ. Tuy nhiên ta sẽ nêu định nghĩa chính xác về độ mật hoàn thiện nhƣ sau: Định nghĩa: Một hệ mật hoàn thiện nếu pP(x/y) = pP(x) với mọi x P và mọi y C. Tức là xác suất hậu nghiệm để thu được bản rõ là x với điều kiện đã thu được bản mã là y đồng nhất với xác suất tiên nghiệm để bản rõ là x. [5] 15
Chƣơng II: Cơ sở toán học Hay nói cách khác, độ mật hoàn thiện cũng tƣơng đƣơng vớipC(y/x)= pC(y)). Định lý Shannon: Giả sử (P, C, K, E, D) là một hệ mật, khi đó hệ mật đạt được độ mật hoàn thiện khi và chỉ khi |K| ≥ |C|. Trong trường hợp |K| = |C| = |P|, hệ mật đạt độ mật hoàn thiện khi và chỉ khi mỗi khoá K được dùng với xác suất bằng nhau, bằng 1/|K| và với mỗi x P, mỗi y C có một khoá K duy nhất sao cho eK(x) = y. [5] Nhƣ vậy ta thấy để đạt độ hoàn thiện đòi hỏi khoá phải rất dài, do vậy rất khókhăn trong việc chuyển giao khoá giữa hai bên truyền tin. Vì vậy trong thực tế, chúng ta không thể có an toàn không điều kiện mà chúng ta chỉ cần an toàn thực tế, tức là phụ thuộc vào thông tin và thời gian cần bảo mật bằng cách sử dụng các hệ mật khác nhau với độbảo mật khác nhau. 3.3. Hệ mật tích Một ý tƣởng khác đƣợc Shannon đƣa ra là ý tƣởng tạo ra các hệ mật mới dựa trên các hệ mật cũ bằng cách tạo tích của chúng. Đây là một ý tƣởng quan trọng trongviệc thiết kế các hệ mật hiện đại ngày nay. Để đơn giản, ở đây chúng ta chỉ xét các hệ mật trong đó C = P, các hệ mật loại này gọi là tự đồng cấu. Giảsử S1 = (P, C, K1, E1, D1) và S2 = (P, C, K2, E2, D2) là các hệ mật tự đồng cấu có cùng không gian bản rõ và bản mã. Khi đó hệ mật tích đƣợcđịnh nghĩa là hệ mật S = (P, C, K1 K2 ,E ,D). Khoá của hệ mật tích K = (K1, K2) trong đóK1 K1, K2 K2. Các hàm mã hoá và giải mã đƣợc xác định nhƣsau: e (x) e (e (x)) (K1 ,K2 ) K2 K1 d (x) d (e (x)) (K1 ,K2 ) K1 K2 Nếu chúng ta lấy tích của S với chính nó, ta có hệ mật (S×S) (ký hiệu S2). Nếulấy tích n lần thì kết quả là Sn. Ta gọi Sn là một hệ mật lặp. Nếu S2 = S thì ta gọi hệmậtlà luỹ đẳng. Nếu S là luỹ đẳng thì không nên lấy tích lặp vì độ bảo mật không tăng lênmà không gian khoá lại lớn hơn. Đƣơng nhiên nếu S không luỹ đẳng thì ta có thể lặplại S nhiều lần để tăng độ bảo mật. Ở đây nảy sinh một vấn đề là làm thếnàođể có một hệ mật không luỹ đẳng? Ta biết rằng nếu S1 và S2 là luỹ đẳng và giao hoán thì S1×S2 cũng luỹ đẳng, đơn giản vì: (S1×S2)×(S1×S2) = S1×(S2×S1)×S2 = S1×(S1×S2)×S2 = (S1×S1)×(S2×S2) = (S1×S2) Vậy nếu muốn (S1×S2) không luỹ đẳng thì cần phải có S1 và S2 không giao hoán. Điều này có thể dễ dàng thực hiện bằng cách lấy tích của một hệ mật theo kiểu thaythế và một hệ mật theo kiểu hoán vị. Đây là kỹ thuật đƣợc dùng để thiếtkếcác hệ mã hiện đại nhƣ mã DES. 16
Chƣơng II: Cơ sở toán học 3. Lý thuyết toán học 3.1. Modulo số hoc̣ Về cơ bả n a  b(mod n) nế u a = b+kn trong đó k là môṭ số nguyên . Nế u a và b dƣơng và a nhỏ hơn n, chúng ta có thể gọi a là phầ n dƣ củ a b khi chia cho n. Nói chung a và b đều là phầ n dƣ khi chia cho n . Ngƣờ i ta cò n gọ b là thăṇ g dƣ củ a a theo modulo n, và a là đồng dƣ của b theo modulo n. Modulo số hoc̣ cũng giố ng nhƣ số hoc̣ bình thƣờ ng , bao gồ m cá c phé p giao hoá n , kế t hợp và phân phố i. Măṭ khá c giả m mỗi giá tri ̣trung gian trong suố t quá trình tính toá n. (a+b) mod n = ((a mod n) + (b mod n)) mod n (a- b) mod n = ((a mod n) - (b mod n)) mod n (a b) mod n = ((a mod n) (b mod n)) mod n (a (b + c)) mod n = (((a b) mod n) + ((a c) mod n)) mod n Các phép tính trong các hệ mã mâṭ hầ u hế t đề u thƣ̣c hiêṇ đố i vớ i môṭ modulo N nà o đó . 3.2. Số nguyên tố Số nguyên tố là môṭ số lớ n hơn 1, nhƣng chi ̉ chia hế t cho 1 và chính nó , ngoài ra không cò n số nào nó có thể chia hết nữa . Số 2 là một số nguyên tố đầ u tiên và là số nguyên tố chẵn duy nhấ t . Do vâỵ 7, 17, 53, 73, 2521, 2365347734339 cũng là số nguyên tố . Số lƣợng số nguyên tố là vô tâṇ . Hê ̣ mâṭ mã thƣờ ng sƣ̉ duṇ g số nguyên tố lớ n cỡ 512 bits và thâṃ chí lớ n hơn nhƣ vâỵ . 3.3. Ƣớc số chung lớn nhất Hai số a và n đƣợc goị là hai số nguyên tố cùng nhau nếu chúng không có thừa số chung nà o khá c 1, hay nó i môṭ cá ch khá c, nế u ƣớ c số chung lớ n nhấ t củ a a và n là bằ ng 1. Chúng ta có thể viết nhƣ sau : GCD(a,n)=1, (GCD-Greatest Common Divisor) Số 15 và 28 là hai số nguyên tố cù ng nhau, nhƣng 15 và 27 thì không phải là hai số nguyên tố cùng nhau do có ƣớ c số chung là 1 và 3, dễ dà ng thấ y 13 và 500 cũng là một căp̣ số nguyên tố cùng nhau. Môṭ số nguyên tố sẽ là nguyên tố cù ng nhau vớ i tấ t cả cá c số nguyên khá c trƣ̀ cá c bôị số củ a nó . Môṭ cá ch dễ nhấ t để tính toá n ra ƣớ c số chung lớ n nhấ t củ a hai số là nhờ và o thuâṭ toán Euclid. Knuth mô tả thuâṭ toá n và môṭ và i mô hình củ a thuâṭ toá n đã đƣợc sƣ̉ a đổ i. Dƣớ i đây là đoaṇ mã nguồ n trong ngôn ngƣ̃ C: /* Thuâṭ toá n tìm ƣớ c số chung lớ n nhấ t củ a x và y, giả sử x,y>0 */ int gcd(int x, int y) { int g; if(x<0) 17
Chƣơng II: Cơ sở toán học x=-x; if(y 0){ g=x; x=y%x; y=g; } return g; } 3.4. Vành ZN (vành đồng dƣ module N) Tâp̣ cá c số nguyên ZN = {0, 1, , N-1} trong đó N là môṭ số tƣ̣ n hiên dƣơng vớ i hai phé p toá n côṇ g (+) và nhân (.) đƣợc điṇ h nghiã nhƣ sau taọ thà nh môṭ vành đồng dƣ modulo N (hay cò n goị là tâp̣ thăṇ g dƣ đầ y đủ theo modulo N): Phép cộng:  a, b ZN: a+b = (a+b) mod N. Phép nhân:  a, b ZN: a . b = (a * b) mod N. Theo tính chấ t củ a modulo số hoc̣ chú ng ta dễ dà ng nhâṇ thấ y Z N là một vành giao hoán và kết hợp. Hầ u hế t cá c tính toá n trong cá c hê ̣ mã mâṭ đề u đƣợc thƣ̣c hiêṇ trên môṭ vành ZN nào đó. Trên và nh ZN số 0 là phần tử trung hòa vì a + 0 = 0 + a = a,  a ZN, số 1 đƣợc goị là phần tử đơn vị vì a . 1 = 1 . a = a  a ZN. 3.5. Phầ n tƣ̉ nghic̣ h đả o Trên trƣờ ng số thƣ̣c R , số nghic̣ h đả o củ a 5 là 1/5, bở i vì 5 1/5=1. Còn trên một vành số nguyên ZN ngƣờ i ta đƣa ra khá i niêṃ về số nghic̣ h đả o củ a môṭ số nhƣ sau: Giả sử a ZN và tồn tại b ZN sao cho a.b = (a*b) mod N = 1. Khi đó b đƣợc goị là -1 phầ n tƣ̉ nghic̣ h đả o củ a a trên ZN và ký hiệu là a = b. Viêc̣ tìm phần tử nghịch đảo của một số a ZN cho trƣớ c thƣ̣c chấ t tƣơng đƣơng vớ i viêc̣ tìm hai số b và k sao cho: a.b = k.N + 1 trong đó b, k ZN. Hay viế t goṇ laị là : a-1  b (mod N ) Điṇ h lý về sƣ̣ tồ n taị củ a phầ n tƣ̉ nghic̣ h đả o : Nế u GCD(a, N) = 1 thì tồn tại duy nhấ t 1 số b ZN là phần tử nghịch đảo của a, nghĩa là thỏa mãn a.b = (a*b) mod N = 1. 18
Chƣơng II: Cơ sở toán học 3.6. Hàm phi Ơle Vớ i mỗi số nguyên N , giá trị của hàm phi Ơle của N là tổng số tất cả các số nguyên ZN và nguyên tố cùng nhau với N . Chẳ ng haṇ nế u P là môṭ số nguyên thì giá tri ̣ hàm phi Ơle của P: (P) = P – 1 hoăc̣ nế u N = p*q trong đó p và q là hai số nguyên tố thì (N) = (p-1)*(q-1). Trong trƣờ ng hợp tổ ng quá t nế u daṇ g phân tích ra thừa số nguyên tố của N là: 12 k N p12 p pk trong đó p i là các số nguyên tố còn i là các số nguyên dƣơng thì giá trị của hàm phi Ơle đƣợc tính nhƣ sau: 12 11 k 1 (N ) ( p1 1) p 1 ( p 2 1) p 2 ( pkk 1) p Liên quan tớ i khá i niêṃ về hà m phi Ơle chú ng ta có điṇ h lý Ơle phá t biể u nhƣ sau: *  ()N  a Z N = ZN – {0} và GCD(a, N) = 1 ta có aN1(mod ) . Có nghĩa là ()N a chính là giá trị nghịch đảo của a trên ZN. Môṭ trƣờ ng hợp riêng củ a điṇ h lý Ơle chính là điṇ h lý Fermat nhỏ : Nế u P là môṭ số * P 1 nguyên tố thì  a Z P ta có aP1(mod ) . Đây là môṭ trong nhƣ̃ ng điṇ h lý đep̣ nhấ t của số học. * Vớ i mỗi số nguyên N và nh Z N gồ m cá c phầ n tƣ̉ thuôc̣ Z N và nguyên tố cù ng nhau * ()N vớ i N, hay nó i cá ch khá c: Z N = {x: x ZN, (x, N) = 1} = {x: x ZN, x 1}. t Vớ i mỗi phầ n tƣ̉ a ZN, bâc̣ t củ a a (ký hiệu là ord (a)) là số nhỏ nhất sao cho : a = 1. Theo điṇ h lý Ơle ta suy ra (N) chia hế t cho t. Cụ thể với N = 21 ta có bả ng sau: * a Z 21 1 2 4 5 8 10 11 13 16 17 19 20 Ord(a) 1 6 3 6 2 6 6 2 3 6 6 2 * Bảng 2.1: Bảng bậc của các phần tử trên Z 21 * Nế u bâc̣ củ a a Z N bằ ng (N) thì a đƣợc g ọi là phần tử sinh hay phần tử nguyên thủy * * của tập Z N. Và nếu tập Z N chỉ có một phần tử sinh thì nó đƣợc gọi là một cyclic. 3.7. Thăṇ g dƣ bâc̣ hai Giả sử a Z*N, khi đó a đƣợc goị là thăṇ g dƣ bâc̣ 2 theo modulo N nế u tồ n taị x 2 Z*N sao cho x = a (mod N). Tâp̣ cá c phầ n tƣ̉ thăṇ g dƣ theo modulo N đƣợc ký hiêụ là QN, tâp̣ cá c phầ n tƣ̉ không thăṇ g dƣ theo modulo N đƣợc gọi là bất thặng dƣ theo modulo N và ký hiệu là QN . 19
Chƣơng II: Cơ sở toán học Điṇ h lý : nế u p là môṭ số nguyên tố lẻ và là một phần tử sinh của Z *N, khi đó a là i môṭ thăṇ g dƣ bâc̣ 2 theo modulo N khi và chi ̉ khi a = mod p, trong đó i là số nguyên lẻ . Tƣ̀ điṇ h lý nà y suy ra QN ( p 1)/ 2 QN . Ví dụ với p = 13, = 6 Z13 ta có bả ng sau: i 0 1 2 3 4 5 6 7 8 9 10 11 i mod 13 1 6 10 8 9 2 12 7 3 5 4 11 Bảng 2.2: Bảng lũy thừa trên Z13 Do đó Q13 = {1, 3, 4, 9, 10, 12} và Q13 = {2, 5, 6, 7, 8, 11}. 2 Vớ i a QN. Nế u x Z*N thỏa mãn x = a (mod N) thì a đƣợc gọi là căn bậc hai của x theo modulo N. 3.8. Thuâṭ toá n lũy thƣ̀ a nhanh Để có thể tìm phầ n tƣ̉ nghic̣ h đả o củ a môṭ số nguyên a trên môṭ và nh Z N cho trƣớ c chúng ta có thể sƣ̉ duṇ g điṇ h lý Ơle để tính giá tri ̣lũy thƣ̀ a củ a a vớ i số mũ là giá tri ̣hà m phi Ơle củ a N . Tuy nhiên để có thể nhanh chó ng tính đƣợc giá tri ̣lũy thƣ̀ a nà y chú ng ta cầ n có môṭ thuâṭ toá n hiêụ quả và môṭ trong cá c thuâṭ toá n đó (còn nhiều thuật toán khác phƣ́ c tap̣ hơn ) là thuật toán lũy thừa nhanh . Thuâṭ toá n nà y do Chivers đƣa ra và o năm 1984. Các bƣớc của thuật toán nhƣ sau: Input: a, m, N. Output: am mod N. Begin Phân tích m thà nh daṇ g nhị phân m = bkbk-1 b0. j = 0, kq = a; while (k>=j) { if (bj==1) kq = (kq * a) mod N; a = (a * a) mod N; j = j + 1; } return kq; end Môṭ cà i đăṭ khá c bằ ng ngôn ngƣ̃ C nhƣ sau: long modexp(long a, long x, long n) { 20
Chƣơng II: Cơ sở toán học long r = 1; while (x > 0){ if (x % 2 == 1) /* is x odd? */ r = (r * a) % n; a = (a*a) % n; x /= 2; } return r; } Thuâṭ toá n nà y chaỵ không quá log2(m+1) bƣớ c. 3.9. Thuâṭ toá n Ơclit mở rôṇ g Trong phầ n 3.3 chúng ta đã biết thuật toán Ơclit đƣợc d ùng để tìm ƣớc số chung lớ n nhấ t củ a ha i số nguyên và trong phầ n 3.7 chúng ta đã biết cách tìm một phần tử nghịch đảo của một số bằ ng cá ch sƣ̉ duṇ g thuâṭ toá n lũy thƣ̀ a nhanh tuy nhiên vẫn có môṭ thuâṭ toá n hiêụ qu ả khác để tìm phầ n tƣ̉ nghịch đảo gọi là thuật tóan Ơclit mở rộng (do dƣ̣a trên thuâṭ toá n Ơclit). Các bƣớc của thuật toán nhƣ sau: input: a, N vớ i GCD(a, N) = 1 output: a-1 begin g0=n, g1 = a, u0 = 1, u1 = 0, v0 = 0, v1 = 1, i = 1; while (gi 0) then return x; else return (N+x); end; 21
Chƣơng II: Cơ sở toán học 3.10. Phƣơng trình đồ ng dƣ bâc̣ nhấ t 1 ẩn Phƣơng trình đồ ng dƣ bâc̣ nhấ t 1 ẩn là phƣơng trình có dạng: ax  b (mod N) trong đó a, b ZN là các hệ số còn x là ẩn số. -1 Nế u nhƣ GCD(a, N) = 1 chúng ta có thể tìm a sau đó nhân và o 2 vế củ a phƣơng trình và tìm ra nghiệm một cách dễ dàng tuy nhiên nếu g = GCD(a, N) là một giá trị khác 1 thì sao ? Khi đó bà i toá n có thể vô nghiêṃ hoăc̣ có nhiề u nghiêṃ . Chúng ta xét điṇ h lý sau: Giả sử g = GCD(a, N) và nếu b chia hết cho g thì phƣơng trình đồng dƣ bậc nhất 1 ẩn: ax  b (mod N) sẽ có g nghiêṃ có daṇ g x  ((b/g)x0 + t(n/g)) (mod N) trong đó t = 0, , g-1, và x0 là nghiệm của phƣơng trình (a/g)x  1 (mod N/g). 3.11. Điṇ h lý phầ n dƣ Trung Hoa. Điṇ h lý phầ n dƣ Trung Hoa là m ột định lý quan trọng của số học đƣợc c ác nhà toán học Trung Quốc khám phá ra vào thế kỷ thứ nhất. Điṇ h lý phá t biể u nhƣ sau: Nế u d1, d2, , dk là các số nguyên đôi một nguyên tố cùng nhau và N = d1d2 dk thì hệ phƣơng trình đồng dƣ: x  xi (mod di), i=1, 2, , k sẽ có một nghiệm thuộc vào ZN. Nghiêṃ củ a hê ̣ có tính theo công thƣ́ c sau: k x ( N / di ) y i x i (mod N ) i 1 trong đó yi là các nghiệm của các phƣơng trình đồng dƣ (N/di) yi  1(mod di). Dƣớ i đây là đoaṇ mã điṇ h lý phầ n dƣ trung hoa trong ngôn ngƣ̃ C : int chinese_remainder(int r, int *m, int *u) { int i; int modulus; int n; modulus = 1; for ( i=0; i<r:++i ) modulus *=m[i]; n=0; for ( i=0; i<r:++i ) 22
Chƣơng II: Cơ sở toán học { n+=u[i]*modexp(modulus/m[i],totient(m[i]),m[i]); n%=modulus; } return n; } 4. Các thuâṭ toá n kiể m tra số nguyên tố . Hàm môṭ phía (one-way functions) là một khái niệm cơ bản của mã hoá công khai. Viêc̣ nhân hai số nguyên tố là môṭ ví du ̣ về hàm một phía , nhân cá c số nguyên tố lớ n để taọ thà nh môṭ hợp số là dễ , nhƣng công viêc̣ ngƣợc laị phân tích môṭ số nguyên lớ n thà nh daṇ g thƣ̀ a số nguyên tố laị là môṭ bà i toá n khó (chƣa có môṭ thuâṭ toá n tố t). Các thuâṭ toá n mã hoá khóa công khai đều cầ n phải sử dụng các số nguyên tố . Có môṭ số phƣơng phá p để sinh ra số nguyên tố và hầu hết chúng đều dựa trên các thuật toán kiểm tra tính nguyên tố của một số nguyên . Tuy nhiên có môṭ số vấ n đề đƣợc đăṭ ra đố i vớ i số nguyên tố nhƣ sau Trong môṭ hê ̣ thố ng có thể đả m bả o hai ngƣờ i dù ng sẽ đƣợc sƣ̉ duṇ g hai số 150 nguyên tố khá c nhau hay không ? Câu trả lờ i là có thể vì có tớ i 10 số nguyên tố có đô ̣ dài 512 bits hoăc̣ nhỏ hơn. Khả năng hai ngƣời dùng sẽ lựa chọn cù ng môṭ số nguyên tố là bao nhiêu. Vớ i sƣ̣ 150 lƣ̣a choṇ tƣ̀ 10 số nguyên tố , điề u kỳ xảy ra với xác xuất nhỏ hơn so với sự tự bốc cháy của máy tính. Các loại thuật toán kiểm tra số nguyên tố đƣợc chia làm hai loại : thuâṭ toá n tấ t điṇ h và thuật toán xác suất. Các thuật toán tất định cho chúng ta biết chính xác câu trả lời một số nguyên có phả i là môṭ số nguyên tố hay không cò n môṭ thuâṭ toá n xác suất cho biế t xác suất của một số ngu yên là môṭ số nguyên tố là bao nhiêu . Trong phầ n nà y sẽ trình bày một số thuật toán kiểm tra số nguyên tố phổ biến. 4.1. Môṭ số ký hiêụ toá n hoc̣ 4.1.1. Ký hiệu Lagrăng (Legendre Symbol) Ký hiệu L(a,p) đƣợc điṇ h nghiã vớ i a là một số nguyên và p là một số nguyên tố lớn hơn 2. Nó nhận ba giá trị 0, 1, -1 : L(a,p) = 0 nế u a chia hế t cho p. L(a,p) = 1 nế u a QN (a là thăṇ g dƣ bâc̣ 2 modulo p). L(a,p) = -1 nế u a QN (a không là thăṇ g dƣ bâc̣ 2 modulo p). Môṭ phƣơng phá p dễ dà ng để tính toá n ra L(a,p) là : L(a,p) = a (p-1)/2 mod p 23
Chƣơng II: Cơ sở toán học 4.1.2. Ký hiệu Jacobi (Jacobi Symbol) Ký hiệu Jacobi đƣợc viết là J (a,n), nó là sự khái quát hoá của ký hiệu Lagrăng , nó điṇ h nghiã cho bấ t kỳ căp̣ số nguyên a và n nào. Ký hiệu Jacobi là một chức năng trên tâp̣ hợp số thăṇ g dƣ thấ p củ a ƣớ c số n và có thể tính toá n theo công thƣ́ c sau: Nế u n là số nguyên tố , thì J(a,n) = 1 nế u a là thăṇ g dƣ bâc̣ hai modulo n . Nế u n là số nguyên tố , thì J(a,n) = -1 nế u a không là thăṇ g dƣ bâc̣ hai modulo n . Nế u n không phả i là số nguyên tố thì Jacobi (a,n) sẽ đƣợc tính theo công thức sau: J(a,n)=J(h,p1) J(h,p2) . . . J(h,pm) vớ i p1,p2. . .,pm là các thừa số lớn nhất của n. Thuâṭ toá n nà y tính ra số Jacobi tuầ n hoà n theo công thƣ́ c sau : 1. J(1,k) = 1 2. J(a b,k) = J(a,k) J(b,k) 2 3. J(2,k) =1 Nế u (k -1)/8 là chia hết và J(2,k) = -1 trong cá c trƣờ ng hợp khá c. 4. J(b,a) = J((b mod a),a) 5. Nế u GCD(a,b)=1 : a. J(a,b) J(b,a) = 1 nế u (a-1)(b-1)/4 là chia hết. b. J(a,b) J(b,a) = -1 nế u (a-1)(b-1)/4 là còn dƣ. Sau đây là thuâṭ toá n trong ngôn ngƣ̃ C : int jacobi(int a,int b) { int a1,a2; if(a>=b) a%=b; if(a==0) return 0; if(a==1) return 1; if(a==2) if(((b*b-1)/8)%2==0) return 1; else return -1; 24
Chƣơng II: Cơ sở toán học if(a&b&1) (cả a và b đều là số dƣ) if(((a-1)*(b-1)/4)%2==0) return +jacobi(b,a); else return -jacobi(b,a); if(gcd(a,b)==1) if(((a-1)*(b-1)/4)%2==0) return +jacobi(b,a); else return -jacobi(b,a); return jacobi(a1,b) * jacobi(a2,b); } Trên thƣ̣c tế có thể tính đƣợc ký hiêụ Jacobi môṭ cá ch thuâṇ lợi hơn nế u dƣ̣a và o 1 trong cá c tính chấ t sau, giả sử m, n là cá c số nguyên lẻ, a, b Z: 2 (i) J(a*b, n) = J(a, n) * J(b, n) do đó J(a , n) = 1. (ii) J(a, m*n) = J(a, m) * J(a, n). (iii) nế u a  b (mod n) thì J(a, n) = J(b, n). (iv) J(1, n) = 1. (v) J(-1, n) = (-1)(n-1)/2 (vi) J(m, n) = J(n, m) * (-1)(m-1)*(n-1)/4 4.2. Thuâṭ toá n Soloway-Strassen Soloway và Strassen đã phá t triể n thuâṭ toá n có thể kiể m tra số nguyên tố . Thuâṭ toán này sử dụng hàm Jacobi. Thuâṭ toá n kiểm tra số p là số nguyên tố : 1. Chọn ngẫu nhiên một số a nhỏ hơn p. 2. Nế u ƣớ c số chung lớ n nhấ t gcd(a,p) 1 thì p là hợp số. 3. Tính j = a(p-1)/2 mod p. 4. Tính số Jacobi J(a,p). 5. Nế u j J(a,p), thì p không phải là số nguyên tố. 6. Nế u j = J(a,p) thì nói p có thể là số nguyên tố với chắc chắn 50%. Lăp̣ laị cá c bƣớ c nà y n lầ n, mỗi lầ n vớ i môṭ giá trị ngẫu nhiên khác nhau của a . n Phầ n dƣ củ a hợp số vớ i n phé p thƣ̉ là không quá 2 . Thƣ̣c tế khi thƣ̣c hiêṇ chƣơng trình, thuâṭ toá n chaỵ vớ i tố c đô ̣ khá nhanh. 25
Chƣơng II: Cơ sở toán học 4.3. Thuâṭ toá n Rabin-Miller Thuâṭ toá n này đƣợc phát triển bởi Rabin , dƣ̣a trên môṭ phầ n ý tƣở ng củ a Miller . Thƣ̣c tế nhƣ̃ ng phiên bả n củ a thuâṭ toá n đã đƣợc giớ i thiêụ taị NIST . (National Institute of Standards and Technology). b Đầu tiên là chọn ngẫu nhiên một số p để kiể m tra. Viế t p dƣớ i daṇ g p = 1+2 m trong đó m là môṭ số lẻ. Sau đây là thuâṭ toá n : 1. Chọn một số ngẫu nhiên a, và giả sử a nhỏ hơn p. 2. Đặt j=0 và z=am mod p. 3. Nế u z=1, hoăc̣ z=p-1 thì p đã qua bƣớc kiểm tra và có thể là số nguyên tố . 4. Nế u j > 0 và z=1 thì p không phải là số nguyên tố. 2 5. Đặt j = j+1. Nế u j < b và z p-1 thì đặt z=z mod p và trở laị bƣớ c 4. 6. Nế u j = b và z p-1, thì p không phải là số nguyên tố. 4.4. Thuâṭ toá n Lehmann. Môṭ phƣơng pháp đơn giản hơn kiểm tra số nguyên tố đƣợc phát triển độc lập bởi Lehmann. Sau đây là thuâṭ toá n vớ i số bƣớ c lăp̣ là 100. 1. Chọn ngẫu nhiên một số n để kiểm tra. 2. Chắ c chắ n rằ ng n không chia hế t cho cá c số nguyên tố nhỏ nhƣ 2,3,5,7 và 11. 3. Chọn ngẫu nhiên 100 số a1, a2, . . . , a100 giƣ̃ a 1 và n-1. (n-1)/2 4. Tính ai (mod n) cho tấ t cả ai = a1. . . a100 . Dƣ̀ ng laị nế u baṇ tìm thấ y ai sao cho phé p kiể m tra là sai. (n-1)/2 5. Nế u ai = 1 (mod n) vớ i moị i, thì n có thể là hợp số . (n-1)/2 Nế u ai 1 hoăc̣ -1 (mod n) vớ i i bấ t kỳ, thì n là hợp số. (n-1)/2 Nế u ai = 1 hoăc̣ -1 (mod n) vớ i moị i 1, thì n là số nguyên tố. 5. Bài tập Bài tập 2.1: hãy tính 1753 mod 29, hỏi cần dùng ít nhất là bao nhiêu phép nhân để tìm ra kết quả. Bài tập 2.2: Tính 876611 mod 899. Sƣ̉ duṇ g môṭ trong cá c ngôn ngƣ̃ lâp̣ trình C, C++, Java hoăc̣ C# để làm các bài tập sau: Bài tập 2.3: Viế t chƣơng trình cà i đăṭ thuâṭ toá n tìm phầ n tƣ̉ nghịch đảo. Bài tập 2.4: Viế t chƣơng trình cà i đăṭ thuâṭ toá n lũy thƣ̀ a nhanh. Bài tập 2.5: Viế t chƣơng trình giả i hê ̣ phƣơng trình đồ ng dƣ bâc̣ nhấ t hai ẩ n. Bài tập 2.6: Viế t chƣơng trình cà i đăṭ thuâṭ toá n kiể m tra số nguyên tố vớ i input là môṭ số nguyên nhỏ hơn 2000000000. 26
Chƣơng II: Cơ sở toán học Bài tập 2.7: Viế t chƣơng trình cà i đăṭ thƣ viêṇ số nguyên lớ n vớ i cá c thao tá c tính toán cơ bản: nhân, chia, côṇ g trƣ̀ , lấ y modulo. Bài tập 2.8: Sƣ̉ duṇ g thƣ viêṇ số lớ n (ở bài tâp̣ 2.5 hoăc̣ môṭ thƣ viêṇ mã nguồ n mở ) cài đặt các thuật toán kiểm tra số nguyên tố đƣợc trình bày trong phần 4 của chƣơng 2. 27
Chƣơng III: Các hệ mã khóa bí mật CHƢƠNG III: CÁC HỆ MÃ KHÓA BÍ MẬT 1. Các hệ mã cổ điển 1.1. Hê ̣ mã hoá thay thế (substitution cipher) Hê ̣ mã hoá thay thế là hê ̣ mã hoá trong đó mỗi ký tƣ̣ củ a bả n rõ đƣợc thay thế bằ ng ký tự khác trong bản mã (có thể là một chữ cái, môṭ số hoăc̣ môṭ ký hiêụ ). Có 4 kỹ thuật thay thế sau đây: 1. Thay thế đơn (A simple substitution cipher): là hệ trong đó một ký tự của bản rõ đƣợc thay bằ ng môṭ ký tƣ̣ tƣơng ƣ́ ng trong bả n ma.̃ Môṭ á nh xa ̣ 1-1 tƣ̀ bả n rõ tớ i bản mã đƣợc sử dụng để mã hoá toàn bộ thông điệp. 2. Thay thế đồ ng âm (A homophonic substitution cipher ): giố ng nhƣ hê ̣ thố ng mã hoá thay thế đơn , ngoại trừ một ký tự của bản rõ có thể đƣợc ánh xạ tới một trong số môṭ và i ký tƣ̣ củ a bả n mã : sơ đồ á nh xa ̣ 1-n (one-to-many). Ví dụ, “A” có thể tƣơng ứng vớ i 5, 13, 25, hoăc̣ 56, “B” có thể tƣơng ƣ́ ng vớ i 7, 19, 31, hoăc̣ 42, v.v. 3. Thay thế đa mẫu tƣ̣ (A polyalphbetic substitution cipher): đƣợc taọ nên tƣ̀ nhiề u thuâṭ toá n mã hoá thay thế đơn. Ánh xạ 1-1 nhƣ trong trƣờ ng hợp thay thế đơn, nhƣng có thể thay đổ i trong phaṃ vi môṭ thông điêp̣ . Ví dụ, có thể có năm thuật toán mã hoá đơn khác nhau đƣợc sử dụng ; đăc̣ biêṭ thuâṭ toá n mã hoá đơn đƣợc sƣ̉ duṇ g thay đổ i theo vi ̣trí củ a mỗi ký tƣ̣ trong bả n ro.̃ 4. Thay thế đa sơ đồ (A polygram substitution cipher ): là thuật toán trong đó các khố i ký tƣ̣ đƣợc mã hoá theo nhó m . Đây là thuâṭ toá n tổ ng quá t nhấ t , cho phé p thay thế cá c nhó m ký tƣ̣ củ a văn bả n gố c . Ví dụ, “ABA” có thể tƣơng ƣ́ ng vớ i “RTQ”, “ABB” có thể tƣơng ƣ́ ng vớ i “SLL”, v.v. 1.2. Hê ̣ mã Caesar Hê ̣ mã Caesar là một hệ mã hoá thay thế đơn âm làm việc trên bảng chữ cái tiếng Anh 26 ký tự (A, B, , Z). Đây là hê ̣ mã cổ điể n và đơn giả n nhấ t đã tƣ̀ ng đƣ ợc dùng trong thƣ̣c tế bở i hoà ng đế La mã Caesar nên đƣợc đăṭ theo tên củ a vi ̣hoà ng đế nà y. Không gian cá c bả n rõ P là các thông điệp đƣợc tạo từ bảng chữ cái A (để tiện trình bày chúng ta xem đây là một bảng chữ cái tổ ng quá t). Tƣơng tƣ̣ không gian cá c bả n mã C  P. Giả sử số phần tử của bảng chữ cái |A| = N. Để mã hó a ngƣờ i ta đá nh số cá c chƣ̃ cá i tƣ̀ 0 tớ i N-1. Không gian khó a K = ZN. Vớ i mỗi khó a K K hàm mã hóa và giải mã một ký tự có số thứ tự là i sẽ đƣợc thực hiện nhƣ sau: Mã hóa: EK(i) = (i + k) mod N. Giải mã: DK(i) = (i – k) mod N. Hê ̣ mã Caesar vớ i bả ng chƣ̃ cá i tiế ng Anh sẽ có N = 26 chƣ̃ cá i, bảng chữ cái đƣợc đá nh số nhƣ sau: 28
Chƣơng III: Các hệ mã khóa bí mật A B C D L M N W X Y Z 0 1 2 3 11 12 13 22 23 23 25 Bảng 3.1: Bảng đánh số các chữ cái tiếng Anh Các phép tính toán số học đƣợc thƣ̣c hiêṇ trên và nh Z 26, số khó a có thể sƣ̉ duṇ g là 26 nhƣng trên thƣ̣c tế chỉ có 25 khóa có ích. Ví dụ : vớ i k=3 (trƣờ ng hợp đã đƣợc hoà ng đế Caesar sƣ̉ duṇ g ), ký tự A đƣợc thay bằ ng D, B đƣợc thay bằ ng E , , W đƣợc thay bằ ng Z , , X đƣợc thay bằ ng A , Y đƣợc thay bằ ng B, và Z đƣợc thay bằng C. Bảng chữ cá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 Bảng chữ cái dùng để mã hoá: 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 Do đó chẳ ng haṇ xâu “ANGLES” sẽ đƣợc mã hó a thà nh “DQJOHV”. Hê ̣ mã Caesar sƣ̉ dụ ng phƣơng phá p thay thế đơn âm nên có hiêṇ tƣợng goị là phụ thuộc tần suất xuất hiện của ngôn ngữ tự nhiên. Trong ngôn ngƣ̃ tƣ̣ nhiên môṭ số chƣ̃ cái xuất hiện nhiều hơn so với các chữ cái khác (chẳ ng haṇ trong tiế ng Anh cá c chƣ̃ cá i xuấ t hiêṇ nhiề u là e, t, i, h ) nên cá c chƣ̃ cá i dù ng để thay thế cho chú ng cũng xuấ t hiêṇ nhiề u. Điề u nà y có thể dẫn tớ i hê ̣ quả là ngƣờ i thá m mã có thể sƣ̉ duṇ g phƣơng phá p thƣ̉ thay thế cá c ký t ự xuấ t hiêṇ nhiề u trong bả n mã bằ ng cá c ký tƣ̣ xuấ t hiêṇ nhiề u trên cá c văn bả n thƣ̣c tế . Trên thƣ̣c tế hê ̣ mã Caesar có số khó a ít nên hoà n toà n có thể thá m mã bằ ng cách thử tất cả các khóa có thể (kiể u tấ n công Brute force). 1.3. Hê ̣ mã Affine Không gian cá c bả n rõ và bả n mã củ a hê ̣ mã là cá c xâu đƣợc hình thà nh tƣ̀ môṭ bảng chữ cái A, giả sử |A| = N. Khi đó không gian khó a củ a hê ̣ mã đƣợc xá c điṇ h nhƣ sau: K = { (a, b): a, b ZN, (a, N) = 1} Để mã hó a ngƣờ i ta đá nh số cá c chƣ̃ cá i củ a bả ng chƣ̃ cá i tƣ̀ 0 tớ i N – 1 và tiến hành mã hóa, giải mã từng ký tự (thay thế ) theo cá c công thƣ́ c sau: Mã hóa: EK(x) = (a*x + b) mod N. Ký tự bản rõ có số thứ tự là x sẽ đƣợc chuyển th ành ký tự có số thứ tự là (a*x+b) mod N trong bả ng chƣ̃ cá i. -1 Để giả i mã ta cầ n tìm a (do (a, N) = 1 nên luôn tìm đƣợc) và tiến hành công thức giải mã sau: 29
Chƣơng III: Các hệ mã khóa bí mật DK(y) = a*(y - b) mod N. Ký tự bản mã có số thứ tự là y sẽ đƣợc thay thế bằ ng ký tƣ̣ có số thứ tự là a*(y - b) mod N trong bả ng chƣ̃ cá i. Có thể thấy rằng đối với một hệ mã Affine thì số khóa có thể sử dụng sẽ là: |K| = (N) * N. Ví dụ với N = 26 tƣơng ƣ́ ng vớ i bả ng chƣ̃ cá i tiế ng Anh chúng ta sẽ có (26) * 26 = 12 * 26 = 312 khóa. Con số nà y là tƣơng đố i nhỏ . 1.4. Hê ̣ mã Vigenere Hê ̣ mã này đƣợc đặt theo tên của một nhà mật mã học ngƣờ i Phá p Blaise de Vigenère (1523-1596). Đối với hệ mã này không gian các bản mã và bản rõ cũng là các thông điệp đƣợc tạo thành từ một bảng chữ cái A nhƣ trong hê ̣ mã Caesar, các chữ cái đƣợc đanh số từ 0 tớ i N-1 trong đó N là số phầ n tƣ̉ củ a bả ng chƣ̃ cá i. Không gian khó a K đƣợc xá c điṇ h nhƣ sau: Vớ i mỗi số nguyên dƣơng M , khóa có độ dài M là một xâu ký tự có độ dài M , K = k1k2 kM. Để mã hó a môṭ bả n rõ P ngƣờ i ta chia P thà nh cá c đoaṇ đô ̣ dà i M và chuyển thành số thƣ́ tƣ̣ tƣơng ƣ́ ng củ a chú ng trong bả ng chƣ̃ c ái, chẳ ng haṇ X = x1x2 xM. Khi đó viêc̣ mã hóa và giải mã đƣợc thực hiện nhƣ sau: EK(X) = (x1 + k1, x2 + k2, , xM + kM) mod N DK(Y) = (y1 - k1, y2 - k2, , yM - kM) mod N vớ i N là số phầ n tƣ̉ củ a bả ng chƣ̃ cá i và Y = y1y2 yM là bản mã. Ví dụ: xét A là bảng chữ cái tiếng Anh , ta có N = 26 giả sử khóa có độ dài 6 và K = “CIPHER”, bản rõ P = “THIS CRYPTOSYSTEM IS NOT SECURE” . Ta có K = 2 8 15 7 4 17, P = 19 7 8 18 2 17 | 24 15 19 14 18 23 | 18 19 4 12 8 18 | 13 14 19 18 4 2 | 20 17 4. Quá trình mã hóa thực hiện nhƣ sau: P = 19 7 8 18 2 17 | 24 15 19 14 18 23 | 18 19 4 12 8 18 | 13 14 19 18 4 2 | 20 17 4 K = 2 8 15 7 4 17 | 2 8 15 7 4 17 | 2 8 15 7 4 17 | 2 8 15 7 4 17 | 2 8 15 C = 21 15 23 25 6 8 | 0 23 8 21 22 14 | 20 1 19 19 12 9 | 15 22 8 25 8 19 | 22 25 19 Vâỵ bả n mã là C = “VPXZGI AXIVWO UBTTMJ PWIZIT WZT”. Về thƣ̣c chấ t hê ̣ mã nà y là kế t hợp củ a nhiề u mã Caesar , trong hê ̣ mã Caesar chúng ta thay thế từng ký tự đơn l ẻ thì trong hệ mã Vigenere này thay thế từng bộ M ký M tƣ̣ liên tiế p. Vớ i mỗi M chú ng ta có số khó a có thể sƣ̉ duṇ g là N , cụ thể là với bảng chữ cái tiếng Anh sẽ có 26M khóa có thể sử dụng. 1.5. Hê ̣ mã Hill Hê ̣ mã hoá n ày dựa trên lý thuyết về đại số tuyến tính do Lester S .Hill đƣa ra năm 1929. Cả không gian bản rõ và bản mã đều là các xâu đƣợc thành lập từ một bảng chữ cái A nhƣ trong hê ̣ mã Vigenere. 30
Chƣơng III: Các hệ mã khóa bí mật Vớ i mỗi số nguyên M khó a củ a hê ̣ mã là một ma trận K vuông kích thƣớc MxM gồm các phần tử là c ác số nguyên thuộc Z N trong đó N là số phầ n tƣ̉ củ a bả ng chƣ̃ cá i . Điề u kiêṇ để ma trâṇ K có thể sƣ̉ duṇ g là m khó a củ a hê ̣ mã là K phả i là môṭ ma trâṇ không suy biế n trên ZN hay nó i cá ch khá c là tồ n taị ma trâṇ nghic̣ h đả o củ a ma trâṇ K trên ZN. Các ký tự của bảng chữ cái cũng đƣợc đánh số từ 0 tớ i N-1. Để mã hó a môṭ bả n rõ ngƣờ i ta cũng chia bả n rõ đó thà nh cá c xâu có đô ̣ dà i M, chuyể n cá c xâu nà y thà nh số thƣ́ tƣ̣ củ a cá c chƣ̃ cá i trong bả ng chƣ̃ cá i dƣớ i daṇ g môṭ vectơ hà ng M chiề u và tiế n hà nh mã hó a, giải mã theo công thức sau: Mã hóa: C = P * K. Giải mã: P = C * K-1. Ví dụ: cho hê ̣ mã Hill có M = 2 (khóa là các ma trận vuông cấp 2) và bảng chữ cái là bảng chữ cái tiếng Anh, tƣ́ c là N = 26. Cho khó a 3 3 K = 2 5 Hãy mã hóa xâu P = “HELP” và giả i mã ngƣợc laị bả n mã thu đƣợc. Để mã hó a chú ng ta chia xâu bả n rõ thà nh hai vecto hà ng 2 chiề u “HE” (7 4) và “LP” (11 15) và tiến hành mã hóa lần lƣợt. 3 3 Vớ i P1 = (7 4) ta có C1 = P1 * K = 7 4 = 3 15 = D P 2 5 Vớ i P2 = (11 15) ta có C2 = P2 * K = 11 15 = 11 4 = L E Vâỵ bả n mã thu đƣợc là C = “DPLE”. Để giả i mã ta tính khó a giả i mã là ma trâṇ ngh ịch đảo của ma trận khóa trên Z 26 theo công thƣ́ c sau: k11 k 12 Vớ i K = và det(K) = (k11*k22 – k21*k12) mod N là môṭ phầ n tƣ̉ có phầ n tƣ̉ k21 k 22 -1 nghịch đảo trên ZN (ký hiệu là det(K) ) thì khóa giải mã sẽ là k22 -k 12 K-1 = det(K)-1* -k21 k 11 Áp dụng vào trƣờng hợp trên ta có det(K) = (15 - 6) mod 26 = 9. GCD(9, 26) =1 nên áp dụng thuật toán Ơclit mở rộng tìm đƣợc det (K)-1 = 3. Vâỵ K -1 = 3 * 5 23 15 17 = . 24 3 20 9 31
Chƣơng III: Các hệ mã khóa bí mật Quá trình giải mã tiến hành giống nhƣ quá trình mã hóa với khóa mã hóa thay bằng khóa giải mã. -1 15 17 Giải mã C = “DP” = ( 3 15 ), P = C * K = (3 15) * = 3 15 = “HE”. 20 9 Tƣơng tự giải mã xâu C = “LE” kết quả sẽ đƣợc bản rõ P = “LP”. Chú ý là trong ví dụ trên chúng ta sử dụng khóa K có kích thƣớc nhỏ nên dễ dàng tìm đƣợc khóa để giải mã còn trong trƣờng hợp tổng quát điều này là không dễ dàng. 1.6. Hê ̣ mã đổ i chỗ (transposition cipher) Môṭ hê ̣ mã hoá đổ i chỗ là hê ̣ mã hoá trong đó cá c ký tƣ̣ củ a bả n rõ vẫn đƣợc giƣ̃ nguyên, nhƣng thƣ́ tƣ̣ củ a chú ng đƣợc đổ i chỗ cho nhau. Ví dụ một hệ mã hoá đổi chỗ cột đơn giản , bản rõ đƣợc viết theo hà ng ngang trên trang giấ y vớ i đô ̣ dà i cố điṇ h, và bản mã đƣợc đọc theo hàng dọc. Bản rõ: COMPUTER GRAPHICS MAY BE SLOW BUT AT LEAST IT‟S EXPENSIVE COMPUTERGR APHICSMAYB ESLOWBUTAT LEASTITSEX PENSIVE Bản mã: CAELPOPSEEMHLANPIOSSUCWTITSBIUEMUTERATSGYAERBTX Bảng 3.2: Mã hoá thay đổi vị trí cột Phƣơng phá p nà y có cá c ky ̃ thuâṭ sau: 1. Đả o ngƣợc toà n bô ̣ bả n rõ: nghĩa là bản rõ đƣợc viết theo thứ tự ngƣợc lại để tạo ra bản mã . Đây là phƣơng phá p mã hoá đơn giả n nhấ t vì vâỵ không đả m bảo an toàn. Ví dụ : bản rõ “TRANSPOSITION CIPHER” đƣợc mã hoá thành “REHPICNOITISOPSNART”. 2. Mã hoá theo mẫu hình học : bản rõ đƣợc sắp xếp lại theo một mẫu hình học nào đó, thƣờ ng là môṭ mả ng hoăc̣ môṭ ma trâṇ hai chiề u. Ví dụ : bản rõ “LIECHTENSTEINER” đƣợc viết thành ma trận 3 5 theo hà ng nhƣ sau: Côṭ 1 2 3 4 5 Bản rõ L I E C H T E N S T E I N E R Bảng 3.3: Mã hóa theo mẫu hình hoc̣ Nế u lấ y cá c ký tƣ̣ ra theo số thƣ́ tƣ̣ côṭ 2, 4, 1, 3, 5 thì sẽ có bản mã “IEICSELTEENNHTR”. 32
Chƣơng III: Các hệ mã khóa bí mật Đổi chỗ cột: Đầu tiên đổi chỗ các ký tự trong bản rõ thành dạng hình chữ nhật theo côṭ , sau đó cá c côṭ đƣợc sắ p xế p laị và cá c chƣ̃ cá i đƣợc lấ y ra theo hà ng ngang Ví dụ: bản rõ gốc là “NGAY MAI BAT DAU CHIEN DICH XYZ” đƣợc viết dƣới dạng ma trâṇ 5 5 theo côṭ nhƣ sau: Côṭ 1 2 3 4 5 Bản rõ N A D I C G I A E H A B U N X Y A C D Y M T H I Z Bảng 3.4: Ví dụ mã hóa theo mẫu hình học Vì có 5 côṭ nên chú ng có thể đƣợc sắ p laị theo 5!=120 cách khác nhau. Để tăng đô ̣ an toà n có thể choṇ môṭ trong cá c cá ch sắ p xế p laị đó . Nế u ta c huyể n vi ̣cá c côṭ theo thƣ́ tƣ̣ 3, 5, 2, 4, 1 rồ i lấ y cá c ký tƣ̣ ra theo hà ng ngang ta sẽ đƣợc bả n mã là “DCAINAHIEGUXBNACYADY HZTIM”. Lƣu ý rằ ng cá c ký tƣ̣ cách đƣợc bỏ đi. Hạn chế của phƣơng pháp này là toàn bộ các ma trận k ý tự phải đƣợc sinh để mã hoá và giải mã. 3. Hoán vị các ký tự của bản rõ theo chu kỳ cố định d : Nế u hà m f là môṭ hoá n vị của một khối gồm d ký tự thì khoá mã hoá đƣợc biểu diễn bởi K(d,f). Do vâỵ , bản rõ: M = m1m2 mdmd+1 m2d Vớ i mi là các ký tự , và bản rõ sẽ đƣợc mã hoá thà nh Ek(M) = mf(1)mf(2) mf(d)mf(d)+1 md+f(d) Trong đó mf(1)mf(2) mf(d) là một hoán vị của m1m2 md. Ví dụ: giả sử d=5 và f hoán vị dãy i=12345 thành f(i)=35142 Vị trí đầu Vị trí hoán vị Tƣ̀ Mã hoá 1 3 G O 2 5 R P 3 1 O G 4 4 U U 5 2 P R Bảng 3.5: Mã hóa hoán vị theo chu kỳ Theo bả ng trên, ký tự đầu trong khối 5 ký tự đƣợc chuyển tới vị trí thứ 3, ký tƣ̣ thƣ́ hai đƣợc chuyể n tớ i vi ̣trí thƣ́ 5, Chẳ ng haṇ tƣ̀ gố c GROUP đƣợc mã hoá thà nh 33
Chƣơng III: Các hệ mã khóa bí mật OPGUR. Bằ ng cá ch đó , bản rõ “I LOVE BEETHOVENS MUSIC” sẽ đƣợc chuyển thành “OEIVLEHBTEESONVSCMIU”. Hê ̣ mã ADFGV củ a Đƣ́ c , đƣợc sƣ̉ duṇ g trong suố t chiế n tranh thế giớ i lầ n thƣ́ I , là môṭ hê ̣ mã hoá đổ i chỗ (có sử dụng phƣơng phá p thay thế đơn giả n). Nó đƣợc coi là một thuâṭ toá n mã hoá phƣ́ c tap̣ và o thờ i ấ y nhƣng nó đã bi ̣phá bở i Georges Painvin , môṭ nhà thám mã ngƣời Pháp . Trên thƣ̣c tế c ó rất nhiều hệ thống mã hoá sử dụng phƣơng pháp đổ i chỗ, nhƣng chúng rấ t rắ c rố i vì thƣờng đòi hỏi không gian nhớ lớ n. 2. Các hệ mã khối Trong phầ n nà y chú ng ta sẽ hoc̣ về cá c hê ̣ mã k hố i điể n hình là chuẩ n mã hó a dƣ̃ liêụ DES (Data Encryption Standard), môṭ trong số cá c hê ̣ mã khố i đƣợc sƣ̉ duṇ g rôṇ g rãi nhấ t và là nề n tả ng cho rấ t nhiề u cá c hê ̣ mã khố i khá c. Chuẩ n mã hó a dƣ̃ liêụ DES là môṭ chuẩ n mã hoá đƣợc công bố bởi Uỷ ban Tiêu chuẩn quốc gia Hoa Kỳ vào 15/02/1977. Hệ mã nà y đƣợc xây dựng dựa trên một hệ mã khố i phổ biếnc ó tên là LUCIFER và đƣợc phát triển bởi IBM. DES có nhiề u ƣu điể m (nhanh, thuâṭ toá n công khai , dễ cà i đăṭ ) và đã tƣ̀ ng đƣợc sƣ̉ duṇ g trên thƣ̣c tế trong môṭ thờ i gian rấ t dà i (cho đế n trƣớ c đầ u nhƣ̃ ng năm 90) tuy nhiên theo thờ i gian năng lƣ̣c củ a cá c má y tính phá t triể n cù ng vớ i cá c ky ̃ thuâṭ thá m mã mớ i đƣợc đƣa ra đã cho thấ y nhu cầ u về môṭ hê ̣ mã khố i maṇ h hơn và chuẩn mã hóa cao cấp AES đã ra đờ i . Chuẩ n nà y ra đờ i dƣ̣a trên môṭ cuôc̣ thi về thiế t kế môṭ hê ̣ mã khố i an toà n hơn (vào năm 1997) thay thế cho DES củ a Ủ y ban Tiêu chuẩ n quố c gia củ a Hoa Kỳ (NIST). Có rất nhiều hệ mã đã đƣợc gửi đến làm ứng cử viên cho AES nhƣng cuố i cù ng hê ̣ mã Rijndael củ a hai tá c giả ngƣờ i Bi ̉ là tiế n si ̃ Joan Daemen và tiế n si ̃ Vincent Rijmen (vào năm 2001). 2.1. Mật mã khối Các hệ mã cổ điển mà chúng ta xem xét ở phần đầu chƣơng này đều có đặc điểm chung là từng ký tự của bản rõ đƣợc mã hoá tách biệt. Điều này làm cho việc phámãtrở nên dễ dàng hơn. Chính vì vậy, trên thực tế ngƣời ta hay dùng một kiểu mật mãkhác, trong đó từng khối ký tự của bản rõ đƣợc mã hoá cùng một lúc nhƣ là một đơn vị mãhoá đồng nhất. Trong kiểu mã hoá này, các tham số quan trọng là kích thƣớc (độ dài) củamỗi khối và kích thƣớc khoá. Điều kiện để mã hoá khối an toàn: Kích thƣớc khối phải đủ lớn để chống lạiphƣơng án tấn công bằng phƣơng pháp thống kê. Tuy nhiên điều này sẽ dẫn đến thời gian mã hoá sẽ tăng lên. Không gian khoá, tức chiều dài khoá phải đủ lớn để chống lại phƣơng ántấn công bằng vét cạn. Tuy nhiên khoá phải đủ ngắn để việc tạo khoá, phân phốivà lƣu trữ khoá đƣợc dễ dàng. Khi thiết kế một hệ mã khối, phải đảm bảo hai yêu cầusau: Sự hỗn loạn (confusion): sự phụ thuộc giữa bản rõ và bản mã phảithựcsự phức tạp để gây khóăn kh đối với việc tìm quy luật thám mã. Mối quan hệ này tốt nhất là phi tuyến. 34
Chƣơng III: Các hệ mã khóa bí mật Sự khuếch tán (diffusion): Mỗi bit của bản rõ và khóa phải ảnh hƣởng lên càng nhiều bit của bản mã càng tốt. Trong khi sự hỗn loạn (confusion) đƣợc tạo ra bằng ky ̃ thuật thay thế thì sự khuếch tán (diffusion) đƣợc tạo ra bằng các ky ̃ thuâṭ hoán vị. Các hệ mã khối mà chúng ta xem xét trong phần này đều thỏa mãn các yêu cầu đó. Ngoài các hệ mã khối đƣợc trình bày trong phần này còn rất nhiều các hệ mã khối khác đã phát triển qua thời gian (tại các quốc gia khác nhau v à ứng dụng trong các lĩnh vƣ̣c khá c nhau), có thể kể ra đây một số hệ mã nổi tiếng nhƣ: Lucifer (1969), DES (1977), Madryga (1984), NewDES (1985), FEAL, REDOC, LOKI (1990), Khufu and Khafre (1990), RC2, RC4, IDEA (1990), MMB, CA-1.1, Shipjack, GOST, CAST, Blowfish, SAFER, 3- Way, Crab, SXAL8/MBAL, SAFER, RC5, RC6 Đặc điểm chung của các hệ mã khối là quá trình mã hóa làm việc với cáckhốidữ liệu (thƣờng ở dạng xâu bit) có kích thƣớc khác nhau (tối thiếu là 64 bit), khóa của hệ mã cũng là một xâu bit có độ dài cố định (56 bit với DES, các hệ mã khác là 128, 256, hoặc thậm chí 512 bit). Tất cả các hệ mã này đều dựa trên lý thuyết của Shannon đƣa ra năm 1949 và nếu mang mã hóa hai bản rõ giống nhau sẽ thu đƣợc cùng một bản mã. Hoạt động của các hệ mãkhối thƣờng đƣợc thực hiện qua một số lần lặp, mỗi lần sẽ sửdụng một khóa con đƣợc sinh ra từ khóa chính. 2.2. Chuẩn mã hoá dữ liệu DES (Data Encryption Standard) Vào cuối thập niên 60, hê ̣ mã Lucifer đã đƣợc đƣa ra bởi Horst Feistel. Hê ̣ mã nà y gắ n liền với hãng IBM nổ i tiế ng. Sau đó Uỷ ban Tiêu chuẩn Hoa Kỳ đã dà n xế p vớ i IBM để thuật toán mã hóa này thành miễn phí và phát triển nó thành chuẩn mã hóa dữ liệu và công bố và o ngà y 15/02/1977. 2.2.1. Mô tả sơ đồ mã hoá DES Mô tả tổ ng quan: DES là thuâṭ toá n mã hó a vớ i input là khố i 64 bit, output cũng là khố i 64 bit. Khóa mã hóa có độ dài 56 bit, thƣ̣c ra chính xá c hơn phả i là 64 bit vớ i cá c bit ở vi ̣trí chia hế t cho 8 có thể sử dụng là cá c bit kiể m tra tính chẵn lẻ . Số khó a củ a không gian khó a K là 256. Hình 3.1: Chuẩ n mã hó a dƣ̃ liêụ DES Thuâṭ toá n thƣ̣c hiêṇ 16 vòng. Tƣ̀ khó a input K, 16 khóa con 48 bit Ki sẽ đƣợc sinh ra, mỗi khó a cho môṭ vò ng thƣ̣c hiêṇ trong quá trình mã hó a . Trong mỗi vò ng , 8 ánh xạ thay thế 6 bit thà nh 4 bit Si (còn gọi là hộp S i) đƣợc choṇ lƣ̣a ky ̃ cà ng và cố điṇ h , ký hiệu chung là S sẽ đƣợc sƣ̉ duṇ g. Bản rõ 64 bit sẽ đƣợc sƣ̉ duṇ g chia thà nh hai nƣ̉ a L 0 và R0. Các vòng có chức năng giống nhau , nhâṇ input là L i-1 và R i-1 tƣ̀ vò ng trƣớ c và sinh ra output là cá c xâu 32 bit Li và Ri nhƣ sau: 35
Chƣơng III: Các hệ mã khóa bí mật Li = Ri-1; (1) Ri = Li-1  f(Ri-1, Ki) trong đó f(Ri-1, Ki) = P( S( E(Ri-1)  Ki ) ); (2) Trong đó:  là ký hiệu của phép tuyển loại trừ (XOR) của hai xâu bit theo modulo 2. Hàm f là một hàm phi tuyến. E là hoá n vi ̣mở rôṇ g á nh xa ̣ R i-1 tƣ̀ 32 bit thà nh 48 bit (đôi khi tấ t cả cá c bit sẽ đƣợc sƣ̉ dụng hoặc một bit sẽ đƣợc sử dụng hai lần). P là hoá n vi ̣cố điṇ h khá c củ a 32 bit. Môṭ hoá n vi ̣bit khở i đầ u (IP) đƣợc sƣ̉ duṇ g cho vò ng đầ u tiên ; sau vò ng cuố i cù ng nƣ̉ a trá i và phả i sẽ đƣợc đổ i cho nhau và cuố i cù ng xâu kế t quả sẽ đƣợc hoá n vi ̣bit lầ n -1 cuố i bở i hoá n vi ̣ngƣợc củ a IP (IP ). Quá trình giải mã diễn ra tƣơng tự nhƣng với các khoá con ứng dụng vào các vòng trong theo thƣ́ tƣ̣ ngƣợc laị. Có thể hình dung đơn giản là phần bên p hải trong mỗi vòng (sau khi mở rôṇ g input 32 bit thà nh 8 ký tự 6 bit – xâu 48 bit) sẽ thực hiện một tính toán thay thế phu ̣ thuôc̣ khó a trên mỗi môṭ ký tƣ̣ trong xâu 48 bit, và sau đó sử dụng một phép chuyển bit cố định để phân bố laị cá c bit củ a cá c ký tƣ̣ kế t quả hình thà nh nên output 32 bit. Các khoá con Ki (chƣ́ a 48 bit củ a K) đƣợc tính bằ ng cá ch sƣ̉ duṇ g cá c bả ng PC1 và PC2 (Permutation Choice 1 và 2). Trƣớ c tiên 8 bit (k8, k16, ,k64) của K bị bỏ đ i (áp dụng PC1). 56 bit cò n laị đƣợc hoá n vi ̣và gá n cho hai biế n 28 bit C và D , và sau đó trong 16 vòng lặp cả C và D sẽ đƣợc quay 1 hoăc̣ 2 bit, và các khóa con 48 bit Ki đƣợc choṇ tƣ̀ kế t quả của việc ghép hai xâu với nhau. Nhƣ vậy, ta có thể mô tả toàn bộ thuật toán sinh mã DES dƣới dạng công thức nhƣ sau: -1 Y = IP f16 T f15 T f2 T f1 IP(x) Trong đó: T mô tả phép hoán vị của các khối LiRi (1 ≤ i ≤ 15). fi mô tả việc dùng hàm f với khoá Ki (1 ≤ i ≤ 16). Thuâṭ toá n chi tiế t: Input: bản rõ M = m1m2 m64, khóa 64 bit K = k1k2 k64 (bao gồ m cả 8 bit chẵn lẻ , viêc̣ thêm bit chẵn lẻ sao cho cá c đoaṇ khó a 8 bit có số bit 1 là lẻ) Output: bản mã 64 bit C = c1c2 c64 1. Sinh khó a con. Tính các khóa con theo thuật toán sinh khóa con bên dƣới 2. (L0,R0)  IP(m1m2 m64) (Sƣ̉ duṇ g bả ng hoá n vi ̣IP để hoá n vi ̣cá c bit , kế t quả nhâṇ đƣợc chia thà nh hai nƣ̉ a là L0 = m58m50 m8, R0 = m57m49 m7.) 3. (16 vòng) for i = 1 to 16 Tính các Li và Ri theo cá c công thƣ́ c (1) và (2), viêc̣ tính 36
Chƣơng III: Các hệ mã khóa bí mật f(Ri-1, Ki) = P( S( E(Ri-1)  Ki ) ) đƣợc thƣ̣c hiêṇ nhƣ sau: a) Mở rôṇ g R i-1 = r1r2 r32 tƣ̀ 32 bit thà nh 48 bit bằ ng cá ch sƣ̉ duṇ g hoá n vi ̣mở rôṇ g E. T  E(Ri-1). (Vì thế T = r32r1r2 r32r1) b) T’  T  Ki. Biể u diễn T’ nhƣ là cá c xâu gồ m 8 ký tự 6 bit T’ = (B1, ,B8) c) T’’  (S1(B1), S2(B2), ,S8(B8)). Trong đó Si(Bi) ánh xạ b1b2 b6 thành các xâu 4 bit củ a phầ n tƣ̉ thuôc̣ hà ng r và côṭ c củ a cá c bả ng S i (S box) trong đó r = 2 * b1 + b6 và c = b2b3b4b5 là một số nhị phân từ 0 tớ i 15. Chẳ ng haṇ S 1(011011) sẽ cho r = 1 và c = 13 và kết quả là 5 biể u diễn dƣớ i daṇ g nhi ̣phân là 0101. d) T’’’  P(T’’) trong đó P là hoá n vi ̣cố điṇ h để hoá n vi ̣ 32 bit củ a T ’’ = t1t2 t32 sinh ra t16t7 t25. 4. b1b2 b64  (R16, L16) (đổ i vi ̣trí cá c khố i cuố i cù ng L16, R16 -1 -1 5. C  IP (b1b2 b64) (Biế n đổ i sƣ̉ duṇ g IP , C = b40b8 b25) Sơ đồ16 vòng lặp của DES: 37