Bài giảng An toàn và bảo mật thông tin - Trần Minh Văn (Phần 1)

99 trang phuongnguyen 4630

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng An toàn và bảo mật thông tin - Trần Minh Văn (Phần 1)", để 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:

bai_giang_an_toan_va_bao_mat_thong_tin_tran_minh_van.pdf

Nội dung text: Bài giảng An toàn và bảo mật thông tin - Trần Minh Văn (Phần 1)

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC NHA TRANG KHOA CÔNG NGHỆ THÔNG TIN   BÀI GIẢNG AN TOÀN VÀ BẢO MẬT THÔNG TIN (Lưu hành nội bộ) Nha Trang, tháng 6 năm 2008 1
BÀI GIẢNG AN TOÀN VÀ BẢO MẬT THÔNG TIN Biên soạn: Trần Minh Văn (Tài liệu tham khảo chính: Cryptography and Network Security Principles and Practices, 4th Edition William Stallings Prentice Hall 2005) 2
MỤC LỤC CHƢƠNG 1. GIỚI THIỆU VỀ AN TOÀN VÀ BẢO MẬT THÔNG TIN 8 1.1 Giới thiệu 8 1.2 Bảo vệ thông tin trong quá trình truyền thông tin trên mạng 8 1.2.1 Các loại hình tấn công 8 1.2.2 Yêu cầu của một hệ truyền thông tin an toàn và bảo mật 10 1.2.3 Vai trò của mật mã trong việc bảo mật thông tin trên mạng 11 1.2.4 Các giao thức (protocol) thực hiện bảo mật. 11 1.3 Bảo vệ hệ thống khỏi sự xâm nhập phá hoại từ bên ngoài 11 1.4 Câu hỏi ôn tập 13 CHƢƠNG 2. MÃ HÓA ĐỐI XỨNG CĂN BẢN 14 2.1 Mã hóa Ceasar 14 2.2 Mô hình mã hóa đối xứng (Symmetric Ciphers) 15 2.3 Mã hóa thay thế đơn bảng (Monoalphabetic Substitution Cipher) 17 2.4 Mã hóa thay thế đa ký tự 19 2.4.1 Mã Playfair 19 2.4.2 Mã Hill 20 2.5 Mã hóa thay thế đa bảng (Polyalphabetic Substitution Cipher) 21 2.6 One-Time Pad 23 2.7 Mã hoán vị (Permutation Cipher) 24 2.8 Tổng kết 25 2.9 Câu hỏi ôn tập 27 2.10 Bài Tập 27 2.11 Bài Tập Thực Hành 28 CHƢƠNG 3. MÃ HÓA ĐỐI XỨNG HIỆN ĐẠI 30 3.1 Mã dòng (Stream Cipher) 31 3.1.1 A5/1 32 3.1.2 RC4 34 3.2 Mã khối (Block Cipher) 37 3.2.1 Mã khối an toàn lý tưởng 37 3.2.2 Mạng SPN 38 3.2.3 Mô hình mã Feistel 38 3.3 Mã TinyDES 40 3.3.1 Các vòng của TinyDES 40 3
3.3.2 Thuật toán sinh khóa con của TinyDES 42 3.3.3 Ví dụ về TinyDES 42 3.3.4 Khả năng chống phá mã known-plaintext của TinyDES 42 3.4 Mã DES (Data Encryption Standard) 43 3.4.1 Hoán vị khởi tạo và hoán vị kết thúc: 44 3.4.2 Các vòng của DES 45 3.4.3 Thuật toán sinh khóa con của DES 46 3.4.4 Hiệu ứng lan truyền (Avalanche Effect) 47 3.4.5 Độ an toàn của DES 48 3.5 Một số phương pháp mã khối khác 49 3.5.1 Triple DES 49 3.5.2 Advanced Encryption Standard (AES) 49 3.6 Các mô hình ứng dụng mã khối 50 3.6.1 Electronic Codebook – ECB 50 3.6.2 Cipher Block Chaining – CBC 51 3.6.3 Counter – CTR 53 3.6.4 Output Feedback – OFB 53 3.6.5 Cipher Feedback – CFB 54 3.7 Tính chứng thực (authentication) của mã hóa đối xứng. 55 3.8 Tính không thoái thác (non-repudiation) của mã hóa đối xứng. 56 3.9 Trao đổi khóa bí mật bằng trung tâm phân phối khóa 56 3.10 Câu hỏi ôn tập 58 3.11 Bài tập 58 3.12 Bài tập thực hành 59 CHƢƠNG 4. MÃ HÓA KHÓA CÔNG KHAI 61 4.1 Lý thuyết số 63 4.1.1 Một số khái niệm 63 4.1.2 Định lý Fermat 64 4.1.3 Phép logarit rời rạc 64 4.2 RSA 66 4.2.1 Nguyên tắc thực hiện của RSA 66 4.2.2 Ví dụ RSA 67 4.3 Độ phức tạp tính toán trong RSA 68 4.3.1 Phép tính mã hóa/giải mã 68 4.3.2 Phép tính sinh khóa 70 4.4 Độ an toàn của RSA 70 4
4.5 Bảo mật, chứng thực và không thoái thác với mã hóa khóa công khai 71 4.6 Trao đổi khóa 72 4.6.1 Trao đổi khóa công khai 73 4.6.2 Dùng mã hóa khóa công khai để trao đổi khóa bí mật 74 4.7 Phương pháp trao đổi khóa Diffie – Hellman 75 4.8 Câu hỏi ôn tập 76 4.9 Bài tập 77 4.10 Bài tập thực hành 77 CHƢƠNG 5. MÃ CHỨNG THỰC THÔNG ĐIỆP, HÀM BĂM 79 5.1 Mã chứng thực thông điệp 80 5.2 Hàm băm – Hash function 82 5.2.1 Bài toán ngày sinh nhật 82 5.2.2 Hàm băm MD5 và SHA-1 84 5.2.3 HMAC 92 5.3 Hàm băm và chữ ký điện tử 95 5.4 Một số ứng dụng khác của hàm băm 92 5.4.1 Lưu trữ mật khẩu 92 5.4.2 Đấu giá trực tuyến 93 5.4.3 Download file 94 5.5 Câu hỏi ôn tập 96 5.6 Bài tập 97 5.7 Bài tập thực hành 97 CHƢƠNG 6. GIAO THỨC 100 6.1 Phát lại thông điệp (Replay Attack) 100 6.2 Giao thức bảo mật 101 6.2.1 Định danh và trao đổi khóa phiên dùng mã hóa đối xứng với KDC 101 6.2.2 Định danh và trao đổi khóa phiên dùng mã hóa khóa công khai 102 6.3 Câu hỏi ôn tập 103 6.4 Bài tập 103 CHƢƠNG 7. MỘT SỐ ỨNG DỤNG THỰC TIỄN 105 7.1 Giới thiệu 105 7.2 Chứng thực X.509 105 7.2.1 Cấu trúc chứng thực 105 7.2.2 Phân cấp chứng thực 108 7.2.3 Các định dạng file của chứng chỉ X.509 109 5
7.3 Giao thức bảo mật web Secure Socket Layer version 3 - SSLv3 110 7.3.1 Giao thức bắt tay - SSL Handshaking Protocol 113 7.3.2 Giao thức truyền số liệu - SSL Record Protocol 116 7.3.3 SSL Session và SSL Connection 117 7.4 Giao thức bảo mật mạng cục bộ Keberos 117 7.4.1 Keberos version 4 117 7.5 Câu hỏi ôn tập 119 7.6 Bài tập thực hành 120 CHƢƠNG 8. PHÁ MÃ VI SAI VÀ PHÁ MÃ TUYẾN TÍNH 121 8.1 Phá mã vi sai (Differential Cryptanalysis) 121 8.2 Phá mã tuyến tính (Linear Cryptanalysis) 126 8.3 Kết luận về nguyên tắc thiết kế mã khối. 128 CHƢƠNG 9. ADVANCED ENCRYPTION STANDARD – AES 129 9.1 Nhóm, vành, trường 129 9.1.1 Nhóm (Group) 129 9.1.2 Vành (Ring) 130 9.1.3 Trường (Field) 130 9.2 Số học modulo và trường hữu hạn GF(p) 131 9.3 Số học đa thức và trường hữu hạn GF(2n) 132 9.3.1 Phép toán đa thức thông thường 132 9.3.2 Đa thức định nghĩa trên tập Zp 133 9.3.3 Phép modulo đa thức 134 9.3.4 Trường hữu hạn GF(2n) 134 9.3.5 Ứng dụng GF(2n) trong mã hóa 136 9.3.6 Tính toán trong GF(2n) 137 9.3.7 Tính toán trong GF(2n) với phần tử sinh 138 9.4 Mã hóa AES 139 9.4.1 Substitute bytes 141 9.4.2 Shift rows 145 9.4.3 Mix columns 145 9.4.4 Add row key 147 9.4.5 Expand key 147 9.4.6 Kết luận 148 CHƢƠNG 10. MÃ HÓA ĐƢỜNG CONG ELLIPTIC 149 10.1 Đường cong Elliptic trên số thực 149 10.2 Đường cong Elliptic trên trường Zp. 152 6
10.3 Đường cong Elliptic trên trường GF(2m). 155 10.4 Đường cong Elliptic trong mã hóa - ECC 156 10.4.1 Trao đổi khóa EC Diffie-Hellman 156 10.4.2 Mã hóa và giải mã EC 157 10.4.3 Độ an toàn của ECC so với RSA 158 10.5 Chuẩn chữ ký điện tử (Digital Signature Standard – DSS) 158 CHƢƠNG 11. MỘT SỐ VẤN ĐỀ AN TOÀN BẢO MẬT 161 11.1 Giấu tin trong ảnh số 161 11.2 Lỗi phần mềm 162 11.2.1 Tràn bộ đệm (Buffer Overflow) 162 11.2.2 Chèn câu lệnh SQL (SQL Injection) 166 11.2.3 Chèn câu lệnh script (Cross-site Scripting XSS) 168 11.3 Bài tập thực hành 170 PHỤ LỤC 1 172 Chi Tiết các S-box của mã hóa DES 172 PHỤ LỤC 2 174 Thuật toán Euclid 174 Phương pháp kiểm tra số nguyên tố lớn Miller-Rabin 176 Định lý số dư Trung Hoa 179 Cài đặt giao thức SSL cho Web server IIS 181 TÀI LIỆU THAM KHẢO 182 7
CHƢƠNG 1. GIỚI THIỆU VỀ AN TOÀN VÀ BẢO MẬT THÔNG TIN 1.1 Giới thiệu Trước đây khi công nghệ máy tính chưa phát triển, khi nói đến vấn đề an toàn bảo mật thông tin (Information Security), chúng ta thường hay nghĩ đến các biện pháp nhằm đảm bảo cho thông tin được trao đổi hay cất giữ một cách an toàn và bí mật. Chẳng hạn là các biện pháp như: Đóng dấu và ký niêm phong một bức thư để biết rằng lá thư có được chuyển nguyên vẹn đến người nhận hay không. Dùng mật mã mã hóa thông điệp để chỉ có người gửi và người nhận hiểu được thông điệp. Phương pháp này thường được sử dụng trong chính trị và quân sự (xem chương 2). Lưu giữ tài liệu mật trong các két sắt có khóa, tại các nơi được bảo vệ nghiêm ngặt, chỉ có những người được cấp quyền mới có thể xem tài liệu. Với sự phát triển mạnh mẽ của công nghệ thông tin, đặt biệt là sự phát triển của mạng Internet, ngày càng có nhiều thông tin được lưu giữ trên máy vi tính và gửi đi trên mạng Internet. Và do đó xuất hiện nhu cầu về an toàn và bảo mật thông tin trên máy tính. Có thể phân loại mô hình an toàn bảo mật thông tin trên máy tính theo hai hướng chính như sau: 1) Bảo vệ thông tin trong quá trình truyền thông tin trên mạng (Network Security) 2) Bảo vệ hệ thống máy tính, và mạng máy tính, khỏi sự xâm nhập phá hoại từ bên ngoài (System Security) Phần tiếp theo sau sẽ lần lượt trình bày các đặc điểm chính của hai mô hình trên. 1.2 Bảo vệ thông tin trong quá trình truyền thông tin trên mạng 1.2.1 Các loại hình tấn công Để xem xét những vấn đề bảo mật liên quan đến truyền thông trên mạng, chúng ta hãy lấy một bối cảnh sau: có ba nhân vật tên là Alice, Bob và Trudy, trong đó Alice và Bob thực hiện trao đổi thông tin với nhau, còn Trudy là kẻ xấu, đặt thiết bị can thiệp vào kênh truyền tin giữa Alice và Bob. Sau đây là các loại hành động tấn công của Trudy mà ảnh hưởng đến quá trình truyền tin giữa Alice và Bob: 1) Xem trộm thông tin (Release of Message Content) Trong trường hợp này Trudy chặn các thông điệp Alice gửi cho Bob, và xem được nội dung của thông điệp. 8
Trudy Đọc nội dung thông điệp của Alice Network Alice Bob Hình 1-1. Xem trộm thông điệp 2) Thay đổi thông điệp (Modification of Message) Trudy chặn các thông điệp Alice gửi cho Bob và ngăn không cho các thông điệp này đến đích. Sau đó Trudy thay đổi nội dung của thông điệp và gửi tiếp cho Bob. Bob nghĩ rằng nhận được thông điệp nguyên bản ban đầu của Alice mà không biết rằng chúng đã bị sửa đổi. Trudy Sửa thông điệp của Alice gửi cho Bob Network Alice Bob Hình 1-2. Sửa thông điệp 3) Mạo danh (Masquerade) Trong trường hợp này Trudy giả là Alice gửi thông điệp cho Bob. Bob không biết điều này và nghĩ rằng thông điệp là của Alice. Trudy Trudy giả là Alice gởi thông điệp cho Bob Network Alice Bob Hình 1-3. Mạo danh 9
4) Phát lại thông điệp (Replay) Trudy sao chép lại thông điệp Alice gửi cho Bob. Sau đó một thời gian Trudy gửi bản sao chép này cho Bob. Bob tin rằng thông điệp thứ hai vẫn là từ Alice, nội dung hai thông điệp là giống nhau. Thoạt đầu có thể nghĩ rằng việc phát lại này là vô hại, tuy nhiên trong nhiều trường hợp cũng gây ra tác hại không kém so với việc giả mạo thông điệp. Xét tình huống sau: giả sử Bob là ngân hàng còn Alice là một khách hàng. Alice gửi thông điệp đề nghị Bob chuyển cho Trudy 1000$. Alice có áp dụng các biện pháp như chữ ký điện tử với mục đích không cho Trudy mạo danh cũng như sửa thông điệp. Tuy nhiên nếu Trudy sao chép và phát lại thông điệp thì các biện pháp bảo vệ này không có ý nghĩa. Bob tin rằng Alice gửi tiếp một thông điệp mới để chuyển thêm cho Trudy 1000$ nữa. Trudy Sao chép thông điệp của Alice và gửi lại sau cho Bob Network Alice Bob Hình 1-4. Phát lại thông điệp 1.2.2 Yêu cầu của một hệ truyền thông tin an toàn và bảo mật Phần trên đã trình bày các hình thức tấn công, một hệ truyền tin được gọi là an toàn và bảo mật thì phải có khả năng chống lại được các hình thức tấn công trên. Như vậy hệ truyền tin phải có các đặt tính sau: 1) Tính bảo mật (Confidentiality): Ngăn chặn được vấn đề xem trộm thông điệp. 2) Tính chứng thực (Authentication): Nhằm đảm bảo cho Bob rằng thông điệp mà Bob nhận được thực sự được gửi đi từ Alice, và không bị thay đổi trong quá trình truyền tin. Như vậy tính chứng thực ngăn chặn các hình thức tấn công sửa thông điệp, mạo danh, và phát lại thông điệp. 3) Tính không từ chối (Nonrepudiation): xét tình huống sau: Giả sử Bob là nhân viên môi giới chứng khoán của Alice. Alice gởi thông điệp yêu cầu Bob mua cổ phiếu của công ty Z. Ngày hôm sau, giá cổ phiếu công ty này giảm hơn 50%. Thấy bị thiệt hại, Alice nói rằng Alice không gửi thông điệp nào cả và quy trách nhiệm cho Bob. Bob phải có cơ chế để xác định rằng chính Alice là người gởi mà Alice không thể từ chối trách nhiệm được. Khái niệm chữ ký trên giấy mà con người đang sử dụng ngày nay là một cơ chế để bảo đảm tính chứng thực và tính không từ chối. Và trong lĩnh vực máy tính, người ta cũng thiết lập một cơ chế như vậy, cơ chế này được gọi là chữ ký điện tử. 10
chuyển đổi chuyển đổi liên quan đến liên quan đến an toàn an toàn kênh thông tin Bên gửi thông tin thông tin Bên nhận bí mật bí mật Đối thủ Hình 1-5. Mô hình bảo mật truyền thông tin trên mạng 1.2.3 Vai trò của mật mã trong việc bảo mật thông tin trên mạng Mật mã hay mã hóa dữ liệu (cryptography), là một công cụ cơ bản thiết yếu của bảo mật thông tin. Mật mã đáp ứng được các nhu cầu về tính bảo mật (confidentiality), tính chứng thực (authentication) và tính không từ chối (non-repudiation) của một hệ truyền tin. Tài liệu này trước tiên trình bày về mật mã cổ điển. Những hệ mật mã cổ điển này tuy ngày nay tuy ít được sử dụng, nhưng chúng thể hiện những nguyên lý cơ bản được ứng dụng trong mật mã hiện đại. Dựa trên nền tảng đó, chúng ta sẽ tìm hiểu về mã hóa đối xứng và mã hóa bất đối xứng, chúng đóng vai trò quan trọng trong mật mã hiện đại. Bên cạnh đó chúng ta cũng sẽ tìm hiểu về hàm Hash, cũng là một công cụ bảo mật quan trọng mà có nhiều ứng dụng lý thú, trong đó có chữ ký điện tử. Các chương 2, 3, 4, 5 sẽ lần lượt trình bày những nội dung liên quan đến mật mã. 1.2.4 Các giao thức (protocol) thực hiện bảo mật. Sau khi tìm hiểu về mật mã, chúng ta sẽ tìm hiểu về cách ứng dụng chúng vào thực tế thông qua một số giao thức bảo mật phổ biến hiện nay là: Keberos: là giao thức dùng để chứng thực dựa trên mã hóa đối xứng. Chuẩn chứng thực X509: dùng trong mã hóa khóa công khai. Secure Socket Layer (SSL): là giao thức bảo mật Web, được sử dụng phổ biến trong Web và thương mại điện tử. PGP và S/MIME: bảo mật thư điện tử email. Mô hình lý thuyết và nội dung các giao thức trên được trình bày trong chương 6 và chương 7. 1.3 Bảo vệ hệ thống khỏi sự xâm nhập phá hoại từ bên ngoài Ngày nay, khi mạng Internet đã kết nối các máy tính ở khắp nơi trên thế giới lại với nhau, thì vấn đề bảo vệ máy tính khỏi sự thâm nhập phá hoại từ bên ngoài là một điều cần thiết. Thông qua mạng Internet, các hacker có thể truy cập vào các máy tính trong một tổ chức (dùng telnet chẳng hạn), lấy trộm các dữ liệu quan trọng như mật khẩu, thẻ tín dụng, tài liệu Hoặc đơn giản chỉ là phá hoại, gây trục trặc hệ thống mà tổ chức đó phải tốn nhiều chi phí để khôi phục lại tình trạng hoạt động bình thường. 11
Để thực hiện việc bảo vệ này, người ta dùng khái niệm “kiểm soát truy cập” (Access Control). Khái niệm kiểm soát truy cập này có hai yếu tố sau: Chứng thực truy cập (Authentication): xác nhận rằng đối tượng (con người hay chương trình máy tính) được cấp phép truy cập vào hệ thống. Ví dụ: để sử dụng máy tính thì trước tiên đối tượng phải logon vào máy tính bằng username và password. Ngoài ra, còn có các phương pháp chứng thực khác như sinh trắc học (dấu vân tay, mống mắt ) hay dùng thẻ (thẻ ATM ). Phân quyền (Authorization): các hành động được phép thực hiện sau khi đã truy cập vào hệ thống. Ví dụ: bạn được cấp username và password để logon vào hệ điều hành, tuy nhiên bạn chỉ được cấp quyền để đọc một file nào đó. Hoặc bạn chỉ có quyền đọc file mà không có quyền xóa file. Với nguyên tắc như vậy thì một máy tính hoặc một mạng máy tính được bảo vệ khỏi sự thâm nhập của các đối tượng không được phép. Tuy nhiên thực tế chúng ta vẫn nghe nói đến các vụ tấn công phá hoại. Để thực hiện điều đó, kẻ phá hoại tìm cách phá bỏ cơ chế Authentication và Authorization bằng các cách thức sau: Dùng các đoạn mã phá hoại (Malware): như virus, worm, trojan, backdoor những đoạn mã độc này phát tán lan truyền từ máy tính này qua máy tính khác dựa trên sự bất cẩn của người sử dụng, hay dựa trên các lỗi của phần mềm. Lợi dụng các quyền được cấp cho người sử dụng (chẳng hạn rất nhiều người login vào máy tính với quyền administrator), các đoạn mã này thực hiện các lệnh phá hoại hoặc dò tìm password của quản trị hệ thống để gửi cho hacker, cài đặt các cổng hậu để hacker bên ngoài xâm nhập. Thực hiện các hành vi xâm phạm (Intrusion): việc thiết kế các phần mềm có nhiểu lỗ hổng, dẫn đến các hacker lợi dụng để thực hiện những lệnh phá hoại. Những lệnh này thường là không được phép đối với người bên ngoài, nhưng lỗ hổng của phần mềm dẫn đến được phép. Trong những trường hợp đặc biệt, lỗ hổng phần mềm cho phép thực hiện những lệnh phá hoại mà ngay cả người thiết kế chương trình không ngờ tới. Hoặc hacker có thể sử dụng các cổng hậu do các backdoor tạo ra để xâm nhập. Để khắc phục các hành động phá hoại này, người ta dùng các chương trình có chức năng gác cổng, phòng chống. Những chương trình này dò tìm virus hoặc dò tìm các hành vi xâm phạm đển ngăn chặn chúng, không cho chúng thực hiện hoặc xâm nhập. Đó là các chương trình chống virus, chương trình firewall Ngoài ra các nhà phát triển phần mềm cần có quy trình xây dựng và kiểm lỗi phần mềm nhằm hạn chế tối đa những lỗ hổng bảo mật có thể có. 12
Hệ Thống Thông Tin - Các tài nguyên tính toán (bộ nhớ, chíp xử lý ) Kênh truy cập - Dữ liệu - Các tiến trình - Phần mềm Chức năng - Các tài nguyên mạng Con người: hacker. gác cổng Phần mềm: virus, worm Hình 1-6.Mô hình phòng chống xâm nhập và phá hoại hệ thống Trong khuôn khổ của tài liệu này chỉ đề cập các nội dung về an toàn và bảo mật truyền tin trên mạng. Các bạn có thể tìm hiểu cụ thể hơn các nội dung liên quan đến bảo vệ chống xâm nhập trong [3]. 1.4 Câu hỏi ôn tập 1) Nêu các hình thức tấn công trong quá trình truyền tin trên mạng. 2) Bảo vệ thông tin trong quá trình truyền đi trên mạng là gì? 3) Bảo vệ hệ thống khỏi sự tấn công bên ngoài là gì? 13
CHƢƠNG 2. MÃ HÓA ĐỐI XỨNG CĂN BẢN Trong chương này chúng ta sẽ tìm hiểu một số khái niệm cơ bản về phương pháp mã hóa đối xứng. Đây là phương pháp chủ yếu trong việc bảo đảm tính bảo mật (confidentiality) của một hệ truyền tin. Trước tiên, chúng ta sẽ tìm hiểu phương pháp mã hóa Ceasar và sau đó là mô hình tổng quát của phương pháp mã hóa đối xứng cùng một số tính chất liên quan. Phần còn lại của chương trình bày một số phương pháp mã hóa cổ điển phổ biến khác. 2.1 Mã hóa Ceasar Thế kỷ thứ 3 trước công nguyên, nhà quân sự người La Mã Julius Ceasar đã nghĩ ra phương pháp mã hóa một bản tin như sau: thay thế mỗi chữ trong bản tin bằng chữ đứng sau nó k vị trí trong bảng chữ cái. Giả sử chọn k = 3, ta có bảng chuyển đổi như sau: Chữ ban đầu: 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 Chữ thay thế: 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 (sau Z sẽ vòng lại là A, do đó x A, y B và z C) Giả sử có bản tin gốc (bản rõ): meet me after the toga party Như vậy bản tin mã hóa (bản mã) sẽ là: PHHW PH DIWHU WKH WRJD SDUWB Thay vì gửi trực tiếp bản rõ cho các cấp dưới, Ceasar gửi bản mã. Khi cấp dưới nhận được bản mã, tiến hành giải mã theo quy trình ngược lại để có được bản rõ. Như vậy nếu đối thủ của Ceasar có lấy được bản mã, thì cũng không hiểu được ý nghĩa của bản mã. Chúng ta hãy gán cho mỗi chữ cái một con số nguyên từ 0 đến 25: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Phương pháp Ceasar được biểu diễn như sau: với mỗi chữ cái p thay bằng chữ mã hóa C, trong đó: C = (p + k) mod 26 (trong đó mod là phép chia lấy số dư) Và quá trình giải mã đơn giản là: p = (C – k) mod 26 k được gọi là khóa. Dĩ nhiên là Ceasar và cấp dưới phải cùng dùng chung một giá trị khóa k, nếu không bản tin giải mã sẽ không giống bản rõ ban đầu. Ngày nay phương pháp mã hóa của Ceasar không được xem là an toàn. Giả sử đối thủ của Ceasar có được bản mã PHHW PH DIWHU WKH WRJD SDUWB và biết được phương pháp mã hóa và giải mã là phép cộng trừ modulo 26. Đối thủ có thể thử tất cả 25 trường hợp của k như sau: 14
KEY PHHW PH DIWHU WKH WRJD SDUWB 1 oggv og chvgt vjg vqic rctva 2 nffu nf bgufs uif uphb qbsuz 3 meet me after the toga party 4 ldds ld zesdq sgd snfz ozqsx 5 kccr kc ydrcp rfc rmey nyprw 6 jbbq jb xcqbo qeb qldx mxoqv 7 iaap ia wbpan pda pkcw lwnpu 8 hzzo hz vaozm ocz ojbv kvmot 9 gyyn gy uznyl nby niau julns 10 fxxm fx tymxk max mhzt itkmr 11 ewwl ew sxlwj lzw lgys hsjlq 12 dvvk dv rwkvi kyv kfxr grikp 13 cuuj cu qvjuh jxu jewq fqhjo 14 btti bt puitg iwt idvp epgin 15 assh as othsf hvs hcuo dofhm 16 zrrg zr nsgre gur gbtn cnegl 17 yqqf yq mrfqd ftq fasm bmdfk 18 xppe xp lqepc esp ezrl alcej 19 wood wo kpdob dro dyqk zkbdi 20 vnnc vn jocna cqn cxpj yjach 21 ummb um inbmz bpm bwoi xizbg 22 tlla tl hmaly aol avnh whyaf 23 skkz sk glzkx znk zumg vgxze 24 rjjy rj fkyjw ymj ytlf ufwyd 25 qiix qi ejxiv xli xske tevxc Trong 25 trường hợp trên, chỉ có trường hợp k=3 thì bản giải mã tương ứng là có ý nghĩa. Do đó đối thủ có thể chắc chắn rằng „meet me after the toga party„ là bản rõ ban đầu. 2.2 Mô hình mã hóa đối xứng (Symmetric Ciphers) Phương pháp Ceasar là phương pháp mã hóa đơn giản nhất của mã hóa đối xứng. Về mặt khái niệm, phương pháp mã hóa đối xứng tổng quát được biểu diễn bằng mô hình sau: bộ sinh khóa kênh an toàn K P kênh thường P nơi gởi Mã hóa Giải mã nơi nhận C ̂ Phá mã ̂ Hình 2-1. Mô hình mã hóa đối xứng Mô hình trên gồm 5 yếu tố: 15
Bản rõ P (plaintext) Thuật toán mã hóa E (encrypt algorithm) Khóa bí mật K (secret key) Bản mã C (ciphertext) Thuật toán giải mã D (decrypt algorithm) Trong đó: C = E (P, K) P = D (C, K) Thuật toán mã hóa và giải mã sử dụng chung một khóa, thuật toán giải mã là phép toán ngược của thuật toán mã hóa (trong mã hóa Ceasar, E là phép cộng còn D là phép trừ). Vì vậy mô hình trên được gọi là phương pháp mã hóa đối xứng. Bản mã C được gởi đi trên kênh truyền. Do bản mã C đã được biến đổi so với bản rõ P, cho nên những người thứ ba can thiệp vào kênh truyền để lấy được bản mã C, thì không hiểu được ý nghĩa của bản mã. Đây chính là đặc điểm quan trọng của mã hóa, cho phép đảm bảo tính bảo mật (confidentiality) của một hệ truyền tin đã đề cập trong chương 1. Một đặc tính quan trọng của mã hóa đối xứng là khóa phải được giữ bí mật giữa người gởi và người nhận, hay nói cách khác khóa phải được chuyển một cách an toàn từ người gởi đến người nhận. Có thể đặt ra câu hỏi là nếu đã có một kênh an toàn để chuyển khóa như vậy thì tại sao không dùng kênh đó để chuyển bản tin, tại sao cần đến chuyện mã hóa? Câu trả lời là nội dung bản tin thì có thể rất dài, còn khóa thì thường là ngắn. Ngoài ra một khóa còn có thể áp dụng để truyền tin nhiều lần. Do đó nếu chỉ chuyển khóa trên kênh an toàn thì đỡ tốn kém chi phí. Đặc tính quan trọng thứ hai của một hệ mã hóa đối xứng là tính an toàn của hệ mã. Như đã thấy ở phần mã hóa Ceasar, từ một bản mã có thể dễ dàng suy ra được bản rõ ban đầu mà không cần biết khóa bí mật. Hành động đi tìm bản rõ từ bản mã mà không cần khóa như vậy được gọi là hành động phá mã (cryptanalysis). Do đó một hệ mã hóa đối xứng được gọi là an toàn khi và chỉ khi nó không thể bị phá mã (điều kiện lý tưởng) hoặc thời gian phá mã là bất khả thi. Trong phương pháp Ceasar, lý do mà phương pháp này kém an toàn là ở chỗ khóa k chỉ có 25 giá trị, do đó kẻ phá mã có thể thử được hết tất cả các trường hợp của khóa rất nhanh chóng. Phương pháp tấn công này được gọi là phương pháp vét cạn khóa (brute- force attack). Chỉ cần nới rộng miền giá trị của khóa thì có thể tăng thời gian phá mã đến một mức độ được coi là bất khả thi. Bảng dưới đây liệt kê một số ví dụ về thời gian phá mã trung bình tương ứng với kích thước của khóa. Kích thƣớc khóa Số lƣợng khóa Thời gian thực hiện Thời gian thực hiện (bít) (tốc độ thử: 103 khóa/giây) (tốc độ thử: 109 khóa/giây) 32 232 ≈ 4.3 x 109 35.8 phút 2.15 mili giây 56 256 ≈ 7.2 x 1016 1142 năm 10.01 giờ 128 2128 ≈ 3.4 x 1038 5.4 x 1024 năm 5.4 x 1018 năm 168 2168 ≈ 3. 7 x 1050 5.9 x 1036 năm 5.9 x 1030 năm hoán vị 26 ký tự 26! ≈ 4 x 1026 6.4 x 1012 năm 6.4 x 106 năm 16
(tốc độ CPU hiện nay khoảng 3x109 Hz, tuổi vũ trụ vào khoảng ≈ 1010 năm) Bảng 2-1. Thời gian vét cạn khóa theo kích thước khóa Phần 2.3 sẽ trình bày phương pháp mã hóa đơn bảng, đây là phương pháp mà miền giá trị của khóa là 26!. Do đó mã hóa đơn bảng an toàn đối với phương pháp tấn công vét cạn trên khóa. Phần 2.6 trình bày phương pháp mã hóa One-Time Pad, phương pháp này có đặt tính là tồn tại rất nhiều khóa mà mỗi khóa khi đưa vào giải mã đều cho ra bản tin có ý nghĩa (phương pháp Ceasar chỉ tồn tại một khóa giải mã cho ra bản tin có ý nghĩa). Do đó việc vét cạn khóa không có ý nghĩa đối với mã hóa One-Time Pad. Về mặt lý thuyết, phương pháp này được chứng minh là an toàn tuyệt đối. Hiện nay, ngoài phương pháp One-Time Pad, người ta chưa tìm ra phương pháp mã hóa đối xứng an toàn tuyệt đối nào khác. Do đó chúng ta chấp nhận rằng một phương pháp mã hóa đối xứng là an toàn nếu phương pháp đó có điều kiện sau: Không tồn tại kỹ thuật tấn công tắt nào khác tốt hơn phương pháp vét cạn khóa Miền giá trị khóa đủ lớn để việc vét cạn khóa là bất khả thi. 2.3 Mã hóa thay thế đơn bảng (Monoalphabetic Substitution Cipher) Xét lại phương pháp Ceasar với k=3: Chữ ban đầu: 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 Chữ thay thế: 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 Phương pháp đơn bảng tổng quát hóa phương pháp Ceasar bằng cách dòng mã hóa không phải là một dịch chuyển k vị trí của các chữ cái A, B, C, nữa mà là một hoán vị của 26 chữ cái này. Lúc này mỗi hoán vị được xem như là một khóa. Giả sử có hoán vị sau: Chữ ban đầu: 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 Khóa : Z P B Y J R S K F L X Q N W V D H M G U T O I A E C Như vậy bản rõ meet me after the toga party được mã hóa thành: NJJU NJ ZRUJM UKJ UVSZ DZMUE Quá trình giải mã được tiến hành ngược lại để cho ra bản rõ ban đầu. Việc mã hóa được tiến hành bằng cách thay thế một chữ cái trong bản rõ thành một chữ cái trong bản mã, nên phương pháp này được gọi là phương pháp thay thế. Số lượng hoán vị của 26 chữ cái là 26!, đây cũng chính là số lượng khóa của phương pháp này. Vì 26! là một con số khá lớn nên việc tấn công phá mã vét cạn khóa là bất khả thi (6400 thiên niên kỷ với tốc độ thử khóa là 109 khóa/giây). Vì vậy mã hóa đơn bảng đã được xem là một phương pháp mã hóa an toàn trong suốt 1000 năm sau công nguyên. Tuy nhiên vào thế kỷ thứ 9, một nhà hiền triết người Ả Rập tên là Al-Kindi đã phát hiện ra một phương pháp phá mã khả thi khác. Phương pháp phá mã này dựa trên nhận xét sau: Trong ngôn ngữ tiếng Anh, tần suất sử dụng của các chữ cái không đều nhau, chữ E được sử dụng nhiều nhất, còn các chữ ít được sử dụng thường là Z, Q, J. Tương tự như vậy 17
đối với cụm 2 chữ cái (digram), cụm chữ TH được sử dụng nhiều nhất. Bảng sau thống kê tần suất sử dụng của các chữ cái, cụm 2 chữ, cụm 3 chữ (trigram) trong tiếng Anh: Chữ cái (%) Cụm 2 chữ (%) Cụm 3 chữ (%) Từ (%) E 13.05 TH 3.16 THE 4.72 THE 6.42 T 9.02 IN 1.54 ING 1.42 OF 4.02 O 8.21 ER 1.33 AND 1.13 AND 3.15 A 7.81 RE 1.30 ION 1.00 TO 2.36 N 7.28 AN 1.08 ENT 0.98 A 2.09 I 6.77 HE 1.08 FOR 0.76 IN 1.77 R 6.64 AR 1.02 TIO 0.75 THAT 1.25 S 6.46 EN 1.02 ERE 0.69 IS 1.03 H 5.85 TI 1.02 HER 0.68 I 0.94 D 4.11 TE 0.98 ATE 0.66 IT 0.93 L 3.60 AT 0.88 VER 0.63 FOR 0.77 C 2.93 ON 0.84 TER 0.62 AS 0.76 F 2.88 HA 0.84 THA 0.62 WITH 0.76 U 2.77 OU 0.72 ATI 0.59 WAS 0.72 M 2.62 IT 0.71 HAT 0.55 HIS 0.71 P 2.15 ES 0.69 ERS 0.54 HE 0.71 Y 1.51 ST 0.68 HIS 0.52 BE 0.63 W 1.49 OR 0.68 RES 0.50 NOT 0.61 G 1.39 NT 0.67 ILL 0.47 BY 0.57 B 1.28 HI 0.66 ARE 0.46 BUT 0.56 V 1.00 EA 0.64 CON 0.45 HAVE 0.55 K 0.42 VE 0.64 NCE 0.45 YOU 0.55 X 0.30 CO 0.59 ALL 0.44 WHICH 0.53 J 0.23 DE 0.55 EVE 0.44 ARE 0.50 Q 0.14 RA 0.55 ITH 0.44 ON 0.47 Z 0.09 RO 0.55 TED 0.44 OR 0.45 Bảng 2-2. Bảng liệt kê tần suất chữ cái tiếng Anh Phương pháp mã hóa đơn bảng ánh xạ một chữ cái trong bản rõ thành một chữ cái khác trong bản mã. Do đó các chữ cái trong bản mã cũng sẽ tuân theo luật phân bố tần suất trên. Nếu chữ E được thay bằng chữ K thì tần suất xuất hiện của chữ K trong bản mã là 13.05%. Đây chính là cơ sở để thực hiện phá mã. Xét bản mã sau: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPPDPTGUDTMOHMQ Số lần xuất hiện của các chữ cái là: A 2 F 3 K 0 P 17 U 9 B 2 G 3 L 0 Q 3 V 5 C 0 H 6 M 7 R 0 W 4 D 6 I 1 N 0 S 10 X 5 E 6 J 0 O 9 T 4 Y 2 18
Z 13 Số lần xuất hiện của các digram (xuất hiện từ 2 lần trở lên) là: DT 2 HZ 2 PE 2 TS 2 XU 2 DZ 2 MO 2 PO 3 UD 2 ZO 2 EP 3 OH 2 PP 2 UZ 3 ZS 2 FP 3 OP 3 SX 3 VU 2 ZU 2 HM 2 PD 3 SZ 2 WS 2 ZW 3 Do đó ta có thể đoán P là mã hóa của e, Z là mã hóa của t. Vì TH có tần suất cao nhất trong các digram nên trong 4 digram ZO, ZS, ZU, ZW có thể đoán ZW là th. Chú ý rằng trong dòng thứ nhất có cụm ZWSZ, nếu giả thiết rằng 4 chữ trên thuộc một từ thì từ đó có dạng th_t, từ đó có thể kết luận rằng S là mã hóa của a (vì từ THAT có tần suất xuất hiện cao). Như vậy đến bước này, ta đã phá mã được như sau: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a a VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th t a EPYEPOPDZSZUFPOMBZWPPDPTGUDTMOHMQ e e e tat e thee e Cứ tiếp tục như vậy, dĩ nhiên việc thử không phải lúc nào cũng suôn sẻ, có những lúc phải thử và sai nhiều lần. Cuối cùng ta có được bản giải mã sau khi đã tách từ như sau: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the enemy in moscow Như vậy việc phá mã dựa trên tần suất chữ cái tốn thời gian ít hơn nhiều so với con số 6400 thiên niên kỷ. Lý do là ứng một chữ cái trong bản gốc thì cũng là một chữ cái trong bản mã nên vẫn bảo toàn quy tắc phân bố tần suất của các chữ cái. Để khắc phục điểm yếu này, có hai phương pháp. Phương pháp thứ nhất là mã hóa nhiều chữ cái cùng lúc. Phương pháp thứ hai là làm sao để một chữ cái trong bản rõ thì có tương ứng nhiều chữ cái khác nhau trong bản mã. Hai phương án trên sẽ lần lượt được trình bày trong phần tiếp theo. 2.4 Mã hóa thay thế đa ký tự 2.4.1 Mã Playfair Mã hóa Playfair xem hai ký tự đứng sát nhau là một đơn vị mã hóa, hai ký tự này được thay thế cùng lúc bằng hai ký tự khác. Playfair dùng một ma trận 5x5 các ký tự như sau: 19
M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z Trong bảng trên, khóa là từ MONARCHY được điền vào các dòng đầu của bảng, các chữ cái còn lại được điền tiếp theo. Riêng hai chữ I, J được điền vào cùng một ô vì trong tiếng Anh, ít khi nhầm lẫn giữa chữ I và chữ J. Ví dụ, nếu gặp đoạn ký tự CL_MATE, ta sẽ biết đó là từ CLIMATE chứ không phải là từ CLJMATE. Trước khi mã hóa, bản rõ được tách ra thành các cặp ký tự. Nếu hai ký tự trong một cặp giống nhau thì sẽ được tách bằng chữ X (trong tiếng Anh ít khi có 2 ký tự X sát nhau). Ví dụ: từ balloon được tách thành ba lx lo on . Việc mã hóa từng cặp được thực hiện theo quy tắc: . Nếu hai ký tự trong cặp thuộc cùng một hàng, thì được thay bằng hai ký tự tiếp theo trong hàng. Nếu đến cuối hàng thì quay về đầu hàng. Ví dụ cặp ar được mã hóa thành RM. . Nếu hai ký tự trong cặp thuộc cùng một cột, thì được thay bằng hai ký tự tiếp theo trong cột. Nếu đến cuối cột thì quay về đầu cột. Ví dụ cặp ov được mã hóa thành HO. . Trong các trường hợp còn lại, hai ký tự được mã hóa sẽ tạo thành đường chéo của một hình chữ nhật và được thay bằng 2 ký tự trên đường chéo kia. Ví dụ: hs trở thành BP (B cùng dòng với H và P cùng dòng với S); ea trở thành IM (hoặc JM) Như vậy nếu chỉ xét trên 26 chữ cái thì mã khóa Playfair có 26x26=676 cặp chữ cái, do đó các cặp chữ cái này ít bị chênh lệch về tần suất hơn so với sự chênh lệnh tần suất của từng chữ cái. Ngoài ra số lượng các cặp chữ cái nhiều hơn cũng làm cho việc phá mã tần suất khó khăn hơn. Đây chính là lý do mà người ta tin rằng mã hóa Playfair không thể bị phá và được quân đội Anh sử dụng trong chiến tranh thế giới lần thứ nhất. 2.4.2 Mã Hill Trong mã Hill, mỗi chữ cái được gán cho một con số nguyên từ 0 đến 25: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Mã Hill thực hiện mã hóa một lần m ký tự bản rõ (ký hiệu p1, p2, ,pm), thay thế thành m ký tự trong bản mã (ký hiệu c1, c2, ,cm). Việc thay thế này được thực hiện bằng m phương trình tuyến tính. Giả sử m = 3, chúng ta minh họa m phương trình đó như sau: 26 26 26 20
Ba phương trình trên có thể biểu diễn thành vector và phép nhân ma trận như sau: c1 k11 k12 k13 p1 c2 = k21 k22 k23 p2 mod 26 c3 k31 k32 k33 p3 Hay: C = KP mod 26 với P và C là vector đại diện cho bản rõ và bản mã, còn K là ma trận dùng làm khóa. Xét ví dụ bản rõ là paymoremoney cùng với khóa K là 17 17 5 K = 21 18 21 2 2 19 Ba chữ cái đầu tiên của bản rõ tương ứng với vector (15, 0, 24) . Vậy 17 17 5 5 11 21 18 21 0 mod 26 = 13 = LNS 18 2 2 19 24 Thực hiện tương tự ta có bản mã đầy đủ là LNSHDLEWMTRW Để giải mã chúng ta cần sử dụng ma trận nghịch đảo của K là K-1, tức là K-1K mod 26 = I là ma trận đơn vị (không phải mọi ma trận K đều tồn tại ma trận nghịch đảo, tuy nhiên nếu tồn tại thì ta có thể tìm được ma trận đơn vị bằng cách tính hạng det của ma trận) Ví dụ ma trận nghịch đảo của ma trận trên là: 4 9 15 K-1 = 15 17 6 24 0 17 Vì : 4 9 15 17 17 5 443 442 442 1 0 0 15 17 6 21 18 21 = 858 495 780 mod 26 = 0 1 0 24 0 17 2 2 19 494 52 365 0 0 1 -1 -1 Khi đó bảng giải mã là: K C mod 26 = K KP mod 26 = P Có thể thấy mã hóa Hill ẩn giấu các thông tin về tần suất nhiều hơn mã hóa Playfair do có thể mã hóa 3 hoặc nhiều hơn nữa các ký tự cùng lúc. 2.5 Mã hóa thay thế đa bảng (Polyalphabetic Substitution Cipher) Với sự phát hiện ra quy luật phân bố tần suất, các nhà phá mã đang tạm thời chiếm ưu thế trong cuộc chiến mã hóa-phá mã. Cho đến thế kỷ thứ 15, một nhà ngoại giao người Pháp tên là Vigenere đã tìm ra phương án mã hóa thay thế đa bảng. Phương pháp Vigenere dựa trên bảng sau đây: 21
key 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 A 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 B 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 A C C 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 D 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 E 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 D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z 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 Bảng 2-3. Bảng mã Vigenere Dòng thứ k của bảng là một mã hóa Ceasar k-1 vị trí. Ví dụ, dòng thứ 4, ứng với từ khóa D là mã hóa Ceasar 3 vị trí. (Trong trường hợp tổng quát, mỗi dòng của bảng Vigenere không phải là một mã hóa Ceasar nữa mà là một mã hóa đơn bảng, do đó có tên gọi là mã hóa đa bảng). Để mã hóa một bản tin thì cần có một khóa có chiều dài bằng chiều dài bản tin. Thường thì khóa là một cụm từ nào đó và được viết lặp lại cho đến khi có chiều dài bằng chiều dài bản tin. Ví dụ với bản tin là „We are discovered, save yourself‟ và khóa là từ DECEPTIVE, chúng ta mã hóa như sau: plaintext: wearediscoveredsaveyourself key: DECEPTIVEDECEPTIVEDECEPTIVE ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ Trong ví dụ trên, ứng với với chữ w trong bản rõ là chữ D trong khóa, nên dòng mã hóa thứ 4 ứng với khóa D trong bảng Vigenere được chọn. Do đó chữ w được mã hóa thành chữ Z. Tương tự như vậy cho các chữ còn lại. Trong ví dụ trên, các chữ e trong bản rõ được mã hóa tương ứng thành I, T, G, T, H, M trong bản mã. Do đó phương pháp phá mã dựa trên thống kê tần suất chữ cái là không 22
thực hiện được. Trong 3 thế kỷ sau đó mã hóa Vigenere được xem là mã hóa không thể bị phá và được biết dưới cái tên “le chipffre indechiffrable” (mật mã không thể phá nổi). Các nhà mã hóa lại chiếm ưu thế trở lại so với người phá mã. Đến thế kỷ 19, nhà khoa học người Anh Charles Barbage, đã tìm ra cách phá mã Vigenere. Việc phá mã bằng cách thống kê sự lặp lại của các cụm từ để phỏng đoán chiều dài của khóa, trong ví dụ trên cụm từ VTW được lặp lại cách nhau 9 vị trí nên có thể đoán chiều dài của khóa là 9. Và từ đó có thể tách bản mã thành 9 phần, phần thứ nhất gồm các chữ 1, 10, 19, 28, phần thứ hai gồm các chữ 2, 11, 20, 29 .cho đến phần thứ chín. Mỗi phần coi như được mã hóa bằng phương pháp mã hóa đơn bảng. Từ đó áp dụng phương pháp phá mã dựa trên tần suất chữ cái cho từng phần một. Cuối cùng ráp lại sẽ tìm ra được bản rõ. 2.6 One-Time Pad Có thể thấy rằng điểm yếu của mã hóa đa bảng là do sự lặp lại các từ trong khóa, ví dụ từ DECEPTIVE được lặp đi lặp lại nhiều lần. Điều này làm cho vẫn tồn tại một mối liên quan giữa bản rõ và bản mã, ví dụ cụm từ red trong bản rõ được lặp lại thì cụm từ VTW cũng được lặp lại trong bản mã. Người phá mã tận dụng mối liên quan này để thực hiện phá mã. Do đó vấn đề ở đây là làm sao để giữa bản rõ và bản mã thật sự ngẫu nhiên, không tồn tại mối quan hệ nào. Để giải quyết vấn đề này, Joseph Mauborgne, giám đốc viện nghiên cứu mật mã của quân đội Mỹ, vào cuối cuộc chiến tranh thế giới lần thứ nhất, đã đề xuất phương án là dùng khóa ngẫu nhiên. Khóa ngẫu nhiên có chiều dài bằng chiều dài của bản rõ, mỗi khóa chỉ sử dụng một lần. Ví dụ mã hóa bản tin „wearediscoveredsaveyourself‟ Bản tin P: wearediscoveredsaveyourself Khóa K1: FHWYKLVMKVKXCVKDJSFSAPXZCVP Bản mã C: BLWPOODEMJFBTZNVJNJQOJORGGU Nếu ta dùng khóa K1 để giải mã thì sẽ có được lại bản tin P „wearediscoveredsaveyourself’. Tuy nhiên xét hai trường hợp giải mã bản mã trên với 2 khóa khác như sau: Trường hợp 1: Bản mã C: BLWPOODEMJFBTZNVJNJQOJORGGU Khóa K2: IESRLKBWJFCIFZUCJLZXAXAAPSY Bản giải mã: theydecidedtoattacktomorrow (they decided to attack tomorrow) Trường hợp 2: Bản mã C: BLWPOODEMJFBTZNVJNJQOJORGGU Khóa K3: FHAHDDRAIQFIASJGJWQSVVBJAZB Bản giải mã: wewillmeetatthepartytonight (we will meet at the party tonight) Trong cả hai trường hợp trên thì bản giải mã đều có ý nghĩa. Điều này có nghĩa là nếu người phá mã thực hiện phá mã vét cạn thì sẽ tìm được nhiều khóa ứng với nhiều bản 23
tin có ý nghĩa, do đó sẽ không biết được bản tin nào là bản rõ. Điều này chứng minh phương pháp One-Time Pad là phương pháp mã hóa an toàn tuyệt đối, và được xem là ly thánh của khoa mật mã cổ điển. Một điều cần chú ý là để phương pháp One-Time Pad là an toàn tuyệt đối thì mỗi khóa chỉ được sử dụng một lần. Nếu một khóa được sử dụng nhiều lần thì cũng không khác gì việc lặp lại một từ trong khóa (ví dụ khóa có từ DECEPTIVE được lặp lại). Ngoài ra các khóa phải thật sự ngẫu nhiên với nhau. Nếu các điều này bị vi phạm thì sẽ có một mối liên hệ giữa bản rõ và bản mã, mà người phá mã sẽ tận dụng mối quan hệ này. Tuy nhiên, phương pháp One-Time Pad không có ý nghĩa sử dụng thực tế. Vì chiều dài khóa bằng chiều dài bản tin, mỗi khóa chỉ sử dụng một lần, nên thay vì truyền khóa trên kênh an toàn thì có thể truyền trực tiếp bản rõ mà không cần quan tâm đến vấn đề mã hóa. Vì vậy sau chiến tranh thế giới thứ nhất, người ta vẫn chưa thể tìm ra loại mật mã nào khác mà không bị phá mã. Mọi cố gắng vẫn là tìm cách thực hiện một mã thay thế đa bảng dùng một khóa dài, ít lập lại, để hạn chế phá mã. Máy ENIGMA được quân đội Đức sử dụng trong chiến tranh thế giới lần 2 là một máy như vậy. Sử dụng máy ENIGMA, Đức đã chiếm ưu thế trong giai đoạn đầu của cuộc chiến. Tuy nhiên trong giai đoạn sau, các nhà phá mã người Ba Lan và Anh (trong đó có Alan Turing, người phá minh ra máy tính có thể lập trình được) đã tìm ra cách phá mã máy ENIGMA. Việc phá mã thực hiện được dựa vào một số điểm yếu trong khâu phân phối khóa của quân Đức. Điều này đóng vai trò quan trọng vào chiến thắng của quân đồng minh trong cuộc chiến. Hình 2-2. Hình minh họa cấu trúc máy ENIGMA, gõ chữ vào bàn phím, bản mã hiện ra ở các bóng đèn bên trên. (nguồn: Wikipedia) 2.7 Mã hoán vị (Permutation Cipher) Các phương pháp mã hóa đã trình bày cho đến thời điểm này sử dụng phương thức thay một chữ cái trong bản rõ bằng một chữ cái khác trong bản mã (phương pháp thay thế). 24
Một cách thực hiện khác là xáo trộn thứ tự của các chữ cái trong bản rõ. Do thứ tự của các chữ cái bị mất đi nên người đọc không thể hiểu được ý nghĩa của bản tin dù các chữ đó không thay đổi. Một cách thực hiện đơn giản là ghi bản rõ theo từng hàng, sau đó kết xuất bản mã dựa trên các cột. Ví dụ bản rõ „attackpostponeduntilthisnoon‟ được viết lại thành bảng 4 x 7 như sau: a t t a c k p o s t p o n e d u n t i l t h i s n o o n khi kết xuất theo từng cột thì có được bản mã: „AODHTSUITTNSAPTNCOIOKNLOPETN’ Một cơ chế phức tạp hơn là chúng ta có thể hoán vị các cột trước khi kết xuất bản mã. Ví dụ chọn một khóa là MONARCH, ta có thể hoán vị các cột: M O N A R C H A C H M N O R a t t a c k p a k p a t t c o s t p o n e p n e o t s o d u n t i l t t l t d n u i h i s n o o n n o n h s i o và có được bản mã: „APTNKNLOPETNAODHTTNSTSUICOIO‟. Việc giải mã được tiến hành theo thứ tự ngược lại. Để an toàn hơn nữa, có thể áp dụng phương pháp hoán vị 2 lần (double transposition), tức sau khi hoán vị lần 1, ta lại lấy kết quả đó hoán vị thêm một lần nữa: M O N A R C H A C H M N O R a p t n k n l n n l a t p k o p e t n a o t a o o e p n d h t t n s t t s t d t h n s u i c o i o c i o s i u o Và cuối cùng bản mã là „NTTCNASILOTOAODSTETIPPHUKNNO‟ Người ta đã đánh giá rằng phá mã phương pháp hoán vị 2 lần không phải là chuyện dễ dàng vì rất khó đoán ra được quy luật hoán vị. Ngoài ra không thể áp dụng được phương pháp phân tích tần suất chữ cái giống như phương pháp thay thế vì tần suất chữ cái của bản rõ và bản mã là giống nhau. 2.8 Tổng kết Các phương pháp mã hóa cổ điển thường dựa trên hai phương thức. Cách thứ nhất là dùng phương thức thay thế một chữ cái trong bản rõ thành một chữ cái khác trong bản mã (substitution). Các mã hóa dùng phương thức này là mã hóa Ceasar, mã hóa thay thế đơn bảng, đa bảng, one-time pad. Cách thứ hai là dùng phương thức hoán vị để thay đổi thứ tự 25
ban đầu của các chữ cái trong bản rõ (permutation). Hai phương thức này cũng đóng vai trò quan trọng trong mã hóa đối xứng hiện đại được trình bày trong chương tiếp theo. Tron chương này chúng ta đã xem xét một số phương thức phá mã. Mục tiêu của việc phá mã là từ bản mã đi tìm bản rõ, hoặc khóa, hoặc cả hai. Chúng ta giả định rằng người phá mã biết rõ thuật toán mã hóa và giải mã (luật Kerchoff). Việc phá mã sẽ có 3 tình huống sau: 1) Chỉ biết bản mã (ciphertext–only): đây là trường hợp gây khó khăn nhất cho người phá mã. Các trường hợp phá mã được trình bày trong chương này thuộc dạng ciphertext only. E Người phá mã chỉ P1 C1 biết C1, C2, C3 cần P2 C2 tìm ra P1, P2, P3 P3 C3 2) Biết một số cặp bản rõ – bản mã (known–plaintext): trong trường hợp này, người phá mã có được một vài cặp bản rõ và bản mã tương ứng. E Người phá mã biết C1, C2, P1 C1 C3 và biết bản rõ tương P2 C2 ứng với C1 là P1. Cần tìm ra P2, P3. P3 C3 Việc biết được một vài cặp bản rõ – bản mã làm cho người phá mã dễ dàng hơn trong việc tìm khóa. Ví dụ, đối với mã hóa Vigenere, nếu người phá mã chỉ cần biết một cặp bản rõ – bản mã thì sẽ dễ dàng suy ra được khóa, từ đó giải các bản mã khác mà cũng được mã hóa bằng khóa này. Ví dụ: nếu biết bản mã : ZICVTWQNGRZGVTWAVZHCQYGLMGJ có bản rõ tương ứng là wearediscoveredsaveyourself, người phá mã có thể tra ngược bản Vigenere và tìm được khóa DECEPTIVE để giải các bản mã khác. 3) Một số cặp bản rõ – bản được lựa chọn (choosen–plaintext): trong trường hợp này, người phá mã có khả năng tự lựa một số bản rõ và quan sát được bản mã tương ứng. Ví dụ khi bạn đi ăn trưa và quên khóa máy, người phá mã có thể dùng chương trình mã hóa của bạn để thực hiện mã hóa một số bản tin chọn trước và có được bản mã tương ứng (dù không biết khóa). Như vậy đối với trường hợp 2 và 3 thì người phá mã sẽ dễ dàng hơn trong việc phá mã so với trường hợp 1. Điều này đặt ra thách thức cho các nhà nghiên cứu là phải tìm ra các thuật toán mã hóa sao cho không thể bị phá mã không chỉ trong trường hợp 1 mà còn ngay cả trong trường hợp 2 và 3. Đó là một số thuật toán mà chúng ta sẽ tìm hiểu trong chương mã hóa đối xứng hiện đại. 26
2.9 Câu hỏi ôn tập 1) Tại sao khi gửi bản mã trên kênh truyền thì không sợ bị lộ thông tin? 2) Khóa là gì? Tại sao cần giữ bí mật khóa chỉ có người gửi và người nhận biết? 3) Tại sao lại gửi khóa qua kênh an toàn mà không gửi trực tiếp bản rõ trên kênh an toàn? 4) Phá mã khác giải mã ở điểm nào? 5) Phá mã theo hình thức vét cạn khóa thực hiện như thế nào? Cần làm gì để chống lại hình thức phá mã theo vét cạn khóa? 6) Các phương pháp Ceasar, mã hóa đơn bảng, đa bảng, one-time pad dùng nguyên tắc gì để mã hóa? 7) Phương pháp hoán vị dùng nguyên tắc gì để mã hóa? 8) Tại sao phương pháp mã hóa đơn bảng có thể bị tấn công phá mã dùng thống kê tần suất? 9) Hãy cho biết ý nghĩa của mã hóa Vigenere. 10) Phân biệt điểm khác nhau giữa ba trường hợp phá mã: ciphertext-only, known- plaintext, chosen-plaintext. Trong hai trường hợp known-plaintext và chosen-plaintext, người phá mã có lợi thế gì so với trường hợp ciphertext-only? 2.10 Bài Tập 1. Giải mã bản mã sau, giả sử mã hóa Ceasar được sử dụng để mã hóa với k=3: IRXUVFRUHDQGVHYHQBHDUVDJR 2. Nếu một máy tính có thể thử 240 khóa /giây, tính thời gian phá mã bằng phương pháp vét cạn khóa nếu kích thước khóa là 128 bít (đáp án tính theo đơn vị năm). 3. Mã hóa bản rõ sau: „enemy coming‟, dùng phương pháp mã hóa thay thế đơn bảng với khóa hoán vị K là: IAUTMOCSNREBDLHVWYFPZJXKGQ 4. Mã hóa từ ‘explanation’ bằng phương pháp Vigenere, từ khóa là LEG. 5. Mã hóa thông điệp sau bằng phương pháp hoán vị: we are all together biết khóa 24153 6. Phá mã bản mã sau, giả sử mã hóa Ceasar được sử dụng: CSYEVIXIVQMREXIH 7. Phá mã bản mã sau (tiếng Anh), biết phương pháp mã hóa sử dụng là phương pháp thay thế đơn bảng: GBSXUCGSZQGKGSQPKQKGLSKASPCGBGBKGUKGCEUKUZKGGBSQEICA CGKGCEUERWKLKUPKQQGCIICUAEUVSHQKGCEUPCGBCGQOEVSHUNSU GKUZCGQSNLSHEHIEEDCUOGEPKHZGBSNKCUGSUKUASERLSKASCUGB SLKACRCACUZSSZEUSBEXHKRGSHWKLKUSQSKCHQTXKZHEUQBKZAEN NSUASZFENFCUOCUEKBXGBSWKLKUSQSKNFKQQKZEHGEGBSXUCGSZQ GKGSQKUZBCQAEIISKOXSZSICVSHSZGEGBSQSAHSGKHMERQGKGSKR EHNKIHSLIMGEKHSASUGKNSHCAKUNSQQKOSPBCISGBCQHSLIMQGKG SZGBKGCGQSSNSZXQSISQQGEAEUGCUXSGBSSJCQGCUOZCLIENKGCA USOEGCKGCEUQCGAEUGKCUSZUEGBHSKGEHBCUGERPKHEHKHNSZKGGKAD (Cần viết chương trình hỗ trợ phá mã, xem bài tập thực hành số 3) 27
8. Tương tự bài tập 7 cho bản mã sau (tiếng Anh): PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQ JVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQU FEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFT DPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZ BOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFL QHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFA 9. Xét phương pháp Vigenere. Giả sử biết bản mã „PVRLHFMJCRNFKKW‟có bản rõ tương ứng là „networksecurity‟. Hãy tìm khóa K. 10. Xét bản mã được mã hóa bằng phương pháp One-Time Pad như sau: KITLKE Nếu bản rõ là „thrill‟ thì khóa là gì? Nếu bản rõ là „tiller‟ thì khóa là gì? 11. Một trường hợp tổng quát của mã hóa Ceasar là mã Affine, trong đó ký tự p được mã hóa thành ký tự C theo công thức: C = E(p, [a, b]) = (ap + b) mod 26 Một yêu cầu của thuật toán mã hóa là tính đơn ánh, tức nếu p≠q thì E(p) ≠E(q). Mã Affine không phải là đơn ánh với mọi a. Ví dụ, với a=2, b=3 thì E(0) = E(13) = 3. a) Có điều kiện gì đặt ra cho b hay không? Tại sao? b) Xác định những giá trị của a làm cho mã Affine không đơn ánh. 2.11 Bài Tập Thực Hành 1. Viết chương trình mã hóa và giải mã một file văn bản ASCII trên máy tính bằng phương pháp mã hóa Ceasar. 2. Viết chương trình mã hóa và giải mã một file văn bản ASCII trên máy tính bằng phương pháp mã hóa Playfair. 3. Viết chương trình mã hóa và giải mã một file văn bản ASCII trên máy tính bằng phương pháp mã hóa Vigenere. 4. Viết chương trình hỗ trợ phá mã thay thế đơn bảng (bài tập 7 và 8), chương trình sẽ làm một số thao tác như thống kê tần suất các chữ cái, các digram, thực hiện phép thay thế 28
CHƢƠNG 3. MÃ HÓA ĐỐI XỨNG HIỆN ĐẠI Đối tượng của các phương pháp mã hóa cổ điển là các bản tin ngôn ngữ, một đơn vị mã hóa là các chữ cái để áp dụng phương thức thay thế hay phương thức hoán vị. Cùng với sự phát triển của máy tính, thông tin ngày một trở nên đa dạng, một bản tin bây giờ không chỉ đơn giản là bản tin gồm các chữ cái, mà có thể gồm cả các thông tin về định dạng văn bản như tài liệu HTML Ngoài ra bản tin có thế xuất hiện dưới các loại hình khác như hình ảnh, video, âm thanh Tất các bản tin đó đều được biểu diễn trên máy vi tính dưới dạng một dãy các số nhị phân. Trong máy tính các chữ cái được biểu diễn bằng mã ASCII. Bản tin: attack Mã ASCII: 97 116 116 97 99 107 Biểu diễn nhị phân: 01100001 01110100 01110100 01100001 01100011 01101011 Và cũng tương tự như bản tin ngôn ngữ, trong bản tin nhị phân cũng tồn tại một số đặc tính thống kê nào đó mà người phá mã có thể tận dụng để phá bản mã, dù rằng bản mã bây giờ tồn tại dưới dạng nhị phân. Mã hóa hiện đại quan tâm đến vấn đề chống phá mã trong các trường hợp biết trước bản rõ (known-plaintext), hay bản rõ được lựa chọn (chosen-plaintext). Để minh họa cách thức thực hiện của mã hóa đối xứng hiện đại, chúng ta sử dụng bản rõ là các chữ cái của một ngôn ngữ gồm có 8 chữ cái A, B, C, D, E, F, G, H trong đó mỗi chữ cái được biểu diễn bằng 3 bít. Chữ cái Nhị phân A 000 B 001 C 010 D 011 E 100 F 101 G 110 H 111 Như vậy nếu có bản rõ là ’head’ thì biểu diễn nhị phân tương ứng là: 111100000011 Giả sử dùng một khóa K gồm 4 bít 0101 để mã hóa bản rõ trên bằng phép XOR : bản rõ: 1111 0000 0011 (head) khóa: 0101 0101 0101 bản mã: 1010 0101 0110 (FBCG) Trong phép mã hóa trên, đơn vị mã hóa không phải là một chữ cái mà là một khối 4 bít. Để giải mã, lấy bản mã XOR một lần nữa với khóa thì có lại bản rõ ban đầu. Tuy nhiên, mã hóa bằng phép XOR như trên thì khá đơn giản ở hai điểm: Khóa được lặp lại, điều này bộc lộ điểm yếu giống như mã hóa Vigenere. Để khắc phục điều này, người ta dùng một bộ sinh số ngẫu nhiên để tạo khóa dài, 30
giả lập mã hóa One-Time pad. Đây là cơ sở thực hiện của mã dòng (stream cipher). Một khối được mã hóa bằng phép XOR với khóa. Điều này không an toàn vì chỉ cần biết một cặp khối bản rõ - bản mã (vd: 1111 và 1010), người phá mã dễ dàng tính được khóa. Để khắc phục điều này, người ta tìm ra các phép mã hóa phức tạp hơn phép XOR, và đây là cơ sở ra đời của mã khối (block cipher). 3.1 Mã dòng (Stream Cipher) Mã dòng có các đặc tính sau: Kích thước một đơn vị mã hóa: gồm k bít. Bản rõ được chia thành các đơn vị mã hóa: Một bộ sinh dãy số ngẫu nhiên: dùng một khóa K ban đầu để sinh ra các số ngẫu nhiên có kích thước bằng kích thước đơn vị mã hóa: Mỗi số ngẫu nhiên được XOR với đơn vị mã hóa của bản rõ để có được bản mã. Quá trình giải mã được thực hiện ngược lại, bản mã C được XOR với dãy số ngẫu nhiên S để cho ra lại bản rõ ban đầu: Trong ví dụ trên đơn vị mã hóa có chiều dài k = 4 bít, n = 3: 1111 11 1 1 1 1 1 1 11 Ví dụ này không phải là mã dòng vì s0, s1, s2 lặp lại khóa K. Về phương diện khóa, ví dụ này giống mã Vigenere hơn. Đối với mã dòng, các số si được sinh ra phải đảm bảo một độ ngẫu nhiên nào đó (chu kỳ tuần hoàn dài): P p0 p1 pn-1 s0 s1 sn-1 C c c c 0 1 n-1 Hình 3-1. Mô hình mã dòng Như vậy có thể thấy mã hóa dòng tương tự như mã hóa Vigenere và mã hóa One- Time Pad. Điểm quan trọng nhất của các mã dòng là bộ sinh số ngẫu nhiên. Nếu chọn khóa có chiều dài ngắn như mã hóa Vigenere thì không bảo đảm an toàn, còn nếu chọn khóa có chiều dài bằng chiều dài bản tin như One-Time Pad thì lại không thực tế. Bộ sinh số của mã dòng cân bằng giữa hai điểm này, cho phép dùng một khóa ngắn nhưng dãy số sinh ra bảo đảm một độ ngẫu nhiên cần thiết như khóa của One-time Pad, dùng rằng không hoàn toàn thực sự ngẫu nhiên. 31
Phần tiếp theo trình bày hai phương pháp mã hóa dòng tiêu biểu là A5/1 và RC4. 3.1.1 A5/1 A5/1 được dùng trong mạng điện thoại GSM, để bảo mật dữ liệu trong quá trình liên lạc giữa máy điện thoại và trạm thu phát sóng vô tuyến. Đơn vị mã hóa của A5/1 là một bít. Bộ sinh số mỗi lần sẽ sinh ra hoặc bít 0 hoặc bít 1 để sử dụng trong phép XOR. Để đơn giản, trước tiên chúng ta sẽ xem xét một mô hình thu nhỏ của A5/1 gọi là TinyA5/1. 1) TinyA5/1 Cơ chế thực hiện của bộ sinh số TinyA5/1 là như sau: Bộ sinh số gồm 3 thanh ghi X, Y, Z. Thanh ghi X gồm 6 bit, ký hiệu là (x0, x1, , x5). Thanh ghi Y gồm 8 bit (y0, y1, , y7). Thanh ghi Z lưu 9 bit (z0, z1, , z8). Khóa K ban đầu có chiều dài 23 bít và lần lượt được phân bố vào các thanh ghi: K XYZ . Các thanh ghi X, Y, Z được biến đổi theo 3 quy tắc: 1) Quay X gồm các thao tác: 0 1 2 3 4 5 6 7 8 t = x2 x4 x5 X 1 0 0 1 0 1 xj = xj-1 với j = 5, 4, 3, 2, 1 x0 = t Ví dụ: giả sử X là 100101, dẫn đến t = 0 0 1 = 1, vậy sau khi quay giá trị của X là 110010. 2) Quay Y: tương tự như quay X, quay Y là như sau: t = y6 y7 Y 0 1 0 0 1 1 1 0 yj = yj-1 với j = 7, 6, 5, , 1 y0 = t 3) Quay Z: Z 1 0 0 1 1 0 0 0 0 t = z2 z7 z8 zj = zj-1 với j = 8, 7, 6, , 1 z0 = t Cho ba bit x, y, z, ta định nghĩa một hàm maj(x, y, z) là hàm “chiếm đa số”, nghĩa là nếu trong 3 bít x, y, z có từ hai bít 0 trở lên thì hàm trả về giá trị 0, nếu không hàm trả về giá trị 1. Tại bước sinh số thứ i, các phép tính sau được thực hiện: m = maj(x1, y3, z3) If x1 = m then thực hiện quay X If y3 = m then thực hiện quay Y If z3 = m then thực hiện quay Z Và bít được sinh ra là: si = x5 y7 z8 Bít si được XOR với bít thứ i trong bản rõ để có được bít thứ i trong bản mã theo quy tắc của mã dòng. Ví dụ: mã hóa bản rõ P=111 (chữ h) với khóa K là 100101. 01001110.100110000. 32
Ban đầu giá trị của các thanh ghi X, Y, Z là: X = 100101 Y = 01001110 Z = 100110000 Bước 0: x1= 0, y3=0, z3= 1 m = 0 quay X, quay Y X = 110010 Y = 10100111 s0= 0 1 0 = 1 Z = 100110000 Bước 1: x1= 1, y3=0, z3= 1 m = 1 quay X, quay Z X = 111001 Y = 10100111 s1= 1 1 0 = 0 Z = 010011000 Bước 2: x1= 1, y3=0, z3= 0 m = 0 quay Y, quay Z X = 111001 Y = 01010011 s2= 1 1 0 = 0 Z = 001001100 Vậy bản mã là C = 111 100 = 011 (chữ D) 2) A5/1 Về nguyên tắc bộ sinh số A5/1 hoạt động giống như TinyA5/1. Kích thước thanh ghi X, Y, Z lần lượt là 19, 22 và 23 bít. Các bước quay X, Y, Z cụ thể như sau: 1) Quay X: t = x13 x16 x17 x18 xj = xj-1 với j = 18, 17,16 , 1 x0 = t 2) Quay Y: t = y20 y21 yj = yj-1 với j = 21, 20, 19, , 1 y0 = t 3) Quay Z: t = z7 z20 z21 z22 zj = zj-1 với j = 22, 21, 20, , 1 z0 = t Hàm maj được tính trên 3 bít x8, y10, z10. Sau khi quay xong bít sinh ra là: si = x18 y21 z22. Toàn bộ quá trình sinh dãy số của A5/1 được minh họa qua hình bên dưới: 33
X 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 t si Y 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 t Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 t Hình 3-2. Mã dòng A5/1 Mã hóa A5/1 có thể được thực hiện dễ dàng bằng các thiết bị phần cứng, tốc độ nhanh. Do đó A5/1 đã từng được sử dụng để mã hóa các dữ liệu real-time như các dãy bít audio. Ngày nay A5/1 được sử dụng để mã hóa dữ liệu cuộc gọi trong mạng điện thoại GSM. 3.1.2 RC4 RC4 được dùng trong giao thức SSL (xem phần 7.3) để bảo mật dữ liệu trong quá trình truyền dữ liệu giữa Web Server và trình duyệt Web. Ngoài ra RC4 còn được sử dụng trong mã hóa WEP của mạng Wireless LAN. Để đơn giản, chúng ta cũng sẽ xem xét một mô hình thu nhỏ của RC4 gọi là TinyRC4. 1) TinyRC4 Khác với A5/1, đơn vị mã hóa của TinyRC4 là 3 bít. TinyRC4 dùng 2 mảng S và T mỗi mảng gồm 8 số nguyên 3 bít (từ 0 đến 7). Khóa là một dãy gồm N số nguyên 3 bít với N có thể lấy giá trị từ 1 đến 8. Bộ sinh số mỗi lần sinh ra 3 bít để sử dụng trong phép XOR. Quá trình sinh số của TinyRC4 gồm hai giai đoạn: a) Giai đoạn khởi tạo: /* Khoi tao day so S va T */ for i = 0 to 7 do S[i] = i; T[i] = K[i mod N]; next i /* Hoan vi day S */ j = 0; for i = 0 to 7 do j = (j + S[i] + T[i]) mod 8; Swap(S[i], S[j]); next i Trong giai đoạn này, trước tiên dãy S gồm các số nguyên 3 bít từ 0 đến 7 được sắp thứ tự tăng dần. Sau đó dựa trên các phần tử của khóa K, các phần tử của S được hoán vị lẫn nhau đến một mức độ ngẫu nhiên nào đó. Ví dụ: mã hóa bản rõ P = 001000110 (từ „bag‟) với khóa K gồm 3 số 2, 1, 3 (N=3) 34
- Khởi tạo S và T S 0 1 2 3 4 5 6 7 T 2 1 3 2 1 3 2 1 K - Hoán vị S i=0 T 2 1 3 2 1 3 2 1 S[i]+T[i]=2 j S 0 1 2 3 4 5 6 7 Swap(S[i], S[j]) i=1 T 2 1 3 2 1 3 2 1 S[i]+T[i]=2 j S 2 1 0 3 4 5 6 7 Swap(S[i], S[j]) i=2 T 2 1 3 2 1 3 2 1 S[i]+T[i]=3 j S 2 4 0 3 1 5 6 7 Swap(S[i], S[j]) Quá trình thực hiện đến khi i=7 và lúc đó dãy S là 6 0 7 1 2 3 5 4 b) Giai đoạn sinh số: i, j = 0; while (true) i = (i + 1) mod 8; j = (j + S[i]) mod 8; Swap (S[i], S[j]); t = (S[i] + S[j]) mod 8; k = S[t]; end while; Trong giai đoạn này, các phần tử của S tiếp tục được hoán vị. Tại mỗi bước sinh số, hai phần tử của dãy S được chọn để tính ra số k 3 bít là số được dùng để XOR với đơn vị mã hóa của bản rõ. Tiếp tục ví dụ trên, quá trình sinh số mã hóa bản rõ „bag‟ thực hiện như sau: 35
Bước 0: 1 i S[i] j S 6 0 7 1 2 3 5 4 s0 = 5 = 101[2] S[i]+S[j]=0+6 Bước 1: 1 i S[i] j S 0 6 7 1 2 3 5 4 s1 = 1 = 001[2] S[i]+S[j]=4+7 Bước 2: 1 i S[i] j S 0 6 4 1 2 3 5 7 s2 = 4 = 111[2] S[i]+S[j]=1+6 Vậy bản mã là C = 001.000.110 101.001.111 = 100.001.001 (từ EBB) 2) RC4 Cơ chế hoạt động của RC4 cũng giống như TinyRC4 với các đặc tính sau: - Đơn vị mã hóa của RC4 là một byte 8 bít. - Mảng S và T gồm 256 số nguyên 8 bít - Khóa K là một dãy gồm N số nguyên 8 bít với N có thể lấy giá trị từ 1 đến 256. - Bộ sinh số mỗi lần sinh ra một byte để sử dụng trong phép XOR. Hai giai đoạn của RC4 là: a) Giai đoạn khởi tạo: /* Khoi tao day S va T*/ for i = 0 to 255 do S[i] = i; T[i] = K[i mod N]; next i /* Hoan vi day S */ j = 0; for i = 0 to 255 do j = (j + S[i] + T[i]) mod 256; Swap(S[i], S[j]); next i 36
b) Giai đoạn sinh số: i, j = 0; while (true) i = (i + 1) mod 256; j = (j + S[i]) mod 256; Swap (S[i], S[j]); t = (S[i] + S[j]) mod 256; k = S[t]; end while; Quá trình sinh số của RC4 cũng sinh ra dãy số ngẫu nhiên, khó đoán trước, vì vậy RC4 đạt được mức độ an toàn cao theo tinh thần của mã hóa One-Time Pad. Mã hóa RC4 hoàn toàn được thực hiện trên các số nguyên một byte do đó tối ưu cho việc thiết lập bằng phần mềm và tốc độ thực hiện nhanh hơn so với mã khối. 3.2 Mã khối (Block Cipher) 3.2.1 Mã khối an toàn lý tưởng Phép toán XOR có một hạn chế là chỉ cần biết một cặp khối bản rõ và bản mã, người ta có thể dễ dàng suy ra được khóa và dùng khóa đó để giải các khối bản mã khác (known- plaintext attack). Xét lại ví dụ đầu chương: bản rõ: 1111 0000 0011 (head) khóa: 0101 0101 0101 bản mã: 1010 0101 0110 (FBCG) Nếu biết bản mã c0 = 1010 có bản rõ tương ứng là p0 = 1111, thì có thể dễ dàng suy ra khóa là 0101. Nói một cách tổng quát, nếu giữa bản rõ P và bản mã C có mối liên hệ toán học thì việc biết một số cặp bản rõ-bản mã giúp ta có thể tính được khóa K. (như trong trường hợp mã Hill) Do đó để chống phá mã trong trường hợp known-plaintext hay choosen-plaintext, chỉ có thể là làm cho P và C không có mối liên hệ toán học. Điều này chỉ có thể thực hiện được nếu ta lập một bản tra cứu ngẫu nhiên giữa bản rõ và bản mã. Ví dụ: Bản rõ Bản mã 0000 1110 0001 0100 0010 1101 0011 0001 0100 0010 0101 1111 0110 1011 0111 1000 1000 0011 1001 1010 1010 0110 1011 1100 1100 0101 1101 1001 1110 0000 1111 0111 37
Lúc này khóa là toàn bộ bảng trên. Người gởi cũng như người nhận phải biết toàn bộ bảng trên để mã hóa và giải mã. Đối với người phá mã, nếu biết một số cặp bản rõ - bản mã thì cũng chỉ biết được một phần của bảng tra cứu trên. Do đó không suy ra được bản rõ cho các bản mã còn lại. Hay nói cách khác, muốn phá mã thì phải biết được tất cả các cặp bản rõ và bản mã. Nếu chọn kích thước của khối là 64 bít thì số dòng của bảng khóa là 264, một con số rất lớn (và có khoảng 264! bảng khóa như vậy). Lúc này việc nắm tất cả các cặp bản rõ-bản mã của bảng khóa là điều không thể đối với người phá mã. Trường hợp này ta gọi là mã khối an toàn lý tưởng. Tuy nhiên, khi kích thước khối lớn thì số dòng của bảng khóa cũng lớn và gây trở ngại cho việc lưu trữ cũng như trao đổi khóa giữa người gởi và người nhận. Bảng khóa có 264 dòng mỗi dòng 64 bít do đó kích thước khóa sẽ là 64x 264= 270 ≈ 1021 bít. Do đó mã khối an toàn lý tưởng là không khả thi trong thực tế. 3.2.2 Mạng SPN Trong thực tế, người ta chỉ tìm cách để chỉ cần dùng một khóa có kích thước ngắn để giả lập một bảng tra cứu có độ an toàn xấp xỉ độ an toàn của mã khối lý tưởng. Cách thực hiện là kết hợp hai hay nhiều mã hóa đơn giản lại với nhau để tạo thành một mã hóa tổng (product cipher), trong đó mã hóa tổng an toàn hơn rất nhiều so với các mã hóa thành phần. Các mã hóa đơn giản thường là phép thay thế (substitution, S-box) và hoán vị (Permutation, P-box). Do đó người ta hay gọi mã hóa tổng là Substitution-Permutation Network (mạng SPN). Hình dưới minh họa một mạng SP. Bít đầu vào Bít đầu ra 0 0 1 S1 S4 1 2 2 S2 S5 P1 P2 P3 S3 S6 11 11 Việc kết hợp các S-box và P-box tạo ra hai tính chất quan trọng của mã hóa là tính khuếch tán (diffusion) và tính gây lẫn (confusion). Hai tính chất này do Claude Shannon giới thiệu vào năm 1946, và là cơ sở của tất cả các mã khối hiện nay. Tính khuếch tán: một bít của bản rõ tác động đến tất cả các bít của bản mã, hay nói cách khác, một bít của bản mã chịu tác động của tất cả các bít trong bản rõ. Việc làm như vậy nhằm làm giảm tối đa mối liên quan giữa bản rõ và bản mã, ngăn chặn việc suy ra lại khóa. Tính chất này có được dựa vào sử dụng P-box kết hợp S-box. Tính gây lẫn: làm phức tạp hóa mối liên quan giữa bản mã và khóa. Do đó cũng ngăn chặn việc suy ra lại khóa. Tính chất này có được dựa vào sử dụng S-box. 3.2.3 Mô hình mã Feistel Mô hình mã Feistel là một dạng tiếp cận khác so với mạng SP. Mô hình do Horst Feistel đề xuất, cũng là sự kết hợp các phép thay thế và hoán vị. Trong hệ mã Feistel, bản rõ sẽ được biến đổi qua một số vòng để cho ra bản mã cuối cùng: 38
K1 K2 K3 Kn-1 P C1 C2 Cn Trong đó bản rõ P và các bản mã Ci được chia thành nửa trái và nửa phải: P = (L0, R0) K1 Ci = (Li, Ri) i = 1, 2, n Quy tắc biến đổi các nửa trái phải này qua các vòng được thực hiện như sau: Li = Ri-1 Ri = Li-1 F(Ri-1, Ki) Ki là một khóa con cho vòng thứ i. Khóa con này được sinh ra từ khóa K ban đầu theo một thuật toán sinh khóa con (key schedule): K K1 K2 Kn F là một hàm mã hóa dùng chung cho tất cả các vòng. Hàm F đóng vai trò như là phép thay thế còn việc hoán đổi các nửa trái phải có vai trò hoán vị. Bản mã C được tính từ kết xuất của vòng cuối cùng: C = Cn = (Ln, Rn) Sơ đồ tính toán của hệ mã Feistel được thể hiện trong hình bên dưới: plaintext K L0 R0 F K1 L1 R1 Ln-1 Rn-1 F Kn Ln Rn ciphertext Hình 3-3. Mô hình mã khối Feistel Để giải mã quá trình được thực hiện qua các vòng theo thứ tự ngược lại: C Ln, Rn Ri-1= Li (theo mã hóa Li = Ri-1 ) Li-1 = Ri F(Ri-1, Ki) (theo mã hóa Ri = Li-1 F(Ri-1, Ki) ) 39
Và cuối cùng bản rõ là P = (L0, R0). Hệ mã Feistel có điểm quan trọng là việc chia các bản mã thành hai nửa trái phải giúp cho hàm F không cần khả nghịch (không cần có F-1). Mã hóa và giải mã đều dùng chiều thuận của hàm F. Hàm F và thuật toán sinh khóa con càng phức tạp thì càng khó phá mã. Ứng với các hàm F và thuật toán sinh khóa con khác nhau thì ta sẽ có các phương pháp mã hóa khác nhau, phần tiếp theo sẽ trình bày mã hóa DES, là một phương pháp mã hóa dựa trên nguyên tắc của hệ mã Feistel. 3.3 Mã TinyDES Vào năm 1973, khi lĩnh vực máy tính ngày càng phát triển, nhu cầu ứng dụng bảo mật vào các mục đích dân sự được đặt ra. Lúc này Cục tiêu chuẩn quốc gia Hoa Kỳ kêu gọi các công ty Mỹ thiết lập một chuẩn mã hóa quốc gia. Mã hóa Lucifer của công ty IBM được chọn và sau một vài sửa đổi của cơ quan an ninh Hoa Kỳ, mã hóa Lucifer đã trở thành mã tiêu chuẩn DES (Data Encryption Standard). Qua quá trình sử dụng mã DES đã chứng tỏ độ an toàn cao và được sử dụng rộng rãi. Tương tự như mã dòng A5/1 và RC4, chúng ta cũng sẽ xem xét một mô hình thu nhỏ của mã DES là TinyDES. Mã TinyDES có các tính chất sau: Là mã thuộc hệ mã Feistel gồm 3 vòng Kích thước của khối là 8 bít Kích thước khóa là 8 bít Mỗi vòng của TinyDES dùng khóa con có kích thước 6 bít được trích ra từ khóa chính. Hình dưới đây minh họa các vòng của mã TinyDES Bản rõ 8 bít Khóa 8 bít 6 8 Vòng 1 Nén khóa Dịch vòng trái 8 8 6 8 Vòng 2 Nén khóa Dịch vòng trái 8 8 6 8 Vòng 3 Nén khóa Dịch vòng trái 8 Bản mã 8 bít Hình 3-4. Các vòng Feistel của mã TinyDES Sơ đồ mã TinyDES trên gồm hai phần, phần thứ nhất là các vòng Feistel, phần thứ hai là thuật toán sinh khóa con. Chúng ta sẽ lần lượt đi vào chi tiết của từng phần. 3.3.1 Các vòng của TinyDES Hình sau minh họa một vòng Feistel của TinyDES 40
Li-1 Ri-1 KLi-1 KRi-1 4 4 4 4 Expand Left Shift Left Shift 6 4 4 Ki Compress 6 S-box 4 P-box 4 4 Li Ri F KLi KRi Hình 3-5. Cấu trúc một vòng của mã TinyDES Trong TinyDES, hàm F của Feistel là: F(Ri-1, Ki) = P-box(S-box(Expand( Ri-1) Ki)) Trong đó hàm Expand vừa mở rộng vừa hoán vị Ri-1 từ 4 bít lên 6 bít. Hàm S-boxes biến đổi một số 6 bít đầu vào thành một số 4 bít đầu ra. Hàm P-box là một hoán vị 4 bít. Mô tả của các hàm trên là như sau: Expand: gọi 4 bít của Ri-1 là b0b1b2b3. Hàm Expand hoán vị và mở rộng 4 bít thành 6 bít cho ra kết quả: b2b3b1b2b1b0. Ví dụ: R0 = 0110 Expand(R0) = 101110 S-box: Gọi b0b1b2b3b4b5 là 6 bít đầu vào của S-box, ứng với mỗi trường hợp của 6 bít đầu vào sẽ có 4 bít đầu ra. Việc tính các bít đầu ra dựa trên bảng sau: b1b2 b3b4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 00 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111 01 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000 b0b5 10 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000 11 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101 \ Hai bít b0b1 xác định thứ tự hàng, bốn bít b1b2b3b4 xác định thứ tự cột của bảng, Từ đó dựa vào bảng tính được 4 bít đầu ra. Để cho đơn giản, ta có thể viết lại bảng trên dưới dạng số thập lục phân. b1b2 b3b4 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7 b0b5 1 0 F 7 4 E 2 D 1 A 6 C B 9 5 3 8 2 4 1 E 8 D 6 2 B F C 9 7 3 A 5 0 3 F C 8 2 4 9 1 7 5 B 3 E A 0 6 D Ví dụ: X = 101010. Tra bảng ta có S-box(X) = 0110. 41
P-box: thực hiện hoán vị 4 bít đầu b0b1b2b3 cho ra kết quả b2b0b3b1. 3.3.2 Thuật toán sinh khóa con của TinyDES Khóa K 8 bít ban đầu được chia thành 2 nửa trái phải KL0 và KR0 , mỗi nửa có kích thước 4 bít. Tại vòng thứ nhất KL0 và KR0 được dịch vòng trái 1 bít để có được KL1 và KR1. Tại vòng thứ hai KL1 và KR1 được dịch vòng trái 2 bít để có được KL2 và KR2. Tại vòng tại vòng thứ 3 KL2 và KR2 được dịch vòng trái 1 bít để có KL3 và KR3. Cuối cùng khóa Ki của mỗi vòng được tạo ra bằng cách hoán vị và nén (compress) 8 bít của KLi và KRi (k0k1k2k3k4k5k6k7) thành kết quả gồm 6 bít : k5k1k3k2k7k0. 3.3.3 Ví dụ về TinyDES Ví dụ: mã hóa bản rõ P = 0101.1100 (5C) với khóa K = 1001.1010 L0 = 0101, R0 = 1100, KL0 = 1001, KR0 = 1010 Vòng 1: - L1 = R0 = 1100, Expand(R0) = 001011 - KL1 = KL0 <<1 = 0011, KR1 =KR0 << 1 = 0101 - K1 = Compress(KL1KR1) = 101110 - Expand(R0) K1 = 100101 - S-box(100101) = 1000 - F1 = P-box(1000) = 0100 - R1 = L0 F1 = 0001 Vòng 2: - L2 = R1 = 0001, Expand(R1) = 010000 - KL2 = KL1 <<2 = 1100, KR2 =KR1 << 2 = 0101 - K2 = Compress(KL2KR2) = 110011 - Expand(R1) K2 = 100011 - S-box(100011) = 1100 - F2=P-box(1100) = 0101 - R2 = L1 F2 = 1001 Vòng 3: - L3 = R2 = 1001, Expand(R2) = 010001 - KL3 = KL2 <<1 = 1001, KR3 =KR2 << 1 = 1010 - K3 = Compress(KL3KR3) = 001001 - Expand(R2) K3 = 011000 - S-box(011000) = 0101 - F3 = P-box(0101) = 0011 - R3 = L2 F3 = 0010 Kết quả C= L3R3 = 1001.0010 (hệ thập lục phân: 92) 3.3.4 Khả năng chống phá mã known-plaintext của TinyDES Xét trường hợp mã TinyDES chỉ có 1 vòng, tức P = (L0, R0) và C = (L1, R1). 42
L0 R0 Expand X K 1 S-box Y P-box Z L1 R1 Trong trường hợp này người phá mã biết P và C, tuy nhiên không biết K. Giả sử P = 0101.1100 và C = 1100.0001. Người phá mã tiến hành tính K như sau: Từ R0 tính X =001011. Từ L0 và R1 tính Z = 0100, và từ Z tính Y = 1000. Tra cứu bảng S-box với đầu ra là 1000, ta xác định được các đầu vào X K1 có thể xảy ra là: {100101, 100111, 001110, 011111} Như vậy khóa K1 là một trong các giá trị {101110, 101100, 000101, 010100} Thử tiếp với 1 vài cặp bản rõ-bản mã khác ta sẽ tìm được K1 = 101110 và từ đó tính được K = 1001.1010 Tuy nhiên với mã TinyDES ba vòng, việc phá mã không còn đơn giản như vậy, người phá mã chỉ biết được input của vòng đầu là P và output của vòng cuối là C, giá trị trung gian L1R1, L2R2 bị ẩn giấu nên không thể giới hạn miền tìm kiếm của các khóa K1, K2, K3 theo phương pháp trên. Dưới tác động của S-box, việc thay đổi 1 bít trong bản rõ hoặc khóa K sẽ ảnh hưởng đến nhiều bít khác nhau trong các giá trị trung gian L1R1, L2R2 (trong phần mã DES ta sẽ gọi là hiệu ứng lan truyền), nên khó phân tích mối liên quan giữa bản rõ, bản mã và khóa. Việc phá mã còn khó khăn hơn nữa trong trường hợp mã DES gồm 16 vòng và kích thước khối là 64 bít. 3.4 Mã DES (Data Encryption Standard) Mã DES có các tính chất sau: Là mã thuộc hệ mã Feistel gồm 16 vòng, ngoài ra DES có thêm một hoán vị khởi tạo trước khi vào vòng 1 và một hoán vị khởi tạo sau vòng 16 Kích thước của khối là 64 bít: ví dụ bản tin „meetmeafterthetogaparty‟ biểu diễn theo mã ASCII thì mã DES sẽ mã hóa làm 3 lần, mỗi lần 8 chữ cái (64 bít): meetmeaf - tertheto - gaparty. Kích thước khóa là 56 bít Mỗi vòng của DES dùng khóa con có kích thước 48 bít được trích ra từ khóa chính. Hình dưới đây minh họa các vòng của mã DES 43
Bản rõ 64 bít Khóa 64 bít Hoán vị khởi tạo Hoán vị khóa 64 56 48 56 Vòng 1 Nén khóa Dịch vòng trái 64 56 48 56 Vòng 2 Nén khóa Dịch vòng trái 64 56 . . 48 56 Vòng 16 Nén khóa Dịch vòng trái 64 Đổi 2 nửa đầu, cuối 64 Hoán vị kết thúc Bản mã 64 bít Hình 3-6. Các vòng Feistel của mã DES Sơ đồ mã DES trên gồm ba phần, phần thứ nhất là các hoán vị khởi tạo và hoán vị kết thúc. Phần thứ hai là các vòng Feistel, phần thứ ba là thuật toán sinh khóa con. Chúng ta sẽ lần lượt đi vào chi tiết của từng phần. 3.4.1 Hoán vị khởi tạo và hoán vị kết thúc: Ta đánh số các bít của khối 64 bít theo thứ tự từ trái sang phải là 0, 1, , 62, 63: Hoán vị khởi tạo sẽ hoán đổi các bít theo quy tắc sau : 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 56 48 40 32 24 16 8 0 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 ( Hoán vị kết thúc hoán đổi các bít theo quy tắc sau: 44
39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 32 0 40 8 48 16 56 24 Hoán vị kết thúc chính là hoán vị nghịch đảo của hoán vị khởi tạo. Đối với known- plaintext hay chosen-plaintext attack, hoán vị khởi tạo và hoán vị kết thúc không có ý nghĩa bảo mật, sự tồn tại của hai hoán vị trên được nhận định là do yếu tố lịch sử. 3.4.2 Các vòng của DES Hình sau minh họa một vòng Feistel của DES Li-1 Ri-1 KLi-1 KRi-1 32 28 28 32 Expand Left Shift Left Shift 48 28 28 K i Compress 48 S-boxes 32 P-box 32 32 Li Ri KLi KRi Hình 3-7. Cấu trúc một vòng của mã DES Trong DES, hàm F của Feistel là: F(Ri-1, Ki) = P-box(S-boxes(Expand( Ri-1) Ki)) Trong đó hàm Expand vừa mở rộng vừa hoán vị Ri-1 từ 32 bít lên 48 bít. Hàm S- boxes nén 48 bít lại còn 32 bít. Hàm P-box là một hoán vị 32 bít. Mô tả của các hàm trên là như sau: Expand: đánh số các bít của Ri-1 theo thứ tự từ trái sang phải là 0, 1, 2, , 31. Hàm Expand thực hiện vừa hoán vị vừa mở rộng 32 bít thành 48 bít theo quy tắc: 45
31 0 1 2 3 4 3 4 5 6 7 8 7 8 9 10 11 12 11 12 13 14 15 16 48 bít 15 16 17 18 19 20 19 20 21 22 23 24 23 24 25 26 27 28 27 28 29 30 31 0 S-boxes: Hàm S-boxes của DES biến đổi một số 48 bít thành một số 32 bít. Tuy nhiên, nếu chỉ lập một bảng tra cứu như ở TinyDES thì bảng này phải có 216 dòng và 232 cột, dẫn đến số phần tử của bảng rất lớn. Để giảm kích thước của bảng tra cứu, người ta chia hàm S-boxes thành 8 hàm S-box con, mỗi hàm biến đổi số 6 bít thành số 4 bít (hình dưới) 48 bít S1 S2 S3 S4 S5 S6 S7 S8 32 bít Hàm S-box đầu tiên, hộp S1, giống hoàn toàn như S-box của TinyDES, tức có nội dung như sau: b1b2 b3b4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 00 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111 01 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000 b0b5 10 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000 11 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101 \ Chi tiết các hộp còn lại được trình bày trong Phụ lục 1. Có thể thấy, mỗi hàm S-box con là một phép thay thế Substitution. Các hàm S-box con không khả nghịch, do đó hàm S-boxes cũng không khả nghịch. Sự phức tạp này của S-boxes là yếu tố chính làm cho DES có độ an toàn cao. P-box: hàm P-box cũng thực hiện hoán vị 32 bít đầu vào theo quy tắc: 15 6 19 20 28 11 27 16 0 14 22 25 4 17 30 9 1 7 23 13 31 26 2 8 18 12 29 5 21 10 3 24 3.4.3 Thuật toán sinh khóa con của DES 46
Khóa K 64 bít ban đầu được rút trích và hoán vị thành một khóa 56 bít (tức chỉ sử dụng 56 bít) theo quy tắc: 56 48 40 32 24 16 8 0 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 56 bít 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 60 52 44 36 28 20 12 4 27 19 11 3 Khóa 56 bít này được chia thành 2 nửa trái phải KL0 và KR0 , mỗi nửa có kích thước 28 bít. Tại vòng thứ i (i = 1, 2, 3, ,16), KLi-1 và KRi-1 được dịch vòng trái ri bít để có được KLi và KRi, với ri được định nghĩa: 1 1 2 9 16 2 Cuối cùng khóa Ki của mỗi vòng được tạo ra bằng cách hoán vị và nén 56 bít của KLi và KRi thành 48 bít theo quy tắc: 13 16 10 23 0 4 2 27 14 5 20 9 22 18 11 3 25 7 15 6 26 19 12 1 48 bít 40 51 30 36 46 54 29 39 50 44 32 47 43 48 38 55 33 52 45 41 49 35 28 31 3.4.4 Hiệu ứng lan truyền (Avalanche Effect) Một tính chất quan trọng cần thiết của mọi thuật toán mã hóa là chỉ cần một thay đổi nhỏ trong bản rõ hay trong khóa sẽ dẫn đến thay đổi lớn trong bản mã. Cụ thể, chỉ cần thay đổi một bít trong bản rõ hay khóa thì dẫn đến sự thay đổi của nhiều bít bản mã. Tính chất này được gọi là hiệu ứng lan truyền. Nhờ có tính chất này mà người phá mã không thể giới hạn miền tìm kiếm của bản rõ hay của khóa (dù phá mã theo known-plaintext hay chosen-plaintext) nên phải thực hiện vét cạn khóa. DES là một phương pháp mã hóa có hiệu ứng lan truyền này. Xét hai bản rõ sau (64 bít): P1: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 P2: 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 Hai bản rõ trên được mã hóa bằng DES với khóa: K: 0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010 Bảng 2-1.a cho biết số bít khác nhau của bản mã tương ứng với P1 và P2 qua các vòng của DES: 47
Vòng thứ Số bít khác nhau Vòng thứ Số bít khác nhau 0 1 0 0 1 6 1 2 2 21 2 14 3 35 3 28 4 39 4 32 5 34 5 30 6 32 6 32 7 31 7 35 8 29 8 34 9 42 9 40 10 44 10 38 11 32 11 31 12 30 12 33 13 30 13 28 14 26 14 26 15 29 15 34 16 34 16 35 a) b) Bảng 3-1. Hiệu ứng lan truyền Chỉ cần đến vòng thứ 2, số bít khác nhau giữa hai bản mã đã là 21 bít, sau 16 vòng số bít khác nhau là 34 bít (khoảng 1/2 tổng số bít của bản rõ) Xét bản rõ sau (64 bít): P: 01101000 10000101 00101111 01111010 00010011 01110110 11101011 10100100 Dùng hai khóa sau đây để mã hóa bản rõ trên (hai khóa này chỉ khác nhau 1 bít): K1: 1110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100 K2: 0110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100 Bảng 2-1.b cho biết số bít khác nhau của bản mã tương ứng với K1 và K2 qua các vòng của DES. Sau 16 vòng, số bít khác nhau là 35 bít, cũng khoảng 1/2 tổng số bít của bản rõ. 3.4.5 Độ an toàn của DES Ta hãy xem xét tính an toàn của DES trước một vài phương pháp tấn công phá mã. 1) Tấn công vét cạn khóa (Brute Force Attack): Vì khóa của mã DES có chiều dài là 56 bít nên để tiến hành brute-force attack, cần kiểm tra 256 khóa khác nhau. Hiện nay với những thiết bị phổ dụng, thời gian gian để thử khóa là rất lớn nên việc phá mã là không khả thi (xem bảng). Tuy nhiên vào năm 1998, tổ chức Electronic Frontier Foundation (EFF) thông báo đã xây dựng được một thiết bị phá mã DES gồm nhiều máy tính chạy song song, trị giá khoảng 250.000$. Thời gian thử khóa là 3 ngày. Hiện nay mã DES vẫn còn được sử dụng trong thương mại, tuy nhiên người ta đã bắt đầu áp dụng những phương pháp mã hóa khác có chiều dài khóa lớn hơn (128 bít hay 256 bít) như TripleDES hoặc AES. 48
2) Phá mã DES theo phương pháp vi sai (differential cryptanalysis): Năm 1990 Biham và Shamir đã giới thiệu phương pháp phá mã vi sai. Phương pháp vi sai tìm khóa ít tốn thời gian hơn brute-force. Tuy nhiên phương pháp phá mã này lại đòi hỏi phải có 247 cặp bản rõ - bản mã được lựa chọn (chosen-plaintext). Vì vậy phương pháp này là bất khả thi dù rằng số lần thử có thể ít hơn phương pháp brute-force. 3) Phá mã DES theo phương pháp thử tuyến tính (linear cryptanalysis) Năm 1997 Matsui đưa ra phương pháp phá mã tuyến tính. Trong phương pháp này, cần phải biết trước 243 cặp bản rõ-bản mã (known-plaintext). Tuy nhiên 243 cũng là một con số lớn nên phá mã tuyến tính cũng không phải là một phương pháp khả thi. 3.5 Một số phương pháp mã khối khác 3.5.1 Triple DES Một trong những cách để khắc phục yếu điểm kích thước khóa ngắn của mã hóa DES là sử dụng mã hóa DES nhiều lần với các khóa khác nhau cho cùng một bản tin. Đơn giản nhất là dùng DES hai lần với hai khóa khác nhau, cách thức này được gọi là Double DES: Điều này giống như là Double DES dùng một khóa có kích thước là 112 byte, chỉ có một hạn chế là tốc độ chậm hơn DES vì phải dùng DES hai lần. Tuy nhiên người ta đã tìm được một phương pháp tấn công Double DES có tên gọi là gặp-nhau-ở-giữa (meet-in-the- middle). Đây là một phương pháp tấn công chosen-plaintext. Vì vậy người ta chọn dùng DES ba lần với ba khóa khác nhau, cách thức này được gọi là Triple DES: Chiều dài khóa là 168 bít sẽ gây phức tạp hơn nhiều cho việc phá mã bằng phương pháp tấn công gặp-nhau-ở-giữa. Trong thực tế người ta chỉ dùng Triple DES với hai khóa K1, K2 mà vẫn đảm bảo độ an toàn cần thiết. Công thức như sau: Nguyên nhân của việc dùng EDE thay cho EEE là nếu với K1 = K2 = K thì Nghĩa là Triple DES suy giảm thành một DES đơn. 3.5.2 Advanced Encryption Standard (AES) Vào những năm 1990, nhận thấy nguy cơ của mã hóa DES là kích thước khóa ngắn, có thể bị phá mã trong tương lai gần, Cục tiêu chuẩn quốc gia Hoa Kỳ đã kêu gọi xây dựng một phương pháp mã hóa mới. Cuối cùng một thuật toán có tên là Rijndael được chọn và đổi tên thành Andvanced Encryption Standard hay AES. Có thể nói rằng mã hóa AES với khóa có kích thước 256 bít là “an toàn mãi mãi” bất kể những tiến bộ trong ngành kỹ thuật máy tính. 49
Giống như DES, mã hóa AES là một mã khối gồm nhiều vòng. Khác với DES, mã hóa AES không phải là một mã hóa Feistel. Thuật toán AES khá phức tạp, ở đây chúng ta chỉ nêu ra một số đặc điểm chính của AES: Cho phép lựa chọn kích thước khối mã hóa là 128, 192 hay 256 bít. Cho phép lựa chọn kích thước của khóa một cách độc lập với kích thước khối: là 128, 192 hay 256 bít. Số lượng vòng có thể thay đổi từ 10 đến 14 vòng tùy thuộc vào kích thước khóa. Độ an toàn của AES làm cho AES được sử dụng ngày càng nhiều và trong tương lai sẽ chiếm vai trò của DES và Triple DES. 3.6 Các mô hình ứng dụng mã khối Mã khối (như mã DES) được áp dụng để mã hóa một khối dữ liệu có kích thước xác định. Để mã hóa một bản tin dài, bản tin được chia ra thành nhiều khối ( ) và áp dụng mã khối cho từng khối một. Có nhiều mô hình áp dụng mã khối là ECB, CBC, CTR, OFB và CFB. 3.6.1 Electronic Codebook – ECB Trong mô hình ECB, mỗi khối được mã hóa một cách riêng rẽ, dùng chung một khóa K. P p0 p1 pn-1 K K K E E E C c0 c1 cn-1 a) Quá trình mã hóa C c0 c1 cn-1 K K K D D D P p0 p1 pn-1 b) Quá trình giải mã Hình 3-8. Mô hình ECB của mã khối Trong mã hóa ECB, nếu Pi = Pj thì Ci = Cj và ngược lại. Có thể thấy rằng mã ECB tương tự như mã hóa đơn bảng cổ điển, trong đó Pi và Ci giống như là các chữ cái, còn khóa K cùng với mã khối giống như là một phép hoán vị. Do đó, người phá mã có thể dựa vào một số đặc tính thống kê của dữ liệu để tiến hành phá mã, giống như dùng thống kê tần suất chữ cái để phá mã mã hóa đơn bảng (dù rằng Pi có kích thước lớn nên đặc tính thống 50
kê cũng khó phát hiện hơn). Vì vậy mã hóa ECB chỉ thích hợp để mã hóa những bản tin ngắn. Hình 3-9. Mã hóa ECB không che dấu hết thông tin (nguồn: trích từ [3]) Để minh họa đặc tính thống kê của dữ liệu, hình trên thể hiện một tấm ảnh được mã hóa bằng ECB. Dù rằng mỗi khối đã được biến đổi qua phép mã hóa, tuy nhiên nhìn tổng thể thì vẫn tồn tại một sự liên hệ nào đó giữa các khối. 3.6.2 Cipher Block Chaining – CBC Trong mô hình CBC, bản mã của một lần mã hóa được sử dụng cho lần mã hóa tiếp theo: với i = 1, 2, 3 n-1 Do đó để mã hóa khối đầu tiên, người ta dùng một khối dữ liệu giả được gọi là vector khởi tạo (initialization vector – IV) và được chọn ngẫu nhiên: Để giải mã, tiến hành ngược lại: với i = 1, 2, n-1 51
P p0 p1 pn-1    E E E IV c0 c1 cn-1 a) Quá trình mã hóa IV c0 c1 cn-1 D D D    P p0 p1 pn-1 b) Quá trình giải mã Hình 3-10. Mô hình CBC của mã khối Người mã hóa và người giải mã phải dùng chung vector khởi tạo IV. Vector khởi tạo không cần giữ bí mật nên thường được gắn vào trước bản mã trước khi truyền thông điệp ( ). Có thể thấy rằng nội dung của bản mã Ci không chỉ phụ thuộc vào bản rõ Pi mà còn phụ thuộc vào tất cả các bản rõ đứng trước và IV. Do đó nếu có hai bản rõ giống nhau thì hai bản mã sẽ không giống nhau (do IV ngẫu nhiên). Điều này khắc phục được hạn chế của mô hình ECB, từ bản mã người phá mã không thể phát hiện ra những đặc tính thống kê của dữ liệu. Ngược lại, đối với việc giải mã, bản rõ Pi không chỉ phụ thuộc vào bản mã Ci mà còn phụ thuộc vào bản mã Ci-1 đứng trước. Do đó nếu xảy lỗi trên đường truyền, chỉ cần một bít bị hỏng thì dẫn đến không thể giải mã được bản mã đó và bản mã tiếp theo sau. 52
Hình 3-11. Bức ảnh sau khi mã hóa dùng mô hình CBC (nguồn: trích từ [3]) 3.6.3 Counter – CTR Đến thời điểm này, chúng ta đã tìm hiểu hai cách tiếp cận để chống lại việc phá mã dựa trên thống kê tần suất. Cách tiếp cận thứ nhất là theo mô hình của mã dòng, dùng một bộ sinh khóa ngẫu nhiên (confusion – làm rối). Cách tiếp cận thứ hai là theo mô hình CBC của mã khối, dùng các khối phía trước tác động đến bản mã của các khối đi sau (diffusion – khuếch tán). Xét lại mô hình mã dòng: P p0 p1 pn-1 s0 s1 sn-1 C c c c 0 1 n-1 Trong đó s0, s1, s2, được sinh ra từ bộ sinh số ngẫu nhiên. CTR thực ra là một phương pháp mã hóa thuộc loại mã dòng, tuy nhiên bộ sinh khóa ngẫu nhiên có dùng đến mã khối để sinh số. Kích thước của đơn vị mã hóa là kích thước mã khối (ví dụ nếu dùng mã DES thì đơn vị mã hóa là 64 bít). Với một vector khởi tạo ban đầu, công thức sinh số như sau: Do hiệu ứng lan truyền (Avalanche Effect) của mã khối nên có thể xem bộ sinh khóa trên sinh ra một dãy số ngẫu nhiên theo nguyên tắc thiết kế của mã dòng. 3.6.4 Output Feedback – OFB Mô hình CTR là một mã dòng trong đó đơn vị mã hóa có kích thước cố định là b bít, với b là kích thước mã khối. Để mã hóa với đơn vị mã hóa có kích thước bất kỳ, mô hình OFB được đề xuất. Mô hình này có hai điểm khác so với mô hình CTR: 53
Chỉ dùng s bít đầu tiên của khóa sinh ra bởi bộ sinh khóa, với s là kích thước đơn vị mã hóa dùng trong phép XOR. Để tăng thêm tính ngẫu nhiên của bộ sinh khóa, s bít này của khóa được ghép vào vector khởi tạo IV cho lần mã hóa tiếp theo. Phép ghép được thực hiện bằng cách đẩy trái IV s bít và đưa s bít của khóa vào s bít thấp của IV. Register = IV; for i = 0 to n-1 do Ti = E(Register, K); Ti = Ti SHR (b-s); // lấy s bít đầu của Ti Ci = Pi XOR Ti; Register = Register SHL s; Register = Register OR Ti; next i s s Thanh ghi dịch trái s bít IV b bít b b K Mã khối K Mã khối K Mã khối b b b s s s s s s s s s bít s s P0 P1 P2 C0 C1 C2 Hình 3-12. Mô hình OFB của mã khối Giống như mô hình ECB, trong mô hình CTR và OFB, mỗi khối được mã hóa một cách riêng rẽ, không phụ thuộc vào nhau. 3.6.5 Cipher Feedback – CFB Mô hình CFB có thay đổi một chút so với mô hình OFB. Mô hình OFB dùng s bít của khóa do bộ sinh khóa tạo ra để ghép với IV cho lần mã hóa tiếp theo. Còn mô hình CFB dùng s bít của bản mã để ghép với IV. 54
s s Thanh ghi dịch trái s bít IV b b b K Mã khối K Mã khối K Mã khối b b b s s s s s s s s P0 s bít P1 s P2 C0 C1 C2 Hình 3-13. Mô hình CFB của mã khối Do đó giống như mô hình CBC, có thể thấy rằng nội dung của bản mã Ci không chỉ phụ thuộc vào bản rõ Pi mà còn phụ thuộc vào tất cả các bản rõ đứng trước và IV. Ngược lại, đối với việc giải mã, bản rõ Pi không chỉ phụ thuộc vào bản mã Ci mà còn phụ thuộc vào bản mã Ci-1 đứng trước. 3.7 Tính chứng thực (authentication) của mã hóa đối xứng. Trong phần lớn chương này, chúng ta đã tìm hiểu về cách thức mã hóa đối xứng thực hiện tính bảo mật. Vậy còn tính chứng thực thì sao? Mã hóa đối xứng có thể chống lại các hình thức tấn công sửa đổi thông điệp, mạo danh và phát lại thông điệp được hay không? Câu trả lời là có. Trước tiên là vấn đề mạo danh. Trudy có thể nào gửi thông điệp cho Bob mà Bob nghĩ rằng thông điệp đó là từ Alice không? Xét tình huống sau: Alice và Bob quyết định dùng mã Vigenere để trao đổi dữ liệu, với khóa bí mật KAB là „DECEPTIVE‟ Khi Alice gửi cho Bob một bản mã C, Bob dùng KAB để giải mã cho ra bản rõ. Ví dụ, Alice gửi bản mã: „ZICVTWQNGRZGVTWAVZHCQYGLMGJ‟. Bob giải mã có được bản rõ: „wearediscoveredsaveyourself‟. Đây là một bản tin tiếng Anh có ý nghĩa. Trudy muốn mạo danh Alice nên tìm một bản mã CT và gửi CT cho Bob. Bob nghĩ rằng CT là từ Alice nên giải mã bằng KAB và có được bản rõ PT. Vấn đề ở đây là làm sao Bob biết được PT là của Trudy chứ không phải của Alice? Vì Trudy không biết KAB nên Trudy không thể chọn PT trước rồi mới có CT. Do đó Trudy phải chọn ngẫu nhiên một CT nào đó. Ví dụ Trudy chọn CT là „WDTAXRLKY‟. Như vậy Bob giải mã có được PT là „tzrwiydpu‟. Tuy nhiên PT này không phải là văn bản có nghĩa trong tiếng Anh. Có thể thấy rằng việc Trudy chọn được một CT nào đó, sao cho sau khi Bob giải mã cho ra PT là văn bản có nghĩa, thì có xác suất rất bé. Trong trường hợp PT có nghĩa theo ý muốn của Trudy thì coi như là không thể xảy ra. 55
Do đó có thể chắc chắn rằng nếu Trudy mạo danh thì PT sẽ là văn bản vô nghĩa, từ đó Bob biết được CT là không phải từ Alice. Tương tự như vậy với vấn đề sửa nội dung thông điệp, nếu Trudy chặn được bản mã C của Alice và sửa C thành CT, thì xác suất để PT là văn bản có nghĩa cũng rất bé. Và Bob biết được C đã bị sửa đổi. Đối với mã hóa hiện đại cũng vậy, nếu Trudy chọn CT là một dãy bít bất kỳ thì bản rõ PT cũng là một dãy bít lộn xộn, không có cấu trúc ý nghĩa. Tuy nhiên, trong thực tế, việc xác định như thế nào là dãy bít vô nghĩa là một công việc khó khăn đối với máy tính. Ngoài ra, có những loại dữ liệu hoàn toàn là một dãy bít ngẫu nhiên. Trong thực tế, chúng ta phải chấp nhận rằng bất cứ dãy bít P nào cũng có thể là có ý nghĩa. Do đó, để đảm bảo tính chứng thực, người ta dùng khái niệm mã chứng thực thông điệp – MAC để biến dãy bít ngẫu nhiên thành dãy bít có cấu trúc. Chúng ta sẽ tìm hiểu về MAC trong chương 5. Còn tại thời điểm này, chúng ta chấp nhận rằng một thông điệp có ý nghĩa thì là một dãy bít có cấu trúc. Đối với tấn công phát lại thông điệp (replay attack). Alice gửi bản mã C cho Bob, Bob nhận được và giải mã để có bản rõ P. Tuy nhiên Trudy chặn được bản mã C và sau đó mạo danh Alice gửi C cho Bob thêm một lần nữa. Bob giải mã và cũng có được P. Như vậy Bob nhận được cùng một thông điệp P hai lần. Tại lần thứ 2, Bob không có cơ sở xác định là Alice muốn gửi lại hay là do Trudy gửi. Chương 6 sẽ trình bày các phương pháp chống lại hình thức tấn công phát lại thông điệp. 3.8 Tính không từ chối (non-repudiation) của mã hóa đối xứng. Dù rằng mã hóa đối xứng đảm bảo tính bảo mật của hệ truyền tin, tuy nhiên mã hóa đối xứng lại không thực hiện được tính không từ chối. Nguyên nhân ở đây là tính bí mật của khóa. Vì khóa K bít mật có hai người biết, nên nếu K bị tiết lộ thì không có cơ sở để quy trách nhiệm cho Alice hay Bob làm lộ khóa. Do đó Alice có thể từ chối là đã gửi bản tin. Lấy lại ví dụ về chứng khoán, giả sử Bob là nhân viên môi giới chứng khoán của Alice. Alice gởi thông điệp yêu cầu Bob mua cổ phiếu của công ty Z. Thông điệp này được mã hóa. Ngày hôm sau, giá cổ phiếu công ty này giảm hơn 50%. Thấy bị thiệt hại, Alice nói rằng Bob đã làm lộ khóa, Trudy có được khóa và gởi thông điệp chứ không phải là Alice. Bob không thể nào bác bỏ lập luận này. Vì vậy các nhà nghiên cứu bắt đầu tìm kiếm các phương án mã hóa khác, sao cho khóa bí mật chỉ có một người biết mà thôi. Đó là phương pháp mã hóa khóa công khai, được trình bày trong chương tiếp theo. 3.9 Trao đổi khóa bí mật bằng trung tâm phân phối khóa Giả sử có N người sử dụng, trao đổi dữ liệu bằng mã hóa đối xứng, mỗi cặp người sử dụng cần có một khóa bí mật riêng, dẫn đến cần có N(N-1)/2 khóa bí mật. Việc thiết lập các khóa bí mật này sẽ gây ra khó khăn cho các người sử dụng vì mỗi người cần thiết lập N-1 khóa. 56
KAB A B K KAE AC KBC KAD E C KDC D Phương pháp trao đổi khóa bằng trung tâm phân phối khóa (Key Distribution Center – KDC) giúp đơn giản hóa vấn đề này. Trong mô hình sử dụng KDC, mỗi người sử dụng chỉ cần có một khóa bí mật với KDC. Còn khóa dùng để trao đổi dữ liệu giữa các người sử dụng sẽ do KDC cung cấp. A B KA KB KDC KE KC E C KD D Giả sử Alice có khóa bí mật KA với KDC và Bob có khóa bí mật KB với KDC. Bây giờ Alice muốn trao đổi dữ liệu với Bob. Quá trình thiết lập khóa chung KAB giữa Alice và Bob gồm các bước: 1) Alice gửi yêu cầu muốn trao đổi dữ liệu với Bob cho KDC. 2) KDC tạo một khóa bí mật KAB và mã hóa thành hai bản mã. Một bản mã được mã hóa bằng khóa bí mật của Alice E(KAB, KA) và một bản mã được mã hóa bằng khóa bí mật của Bob E(KAB, KB). 3) Alice giải mã E(KAB, KA) để có KAB 4) Alice gửi E(KAB, KB) cho Bob, Bob giải mã để có được KAB 5) Alice và Bob trao đổi dữ liệu qua khóa bí mật KAB KDC 1. REQUEST to B 2. E(KAB, KA)||E(KAB, KB) 4. E(KAB, KB) A B 5. E(P, K ) AB Hình 3-14. Trao đổi khóa bít mật dùng KDC Như vậy, khóa KAB chỉ có KDC, Alice và Bob biết. Trách nhiệm của KDC là giữ bí mật khóa này. Alice và Bob dùng khóa KAB để mã hóa dữ liệu. Khi kết thúc quá trình 57
truyền dữ liệu, KAB được hủy bỏ. Lần sau nếu Alice lại truyền số liệu với Bob thì KDC sẽ cung cấp khóa KAB khác. Như vậy chỉ cần Alice có thiết lập khóa bí mật KA với KDC thì Alice có thể truyền số liệu không chỉ với Bob mà còn với những người khác. Một khái niệm quan trọng khác có thể rút ra từ mô hình dùng KDC là khái niệm khóa chủ và khóa phiên (master key và session key). Trong ví dụ trên các khóa KA, KB không được sử dụng trực tiếp để mã hóa dữ liệu, chúng chỉ được dùng để mã hóa các khóa tạm KAB. Các khóa KAB này mới trực tiếp mã hóa dữ liệu và bị hủy bỏ khi sau quá trình truyền dữ liệu kết thúc. Vì vậy KA, KB được gọi là khóa chủ, chúng ít được sử dụng nên người phá mã khó có cơ hội thu thập bản mã để phá mã. Khóa KA, KB được sử dụng lâu dài. Còn KAB được gọi là khóa phiên, KAB chỉ tồn tại trong một phiên truyền dữ liệu duy nhất mà thôi. Chương 7 trình bày giao thức Keberos, là một giao thức dựa trên khái niệm trung tâm phân phối khóa. Keberos được sử dụng trong các hệ điều hành ngày nay, để mã hóa dữ liệu trong mạng cục bộ LAN. 3.10 Câu hỏi ôn tập 1) Mã hóa đối xứng hiện đại và mã hóa đối xứng cổ điển khác nhau ở điểm nào. 2) Mã dòng hoạt động dựa trên nguyên tắc thay thế hay hoán vị? 3) Từ nguyên tắc sinh số của mã hóa A5/1 và RC4, hãy cho biết lý do mã dòng lại dùng bộ sinh số để sinh ra dãy bít? Tại sao không dùng trực tiếp khóa K để thực hiện phép XOR ? 4) Hệ mã Fiestel có thuận lợi gì trong việc thực hiện mã khối? 5) Tại sao mã hóa DES lại dùng các phép biến đổi phức tạp chỉ để mã hóa một khối 64 bít? 6) Xét mô hình ECB, để mã hóa một bản tin dài bằng mã DES, chúng ta phải lần lượt mã hóa từng khối 64 bít. Việc thực hiện như vậy giống và khác với mã dòng ở những điểm nào? 7) Mô hình CBC có đặc tính gì mà các phương pháp mã hóa theo nguyên tắc thay thế (như ECB) không có? 8) Tại sao nói mô hình CTR, OFB và CFB thực ra là mã dòng? 9) Một bản rõ phải có đặc điểm gì thì mới có thể nói phương pháp mã hóa đối xứng có tính chứng thực? Nếu Trudy không biết khóa bí mật của Alice và Bob, Trudy có thể mạo danh Alice gửi thông điệp mà Trudy muốn cho Bob được không? 10) Trong mã hóa đối xứng, việc hai người cùng biết khóa dẫn đến nhược điểm gì của phương pháp mã hóa này? 11) Hãy nêu lợi ích của việc dùng khóa chủ và khóa phiên. 3.11 Bài tập 1. Xét thuật toán TinyA5/1, giả sử ban đầu X=21, Y = 55, Z=60. Tính bít thứ 1, 2, 3 được sinh ra bởi bộ sinh khóa. 2. Trong bước khởi tạo của thuật toán RC4, đầu tiên S là dãy các giá trị tăng dần từ 1 đến 255. Tìm khóa K để sau khi hoàn tất khởi tạo, S không đổi (vẫn là dãy tăng dần từ 1 đến 255). 58
3. Alice và Bob trao đổi dữ liệu bằng thuật toán A5/1, tuy nhiên họ muốn tránh việc dùng một khóa mới cho mỗi lần truyền dữ liệu. Alice và Bob bí mật chia sẻ một khóa k ban đầu gồm 128 bit. Để mã hóa thông điệp m, Alice tiến hành như sau: - Chọn một giá trị v bất kỳ gồm 80 bít. - Mã hóa bằng RC4: C = A51(v||k)  m - Gửi đi dãy bít v||C a. Mô tả các bước thực hiện của Bob để giải mã thông điệp b. Giả sử Trudy quan sát thấy dãy (v1||C1), (v2||C2), (v3||C3), gửi đi giữa Alice và Bob, nêu giải pháp để Trudy có thể phá mã. 4. Chứng minh rằng sau một số bước thực hiện, khóa sinh ra bởi thuật toán A5/1 sẽ lặp lại. 5. Chứng minh rằng sau một số bước thực hiện, khóa sinh ra bởi thuật toán RC4 sẽ lặp lại. 6. Xét một mã khối thuộc hệ Feistel gồm 4 vòng và P = (L0, R0). Cho biết bảng mã C ứng với các trường hợp sau của hàm F: a. F(Ri−1, Ki ) = 0. b. F(Ri−1, Ki ) = Ri−1. c. F(Ri−1, Ki ) = Ki d. F(Ri−1, Ki ) = Ri−1 Ki . 7. Xét một mã khối thuộc hệ Feistel gồm 2 vòng với kích thước khối và kích thước khóa là 128 bít. Thuật toán sinh khóa con sinh ra khóa cho 2 vòng là như nhau k1 = k2. Giả sử chúng ta được lựa chọn một (và chỉ một) bản rõ và có bản mã tương ứng (chosen-plaintext attack). Hãy nêu phương thức để phá mã một bản mã C nào đó. 8. Xét mã TinyDES trong đó khóa K là 10100100. Hãy tính bản mã trong trường hợp bản rõ là P = 01001011 9. Công thức mã hóa cho mô hình ứng dụng mã khối CTR là: Giả sử thay vì sử dụng công thức trên ta dùng công thức: Thực hiện như vậy có an toàn không? Tại sao? 10. Xét một mô hình ứng dụng mã khối sau: Hãy cho biết công thức giải mã. Trình bày một điểm yếu của mô hình này so với mô hình CBC. 11. Trong mô hình CBC, nếu Alice dùng một IV duy nhất cho tất cả các lần truyền dữ liệu thì có an toàn không? (các lần truyền đều dùng cùng khóa) 12. Trong mô hình CBC áp dụng mã khối 64 bít, nếu có một bít của bản mã bị hỏng trong quá trình truyền dữ liệu, tính số bít bị hỏng của bản giải mã. 3.12 Bài tập thực hành 59
1. Viết chương trình mã hóa và giải mã file bằng thuật toán A5/1, khóa là X, Y, Z nhập từ bàn phím. 2. Viết chương trình mã hóa và giải mã file bằng thuật toán RC4, khóa là dãy N byte nhập từ bàn phím. 3. Viết chương trình mã hóa và giải mã file bằng thuật toán DES và mô hình mã khối CBC. Khóa K được lưu trong 1 file text riêng dưới dạng chữ số thập lục phân. 4. Tìm hiểu về thư viện mã hóa của môi trường lập trình .NET (namespace System.Security.Cryptography). Viết chương trình mã hóa và giải mã một file dùng thuật toán DES, TripleDES, Rijndael và AES trong thư viện mã hóa của .NET. Khóa K được lưu trong 1 file text riêng dưới dạng chữ số thập lục phân. 60
CHƢƠNG 4. MÃ HÓA KHÓA CÔNG KHAI Mã hóa đối xứng dù rằng đã phát triển từ cổ điển đến hiện đại, vẫn tồn tại hai điểm yếu sau: Vấn đề trao đổi khóa giữa người gửi và người nhận: Cần phải có một kênh an toàn để trao đổi khóa sao cho khóa phải được giữ bí mật chỉ có người gửi và người nhận biết. Điều này tỏ ra không hợp lý khi mà ngày nay, khối lượng thông tin luân chuyển trên khắp thế giới là rất lớn. Việc thiết lập một kênh an toàn như vậy sẽ tốn kém về mặt chi phí và chậm trễ về mặt thời gian. Tính bí mật của khóa: không có cơ sở quy trách nhiệm nếu khóa bị tiết lộ. Vào năm 1976 Whitfield Diffie và Martin Hellman đã tìm ra một phương pháp mã hóa khác mà có thể giải quyết được hai vấn đề trên, đó là mã hóa khóa công khai (public key cryptography) hay còn gọi là mã hóa bất đối xứng (asymetric cryptography). Đây có thể xem là một bước đột phá quan trọng nhất trong lĩnh vực mã hóa. Xét lại mô hình mã hóa đối xứng: bộ sinh khóa kênh an toàn K P kênh thường P nơi gởi Mã hóa Giải mã nơi nhận C ̂ Phá mã ̂ Để khắc phục điểm yếu của mã hóa đối xứng người ta tập trung vào nghiên cứu theo hướng: có phương pháp nào để việc mã hóa và giải mã dùng hai khóa khác nhau? Có nghĩa là C = E(P, K1) và P = D(C, K2). Nếu thực hiện được như vậy thì chúng ta sẽ có 2 phương án áp dụn: Phương án 1: người nhận (Bob) giữ bí mật khóa K2, còn khóa K1 thì công khai cho tất cả mọi người biết. Alice muốn gởi dữ liệu cho Bob thì dùng khóa K1 để mã hóa. Bob dùng K2 để giải mã. Ở đây Trudy cũng biết khóa K1, tuy nhiên không thể dùng chính K1 để giải mã mà phải dùng K2. Do đó chỉ có duy nhất Bob mới có thể giải mã được. Điều này bảo đảm tính bảo mật của quá trình truyền dữ liệu. Ưu điểm của phương án này là không cần phải truyền khóa K1 trên kênh an toàn. P = D(C, K ) P = D(C, K ) 1 2 Phương án 2: người gửi (Alice) giữ bí mật khóa K1, còn khóa K2 thì công khai cho tất cả mọi người biết. Alice muốn gởi dữ liệu cho Bob thì dùng khóa K1 để mã hóa. Bob 61
dùng K2 để giải mã. Ở đây Trudy cũng biết khóa K2 nên Trudy cũng có thể giải mã được. Do đó phương án này không đảm bảo tính bảo mật. Tuy nhiên lại có tính chất quan trọng là đảm bảo tính chứng thực và tính không từ chối. Vì chỉ có duy nhất Alice biết được khóa K1, nên nếu Bob dùng K2 để giải mã ra bản tin, thì điều đó có nghĩa là Alice là người gửi bản mã. Nếu Trudy cũng có khóa K1 để gửi bản mã thì Alice sẽ bị quy trách nhiệm làm lộ khóa K1. Trong phương án này cũng không cần phải truyền K2 trên kênh an toàn. Vì vậy nếu kết hợp phương án 1 và phương án 2, thì mô hình đề xuất của chúng ta khắc phục được các nhược điểm của mã hóa đối xứng. Trong cả hai phương án, một khóa được giữ bí mật chỉ một người biết, còn khóa kia được công khai. Do đó mô hình mã hóa trên được gọi là mã hóa khóa công khai (hay mã hóa bất đối xứng). Để thuận tiện ta quy ước lại các ký hiệu như sau: - Để tránh nhầm lẫn với khóa bí mật của mã đối xứng, khóa bí mật trong mô hình trên được gọi là khóa riêng (private key) và ký hiệu là KR. - Khóa công khai (public key) được ký hiệu là KU. - Bản rõ được ký hiệu là M, còn bản mã giữ nguyên ký hiệu là C - Phương án 1 viết lại thành: C = E(M, KU) M = D(C, KR) - Phương án 2 viết lại thành: C = E(M, KR) M = D(C, KU) Vấn đề còn lại ở đây là liệu có tồn tại một mô hình mã hóa và giải mã dùng hai khóa khác nhau như vậy không? Dĩ nhiên là hai khóa KU và KR không thể nào hoàn toàn độc lập với nhau. Phải có một mối quan hệ nào đó giữa KU và KR thì mới có thể tiến hành giải mã hóa và giải mã được. Có nghĩa là KR = f(KU). Tuy nhiên một yêu cầu rất quan trọng là việc tính KR = f(KU) phải là bất khả thi về mặt thời gian. Nếu nguyên tắc này bị vi phạm thì việc giữ bí mật khóa KR không còn ý nghĩa vì từ khóa công khai KU có thể tính được KR. Để có được cặp khóa KR và KU như trên, người ta thường dùng các hàm một chiều (oneway function). Các hàm một chiều có tính chất là hàm nghịch đảo của chúng rất khó thực hiện. Sau đây là ví dụ về hàm một chiều: việc sinh ra hai số nguyên tố lớn p, q và tính tích N = pq thì thực hiện dễ dàng. Tuy nhiên nếu chỉ cho trước N và thực hiện phân tích N để tìm lại hai số nguyên tố p, q là việc hoàn toàn bất khả thi về mặt thời gian. Chúng ta sẽ xem cách thức áp dụng hàm một chiều này để tạo khóa KR và KU trong phần mã hóa RSA. Có nhiều phương pháp mã hóa thuộc loại mã hóa khóa công khai. Đó là các phương pháp Knapsack, RSA, Elgaman, và phương pháp đường cong elliptic ECC . Mỗi phương pháp có cách thức ứng dụng hàm một chiều khác nhau. Trong tài liệu này, chúng ta chỉ tập trung vào tìm hiểu phương pháp RSA. Bên cạnh đó, chúng ta cũng đề cập đến phương pháp trao đổi khóa Diffie-Hellman, một cách áp dụng hàm một chiều nhưng không phải để mã hóa. Tuy nhiên trước tiên chúng ta sẽ tìm hiểu sơ lược về lý thuyết số, đây là nền tảng toán học của phương pháp mã hóa khóa công khai. 62