Sơ đồ chữ ký kết hợp RSA và rabin

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.