Các thuật toán tối ưu hóa trong bảo mật thông tin

nhiệm khoa và các cán bộ đã tạo điều kiện tốt nhất cho chúng tơi học tập và hồn thành đề tài tốt nghiệp của mình. Đặc biệt, tơi xin gửi tới PGS. TSKH Nguyễn Xuân Huy, thầy đã tận tình chỉ bảo tơi trong suốt quá trình thực hiện đề tài lời cảm ơn và biết ơn sâu sắc nhất. Bên cạnh những kiến thức khoa học, thầy đã giúp tơi nhận ra những bài học về phong cách học tập, làm việc và những kinh nghiệm sống quý báu. Tơi xin bày tỏ lịng biết ơn tới gia đình, bạn bè, đồng nghiệp và những ngƣời thân đã động viên khích lệ tinh thần và giúp đỡ để tơi hồn thành luận văn này. Thái Nguyên, ngày 10 tháng 11 năm 2008 Nguyễn Ngọc Trung 3 LỜI CAM ĐOAN Tơi xin cam đoan, tồn bộ nội dung liên quan tới đề tài đƣợc trình bày trong luận văn là bản thân tơi tự tìm hiểu và nghiên cứu, dƣới sự hƣớng dẫn khoa học của Thầy giáo PGS. TSKH Nguyễn Xuân Huy. Các tài liệu, số liệu tham khảo đƣợc trích dẫn đầy đủ nguồn gốc. Tơi xin chịu trách nhiệm trƣớc pháp luật lời cam đoan của mình. Học viên thực hiện Nguyễn Ngọc Trung 4 MỤC LỤC Trang LỜI CẢM ƠN LỜI CAM ĐOAN MỤC LỤC ............................................................................................................................... DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .................................................................................. MỞ ĐẦU ............................................................................................................................... 1 CHƢƠNG 1 - LÝ THUYẾT MẬT MÃ ................................................................................ 6 1.1 MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ MÃ HĨA ......................................................... 6 1.2 LÝ THUYẾT ĐỘ PHỨC TẠP .................................................................................. 10 1.3 CƠ SỞ TỐN HỌC CỦA MẬT MÃ ..................................................................... 13 CHƢƠNG 2 - NGHIÊN CỨU CƠ CHẾ HOẠT ĐỘNG CỦA HỆ MẬT KHĨA CƠNG KHAI ................................................................................................................................... 20 2.1 GIỚI THIỆU VỀ HỆ MẬT VỚI KHĨA CƠNG KHAI ........................................... 20 2.2 HỆ MẬT MÃ KHĨA CƠNG KHAI RSA ................................................................ 22 2.3 HỆ MẬT MÃ KHĨA CƠNG KHAI RSA WITH CRT ............................................ 29 2.4 CƠ CHẾ HOẠT ĐỘNG CỦA RSA .......................................................................... 34 2.5 KHẢ NĂNG BỊ BẺ KHĨA CỦA HỆ MÃ CƠNG KHAI RSA ............................... 36 2.6 HỆ MẬT MÃ KHĨA CƠNG KHAI ELGAMAL .................................................... 40 CHƢƠNG 3 - MỘT SỐ GIẢI THUẬT XỬ LÝ SỐ HỌC ÁP DỤNG ĐỂ TỐI ƢU HĨA QUÁ TRÌNH MÃ HĨA VÀ GIẢI MÃCỦA HỆ MÃ RSA ……………………………...41 3.1 PHÂN TÍCH CÁC PHÉP XỬ LÝ TỐN HỌC TRONG HỆ MÃ RSA .................. 41 3.2 ỨNG DỤNG GIẢI THUẬT FAST FOURIER TRANSFORM TRONG XỬ LÝ PHÉP NHÂN SỐ LỚN .................................................................................................... 45 3.1 CÀI ĐẶT THỬ NGHIỆM CÁC PHÉP TỐN VỚI SỐ LỚN .............................. 53 CHƢƠNG 4: ỨNG DỤNG TRONG XÂY DỰNG HỆ MÃ RSA ..................................... 56 4.1 XÂY DỰNG HỆ MÃ RSA THỬ NGHIỆM ............................................................. 56 4.2 ĐÁNH GIÁ VÀ NHẬN XÉT KẾT QUẢ ................................................................. 59 CHƢƠNG 5 – KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .................................................. 60 5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT CRT Chinese Remainder Theorem DES Data Encryption Standard RSA Rivest ShamirAdleman GCD Great Comon Divisor FFT Fast Fourier Transform 6 DANH MỤC CÁC BẢNG Trang Bảng 1.1: Bảng chi phí thời gian để phân tích số nguyên n ra thừa số nguyên tố .. 12 Bảng 2.1: Tĩm tắt các bước tạo khố, mã hố, giải mã của Hệ ElGamal .............. 25 Bảng 2.2: Bảng chi phí thời gian cần thiết để phân tích các số nguyên N .............. 28 Bảng 2.3: Tĩm tắt các bước tạo khố, mã hố, giải mã của Hệ ElGamal .............. 42 7 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Trang Hình 1.1: Mơ hình mã hĩa khĩa đối xứng ................................................................. 7 Hình 1.2: Mơ hình mã hĩa khĩa bất đối xứng . ...................................................... 10 Hình 2.1: Đồ thị so sánh chi phí tấn cơng khĩa bí mật và khĩa cơng khai. ........... 39 Hình 3.1: Sơ đồ thực hiện giải thuật nhân nhanh sử dụng DFT. ........................... 49 Hình 3.2: Giao diện thực hiện phép cộng. .............................................................. 54 Hình 3.3: Giao diện thực hiện phép nhân. .............................................................. 55 Hình 4.1: Giao diện chương trình mơ phỏng hệ RSA. ............................................. 56 Hình 4.2 và 4.3: Giao diện thực hiện mã hĩa và giải mã file văn bản. .................. 57 8 MỞ ĐẦU 1. Lý do chọn đề tài Các hệ mã cơng khai nhƣ RSA thực hiện tính tốn với các số nguyên lớn hàng trăm chữ số. Độ phức tạp trong việc giải mã các hệ mã này tỉ lệ thuận với độ lớn của các số nguyên tham gia vào việc tạo khĩa mã hĩa và khĩa cơng khai. Do đĩ để hệ mã an tồn, cần tăng kích thƣớc của các số nguyên. Mặt khác, khi kích thƣớc của các số nguyên cần xử lý lớn thì thời gian xử lý của chƣơng trình mã hĩa cũng tăng lên. Thơng tin cần mã hĩa ngày càng đa dạng và cĩ khối lƣợng lớn, địi hỏi hệ mã giảm thiểu thời gian xử lý. Các cơng cụ và giải thuật nhằm bẻ khĩa các hệ mật mã đƣợc cải tiến địi hỏi hệ mã cần đƣợc nâng cấp tính bảo mật. Tuy nhiên, việc nghiên cứu và triển khai các nâng cấp trong việc tối ƣu hĩa về mặt thuật tốn trong các phép xử lý số học của các hệ mã cịn hạn chế trong phạm vi các chƣơng trình độc quyền. Để hỗ trợ giải quyết các vấn đề trên, đề tài này tập trung vào việc xây dựng một số thuật tốn tối ƣu hĩa nhằm tăng hiệu quả các phép tính tốn thực hiện với số nguyên lớn. Các kết quả của đề tài sẽ đƣợc ứng dụng trong việc hỗ trợ cho các phép xử lý số học của các hệ mã. Từ đĩ làm tăng tốc độ xử lý và tính bảo mật của các hệ mã. Từ tính cấp thiết của vấn đề tối ƣu hĩa các hệ mã cơng khai, đồng thời đƣợc sự hƣớng dẫn và gợi ý của PGS.TSKH Nguyễn Xuân Huy tơi đã chọn đề tài cho luận văn tốt nghiệp Cao học ngành khoa học máy tính là: “Các thuật tốn tối ƣu hĩa trong bảo mật thơng tin”. 9 2. Mục đích và nhiệm vụ  Mục tiêu o Về học thuật: Đề tài này tập trung vào việc xây dựng một số thuật tốn tối ƣu hĩa nhằm tăng hiệu quả các phép tính tốn thực hiện với số nguyên lớn. o Về phát triển và triển khai ứng dụng: Các kết quả của đề tài sẽ đƣợc ứng dụng trong việc hỗ trợ cho các phép xử lý số học với số nguyên lớn trong các hệ mã. Từ đĩ làm tăng tốc độ xử lý và tính bảo mật của các hệ mã.  Nhiệm vụ - Nghiên cứu các quá trình thực hiện mã hĩa và giải mã của các hệ mã cơng khai. - Tìm hiểu các thuật tốn xử lý số học đƣợc dùng trong các hệ mã. - Phát hiện các giải thuật tính tốn cần tối ƣu hĩa. - Thực hiện đƣa ra giải pháp tối ƣu hĩa các giải thuật này. - Ứng dụng trong một hệ mã cụ thể. - So sánh với kết quả thực thi của hệ mã khi chƣa thực hiện tối ƣu hĩa. 3. Phƣơng pháp nghiên cứu - Nghiên cứu dựa trên việc tìm hiểu các giải thuật xử lý với số nguyên lớn của các hệ mã. Cụ thể là hệ mã hĩa RSA, từ kết quả nghiên cứu cĩ đƣợc sẽ định hƣớng lựa chọn thuật tốn nào cần tối ƣu hĩa. - Thực hiện việc tối ƣu hĩa các giải thuật bằng cách tối ƣu các phép xử lý với số học lớn. Thao tác này sử dụng kết hợp các phƣơng pháp tính tốn với số học nhằm tăng hiệu năng của từng bƣớc xử lý. - Thu thập các tài liệu đã xuất bản, các bài báo trên các tạp chí khoa học và các tài liệu trên mạng Internet cĩ liên quan đến vấn đề đang nghiên cứu. - Tìm hiểu, vận dụng và kế thừa các thuật tốn và qui trình mã đã cơng bố kết quả. 10 - Thực nghiệm cài đặt ứng dụng để minh họa các vấn đề trình bày trong đề tài. 4. Đối tƣợng và phạm vi nghiên cứu  Đối tượng nghiên cứu : Các hệ mật mã khĩa cơng khai, trong đĩ hệ mật mã RSA đƣợc sử dụng làm đối tƣợng nghiên cứu chính của đề tài nhằm phát hiện các phép xử lý tốn học cần tối ƣu. Từ các kết quả thu đƣợc bƣớc đầu đề tài đƣa ra một cách xây dựng thử nghiệm hệ mã RSA áp dụng các kết quả tối ƣu hĩa.  Phạm vi nghiên cứu Đề tài thực hiện việc tối ƣu hĩa với một số phép tính tốn với số nguyên lớn. Ứng dụng thử nghiệm trong một hệ mã nhằm so sánh hiệu năng xử lý của hệ mã trƣớc và sau khi tối ƣu. Đề tài giới hạn trong phạm vi nghiên cứu để đƣa ra giải pháp, việc triển khai ứng dụng thực tiễn cần cĩ thêm các điều kiện về thời gian và quy mơ. 5. Ý nghĩa khoa học và thực tiễn của luận văn  Ý nghĩa khoa học - Trình bày các kiến thức tốn học cơ bản, lý thuyết độ phức tạp của thuật tốn, các thuật tốn thƣờng dùng trong các hệ mật mã khố cơng khai. - Trình bày các phƣơng pháp mật mã gồm: Phƣơng pháp mã hố khĩa bí mật và phƣơng pháp mã hố khĩa cơng khai. Với phƣơng pháp mã hĩa khĩa cơng khai thì tập trung vào các thuật tốn mã hĩa RSA. Với phƣơng pháp mã hĩa khĩa bí mật chỉ giới thiệu sơ lƣợc để so sánh với phƣơng pháp mã hĩa khĩa cơng khai. - Tối ƣu các phép xử lý số học với số nguyên lớn là một yêu cầu cần thiết trong việc xây dựng các hệ mã hĩa cĩ tốc độ xử lý và độ an tồn cao.  Ý nghĩa thực tiễn - Cài đặt hồn chỉnh các giải thuật xử lý số học với số nguyên lớn cỡ hàng trăm chữ số. 11 - Đƣa ra đƣợc chƣơng trình thử nghiệm các giải thuật xây dựng đƣợc trong một hệ mã. - Đƣa ra kết quả so sánh hiệu năng xử lý của hệ mã trƣớc và sau khi tối ƣu. 6. Bố cục của luận văn Mở đầu 1. Lý do chọn đề tài. 2. Mục đích và ý nghĩa. 3. Phƣơng pháp nghiên cứu. 4. Đối tƣợng và phạm vi nghiên cứu. 5. Ý nghĩa khoa học và thực tiễn của luận văn. Chƣơng 1: Nghiên cứu lý thuyết và thực tiển về mã hĩa dữ liệu. 1.1 Một số khái niệm cơ bản về mã hĩa. 1.2 Lý thuyết độ phức tạp của thuật tốn. 1.3 Các phép xử lý số học cơ bản – Cơ sở tốn học của mật mã. Chƣơng 2: Các thuật tốn xử lý số học trong các hệ mã thơng dụng. 2.1 Giới thiệu về hệ mật mã với khĩa cơng khai. 2.2 Hệ mật mã cơng khai RSA. 2.3 Hệ mật mã cơng khai RSA with CRT. 2.4 Phân tích cơ chế hoạt động của hệ mã RSA. 2.5 Các phép xử lý số học trong hệ mã RSA. 2.6 Khả năng bị bẻ khĩa của hệ mã cơng khai RSA. 2.7 Hệ mật mã khĩa cơng khai ELGAMAL. Chƣơng 3: Tối ƣu hĩa một số giải thuật xử lý số học trong một hệ mã cụ thể. 3.1 Phân tích các giải thuật xử lý số học trong hệ mã RSA 3.2 Tối ƣu hĩa các giải thuật để xử lý với các số nguyên lớn. Chƣơng 4: Ứng dụng kết quả trong một hệ mã hĩa cụ thể. 4.1 Xây dựng ứng dụng. 12 4.2 Kiểm nghiệm và so sánh kết quả đạt đƣợc trƣớc và sau khi tối ƣu hĩa. Chƣơng 5: Kết luận. 5.1 Đánh giá và nêu ƣu nhƣợc điểm của đề tài. 5.2 Định hƣớng phát triển đề tài. 7. Đĩng gĩp của luận văn - Luận văn hệ thống các cơ sở lý thuyết cơ bản về hệ mật mã khĩa cơng khai. - Xây dựng chƣơng trình thử nghiệm ứng dụng bảo mật và xác thực trong giảng dạy. Từ đĩ cĩ thể mở rộng và hồn thiện thêm một số chức năng để đƣa vào ứng dụng trong thực tiễn. 13 CHƢƠNG 1 – NGHIÊN CỨU LÝ THUYẾT VÀ THỰC TIỄN VỀ MÃ HĨA DỮ LIỆU 1.1 MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ MÃ HĨA Lịch sử của mật mã học đã cĩ từ rất sớm, ban đầu con ngƣời cố gắng tìm một cách để bảo vệ thơng tin, tránh việc thơng tin bị giải mã khi ngƣời khác cĩ đƣợc chúng. Các cách áp dụng đĩ thƣờng mang tính mẹo mực đơn giản và cĩ thể dễ dàng bị giải mã nếu thơng tin về cách thức che giấu bị lộ hoặc bị suy đốn. Mật mã học ban đầu đƣợc áp dụng nhiều trong lĩnh vực quân đội. Các phƣơng pháp mã hĩa cổ điển đã đƣợc áp dụng nhƣ Caesar, Playfair, … Các hệ mật mã cổ điển đƣợc sử dụng nhiều nhƣng dần dần chúng bộc lộ một hạn chế lớn. Do các cách mã hĩa đều dựa trên phƣơng pháp mã khĩa bí mật, khi gửi bản mã đi thì cần phải gửi kèm theo cả cách giải mã. Bên cạnh đĩ, nếu cách mã hĩa là quen thuộc hoặc đơn giản thì ngƣời cĩ đƣợc thơng tin đã bị mã hĩa cĩ thể tiến hành các cách để dị ra luật mã hĩa để cĩ đƣợc văn bản gốc. Ngày nay cũng với sự trợ giúp của máy tính điện tử, các phƣơng pháp mã hĩa với khĩa bí mật đƣợc sử dụng chung cho quá trình mã hĩa và giải mã (hay cịn gọi là mã hĩa cổ điển) cĩ thể dễ dàng bị giải mã. Sự cần thiết phải cĩ các phƣơng pháp mã hĩa an tồn hơn đã đƣợc đáp ứng bằng việc áp dụng các kết quả nghiên cứu của tốn học. Sự thay đổi về phƣơng pháp mã hĩa cũng nhƣ độ an tồn của các hệ mã mới đã đƣa lịch sử của mật mã học sang trang mới. Các hệ mật mã với khĩa mã đối xứng đã gĩp phần to lớn trong việc củng cố vai trị của mật mã học trong các ứng dụng của con ngƣời. Đƣa mật mã đến với cả các ứng dụng trong cuộc sống đời thƣờng của con ngƣời, mật mã khơng cịn chỉ đƣợc nhắc đến nhiều trong lĩnh vực quân sự. Ứng của mật mã học đã trở thành một cơng cụ cần thiết cho mọi ngƣời, cần thiết cho các hoạt động thƣờng ngày. Các phƣơng pháp mã hĩa khác nhau cĩ những ƣu, nhƣợc điểm khác nhau. Khi sử dụng các phƣơng pháp mã hĩa, ngƣời dùng sẽ cân nhắc để lựa chọn phƣơng pháp mã hĩa thích hợp nhất đối với mình. Cĩ thể lựa chọn mơi trƣờng cần phải an 14 tồn tuyệt đối bất kể thời gian và chi phí hoặc lựa chọn mơi trƣờng lại cần giải pháp dung hịa giữa bảo mật và chi phí. Các mơ hình mã hĩa cĩ chung một số thuật ngữ nhƣ sau: Bản rõ: Là nội dung của thơng điệp cần gửi đi và cần đƣợc bảo vệ an tồn. Nĩ cĩ thể là xâu các bít, các file văn bản, các file cĩ cấu trúc. Mã hố: Là quá trình xử lý thơng điệp cần bảo mật trƣớc khi gửi đi. Bản mã: Là kết quả thu đƣợc khi mã hĩa bản rõ theo qui trình mã hĩa của phƣơng pháp đang đƣợc chọn. Giải mã: Là quá trình xử lý ngƣợc, tiến hành giải mã bản mã để thu lại bản rõ. Ví dụ: Mã hĩa văn bản cĩ nội dung là “ABC” với luật mã là tịnh tiến vịng 1 đơn vị đối với mã ASCII của mỗi kí tự. Vậy ta cĩ: Bản rõ: “ABC” Mã hĩa: Thực hiện mã hĩa theo luật mã. Biến đổi các kí tự thành các số theo mã ASCII của kí tự đĩ. A  65, B  66, C  67 Thu đƣợc các mã mới sau khi tịnh tiến là: 66 - 67 - 68 Biến đổi các mã mới thành kí tự. Bản mã: “BCD”. Giải mã: Thu đƣợc bản rõ là “ABC”. 1.1.1. Khái niệm chung về mật mã Hệ mật mã hiện đại thƣờng gồm 5 thành phần (P, C, K, E, D) trong đĩ: P (Plaintext) tập hợp hữu hạn các bản rõ cĩ thể (khơng gian các bản rõ). C (Ciphertext) tập hợp hữu hạn các bản mã cĩ thể (khơng gian các bản mã). K (Key) tập hợp các bản khố cĩ thể. E (Encrytion) tập hợp các qui tắc mã hố cĩ thể. D (Decrytion) tập hợp các qui tắc giải mã cĩ thể. Nội dung cần mã hĩa thể hiện dƣới dạng bản rõ (P). Ngƣời gửi sử dụng qui tắc (E) và khĩa (K) mã hố bản rõ (P), kết quả thu đƣợc gọi là bản mã (EK(P) = C). Bản 15 mã này đƣợc gửi đi trên một đƣờng truyền tới ngƣời nhận, sau khi nhận đƣợc bản mã (C) ngƣời nhận sử dụng qui tắc (D) và khĩa (K) giải mã nĩ để hiểu đƣợc nội dung thơng điệp gốc (DK(C) = P). 1.1.2. Những yêu cầu đối với hệ mật mã hiện đại Hệ mật mã hiện đại cần đảm bảo đƣợc hai yêu cầu sau: - Đảm bảo tính bảo mật. - Đảm bảo tính xác thực. Bảo mật: Ngăn khơng để ngƣời lạ thực hiện việc trích chọn, sửa đổi thơng tin từ các bản mã đƣợc gửi trên các kênh truyền phổ biến (thƣờng khơng an tồn). Xác thực: Đảm bảo chỉ cĩ ngƣời nhận đúng mới cĩ thể giải mã nội dung bản mã, đồng thời cũng đảm bảo ngƣời gửi khơng thể phủ nhận nội dung đã gửi. 1.1.3 Các phƣơng pháp mã hĩa 1.1.3.1 Hệ thống mã hĩa đối xứng Cả hai quá trình mã hĩa và giải mã của hệ thống mã hĩa đối xứng đều sử dụng chung một khĩa bí mật. Do đĩ, khi bị mất khĩa bí mật này thì tính bảo mật của hệ mã bị phá vỡ. Ban đầu, bản rõ đƣợc ngƣời gửi A mã hĩa với khĩa k. Sau đĩ bản mã đƣợc gửi tới ngƣời nhận B. Khi nhận đƣợc bản mã, ngƣời B sử dụng khĩa k giải mã để thu đƣợc bản rõ. Do đĩ, nếu một ngƣời khác cĩ đƣợc khĩa k thì hệ thống mã hĩa này sẽ bị tấn cơng. (Hình 1.1) Hình 1.1: Sơ đồ hoạt động của mã hĩa khĩa đối xứng Các hệ mật mã nhƣ DES, 3DES-Triple DES đƣợc xây dựng trên phƣơng pháp mã hĩa khĩa đối xứng. Bản mã Bản rõ Mã hĩa Giải mã Bản rõ Khĩa bí mật 16 Nhận xét: - Trong các giao dịch trên mạng, khĩa k phải đƣợc truyền đi trên mơi trƣờng này. Do đĩ nĩ cĩ thể bị lấy cắp. Để an tồn hơn, việc bảo mật cho khĩa k cần phải đƣợc chú trọng. Thƣờng phải dùng thêm các cơ chế và giải thuật khác trong việc quản lý, trao đổi khĩa giữa các đối tƣợng. - Nội dung của bản rõ khơng thể xác thực đƣợc nguồn gốc cũng nhƣ khơng cĩ tính chất khơng thể phủ nhận của chủ thể. - Khi số lƣợng khĩa bí mật tăng lên, việc quản lý các khĩa này trở nên phức tạp và khĩ khăn cho cơng việc khi một ngƣời phải giữ nhiều khĩa bí mật khi giao dịch với nhiều đối tƣợng khác nhau. Những nhƣợc điểm trên dẫn đến hệ mã với khĩa mã đối xứng khĩ cĩ thể áp dụng rộng rãi. Trong nội dung của đề tài này, các phƣơng pháp mã hĩa với khĩa mã cơng khai đƣợc nghiên cứu để thực hiện mục đích của đề tài. 1.1.3.2 Hệ thống mã hĩa bất đối xứng Hệ thống mã hĩa bất đối xứng hay cịn gọi là mã hĩa với khĩa cơng khai đã đƣợc Martin Hellman, Ralph Merkle và Whitfield Diffie thuộc Đại học Stanford giới thiệu vào năm 1976. Hệ mã này đƣợc áp dụng các kết quả của tốn học đã khắc phục đƣợc các hạn chế của các phƣơng pháp mã hĩa khĩa đối xứng. Phƣơng pháp mã hĩa bất đối xứng sử dụng hai loại khĩa trong cùng một cặp khĩa: Khĩa cơng khai (public key) đƣợc cơng bố rộng rãi và sử dụng để mã hĩa các thơng điệp, khĩa riêng (private key) chỉ do chủ thể nắm giữ và đƣợc sử dụng để giải mã thơng điệp đã đƣợc mã hĩa bằng khĩa cơng khai. Các lý thuyết tốn học dựa trên cơ sở khai thác những ánh xạ f mà việc thực hiện ánh xạ ngƣợc f -1 rất khĩ so với việc thực hiện ánh xạ f đƣợc sử dụng trong các phƣơng pháp mã hĩa này. Việc thực hiện ánh xạ ngƣợc f -1 chỉ tiến hành đƣợc khi biết đƣợc khĩa riêng. 17 Hình 1.2 Sơ đồ hoạt động của mã hĩa khĩa bất đối xứng Khi thực hiện mã hĩa bất đối xứng, ngƣời A sử dụng khĩa cơng khai do ngƣời B tạo để mã hĩa thơng điệp và gửi cho ngƣời B. Do biết đƣợc khĩa riêng nên B mới cĩ thể giải mã đƣợc thơng điệp mà A đã mã hĩa. Trong trƣờng hợp bản mã bị một ngƣời thứ ba cĩ đƣợc, nếu chỉ kết hợp với thơng tin về khĩa cơng khai đã đƣợc cơng bố, cũng rất khĩ cĩ khả năng giải mã đƣợc bản mã này trong khoảng thời gian chấp nhận đƣợc do khơng nắm đƣợc khĩa riêng của B. Khĩa cơng khai và khĩa riêng cĩ quan hệ tốn học với nhau theo nghĩa từ khĩa riêng cĩ thể tính tốn để suy ra đƣợc khĩa cơng khai, nhƣng để từ khĩa cơng khai suy ra khĩa riêng sẽ rất phức tạp vì số lƣợng phép tính tốn là rất lớn dẫn đến thời gian thực hiện để giải mã là khơng khả thi khi chiều dài của khĩa đủ lớn. Đây cũng là mấu chốt của vấn đề bảo mật và tấn cơng trong các hệ mã khĩa cơng khai. Đề tài này sẽ đề cập đến vấn đề an tồn của hệ mã cơng khai. Nghiên cứu đƣa ra các giải pháp hỗ trợ làm tăng tính an tồn của các hệ mã này bằng cách cố gắng áp dụng các thuật tốn xử lý nhanh với số lớn. Từ đĩ cĩ thể tăng chiều dài của khĩa mà vẫn đảm bảo yếu tố thời gian mã hĩa và giải mã chấp nhận đƣợc. 1.2 LÝ THUYẾT ĐỘ PHỨC TẠP 1.2.1 Khái niệm độ phức tạp của thuật tốn Khi tiến hành chạy cùng một thuật tốn trên nhiều máy tính với cấu hình khác nhau ta sẽ thu đƣợc thời gian thực hiện thuật tốn khác nhau. Do đĩ ta khơng thể lấy thời gian thực hiện của thuật tốn trên một máy tính để đánh giá độ phức tạp của thuật tốn. Bản mã Bản rõ Mã hĩa Giải mã Bản rõ Khĩa mã Khĩa giải 18 Độ phức tạp của một thuật tốn sẽ đƣợc tính bằng số các phép tính cơ sở máy tính thực hiện khi tiến hành chạy thuật tốn (các phép tính cơ sở: đọc, ghi, phép so sánh). Ngồi ra, số lƣợng phép tính cịn phụ thuộc vào kích cỡ đầu vào của thuật tốn. Nhƣ vậy, độ phức tạp của thuật tốn phải là một hàm số theo độ lớn của đầu vào. Việc xác định chính xác hàm này cĩ thể rất phức tạp, tuy nhiên khi biết cỡ của chúng thì ta đã cĩ đƣợc một ƣớc lƣợng chấp nhận đƣợc. Độ phức tạp của một thuật tốn đƣợc đo bằng số các phép tính bit. Phép tính bit là một phép tính logic hay số học thực hiện trên các số một bit 0 và 1. Để ƣớc lƣợng độ phức tạp của thuật tốn, ta dùng khái niệm bậc O-lớn. Định nghĩa 1.1: Giả sử f(n) và g(n) là hai hàm xác định trên tập hợp các số nguyên dƣơng. Ta nĩi f(n) cĩ bậc O-lớn của g(n), và viết f(n) = O(g(n)) hoặc f=O(g), nếu tồn tại một hằng số C > 0 sao cho với n đủ lớn. Ta cĩ 0 < f(n) < Cg(n). Định nghĩa 1.2: Một thuật tốn đƣợc gọi là cĩ độ phức tạp đa thức, hoặc cĩ thời gian đa thức, nếu số các phép tính cần thiết khi thực hiện thuật tốn khơng vƣợt quá O(logkn), trong đĩ n là độ lớn của đầu vào, và k là số nguyên dƣơng nào đĩ. Nĩi cách khác, nếu đầu vào là các số m-bit thì thời gian thực hiện thuật tốn là O(m d), tức là tƣơng đƣơng với một đa thức của m. Các thuật tốn với thời gian O(αn), α > 1, đƣợc gọi là các thuật tốn với độ phức tạp mũ, hoặc thời gian mũ. Một thuật tốn cĩ độ phức tạp O(g), thì cũng cĩ thể nĩi nĩ cĩ độ phức tạp O(h) với mọi hàm h > g. Tuy nhiên, ta luơn luơn cố gắng tìm ƣớc lƣợng tốt nhất cĩ thể đƣợc để tránh hiểu sai về độ phức tạp thực sự của thuật tốn. Tồn tại những thuật tốn cĩ độ phức tạp trung gian giữa đa thức và mũ. Các thuật tốn đĩ đƣợc gọi là thuật tốn dƣới mũ. Độ phức tạp khơng phải là tiêu chuẩn duy nhất để đánh giá thuật tốn. Cĩ những thuật tốn, về lý thuyết thì cĩ độ phức tạp cao hơn một thuật tốn khác, nhƣng khi sử dụng lại cho kết quả nhanh hơn. 19 Bảng dƣới đây đƣa ra các thơng số về thời gian và số lƣợng phép tốn trên bit để thực hiện việc phân tích một số nguyên n ra thừa số nguyên tố áp thuật tốn tốt nhất trên máy tính cĩ tốc độ xử lý một triệu phép tính trên một giây: Giải thuật này cĩ độ phức tạp dƣới mũ:  .logloglogexp nn Bảng 1.1: Bảng chi phí thời gian phân tích số nguyên n ra thừa số nguyên tố Số chữ số thập phân Số phép tính trên bit Thời gian 50 1,4.10 10 3,9 giờ 75 9,0.10 12 104 ngày 100 2,3.10 15 74 năm 200 1,2.10 23 3,8.10 9 năm 300 1,5.10 29 4,9.10 15 năm 500 1,3.10 39 4,2.10 25 năm Dễ nhận thấy rằng với một thuật tốn dƣới mũ, thời gian làm việc với các số nguyên lớn vẫn khơng khả thi. Do đĩ, với các ứng dụng xử lý số lớn, ta thƣờng phải cố gắng biến đổi để thu đƣợc một thuật tốn cĩ thời gian tính tốn đa thức. Ý tƣởng này sẽ đƣợc áp dụng trong phần nghiên cứu của để tài để xử lý cho các phép tốn số học với số lớn trong các hệ mã hĩa cơng khai. 1.2.2 Các bài tốn khĩ tính tốn và ứng dụng trong mật mã học Một hệ mật phải cố gắng gây khĩ khăn cho ngƣời giải mã khi khơng biết khĩa giải nhƣng lại dễ dàng giải mã khi biết đƣợc khĩa giải mã. Một hệ mã nhƣ vậy sẽ cĩ một thơng tin “cửa sập” bí mật đƣợc chèn thêm vào bài tốn dựa trên tính khĩ khăn khi thực hiện nghịch đảo một hàm một chiều. Định nghĩa 1.3: Cho các tập hữu hạn S, T. Hàm f : S  T đƣợc gọi là hàm một chiều (one- way function) nếu nhƣ: 20 - Hàm f dễ tính tốn, nghĩa là  x  S, cĩ thể dễ dàng tính y = f(x). - Hàm ngƣợc f -1(y) khĩ tính, nghĩa là cho y  T thì khĩ tính đƣợc x = f -1(y). Định nghĩa 1.4: Hàm một chiều cửa sập (trapdoor one-way function) là hàm một chiều f đƣợc thêm vào thơng tin cửa sập (trapdoor information) để cĩ thể dễ dàng tính x khi biết bất kỳ y  T thoả mãn x = f -1(y). Ví dụ về hàm một chiều: - f(p,q) = p*q, là hàm một chiều với p, q là các số nguyên tố lớn. Nhƣ vậy, ta cĩ thể thực hiện phép nhân p * q (độ phức tạp đa thức); nhƣng tính f -1 lại là bài tốn cực khĩ (bài tốn phân tích ra thừa số nguyên tố - độ phức tạp mũ). - fg ,N : x  g x mod N là hàm một chiều. Thực vậy, phép tính gx mod N cĩ độ phức tạp đa thức; nhƣng tính f -1 lại là bài tốn cực khĩ (bài tốn logarithm rời rạc). - fk ,N : x  x k mod N là hàm một chiều, với N = pq, p và q là các số nguyên tố lớn, kk’  1(mod φ(N)). Thực vậy, phép tính xk mod N cĩ độ phức tạp đa thức, nhƣng tính f -1 lại cực khĩ. Tuy nhiên, nếu biết k’ cĩ thể dễ dàng tính đƣợc f từ cơng thức (xk)k’= x. 1.3 CƠ SỞ TỐN HỌC CỦA MẬT MÃ 1.3.1. Hàm phi Euler Định nghĩa 1.5 Cho n ≥1, đặt φ(n) là tập các số nguyên trong khoảng [1, n] nguyên tố cùng nhau với n. Hàm φ nhƣ thế đƣợc gọi là hàm phi Euler. Tính chất của hàm phi Euler 1. Nếu p là số nguyên tố thì φ(n) = p – 1 2. Hàm phi Euler là hàm cĩ tính nhân: Nếu gcd(m,n) = 1 thì φ(m.n) = φ(m).φ(n). (trong đĩ gcd(m, n) là ký hiệu ƣớc số chung lớn nhất của m và n) Nếu n = p1 e1 p2 e2…pk ek trong đĩ p1, p2, ..., pk là các thừa số nguyên tố của n thì: φ(n) = n(1 - 1 1 p )(1 - 2 1 p )… (1 - pk 1 ) 1.3.2. Lý thuyết đồng dƣ thức 21 Định nghĩa 1.6 Cho a và b là các số nguyên, a đƣợc gọi là đồng dƣ với b theo modulo n, ký hiệu là a  b (mod n) nếu n chia hết (a-b). Số nguyên n đƣợc gọi là modulo của đồng dƣ. * Tính chất của đồng dư: Cho a, a1, b, b1, c  Z. Ta cĩ các tính chất sau: i. a  a(mod n) (phản xạ); ii. Nếu a  b(mod n) b  a(mod n) (đối xứng); iii. Nếu a  b(mod n), b  c(mod n) a  c(mod n) (bắc cầu); iv. Nếu a  a1(mod n), b  b1(mod n) a + b  (a1 + b1)(mod n), ab  (a1b1) (mod n), a n  (a1) n(mod n), với mọi n  Z. Ta cĩ khái niệm lớp tƣơng đƣơng nhƣ sau: Lớp tƣơng đƣơng của một số nguyên a là tập hợp các số nguyên đồng dƣ với a theo modulo n. Từ các tính chất i, ii và iii ta thấy: Cho n cố định, các số đồng dƣ theo modulo n trong khơng gian Z đƣợc xếp vào một lớp tƣơng đƣơng. Nếu a = qn + r, trong đĩ 0 ≤ r < n thì a  r (mod n). Vì vậy mỗi số nguyên a là đồng dƣ theo modulo n với duy nhất một số nguyên trong khoảng [0, n-1] và đƣợc gọi là thặng dƣ nhỏ nhất của a theo modulo n, a và r cùng thuộc một lớp tƣơng đƣơng. Do đĩ r cĩ thể đơn giản đƣợc sử dụng để thể hiện lớp tƣơng đƣơng. 1.3.3. Khơng gian Zn * Các định nghĩa trong khơng gian Zn - Các số nguyên theo modulo n ký hiệu Zn là một tập hợp các số nguyên {0, 1, 2, 3,…, n - 1}. Các phép tốn cộng, trừ, nhân trong Zn đƣợc thực hiện theo modulo n. - Cho aZn. Nghịch đảo nhân của a theo modulo n là một số nguyên x Zn sao cho a*x  1(mod n). Nếu x tồn tại thì đĩ là giá trị duy nhất và a đƣợc gọi là khả nghịch, nghịch đảo của a ký hiệu là a -1. - Cho a, bZn. Phép chia của a cho b theo modulo n là tích của a và b -1 theo modulo n, và chỉ đƣợc xác định khi b cĩ nghịch đảo theo modulo n. * Các tính chất trong khơng gian Zn 22 Cho a Zn, a cĩ nghịch đảo khi và chỉ khi a và n nguyên tố cùng nhau (gcd(a,n) = 1), trong đĩ gcd(a,n) là ƣớc số chung lớn nhất của a và n. Giả sử d = gcd(a,n). Phƣơng trình đồng dƣ ax  b (mod n) cĩ nghiệm x nếu và chỉ nếu b chia hết cho d, trong trƣờng hợp các nghiệm d nằm trong khoảng [0, n- 1] thì các nghiệm đồng dƣ theo modulo n/d. 1.3.4 Nhĩm nhân Z*n * Các định nghĩa trong nhĩm nhân Z*n - Nhĩm nhân của Zn ký hiệu là Z * n = {a Zn | gcd (a, n) = 1}. Nếu n là số nguyên tố thì Z*n = {aZn | 1 ≤ a ≤ n-1} - Cho aZn * . Bậc của a ký hiệu là ord(a) là số nguyên dƣơng t nhỏ nhất sao cho a t ≡ 1(mod n). - Cho aZn * . Bậc của a ký hiệu là ord(a) là số nguyên dƣơng t nhỏ nhất sao cho a t  1 (mod n). * Các tính chất trong Zn * - Cho số nguyên n ≥ 2 . Định lý 1.1 (Euler) Nếu a Zn * thì aφ(n)  1 (mod n). Nếu n là tích của các số nguyên tố phân biệt và nếu r  s(mod φ(n)) thì ar  as (mod n) với mọi số nguyên a. Nĩi cách khác, làm việc với các số theo modulo nguyên tố p thì số mũ cĩ thể giảm theo modulo φ(n). Định lý 1.2 (Fermat) Cho p là số nguyên tố. Nếu gcd(a, p) = 1 thì ap-1  1(mod p). Nếu r  s(mod(p-1)) thì ar  as(mod p) với mọi số nguyên a. a p  a (mod p) với mọi số nguyên a. 1.3.5 Thặng dƣ Định nghĩa 1.7 Cho aZn * , a đƣợc gọi là thặng dƣ bậc 2 theo modulo n hoặc căn bậc 2 theo modulo n nếu tồn tại xZn * sao cho x 2  a(mod n). Nếu khơng tồn tại x thì a đƣợc 23 gọi là thặng dƣ khơng bậc 2 theo modulo n. Tập hợp các thặng dƣ bậc 2 theo modulo n ký hiệu là Qn và tập hợp các thặng dƣ khơng bậc 2 theo modulo n ký hiệu là ___ Q n. Theo định nghĩa ta cĩ 0 Zn * nên 0 Qn và 0  ___ Q n . * Tính chất của thặng dư Cho n là tích của 2 số nguyên tố p và q. Khi đĩ a Zn * là một thặng dƣ bậc 2 theo modulo n khi và chỉ khi a Qn và a  ___ Q n. Ta cĩ, |Qn| = |Qp|.|Qq| = (p-1)(q-1)/4 và | ___ Q n| = 3(p-1)(q-1)/4 1.3.6 Căn bậc modulo Định nghĩa 1.8 Cho a Qn . Nếu a Zn * thoả mãn x2  a (mod n) thì x đƣợc gọi là căn bậc 2 của a theo modulo n. * Tính chất (số căn bậc 2) Nếu p là một số nguyên tố lẻ và a Qn thì a cĩ đúng 2 căn bậc 2 theo modulo p Tổng quát hơn: cho n = p1 e1 p2 e2…pk ek trong đĩ pi là các số nguyên tố lẻ phân biệt và ei ≥1. Nếu a Qn thì a cĩ đúng 2 k căn bậc 2 theo modulo n. 1.3.7 Các thuật tốn trong Zn Cho n là số nguyên dƣơng. Nhƣ đã nĩi ở trƣớc, các phần tử trong Zn đƣợc thể hiện bởi các số nguyên {0, 1, 2,…, n-1}. Ta thấy rằng: nếu a, b Zn thì: (a + b) mod n = a + b nếu a + b <n a + b – n nếu a + b ≥ n Vì vậy, phép cộng modulo (phép trừ modulo) cĩ thể đƣợc thực hiện mà khơng cần thực hiện các phép chia dƣ. Phép nhân modulo của a và b cĩ thể đƣợc thực hiện bằng phép nhân thơng thƣờng a với b nhƣ các số nguyên bình thƣờng, sau đĩ lấy phần dƣ của kết quả sau khi chia cho n. Phép tính nghịch đảo trong Zn cĩ thể đƣợc thực hiện nhờ sử dụng thuật tốn Euclid mở rộng nhƣ mơ tả sau: 24 * Thuật tốn tính nghịch đảo nhân trong Zn Bài tốn phát biểu nhƣ sau: Cho a Zn, hãy tìm a -1 mod n nếu cĩ. Bƣớc đầu, dùng thuật tốn Euclid mở rộng sau để tìm các số nguyên x và y sao cho: ax + ny = d với d = gcd(a,n). Nếu d > 1 thì a-1 mod n khơng tồn tại. Ngƣợc lại, return (x). Thuật tốn Euclid mở rộng(N+={1,2,3,…,} là tập các số nguyên dương) Algorithm Euclid INPUT: a, b  N+ ; OUTPUT: x, y  Z thoả ax + by ._.