Tài liệu Nghiên cứu tìm hiểu hệ mã hóa đồng cấu và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRƯƠNG HÀ DIỆP NGHIÊN CỨU TÌM HIỂU HỆ MÃ HÓA ĐỒNG CẤU VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRƯƠNG HÀ DIỆP NGHIÊN CỨU TÌM HIỂU HỆ MÃ HÓA ĐỒNG CẤU VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS HỒ VĂN CANH THÁI NGUYÊN - 2016 i LỜI CAM ĐOAN Tôi xin cam đoan luận văn “Nghiên cứu tìm hiểu hệ mã hóa đồng cấu và ứng dụng” là công trình nghiên cứu của cá nhân tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của TS Hồ Văn Canh. Các kết quả là hoàn toàn trung thực, toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các nguồn tài liệu được trích dẫn và chú thích đầy đủ. TÁC GIẢ LUẬN VĂN Trương Hà Diệp ii LỜI CẢM ƠN Học viên xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện công nghệ thông tin, các thầy cô giáo Trường Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên đã mang lại cho học viên kiến thức vô cùng quý giá và bổ ích trong suốt quá trình học tập chương trình cao học tại trường. Đặc biệt học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS Hồ Văn Canh đã định hướng khoa học và đưa ra những góp ý, gợi ý, chỉnh sửa quý báu, quan tâm, tạo điều kiện thuận lợi trong quá trình nghiên cứu hoàn thành luận văn này. Cuối cùng, học viên xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đình và người thân đã quan tâm, giúp đỡ và chia sẻ với học viên trong suốt quá trình học tập. Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi những thiếu sót nhất định. Học viên rất mong nhận được những sự góp ý quý báu của thầy cô và các bạn. Thái Nguyên, ngày 28 tháng 12 năm 2016 HỌC VIÊN Trương Hà Diệp iii MỤC LỤC LỜI CAM ĐOAN ...................................................................................... i LỜI CẢM ƠN ........................................................................................... ii MỤC LỤC................................................................................................iii MỤC CÁC HÌNH VẼ, ĐỒ THỊ .............................................................. vi MỞ ĐẦU................................................................................................... 1 CHƯƠNG 1 .............................................................................................. 3 MẬT MÃ CỔ ĐIỂN VÀ HỆ MẬT MÃ ĐỒNG CẤU ............................ 3 1.1 Khái quát hệ mật mã .......................................................................... 3 1.1.1 Khái niệm ........................................................................................ 3 1.1.2 Định nghĩa ........................................................................................ 3 1.1.3 Những yêu cầu đối với hệ mật mã ................................................... 4 1.2 Một số hệ mật mã đơn giản ................................................................. 5 1.2.1 Mã dịch vòng ( shift cipher) ............................................................ 5 1.2.1.1 Định nghĩa (modulo): Định nghĩa về đồng dư ............................. 5 1.2.1.2 Định nghĩa mã dịch vòng:............................................................. 6 1.2.2 Mã thay thế (MTT) ......................................................................... 7 1.2.3 Mã Anffine ........................................................................................ 8 1.2.3.1 Định lý (đồng dư thức) ................................................................. 9 1.2.3.2 Định nghĩa (hàm Euler) ................................................................ 9 1.2.3.3 Định nghĩa (phần tử nghich đảo trong phép nhân) ..................... 10 1.2.4 Mã Vigenere ..................................................................................... 13 1.2.5 Mật mã Hill.................................................................................... 14 1.2.5.1 Khái niệm .................................................................................... 14 iv 1.2.5.2 Định nghĩa (ma trận đơn vị) ....................................................... 14 1.2.5.3 Định nghĩa (Định thức của ma trận) ........................................... 15 1.2.5.4 Định lý (ma trận ngịch đảo) ........................................................ 15 1.2.5.5 Định nghĩa mật mã Hill .............................................................. 15 1.2.6 Mã hóa hoán vị............................................................................... 15 1.2.7 Thám mã ........................................................................................ 17 1.3 Các phương pháp mã hóa đối xứng .................................................. 17 1.3.1 Hệ mã hóa DES .............................................................................. 17 1.3.2 Hệ mã hóa AES .............................................................................. 19 1.3.3 Hệ mã hóa IDEA ............................................................................ 19 1.4 Hệ mã hóa đồng cấu .......................................................................... 21 1.4.1 Định nghĩa ...................................................................................... 21 1.4.1.1 Định nghĩa đồng cấu trong toán học ........................................... 21 1.4.1.2 Định nghĩa hệ mã hoá đồng cấu ................................................. 21 1.4.2 Hệ mã hoá đồng cấu cộng .............................................................. 21 1.4.3 Hệ mã hoá đồng cấu nhân .............................................................. 22 CHƯƠNG 2. HỆ MẬT MÃ DES VÀ HỆ MẬT MÃ IDEA.................. 23 2.1 Hệ mật mã DES ................................................................................ 23 2.1.1 Mô tả hệ mật .................................................................................. 23 2.1.2 Quá trình mã hóa ............................................................................ 24 2.1.2.1 Giai đoạn 1: Cách tính biến x0 ..................................................... 24 2.1.2.2 Giai đoạn 2 .................................................................................. 25 2.1.2.3 Giai đoạn 3 .................................................................................. 32 2.1.2.4 Ví dụ ............................................................................................ 32 2.1.3 Quá trình giải mã .......................................................................... 36 2.1.3.1 Thuật toán ................................................................................... 37 v 2.1.3.2 Chứng minh thuật toán ............................................................... 37 2.1.4 Ưu nhược điểm của hệ mật DES ................................................... 39 2.1.4.1 Ưu điể m....................................................................................... 39 2.1.4.2 Nhược điểm của DES ................................................................ 39 2.1.5 Độ an toàn của DES ....................................................................... 41 2.1.5.1 Các đặc trưng an toàn cơ bản của một hệ mã khối ..................... 41 2.1.5.2 Độ an toàn của DES trước một vài phương pháp tấn công phá mã42 2.2 Hệ mật IDEA .................................................................................... 43 2.2.1 Mô tả hệ mật IDEA ........................................................................ 43 2.2.2 Các phép toán sử dụng trong IDEA ............................................... 43 2.2.3 Mã hoá và giải mã trong IDEA...................................................... 45 2.2.3.1 Mã hoá......................................................................................... 45 2.2.4 Quá trình làm việc của một Modul ................................................ 51 CHƯƠNG 3 NGHIÊN CỨU PHƯƠNG PHÁP MÃ HÓA TỰ ĐỒNG CẤU MỞ RỘNG KHÔNG GIAN KHÓA CHO CÁC MÃ CỔ ĐIỂN . 55 3.1 Mở đầu .............................................................................................. 55 3.2 Nội dung phương pháp ...................................................................... 55 3.2.1 Khái niệm, định nghĩa .................................................................... 55 3.2.2 Thuật toán mã hóa .......................................................................... 55 3.2.3. Ví dụ .............................................................................................. 55 3.2.4 Thuật toán giải mã ......................................................................... 59 3.3 Đánh giá độ an toàn của thuật toán ................................................... 61 3.4 Đề xuất hướng ứng dụng trong thực tế ............................................ 62 4. KẾT LUẬN HƯỚNG NGHIÊN CỨU ............................................... 63 TÀI LIỆU THAM KHẢO ...................................................................... 64 vi MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Kênh liên lạc ............................................................................. 4 Hình 1.2 Mã dịch vòng .............................................................................. 6 Hình 1.3 Mã thay thế ................................................................................. 7 Hình 1.4. Mã hóa Anffine ........................................................................ 12 Hình 1.5. Phương pháp mã hóa Vigenere ................................................ 13 Hình 1.6. Mật mã Hill.............................................................................. 15 Hình 1.7 Mã hoán vị ................................................................................ 16 Hình 2.1 Biểu diễn dãy 64 bit x thành 2 thành phần L và R .................... 23 Hình 2.2 Quy trình phát sinh dãy Li Ri từ dãy Li-1 Ri-1 và khóa Ki ......... 24 Hình 2.3 Sơ đồ của hàm mở rô ̣ng ........................................................... 25 Hình 2.4 Sơ đồ tạo khóa con ................................................................... 26 Hình 2.5 Hàm f ........................................................................................ 28 Hình 2.6 Quá trình mã hóa DES ............................................................. 32 Hình 2.7 Sơ đồ giải mã ........................................................................... 38 Hình 2.8 Cấu trúc Multiplication/Additio (MA) .................................... 44 Hình 2.9 Cấu trúc IDEA ......................................................................... 45 Hình 2.10 Cấu trúc một modul (Modul 1) .............................................. 46 Hình 2.11 Hàm biến đổi của IDEA ....................................................... 47 Hình 2.12 Mã hoá và giải mã trong IDEA.............................................. 49 Hình 2.13 Cấu trúc một modul (Modul 1) .............................................. 51 Hình 3.1: Mã hóa thông điệp .................................................................. 59 Hình 3.2: Giải mã thông điệp.................................................................. 61 vii DANH MỤC BẢNG BIỂU Bảng 2.2 Bảng chọn E bít ....................................................................... 26 Bảng 2.3 Hoán vi ̣IP-1 .............................................................................. 27 Bảng 2.5 Hoán vi ̣PC - 2 ......................................................................... 27 Bảng 2.7 8 hô ̣p S-Box ............................................................................ 31 Bảng 2.8 Phép hoán vị P ......................................................................... 31 Bảng2.9 16 vòng lặp mã ........................................................................ 36 Bảng 2.10 Các khóa yếu của DES ........................................................... 40 Bảng 2.11 Các khóa nửa yếu của DES .................................................... 40 1 MỞ ĐẦU 1. Đặt vấn đề Để đảm bảo các thông tin quan trọng liên quan đến Quốc phòng, An ninh và Thương mại, người ta sử dụng công nghệ mật mã. Có hai loại hệ mật mã được dùng là mật mã khóa đối xứng và mật mã khóa bất đối xứng (Asymmetric key). Hệ thống mật mã bất đối xứng chủ yếu được sử dụng trong môi trường chữ ký số (digital signatures), trong xác thực và trong việc trao đổi các khóa mã đối xứng (symmetric keys). Mật mã đối xứng đóng vai trò quan trọng trong lĩnh vực bảo mật dữ liệu. Mật mã đối xứng có hai loại chính là mật mã hiện đại như mật mã DES (Data Enecryption Standard), mật mã AES (Advanced Encryption Standard), mật mã IDEA (International Data Encryption Algorithm)… và mật mã truyền thống. Mật mã truyền thống rất đơn giản và thuận lợi mà thế giới đã sử dụng hàng thế kỷ trước. một nhược điểm cơ bản của mật mã truyền thống là độ bảo mật không cao vì không gian khóa thường quá nhỏ. Mục đích của đề tài luận văn là nghiên cứu thuật toán mã hóa trên cơ sở kết hợp các mật mã truyền thống thành một hệ mật mã có độ bảo mật cao hơn nhiều trên cơ sở đánh giá tính ngẫu nhiên của nó bằng kỹ thuật của lý thuyết thống kê toán học. 2. Đối tượng và phạm vi nghiên cứu Đề tài luận văn sẽ nghiên cứu và trình bày phương pháp tạo ra một thuật toán mã hóa từ các thuật toán mật mã truyền thống nhưng có độ bảo mật cao hơn. 3. Hướng nghiên cứu của đề tài Đề tài luận văn tập trung tìm hiểu hệ mật mã đồng cấu, trên cơ sở đó xây dựng một hệ mật mã đồng cấu sử dụng các hệ mật mã truyền thống, đưa ra một phương pháp khắc phục được những lỗ hổng về độ an toàn của các hệ mật mã này. 4. Những nội dung nghiên cứu chính Luận văn gồm 3 chương. Chương 1: Mật mã cổ điển và hệ mật mã đồng cấu Chương 2: Hệ mật mã DES và hệ mật IDEA Chương 3: Phương pháp mã hóa tự đồng cấu mở rộng không gian khóa cho các mã cổ điển 2 5. Phương pháp nghiên cứu - Phương pháp tổng hợp, so sánh để tìm ra vấn đề còn tồn tại để nghiên cứu - Phương pháp lập trình để thử nghiệm thuật toán mới. 6. Ý nghĩa khoa học của đề tài Luận văn nghiên cứu phương pháp trao đổi khóa mã đối xứng nói chung không sử dụng mật mã khóa công khai [8]. Thuật toán đơn giản đễ sử dụng và có độ an toàn cao. 3 CHƯƠNG 1 MẬT MÃ CỔ ĐIỂN VÀ HỆ MẬT MÃ ĐỒNG CẤU 1.1 Khái quát hệ mật mã 1.1.1 Khái niệm - Chức năng cơ bản của mật mã là tạo ra khả năng liên lạc trên một kênh không mật cho hai người sử dụng (tạm gọi là A và B) sao cho đối phương (C) không thể hiểu được thông tin được truyền đi. - Kênh liên lạc có thể là một đường dây điện thoại hoặc một mạng máy tính. - Thông tin mà A muốn gửi cho B bản rõ có thể là một văn bản tiếng Anh, các dữ liệu bằng số hoặc bất cứ tài liệu nào có cấu trúc tuỳ ý. - A sẽ mã hoá bản rõ bằng một khóa đã được xác định trước và gửi bản mã kết quả trên kênh. C có bản mã thu trộm được trên kênh song không thể xác định nội dung của bản rõ, nhưng B (người đã biết khoá mã) có thể giải mã và thu được bản rõ. 1.1.2 Định nghĩa Một hệ mật là một bộ 5 (P,C, K, E, D) thoả mãn các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể. 2. C là một tập hữu hạn các bản mã có thể. 3. K (không gian khoá) là tập hữu hạn các khoá có thể. 4. Đối với mỗi k  K có một quy tắc mã ek: P  C và một quy tắc v giải mã tương ứng dk  D. Mỗi ek: P  C và dk: C  P là những hàm sao cho: dk(ek (x)) = x với mọi bản rõ x  P. Trong đó, chúng ta cần lưu ý tính chất 4: Nội dung của nó là nếu một bản rõ x được mã hoá bằng ek và bản mã nhận được sau đó được giải mã bằng dk thì ta phải thu được bản rõ ban đầu x. Giả sử A gửi cho B một thông báo trên một kênh mật, ta có bản rõ cần truyền đi là: x = x1, x2,. . ., xn. Với số nguyên n  1 nào đó. Ở đây mỗi ký hiệu của mỗi bản rõ xi  P, 1  i  n. Mỗi xi sẽ được mã hoá bằng quy tắc mã ek với khoá K xác định trước đó. A tính yi = ek(xi), 1  i  n và bản mã thu được là: 4 y = y1, y2,. . .,yn Khi B nhận đươc y1, y2, . . ., yn anh ta sẽ giải mã bằng hàm giải mã dk và thu được bản rõ gốc x1, x2, . . ., xn. C x A x y Bộ mã hoá Bộ giải mã B k k k Kênh an toàn k Nguồn khoá Hình 1.1. Kênh liên lạc Rõ ràng là trong trường hợp này hàm mã hoá phải là hàm đơn ánh (tức là ánh xạ 1-1), nếu không việc giải mã sẽ không thực hiện được một cách tường minh. Ví dụ: y = ek(x1) = ek(x2), trong đó x1  x2, thì B sẽ không có cách nào để biết liệu bản rõ là x1 hay x2 . 1.1.3 Những yêu cầu đối với hệ mật mã Cung cấp một mức cao về tính bảo mật, tính toàn vẹn, tính chống chối bỏ và tính xác thực:  Tính bảo mật: Bảo đảm bí mật cho các thông báo và dữ liệu bằng việc che dấu thông tin nhờ các kỹ thuật mã hóa.  Tính toàn vẹn (integrity): Bảo đảm với các bên rằng bản tin không bị thay đổi trên đường truyền tin.  Tính không thể chối bỏ (Non-repudiation): Có thể xác nhận rằng tài liệu đã đến từ ai đó, ngay cả khi họ cố gắng từ chối nó.  Tính xác thực (Authentication): Cung cấp hai dịch vụ: o Nhận dạng nguồn gốc của một thông báo và cung cấp một vài bảo đảm rằng nó là đúng sự thực. 5 o Kiểm tra định danh của người đang đăng nhập một hệ thống, tiếp tục kiểm tra đặc điểm của họ trong trường hợp ai đó cố gắng kết nối và giả danh là người sử dụng hợp pháp. 1.2 Một số hệ mật mã đơn giản 1.2.1 Mã dịch vòng ( shift cipher) 1.2.1.1 Định nghĩa (modulo): Định nghĩa về đồng dư Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi đó ta viết a b (mod m) nếu a-b chia hết cho m. Mệnh đề a  b (mod m) được gọi là " a đồng dư với b theo modulo m". Số nguyên m được gọi là mudulus. Bây giờ ta có thể định nghĩa số học modulo m: Zm được coi là tập hợp {0,1,. . .,m-1} có trang bị hai phép toán cộng và nhân. Việc cộng và nhân trong Z m được thực hiện giống như cộng và nhân các số thực ngoài trừ một điểm là các kết quả được rút gọn theo modulo m. Ví dụ tính 11x 13 trong Z16 . Tương tự như với các số nguyên ta có 11 x 13 = 143. Để rút gọn 143 theo modulo 16, ta thực hiện phép chia bình thường: 143 = 8 x 16 + 15, bởi vậy 143 mod 16 = 15 trong Z16. Các định nghĩa trên phép cộng và phép nhân Z m thỏa mãn hầu hết các quy tắc quen thuộc trong số học. Sau đây ta sẽ liệt kê mà không chứng minh các tính chất này: 1. Phép cộng là đóng, tức với bất kì a, b  Zm, a +b  Zm 2. Phép cộng là giao hoán, tức là với a, b bất kì  Zm, a + b = b+ a 3. Phép cộng là kết hợp, tức là với bất kì a, b, c  Zm, (a+b)+c = a+(b+c) 4. 0 là phần tử đơn vị của phép cộng, có nghĩa là  a bất kì  Zm, a+0 = 0+a = a 5. Phép nhân là đóng, tức là với a, b bất kì  Zm, ab  Zm. 6. Phép nhân là giao hoán, nghĩa là với a, b bất kì  Zm, ab = ba 7. Phép nhân là kết hợp, nghĩa là với a, b, c  Zm, (ab)c = a(cb) 8. 1 là phần tử đơn vị của phép nhân, tức là với bất kỳ a  Zm 9. Phần tử nghịch đảo của phép cộng của phần tử bất kì (a  Zm) là m-a, nghĩa là a + (m-a) = (m-a) + a = 0 với bất kì a  Zm. 10. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với a, b, c 6  Zm, (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac) Vì phần tử ngược của phép cộng tồn tại trong Zm nên cũng có thể trừ các phần tử trong Zm. Ta định nghĩa a-b trong Zm là a+m-b mod m. Một cách tương tự có thể tính số nguyên a-b rồi rút gọn theo modulo m. Ví dụ: Để tính 11-18 trong Z31, ta tính 11+13 mod 31 = 24. Ngược lại, có thể lấy 11-18 được -7 rồi sau đó tính -7 mod 31 = 24. 1.2.1.2 Định nghĩa mã dịch vòng: Mã dịch vòng được xác định trên Z26 (do có 26 chữ cái trên bảng chữ cái tiếng Anh) mặc dù có thể xác định nó trên Zm với modulus m tuỳ ý. Dễ dàng thấy rằng, mã dịch vọng (MDV) sẽ tạo nên một hệ mật như đã xác định ở trên, tức là dK (eK(x)) = x với mọi x  Z26. Cho P = C = K = Zn Với mỗi khóa k  K, định nghĩa: ek (x)= (x + k) mod n và dk (y)= (y - k) mod n với x, y  Zn E={ ek , k  K} và D={ dk, k  K} Hình 1.2 Mã dịch vòng Ta sẽ 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 modulo 26 như sau: A  0, B  1, . . ., Z  25. Vì phép tương ứng này còn dùng trong một vài ví dụ nên ta sẽ ghi lại để còn tiện dùng sau này: A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 9 10 11 12 N O P Q R S T U V W X Y Z 8 13 14 15 16 17 18 19 20 21 22 23 24 25 Ví dụ: Dùng khoá k = 9 để mã hoá dòng thư: “toinaydichoi” dòng thư đó tương ứng với dòng số T o i n a y d i c h o i 19 14 8 12 0 24 3 8 2 7 14 8 7 Qua phép mã hoá e9: cộng 9 vào mỗi giá trị rồi rút gọn theo tổng modulo 26 ta có: 2 23 17 22 9 7 12 17 11 16 23 17 c x r w j h m r l q x r Bản mã sẽ là: “qnwcxrcqdkjh” Để giải được bản mã này, trước tiên người nhận biến đổi bản mã này thành dãy các số nguyên rồi trừ đi 9 (rút gọn theo modulo 26) và cuối cùng biến đổi lại dãy này thành các ký tự. Cách đây 2000 năm mã dịch chuyển đã được Julius Ceasar sử dụng Với khoá k = 3 mã dịch vòng được gọi là mã Ceasar. Tập khoá phụ thuộc vào Zm với m là số khoá có thể. Trong tiếng anh tập khóa chỉ có 26 khóa có thể, việc thám mã có thể được thực hiện bằng cách duyệt tuần tự 26 khóa đó, vì vậy độ an toàn của mã dịch chuyển rất thấp. 1.2.2 Mã thay thế (MTT) Trên thực tế mã thay thế có thể lấy cả P và C đều là bộ chữ cái tiếng anh, gồm 26 chữ cái. Ta dùng Z26 trong MDV vì các phép mã và giải mã đều là các phép toán đại số. Tuy nhiên, trong MTT, thích hợp hơn là xem phép mã và giải mã như các hoán vị của các kí tự. Cho P = C = Zn. K là tập hợp tất cả các hoán vị của n phần tử 0, 1, ..., n-1. Như vậy, mỗi khóa   K là một hoán vị của n phần tử 0, 1, ..., n-1. Với mỗi khóa   K, định nghĩa : e (x)= (x) và d(y)=-1(y) với x,y  Zn E={e,  K} và D={D, K} Hình 1.3 Mã thay thế Sau đây là một ví dụ về phép hoán vị ngẫu nhiên  tạo nên một hàm mã hoá (cũng như trước, các kí hiệu của bản rõ được viết bằng chữ thường còn các kí hiệu của bản mã là chữ in hoa). a X n S b N o F c Y p L d A q R e H r C F P S V g O t M h G u U i Z v E j Q w K k W x J l B y D m T Z I 8 Như vậy, e  (a) = X, e  (b) = N,. . . . Hàm giải mã là phép hoán vị ngược. Điều này được thực hiện bằng cách viết hàng thứ hai lên trước rồi sắp xếp theo thứ tự chữ cái. Ta nhận được: A B C D E F G H I J K L M d l r y v O h e z x w p T N O P Q R S T U V W X Y Z b g f j q N m u s k a c i Mỗi khoá của MTT là một phép hoán vị của 26 kí tự. Số các hoán vị này là 26!, lớn hơn 4 x1026 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không thể thực hiện được, thậm chí bằng máy tính. Tuy nhiên, sau này sẽ thấy rằng MTT có thể dễ dàng bị thám bằng các phương pháp khác. Ví dụ: bản rõ: “toinaydichoi” sẽ được mã hoá thành bản mã (với khoá π): “mfzsxdazygfz” Dễ xác định được π-1, và do đó từ bản mã ta tìm được bản rõ. Mã thay thế có tập hợp khoá khá lớn bằng số các hoán vị trên bảng chữ cái, tức số các hoán vị trên Z26, hay là 26! > 4 x 1026. Việc duyệt toàn bộ các hoán vị để thám mã là rất khó, ngay cả đối với máy tính. Tuy nhiên, bằng phương pháp thống kê, ta có thể dễ dàng thám được các bản mã loại này, và do đó mã thay thế cũng không dễ dàng thám được các bản mã loại này, và do đó mã thay thế cũng không thể được xem là an toàn. 1.2.3 Mã Anffine MDV là một trường hợp đặc biệt của MTT chỉ gồm 26 trong số 26! các hoán vị có thể của 26 phần tử. Một trường hợp đặc biệt khác của MTT là mã Affine được mô tả dưới đây. Trong mã Affine, ta giới hạn chỉ xét các hàm mã có dạng: e(x) = ax + b mod 26, a, b  Z26. Các hàm này được gọi là các hàm Affine (chú ý rằng khi a = 1, ta có MDV). Để việc giải mã có thể thực hiện được, yêu cầu cần thiết là hàm Affine phải là đơn ánh. Nói cách khác, với bất kỳ y  Z26, ta muốn có đồng nhất thức sau: ax + b  y (mod 26) phải có nghiệm x duy nhất. Đồng dư thức này tương đương với: 9 ax  y-b (mod 26) Vì y thay đổi trên Z26 nên y-b cũng thay đổi trên Z26. Bởi vậy, ta chỉ cần nghiên cứu phương trình đồng dư: ax  y (mod 26) (y  Z26 ). 1.2.3.1 Định lý (đồng dư thức) Đồng dư thức ax  b mod m chỉ có một nghiệm duy nhất x  Zm với mọi b  Zm khi và chỉ khi UCLN(a,m) = 1. Vì 26 = 2 x 13 nên các giá trị a  Z26 thoả mãn UCLN(a, 26) = 1 là a = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 và 25. Tham số b có thể là một phần tử bất kỳ trong Z26. Như vậy, mã Affine có 13 x 25 = 325 (vì k = 0 bị loại) khoá có thể (dĩ nhiên con số này quá nhỏ để bảo đảm an toàn). Bây giờ ta sẽ xét bài toán chung với modulo m. Ta cần một định nghĩa khác trong lý thuyết số. 1.2.3.2 Định nghĩa (hàm Euler) Giả sử a  1 và m  2 là các số nguyên. UCLN(a,m) = 1 thì ta nói rằng a và m là nguyên tố cùng nhau. Số các số nguyên trong Zm nguyên tố cùng nhau với m thường được ký hiệu là  (m) ( hàm này được gọi là hàm Euler). Một kết quả quan trọng trong lý thuyết số cho ta giá trị của  (m) theo các thừa số trong phép phân tích theo luỹ thừa các số nguyên tố của m. (Một số nguyên p  1 là số nguyên tố nếu nó không có ước dương nào khác ngoài 1 và p. Mọi số nguyên m >1 có thể phân tích được thành tích của các luỹ thừa các số nguyên tố theo cách duy nhất. Ví dụ 60 = 23 x 3 x 5 và 98 = 2 x 72). Ta sẽ ghi lại công thức cho (m) trong định lí sau: n Định lý: Giả sử m   pie i i 1 Trong đó các số nguyên tố pi khác nhau và ei >0, 1  i  n. Khi đó  (m)   ( pie  pie ) i i 1 i 1 10 Định lý này cho thấy rằng, số khoá trong mã Affine trên Z m bằng m x  (m), trong đó  (m) được cho theo công thức trên. (Số các phép chọn của b là m và số các phép chọn của a là  (m) với hàm mã hoá là e(x) = ax + b). Ví dụ, khi m = 60, m=2×2×3×5=22×31×51=>  (60) = (22-21)( 31-30)(51-50) = 16 và số các khoá trong mã Affine là: 16 x 60=960. Một vài tính chất đáng lưu ý của hàm Euler( ). (a) Nếu p là số nguyên tố thì  (p) = p-1. (b) Nếu p, q là hai số nguyên tố khác nhau. Khi đó,  (p.q)=  (p).  (q) = (p-1)(q-1) (c) Giả sử m, n là hai số nguyên dương tùy ý sao cho UCLN(m, n)=1 (tức m, n nguyên tố cùng nhau). Khi đó,  (m,n) =  (m).  (n) Ví dụ m = 15, n = 16 Khi đó  (m,n) =  (15,16) =  (15).  (16) = 8.8 = 64. (d) Nếu m = pk với p là số nguyên tố, thì  (m) =  (pk) = pk-1(p-1). Từ đó suy ra rằng  (2) =1,  (1) = 0 1.2.3.3 Định nghĩa (phần tử nghich đảo trong phép nhân) Giả sử a  Zm. Phần tử nghịch đảo (theo phép nhân) của a là phần tử a-1  Zm sao cho aa-1  a-1a  1 (mod m). Bằng các lý luận tương tự như trên, có thể chứng tỏ rằng a có nghịch đảo theo modulo m khi và chỉ khi UCLN(a, m) =1, và nếu nghịch đảo này tồn tại thì nó phải là duy nhất. Ta cũng thấy rằng, nếu b = a-1 thì a = b-1. Nếu p là số nguyên tố thì mọi phần tử khác không của ZP đều có nghịch đảo. Một vành trong đó mọi phần tử khác 0 đều có nghịch đảo được gọi là một trường. Bằng phương pháp thử và sai ta có thể tìm được các nghịch đảo của các phần tử nguyên tố cùng nhau với 26: 1-1 = 1, 3-1 = 9, 5-1 = 21, 7-1 = 15, 11-1 = 19, 17-1 =23, 25-1 = 25. (Có thể dễ dàng kiểm chứng lại điều này, ví dụ: 7 x 15 = 105  1 mod 26, bởi vậy 7-1 = 15). Xét phương trình đồng dư y  ax+b (mod 26). Phương trình này tương đương với: ax  y - b ( mod 26). 11 Vì UCLN(a, 26) =1 nên a có nghịch đảo theo modulo 26. Nhân cả hai vế của đồng dư thức với a-1 ta có: a-1(ax)  a-1(y-b) (mod 26) Áp dụng tính kết hợp của phép nhân modulo: a-1(ax)  (a-1a)x  1x  x. Kết quả là x  a-1(y-b) (mod 26). Đây là một công thức tường minh cho x. Như vậy hàm giải mã là: d(y) = a-1(y-b) mod 26 Thuật toán Euclide mở rộng : Bổ đề : Nếu UCLN(m,n) = k thì tồn tại 2 số nguyên x, y sao cho mx + ny = k. Thuật toán Euclide mở rộng cho phép tìm được cả 3 số x, y, k khi điều kiện của bồ đề được thỏa mãn. Sau đây là nội dung của thuật toán Euclide mở rộng: Cho m, n là hai số nguyên dương Ta hãy tìm x, y, k sao cho mx + ny = k. Đầu vào (input): m, n (giả sử m>n). Đầu ra: x, y, k. Cho (a1, a2, a3), (b1, b2, b3), (c1, c2, c3) là 3 vectơ Bước 1: (a1, a2, a3) ←(1, 0, m), (b1, b2, b3)←(0, 1, n) Bước 2: Nếu b3 = 0 thì thuật toán dừng và a1, a2, a3 là đáp số của bài toán (tức là x = a1, y = a2, k = a3). Bước 3: Đặt q=[a3/b3]; (là phần nguyên của a3/b3, tức q là số nguyên lớn nhất nhưng không vượt quá a3/b3) và (c1,c2,c3)← (a1,a2,a3) - q(b1,b2,b3); (a1,a2,a3)← ( b1,b2,b3); ( b1,b2,b3)← (c1,c2,c3) và trở về bước 2. Thuật toán dừng sẽ cho: a1 = x, a2 = y, a3 = k Ví dụ1: Cho m = 42, n = 4 Ta có bảng quá trình tính toán sau đây: q a1 a2 a3 b1 b2 b3 c1 c2 4 1 -10 2 -2 21 10 1 0 42 0 1 2 0 1 4 1 -10 2 1 -10 2 -2 21 0 c3 0