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

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. 
. 
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: 
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 < 496 bit < 239 bit 
 2048 bit > 140 bit < 1007 bit < 494 bit 
 3072 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ễ 
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: 
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ố 
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 
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. 
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.