Sơ đồ chữ ký kết hợp RSA và rabin - Hoàng Thị Mai

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 143 SƠ ĐỒ CHỮ KÝ KẾT HỢP RSA VÀ RABIN Hoàng Thị Mai* Tóm tắt: Bài báo này đưa ra một tiếp cận mới cho việc xây dựng các sơ đồ chữ ký trên vành ℤ, đó là kết hợp hai sơ đồ RSA và Rabin. Nếu như trong sơ đồ RSA, số mũ kiểm tra e cần nguyên tố cùng nhau với p – 1 và q – 1, trong sơ đồ Rabin e cần là ước của cả p – 1 lẫn q – 1 thì trong sơ đồ đưa ra ở bài báo này, số mũ kiểm tra e chỉ là ước của một trong hai giá trị p – 1 hoặc q – 1. Từ khóa: Sơ đồ chữ ký trên ℤ ∗ , Số mũ kiểm tra, Độ an toàn của sơ đồ chữ ký, Chi phí kiểm tra và chi phí tạo chữ ký. 1. ĐẶT VẤN ĐỀ Trên vành ℤ, có hai sơ đồ chữ ký số điển hình, một là sơ đồ RSA [1] và hai là sơ đồ Rabin cùng các phát triển của nó [2], [3], .... Đặc điểm nổi bật của hai sơ đồ trên là: Thứ nhất. Chi phí cho việc kiểm tra chữ ký thấp. Cụ thể với sơ đồ của Rabin và sơ đồ của Williams chỉ cần cỡ một phép nhân; với sơ đồ RSA số mũ kiểm tra e = 3 chỉ cần cỡ hai phép nhân trên ℤ ... Thứ hai. Có độ an toàn dựa trên độ khó của việc phân tích n theo nghĩa: Nếu phân tích được n ra thừa số thì sẽ phá được các sơ đồ này và cho đến nay vẫn chưa tồn tại thuật toán hiệu quả (thời gian đa thức) cho phép nếu phá được một trong các sơ đồ chữ ký nêu trên. Chính nhờ đặc điểm thứ nhất nên các sơ đồ trên luôn được sử dụng trong chứng chỉ số và trong những giao dịch mật mã kiểu “nhiều-một” (nhiều người gửi thông tin đến một người: chẳng hạn tại các đầu mối tiếp nhận hồ sơ; xác nhận tính hợp lệ của phiếu bầu cử trong việc bầu cử điện tử ...). Nếu như sơ đồ RSA kể từ khi xuất hiện đến nay hầu như không có một phát triển nào thì sơ đồ Rabin đã có hàng loạt những cải biên đáng kể theo các định hướng như: - Mở rộng các modulo dùng được như của L. Harn và T. Kiesler [7], của Kaoru Kurosawa và Wakaha Ogata [5], của M. Ela - M. Piva - D. Schipani [6], của Hoàng Thị Mai [9]... trong đó triệt để nhất là đóng góp của M. Ela, M. Piva và D. Schipani đưa ra năm 2013 cho phép xây dựng được hệ mật kiểu Rabin với modulo n là tích của hai số nguyên tố bất kỳ bởi việc dùng tổng Dedekind thay cho kí hiệu Jacobi. - Cải tiến thuật toán tạo chữ ký bằng cách kết hợp công thức tính căn và kí hiệu Jacobi của L. Harn và T. Kiesler [7] hoặc dùng kỹ thuật “tránh được” việc tính kí hiệu Jacobi của Hoàng Thị Mai [9]... - Thay số mũ kiểm tra từ 2 thành 3 của J. H. Loxton, David S. P. Khoo, Gregory J. Bird và Jennifer Seberry đưa ra năm 1992 [10] và của R. Scheidler đưa ra năm 1998 [11], Trong bài báo này, chúng tôi đưa ra một tiếp cận mới cho việc xây dựng các sơ đồ chữ ký trên vành ℤ, đó là kết hợp hai sơ đồ RSA và Rabin. Nếu như trong sơ đồ RSA, số mũ kiểm tra e cần nguyên tố cùng nhau với p – 1 và q – 1, sơ đồ Rabin thì e cần là ước của cả p – 1 lẫn q – 1 thì trong sơ đồ đưa ra ở bài báo này, ý nghĩa kết hợp thể hiện ở việc số mũ kiểm tra e chỉ là ước của một trong hai giá trị p – 1 hoặc q – 1. Trong mục 2, bài báo trình bày cơ sở toán học. Sơ đồ chữ ký kết hợp RSA và Rabin với số mũ kiểm tra e=3 được đề xuất trong mục 3. Mục 4 của bài báo đưa ra kết luận và hướng nghiên cứu phát triển. 2. CƠ SỞ TOÁN HỌC 2.1. Một số thống nhất và ký hiệu Công nghệ thông tin & Cơ sở toán học cho tin học Hoàng Thị Mai, “Sơ đồ chữ ký kết hợp RSA và Rabin.” 144 Trong bài viết này thống nhất sử dụng một số tham số và ký hiệu sau: - Tham số n: n = p.q với p, q là hai số nguyên tố sao cho p = 3.t + 1 với gcd(t,3) = 1 và gcd(3, q – 1) = 1 (1) Nhắc lại rằng với mọi a ∈ℤ tương ứng duy nhất với cặp a, a ∈ ℤ × ℤ với a = a mod p, a = a mod q và ánh xạ ngược, ký hiệu là CRT, được xác định theo công thức sau. CRT(u,v) = (. ( ). + . ( ). ) (2) - Ánh xạ trên bảo toàn phép nhân, tức là: CRT(u.x mod p,v.y mod q) = CRT(u,v). CRT(x,y) mod n (3) 2.2. Hàm CR và việc khai căn bậc 3 trên GF(p) với p ≠ 1 (mod 3) là số nguyên tố Định nghĩa 1. (Hàm CR) Cho p ≠ 1 (mod 9) là số nguyên tố lẻ, ký hiệu d = ⎣ ⎢ ⎢ ⎡3 ( – 1) ế ≠ 1 ( 3) ế ≡ 4 ( 9) ế ≡ 7 ( 9) (4) Hàm CR(., p): GF(p) → GF(p) được xác định theo công thức sau CR(a, ) = mod p. (5) Khi đó ta có bổ đề sau: Bổ đề 1. Cho p ≠ 1 (mod 9) là số nguyên tố lẻ. Khi đó với mọi a ∈ GF*(p) ta có: Nếu p ≠ 1 (mod 3) thì (, ) ≡ a (mod p). (6) Nếu p ≡ 4 (mod 9) thì (, ) ≡ a. (mod p). (7) Nếu p ≡ 7 (mod 9) thì (, ) ≡ a. (mod p). (8) Chứng minh Từ (5) thì CR(a, p) = a., nên thay d từ (4) vào đẳng thức trên ta có: Nếu p ≠ 1 mod 3 thì d.3 ≡ 1 (mod (p – 1)) hay (6) được chứng minh. Nếu p ≡ 4 (mod 9) thì d.3 = = 1 + 2 hay (7) được chứng minh. Nếu p ≡ 7 (mod 9) thì d.3 = = 1 + hay (8) được chứng minh. 2.3. Các tập E(β) và B(β) Mệnh đề 1. Cho β∈ℤ ∗ sao cho = ≠ 1 (mod p). (9) Ký hiệu () = = ,, . (10) () = = ,, . (11) Ta có: Thứ nhất. E(β) là tập các căn bậc 3 của đơn vị trong GF(p). Thứ hai. Với mọi a ∈ℤ ∗ , nếu = , (12) lấy j = – i mod 3 (13) thì điều kiện sau được thỏa mãn. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 145 . = 1 (14) Chứng minh: Từ (9) ta có ε = β ≡ 1 (mod p) nên ε ≠ 1 chính là căn bậc 3 của đơn vị trong GF(p) và do 3 là số nguyên tố nên tập B(β) chính là tập các căn bậc 3 của đơn vị trong GF(p). Xét a. b mod p. Theo (11) thì b = β mod n, do p là ước của n nên b ≡ β (mod p). Cho nên a. b ≡ a . β ≡ a β (mod p). Theo (9) và (12) thì vế phải của đồng dư thức trên trở thành e. ε , lại theo (10) và (13) thì e = ε mod p nên a. b ≡ e. ε ≡ ε ≡ ε ≡ 1 (mod p). (15) Như vậy, đẳng thức (14) đã được chứng minh. 2.4. Quan hệ giữa việc giải phương trình đồng dư bậc 3 trên ℤ và việc phân tích n ra thừa số nguyên tố Xét phương trình với a ∈ℤ. x ≡ a (mod n). (16) Ta có kết quả sau. Bổ đề 2. Điều kiện cần và đủ để (16) có nghiệm là = 1 (17) Khi này một nghiệm của (16) được cho bởi công thức sau x = CRT(CR(a mod p, p), CR(a mod q, q)). (18) Chứng minh: Ký hiệu a = a mod p và a = a mod q. Điều kiện (17) là tương đương với a mod p = 1. Theo (7) và (8) thì đây cũng là điều kiện cần và đủ để CR(a mod p, p) thỏa mãn (a, p) ≡ a (mod p). Còn theo (6) ta luôn có đồng dư thức sau (a, q) ≡ a (mod q). Như vậy: (a mod p, p), (a mod q, q) = ((a, p), (a, q)) = a, p mod p, a, q mod q = a, a = a. Bổ đề đã được chứng minh. Từ bổ đề trên ta thu được hệ quả sau. Hệ quả 1. Nếu phân tích được n ra các thừa số p và q thì luôn giải được phương trình (16). Cho đến nay chưa có một công bố nào cho phép tìm được 1 nghiệm nào đó của (16) mà không cần biết phân tích của n. Ngược lại, cũng chưa tồn tại một công bố nào cho phép phân tích được n nếu luôn giải được phương trình (16). Ở đây, chúng tôi đưa ra một kết quả có lẽ là gần nhất để giải quyết vấn đề ngược lại như sau. Công nghệ thông tin & Cơ sở toán học cho tin học Hoàng Thị Mai, “Sơ đồ chữ ký kết hợp RSA và Rabin.” 146 Mệnh đề 2. Nếu tìm được hai nghiệm khác nhau của phương trình (16) thì sẽ phân tích được n. Chứng minh: Nếu a∉ℤ ∗ thì ta có luôn một ước của n là gcd(a, n), và do đó, phân tích được n. Ngược lại, giả sử u ≠ v là hai nghiệm của (16) với a∈ℤ ∗ nào đó, khi đó u và v đều thuộc ℤ ∗ cho nên w = u/v mod n sẽ là một căn bậc 3 không tầm thường của đơn vị theo modulo n. Tức là: w ≠ 1 và (19) ≡ 1 ( ). (20) Từ (20) ta có w mod q = 1 và do gcd(3, q – 1) = 1 nên ta có w mod q = 1. (21) Còn từ (19) nên w mod p≠ 1. (22) Từ (21) và (22) ta thu được: q = gcd(w – 1,n) Như vậy, tìm được ước q của n,và do đó, phân tích được n. Vậy, Mệnh đề2 đã được chứng minh. 3. SƠ ĐỒ RSA-RABIN3 Trong phần này chúng tôi đưa ra sơ đồ kết hợp giữa RSA và Rabin với số mũ kiểm tra bằng 3, ký hiệu là sơ đồ RSA-Rabin3. 3.1. Mô tả sơ đồ RSA-Rabin3 Sơ đồ được mô tả qua 3 mục con đó là: Tham số hệ thống, thuật toán tạo chữ ký và thuật toán kiểm tra chữ ký. Sơ đồ RSA-Rabin3 được mô tả dưới dạng một sơ đồ nguyên thủy theo nghĩa tập các văn bản chính là ℤ 3.1.1. Tham số hệ thống Mỗi thành viên tự chọn số nguyên n = p.q với p và q như đã nêu trong điều kiện (1) sao cho việc phân tích n ra thừa số là khó. d và d được tính theo như giá trị d tương ứng trong công thức (4). Tìm giá trị β nhỏ nhất thỏa mãn điều kiện (9) và xây dựng các tập E=E(β), B=B(β) theo hai công thức (10) và (11). Khi này: Tham số mật của người ký là bộ (p, q, E) còn tham số công khai tương ứng là bộ (n,B). 3.1.2. Thuật toán tạo chữ ký Thuật toán 1. Input: a ∈ℤ là văn bản cần ký. Output: (s, j) ∈ℤ × ℤ là chữ ký lên m. 1. r = a mod p (23) 2. if (r == e) j = – i mod 3; (24) 3. u = a.b mod n; (25) 4. s = CRT(CR(u mod p, p),CR(u mod q, q)); (26) 5. return (s, j); (27) 3.1.3. Thuật toán kiểm tra Thuật toán 2. Input: (s, j) là chữ ký lên a của người có tham số công khai (n, B). Output: Accept∈ {0,1} theo nghĩa Accept = 1 khi và chỉ khi chấp nhận (s, j) là chữ ký lên a của người có tham số công khai là (n, B). Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 147 1. u = a.b mod n; 2. if (u == s mod n)Accept = 1; else Accept = 0; (28) 3. return Accept 3.2. Phân tích sơ đồ RSA-Rabin3 3.2.1. Sơ đồ RSA-Rabin3 là đúng đắn Tính đúng đắn của sơ đồ RSA-Rabin3 được cho bởi kết quả sau. Mệnh đề 3. Mọi chữ ký (s, j) lên văn bản a được tạo từ thuật toán 1 đều có giá trị đầu ra bằng 1 theo thuật toán 2. Chứng minh: Với công thức (23) ở bước 1 và điều kiện (24) đưa ra trong bước 2 của thuật toán 1 thì văn bản a thỏa mãn điều kiện (12) đưa ra trong mệnh đề 1. Từ đó với j xác định trong bước 2 thì theo kết luận thứ hai của mệnh đề 1, ta có giá trị u tính theo (25) sẽ thỏa mãn điều kiện u mod p = 1. Như vậy, theo bổ đề 1 thì giá trị s tính theo (26) chính là một nghiệm của phương trình (16), nói một cách khác ta sẽ có đồng dư thức: u ≡ s (mod n). (29) Do giá trị u tính được tại bước 1 của thuật toán 2 cũng chính là giá trị u tính theo (25), nên từ đồng dư thức (29) ta có điều kiện ở bước 2 của thuật toán 2 là đúng. Vì vậy Accept =1. Đây là điều cần chứng minh. 3.2.2.Độ an toàn của sơ đồ RSA-Rabin3 Rõ ràng để tạo ra một chữ ký hợp lệ lên văn bản a theo sơ đồ RSA-Rabin3 thì người giả mạo (không có bộ tham số mật (p, q, E)) cần tìm được một nghiệm của phương trình (16) với vế phải là a.b mod n (i = 0, 1, 2). Như đã nêu sau hệ quả 1 thì chưa tồn tại thuật toán nào ngoài thuật toán biết phân tích n ra thừa số cho nên chúng ta có được kết quả sau. Mệnh đề 4. Độ an toàn của sơ đồ RSA-Rabin3 được dựa vào tính khó phân tích của tham số n ra thừa số. 3.2.3. Chi phí tính toán cho việc tạo và việc kiểm tra chữ ký trong sơ đồ RSA-Rabin3 Xét chi phí tính toán của thuật toán tạo chữ ký (thuật toán 1)  Từ (23) cần một phép tính lũy thừa  Từ (25) cần một phép nhân  Từ (26) cần một phép tính hàm CRT và hai phép tính CR(.,p) và CR(.,q). Theo (5) thì hai phép tính CR(.,p) và CR(.,q) chính là hai phép lũy thừa trên GF(p) và GF(q). Như vậy, thuật toán tạo chữ ký cần đến một phép nhân, ba phép tính lũy thừa và một phép tính hàm CRT. Xét chi phí tính toán của thuật toán kiểm tra chữ ký (thuật toán 2)  Ở bước 1 cần một phép nhân  Ở bước 2 cần một phép lũy thừa 3 trên ℤ (bằng 2 phép nhân) Vậy thuật toánkiểm tra chữ ký cần đến ba phép nhân. Nếu ký hiệu t, t và t lần lượt là thời gian thực hiện một phép nhân, phép lũy thừa và phép tính hàm CRT ta thu được kết quả sau. Mệnh đề 5. Chi phí của thuật toán tạo chữ ký, ký hiệu , và của thuật toán kiểm tra, ký hiệu , trong sơ đồ RSA-Rabin3 được cho theo công thức sau = + 3. + (30) = 3. . (31) 4. MỘT SỐ VẤN ĐỀ CÓ THỂ PHÁT TRIỂN Với ý tưởng được đề xuất trong bài báo này bạn đọc có thể phát triển theo một số hướng sau. Công nghệ thông tin & Cơ sở toán học cho tin học Hoàng Thị Mai, “Sơ đồ chữ ký kết hợp RSA và Rabin.” 148 Thứ nhất. Tìm hiểu khả năng tránh được việc tính giá trị r = a mod p trong bước 1 của thuật toán tạo chữ ký vì bản chất của việc làm này giống hệt như việc phải tính giá trị Jacobi = a mod p trong các sơ đồ phát triển từ Rabin. Thứ hai. Thay số mũ kiểm tra từ 3 thành e là một số nguyên lẻ bất kỳ. TÀI LIỆU THAM KHẢO [1]. R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryp-tosystems”, Comm. ACM, vol. 21, no. 2 (1978), pp. 120–126. [2]. Rabin, M. O. (1978), “Digitalized signatures”, Foundations of Secure Computations, R. Lipton and R. DeMillo editors, Academic Press New York, 1978. [Rabin M. O. 1978] [3]. H. C. Williams, “A modification of the RSA public-key procedure”, IEEE Trans. Inform. Theory 26 (1980), 726-729 [4]. H. C. Williams, “An M3 a public-key encryption scheme, Advances in Cryptology”, CRYPTO '85, Lecture Notes in Computer Science, vol. 218, Springer-Verlag, Berlin, pp. 358-368. [5]. Kaoru Kurosawa; Wakaha Ogata; “Efficient Rabin-type Digital Signature Scheme”, Designs, Codes and Cryptgraphy, January 1999, Volume 16, Issue 1, pp53-64 [6]. M.Ela, M.Piva, D.Schipani, “The Rabin Cryptosystem revisited”, https://www.math.uzh.ch/fileadmin/user/davide/publikation/RabinSchemev39.pdf [7]. L.Harn; T.Kiesler, “Improved Rabin’s scheme with high efficiency”, Electronics Letters (Volume: 25, Issue: 11, 25 May 1989) [8]. International Standard ISO/IEC 27005 Information technology – Security techniques- Information Security risk management. [ISO/IEC 2008] [9]. Hoàng Thị Mai, “Cải biên chữ ký số Rabin”, Tạp chí Nghiên cứu Khoa học và Công nghệ Quân sự, số đặc san Công nghệ thông tin, 12-2017, ISSN 1859-1043, pp.73-82 [10]. J. H. Loxton, David S. P. Khoo, Gregory J. Bird and Jennifer Seberry, “A Cubic RSA Code Equivalent to Factorization”, Journal of Cryptology 5 (1992), 139-150. [11]. R. Scheidler , “A Public-Key Cryptosystem Using Purely Cubic Fields”, Journal of Cryptology 11 (1998), 109–124 ABSTRACT THE SIGNATURE SCHEME IN COMBINATION WITH RSA AND RABIN In this paper, a new approach to the development of Zn signature schemes that is combining RSA and Rabin is presented. While the exponent e in the RSA is required to be the relatively prime with p - 1 and q – 1, or that in the Rabin needs to be a divisor of both p - 1 and q – 1; then in this paper, the exponent e is only required to be a divisor of either (p – 1) or (q – 1). Keywords:Signature schemes inℤ ∗ , The exponent e, Security of signature schema,The cost ofverification, The cost of generating signature. Nhận bài ngày 25 tháng 01 năm 2018 Hoàn thiện ngày 20 tháng 02 năm 2018 Chấp nhận đăng ngày 26 tháng 02 năm 2018 Địa chỉ: Trường Đại học Thủ đô Hà Nội. *Email: htmai@daihocthudo.edu.vn.