Tài liệu Tìm hiểu một số phương pháp thám mã hệ mật mã khóa công khai ứng dụng trong bảo mật dữ liệu

i ®¹i häc th¸i nguyªn Tr-êng ®¹i häc C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG VŨ QUỐC THỊNH TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP THÁM MÃ HỆ MẬT MÃ KHÓA CÔNG KHAI ỨNG DỤNG TRONG BẢO MẬT DỮ LIỆU LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH th¸i nguyªn - n¨m 2014 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ ii ®¹i häc th¸i nguyªn Tr-êng ®¹i häc C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG VŨ QUỐC THỊNH TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP THÁM MÃ HỆ MẬT MÃ KHÓA CÔNG KHAI ỨNG DỤNG TRONG BẢO MẬT DỮ LIỆU LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 Ngƣời hƣớng dẫn khoa học: TS. NGUYỄN DUY MINH Thái Nguyên, 2014 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ iii LỜI CẢM ƠN Lời đầu tiên, em xin đƣợc gửi lời cảm ơn sâu sắc đến TS.Nguyễn Duy Minh, ngƣời thầy đã giúp đỡ em trong suốt quá trình làm khóa luận, đồng thời cũng là ngƣời thầy đã hƣớng dẫn em những bƣớc đi đầu tiên để khám phá một lĩnh vực đầy bí ẩn và thách thức – lĩnh vực an toàn và bảo mật dữ liệu. Em xin đƣợc cảm ơn các thầy, các cô đã giảng dạy em trong suốt quá trình học tập. Những kiến thức mà các thầy các cô đã dạy sẽ mãi là hành trang giúp em vững bƣớc trong tƣơng lai. Em cũng xin đƣợc gửi lời cảm ơn đến tập thể lớp CK11G, một tập thể lớp đoàn kết với những ngƣời bạn không chỉ học giỏi mà còn luôn nhiệt tình, những ngƣời bạn đã giúp đỡ em trong suốt quá trình học tập. Cuối cùng em xin đƣợc gửi lời cảm ơn sâu sắc tới gia đình em, những ngƣời luôn kịp thời động viên, khích lệ em, giúp đỡ em vƣợt qua những khó khăn trong cuộc sống. Thái Nguyên, tháng 08 năm 2014 Học viên Vũ Quốc Thịnh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ iv ĐỊNH NGHĨA, VIẾT TẮT Advanced Encryption Standard (AES) Tiêu chuẩn tiên tiến Asymmetric key cryptography Mã hóa bất đối xứng Authentication Tính xác thực Cipher text Bản mã Concatenate frequency of pairs Tần số bộ đôi móc xích Confidentiality Tính bảo mật Cryptannalysis Thám mã Cryptography Mật mã Cryptology Mật mã học Data Encryption Standard (DES) Tiêu chuẩn mã hóa dữ liệu Decryption Giải mã Encryption Mã hóa Frequency Tấn số Integrity Tính toàn vẹn Key seed Mầm khóa Most Likelihood Ratio (MLR) Tỷ số hợp lý cực đại Non – repudation Tính không thể chối bỏ Plain text Bản rõ Private key Khóa bí mật Public key Khóa công khai Relative frequency Tần số tƣơng đối Rivest, Shamir, & Adleman (RSA) Symmetric - key cryptography Mã hóa đối xứng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ v MỤC LỤC LỜI CẢM ƠN .................................................................................................................. i ĐỊNH NGHĨA, VIẾT TẮT ............................................................................................ iv MỤC LỤC ....................................................................................................................... v DANH MỤC HÌNH VẼ...............................................................................................viii LỜI NÓI ĐẦU................................................................................................................. 1 CHƢƠNG 1: TỔNG QUAN VỀ MẬT MÃ KHÓA CÔNG KHAI VÀ THÁM MÃ . 3 1.1. Giới thiệu..........................................................................................................3 1.2. Các khái niệm cơ bản .......................................................................................3 1.2.1. Mật mã ......................................................................................................3 1.2.2. Mật mã học ................................................................................................4 1.2.3. Bản rõ ........................................................................................................4 1.2.4. Bản mã ......................................................................................................4 1.2.5. Mã hóa .......................................................................................................4 1.2.6. Giải mã ......................................................................................................4 1.2.7. Khái niệm hệ mật mã ................................................................................5 1.3. Phân loại các hệ mật mã ...................................................................................6 1.3.1. Mã hóa đối xứng .......................................................................................6 1.3.2. Mã hóa bất đối xứng .................................................................................7 1.4. Tiêu chuẩn đánh giá hệ mật mã......................................................................10 1.5. Hệ mật mã RSA .............................................................................................10 1.5.1. Mô tả hệ mật RSA ...................................................................................11 1.5.2. Thực thi hệ RSA......................................................................................13 1.5.3. Độ an toàn của hệ RSA ...........................................................................14 1.6. Thám mã .........................................................................................................15 1.6.1. Khái niệm ................................................................................................15 1.6.2. Các bƣớc cơ bản để tiến hành thám mã ..................................................19 1.7. Kết luận ..........................................................................................................26 CHƢƠNG 2: CÁC PHƢƠNG PHÁP THÁM MÃ HỆ MẬT MÃ KHÓA CÔNG KHAI ............................................................................................................................. 27 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ vi 2.1. Tính an toàn của hệ mật mã ...........................................................................27 2.1.1. An toàn vô điều kiện ...............................................................................27 2.1.2. An toàn đƣợc chứng minh .......................................................................27 2.1.3. An toàn tính toán .....................................................................................27 2.2. Các kiểu thám mã ...........................................................................................28 2.2.1. Tấn công dạng 1: Tìm cách xác định khóa bí mật ..................................28 2.2.2. Tấn công dạng 2: Tìm cách xác định bản rõ ...........................................30 2.3. Một số sơ hở dẫn đến tấn công hệ mật RSA ..................................................32 2.3.1. Biết (n) tìm đƣợc p, q ............................................................................33 2.3.2. Biết số mũ giải a ......................................................................................33 2.3.3. Giao thức công chứng .............................................................................34 2.3.4. Giao thức số mũ công khai nhỏ ..............................................................35 2.3.5. Giao thức số mũ bí mật nhỏ ....................................................................37 2.3.6. Trƣờng hợp các tham số p-1 và q-1 có các ƣớc nguyên tố nhỏ ..............39 2.4. Kết luận ..........................................................................................................42 CHƢƠNG 3: THỬ NGHIỆM PHƢƠNG PHÁP THÁM MÃ VỚI HỆ RSA ............ 44 3.1. Mô tả bài toán tấn công RSA sử dụng modul chung .....................................44 3.2. Thuật toán tấn công giao thức modul n chung ...............................................44 3.2.1. Kiểu tấn công thứ nhất: Tấn công dựa trên các số mũ mã hóa nguyên tố cùng nhau ..........................................................................................................44 3.2.2. Kiểu tấn công thứ hai: Phân tích số modul n bằng cách tìm căn bậc hai không tầm thƣờng của 1 mod n .........................................................................45 3.2.3. Kiểu tấn công thứ ba: Sử dụng khóa công khai và bí mật của mình để sinh ra khóa bí mật của ngƣời dùng khác .........................................................47 3.3. Thử nghiệm chƣơng trình...............................................................................48 3.3.1. Cơ sở lý thuyết ........................................................................................48 3.2.2. Thuật toán................................................................................................49 3.3.3. Đánh giá kết quả...................................... Error! Bookmark not defined. 3.3.4. Thử nghiệm .............................................................................................51 3.4. Kết luận ..........................................................................................................60 KẾT LUẬN ................................................................................................................... 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ vii TÀI LIỆU THAM KHẢO ............................................................................................ 62 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ viii DANH MỤC HÌNH VẼ Hình 1.1: Quá trình mã hóa và giải mã ........................................................................... 5 Hình 1.2: Mã hóa thông điệp sử dụng khóa công khai P ............................................... 8 Hình 1.3: Giải mã thông điệp sử dụng khóa riêng của ngƣời nhận ............................... 8 Hình 1.4: Mã hóa thông điệp sử dụng khóa bí mật S để mã thông điệp và................... 9 Hình 1.5: Giải mã thông điệp sử dụng khóa bí mật S để giải mã thông điệp và ........... 9 Hình 1.6: Sơ đồ biểu diễn thuật toán mã hóa RSA ...................................................... 13 Hình 3.1: Lƣu đồ giải thuật thám mã RSA ................................................................... 50 Hình 3.2: Giao diện chính của chƣơng trình thám mã RSA ........................................ 52 Hình 3.3: Nhập các tham số RSA ................................................................................ 53 Hình 3.4: Tính khóa bí mật d1, d2 ................................................................................ 54 Hình 3.5: Mã hóa ........................................................................................................... 55 Hình 3.6: Mã hóa thông điệp ........................................................................................ 56 Hình 3.7: Thám mã tìm ra khóa bí mật d1.................................................................... 57 Hình 3.8: Giải mã tìm ra bản rõ theo khóa d1 .............................................................. 58 Hình 3.9: Giải mã tìm ra thông điệp ............................................................................. 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 1 LỜI NÓI ĐẦU Từ khi con ngƣời có nhu cầu trao đổi thông tin, thƣ từ với nhau thì nhu cầu giữ bí mật và bảo mật tính riêng tƣ của những thông tin, thƣ từ đó cũng nảy sinh. Hình thức thông tin trao đổi phổ biến sớm nhất là dƣới dạng các văn bản, để giữ bí mật của thông tin ngƣời ta đã sớm nghĩ đến cách che dấu nội dung các văn bản bằng các biến dạng các văn bản đó để ngƣời ngoài đọc nhƣng không hiểu đƣợc, đồng thời có cách khôi phục lại nguyên dạng ban đầu để ngƣời trong cuộc vẫn hiểu đƣợc; theo cách gọi ngày nay thì dạng biến đổi của văn bản đƣợc gọi là mật mã của văn bản, cách lập mã cho một văn bản đƣợc gọi là phép lập mã, còn cách khôi phục lại nguyên dạng ban đầu gọi là phép giải mã. Phép lập mã và phép giải mã đƣợc thực hiện nhờ một chìa khóa riêng nào đó mà chỉ những ngƣời trong cuộc đƣợc biết và nó đƣợc gọi là khóa lập mã. Ngƣời ngoài dù có lấy đƣợc bản mật mã trên đƣờng truyền mà không có khóa mật mã thì cũng không thể hiểu đƣợc nội dung của văn bản truyền đi. Trong số các phƣơng pháp đảm bảo an toàn thông tin thì phƣơng pháp mật mã hóa (Cryptography) đƣợc sử dụng rộng rãi và đảm bảo an toàn nhất. Tuy nhiên phƣơng pháp mật mã hóa không tốt (mặc dù việc quản lý khóa mã đƣợc giả thiết là an toàn) thì rất nguy hiểm. Vậy làm thế nào để đánh giá đƣợc chất lƣợng của một hệ mã là tốt? Có nhiều phƣơng pháp đánh giá chất lƣợng của một hệ mật nhƣ phƣơng pháp Entropy của Shannon, nhƣng phƣơng pháp tốt nhất và trực quan nhất, đó là phƣơng pháp phân tích trực tiếp bản mã khi không có khóa mã trong tay mà ngƣời ta thƣờng gọi là thám mã (Cryptannalysis). Hiện nay thám mã cũng là một lĩnh vực cũng thƣờng đƣợc quan tâm nghiên cứu nhƣng ít khi đƣợc công khai, hoặc công khai không đầy đủ. Sự hiểu biết về các phƣơng pháp thám mã hiện nay ở trong nƣớc nói chung đang còn rất hạn chế. Tuy đã có nhiều công trình nghiên cứu về thám mã nhƣng việc đƣa ra hệ quy trình thám mã và chƣơng trình thám mã vẫn ở mức độ hẹp và khó khăn trong ứng dụng thực tế. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 2 Xuất phát từ thực tế đó, để góp phần tăng cƣờng độ an toàn cho các hệ mật mã hiện đại nhằm góp phần bảo vệ an ninh thông tin trong tình hình mới nên em đã chọn đề tài “Tìm hiểu một số phương pháp thám mã hệ mật mã khóa công khai ứng dụng trong bảo mật dữ liệu” nhằm nghiên cứu và ứng dụng. Trong khuôn khổ đề tài đƣợc giao, luận văn đƣợc trình bày trong 3 chƣơng. Có phần mở đầu, phần kết luận, phần mục lục, tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày nhƣ sau: Chƣơng 1: “Tổng quan về mật mã khóa công khai và thám mã”. Ở chƣơng này, luận văn trình bày chi tiết về lịch sử cũng nhƣ các khái niệm về các hệ mã thuộc dòng mã truyền thống cũng nhƣ dòng mã đối xứng, mã bất đối xứng giúp chúng ta hiểu cơ sở lý thuyết về các hệ mật mã. Vấn đề thám mã nói chung và thám mã đối với hệ mật RSA cũng đƣợc em trình bày kỹ trong chƣơng này. Chƣơng 2: “Các phƣơng pháp thám mã hệ mật mã khóa công khai”. Trên cơ sở hiểu các hệ mật đƣợc trình bày ở chƣơng 1, để có cái nhìn tổng quan về vấn đề thám mã đối với hệ mật RSA và trên cơ sở trình bày các phƣơng pháp thám mã đã tổng kết lại các phƣơng pháp và đánh giá kết quả của phƣơng pháp nhƣ: các tấn công cơ bản - modul chung, tấn công vào số mũ công khai hoặc số mũ bí mật nhỏ, giao thức công chứng... Chƣơng 3: “Thử nghiệm phƣơng pháp thám mã với hệ RSA”. Qua nghiên cứu các phƣơng pháp thám mã trong chƣơng 2, chƣơng 3 đề xuất phƣơng pháp tấn công giao thức sử dụng hệ mật mã RSA có modul n chung. Để minh chứng cho phƣơng pháp này, luận văn xây dựng thuật toán và cài đặt chƣơng trình thử nghiệm trong hệ bảo mật. Do mức độ phức tạp của công việc thám mã là rất lớn nên bài toán đặt ra với giả thiết ngƣời thám mã biết đƣợc các thông tin và bản mã đƣợc mã hóa bởi RSA từ bản rõ tƣơng ứng là một thông điệp dạng Text. Từ giả thiết này xây dựng thuật toán để xác định khóa mật K đã sử dụng để mã hóa cũng nhƣ tìm ra bản rõ tƣơng ứng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 3 CHƢƠNG 1 TỔNG QUAN VỀ MẬT MÃ KHÓA CÔNG KHAI VÀ THÁM MÃ 1.1. Giới thiệu Mật mã đã đƣợc con ngƣời sử dụng từ lâu đời. Các hình thức mật mã sơ khai đã đƣợc tìm thấy từ khoảng bốn nghìn năm trƣớc trong nền văn minh Ai Cập cổ đại.Trải qua hàng nghìn năm lịch sử, mật mã đã đƣợc sử dụng rộng rãi ở khắp nơi trên thế giới từ Đông sang Tây để giữ bí mật cho việc giao lƣu thông tin trong nhiều lĩnh vực hoạt động giữa con ngƣời và các quốc gia, đặc biệt trong các lĩnh vực quân sự, chính trị, ngoại giao. Mật mã trƣớc hết là một loại hoạt động thực tiễn, nội dung chính của nó là để giữ bí mật thông tin. Ví dụ muốn gửi một văn bản từ một ngƣời gửi A đến một ngƣời nhận B, A phải tạo cho văn bản đó một bản mã mật tƣơng ứng và thay vì gửi văn bản rõ thì A chỉ gửi cho B bản mã mật, B nhận đƣợc bản mã mật và khôi phục lại văn bản rõ để hiểu đƣợc thông tin mà A muốn gửi cho mình. Do văn bản gửi đi thƣờng đƣợc chuyển qua các con đƣờng công khai nên ngƣời ngoài có thể “lấy trộm” đƣợc, nhƣng vì đó là bản mật mã nên không đọc hiểu đƣợc; Còn A có thể tạo ra bản mã mật và B có thể giải bản mã mật thành bản rõ để hiểu đƣợc là do hai ngƣời đã có một thoả thuận về một chìa khóa chung, chỉ với khóa chung này thì A mới tạo đƣợc bản mã mật từ bản rõ và B mới khôi phục đƣợc bản rõ từ bản mã mật. Khóa chung đó đƣợc gọi là khóa mật mã. Để thực hiện đƣợc một phép mật mã, ta còn cần có một thuật toán biến bản rõ cùng với khóa mật mã thành bản mã mật và một thuật toán ngƣợc lại biến bản mật cùng với khóa mật mã thành bản rõ. Các thuật toán đó đƣợc gọi tƣơng ứng là thuật toán lập mã và thuật toán giải mã. Các thuật toán này thƣờng không nhất thiết phải giữ bí mật, mà cái luôn cần đƣợc giữ bí mật là khóa mật mã. Trong thực tiễn, có những hoạt động ngƣợc lại với hoạt động bảo mật là khám phá bí mật từ các bản mã “lấy trộm” đƣợc, hoạt động này thƣờng đƣợc gọi là mã thám hay phá khóa. 1.2. Các khái niệm cơ bản 1.2.1. Mật mã Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 4 Mật mã (Cryptography) là tập hợp mọi phƣơng pháp (hoặc quy tắc) biến đổi nào đó nhằm chuyển các thông báo (messages) dƣới dạng nhận thức đƣợc nội dung (nhƣ chữ viết, tiếng nói, hình vẽ, hình ảnh…) thành dạng bí mật mà những ngƣời ngoài cuộc không hiểu đƣợc nội dung nếu họ không biết đƣợc phƣơng pháp (hoặc quy tắc) biến đổi đó. 1.2.2. Mật mã học Mật mã học (Cryptology) là một bộ môn khoa học chuyên nghiên cứu về mật mã và thám mã. 1.2.3. Bản rõ Ta hiểu bản rõ (Plain text) tức là một bản thông báo có mang nội dung thông tin mà ngƣời đọc có thể hiểu đƣợc nó nói cái gì hoặc là nó có ý nghĩa rõ ràng. Bản rõ (bản thông báo) có thể tồn tại dƣới dạng chữ viết, tiếng nói, hình vẽ, biểu bảng… tƣơng ứng ta sẽ có khái niện mã ký tự, mã thoại, mã fax, mã dữ liệu… Bản rõ thƣờng đƣợc dùng biểu diễn (viết) dƣới dạng một dãy các chữ cái theo quy tắc cú pháp nào đó hoặc ký hiệu thuộc bảng chữ cái A hữu hạn đƣợc xác định trƣớc. Để trình bày, ta ký hiệu M là không gian các bản rõ (message space). Ví dụ: M có thể là gồm dãy nhị phân, các văn bản tiếng Việt, hoặc mã chƣơng trình của máy tính… 1.2.4. Bản mã Bản mã (Cipher text) thƣờng cũng đƣợc biểu diễn dƣới dạng một dãy các ký hiệu có thể cũng thuộc A nhƣng không theo một quy tắc cú pháp nào cả. Ngƣời ta nói rằng đó là dãy ngẫu nhiên. Ta ký hiệu tập tất cả các bản mã ứng với các bản rõ m là C. 1.2.5. Mã hóa Mã hóa (Encryption) là quá trình chuyển đổi thông tin từ bản rõ sang bản mã. Trong quá trình này thông tin trong bản rõ sẽ đƣợc ẩn đi và do đó bất kỹ một ngƣời nào đọc thông điệp này cũng không hiểu đƣợc trừ trƣờng hợp ngƣời đó có thể giải mã (PlainText → CipherText) 1.2.6. Giải mã Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 5 Là quá trình giải mã (Decryption) để lấy lại thông tin ban đầu, ngƣợc với quá trình mã hóa (CipherText → PlainText). 1.2.7. Khái niệm hệ mật mã Hệ mật mã đƣợc định nghĩa là một bộ năm (P, C, K, E, D), trong đó: - P (Plain text) là một tập hợp hữu hạn các các bản rõ có thể, nó đƣợc gọi là không gian bản rõ. - C (Cipher text) tập hữu hạn các bản mã có thể, nó còn đƣợc gọi là không gian các bản mã. Mỗi phần tử của C có thể nhận đƣợc bằng cách áp dụng phép mã hóa Ek lên một phần tử của P, với k ∈ K. - K (Key) là tập hữu hạn các khóa có thể hay còn gọi là không gian khóa. Đối với mỗi phần tử k của K đƣợc gọi là một khóa. Số lƣợng của không gian khóa phải đủ lớn để kẻ địch không có đủ thời gian để thử mọi khóa có thể (phƣơng pháp vét cạn). - E (Encryption) là tập các hàm lập mã - D (Decryption) là tập các hàm giải mã. Với mỗi k ∈ K, có một hàm lập mã ek ∈ E, ek : P → C và một hàm giải mã dk ∈ D, dk: C → P sao cho dk(ek(x)) = x , ∀x ∈ P Hình 1.1: Quá trình mã hóa và giải mã Hệ mật hiện đại cần phải đáp ứng đƣợc những yêu cầu sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 6 - Tính bảo mật (Confidentiality): đảm bảo dữ liệu đƣợc truyền đi một cách an toàn và không bị lộ nếu nhƣ ai đó cố tình muốn có đƣợc thông điệp gốc ban đầu. Chỉ những ngƣời đƣợc phép mới có khả năng đọc đƣợc nội dung thông tin ban đầu. - Tính xác thực (Authentication): giúp cho ngƣời nhận thông điệp các định đƣợc chắc chắn thông điệp mà họ nhận là thông điệp gốc ban đầu. Kẻ giả mạo không thể giả dạng một ngƣời khác hay nói cách khác không thể mạo danh để gửi thông điệp. Ngƣời nhận có khả năng kiểm tra nguồn gốc thông điệp mà họ nhận đƣợc. - Tính toàn vẹn (Integrity): ngƣời nhận thông điệp có thể kiểm tra thông điệp không bị thay đổi trong quá trình truyền đi. Kẻ giả mạo không thể có khả năng thay thế dữ liệu ban đầu bằng dữ liệu giả mạo. - Tính không thể chối bỏ (Non - repudation): ngƣời gửi, ngƣời nhận không thể chối bỏ sau khi đã gửi hoặc nhận thông điệp. 1.3. Phân loại các hệ mật mã Công nghệ thông tin phát triển, việc sử dụng máy tính gia tăng cùng với tốc độ phát triển mạnh mẽ của Internet càng làm tăng nguy cơ bị đánh cắp các thông tin độc quyền. Với mối đe dọa đó có nhiều biện pháp để đối phó song mã hóa là một phƣơng pháp chính để có thể bảo vệ các giá trị của thông tin điện tử. Có thể nói mã hóa là công cụ tự động, quan trọng nhất cho an ninh mạng và truyền thông. Có hai hình thức mã hóa đƣợc sử dụng phổ biến là mã hóa đối xứng (symmetric - key cryptography) và mã hóa bất đối xứng (asymmetric key cryptography). 1.3.1. Mã hóa đối xứng Thuật toán đối xứng hay còn gọi là thuật toán mã hóa cổ điển. Thuật toán này còn có nhiều tên gọi khác nhƣ thuật toán khóa bí mật, thuật toán đơn giản, thuật toán một khóa. Là thuật toán mà tại đó khóa mã hóa có thể tính toán ra đƣợc từ khóa giải mã. Trong rất nhiều trƣờng hợp, khóa mã hóa và khóa giải mã là giống nhau. Ƣu điểm: - Xử lý nhanh Nhƣợc điểm: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 7 - Các phƣơng pháp mã hóa cổ điển đòi hỏi ngƣời mã hóa và ngƣời giải mã phải cùng chung một khóa. Khi đó khóa phải giữ bí mật tuyệt đối, do vậy ta dễ dàng xác định đƣợc một khóa nếu biết khóa kia. - Hệ mã hóa đối xứng không bảo vệ đƣợc sự an toàn nếu có xác suất cao khóa ngƣời gửi bị lộ. Trong hệ khóa phải đƣợc gửi đi trên kênh an toàn nếu kẻ địch tấn công trên kênh này có thể phát hiện ra khóa. - Vấn đề quản lý và phân phối khóa là khó khăn và phức tạp khi sử dụng hệ mã hóa cổ điển. Ngƣời gửi và ngƣời nhận luôn luôn thống nhất với nhau về vấn đề khóa. Việc thay đổi khóa là rất khó và rất dễ bị lộ. - Khuynh hƣớng cung cấp khóa dài mà nó phải đƣợc thay đổi thƣờng xuyên cho mọi ngƣời trong khi vẫn duy trì cả tính an toàn lẫn hiệu quả chi phí sẽ cản trở rất nhiều tới sự phát triển của hệ mật mã cổ điển. 1.3.2. Mã hóa bất đối xứng Để giải quyết vấn đề phân phối và thoả thuận khóa của mật mã khóa đối xứng, năm 1976 Diffie và Hellman đã đƣa ra khái niệm về hệ mật mã khóa công khai và một phƣơng pháp trao đổi công khai để tạo ra một khóa bí mật chung mà tính an toàn đƣợc bảo đảm bởi độ khó của một bài toán toán học cụ thể (là bài toán tính “logarit rời rạc”). Hệ mật mã khóa công khai hay còn đƣợc gọi là hệ mật mã phi đối xứng sử dụng một cặp khóa, khóa mã hóa còn gọi là khóa công khai (publickey) và khóa giải mã đƣợc gọi là khóa bí mật hay khóa riêng (private key). Trong hệ mật này, khóa mã hóa khác với khóa giải mã. Về mặt toán học thì từ khóa công rất khó tính đƣợc khóa riêng. Biết đƣợc khóa này không dễ dàng tìm đƣợc khóa kia. Khóa giải mã đƣợc giữ bí mật trong khi khóa mã hóa đƣợc công bố công khai. Một ngƣời bất kỳ có thể sử dụng khóa công khai để mã hóa tin tức, nhƣng chỉ có ngƣời nào có đúng khóa giải mã mới có khả năng xem đƣợc bản rõ. Ngƣời gửi A sẽ mã hóa thông điệp bằng khóa công của ngƣời nhận và ngƣời nhận B sẽ giải mã thông điệp với khóa riêng tƣơng ứng của mình. Quá trình này đƣợc mô tả trong hình 1.2 và 1.3. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 8 Hình 1.2: Mã hóa thông điệp sử dụng khóa công khai P Hình 1.3: Giải mã thông điệp sử dụng khóa riêng của người nhận Việc phát minh ra phƣơng pháp mã công khai tạo ra một cuộc “cách mạng” trong công nghệ an toàn thông tin điện tử. Nhƣng thực tiễn triễn khai cho thấy tốc độ mã hóa khối dữ liệu lớn bằng các thuật toán mã hóa công khai chậm hơn rất nhiều so với hệ mã hóa đối xứng. Ví dụ, để đạt đƣợc độ an toàn nhƣ các hệ mã đối xứng mạnh cùng thời, RSA đòi hỏi thời gian cho việc mã hóa một văn bản lâu hơn gấp hàng ngàn lần. Do đó, thay bằng việc mã hóa văn bản có kích thƣớc lớn bằng lƣợc đồ khóa công khai thì văn bản này sẽ đƣợc mã hóa bằng một hệ mã đối xứng có tốc độ cao nhƣ DES, IDEA,…sau đó khóa đƣợc sử dụng trong hệ mã đối xứng sẽ đƣợc mã hóa sử dụng mật mã khóa công khai. Phƣơng pháp này rất khả thi trong việc mã và giải mã những văn bản có kích thƣớc lớn nhƣ đƣợc mô tả trong hình 1.4 và 1.5. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 9 Hình 1.4: Mã hóa thông điệp sử dụng khóa bí mật S để mã thông điệp và khóa công khai P để mã khóa bí mật S. Hình 1.5: Giải mã thông điệp sử dụng khóa bí mật S để giải mã thông điệp và khóa riêng P để giải mã khóa bí mật S. Ƣu và nhƣợc điểm của hệ mật mã khóa công khai Vấn đề còn tồn đọng của hệ mật mã khóa đối xứng đƣợc giải quyết nhờ hệ mật mã khóa công khai. Chính ƣu điểm này đã thu hút nhiều trí tuệ vào việc đề xuất, đánh giá các hệ mật mã công khai. Nhƣng do bản thân các hệ mật mã khóa công khai đều dựa vào các giả thiết liên quan đến các bài toán khó nên đa số các hệ mật mã này đều có tốc độ mã dịch không nhanh lắm. Chính nhƣợc điểm này làm cho các hệ mật mã khóa công khai khó đƣợc dùng một cách độc lập. Một vấn đề nữa nảy sinh khi sử dụng các hệ mật mã khóa công khai là việc xác thực mà trong mô hình hệ mật mã đối xứng không đặt ra. Do các khóa mã công khai đƣợc công bố một cách công khai trên mạng cho nên việc đảm bảo rằng “khóa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 10 đƣợc công bố có đúng là của đối tƣợng cần liên lạc hay không?” là một kẽ hở có thể bị lợi dụng. Vấn đề xác thực này đƣợc giải quyết cũng chính bằng các hệ mật mã khóa công khai. Nhiều thủ tục xác thực đã đƣợc nghiên cứu và sử dụng nhƣ Kerberos, X.509… Một ƣu điểm nữa của các hệ mật mã khóa công khai là các ứng dụng của nó trong lĩnh vực chữ ký số, cùng với các kết quả về hàm băm, thủ tục ký để bảo đảm tính toàn vẹn của một văn bản đƣợc giải quyết. 1.4. Tiêu chuẩn đánh giá hệ mật mã Để đánh giá một hệ mật mã ngƣời ta thƣờng đánh giá thông qua các tính chất sau: Độ an toàn: Một hệ mật đƣợc đƣa vào sử dụng điều đầu tiên phải có độ an toàn cao. Ƣu điểm của mật mã là có thể đánh giá đƣợc độ an toàn thông qua độ an toàn tính toán mà không cần phải cài đặt. Một hệ mật đƣợc coi là an toàn nếu để phá hệ mật mã này phải dùng n phép toán. Mà để giải quyết n phép toán cần thời gian vô cùng lớn, không thể chấp nhận đƣợc. Tốc độ mã và giải mã: Khi đánh giá hệ mật mã chúng ta phải chú ý đến tốc độ mã và giải mã. Hệ mật tốt thì thời gian mã và giải mã nhanh. Phân phối khóa: Một hệ mật mã phụ thuộc vào khóa, khóa này đƣợc truyền công khai hay truyền khóa bí mật. Phân phối khóa bí mật thì chi phí sẽ cao hơn so với các hệ mật có khóa công khai. Vì vậy đây cũng là một tiêu chí khi lựa chọn hệ mật mã. 1.5. Hệ mật mã RSA Có nhiều hệ thống khóa công khai đƣợc triển khai rộng rãi nhƣ hệ RSA, hệ ElGamal sử dụng giao thức trao đổi khóa Diffie-Hellman và nổi lên trong những năm gần đây là hệ đƣờng cong Elliptic. Trong số các hệ mật mã trên thì hệ RSA là hệ đƣợc cộng đồng chuẩn quốc tế và công nghiệp chấp nhận rộng rãi trong việc thực thi mật mã khóa công khai. Hệ mật mã RSA, do Rivest, Shamir và Adleman tìm ra, đã đƣợc công bố lần đầu tiên vào tháng 8 năm 1977 trên tạp chí Scientific American. Hệ mật mã RSA đƣợc sử dụng rộng rãi trong thực tiễn đặc biệt cho mục đích bảo mật và xác thực dữ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ 11 liệu số. Tính bảo mật và an toàn của chúng đƣợc bảo đảm bằng độ phức tạp của một bài toán số học nổi tiếng là bài toán phân tích số nguyên thành các thừa số nguyên tố. Hệ mật mã RSA đƣợc sử dụng để cung cấp sự bảo mật và đảm bảo tính xác thực của dữ liệu số. Hiện nay RSA đƣợc sử dụng trong nhiều hệ thống thƣơng mại. Các dịch vụ web server và web browser sử dụng nó để đảm bảo an toàn việc truyền thông web, nó đƣợc sử dụng để đảm bảo bảo mật và xác thực của Email, đảm bảo an toàn cho các phiên truy nhập từ xa và là bộ phận quan trọng của các hệ thống thanh toán thẻ tín dụng điện tử. Tóm lại, RSA thƣờng đƣợc sử dụng trong các ứng dụng cần sự bảo đảm an toàn và bảo mật dữ liệu số. 1.5.1. Mô tả hệ mật RSA Hệ mật mã RSA sử dụng các tính toán trong Zn, trong đó n là tích của hai số nguyên tố phân biệt p, q và (n) = (p-1)(q-1). Mô tả hình thức của hệ mật này nhƣ sau: Hệ mật mã RSA đƣợc mô tả nhƣ sau: Cho n = p*q với p, q là số nguyên tố lớn. Đặt P = C = Zn Chọn b nguyên tố cùng nhau với (n), (n) = (p-1)(q-1) Ta định nghĩa K = {(n, b, a): a*b 1mod (n)} Trong đó (n, b) là công khai, a là bí mật Với mỗi K = (n, a, b), mỗi x ∈ P, y ∈ C, định nghĩa: Hàm mã hóa: y = xb mod n Hàm giải mã: x = ya mod n trong đó (x, y Zn). Các giá trị n, b công khai còn các giá trị p, q, a giữ bí mật. Ta hãy kiểm tra xem các phép mã và giải mã có phải là các phép toán nghịch đảo của nhau hay không. Vì ab 1(mod (n)) nên ta có ab = t. (n) + 1 với một số nguyên t Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 nào đó. http://www.lrc-tnu.edu.vn/ 12 Giả sử x Zn ; a. Trƣờng hợp (x,n) =1 Khi đó ta có: x (n) mod n = 1. ya modn (xb)a mod n xt (n)+1 ((x (n) mod n mod n)t ).x mod n 1t .x (mod n) x (mod n) b. Trƣờng hợp (x,n)= d>1 d = p hoặc d = q. Giả sử d = p, khi đó x = hp với 0 < h < q và (h,n) = 1, suy ra: ya modn (xb)a mod n Do (h,n) = 1 nên hab modn (hab modn)( pab modn) modn h Bên cạnh đó, pabmodn = pabmod(p.q) pab mod q p.p (n) p.p (p). (q) p.(p Vậy ya modn mod q (p) ) mod q (q) mod q p h.p modn = h.p = x. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/