Xây dựng lược đồ chữ ký số dựa trên tính khó của việc giải hệ phương trình phi tuyến trên Zp

Công nghệ thông tin 
L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số  phi tuyến trên Zp.” 104 
XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN TÍNH KHÓ CỦA 
VIỆC GIẢI HỆ PHƯƠNG TRÌNH PHI TUYẾN TRÊN Zp 
Lưu Xuân Văn1*, Đoàn Văn Hòa2, Lưu Hồng Dũng3 
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 việc giải một hệ phương trình phi tuyến trên Zp. Đây là một dạng 
bài toán khó mới chưa có phương pháp giả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: Chữ ký số; Thuật toán ký số; Lược đồ ký số; Logarith rời rạc. 
1. ĐẶT VẤ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 [1 – 11] 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 [12] trên cơ sở tính khó 
của việc giải một hệ phương trình phi tuyế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 TÍNH KHÓ GIẢI 
CỦA HỆ PHƯƠNG TRÌNH PHI TUYẾN TRÊN Zp 
2.1. Giải hệ phương trình phi tuyến trên Zp - Một dạng bài toán khó mới 
Bài toán giải hệ phương trình phi tuyến trên trường Zp được đề xuất ở đây là 
một dạng bài toán khó mới, bài toán này có thể phát biểu như sau: 
Với mỗi cặp số nguyên dương *21, pZyy , hãy tìm các số 1x và 2x thỏa mãn 
hệ phương trình sau: 
2
.
2
1
.
1
mod
mod
21
21
ypx
ypx
xx
xx
Về mặt hình thức, nếu 1x là hằng số còn 2x là biến cần tìm thì bài toán trên sẽ 
trở thành bài toán logarit rời rạc trên Zp - DLP (Discrete Logarithm Problem). Tuy 
nhiên, ở đây 1x cũng là ẩn số như 2x , vì thế các giải thuật cho DLP không thể áp 
dụng với bài toán này. Tương tự, nếu 2x là hằng số và 1x là biến thì bài toán trên 
lại trở thành bài toán khai căn trên Zp - RP (Root Problem) [12]. Song ở đây 2x 
cũng là biến cần tìm, do vậy các giải thuật cho RP cũng không áp dụng được đối 
với bài toán mới đề xuất. Trong toán học, bài toán trên thực chất là một hệ phương 
trình phi tuyến và thuộc lớp các bài toán chưa có cách giải, các giải thuật cho DLP 
và RP hiện tại là không áp dụng được với bài toán này. Điều đó cho thấy bài toán 
mới đề xuất ở đây có mức độ khó cao hơn DLP và RP. 
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, 04 - 2019 105
2.2. Xây dựng lược đồ chữ ký dựa trên tính khó của bài toán mới đề xuất 
2.2.1. Thuật toán sinh khóa 
Ở lược đồ chữ ký mới đề xuất, bài toán trên đượ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 logarit rời rạc là khó. Cặp ( 1x , 2x ) là khóa bí mật 
và ( 1y , 2y ) là các khóa công khai tương ứng của mỗi đối tượng ký trong hệ thống. 
Để tạo khóa ( 1x , 2x ) 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 cặp số *( , ) pZ  . Khóa bí mật 1x được tạo theo: px
q
p
mod
1
1
 . 
Khóa bí mật 2x được tạo theo: px
q
p
mod
1
2
  . 
Sau đó, các khóa công khai được tạo ra từ ( 1x , 2x ) theo: 
 pxy xx mod21.11 , pxy
xx
mod21
.
22 (1) 
Chú ý rằng tham số q cũng được sử dụng với vai trò của một khóa bí mật tương 
tự như 1x và 2x trong thuật toán ký. 
Thuật toán sinh khóa có thể được mô tả lại như trên Thuật toán 1 sau đây: 
Thuật toán 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, y. 
[B1] generate q: len(q) = lq, q|(p-1) 
[B2] select (α, ): p  ,1 
[B3] px qp mod/11
  , px qp mod/12
   
[B4] if (( 1x =1) or ( 2x =1)) then goto [B2] 
[B5] pxy xx mod21.11  , pxy
xx
mod21
.
22  
[B6] 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. 
- p: Tham số hệ thống/tham số miề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 và R được tính từ *pu Z theo công thức: 
 puR x mod2 (2) 
và S được tính từ *pv Z theo: 
 pvS x mod2 (3) 
Cũng giả thiết rằng phương trình kiểm tra của lược đồ có dạng: 
Công nghệ thông tin 
L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số  phi tuyến trên Zp.” 106 
 1 2
mod
1 2 mod
y y E R S p
R S y y p
 
với: ( )E H M và: 2xmod ( ) modR S p k p 
(4) 
Trong đó: H(.) là hàm băm và *pZk . 
Đặt: Zpk x mod2 (5) 
Khi đó có thể đưa phương trình kiểm tra về dạng: 
 pyySR ZEyy mod2121  (6) 
Từ (1), (2), (3) và (6) ta có: 
 pxxvu ZxxExxyxyx mod..2
..
1
.. 21212212  (7) 
Từ (7) suy ra: 
 pxxvu ZxExyy mod.2
.
1
1121  
Nên: 
 pxxv
pxxvu
yxZEyy
ZyxEyxyy
mod
mod
1
112
1
1
1
11
1
112
1
1
.
21
.
..
2
..
1
.
 (8) 
Mặt khác, từ (2), (3) và (4) ta có: 
 kpvu mod (9) 
Từ (8) và (9) ta có: 
 kpxxvv yxZEyy 
mod
1
112
1
1
.
21
.
Hay: 
 kpxxv yxZEyy 
mod
1
112
1
1
.
21
1.
 (10) 
Từ (10), suy ra: 
pxxkv
yy
yxZE
mod
1
2
1
11
11
1.
.
21
 (11) 
Từ (11), có thể tính được giá trị u theo (8): 
 pxxvu yxZEyy mod
1
112
1
1
.
21
.
Từ các giá trị u và v có thể tính R của chữ ký theo (2): puR x mod2 
và tính S theo (3): pvS x mod2 
Từ đây thuật toán ký được mô tả trên Thuật toán 2 như sau: 
Thuật toán 2. Thuật toán k ý 
Input: p, q, x1, x2, y1, y2, M. 
Output: (R,S). 
[B1] )(MHE 
[B2] select k: 11 pk 
[B3] pkZ x mod2 
[B4] 
pxxkv
yy
yxZE
mod
1
2
1
11
11
1.
.
21
  
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, 04 - 2019 107
[B5] pxxvu yxZEyy mod
1
112
1
1
.
21
.
  
[B6] puR x mod2 
[B7] pvS x mod2 
[B8] If ((R=1) or (S=1)) then goto [B2] 
[B9] return (R,S) 
Chú thích: 
- M: bản tin cần ký, với: 0,1M
 . 
- H(.): Hàm băm 
*
: 0,1 nH Z , với: pnq 
- (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 giả thiết là: 
 1 2
mod
1 2 mod
y y E R S p
R S y y p
 
Ở đây, E là giá trị đại diện của bản tin cần thẩm tra: )(MHE . Nếu M và chữ 
ký (R,S) thỏa mãn đẳng thức trên thì chữ ký được coi là hợp lệ và bản tin sẽ được 
xác thực về nguồn gốc và tính toàn vẹn. Ngược lại, thì chữ ký bị coi là giả mạo và 
bản tin bị phủ nhận về nguồn gốc và tính toàn vẹn. Do đó, nếu vế trái của đẳng 
thức kiểm tra được tính theo: 
 pRA y mod1 (12) 
và vế phải được tính theo: 
 pyySB ZEy mod212 (13) 
ở đây: 
 pSRZ mod (14) 
Thì điều kiện chữ ký hợp lệ là: A=B. 
Khi đó, thuật toán kiểm tra của lược đồ mới đề xuất được mô tả trong Thuật 
toán 3 như sau: 
Thuật toán 3. Thuật toán kiểm tra. 
Input: p, y1, y2, M, (R, S). 
Output: true / false . 
[B1] )(MHE 
[B2] pRA y mod1 
[B3] pSRZ mod  
[B4] pyySB ZEy mod212  
[B5] if ( BA ) then {return true } 
 else {return false} 
Công nghệ thông tin 
L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số  phi tuyến trên Zp.” 108 
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), 
 : 0,1 nH Z
 , q n p , 1 , p  , 1 /
1 mod
p qx p , 1 /2 mod
p qx p , 
 1 2
.
1 1 mod
x x
y x p , 1 2
.
2 2 mod
x x
y x p , 1 k p , 1 mod
k
Z x p , E H M , 
11
1 21
1 1
. 1
.
1 2 mod
y y
x yE Z
v k x x p
, 
 11 1 1
1 2
..
1 2 mod
x yy y E Z
u v x x p
 , 
 2 mod
x
R u p , 2 mod
x
S v p . Nếu: modZ R S p , 1 mod
y
A R p , 
 2 1 2 mod
y E Z
B S y y p thì: A B . 
Tính đúng đắn của thuật toán mới đề xuất được chứng minh như sau: 
Thật vậy, từ (1), (2), (3), (8), (11) và (13) ta có: 
 pyyS
pxxvpxxv
pxxvpupRA
ZEy
ZxxExxyxyxyxZEyxyy
yx
yxZEyyyxy
mod
modmod
modmodmod
21
..
2
..
1
....
21
...
.
.
21
..
2
21212212
1
11122
1
1
121
112
1
1121
 (15) 
Mặt khác từ (2), (3), (8), (11) và (12) ta lại có: 
 Zpkpxxxxk
pxxxxk
pxxxxk
pxxxxk
pvxxvpvupSRZ
xyxxZEyxxZEx
yxxZE
x
yxZE
yxxZE
xyyyy
yxZE
yxxZE
xxyyyy
yxZE
x
x
yxZEyyxx
x
modmod
mod
mod
mod
modmodmod
2
1
121
1
1212
1
121
21
11
1
121
2
1
1
1
2
1
11
11
1
121
222
1
1
1
2
1
11
11
2
21
112
1
122
..
21
..
21
..
21
.
21
..
21
.1..1.
.
21
..
21
...1.
.
21
.
21
.
(16) 
Thay (16) vào (14) ta có: 
 pyySpyySB ZEyZEy modmod 2121 22 (17) 
Từ (15) và (17) suy ra điều cần chứng minh: A=B. 
2.2.5. Ví dụ 
Tính đúng đắn của lược đồ mới đề xuất được minh họa bằng một ví dụ số như 
sau: 
a) Sinh tham số và khóa (Thuật toán 1): 
- Giá trị của p: 
5119598402113263619647413046633333105228285000515677334589179699240770801113128
691621557751719430180712670366353305678543690093876314500926174034029269201 
- Giá trị của q: 
781808462830405458176129153441979513485392456993 
- Giá trị của x1: 
2842490911972753945445545799896416929243929107224821054069717968535655071231625
868946966274549239240045805503435429351793721944283213959121960755096375518 
- Giá trị của x2: 
2150489955287383614222854701556275163987322304198611569590308894844039864014099
718064145199641713717746858366613043851522532672340735468822509573484417688 
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, 04 - 2019 109
- Giá trị của y1: 
4752362188846001432451095168838825977504351218822787215613509267352461456687426
56121480111237216936503278668969026786609936834063244169724270072075518431 
- Giá trị của y2: 
3081638004632919571970082331697065656387874785417547708965887191683350492975303
397728024143445032265545183583948790216795931358943797379106312175468166564 
b) Sinh chữ ký (Thuật toán 2): 
Input: p,y1,y2,x1,x2,M. 
Output: (R,S). 
- Bản tin: M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
- Giá trị của k: 
3619181932015181332921654987246100638190279416171216670649804377304799497072483
779971623141639815886338262489818819792551921945442629354196112649212826547 
- Giá trị của E tính được: 
765446923420569464858869279161340593924873951250 
- Giá trị của R tính được: 
2578978040546995360931057356885224501796548859040273140196191758320843166213664
239378150901806465978336262717423570863122966304174638419711719558730285244 
- Giá trị của S tính được: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
c) Kiểm tra chữ ký (Thuật toán 3): 
Input: p,y1,y2,(R,S),M. 
+ Trường hợp 1: 
- Bản tin: M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
- Giá trị của R: 
2578978040546995360931057356885224501796548859040273140196191758320843166213664
239378150901806465978336262717423570863122966304174638419711719558730285244 
- Giá trị của S: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
- Giá trị của E tính được: 
765446923420569464858869279161340593924873951250 
- Giá trị của Z tính được: 
2365275623359255232876702232858324517036687506731193281049014835102728749249307
140783514760198811210087113971222711956968797566427029467752619495993833742 
- Giá trị của A tính được: 
5009182436092899969432922977146621404462547823386495213041663626091080070784452
500719758764653871289777747917389887273902468251921618658597941797697356682 
- Giá trị của B tính được: 
5009182436092899969432922977146621404462547823386495213041663626091080070784452
500719758764653871289777747917389887273902468251921618658597941797697356682 
Output: (R,S) = true. 
+ Trường hợp 2: Bản tin M bị giả mạo. 
- Bản tin: M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM ” 
- Giá trị của R: 
2578978040546995360931057356885224501796548859040273140196191758320843166213664
239378150901806465978336262717423570863122966304174638419711719558730285244 
- Giá trị của S: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
- Giá trị của E tính được: 
74094010598378196819556769036091466548756606187 
- Giá trị của Z tính được: 
2365275623359255232876702232858324517036687506731193281049014835102728749249307
140783514760198811210087113971222711956968797566427029467752619495993833742 
- Giá trị của A tính được: 
5009182436092899969432922977146621404462547823386495213041663626091080070784452
500719758764653871289777747917389887273902468251921618658597941797697356682 
- Giá trị của B tính được: 
1488359126273936813243632434469538093103616224220548588334028888150119304738618
467211912505689489579585662805761050860949693472937075275922757676168457192 
Output:(R,S) = false. 
+ Trường hợp 3: Thành phần R của chữ ký bị giả mạo. 
- Bản tin: M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
Công nghệ thông tin 
L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số  phi tuyến trên Zp.” 110 
- Giá trị của R: 
2578978040546995360931057356885224501796548859040273140196191758320843166213664
239378150901806465978336262717423570863122966304174638419711719558730285240 
- Giá trị của S: 
2224380751316613878874711758700910418813066109969658023430376378057660278968159
131581470430550228983218202294093687404074195903972620481571752314084294658 
- Giá trị của E tính được: 
765446923420569464858869279161340593924873951250 
- Giá trị của Z tính được: 
3706949422319326956672681291321349052240993067883915856505868721353629235602927
997700748541436755638639645527554573697759394138289176543317958307715193512 
- Giá trị của A tính được: 
2103122925751575293927695945461415162983886316746280267035526289513905507273974
454583000897168494366134213430890824367120283956832755497130820091415965038 
- Giá trị của B tính được: 
1985222396844154533147613443758246007006163638474614219703118890277777325994538
876375304639811775582256510153550569528863364399572239755832733993950686404 
Output:(R,S) = false. 
2.2.6. 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 chống 
một số dạng tấn công như: 
+ 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 hệ phương trình phi tuyế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 hệ 
phương trình nói trên. Cần chú ý, đây 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 RP 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 1x , 2x .Tuy nhiên, việc tìm bậc của 
1x , 2x là không thể thực hiện được, vì 1x , 2x ở đây là đều là các tham số bí mật. 
+ Tấn công giả mạo chữ ký 
Từ thuật toán kiểm tra (Thuật toán 3) 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: 
 1 2
mod
1 2 mod
y y E R S p
R S y y p
 (18) 
Từ (18), nếu chọn trước R rồi tính S thì khi đó điều kiện (18) sẽ có dạng: 
 2
mod
2 mod
y R S p
S a y p
 (19) 
Còn nếu chọn trước S rồi tính R thì khi đó điều kiện (18) sẽ trở thành: 
 1
mod
2 mod
y R S p
R b y p
 (20) 
Với a, b là hằng số, dễ thấy rằng (19) và (20) cũng là một dạng bài toán khó 
chưa có cách giải. 
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, 04 - 2019 111
3. KẾT LUẬN 
Bài báo đề xuất một lược đồ chữ k ý số mới dựa trên tính khó của việc giải một 
hệ phương trình phi tuyến trên Zp. Do đó, 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 hệ 
phương trình trên. Trong toán học, đây là một dạng bài toán chưa có phương pháp 
giải. Vì vậy, phương pháp mới đề xuất ở đây có thể sử dụng để phát triển một lớp 
thuật toán chữ ký số cho các ứng dụng yêu cầu có độ an toàn cao trong thực tế. 
TÀI LIỆU THAM KHẢO 
[1]. 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. 
[2]. 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. 
[3]. 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. 
[4]. 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. 
[5]. 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. 
[6]. 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. 
[7]. 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. 
[8]. 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. 
[9]. N.A. Moldovyan, “Digital Signature Scheme Based on a New Hard 
Problem”, Computer Science Journal of Moldova, vol.16, no.2(47), 2008. 
[10]. Phạm Văn Hiệp, Nguyễn Hữu Mộng, Lưu Hồng Dũng, “Một thuật toán chữ 
ký xây dựng dựa trên tính khó của việc giải đồng thời hai bài toán phân tích 
số và logarit rời rạc”, Tạp chí Khoa học và Công nghệ Đại học Đà Nẵng, số 
7(128). 2018, ISSN: 1859 – 1531. 
[11]. Nguyễn Vĩnh Thái, Lưu Hồng Dũng, “Hệ mật khóa công khai dựa trên tính 
khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số/khai 
Công nghệ thông tin 
L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số  phi tuyến trên Zp.” 112 
căn”, Tạp chí Thông tin và Truyền thông, Bộ Thông tin và Truyền thông, 
ISSN: 1859 – 3550, 12/2018. 
[12]. Lưu Hồng Dũng, Tống Minh Đức, Lưu Xuân Văn, “Phương pháp xây dựng 
lược đồ chữ ký số dựa trên tính khóa của việc giải đồng thời bài toán phân 
tích số và bài toán logarit rời rạc kết hợp khai căn trên Zn”, Hội nghị Quốc 
gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công Nghệ thông tin 
(FAIR), Hà Nội, ngày 09-10/08/2018. 
ABSTRACT 
A NEW DIGITAL SIGNATURE SCHEMA BASED ON THE DIFFICULTY OF 
SOLVING A SYSTEM OF NONLINEAR EQUATIONS ON ZP 
This paper presents the proposed method of building a digital signature 
algorithm which is based on the difficulty of solving a system of nonlinear 
equations on Zp. This is a new form of difficult problem without the solution, 
also originally proposed and applied to build digital signature algorithms. 
From this proposed method, it is possible to build a high-security digital 
signature platform for practical applications. 
Keywords: Digital signature; Digital signature algorithm; Digital signature schema; Discrete logarithm 
problem. 
Nhận bài ngày 10 tháng 11 năm 2018 
Hoàn thiện ngày 18 tháng 3 năm 2019 
Chấp nhận đăng ngày 25 tháng 3 năm 2019 
Địa chỉ: 1 Khoa Công nghệ & an ninh thông tin, Học viện An ninh nhân dân; 
 2 Viện Công nghệ thông tin, Viện Khoa học - Công nghệ quân sự; 
 3 Khoa Công nghệ thông tin, Học viện Kỹ thuật quân sự. 
 * Email: vanlx.hvan@gmail.com.