Sơ đồ chữ ký kết hợp RSA và Rabin
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óm tắt nội dung Sơ đồ chữ ký kết hợp RSA và Rabin, để xem tài liệu hoàn chỉnh bạn click vào nút "TẢI VỀ" ở trên
hiê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.
File đính kèm:
so_do_chu_ky_ket_hop_rsa_va_rabin.pdf
