Phương pháp xây dựng thuật toán chữ ký số dựa trên một dạng bài toán khó mới

Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
1 
Phương pháp xây dựng thuật toán chữ ký số dựa trên một dạng 
bài toán khó mới 
A construction method of digital signature algorithms based on a new hard 
problem 
Lưu Hồng Dũng 
Khoa CNTT 
Học Viện KTQS 
Hà Nội, Việt Nam 
e-mail: luuhongdung@gmail.com 
Nguyễn Đức Thụy 
Khoa CNTT 
CĐ Kinh tế - Kỹ thuật 
Tp.HCM, Việt Nam 
e-mail: thuyphulam2013@gmail.com 
Abstract— 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ế. 
Keywords: Digital signature; Digital signature 
algorithm; Digital Signature Schema; Discrete 
logarithm problem. 
I. ĐẶ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ế. 
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
2 
II. BÀI TOÁN KHÓ MỚI VÀ PHƯƠNG PHÁP 
XÂY DỰNG THUẬT TOÁN CHỮ KÝ SỐ 
A. 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 
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 
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) 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. 
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 +×= SxNp , 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. 
B. Xây dựng lược đồ chữ ký dựa trên tính khó của 
bài toán DLRP 
1) Phương pháp xây dựng 
Ở 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
−
= α 
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
3 
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.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ý. 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= (1.2) 
Và s được tính từ v theo công thức: 
 ( ) pxs v mod1= (1.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 yysrfMfyysrfMfyysrfMf mod213212211 ,,,,1
,,,,,,,, ×≡ 
Với ),( sr ... heo 
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 ← 
 (2.1) 
[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ý. 
Bảng 1.2. Thuật toán ký 
Input: p, q, x1, x2, y1, y2, M. 
Output: (r,s). 
[1]. select k: qk <<1 
[2]. ( ) pxZ k mod1← 
[3]. ),,,( 2111 yyZMfw ← 
[4]. ),,,( 2122 yyZMfw ← 
[5]. ),,,( 2133 yyZMfw ← 
[6]. ( ) qwww mod2114 ×← − 
[7]. ( ) qwww mod3115 ×← − 
[8]. ( ) ( ) qwxkwu mod1 5214 ×−×+← − 
[9]. ( ) qwxwuv mod524 ×+×← 
[10]. ( ) pxr u mod1← 
[11]. ( ) pxs v mod1← 
[12]. return (r,s) 
Chú thích: 
(i) M: bản tin cần ký, với: ∞∈ }1,0{M . 
(ii) (r,s): chữ ký của U lên M. 
 Bảng 1.3. Thuật toán kiểm tra chữ ký 
Input: p, y1, y2, M, (r,s). 
Output: true / false . 
[1]. ),( srfZ ← 
[2]. ),,,( 2111 yyZMfw ← 
[3]. ),,,( 2122 yyZMfw ← 
[4]. ),,,( 2133 yyZMfw ← 
[5]. ( ) psA w mod1← 
[6]. ( ) ( ) pyrB ww mod32 1×← 
[7]. if ( BA = ) 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) Một số thuật toán chữ ký xây dựng theo 
phương pháp mới đề xuất 
a) Thuật toán MTA 18.9 –01 
Thuật toán chữ ký thứ nhất đề xuất ở đây – ký 
hiệu: MTA 18.9 – 01, được xây dựng theo các 
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
5 
Bảng 1.1, 1.2 và 1.3 ở mục A với lựa chọn các hàm 
như sau: 
)(),,,( 211 MHyyZMf = , 2212 ),,,( yyyZMf = , 
ZyyZMf =),,,( 213 . 
Khi đó, các thuật toán ký và kiểm tra chữ ký 
của thuật toán được mô tả trong các Bảng 2.1 và 
Bảng 2.2 dưới đây: 
Bảng 2.1. 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← (2.2) 
[4]. ( ) ( ) qEZxkEyu mod1 12112 −−− ××−×+×← (2.3) 
[5]. ( ) qZxyuEv mod221 ×+××← − (2.4) 
[6]. ( ) pxr u mod1← (2.5) 
[7]. ( ) pxs v mod1← (2.6) 
[8]. return (r,s) 
Bảng 2.2. Thuật toán kiểm tra 
Input: p, y1, y2, M, (r,s). 
Output: true / false . 
[1]. )(MHE ← 
[2]. ( ) psA E mod← 
[3]. psrZ mod×← (2.7) 
[4]. ( ) ( ) pyrB Zy mod12 ×← (2.8) 
[5]. if ( BA = ) then {return true } 
 else {return false } 
+ Tính đúng đắn của thuật toán được đề 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 a∗1,0: , pnq << , 
p<< α1 , ( ) px qp mod/11 −= α , qxk << 2,1 , 
( ) pxy x mod211 = , ( ) pxy x mod122 = , ( )MHE = , 
( ) pxZ k mod1= , 
( ) ( ) qEZxkEyu mod1 12112 −−− ××−×+×= , 
( ) qZxyuEv mod221 ×+××= − , ( ) pxr u mod1= , 
( ) pxs v mod1= . Nếu: psrZ mod×= , ( ) psA E mod= , 
( ) ( ) pyrB Zy mod12 ×= thì: BA = . 
Tính đúng đắn của thuật toán mới đề xuất 
được chứng minh như sau: 
Từ (2.2), (2.3), (2.4) và (2.6) ta có: 
( ) ( )
( )( ) ( )
( ) px
px
pxpsA
Zxyu
EEZxyu
EvE
mod
mod
modmod
..
1
....
1
.
1
22
1
22
+
+
=
=
===
−
 (2.9) 
Với: 
 ( ) ( ) qEZxkEyu mod1 12112 −−− ××−×+×= 
Từ (2.3), (2.4), (2.5) và (2.6) ta có: 
( ) ( )
( )
( )( ) ( ) ( ) ( )
( )( ) ( )
( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( )
( ) Zpx
pxxx
pxx
xpx
xx
xx
px
x
pxx
px
pxxpsrZ
k
ZxEEZxk
ZxEEyEyEZx
EyEykZxE
yEZxEyEykEyE
EyEZxEyk
ZxyEZxkEyE
EZxkEy
ZxyuEEZxkEy
vu
vu
==
××=
××
=×
××
×=
×
×=
×=
=
×=×=
−−
−−
−
−−
−
−
−−
−
−
−−
−
−−
−
−−
−
−
−
−
−−
−
−
−
−−
−
−
−
++−
++
+−+
+−+





 +−+
−+
+−+
+
mod
mod
mod
mod
mod
mod
mod
modmod
1
..
1
..
11
..
1
1..1....
1
1..1..
1
..
1
....1..
1
..1..
1
1....
1
1..
1
.....1..
1
...1..
1
...
1
...1.
1
1
11
2
11
2
2
11
2
11
2
1
2
1
2
11
22
1
2
1
2
11
2
1
2
11
2
1
11
2
1
2
11
2
22
1
2
11
2
1
1
2
11
2
22
11
2
11
2
 (2.10) 
Thay (2.1), (2.3), (2.5), (2.7) và (2.10) vào (2.8) 
ta lại có: 
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
6 
( ) ( )
( ) ( )
( ) px
pxx
pyrw
Zxyu
Zxyu
Zy
mod
mod
mod
..
1
.
1
.
1
11
22
22
2
+
=
×=
=×=
 (2.11) 
Với: 
 ( ) ( ) qEZxkEyu mod1 12112 −−− ××−×+×= 
Từ (2.9) và (2.11) suy ra điều cần chứng minh: 
 BA = 
+ 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 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.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 psryE modmod).(12 ×≡ (2.12) 
Từ (2.12), nếu chọn trước r rồi tính s thì khi đó 
điều kiện (2.12) sẽ có dạng: 
 ( ) ( ) pas prsE modmod.≡ (2.13) 
Còn nếu chọn trước s rồi tính r thì khi đó điều 
kiện (2.12) sẽ trở thành: 
 ( ) ( )( ) pbr psry modmod.2 ≡ (2.14) 
Với a, b là hằng số, dễ thấy rằng việc giải 
(2.13) và (2.14) là khó tương đương với DLRP. 
b) Thuật toán MTA 18.9 – 02 
Thuật toán chữ ký thứ hai đề xuất ở đây – ký 
hiệu: MTA 18.9 – 02, cũng được xây dựng theo 
phương pháp tương tự MTA 18.9 – 01 với một số 
thay đổi như sau: 
Các giá trị: x1, x2, y2 được sử dụng làm khóa bí 
mật của đối tượng ký, khóa công khai được tính 
theo: 
 ( ) pyy y mod21= (3.1) 
Và đẳng thức kiểm tra được giả thiết là: 
 ( ) ( ) ( ) pyrs ZyE mod×≡ 
Khi đó, các thuật toán ký và kiểm tra chữ ký 
của thuật toán được mô tả trong các Bảng 3.1 và 
Bảng 3.2 dưới đây: 
Bảng 3.1. Thuật toán k ý 
Input: p, q, x1, x2, y2, y, M . 
Output: (r,s). 
[1]. )(MHE ← 
[2]. select k: 11 −<< pk 
[3]. ( ) pxZ k mod1← (3.2) 
[4]. ( ) ( ) qEZyxkEyu mod1 12211 −−− ×××−×+×← 
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
7 
 (3.3) 
[5]. ( ) qZyxyuEv mod221 ××+××← − (3.4) 
[6]. ( ) pxr u mod1← (3.5) 
[7]. ( ) pxs v mod1← (3.6) 
[8]. return (r,s) 
Bảng 3.2. Thuật toán kiểm tra 
Input: p, y, M, (r,s). 
Output: true / false . 
[1]. )(MHE ← 
[2]. ( ) psA E mod← 
[3]. psrZ mod×← (3.7) 
[4]. ( ) ( ) pyrB Zy mod×← (3.8) 
[5]. if ( BA = ) then {return true } 
 else {return false } 
Nhận xét: 
Từ việc xây dựng các thuật toán MTA 18.9 – 01 
và MTA 18.9 – 02 cho thấy phương pháp mới đề xuất 
ở đây có thể tạo ra các thuật toán chữ ký với nhiều 
khóa bí mật và 1 hoặc 2 khóa công khai là hoàn toàn 
tùy thuộc vào ý định thiết kế. 
+ Tính đúng đắn của thuật toán được đề 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 a∗1,0: , pnq << , 
p<< α1 , ( ) px qp mod/11 −= α , qxk << 2,1 , 
( ) pxy x mod211 = , ( ) pxy x mod122 = , ( ) pyy y mod21= , 
( )MHE = , ( ) pxZ k mod1= , 
( ) ( ) qEZyxkEyu mod1 12211 −−− ×××−×+×= , 
( ) qZyxyuEv mod221 ××+××= − , ( ) pxr u mod1= , 
( ) pxs v mod1= . Nếu: psrZ mod×= , ( ) psA E mod= , 
( ) ( ) pyrB Zy mod×= thì: BA = . 
Tính đúng đắn của thuật toán mới đề xuất 
được chứng minh như sau: 
Từ (3.2), (3.3), (3.4) và (3.6) ta có: 
( ) ( )
( )( ) ( )
( ) px
px
pxpsA
Zyxyu
EEZyxyu
EvE
mod
mod
modmod
...
1
.....
1
.
1
22
1
22
+
+
=
=
===
−
 (3.9) 
Với: 
 ( ) ( ) qEZyxkEyu mod1 12211 −−− ×××−×+×= 
Từ (3.3), (3.4), (3.5) và (3.6) ta có: 
( ) ( )
( )
( )( ) ( )
( ) ( )
( )( ) ( )
( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( )
( ) Zpx
pxxx
pxx
xpx
xx
xx
px
x
px
x
px
pxxpsrZ
k
ZyxEEZyxk
ZyxEEyEyEZyx
EyEykZyxE
yEZyxEyEykEyE
EyEZyxEyk
ZyxyEZyxkEyE
EZyxkEy
ZyxyuE
EZyxkEy
vu
vu
==
××=
××
=×
××
×=
×
×=
×
×=
=
×=×=
−−
−−
−
−−
−
−
−−
−
−
−−
−
−−
−
−−
−
−
−
−
−−
−
−
−
−
−
−
−
−
++−
++
+−+
+−+





 +−+
−+
+
−+
+
mod
mod
mod
mod
mod
mod
mod
modmod
1
...
1
...
11
...
1
1..1.....
1
1..1..
1
...
1
.....1..
1
..1..
1
1.....
1
1..
1
.......1..
1
....1..
1
....
1
....1.
1
1
11
22
11
22
22
11111
22
111
22
1
1
22
111111
111
22
11
22
1
22
111
1
22
11
22
1
1
22
11
(3.10) 
Thay (3.1), (3.3), (3.5), (3.7) và (3.10) vào (3.8) 
ta lại có: 
( ) ( )
( ) ( )
( ) px
pxx
pyrw
Zyxyu
Zyxyu
Zy
mod
mod
mod
...
1
..
1
.
1
1
22
22
+
=
×=
=×=
 (3.11) 
Với: 
 ( ) ( ) qEZyxkEyu mod1 12211 −−− ×××−×+×= 
Từ (3.9) và (3.11) suy ra điều cần chứng minh: 
 BA = 
+ 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ể 
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
8 
đánh giá qua khả năng như: 
- Chống tấn công khóa bí mật 
Tương tự MTA 18.9 – 01, 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ũng được đánh giá bằng mức 
độ khó của việc giải được bài toán DLRP. 
- Chống giả mạo chữ ký 
Từ thuật toán kiểm tra (Bảng 3.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 psryE modmod).(×≡ (3.12) 
Từ (3.12), nếu chọn trước r rồi tính s thì khi đó 
điều kiện (3.12) sẽ có dạng: 
 ( ) ( ) pas prsE modmod.≡ (3.13) 
Còn nếu chọn trước s rồi tính r thì khi đó điều 
kiện (3.12) sẽ trở thành: 
 ( ) ( )( ) pbr psry modmod.≡ (3.14) 
Với a, b là hằng số, cũng dễ thấy rằng việc giải 
(3.13) và (3.14) là khó tương đương với bài toán 
DLRP. 
III. KẾT LUẬN 
Bài báo đề xuất một phương pháp xây dựng thuật 
toán 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. 
[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. 
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 
9