Tài liệu Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng

i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi, các số liệu và kết quả trình bày trong luận án là trung thực và chưa được công bố ở bất kỳ công trình nào khác. Tác giả Hồ Quang Bửu ii LỜI CẢM ƠN Luận án Tiến sĩ kỹ thuật này được thực hiện tại Học viện Công nghệ Bưu chính Viễn thông. Tác giả xin tỏ lòng biết ơn đến thầy giáo GS.TSKH. Nguyễn Xuân Quỳnh đã trực tiếp định hướng, tạo mọi điều kiện trong suốt quá trình nghiên cứu. Tác giả cũng xin cảm ơn GS.TS. Nguyễn Bình đã trực tiếp hướng dẫn học thuật hóa, kiểm tra những kết quả của các công trình nghiên cứu. Tôi xin chân thành cảm ơn Lãnh đạo Học viện Công nghệ Bưu chính Viễn thông đã tạo những điều kiện thuận lợi để hoàn thành và bảo vệ luận án trong thời gian nghiên cứu của nghiên cứu sinh. Tôi xin cảm ơn khoa Quốc tế và Đào tạo sau đại học, Sở Thông tin truyền thông tỉnh Quảng Nam (nơi tôi đang công tác), cũng như các đồng nghiệp đã tạo điều kiện và giúp đỡ tôi hoàn thành được đề tài nghiên cứu của mình. Cuối cùng là sự biết ơn tới gia đình, bạn bè đã thông cảm, động viên giúp đỡ cho tôi có đủ nghị lực để hoàn thành luận án. Hà nội, tháng 12 năm 2013 iii MỤC LỤC LỜI CAM ĐOAN ...................................................................................................... i LỜI CẢM ƠN ..........................................................................................................ii MỤC LỤC ...............................................................................................................iii DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ............................................. vi DANH MỤC CÁC BẢNG ....................................................................................viii DANH MỤC CÁC HÌNH VẼ ................................................................................. ix PHẦN MỞ ĐẦU ...................................................................................................... 1 1. MỞ ĐẦU ....................................................................................................... 1 2. TÌNH HÌNH NGHIÊN CỨU ......................................................................... 1 3. LÝ DO CHỌN ĐỀ TÀI ................................................................................. 4 4. MỤC TIÊU NGHIÊN CỨU .......................................................................... 4 5. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU .................................................... 5 6. PHƯƠNG PHÁP NGHIÊN CỨU ................................................................. 5 7. Ý NGHĨA KHOA HỌC VÀ THỰC TIÊN CỦA ĐỀ TÀI ............................ 5 CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ HỌC .................................................. 6 1.1. CÁC KHÁI NIỆM CƠ BẢN ......................................................................... 6 1.2. CÁC HỆ MẬT KHÓA BÍ MẬT .................................................................... 8 1.2.1. Sơ đồ khối chức năng hệ mật khóa bí mật .................................... 8 1.2.2. Các hệ mật thay thế ....................................................................... 8 1.2.3. Các hệ mật hoán vị (MHV) ......................................................... 11 1.2.4. Các hệ mật mã tích ...................................................................... 12 1.2.5. Các hệ mật mã dòng và việc tạo các dãy giả ngẫu nhiên ............ 15 1.2.6. Chuẩn mã dữ liệu DES ................................................................ 26 1.2.7. Ưu nhược điểm của mật mã khóa bí mật..................................... 29 iv 1.3. HỆ MẬT KHÓA CÔNG KHAI................................................................... 30 1.3.1. Sơ đồ chức năng .......................................................................... 30 1.3.2. Một số bài toán xây dựng hệ mật khóa công khai ....................... 31 1.4. CƠ BẢN VỀ HÀM BĂM ............................................................................ 33 1.4.1. Mở đầu ......................................................................................... 33 1.4.2. Các định nghĩa và tính chất cơ bản.............................................. 35 1.4.3. Một số phương pháp xây dựng hàm băm .................................... 37 1.4.4. Các loại tấn công hàm băm cơ bản .............................................. 41 1.4.5. Độ an toàn mục tiêu ..................................................................... 43 1.5. TÍNH TOÀN VẸN CỦA DỮ LIỆU VÀ XÁC THỰC THÔNG BÁO........ 44 1.5.1. Các phương pháp kiểm tra tính toàn vẹn dữ liệu ........................ 44 1.5.2. Chữ ký số ..................................................................................... 46 1.6. KẾT LUẬN CHƯƠNG 1............................................................................. 49 CHƯƠNG 2. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC .. 50 2.1. NHÓM NHÂN CYCLIC TRÊN VÀNH ĐA THỨC .................................. 50 2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức ......................... 50 2.1.2. Các loại nhóm nhân cyclic trên vành đa thức.............................. 52 2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC ................................. 54 2.2.1. Khái niệm về cấp số nhân cyclic trên vành đa thức .................... 54 2.2.2. Phân hoạch vành đa thức ............................................................. 55 2.3. XÂY DỰNG M-DÃY LỒNG GHÉP TRÊN VÀNH ĐA THỨC CÓ HAI LỚP KỀ CYCLIC ....................................................................................... 61 2.3.1. Vành đa thức có hai lớp kề .......................................................... 61 2.3.2. M-dãy xây dựng trên vành đa thức.............................................. 63 2.3.3. Xây dựng M-dãy lồng ghép từ các cấp số nhân cyclic trên vành đa thức có hai lớp kề ...................................................................................... 64 v 2.4. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC ................ 71 2.4.1. Vấn đề mã hóa ............................................................................. 71 2.4.2. Xây dựng hệ mật dùng cấp số nhân cyclic .................................. 76 2.5. KẾT LUẬN CHƯƠNG 2 ............................................................... 82 CHƯƠNG 3. HÀM BĂM XÂY DỰNG TRÊN CẤP SỐ NHÂN CYCLIC ....... 83 3.1. CÁC HÀM BĂM HỌ MD4 ........................................................... 83 3.1.1. Cấu trúc........................................................................................ 83 3.1.2. Mở rộng thông báo ...................................................................... 87 3.1.3. Các bước mã hóa ......................................................................... 89 3.2. XÂY DỰNG HÀM BĂM MỚI TRÊN CÁC CẤP SỐ NHÂN CYCLIC ... 94 3.2.1. Sơ đồ khối mật mã trong hàm băm.............................................. 94 3.2.2. Các đánh giá kết quả mô phỏng hàm băm mới ......................... 100 3.3. KẾT LUẬN CHƯƠNG 3........................................................................... 101 KẾT LUẬN VÀ KIẾN NGHỊ .............................................................................. 102 DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN ÁN ........... 104 TÀI LIỆU THAM KHẢO .................................................................................... 105 PHỤ LỤC A: THÔNG SỐ CỦA MỘT SỐ HÀM BĂM .................................... 109 PHỤ LỤC B: CÁC CHƯƠNG TRÌNH TÍNH TOÁN VÀ MÔ PHỎNG ........... 122 vi DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT AES Advanced Encryption Standard ANSI CAST American National Standards Institute CBC Carlisle Adams and Stafford Tavares Cipher Block Chaining CFB Cipher Feedback Block CGP Cấp số nhân cyclic (Cyclic Geometic Progressions) CMG CRC Nhóm nhân cyclic (Cyclic Multiplicate Group) Cyclic Redundancy Check CRF Collision Resistant Function CRHF Collision Resistant Hash Function CS Chu trình d0 Khoảng cách Hamming deg DEA Bậc của đa thức (Degree) Data Encryption Algorithm DES Chuẩn mã dữ liệu (Data Encryption Standard) e( x) Đa thức lũy đẳng ECB Electronic Codebook F G GF(p) Trường (Field) h Hàm băm (Hash) I IDEA Ideal International Data Encryption Algorithm IV Initial Value MAC Message Authentication Code MDC Manipulation Detection Code MD-x NESSIE Message Digest x Nhóm (Group) Trường đặc số p New European Schemes for Signatures, Integrity and Encryption vii NIST National Institute for Standards and Technology (US) OFB Output Feedback ord OWF Cấp của đa thức (Order) One-Way Function OWHF One-Way Hash Function R RIPE Vành (Ring) Race Integrity Primitives Evaluation RSA Rivest Shamir Adleman SHA TDEA Secure Hash Algorithm UOWHF VEST Triple Data Encryption Algorithm Universal One-Way Hash Function Very Efficient Substitution Transposition W Trọng số (Weight) Z2 [ x]/ x n  1 Vành đa thức trên GF2 viii DANH MỤC CÁC BẢNG Bảng 1. Một số hàm băm ......................................................................................... 3 Bảng 1.1. Trạng thái của các vector đầu ra M-dãy ................................................ 22 Bảng 1.2. Các đặc tính của dãy tuyến tính có chu kỳ 2m-1 .................................... 26 Bảng 1.3. Bảng IP và IP-1 ....................................................................................... 28 Bảng 1.4. Độ an toàn mục tiêu của hàm băm ......................................................... 43 Bảng 2.1. Số kiểu phân hoạch không suy biến M của một số vành ....................... 57 Bảng 2.2. Tổng số các kiểu phân hoạch của vành Z2 [ x]/ x n  1 ........................... 58 Bảng 2.3. M-dãy xây dựng trên vành Z2 [ x] / x15  1 .................................................. 63 Bảng 2.4. Các tam thức cấp cực đại 4095 (32.5.7.13) trên vành x13 + 1 ................ 68 Bảng 2.5. Một số phần tử của M-dãy trên vành x13+1 ........................................... 69 Bảng 2.6. M-dãy với chiều dài 4095 theo phân hoạch cực đại .............................. 69 Bảng 2.7. Số lượng M-dãy lồng ghép với một vài giá trị n khác nhau .................. 70 Bảng 2.8. Bảng hoán vị ban đầu (IP) ..................................................................... 78 Bảng 2.9. Bảng hoán vị đảo (IP-1) .......................................................................... 78 Bảng 2.10. Khoảng cách Hamming dH(C1,Ci) giữa các cặp bản mã khi các bản rõ khác nhau 1 bit, dH(M1,Mi) = 1, với cùng một khóa K ................................... 80 Bảng 2.11. Khoảng cách Hamming dH(C1,Ci) giữa các cặp bản mã khi các khóa khác khóa K1 2 bit dH(K1, Ki)=2 với cùng một bản rõ M ............................... 81 Bảng 3.1. Thông số của các hàm băm họ MD4 ..................................................... 85 Bảng 3.2. Ký hiệu các thông số và các biến ........................................................... 86 Bảng 3.3. Khoảng cách Hamming dH(MD1, MDi) khi các khối dữ liệu khác khối ban đầu 1 bit ................................................................................................... 97 Bảng 3.4. Khoảng cách Hamming dH(MD1, MDi) giữa các cặp giá trị băm khi các khóa khác khóa K1 2 bit.................................................................................. 99 Bảng 3.5. Tính khoảng cách Hamming trung bình khi thay đổi khóa K và thay đổi bản tin rõ. ...................................................................................................... 100 ix DANH MỤC CÁC HÌNH VẼ Hình 1.1. Sơ đồ khối chức năng hệ mật khóa bí mật ............................................... 8 Hình 1.2. M-dãy tạo từ thanh ghi dịch phản hồi tuyến tính LFSR ........................ 22 4 Hình 1.3. Mạch tạo M-dãy từ đa thức g(x) = 1+x+x ........................................... 23 Hình 1.4. Bộ tạo dãy Gold đối với g1(d) = d3 + d +1 và g2(d) = d3 + d2 +1............ 24 Hình 1.5. Sơ đồ mã hóa DES ................................................................................. 27 Hình 1.6. Mô tả hàm f trong DES .......................................................................... 28 Hình 1.7. Các bước tạo khóa cho các vòng mã hóa của DES ................................ 29 Hình 1.8. Sơ đồ khối chức năng hệ mật khóa công khai ........................................ 30 Hình 1.9. Phân loại hàm băm ................................................................................. 36 Hình 1.10. Các sơ đồ hàm băm đơn a) Matyas-Mayer–Oseas; b) Davies-Mayer và c) Miyaguchi – Preneel ...................................... 37 Hình 1.11. Thuật toán MDC-2 ............................................................................... 39 Hình 1.12. Thuật toán MDC-4 ............................................................................... 40 Hình 1.13. Sơ đồ Miyaguchi – Preneel .................................................................. 41 Hình 1.14. Kiểm tra tính toàn vẹn bằng MAC ....................................................... 45 Hình 1.15. Kiểm tra tình toàn vẹn dùng MDC và thuật toán mã hóa .................... 45 Hình 1.16. Kiểm tra tính toàn vẹn dùng MDC và kênh an toàn ............................ 46 Hình 1.17. Quá trình tạo chữ ký số và kiểm tra chữ ký số ..................................... 47 Hình 1.18. Sơ đồ chữ ký số dùng RSA .................................................................. 47 Hình 1.19. Sơ đồ chữ ký số dùng RSA và có bảo mật thông báo .......................... 48 Hình 2.1. Mã hóa và giải mã xây dựng trên cấp số nhân cyclic ............................ 71 Hình 2.2. Sơ đồ thiết bị mã hoá .............................................................................. 75 Hình 2.3. Sơ đồ thiết bị giải mã ............................................................................. 75 Hình 2.4. Sơ đồ mạng thay thế Feistel ................................................................... 76 Hình 2.5. Sơ đồ mã hóa khối E .............................................................................. 77 Hình 2.6. Sơ đồ khối mã hóa , với khóa K1  1  x 4  x 5 ..................................... 79 Hình 3.1. Tương tác giữa mở rộng thông báo và các thao tác bước ...................... 83 Hình 3.2. Một bước mã hóa của MD5 ................................................................... 92 Hình 3.3. Sơ đồ thực hiện hàm băm ....................................................................... 95 Hình 3.4. Sơ đồ bộ mã hóa khóa E với khóa K1 .................................................... 95 1 PHẦN MỞ ĐẦU 1. MỞ ĐẦU Trong sự phát triển của xã hội loài người, kể từ khi có sự trao đổi thông tin, thì an toàn thông tin trở thành một nhu cầu gắn liền với nó. Từ thủa sơ khai, an toàn thông tin được hiểu đơn giản là giữ bí mật và điều này được xem như một nghệ thuật chứ không phải là một ngành khoa học. Với sự phát triển của khoa học kỹ thuật và công nghệ, cùng với các nhu cầu đặc biệt có liên quan tới an toàn thông tin, ngày nay cần có các yêu cầu kỹ thuật đặc biệt trong việc đảm bảo an toàn thông tin, các kỹ thuật đó bao gồm: Kỹ thuật mật mã (Cryptography); kỹ thuật ngụy trang (Steganography); kỹ thuật tạo bóng mờ (Watermarking – hay thủy vân). Hiện nay việc trao đổi thông tin thương mại trên Internet có nhiều nguy cơ không an toàn do thông tin có thể bị lộ hay bị sửa đổi. Nói chung, để bảo vệ các thông tin khỏi sự truy cập trái phép cần phải kiểm soát được những vấn đề như: thông tin được tạo ra, lưu trữ và truy nhập như thế nào, ở đâu, bởi ai và vào thời điểm nào. Để giải quyết các vấn đề trên, kỹ thuật mật mã hiện đại phải đảm bảo các dịch vụ an toàn cơ bản: (1) bí mật (Confidential); (2) xác thực (Authentication); (3) đảm bảo tính toàn vẹn (Integrity), và để thực hiện các nhiệm vụ này người ta sử dụng hàm băm mật mã (Cryptographic Hash Function). 2. TÌNH HÌNH NGHIÊN CỨU Cho đến nay các nghiên cứu về hàm băm được chia thành hai loại: hàm băm không khóa và hàm băm có khóa. Thông thường các hàm băm đều xây dựng dựa trên mật mã khối với hai phương pháp chính là Mã phát hiện sửa đổi (MDCManipullation Detection Code) và Mã xác thực thông báo (MAC-Message Authentication Code). 2 Hiện nay trên thế giới có khá nhiều hệ mật mã khối khóa bí mật đã được nghiên cứu sử dụng cho các lược đồ xây dựng hàm băm, điển hình là các hệ mật sau: DES, IDEA, TDEA, AES, CAST,… Những nghiên cứu về các hệ mật này đã xuất hiện trong rất nhiều công trình từ rất nhiều năm qua, tuy nhiên chúng đã được tổng kết trong các công trình sau [19], [20], [25], [28], [31], [33]. Các sơ đồ mã hóa thường sử dụng một số lưu đồ như: Feistel cân bằng (như trong DES), Feistel không cân bằng 4 nhánh, Lai-Massey, các mạng thay thế hoán vị… Một hàm băm mật mã học là một hàm h( x ) phải có các tính chất sau [24], [25], [26]:  Tính chất nén  Tính chất dễ tính toán.  Kháng tiền ảnh.  Kháng tiền ảnh thứ hai.  Kháng va chạm. Các lược đồ được sử dụng để xây dựng hàm băm phổ biến bao gồm [4], [15], [22], [29], [37]:  Matyas – Mayer – Oseas (M-M-O).  Davies – Mayer (D-M).  Miyaguchi – Preneel (M-P).  MDC-2  MDC-4  MAC… Cho đến nay đã có nhiều nghiên cứu về hàm băm trên thế giới, các nghiên cứu tập trung xây dựng các hàm băm có độ bảo mật tốt và đặc biệt là khả năng kháng va chạm, thông thường để có được các tính chất này người ta thường phát triển các thuật toán mã hóa, các các phép toán trong hàm mã hóa và tăng chiều dài mã băm… Một số hàm băm cho trong bảng 1 dưới đây. Bảng 1: Một số hàm băm 3 TT Thuật toán Kích thước đầu ra (bit) Xung đột 256/224/192/160/128 Có 1 HAVAL 2 MD2 128 Khả năng lớn 3 MD4 128 Có 4 MD5 128 Có 5 PANAMA 256 Có lỗi 6 RIPEMD 128 Có 7 RIPEMD-128/256 128/256 Không 8 RIPEMD-160/256 160/256 Không 9 SHA-0 160 Không 10 SHA-1 160 Có lỗi 11 SHA-256/224 256/244 Không 12 SHA-512/384 512/384 Không 13 Tiger 192/160/128 192/160/128 Không 14 VEST-4/8 160/256 Không 15 VEST-16/32 320/256 Không 16 WHIRLPOOL 512 Không SHA-1, MD5, và RIPEMD-160 nằm trong số các thuật toán băm được dùng rộng rãi nhất của năm 2005. Tháng 8 năm 2004, các nhà nghiên cứu đã tìm được các điểm yếu của một loạt hàm băm, trong đó có MD5, SHA-0 và RIPEMD. Tháng 2 năm 2005, người ta ghi nhận một tấn công đối với SHA-1. Tháng 8 năm 2005 người ta lại ghi nhận một tấn công khác đối với SHA-1. Các hàm băm SHA-1, MD5, RIPEMD đều thuộc họ MD4. Cấu trúc và thuật toán mã hóa của họ MD4 khá phức tạp (được trình bày trong chương 3 của luận án) và trải qua nhiều bước như: mở rộng thông báo đầu vào (theo kiểu hoán vị 4 vòng hoặc đệ quy), các bước mã hóa sử dụng các phép toán Boolean, phép cộng số tự nhiên theo modulo, phép dịch và quay bit, tổ hợp mã băm đầu ra với vector khởi tạo IV…[23], [24]. Ở Việt Nam việc nghiên cứu các hệ mật cũng đã rất phát triển từ nhiều năm qua, tuy nhiên việc sử dụng các hệ mật này cho các lược đồ xây dựng hàm băm còn khá mới mẻ. Cũng có một số công trình nghiên cứu về hệ mật [13], [14] và xây dựng hạ tầng khóa công khai phục vụ thương mại điện tử [3]. 3. LÝ DO CHỌN ĐỀ TÀI Việc sử dụng cấu trúc nhóm nhân cyclic và cấp số nhân cyclic trên vành đa thức trong việc tạo mã sửa sai trong thời gian qua ở Việt nam đã có các kết quả đáng khích lệ [2,] [6], [7], [8], [9], [10], [11], [12], [13], [14], bởi một số lý do: cấu trúc đại số chặt chẽ, số lượng cấp số nhân trên vành đa thức nhiều (thuận lợi cho việc tạo khóa trong các hệ mật), mạch điện phần cứng thực hiện khá dễ dàng (thuận lợi cho việc áp dùng vào thực tế). Trên cơ sở đó phân tích các hàm băm hiện có tác giả thấy rằng, mặc dù các hàm băm có tính chất tốt nhưng lại có nhược điểm là phức tạp dẫn tới yêu cầu về tài nguyên tính toán và thời gian tính toán. Với các ưu điểm của cấu trúc của cấp số nhân cyclic như đề cập ở trên tác giả nhận thấy việc sử dụng cấu trúc này vào việc xây dựng các hệ mật và các hàm băm là hướng nghiên cứu mở, đây là một vấn đề cần thiết trong quá trình phát triển lý thuyết mật mã nói chung và xây dựng các hàm băm mới nói riêng ở Việt Nam. 4. MỤC TIÊU NGHIÊN CỨU  Khảo sát đánh giá hệ mật khối sử dụng cho lược đồ hàm băm.  Xây dựng hệ mật trên các cấp số nhân cyclic trên vành đa thức.  Xây dựng các hàm băm mới sử dụng hệ mật dựa trên các cấp số nhân cyclic trên vành đa thức. 5  Viết các chương trình phần mềm mô phỏng, thử nghiệm và đánh giá kết quả đã nghiên cứu. 5. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU Luận án thuộc phạm vi lý thuyết cơ sở, tập trung nghiên cứu các thuật toán mật mã hóa và sử dụng chúng trong lược đồ xây dựng các hàm băm. Các thuật toán mã hóa và sơ đồ tạo khóa trong các sơ đồ mã hóa được xây dựng trên cấu trúc cấp số nhân cyclic, đây là một cấu trúc đại số chặt chẽ được xây dựng trên cơ sở là nhóm nhân cyclic trên vành đa thức. 6. PHƯƠNG PHÁP NGHIÊN CỨU Phương pháp nghiên cứu của đề tài là phân tích và tổng hợp dựa vào các công cụ toán học, đặc biệt là đại số đa thức, lý thuyết thông tin và mật mã, lý thuyết xác xuất... cùng với sự hỗ trợ tính toán của máy tính và các chương trình phần mềm mô phỏng để thử nghiệm đánh giá. 7. Ý NGHĨA KHOA HỌC VÀ THỰC TIÊN CỦA ĐỀ TÀI Những kết quả trong luận án này là một đóng góp nhỏ bé vào việc phát triển lý thuyết mật mã nói chung và các hàm băm nói riêng. Các nghiên cứu trong luận án đưa ra được một phương pháp xây dựng mật mã khối và một số hàm băm trên cơ sở là các cấp số nhân cyclic của vành đa thức. 6 CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ HỌC 1.1. CÁC KHÁI NIỆM CƠ BẢN Mật mã học là một bộ phận của khoa học mật mã (Cryptology), được chia thành 2 bộ phận chính [4]: + Mật mã học (Cryptography): chia thành 3 nội dung:  Mật mã khóa bí mật (Khóa đối xứng)  Mật mã khóa công khai (khóa bất đối xứng)  Hàm băm, xác thực và chữ ký số + Phân tích mật mã (Cryptonalys): Dành riêng cho các nhà nghiên cứu chuyên sâu về mật mã, chuyên nghiên cứu tìm hiểu các phương pháp thám mã:  Phương pháp tấn công tổng lực (tìm khóa vét cạn)  Phương pháp thống kê  Phương pháp phân tích cấu trúc… Trong lý thuyết mã mã hóa nguồn và mã sửa sai khâu mã hóa (coding) thường chỉ có đầu vào là bản tin và đầu ra là bản mã (và ngược lại với khâu giải mã (decoding)). Tuy nhiên với mật mã học thì hai khâu này có một sự khác biệt đó là đầu vào của mã hóa (giải mã) ngoài bản tin ra còn có thêm khóa (K). * Mã hóa (Encryption): Ta có: C  EK  M  hay C  E  M , K  M Encryption C K * Giải mã (Decryption) C Ta có: M  EK1  C   DK  C   D  C, K  Decryption K Trong đó: M – bản rõ; C – bản mã; K – khóa * Các phương pháp xử lý thông tin số trong các hệ thống mật mã bao gồm: + Mật mã khóa bí mật (khóa đối xứng): M 7 Với hệ mật này, việc mã hóa và giải mã sử dụng chung một khóa, do đó hai bên liên lạc phải thống nhất và bảo mật khóa trước khi truyền tin. Các thuật toán mã hóa trong hệ mật khóa bí mật thường sử dụng các phương pháp sau:     Hoán vị. Thay thế. Xử lý bit (chủ yếu trong các ngôn ngữ lập trình). Phương pháp hỗn hợp (điển hình là chuẩn mã hóa dữ liệu – DES). + Mật mã khóa công khai (khóa không đối xứng): Thông thường mỗi bên liên lạc tự tạo cho mình một cặp khóa Công khai và bí mật, khóa công khai dùng để mã hóa bản tin và khóa này được công khai trên mạng, còn khóa bí mật dùng để giải mã (chỉ có bên nhận tin lưu trữ). Các thuật toán mã hóa công khai cho đến nay được xây dựng theo một trong năm bài toán một chiều cơ bản đó là:      Bài toán logarit rời rạc Bài toán phân tích thừa số Bài toán xếp ba lô Bài toán mã sửa sai Bài toán trên đường cong elliptic + Mật mã khối: Trong các hệ mật mã khối quá trình xử lý thông tin được thực hiện theo các khối bit có độ dài xác định. + Mật mã dòng: Trong các hệ mật mã dòng quá trình xử lý thông tin thực hiện trên từng bit. + Độ phức tạp tính toán: - Độ phức tạp tính toán P (theo thời gian đa thức) các bài toán này là khả thi và khá đơn giản. - Độ phức tạp NP: NP là ký hiệu lớp các bài toán giải được bằng thuật toán không tất định (NonDeterminal) trong thời gian đa thức (Polynomial). Bài toán thuộc lớp NP thường khó giải và khá phức tạp. 8 1.2. CÁC HỆ MẬT KHÓA BÍ MẬT 1.2.1. Sơ đồ khối chức năng hệ mật khóa bí mật Thám mã Bản rõ M Nguồn tin (Alice) Bản mã C Bộ mã hoá K K E Bản mã C Kênh mở (không an toàn) (Oscar) Bản rõ M Bộ giải mã Nhận tin (Bob) Kênh an toàn KD Nguồn khoá Hình 1.1. Sơ đồ khối chức năng hệ mật khóa bí mật Một hệ mật là một bộ gồm 5 tham số P, C, K, E, D thoả mãn các điều kiện sau [4]: a) b) c) d) P là một tập hữu hạn các bản rõ có thể. C là một tập hữu hạn các bản mã có thể. K là một tập hữu hạn các khoá có thể (không gian khoá). Đối với mỗi k  K có một quy tắc mã e k  E ek : P  C và một quy tắc giải mã tương ứng d k  D dk : C  P sao cho: d k e k x   x với  x  P . 1.2.2. Các hệ mật thay thế 1.2.2.1. Các hệ mật thay thế đơn biểu a) Mật mã dịch vòng (MDV) Giả sử P  C  K  Z26 với 0  k  25 , ta định nghĩa: Mã hóa: C  M  K mod n Giải mã: M  C  K mod n 9 Ví dụ 1.1: Với văn bản tiếng Anh, n  26 hoặc 27, như vậy M , C, K  Z26 hoặc Z27 Ta sử dụng MDV (với modulo 26) để mã hoá một văn bản tiếng Anh thông thường bằng cách thiết lập sự tương ứng giữa các ký tự và các thặng dư theo mod 26 như sau: Ký tự A B C D E F G H I J K L M Mã tương ứng 0 1 2 3 4 5 6 7 8 9 10 11 12 Ký tự N O P Q R S T U V W X Y Z Mã tương ứng 13 14 15 16 17 18 19 20 21 22 23 24 25 Nhận xét: - Khi k  3 , hệ mật này thường được gọi là mã Caesar đã từng được Hoàng đế Caesar sử dụng. - MDV (theo mod 26) là không an toàn vì nó có thể bị thám theo phương pháp tìm khoá vét cạn (thám mã có thể dễ dàng thử mọi khoá dk có thể cho tới khi tìm được bản rõ có nghĩa). Trung bình có thể tìm được bản rõ đúng sau khi thử khoảng 26 2  13 quy tắc giải mã. - Từ ví dụ trên ta thấy rằng, điều kiện cần để một hệ mật an toàn là phép tìm khoá vét cạn phải không thể thực hiện được. Tuy nhiên, một không gian khoá lớn vẫn chưa đủ để đảm bảm độ mật. b. Mã thay thế (MTT). Thay thế một ký tự bằng một ký tự khác trong bảng ký tự. Số khóa có thể có là: K  26! , với các máy tính hiện nay thì chưa đủ an toàn. Khi độ dài bản rõ đủ lớn, có thể sử dụng phương pháp thống kê để thám mã. c) Hệ mật Affine Mã hóa: C  aM  b mod n đây là một phương trình tuyến tính Giải mã: M  a 1 (C  b) mod n Điều kiện tồn tại: để có a 1 thì  a, n   1 10 Nhận xét: Do khoảng trống xuất hiện nhiều trong văn bản, nên khi mã hóa nên mã hóa cả khoảng trống để giảm số lần xuất hiện. d) Mật mã cũi lợn Sử dụng các hình tượng khác nhau không nằm trong bảng ký tự thay thế cho các ký tự. 1.2.2.2. Các hệ mật trên là hệ mật thay thế đa biểu Hệ mậtVigenère Sử dụng phép tương ứng A  0, B  1, , Z  25 mô tả ở trên, ta có thể gắn cho mỗi khoá K một chuỗi ký tự có độ dài m, được gọi là từ khoá. Mật mã Vigenère sẽ mã hoá đồng thời m ký tự: mỗi phần tử của bản rõ tương đương với m ký tự. Ví dụ 1.2: Giả sử bản tin m = 6 và từ khoá là k = CIPHER. Từ khoá này tương ứng với dãy số k = (2, 8, 15, 7, 4, 17). Giả sử bản rõ là: meet me at sunset Ta sẽ biến đổi các phần tử của bản rõ thành các thặng dư theo mod 26, viết chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau: 12 4 4 19 12 4 0 19 18 20 13 18 4 19 Bản rõ 2 8 15 7 4 17 2 8 15 7 4 17 2 8 Khoá 14 12 19 0 16 21 2 1 7 1 17 9 6 1 Bản mã Như vậy, dãy ký tự tương ứng với xâu bản mã sẽ là: OMTA QV CB HBRJGB Ta có thể mô tả mật mã Vigenère như sau: Cho m là một số nguyên dương cố định nào đó. Ta định nghĩa P  C  K   Z 26  Với khoá k   k1 , k2 , ek  x1 , x2 , n , km  , ta xác định: , xm    x1  k1 , x2  k2 , , xm  km  , ym    y1  k1 , y2  k2 , , ym  km  và dk  y1 , y2 , trong đó tất cả các phép toán được thực hiện trong Z26 . 11 Chú ý: Để giải mã, ta có thể dùng cùng từ khoá nhưng thay cho cộng, ta trừ nó theo modulo 26. Ta thấy rằng, số các từ khoá có thể với độ dài m trong mật mã Vigenere là 26m . Bởi vậy, thậm chí với m khá nhỏ, phương pháp tìm kiến vét cạn cũng yêu cầu thời gian khá lớn. Ví dụ, với m = 6 thì không gian khoá cũng có kích thước lớn hơn 3.108 khoá. 1.2.3. Các hệ mật hoán vị (MHV) Khác với MTT, ý tưởng của MHV là giữ các ký tự của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này. Ở đây không có một phép toán đại số nào cần thực hiện khi mã hoá và giải mã. * Hệ mật hoán vị độ dài K Chia bản rõ thành khác khối độ dài K và hoán vị các ký tự trong mỗi khối Ví dụ 1.3: Giả sử m = 6 và khoá là phép hoán vị sau: 1 2 3 4 5 6 3 5 1 6 4 2 Khi đó, phép hoán vị ngược sẽ là: 1 2 3 4 5 6 3 6 1 5 2 4 Giả sử ta có bản rõ: asecondclasscarriageonthetrain Trước tiên, ta nhóm bản rõ thành các nhóm 6 ký tự: a sec on dclass carria geonth etrain Sau đó, mỗi nhóm 6 chữ cái lại được sắp xếp lại theo phép hoán vị π , ta có: EOANCS LSDSAC RICARAOTGHNE RIENAT Cuối cùng, ta có bản mã sau: EOANCSLSDSACRICARAOTGHNERIENAT