Xây dựng lược đồ chữ ký số trên bài toán phân tích số

Nội dung text: Xây dựng lược đồ chữ ký số trên bài toán phân tích số

1. 92 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN PHÂN TÍCH SỐ Hoàng Thị Mai1 Trường Đại học Thủ đô Hà Nội Tóm tắt: Trong các giao dịch điện tử, chữ ký số (Digital Signature) được sử dụng nhằm đáp ứng yêu cầu chứng thực về nguồn gốc và tính toàn vẹn của thông tin. Bài báo trình bày lược đồ chữ ký số RSA, lược đồ đầu tiên theo hệ mật khóa công khai dựa trên bài toán phân tích số và hướng phát triển các lược đồ chữ ký số mới dựa trên tính khó giải của bài toán này. Từ khoá: Chữ ký số, lược đồ chữ ký số, bài toán phân tích số, chữ ký số RSA. 1. ĐẶT VẤN ĐỀ Với sự phát triển mạnh mẽ của công nghệ thông tin và truyền thông, đặc biệt là mạng Internet, ngày càng có nhiều thông tin được lưu trữ trên máy tính và truyền đi trên mạng. Theo [1], một hệ truyền tin được gọi là truyền thông tin an toàn và bảo mật khi có các đặc tính sau: 1- Tính bảo mật (Confidentiality): ngăn chặn được vấn đề xem trộm thông báo; 2- Tính chứng thực (Authentication): nhằm đảm bảo rằng thông báo gửi đi thực sự là của người gửi và không bị thay đổi trong quá trình truyền tin; 3- Tính không từ chối (Nonrepudiation): nhằm xác định rằng thông báo là do chính người gửi gửi đi, người gửi không thể chối bỏ trách nhiệm. Chữ ký số là một cơ chế cho phép đảm bảo tính chứng thực và tính không từ chối của một hệ truyền tin. Một chữ ký số kèm theo mỗi thông báo được tạo ra dựa trên giá trị băm của thông điệp và một cách mã hóa giá trị băm này nhờ khóa riêng của người gửi. Hầu hết các lược đồ chữ ký số hiện nay đều dựa trên tính khó của bài toán: phân tích một số nguyên lớn ra các thừa số nguyên tố, bài toán khai căn và bài toán logarit rời rạc trong modulo hợp số. Thuật toán chữ ký số đầu tiên (RSA) [2] được đề xuất và công bố bởi Ron 1 Nhận bài ngày 16.01.2016, gửi phản biện và duyệt đăng ngày 25.01.2016. Liên hệ tác giả: Hoàng Thị Mai; Email: htmai@daihocthudo.edu.vn. .
2. TẠP CHÍ KHOA HỌC SỐ 2/2016 93 Rivest, Adi Shamir và Len Adleman vào năm 1977 tại Viện Công nghệ Massachusetts (MIT) Hoa Kỳ. Thuật toán chữ ký số này được xây dựng dựa trên tính khó của bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố. Dựa trên nền tảng thuật toán chữ ký số RSA, có nhiều hướng nghiên cứu phát triển các lược đồ chữ ký số. 2. LƯỢC ĐỒ CHỮ KÝ SỐ RSA 2.1. Bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố Bài toán phân số về cơ bản có thể được phát biểu như sau: Cho số , hãy tìm biểu diễn: , với ei ≥1 và pi là các số nguyên tố. Trong hệ mật RSA [2], bài toán phân tích số được sử dụng làm cơ sở để hình thành cặp khóa công khai (e)/bí mật (d) cho mỗi thực thể k ý và có thể phát biểu như sau: − Cho p, q là 2 số nguyên tố lớn và mạnh; − Từ p và q dễ dàng tính được: ; − Từ n rất khó tìm được p và q. Với việc giữ bí mật các tham số p, q thì khả năng tính được khóa mật (d) từ khóa công khai (e) và modulo n là rất khó thực hiện, nếu p, q được chọn đủ lớn và mạnh [3,4]. Hiện tại, bài toán trên vẫn được coi là bài toán khó do chưa có giải thuật thời gian đa thức cho nó và hệ mật RSA là một chứng minh thực tế cho tính khó giải của bài toán này. Trong ứng dụng thực tế, các tham số {p,q} của hệ mật RSA có thể chọn theo Chuẩn X9.31 [5] hay FIPS 186-3 [6] của Hoa Kỳ như sau: Chuẩn X9.31. Theo X9.31, tiêu chuẩn đối với các tham số {p,q} của hệ mật RSA bao gồm: - Độ dài modulo n (nlen) là: 1024+256s (s ≥ 0). - 2511+128s ≤ p, q ≤ 2511+128s (s ≥ 0). - |p – q| > 2412+128s (s ≥ 0). - Các ước nguyên tố của p±1 và q±1 (các số nguyên tố bổ trợ), k ý hiệu là: p1, p2 và: q1, q2 phải thỏa mãn các thông số kỹ thuật được cho trong Bảng 1.1 dưới đây: Bảng 1: Tiêu chuẩn an toàn đối với các số nguyên tố bổ trợ nlen Độ dài tối thiểu của p1, p2 và Độ dài tối đa của p1, p2 và q1, q2 q1, q2 1024 + 256.s > 100 bit ≤ 120 bit Chuẩn FIPS 186-3. Theo FIPS 186-3, tiêu chuẩn đối với các tham số {p,q} của hệ mật RSA bao gồm:
3. 94 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI - 2511+128s ≤ p, q ≤ 2511+128s (s ≥ 0). - |p – q| > . - Các ước nguyên tố của p±1 và q±1 (các số nguyên tố bổ trợ), k ý hiệu là: p1, p2 và q1, q2 phải thỏa mãn các thông số kỹ thuật được cho trong Bảng 2 dưới đây: Bảng 2: Tiêu chuẩn an toàn đối với các số nguyên tố bổ trợ Độ dài của Độ dài tối thiểu Độ dài tối đa của len(p1) + len(p2) modulo n của p1, p2, q1, q2 và len(q1) + len(q2) (nlen) Các số nguyên tố Các số nguyên tố xác xuất chứng minh được 1024 bit > 100 bit 140 bit 170 bit < 1518 bit < 750 bit 2.2. Chữ ký số RSA 2.2.1. Sơ đồ chung của chữ ký số Một sơ đồ chữ ký số là bộ năm (P, A, K, S, V) thoả mãn các điều kiện dưới đây: - P là tập hữu hạn các thông báo có thể có. - A là tập hữu hạn các chữ ký có thể có. - K là tập tập hữu hạn các khoá. Mỗi khóa k ∈ K gồm hai thành phần k=(k1,k2) trong đó k1 là khóa bí mật dành cho việc ký, k2 là khóa công khai dành cho việc kiểm thử chữ ký. - S là tập các thuật toán ký. - V là tập các thuật toán xác minh chữ ký. - Với mỗi khoá k=(k1,k2) tồn tại một thuật toán ký trong S là và một thuật toán xác minh trong V là sao cho thỏa mãn điều kiện sau đây với mỗi bức điện x ∈ P và mỗi chữ ký y∈ A: Trong sơ đồ trên, mỗi chủ thể sở hữu một cặp khóa k=(k1,k2), công bố công khai khóa k2 để mọi người có thể xác thực chữ ký của mình, giữ bí mật khóa k1 để thực hiện ký trên các thông báo mà mình muốn gửi đi. Các hàm và phải tính được một cách dễ
4. TẠP CHÍ KHOA HỌC SỐ 2/2016 95 dàng (trong thời gian đa thức) khi biết k1. Tuy nhiên, hàm là khó tính được nêu không biết k1. Điều này đảm bảo bí mật cho chữ ký và chống giả mạo chữ ký. 2.2.2. Chữ ký số RSA Một sơ đồ chung chữ ký số RSA là bộ năm (P, A, K, S, V) thoả mãn các điều kiện dưới đây: - P = A = Zn với n = p.q là tích của hai số nguyên tố lớn p, q. - K là tập hợp các khóa. Mỗi khóa k∈ K là một bộ gồm hai khóa k=(k1,k2), trong đó k1 là khóa bí mật dành cho việc ký, k2 là khóa công khai dành cho việc kiểm thử chữ ký, được xác định k1=(d,n), k2=(e,n)với e, d là số nguyên thuộc và - Với mỗi khoá k=(k1,k2), các hàm ký và xác thực chữ ký được xác định như sau: Từ sơ đồ chung, ta cụ thể từng giai đoạn của sơ đồ chữ ký RSA như sau: Thuật toán hình thành khóa - Sinh 2 số nguyên tố p và q lớn. - Tính - Chọn khóa công khai e là một giá trị ngẫu nhiên thỏa mãn: và . - Tính khóa bí mật d là phần tử nghịch đảo của e theo công thức: Thuật toán hình thành chữ k ý - Lựa chọn hàm băm (hash function) H: ; - Tính giá trị đại diện cho bản tin cần k ý z: - Hình thành chữ k ý theo công thức: Thuật toán kiểm tra - Tính giá trị đại diện cho bản tin cần k ý z: - Tính giá trị theo công thức:
5. 96 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI - Kiểm tra nếu thì chữ ký s hợp lệ, do đó nguồn gốc và tính toàn vẹn của bản tin cần thẩm tra M được công nhận. 2.2.3. Mức độ an toàn của thuật toán chữ ký số RSA Mức độ an toàn của thuật toán chữ ký số RSA được đánh giá qua khả năng chống tấn công làm lộ khóa mật và khả năng chống giả mạo chữ k ý. Khả năng chống tấn công làm lộ khóa mật Việc tấn công làm lộ khóa mật có thể thực hiện qua 2 cách như sau: - Phân tích modulo n để tìm p và q, từ đó tính rồi tính khóa mật theo công thức: . - Từ thuật toán hình thành chữ k ý: tính khóa bí mật d nhờ giải: Ở cách thứ nhất, kẻ tấn công phải giải bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố (Bài toán phân tích số). Còn ở cách thứ hai, kẻ tấn công phải giải bài toán logarit rời rạc trong modulo n với n là hợp số (Bài toán logarit rời rạc trong modulo hợp số). Hiện tại, cả 2 bài toán trên vẫn được coi là bài toán khó [2] và trên thực tế hệ mật RSA vẫn chưa bị phá vỡ bởi việc giải các bài toán này. Khả năng chống giả mạo chữ k ý Điều kiện để chữ k ý s tương ứng với thông điệp dữ liệu x được công nhận là hợp lệ nếu cặp (x,s) thỏa mãn điều kiện: . Do đó, về l ý thuyết có thể chọn một giá trị bất kỳ từ việc tính làm chữ k ý giả mạo. Tuy nhiên, để tìm được giá trị chính xác của chữ k ý tương ứng với thông điệp dữ liệu x kẻ tấn công phải giải được bài toán khai căn trong modulo n với n là hợp số (Bài toán khai căn trong modulo hợp số): . Tương tự như bài toán phân tích số và bài toán logarit rời rạc (trong modulo hợp số), bài toán khai căn trong modulo hợp số cũng được coi là bài toán khó [2] và độ an toàn của thuật toán RSA vẫn chưa bị đe dọa bởi việc giải bài toán này. 3. HƯỚNG NGHIÊN CỨU XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN CƠ SỞ BÀI TOÁN PHÂN TÍCH SỐ Trên nền tảng của bài toán phân tích số, có nhiều hướng nghiên cứu phát triển thuật toán chữ ký số RSA. [7] và [8] nghiên cứu việc sinh các tham số đầu vào cho thuật toán nhằm tăng mức độ an toàn của thuật toán, [9] nghiên cứu xác thực bản tin bằng chữ ký số
6. TẠP CHÍ KHOA HỌC SỐ 2/2016 97 RSA-PSS theo cách sử dụng hai thuật toán nền tảng là thuật toán mã hóa và kiểm tra EMSA-PSS cho bản tin và thuật toán tạo chữ ký RSA để xác thực bản tin. Nhằm tăng độ an toàn cho các lược đồ chữ ký số, có một mạch nghiên cứu khác là xây dựng lược đồ chữ ký dựa trên nền tảng của hai bài toán: phân tích số và logarit rời rạc. Năm 1998, Shao [10] và Li-Xiao [11] đã đề xuất các lược đồ chữ ký số dạng này. Sau đó Lee [12] năm 2000 chứng minh rằng lược đồ chữ ký của Shao là không an toàn như báo cáo. Để khắc phục những nhược điểm của lược đồ chữ ký Shao, He [13] năm 2001 đề xuất một sơ đồ chữ ký số cũng dựa vào bài toán phân tích số nguyên và bài toán logarit rời rạc; sử dụng cùng modulo và một tập số mũ và các khóa bí mật. Vào năm 2002, Hung Min Sun [14] chỉ ra rằng các lược đồ đó chỉ dựa trên bài toán logarit rời rạc. Năm 2003, Wang, Lin và Chang [15] đề xuất một lược đồ chữ ký dựa trên cả hai bài toán khó. Năm 2007, Wei [16] đưa ra hai lược đồ cải tiến từ hai lược đồ của Shao và Li-Xiao nhằm chống lại những tấn công vào hai lược đồ này. Năm 2009, Lin, Gun và Chen [17] cho rằng các lược đồ của Wei vẫn không an toàn do có thể giả mạo chữ ký hợp lệ của một thông điệp bằng cách sử dụng phương pháp của Pollard và Schnorr. Theo một hướng nghiên cứu khác, [18] đề cập đến việc xây dựng một lược đồ chữ ký số trên cơ sở bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố (bài toán phân tích số) kết hợp với bài toán khai căn trong modulo hợp số (bài toán khai căn). Tuy nhiên, đóng vai trò quyết định đến mức độ an toàn của lược đồ là bài toán phân tích số. Cũng theo mạch nghiên cứu này, [19] đề xuất một phương pháp xây dựng lược đồ chữ ký số theo cùng nguyên tắc đã được chỉ ra trong [18] nhưng phương pháp đề xuất ở đây được mô tả dưới dạng một lược đồ tổng quát từ đó cho phép triển khai ra các lược đồ chữ ký số khác nhau cho các ứng dụng thực tế. Hơn nữa, phương pháp đề xuất ở đây được xây dựng trên cơ sở bài toán phân tích số kết hợp với bài toán logarit rời rạc trong modulo hợp số (bài toán logarit rời rạc) nên cho phép tạo ra các lược đồ chữ ký có hiệu quả thực hiện (tốc độ, tài nguyên hệ thống) cao hơn lược đồ chữ ký được xây dựng trong [18]. Cũng tương tự như bài toán khai căn đối với lược đồ trong [18], bài toán logarit rời rạc cũng không có vai trò quyết định tới độ an toàn của các lược đồ xây dựng theo phương pháp mới đề xuất trong [19]. 4. KẾT LUẬN Nghiên cứu phát triển các lược đồ chữ ký số mới luôn là vấn đề đặt ra trong lĩnh vực an toàn và bảo mật thông tin. Bài báo đã trình bày tổng quan một số kiến thức nền tảng xây dựng lược đồ chữ ký số trên bài toán phân tích số và các hướng nghiên cứu phát triển các lược đồ chữ ký số dựa trên bài toán này. Các dạng lược đồ chữ ký số mới được xây dựng đều có độ an toàn được đảm bảo bằng tính khó giải của bài toán phân tích một số nguyên
7. 98 TRƯỜNG ĐẠI HỌC THỦ ĐÔ HÀ NỘI lớn ra các thừa số nguyên tố. Từ các hướng nghiên cứu này, các dạng lược đồ mới đề xuất có thể phát triển thành các lược đồ chữ k ý số ứng dụng trong thực tế. TÀI LIỆU THAM KHẢO 1. Stallings, W., and Brown, L. (2011), Cryptography and Network Security, Principles and Practice, Prentice Hall. 2. R. L. Rivest, A. Shamir, and L. M. Adleman (1978), A Method for Obtaining Digital Signatures and Public Key Cryptosystems / Commun. of the ACM, Vol. 21, No. 2, pp. 120- 126. 3. Burt Kaliski (2000), “RSA Digital Signature Standards”, RSA Laboratories 23rd National Information Systems Security Conference, October, pp.16-19. 4. National Institute of Standards and Technology, NIST FIPS PUB 186-3, Digital Signature Standard, U.S. Department of Commerce, 1994. 5. Lều Đức Tân, Hoàng Văn Thức (2006),”Một thuật toán sinh cặp số nguyên tố RSA mạnh p, q thoả mãn điều kiện |p - q| có ước nguyên tố lớn,” Tạp chí Nghiên cứu khoa học kỹ thuật và công nghệ quân sự số 14, tr.63-67. 6. Hoàng Văn Thức (2010), “Thuật toán sinh tham số RSA an toàn,” Tạp chí nghiên cứu khoa học và công nghệ quân sự, tr.40-45. 7. Bùi Việt Hồng (2007), “Xây dựng thuật toán xác thực bản tin bằng chữ ký số theo hệ ký RSA- PSS,”. Tạp chí Nghiên cứu khoa học kỹ thuật và công nghệ quân sự số 19, tr.59-64. 8. Z. Shao (1998), “Signature Schemes Based on Factoring and Discrete Logarithms”. Computers and Digital Techniques, IEE Proceeding, 145(1), pp.33-36. 9. J. Li and G. Xiao, “Remarks on New Signature Scheme Based on Two Hard Problems,” Electronics Letters, 34(25), p.2401. 10. N. Y. Lee (1998), “Security of Shao’s Signature Schemes Based on Factoring and Discrete Logarithms,” IEE Proceeding, 146(2), pp.119-121, 1999. 11. W. H. He (2001), “Digital Signature Scheme Based on Factoring and Discrete Logarithms,” Electronics Letters, 37(4), pp.220-222. 12. C. T. Wang, C. H. Lin, and C. C. Chang (2003), “Signature Scheme Based on Two Hard Problems Simultaneously”, Proceedings of the 17th International Conference on Advanced Information Networking and Application, Mar. 27-29, IEEE Computer Society, Washington, DC, USA, pp.557-561. 13. S. Wei (2007), “Digital Signature Scheme Based on Two Hard Problems”, International Journal of Computer Science and Network Security, 7(12), pp.207-209, December. 14. H. Lin, C. Gun, and C. Chen (2009), “Comments on Wei’s Digital Signature Scheme Based on Two Hard Problems,” IJCSNS International Journal of Computer Science and Network Security, 9(2), pp.1-3.
8. TẠP CHÍ KHOA HỌC SỐ 2/2016 99 15. Lê Văn Tuấn, Lưu Hồng Dũng, Nguyễn Tiền Giang (2014), “Phát triển lược đồ chữ ký trên bài toán phân tích số,” Tạp chí Nghiên cứu khoa học và công nghệ quân sự - Đặc san CNTT. 16. Hoàng Thị Mai, Nguyễn Hữu Mộng, Lưu Hồng Dũng (2015), “Một dạng lược đồ chữ ký xây dựng trên bài toán phân tích số”, Tạp chí Nghiên cứu khoa học và công nghệ quân sự, số 39. DEVELOPING DIGITAL SIGNATURE SCHEMES BASED ON INTEGER FACTORIZATION PROBLEM Abstract: In the area of safety and security information, developing new digital signature schemes is always the concern of researchers. In this paper, we present the RSA digital signature scheme, the first public-key scheme and developing digital signature schemes based on integer factorization problem. The result of this research can be applied to develop signature schemes in many applications in reality. Keywords: Digital Signature, Digital Signature Scheme, Integer Factorization Problem, RSA.