Xây dựng lược đồ chữ ký số dựa trên một dạng bài toán khó mới

Công nghệ thông tin 
N. Đ. Thụy, L. H. Dũng, “Xây dựng lược đồ chữ ký số  bài toán khó mới.” 174 
XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN 
 MỘT DẠNG BÀI TOÁN KHÓ MỚI 
Nguyễn Đức Thụy1, Lưu Hồng Dũng2* 
Tóm tắt: Bài báo đề xuất một phương pháp xây dựng thuật toán chữ ký số dựa 
trên tính khó của bài toán logarit rời rạc kết hợp khai căn trên Zp. Đây là một dạng 
bài toán khó mới, lần đầu được đề xuất và ứng dụng để xây dựng các thuật toán chữ 
ký số. Từ phương pháp được đề xuất có thể xây dựng một lớp thuật toán chữ ký số có 
độ an toàn cao cho các ứng dụng trong thực tế. 
Từ khóa: Digital signature; Digital signature algorithm; Digital Signature Schema; Discrete logarithm 
problem. 
1. ĐẶT VẤN ĐỀ 
Trong [1,2] đề xuất một phương pháp xây dựng thuật toán chữ ký số dựa trên 
tính khó của việc giải bài toán logarit rời rạc trên Zp. Ưu điểm của phương pháp 
mới đề xuất là từ đó có thể triển khai một lớp thuật toán chữ ký số cho các ứng 
dụng khác nhau. Tuy nhiên, độ an toàn của các thuật toán chữ ký được xây dựng 
theo phương pháp này chỉ được đảm bảo bởi độ khó của việc giải bài toán logarit 
rời rạc - DLP (Discrete Logarithm Problem) trên Zp. Do đó, nếu có một giải thuật 
thời gian đa thức cho bài toán này (DLP) thì tính an toàn của các thuật toán sẽ bị 
phá vỡ hoàn toàn. Nâng cao độ an toàn cho các thuật toán chữ k ý số dựa trên tính 
khó của việc giải đồng thời 2 bài toán khó là một hướng tiếp cận đang nhận được 
nhiều sự quan tâm của các nhà nghiên cứu, trong [3 – 10] các tác giả đã đề xuất 
một số thuật toán chữ ký xây dựng trên đồng thời hai bài toán phân tích số và 
logarit rời rạc. Trong bài báo này, cũng với mục đích nâng cao độ an toàn cho các 
thuật toán chữ ký số, nhóm tác giả tiếp tục phát triển phương pháp đề xuất trong 
[1,2] trên cơ sở tính khó của việc giải một bài toán khó mới, ở đây được gọi là bài 
toán logarit rời rạc kết hợp khai căn trên Zp. Đây là một dạng bài toán khó lần đầu 
được đề xuất và ứng dụng cho việc xây dựng thuật toán chữ ký số và có nhiều triển 
vọng tạo ra các thuật toán có độ an toàn cao cho các ứng dụng thực tế. 
2. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN BÀI TOÁN LOGARIT 
RỜI RẠC KẾT HỢP KHAI CĂN TRÊN Zp 
2.1. Một số bài toán khó ứng dụng trong mật mã và bài toán logarit rời rạc 
kết hợp khai căn trên Zp 
2.1.1. Bài toán logarit rời rạc trên Zp 
Bài toán logarit rời rạc trên Zp là cơ sở xây dựng hệ mật khóa công khai 
ElGamal [11]. Bài toán có thể được phát biểu như sau: Cho p là số nguyên tố, g là 
phần tử sinh của nhóm Zp
*. Với mỗi số nguyên dương y Zp
*, hãy tìm x thỏa mãn 
phương trình: 
ypg x mod 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 175
Giải thuật cho bài toán DLP có thể được viết như một thuật toán tính hàm 
DLP(.) với biến đầu vào là y còn giá trị hàm là nghiệm x của phương trình: 
)(yDLPx 
Ở hệ mật ElGamal, bài toán logarit rời rạc được sử dụng với vai trò hàm một chiều 
trong việc hình thành khóa của các thực thể trong cùng hệ thống với bộ tham số 
{p,g} dùng chung. 
2.1.2. Bài toán khai căn trên Zp 
Bài toán khai căn (FRP) trên Zp có thể được phát biểu như sau: Cho p là số 
nguyên tố, với mỗi số nguyên dương y Zp
*, hãy tìm x thỏa mãn phương trình: 
 ypx k mod 
Trong [12], tác giả N.A. Moldovyan đã chứng minh bài toán khai căn trên là 
khó nếu thỏa mãn: 
1. SkNp 
Ở đây: N là một số nguyên chẵn, k là một số nguyên tố và S ≥ 2. Ngoài ra, p và 
k còn phải có kích thước thỏa mãn: |p| ≥ 1024 bit và: |k| ≥ 160 bit. 
2.1.3. Bài toán logarit rời rạc kết hợp khai căn trên trường Zp 
Bài toán logarit rời rạc kết hợp khai căn trên trường Zp (Bài toán DLRP) được đề 
xuất ở đây có thể phát biểu như sau: 
Bài toán DLRP: Với mỗi số nguyên dương *
pZy , hãy tìm các số x1 và x2 
thỏa mãn phương trình sau: 
 ypx x mod21 
Trường hợp x1 là hằng số thì DLRP trở thành DLP, còn nếu x2 là 1 số nguyên 
tố (hằng số) và thỏa mãn điều kiện theo [12]: 12 
S
xNp , với: N là một số 
nguyên chẵn và S ≥ 2, thì DLRP sẽ trở thành FRP. Dễ thấy rằng, việc giải được 
DLRP là khó hơn cả DLP và FRP. Ngay cả khi có các giải thuật thời gian đa thức 
cho DLP và FRP thì cũng không có nghĩa là sẽ giải được DLRP. 
2.2. Xây dựng lược đồ chữ ký dựa trên tính khó của bài toán DLRP 
2.2.1. Thuật toán sinh khóa 
Ở phương pháp xây dựng thuật toán chữ ký mới đề xuất, DLRP được sử dụng 
để hình thành cặp khóa bí mật và công khai của đối tượng ký. Trong đó, p là tham 
số hệ thống (tham số miền) do nhà cung cấp dịch vụ tạo ra, ở đây p là số nguyên tố 
cần phải được chọn sao cho việc giải bài toán DLP là khó. Cặp (x1, x2) là khóa bí 
mật và y là khóa công khai tương ứng của mỗi đối tượng ký trong hệ thống. Để tạo 
khóa x1 mỗi thực thể ký cần tạo trước số nguyên tố q thỏa mãn: q|(p – 1) và một số 
*
pZ . Khóa x1 được tạo theo: 
px q
p
mod
1
1
Công nghệ thông tin 
N. Đ. Thụy, L. H. Dũng, “Xây dựng lược đồ chữ ký số  bài toán khó mới.” 176 
Khóa x2 là một giá trị được chọn ngẫu nhiên trong khoảng (1, q). Sau đó, các 
khóa công khai được tạo ra từ (x1, x2) theo: 
 pxy x mod211 , pxy
x
mod122 (1) 
Chú ý rằng tham số q cũng sẽ được sử dụng với vai trò của một khóa bí mật 
tương tự như x1 và x2 trong thuật toán ký. 
Thuật toán sinh khóa có thể được mô tả lại như trên Bảng 1 sau đây: 
Bảng 1. Thuật toán sinh khóa. 
Input: p – số nguyên tố, lq – độ dài (tính theo bit) của số nguyên tố q. 
Output: q, x1, x2, y1, y2. 
[1]. generate q: len(q) = lq, q|(p-1) 
[2]. select α: p 1 
[3]. px qp mod/11
  
[4]. if (x1 = 1) then goto [2] 
[5]. select x2: qx 21 
[6]. pxy x mod211  , pxy
x
mod122  
[7]. return {q, x1, x2, y1, y2 } 
Chú thích: 
- len(.) là hàm tính độ dài (theo bit) của một số nguyên. 
- q, x1, x2: Khóa bí mật. 
- y1, y2: Khóa công khai của đối tượng ký (U). 
2.2.2. Thuật toán ký 
Giả sử (r,s) là chữ k ý lên bản tin M, u là 1 giá trị trong khoảng (1,q) và r được 
tính từ u theo công thức: 
 pxr u mod1 (2) 
Và s được tính từ v theo công thức: 
 pxs v mod1 (3) 
Ở đây: v cũng là 1 giá trị trong khoảng (1,q). 
Cũng giả thiết rằng phương trình kiểm tra của lược đồ có dạng: 
 pyrs Epsry mod1
mod.2  
Với: )(MHE và: pxpsr k modmod 1 (4) 
Trong đó: H(.) là hàm băm và k là một giá trị được chọn ngẫu nhiên trong 
khoảng (1,q). 
Đặt: 
 Zpx k mod1 (5) 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 177
Khi đó có thể đưa phương trình kiểm tra về dạng: 
 pyrs EZy mod12  (6) 
Từ (1), (2), (3) và (6) ta có: 
 pxxx ExZuyv mod.1
.
1
.
1
22  (7) 
Từ (7) suy ra: 
 qExZuyv mod22  
hay: qExZuyv mod2
1
2 
 (8) 
Mặt khác, từ (2), (3) và (4) ta có: 
 kquv mod (9) 
Từ (8) và (9) ta có: 
 kquyExZu mod122 
Hay: 
 kqyExyZu mod1 12212 (10) 
Từ (10), suy ra: 
 qyExkyZu mod1 122
11
2
 (11) 
Từ (11), có thể tính thành phần thứ nhất của chữ ký theo (2): 
 pxr u mod1 
và thành phần thứ 2 được tính theo (3): 
 pxs v mod1 
với v được tính theo (8): 
 qExZuyv mod2
1
2 
Từ đây thuật toán ký được mô tả trên Bảng 2 như sau: 
Bảng 2. Thuật toán k ý. 
Input: p, q, x1, x2, y2,M . 
Output: (r,s). 
[1]. )(MHE  
[2]. select k: 11 pk 
[3]. pxZ k mod1 
[4]. qyExkyZu mod1 122
11
2
  
[5]. qExZuyv mod2
1
2 
[6]. pxr u mod1 
[7]. pxs v mod1 
[8]. return (r,s) 
Công nghệ thông tin 
N. Đ. Thụy, L. H. Dũng, “Xây dựng lược đồ chữ ký số  bài toán khó mới.” 178 
Chú thích: 
- M: bản tin cần ký, với: }1,0{M . 
- (r,s): chữ ký của U lên M. 
2.2.3. Thuật toán kiểm tra 
Thuật toán kiểm tra của lược đồ được mô tả trong Bảng 3 như sau: 
 Bảng 3. Thuật toán kiểm tra. 
Input: p, y1, y2, M, (r,s). 
Output: true / false . 
[1]. )(MHE  
[2]. psrZ mod  (12) 
[3]. pyrw EZ mod11  (13) 
[4]. psw y mod22  
 if (
21 ww ) then {return true } 
 else {return false } 
Chú thích: 
 - M, (r,s): bản tin, chữ ký cần thẩm tra. 
 - Nếu kết quả trả về là true thì tính toàn vẹn và nguồn gốc của M được khẳng 
định. Ngược lại, nếu kết quả là false thì M bị phủ nhận về nguồn gốc và tính toàn 
vẹn. 
2.2.4. Tính đúng đắn của lược đồ mới đề xuất 
Điều cần chứng minh ở đây là: Cho p, q là 2 số nguyên tố với q|(p-1), 
  nZH 
1,0: , pnq , p 1 , px qp mod/11
 , qxk 2,1 , 
 pxy x mod211 , pxy
x
mod122 , MHE , pxZ
k
mod1 , 
 qyExkyZu mod1 122
11
2
 , qExZuyv mod2
1
2 
 , 
 pxr u mod1 , pxs
v
mod1 . Nếu: psrZ mod , pyrw
EZ
mod11 , 
 psw y mod22 thì: 21 ww . 
Tính đúng đắn của thuật toán mới đề xuất được chứng minh như sau: 
Thật vậy ta có: 
 px
pxpxpsw
ExZyExkyZ
yyExZuyvy
mod
modmodmod
.....1.
1
....
1
.
12
2
1
22
11
2
2
1
2222
 (14) 
Mặt khác từ (12) ta lại có: 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 179
 Zpxpx
px
px
px
pxpxxpsrZ
kyExyExk
yExyZyExkyZ
yExZyyExkyZyExkyZ
ExZyExkyZyyExkyZ
vuvu
modmod
mod
mod
mod
modmodmod
1
....
1
..1.....1.
1
.......1....1.
1
.....1.....1.
1
111
1
22
1
22
1
22
1
2
1
22
11
2
1
22
1
2
1
22
11
2
1
22
11
2
2
1
22
11
2
1
2
1
22
11
2
 (15) 
Thay (15) vào (13) ta lại có: 
 px
pxx
pxxpyrw
ExZyExkyZ
ExZyxkyZ
ExZuEZ
mod
mod
modmod
.....1.
1
.
1
...1.
1
.
1
.
111
2
1
22
11
2
2
1
22
11
2
2
 (16) 
Từ (14) và (16) suy ra điều cần chứng minh: 
21 ww 
2.2.5. Mức độ an toàn của thuật toán được đề xuất 
Mức độ an toàn của lược đồ mới đề xuất có thể đánh giá qua khả năng như: 
+ Chống tấn công làm lộ khóa bí mật 
Ở thuật toán mới đề xuất, cặp tham số x1, x2 cùng được sử dụng làm khóa bí 
mật để hình thành chữ k ý. Vì thế, thuật toán chỉ bị phá vỡ nếu cả 2 tham số này 
cùng bị lộ, nói cách khác là kẻ tấn công phải giải được bài toán logarit rời rạc kết 
hợp khai căn trên Zp. Do đó, mức độ an toàn của thuật toán mới đề xuất xét theo 
khả năng chống tấn công làm lộ khóa mật được đánh giá bằng mức độ khó của 
việc giải được DLRP. Cần chú ý, DLRP là một dạng bài toán khó mới, mà ngay cả 
khi có các giải thuật thời gian đa thức cho FRP và DLP cũng không có nghĩa là sẽ 
giải được bài toán này. Ngoài ra, tham số q cũng được sử dụng với vai trò khóa bí 
mật trong thuật toán ký. Như vậy, để phá vỡ tính an toàn của thuật toán, kẻ tấn 
công còn phải giải được bài toán tìm bậc của x1. Tuy nhiên, việc tìm bậc của x1 là 
không thể thực hiện được, vì x1 ở đây là 1 tham số bí mật. 
+ Chống giả mạo chữ ký 
Từ thuật toán kiểm tra (Bảng 2) của thuật toán mới đề xuất cho thấy, một cặp 
(r,s) giả mạo sẽ được công nhận là chữ ký hợp lệ với một bản tin M nếu thỏa mãn 
điều kiện: 
 pyrs Epsry mod1
mod).(2  (17) 
Từ (17), nếu chọn trước r rồi tính s thì khi đó điều kiện (17) sẽ có dạng: 
 pas prsy modmod.2  (18) 
Còn nếu chọn trước s rồi tính r thì khi đó điều kiện (17) sẽ trở thành: 
 prb psr modmod. (19) 
Với a, b là hằng số, dễ thấy rằng việc giải (18) và (19) là khó tương đương với 
bài toán DLRP. 
Công nghệ thông tin 
N. Đ. Thụy, L. H. Dũng, “Xây dựng lược đồ chữ ký số  bài toán khó mới.” 180 
4. KẾT LUẬN 
Bài báo đề xuất một lược đồ chữ k ý số mới dựa trên bài toán logarit rời rạc kết 
hợp khai căn trên Zp. Mức độ an toàn của các thuật toán xây dựng theo phương 
pháp này sẽ được đảm bảo bằng mức độ khó của việc giải bài toán trên. Ở đây, bài 
toán logarit rời rạc kết hợp khai căn trên trường Zp là một dạng bài toán khó mới, 
lần đầu được đề xuất và ứng dụng trong việc xây dựng thuật toán chữ ký số. Từ 
phương pháp mới đề xuất có thể xây dựng một lớp thuật toán chữ ký số có độ an 
toàn cao cho các ứng dụng trong thực tế. 
TÀI LIỆU THAM KHẢO 
[1]. Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Văn Phúc và Đỗ Anh Tuấn, 
“Một phương pháp xây dựng thuật toán chữ ký số”, Hội thảo lần thứ I: Một số 
vấn đề chọn lọc về an toàn, an ninh thông tin (SoIS 2016), 11/2016. 
[2]. Nguyen Duc Thuy and Luu Hong Dung, “A New Construction Method of 
Digital Signature Algorithms”, IJCSNS International Journal of Computer 
Science and Network Security. Vol. 16 No. 12 pp. 53-57, December 2016. 
ISSN: 1738 - 7906. 
[3]. Q. X. WU, Y. X. Yang and Z. M. HU, "New signature schemes based on 
discrete logarithms and factoring", Journal of Beijing University of Posts and 
Telecommunications, vol. 24, pp. 61-65, January 2001. 
[4]. Z. Y. Shen and X. Y. Yu, "Digital signature scheme based on discrete logarithms 
and factoring", Information Technology, vol. 28,pp. 21-22, June 2004. 
[5]. Shimin Wei, “Digital Signature Scheme Based on Two Hard Problems”, 
IJCSNS International Journal of Computer Science and Network Security, 
VOL.7 No.12, December 2007. 
[6]. Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A New Digital 
Signature Scheme Based on Factoring and Discrete Logarithms”, Journal of 
Mathematics and Statistics, 04/2008; 12(3). DOI: 
10.3844/jmssp.2008.222.225 Source:DOAJ. 
[7]. Qin Yanlin , Wu Xiaoping,“ New Digital Signature Scheme Based on both 
ECDLP and IFP”, Computer Science and Information Technology, 2009. 
ICCSIT 2009. 2nd IEEE International Conference on, 8-11 Aug. 2009, E-
ISBN : 978-1-4244-4520-2, pp 348 - 351. 
[8]. Swati Verma1, Birendra Kumar Sharma, “A New Digital Signature Scheme 
Based on Two Hard Problems”, International Journal of Pure and Applied 
Sciences and Technology, ISSN 2229 – 6107, Int. J. Pure Appl. Sci. Technol., 
5(2) (2011), pp. 55-59. 
[9]. Sushila Vishnoi , Vishal Shrivastava, ”A new Digital Signature Algorithm 
based on Factorization and Discrete Logarithm problem”, International 
Journal of Computer Trends and Technology, volume 3, Issue 4, 2012. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 181
[10]. A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, "Cryptoschemes Based 
on Difficulty of Simultaneous Solving Two Different Difficult Problems", 
Computer Science Journal of Moldova, vol.21, no.2(62), 2013. 
[11]. T. ElGamal, “A public key cryptosystem and a signature scheme based on 
discrete logarithms”, IEEE Transactions on Information Theory, Vol. IT-31, 
No. 4. pp.469–472. 
[12]. N.A. Moldovyan, "Digital Signature Scheme Based on a New Hard Problem", 
Computer Science Journal of Moldova, vol.16, no.2(47), 2008. 
ABSTRACT 
A NEW DIGITAL SIGNATURE SCHEMA 
BASED ON NEW HARD PROBLEMS 
 This paper proposes a signature schema based on the difficulty of the 
new hard problem. The new signature scheme proposed has higher safety 
level compared to the schemas which have been published previously about 
the ability of keeping secret the source of the signed messages. 
Keywords: Digital signature; Digital signature algorithm; Digital Signature Schema; Discrete logarithm problem. 
Nhận bài ngày 12 tháng 6 năm 2018 
Hoàn thiện ngày 15 tháng 10 năm 2018 
Chấp nhận đăng ngày 05 tháng 11 năm 2018 
Địa chỉ: 1 Khoa CNTT, Cao đẳng Kinh tế - Kỹ thuật TP. Hồ Chí Minh; 
 2 Khoa CNTT, Học viện KTQS. 
 *Email: luuhongdung@gmail.com.