Phân tích và cải tiến phương pháp mật mã hóa khóa công khai - Phan Thị Ngọc Mai

Tạp chí Khoa học công nghệ và Thực phẩm số 11 (2017) 95-104 95 PHÂN TÍCH VÀ CẢI TIẾN PHƢƠNG PHÁP MẬT MÃ HÓA KHÓA CÔNG KHAI Phan Thị Ngọc Mai*, Nguyễn Thị Thuỳ Trang Trường Đại học Công nghiệp Thực phẩm Tp.HCM *Email: maiptn@cntp.edu.vn Ngày nhận bài: 08/03/2017; Ngày chấp nhận đăng: 12/04/2017 TÓM TẮT Trong bài báo này chúng tôi khảo sát phương pháp mã hóa khóa công khai dựa vào định lý số dư Trung Hoa và phương trình ma trận trong quá trình phát sinh khóa, mã khóa và giải mã do Baocang WANG và Yongzhuang WEI, Yupu HU đưa ra năm 2009 [1] và cùng với các nội dung cần cải tiến sau đây: phát sinh nhanh các ma trận khóa, phát sinh nhanh khóa, hiện thực và so sánh với phương pháp gốc và với RSA. Từ khóa: số nguyên tố và mã hóa khóa công khai, số dư Trung Hoa. 1. TỔNG QUAN Mã hóa khóa công khai đã được ứng dụng rộng rãi trong thực tế và thu hút được sự quan tâm nghiên cứu của nhiều nhà khoa học trên thế giới. Tuy nhiên hầu hết các hệ thống mã hóa khóa công khai thông dụng như RSA, ElGamal gặp vấn đề về tốc độ phát sinh cũng như mã hóa khóa tương đối chậm. Nguyên nhân chính của vấn đề này là do trong quá trình phát sinh và mã khóa hóa, giải mã đều tính toán các số nguyên và số nguyên tố rất lớn. Có nhiều phương pháp giải quyết vấn đề trên đã được đề xuất, một trong những phương pháp là vận dụng định lý số dư Trung Hoa và phương trình ma trận trong quá trình phát sinh khóa, mã hóa và giải mã do Baocang WANG và Yongzhuang WEI, Yupu HU đưa ra năm 2009 [1]. Hầu hết các hệ thống mã hóa khóa công khai như RSA, ElGamal thực hiện tính toán với các số nguyên lớn hàng trăm chữ số. Độ phức tạp trong việc mã hóa, giải mã các hệ thống mã hóa khóa công khai 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 toà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ý về các mặt phát sinh và mã hóa khó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ý. Trên thực tế, tốc độ hiệu quả cũng như tính bảo mật là các vấn đề được quan tâm. RSA và ElGamal là hai thuật toán còn tồn tại trong môi trường yêu cầu tính bảo mật khắc nghiệt trong thập kỷ qua. Tuy nhiên cả hai thuật toán trên đều có tốc độ khá chậm vì tính toán dựa trên hàm mũ là hàm sử dụng nhiều tài nguyên. Phan Thị Ngọc Mai, Nguyễn Thị Thùy Trang 96 Để hỗ trợ giải quyết các vấn đề trên, bài báo ―Phân tích và cải tiến phương pháp mật mã hóa khóa công khai‖ tập trung vào việc xây dựng và đề xuất một số thuật toán tối ưu hóa nhằm tăng hiệu năng của quá trình phát sinh khóa dựa vào định lý số dư Trung Hoa và ứng dụng trong phân tích, cải tiến hiệu năng tính toán của quá trình phát sinh khóa. 2. CƠ SỞ LÝ THUYẾT 2.1. Định lý về số dƣ Trung hoa Cho tập số nguyên tố đôi một nguyên tố cùng nhau [2], với mỗi bộ số nguyên bất kỳ thì hệ phương trình đồng dư. { ( ) ( ) ( ) luôn có nghiệm duy nhất , được xác định như sau: ( ) Với được tính ( ) với có thể biểu diễn dưới dạng ( ) và ngược lại từ ( ) ta tìm được duy nhất một x. Chứng minh tính duy nhất và tồn tại có thể tham khảo [2]. Ví dụ: Tìm x thỏa mãn hệ phương trình đồng dư sau: { ( ) ( ) ( ) Ta tính như sau: ( ) ( ) ( ) , ( ) ( ) ( ) , ( ) ( ) ( ) Vậy ta suy ra: ( ) Thuật toán về định lý số dư Trung Hoa Input, , - , - Output: (1) (2) (3) For Do . / (4) End For (5) For Do . / (6) End For (7) Return Phân tích và cải tiến phương pháp mật mã hóa khóa công khai 97 Trong thuật toán trên ta sử dụng tính nghịch đảo của một số nguyên. Ta tính như sau: gọi là nghịch đảo của ( ) nếu: ( ) 2.2. Sinh nhanh ma trận khả nghịch 2.2.1. Ma trận khả nghịch Cho là ma trận vuông cấp n, một ma trận B gọi là ma trận nghịch đảo của Khi đó được gọi là ma trận khả nghịch. 2.2.2. Cách tìm ma trận khả nghịch a. Dựa vào định thức ( ) với ( ) ( ) lấy từ ma trận bằng cách bỏ đi hàng cột . b. Dựa vào phép biến đổi sơ cấp trên hàng  |n nA I ( nI là ma trận đơn vị cấp n)  |n nA I = 11 12 1 21 22 2 1 2 ... 1 0 ... 0 ... 0 1 ... 0 ... ... ... ... ... ... ... ... ... 0 0 ... 1              n n n n nn a a a a a a a a a c. Dựa vào cách giải hệ phương trình là ma trận tam giác trên (Upper Matrix), là ma trận tam giác dưới (Lower Matrix). 1.  L L I 1 1. [ ,..., ]    n nL L LX L X X I 11 1 21 22 2 1 2 0 ... 0 ... 0 ... ... ... ... ... ...                    n n nn n l x l l x l l l x = 1 0 ... 0 0 1 ... 0 ... ... ... ... 0 0 ... 1             Phan Thị Ngọc Mai, Nguyễn Thị Thùy Trang 98 0 ... 1 ... 0                 i iLX 11 1 21 22 1 2 0 ... 0 ... 0 ... ... ... ... ...                      i jj ij n n nn in l x l l l x l l l x = 0 ... 1 0             1 (1 ) /    j ij jk k jj k x l x l Như vậy nếu khả nghịch thì 2.3. Sinh ma trận và tìm ma trận nghịch đảo 2.3.1. Sinh ma trận Trong bài báo này chúng tôi đưa ra cách cài đặt thuật toán phát sinh ma trận thông qua hai ma trận và . Trong đó là ma trận tam giác trên, là ma trận tam giác dưới. khả nghịch 0 0   n ii i u khả nghịch 0 0   n ii i l cũng khả nghịch. Thuật toán phát sinh ma trận thông qua hai ma trận trên trường (1) là ma trận vuông tam giác trên khả nghịch 1 % 0         n ii i u p (2) là ma trận vuông tam giác dưới khả nghịch 1 % 0         n ii i l p (3) 2.3.2. Tìm ma trận nghịch đảo Thuật toán tìm ma trận nghịch đảo B thông qua hai ma trận (1) Tìm (2) Tìm (3) ( ) Phân tích và cải tiến phương pháp mật mã hóa khóa công khai 99 Một số ma trận tam giác đặc biệt Định nghĩa ma trận đối hợp: Cho ma trận vuông nxnA , được gọi là ma trận đối hợp (Involation Matrix) nếu Trong quá trình phát sinh ngẫu nhiên hai ma trận có những trường hợp: hay 11 12 1 22 2 ... 0 ... ... ... ... ... 0 0 ...              n n nn u u u u u u 11 12 1 22 2 ... 0 ... ... ... ... ... 0 0 ...              n n nn u u u u u u = 2 11 2 22 2 0 ... 0 0 ... 0 ... ... ... ... 0 0 ...                  n nn u u I u 2 11 2 22 2 0 ... 0 0 ... 0 ... ... ... ... 0 0 ...                nn u u u = 1 0 ... 0 0 1 ... 0 ... ... ... ... 0 0 ... 1             2 11 2 22 2 1 1 ... 1               nn u u u ( ) Để giải quyết vấn đề trên ta làm như sau: Khi phát sinh một phần tử nào đó dùng thuật toán Euclide tính nếu có nào đó thỏa thì phát sinh lại . Như vậy đảm bảo ma trận tam giác sau khi phát sinh có . 3. HỆ THỐNG MẬT MÃ HÓA KHÓA CÔNG KHAI 3.1. Lịch sử ra đời Một hệ thống mật mã hóa khóa công khai được các nhà khoa học Whitfield Diffie và Martin Hellman đưa ra năm 1976, dựa trên công trình trước đó của Ralph Merkle về phân phối khóa công khai. 3.2. Thuật toán mật mã hóa khóa công khai Tạo khóa: - Phát sinh n số nguyên tố phân biệt chẳng hạn mỗi số có chiều dài khoảng 333b. Tính . Phan Thị Ngọc Mai, Nguyễn Thị Thùy Trang 100 - Phát sinh ngẫu nhiên hai ma trận ma trận vuông gồm 6 hàng 6 cột giá trị khoảng 30b. - Tìm - Tìm ma trận nghịch đảo của ma trận ( ) - Dựa vào định lý số dư Trung Hoa tính - Tính ( ) ( ) ( ) - Khóa công khai: ( ) khóa bí mật: ( ) Mã hóa: chiều dài của bản rõ m mỗi lần mã hóa là 1500b Chia bản rõ m thành 5 khối ( ) Chọn ngẫu nhiên số nguyên có chiều dài 300b ( ) Giải mã: Tính ( ) ( ) ( ) ( ) ( ) ( ) Khôi phục lại bản rõ ban đầu. 3.2.1. Một số vấn đề khó khăn trong quá trình phát sinh khóa Khi phát sinh ma trận để tìm ma trận nghịch đảo của ma trận ta sử dụng một trong các cách đã trình bày trong chương 2 phần 2.3. Nhưng vấn đề đặt ra là các phần tử của ma trận nghịch đảo có thể chứa giá trị là những số thực dẫn tới việc mã hóa gặp nhiều khó khăn, thông tin có thể bị mất mát trong quá trình mã hóa. Sau đây là một số cách giải quyết để tìm được ma trận nghịch đảo mà đã đưa ra để sau khi tìm ma trận nghịch đảo giá trị những phần tử trong ma trận là những số nguyên. (1) Phát sinh ma trận vuông có định thức bằng 1. Khi đó khi tìm ma trận nghịch đảo các phần tử của hiển nhiên sẽ là các số nguyên. (2) Tìm ma trận nghịch đảo của ma trận dựa vào phương pháp đã được trình bày trong phần 2.2.2. (3) Chúng ta gọi là ma trận nghịch đảo của theo modulo nào đó, chẳng hạn. Khi đó khi giải mã ta phải trả lại tính theo công thức sau: ( ) ( ) ( ) Trong quá trình cài đặt ứng dụng, chúng tôi sử dụng phương pháp thứ 3, đó là tính toán dựa trên . 3.2.2. Đề xuất cách phát sinh ma trận Theo thuật toán đã đề ra ở trên, ma trận là một ma trận phát sinh ngẫu nhiên sau đó ta Phân tích và cải tiến phương pháp mật mã hóa khóa công khai 101 phải tính nghịch đảo của . Áp dụng phương pháp tìm ma trận nghịch đảo ở chương 2 phần 2.3. Như vậy ta sẽ không phát sinh trực tiếp mà sẽ tính được thông qua việc phát sinh 2 ma trận tam giác: Ma trận tam giác trên và ma trận tam giác dưới . 3.2.3. Tính bảo mật của hệ thống mã hóa khóa công khai a. Hiệu suất bảo mật thông tin Trong thực tế, bên cạnh việc bảo mật, hiệu quả bảo mật thông tin của một hệ thống mật mã hóa khoá công khai cần được xem xét. Nếu tỉ lệ hiệu quả bảo mật thông tin thấp thì sẽ tốn nhiều không gian lưu trữ và tài nguyên tính toán nhiều. Vì vậy hiệu quả bảo mật thấp thì sẽ không đạt được tốc độ và yêu cầu của mã hóa khóa công khai của chúng ta. Bây giờ ta sẽ ước lượng tỉ lệ mã hóa. Trong quá trình mã hóa chiều dài nhị phân của bản rõ là 1500b. Chú ý rằng chiều dài nhị phân của bản mã c xấp xỉ bằng . Do đó chúng ta có thể tính được tỉ lệ mã hóa của phương pháp chúng ta đề xuất là . Theo đó hiệu suất bảo mật của thuật toán là 4:3 so sánh hiệu suất bảo mật này với thuật toán RSA và El Gamal. Chú ý rằng RSA là 1:1 và của El Gamal là 2:1 từ đó ta thấy rằng hiệu suất bảo mật của chúng ta là tương đối thấp. b. Độ phức tạp của thuật toán Phần này ta sẽ nói về độ phức tạp của thuật toán trong quá trình mã hóa và giải mã. Trong thuật toán mà chỉ thực hiện trên năm phép chia và năm phép cộng modulo. Độ phức tạp của thuật toán nhân modulo là bình phương, độ phức tạp của phép cộng là tuyến tính. Do đó tổng độ phức tạp của thuật toán mã hóa là ( ) với k là tham số bí mật. Ta cũng phải chú ý rằng độ phức tạp của thuật toán mã hóa khóa trong RSA và ElGamal là bậc ba. So sánh trên cho ta thấy rằng thuật toán mã khóa đang khảo sát nhanh hơn RSA và ElGamal. 4. THỬ NGHIỆM VÀ ĐÁNH GIÁ Bảng 1: So sánh thời gian phát sinh ma trận của bài toán gốc với bài toán cải tiến. Cấu hình máy tính Số lần chạy Thời gian chạy trung bình Bài toán gốc Bài toán cải tiến AMD Turion X2 Dual-Core RM-72, 2.10GHz, RAM 4GB 1000 3128,386 2371,228 Intel Core Duo T5270, 1.40GHz, RAM 2GB 1000 2370,145 1780,231 Pentium (R) Dual – Core E550, 2.80 GHz, RAM 2GB 1000 1399,311 979,436 Phan Thị Ngọc Mai, Nguyễn Thị Thùy Trang 102 Bảng 2: So sánh thời gian phát sinh khóa của bài toán gốc với bài toán cải tiến. Cấu hình máy tính Số lần chạy Thời gian chạy trung bình Bài toán gốc Bài toán cải tiến AMD Turion X2 Dual-Core RM-72, 2.10GHz, RAM 4GB 1000 4838,898 3849,868 Intel Core Duo T5270, 1.40GHz, RAM 2GB 1000 4158,335 2950,664 Pentium (R) Dual – Core E550, 2.80 GHz, RAM 2GB 1000 2019,617 1599,743 Bảng 3: So sánh thời gian phát sinh khóa của bài toán cải tiến với RSA. Cấu hình máy tính Số lần chạy Thời gian chạy trung bình Bài toán gốc Bài toán cải tiến AMD Turion X2 Dual-Core RM-72, 2.10GHz, RAM 4GB 1000 2507,455 3849,868 Intel Core Duo T5270, 1.40GHz, RAM 2GB 1000 2352,212 2950,664 Pentium (R) Dual – Core E550, 2.80 GHz, RAM 2GB 1000 1351,309 1599,743 Bảng 4: So sánh thời gian mã hóa, giải mã của bài toán cải tiến với RSA. Dữ liệu/byte Thời gian mã hóa Thời gian giải mã RSA Bài toán cải tiến RSA Bài toán cải tiến 719 1567 406 1344 250 1949 2730 1154 2102 546 4053 3390 1747 2496 1341 5328 3510 2621 2907 1511 6721 3785 2699 3140 1560 5. KẾT LUẬN 5.1. Những kết quả đạt đƣợc Chứng minh tính đúng đắn của thuật toán. Các kết quả nghiên cứu và ứng dụng bước đầu đã thực hiện được mục đích của bài nghiên cứu. Bằng cách ứng dụng phương trình ma trận và định lý về số dư Trung Hoa trong việc xây dựng hệ thống mã hóa khóa công khai. Thuật toán đề xuất cho kết quả tốt hơn về thời gian so với bài toán gốc về các mặt phát sinh ma trận, phát sinh khóa. Chương trình thử nghiệm được xây dựng nhằm chứng minh tính khả thi của các kết quả nghiên cứu. Phân tích và cải tiến phương pháp mật mã hóa khóa công khai 103 5.2. Hƣớng phát triển Các kết quả của bài nghiên cứu có thể được áp dụng trong nhiều hệ thống mã hóa khóa công khai khác nhau và tiếp tục được cải tiến để có được tốc độ thực thi tốt hơn. Các kết quả có thể được áp dụng trên nhiều hệ thống bảo mật, thực hiện trong các giao dịch thương mại, thực hiện tạo và xác thực chữ ký điện tử. Tác giả mong muốn có thể tiếp tục phát triển để đưa các kết quả đã nghiên cứu vào ứng dụng trong thực tế. TÀI LIỆU THAM KHẢO 1. Bùi Xuân Hải, Trần Ngọc Hội, Trịnh Thanh Đèo, Lê Văn Luyện (2009). Đại số tuyến tính và ứng dụng, NXB Đại học Quốc gia TP.HCM. 2. Nguyễn Đình Thúc, Bùi Doãn Khanh (2006), Mã hóa thông tin lý thuyết và ứng dụng, NXB Lao động và xã hội. 3. Phạm Hữu Khang (2005). Lập trình C#, NXB Lao động Xã hội 4. A. Menezes, P. Van Oorschot, and S. Vanstone, Efficient Implementation, Handbook of Applied Cryptography, Chapter 2, 14, CRC Press, 1996. 5. Baocang WANG, Yongzhuang WEI, Yupu HU (2009), Fast public-key encryption scheme based on Chinese remainder theorem. 6. Rivest R L, Shamir A, Adleman L M. A method for obtaining digital signature and public key cryptosystems. Communications of the ACM, 1978, 21(2): 120-126 7. Solovay, R., and Strassen, V. A Fast Monte - Carlo test for primality. SIAM J. Comptnt. (March 1977), 84 - 85 8. 9. ABSTRACT ANALYSE AND IMPROVE PUBLIC KEY CRYPTOGRAPY METHODS Phan Thi Ngoc Mai * , Nguyen Thi Thuy Trang Ho Chi Minh city University of Food Industry *Email: maiptn@cntp.edu.vn In this article, we examine public key cryptography methods based on the Chinese Remainder Theorem and matrix equation in the process of key generation, encryption and decryption by Baocang WANG and Yongzhuang WEI, Yupu HU published in 2009 and along with the contents to the following improvements: generate fast the key matrix, generate fast key, deploy and compare it to the original mode with RSA method. Keyword: prime number and public key cryptography, Chinese remainder theorem.