Phát triển lược đồ chữ ký số trên bài toán logarit rời rạc

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 103
PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN 
BÀI TOÁN LOGARIT RỜI RẠC 
Nguyễn Đức Thụy1*, Hồ Nhật Quang2, Lưu Hồng Dũng2 
Tóm tắt: Bài báo đề xuất phương pháp xây dựng lược đồ chữ ký số dựa trên tính khó giải 
của bài toán logarit rời rạc. Từ dạng lược đồ tổng quát được xây dựng, một số lược đồ chữ 
k ý đã được đề xuất cho các ứng dụng trong thực tế. 
Từ khoá: Digital Signature, Digital Signature Schema, Discrete logarit problem. 
1. MỞ ĐẦU 
Trong các giao dịch điện tử (Chính phủ điện tử, Thương mại điện tử,), chữ ký số được 
sử dụng nhằm đáp ứng yêu cầu chứng thực về nguồn gốc và tính toàn vẹn của thông tin. Hiện 
nay chữ k ý số đã được ứng dụng rộng rãi trong các lĩnh vực Chính phủ điện tử, Thương mại 
điện tử, trên thế giới cũng như đã bước đầu được triển khai ở Việt Nam. Do đó, việc nghiên 
cứu - phát triển các lược đồ chữ k ý số mới cho mục đích thiết kế - chế tạo các sản phẩm, thiết 
bị an toàn và bảo mật thông tin trong nước luôn là vấn đề cần thiết được đặt ra. Bài báo đề xuất 
phương pháp xây dựng lược đồ chữ k ý số dựa trên tính khó của bài toán logarit rời rạc và một 
số lược đồ chữ ký số được phát triển theo phương pháp chung này. 
2. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ DỰA TRÊN 
 BÀI TOÁN LOGARIT RỜI RẠC 
2.1. Bài toán logarit rời rạc 
Cho p là một số nguyên tố và g là phần tử sinh của nhóm ZP*. Khi đó bài toán logarit 
rời rạc - DLP (Discrete Logarithm Problem) trên trường ZP hay còn gọi là bài toán 
),( gpDLP được phát biểu như sau: 
Bài toán DLP(p,g): Với mỗi số nguyên dương y ℤp
*, hãy tìm x thỏa mãn phương trình sau: 
 ypg x mod (1.1) 
Giải thuật cho bài toán logarit rời rạc với các tham số {p, g} công khai có thể được 
viết như một thuật toán tính hàm (.)),( gpDLP 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 (1.1): 
)(),( yDLPx gp 
Trong một hệ thống giao dịch điện tử ứng dụng chứng thực số để xác thực nguồn gốc 
và tính toàn vẹn thông tin cho các thông điệp dữ liệu, bài toán ),( gpDLP là khó theo nghĩa 
không thể thực hiện được trong thời gian thực. Ở đó, mỗi thành viên U của hệ thống tự 
chọn cho mình khóa bí mật x thỏa mãn: )1(1 px , tính và công khai tham số: 
 pgy x mod (1.2) 
Chú ý: 
(i) Bài toán ),( gpDLP là khó theo nghĩa không thể thực hiện được trong thời gian thực, 
tuy nhiên không phải với mọi y ZP* thì việc tính ),( gpDLP đều khó, chẳng hạn những 
pgy x mod với x không đủ lớn thì bằng cách duyệt dần x = 1, 2, ... cho đến khi tìm 
được nghiệm của (1.2) ta sẽ tìm được khóa bí mật x, do đó các giá trị của khóa mật x phải 
được lựa chọn sao cho việc tính )(),( yDLP gp đều khó. 
(ii) Với lựa chọn x như trên thì không có ai ngoài U biết được giá trị x, vì vậy việc biết 
được x đủ để xác thực đó là U. 
Công nghệ thông tin & Khoa học máy tính 
N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký  logarit rời rạc.” 104 
Hiện tại, bài toán trên vẫn được coi là bài toán khó [1,2] do chưa có giải thuật thời 
gian đa thức cho nó và hệ mật ElGamal [3] là một chứng minh thực tế cho tính khó giải 
của bài toán này. 
2.2. Xây dựng lược đồ dạng tổng quát 
Lược đồ dạng tổng quát được sử dụng để phát triển các lược đồ chữ k ý số cho các ứng 
dụng thực tế. Lược đồ dạng tổng quát đề xuất ở đây được xây dựng trên cơ sở tính khó 
giải của bài toán logarit rời rạc và được thiết kế theo dạng lược đồ sinh chữ ký 2 thành 
phần tương tự như DSA trong chuẩn chữ k ý số của Mỹ (DSS) [4] hay GOST R34.10-94 
của Liên bang Nga [5], bao gồm các phương pháp hình thành tham số, phương pháp hình 
thành và kiểm tra chữ ký được chỉ ra dưới đây. 
 Phương pháp hình thành tham số và khóa 
Dữ liệu vào: p, q , x . 
Kết quả: g, y, H(.). 
Các bước thực hiện: 
1. Tính phần tử sinh g của Zp*: phg
qp mod/)1( , với: ph 1 (2.1) 
2. Tính khóa công khai: pgy x mod (2.2) 
3. Chọn hàm băm H: {0,1}* → Zq ; 
Chú thích: 
(i) p, q: 2 số nguyên tố thỏa mãn q|(p-1). 
(ii) x: khóa bí mật của đối tượng ký thỏa mãn: qx 1 . 
 Phương pháp hình thành chữ ký 
Dữ liệu vào: p, q, g, x, M. 
Kết quả: (e,s). 
Các bước thực hiện: 
1. Chọn giá trị k thỏa mãn: qk 1 . Tính giá trị r theo công thức: 
 pgr k mod (2.3) 
2. Thành phần thứ nhất e của chữ k ý được chọn theo một trong hai dạng: 
 qre mod (2.4) 
hoặc: 
 qrMfe mod),(1 (2.5) 
3. Thành phần thứ hai s của chữ k ý được hình thành theo một trong các dạng 
sau: 
 qrMfxrMfks mod)],(.),(.[ 3
1
2 
 (2.6) 
 hoặc: 
 qrMfxrMfks mod)],(.),(.[ 132
 (2.7) 
 Chú thích: 
(i) M: thông điệp dữ liệu cần k ý. 
(ii) (e,s): chữ ký lên M của đối tượng sở hữu {x,y}. 
(iii) ),(),,(),,( 321 rMfrMfrMf : là các hàm của M, r và thỏa mãn điều 
kiện: 
 qrMfrMfrMf ),(),,(),,(1 321 
 Phương pháp kiểm tra chữ ký 
Dữ liệu vào: p, q, g, y, M, (e,s). 
Kết quả: Khẳng định (e,s) là chữ k ý hợp lệ ((e,s) = true) hay (e,s) là giả 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 105
 mạo và/hoặc M không còn toàn vẹn ((e,s) = false). 
Các bước thực hiện: 
1. Tính giá trị u: 
 pygu rMfrMfrMfs mod),().,(),(. 322 (2.8), nếu s được tính theo (2.6) 
 hoặc: 
 pygu rMfsrMfs mod),(.),(. 32 (2.9), nếu s được tính theo (2.7) 
2. Tính giá trị v: 
 quv mod (2.10), nếu e được tính theo (2.4) 
 hoặc: 
 quMfv mod),(1 (2.11), nếu e được tính theo (2.5) 
3. Kiểm tra nếu: v = e (2.12), thì: (e,s) = true, ngược lại: (e,s) = false. 
 Tính đúng đắn của lược đồ dạng tổng quát 
Điều cần chứng minh ở đây là: nếu tham số và khóa được hình thành theo (2.1) và 
(2.2), chữ k ý được hình thành theo các công thức từ (2.3) đến (2.7), còn kiểm tra chữ 
k ý được thực hiện theo (2.8) đến (2.11) thì điều kiện chỉ ra bởi (2.12) sẽ được thỏa 
mãn. 
Bổ đề 1.1: 
Cho p và q là 2 số nguyên tố với q là ước số của (p-1), h là một số nguyên dương 
nhỏ hơn p. Nếu: phg qp mod/1( thì: 1mod pg q . 
Chứng minh: 
Ta có: 
 phpphpg pqqpq modmod)mod(mod )1(/)1( 
Theo định l ý Fermat thì: 
 1mod)1( ph p 
Vì vậy: 
 1mod pg q 
Bổ đề đã được chứng minh. 
Bổ đề 1.2: 
Cho p và q là 2 số nguyên tố với q là ước số của (p -1), h là một số nguyên dương 
nhỏ hơn p và phg qp mod/1( . Nếu: qnqm modmod thì: 
pgpg nm modmod 
Chứng minh: 
Nếu: qnqm modmod thì: m = n + k.q hoặc: n = m + k.q, với k là một số 
nguyên. Không làm mất tính tổng quát, giả sử: m = n + k.q. 
 Do đó: 
ppgpg
ppgpg
pggpgpg
kqn
qkn
qknqknm
mod)mod).(mod(
mod)mod).(mod(
modmodmod
.
..
Theo Bổ đề 1.1 ta có: 
 1mod pg q 
Nên: 
 pgpgpg nknm modmod1.mod 
Công nghệ thông tin & Khoa học máy tính 
N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký  logarit rời rạc.” 106 
Bổ đề đã được chứng minh. 
Mệnh đề 1.1: 
Cho p và q là 2 số nguyên tố với q là ước số của (p-1), h là một số nguyên dương 
nhỏ hơn p và phg qp mod/1( , qkx ,1 . Nếu: pgy x mod , 
pgr k mod , qre mod hoặc: qrMfe mod),(1 , 
qrMfxrMfks mod)],(.),(.[ 3
1
2 
 với: qrMfrMfrMf ),(),,(),,(1 321 , 
pygu rMfrMfrMfs mod),().,(),(. 322 , quv mod hoặc: quMfv mod),(1 thì: 
ev . 
Chứng minh: 
Thật vậy, ta có: 
qrMfrMfxkrMfqrMfxrMfks mod)],().,(..[),(mod)],(.),(.[ 32
1
23
1
2 
 Nên: qrMfrMfxkqrMfs mod)],().,(.[mod),(. 322 
Theo Bổ đề 2.2 ta có: 
 pgpg rMfrMfxkrMfs modmod ),().,(.),(. 322 
Suy ra: pgpgg krMfrMfxrMfs modmod),().,(.),(. 322 
Hay: pgpyg krMfrMfrMfs modmod),().,(),(. 322 (2.13) 
Từ (2.3) và (2.13) ta có: ru 
Do đó: qrquv modmod (2.14) 
hoặc: qrMfquMfv mod),(mod),( 11 (2.15) 
Từ (2.4) và (2.14) hoặc từ (2.5) và (2.15) suy ra: ev 
Đây là điều cần chứng minh. 
Mệnh đề 1.2: 
Cho p và q là 2 số nguyên tố với q là ước số của (p-1), h là một số nguyên dương 
nhỏ hơn p và phg qp mod/1( , qkx ,1 . Nếu: pgy x mod , 
pgr k mod , qre mod hoặc: qrMfe mod),(1 , 
qrMfxrMfks mod)],(.),(.[ 132
 với: qrMfrMfrMf ),(),,(),,(1 321 , 
pygu rMfsrMfs mod),(.),(. 32 , quv mod hoặc: quMfv mod),(1 thì: ev . 
Chứng minh: 
Thật vậy, từ (2.7) ta có: 
 qrMfxrMfsk mod)],(.),(.[ 32 (2.16) 
Theo Bổ đề 2.2 và (2.16) suy ra: 
 pgpgg krMfsxrMfs modmod),(..),(. 32 
hay: pgpyg krMfsrMfs modmod),(.),(. 32 (2.17) 
Từ (2.3) và (2.17) ta có: 
 ru 
Do đó: qrquv modmod (2.18) 
hoặc: qrMfquMfv mod),(mod),( 11 (2.19) 
Từ (2.4) và (2.18) hoặc từ (2.5) và (2.19) suy ra: ev 
Đây là điều cần chứng minh. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 107
2.3 Một số lược đồ chữ ký số phát triển từ lược đồ dạng tổng quát 
2.3.1 Lược đồ thứ nhất LD 1.01 
 Lược đồ LD 1.01 được phát triển từ dạng tổng quát với các lựa chọn: 
qMHrMf mod)(),(2 , qpgrMf
k mod)mod(),(3 , ở đây H(.) là hàm băm và 
H(M) là giá trị đại diện của bản tin được ký M. Khóa công khai được tính theo công 
thức: pgy x mod . Các thuật toán hình thành tham số, hình thành và kiểm tra chữ ký 
được mô tả trong các bảng 1.1 và bảng 1.2 dưới đây: 
a) Thuật toán hình thành chữ k ý 
Bảng 1.1 
Input: p, q, g, x, M. 
Output: (e,s) – chữ ký của U lên M. 
 [1]. select k: qk 1 
 [2]. pgr k mod (3.1) 
 [3]. qre mod (3.2) 
 [4]. qexMHks mod].)(.[ 1  (3.3) 
 [5]. return (e,s) 
Chú ý: 
(i) U: đối tượng k ý sở hữu khóa bí mật x. 
(ii) M: Bản tin được k ý bởi đối tượng U. 
b) Thuật toán kiểm tra chữ k ý 
 Bảng 1.2: 
Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. 
Output: (e,s) = true / false . 
 [1]. pygu MHeMHs mod)(.)(.  (3.4) 
 [2]. quv mod (3.5) 
 [3]. if ( ev ) then {return true } 
 else {return false } 
c) Tính đúng đắn của lược đồ LD 1.01 
Đặt: qMHrMf mod)(),(2 , erMf ),(3 . Theo (3.1), (3.2), (3.3), (3.4), 
(3.5) và Mệnh đề 1.1 ta dễ dàng có được điều cần chứng minh ở đây là: ev . 
2.3.2 Lược đồ thứ hai LD 1.02 
Lược đồ LD 1.02 được phát triển từ dạng tổng quát với các lựa chọn: 
qrMHrMfrMf mod)||(),(),( 21 , )(),(3 MHrMf , khóa công khai được 
tính theo công thức: pgy x mod . Các thuật toán hình thành tham số, hình thành và 
kiểm tra chữ ký được mô tả trong các bảng 2.1 và bảng 2.2 dưới đây. 
a) Thuật toán hình thành chữ k ý 
Bảng 2.1 
Input: p, q, g, x, M. 
Output: (e,s) – chữ ký của U lên M. 
 [1]. select k: qk 1 
 [2]. pgr k mod (4.1) 
Công nghệ thông tin & Khoa học máy tính 
N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký  logarit rời rạc.” 108 
 [3]. qrMHe mod)||( (4.2) 
 [4]. qMHxeks mod)](..[ 1  (4.3) 
 [5]. return (e,s) 
Chú ý: “||” : toán tử nối 2 xâu bit. 
b) Thuật toán kiểm tra chữ k ý 
 Bảng 2.2 
Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. 
Output: (e,s) = true / false . 
 [1]. pygu MHees mod)(..  (4.4) 
 [2]. quMHv mod)||( (4.5) 
 [3]. if ( ev ) then {return true } 
 else {return false } 
c) Tính đúng đắn của lược đồ LD 1.02 
Đặt: erMfrMf ),(),( 21 và: )(),(3 MHrMf . Theo (4.1), (4.2), (4.3), 
(4.4), (4.5) và Mệnh đề 1.1 ta có: ev . Đây là điều cần chứng minh. 
2.3.3 Lược đồ thứ ba LD 2.01 
 Lược đồ LD 2.01 được phát triển từ dạng tổng quát với các lựa chọn: 
)(),(2 MHrMf , rrMf ),(3 , khóa công khai được tính theo công thức: 
pgy x mod . Các thuật toán hình thành tham số, hình thành và kiểm tra chữ ký được 
mô tả trong các bảng 3.1 và bảng 3.2 dưới đây. 
a) Thuật toán hình thành chữ k ý 
Bảng 3.1 
Input: p, q, g, x, M. 
Output: (e,s) – chữ ký của U lên M. 
 [1]. select k: qk 1 
 [2]. pgr k mod (5.1) 
 [3]. qre mod (5.2) 
 [4]. qrxMHks mod].)(.[ 1  (5.3) 
 [5]. return (e,s) 
b) Thuật toán kiểm tra chữ k ý 
 Bảng 3.2 
Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. 
Output: (e,s) = true / false . 
 [1]. pygu esMHs mod.)(.  (5.4) 
 [2]. quv mod (5.5) 
 [3]. if ( ev ) then {return true } 
 else {return false } 
c) Tính đúng đắn của lược đồ LD 2.01 
Đặt: )(),(2 MHrMf , rrMf ),(3 . Theo (5.1), (5.2), (5.3), (5.4), (5.5) và 
Mệnh đề 1.2 ta có: ev . Đây là điều cần chứng minh. 
2.3.4. Lược đồ thứ tư LD 2.02 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 109
Lược đồ LD 2.02 được phát triển từ dạng tổng quát với các lựa chọn: 
qrMHrMfrMf mod)||(),(),( 21 , 1),(3 rMf , khóa công khai được tính 
theo công thức: pgy x mod . Các thuật toán hình thành tham số, hình thành và 
kiểm tra chữ ký được mô tả trong các bảng 4.1 và bảng 4.2 dưới đây. 
a) Thuật toán hình thành chữ k ý 
Bảng 4.1 
Input: p, q, g, x, M. 
Output: (e,s) – chữ ký của U lên M. 
 [1]. select k: qk 1 
 [2]. pgr k mod (6.1) 
 [3]. qrMHe mod)||( (6.2) 
 [4]. qxeks mod].[ 1  (6.3) 
 [5]. return (e,s) 
b) Thuật toán kiểm tra chữ k ý 
 Bảng 4.2. 
Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. 
Output: (e,s) = true / false . 
 [1]. pygu ses mod.  (6.4) 
 [2]. quMHv mod)||( (6.5) 
 [3]. if ( ev ) then {return true } 
 else {return false } 
c) Tính đúng đắn của lược đồ LD 2.02 
Đặt: qrMHrMfrMf mod)||(),(),( 21 , 1),(3 rMf . Theo (6.1), (6.2), 
(.3), (.4), (.5) và Mệnh đề 1.2 ta có: ev . Đây là điều cần chứng minh. 
2.4 Mức độ an toàn của các lược đồ mới đề xuất 
Mức độ an toàn của một lược đồ chữ k ý số nói chung được đánh giá qua các khả năng 
sau: 
 a) Chống tấn công làm lộ khóa mật 
 Ở các lược đồ mới đề xuất, khóa công khai của người k ý được hình thành từ khóa bí 
mật tương ứng theo: pgy x mod . Như vậy, khả năng chống tấn công làm lộ khóa mật 
của các lược đồ này phụ thuộc vào tính khó giải của bài toán logarit rời rạc. 
b) Chống tấn công giả mạo chữ ký 
Từ thuật toán kiểm tra của các lược đồ mới đề xuất cho thấy, một cặp (e,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 được chỉ ra 
trong bảng 5 như sau: 
 Bảng 5. 
Lược đồ Điều kiện để (e,s) là chữ k ý hợp lệ với bản tin M 
LD 1.01 qpyge MHeMHs mod)mod( )(.)(. 
LD 1.02 qMpygHe MHees mod)||]mod([ )(.. 
LD 2.01 qpyge esMHs mod)mod( .)(. 
LD 2.02 qMpygHe ses mod)||]mod([ . 
Công nghệ thông tin & Khoa học máy tính 
N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký  logarit rời rạc.” 110 
Bản chất của việc tìm các (e,s) thỏa mãn điều kiện được chỉ ra trong bảng 5 là giải bài 
toán logarit rời rạc. Từ các kết quả nghiên cứu đã được công bố, có thể thấy rằng đây là 
một dạng bài toán khó nếu các tham số hệ thống được chọn đủ lớn để phương pháp vét cạn 
là không khả thi trong các ứng dụng thực tế. 
3. KẾT LUẬN 
Bài báo đề xuất phương pháp phát triển lược đồ chữ k ý số dựa trên bài toán logarit rời 
rạc bằng việc xây dựng lược đồ dạng tổng quát, từ đó phát triển một số lược đồ có thể ứng 
dụng trong thực tế. Mức độ an toàn của các lược đồ mới đề xuất được đánh giá bằng mức 
độ khó giải của bài toán logarit rời rạc. Tuy nhiên, cũng cần phải thấy rằng, để sử dụng 
trong thực tế, các lược đồ này cần được đánh giá kỹ càng cả về mức độ an toàn cũng như 
khía cạnh hiệu quả thực hiện. 
TÀI LIỆU THAM KHẢO 
 [1]. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", 
CRC Press, (1996). 
[2]. Hans Delfs, Helmut Knebl (2007), “Introduction to Cryptography: Principle and 
Applications”, Second Edition, Springer. 
[3]. T. ElGamal (1985), "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. 
[4]. National Institute of Standards and Technology, NIST FIPS PUB 186-3. Digital 
Signature Standard, US Department of Commerce, 1994. 
[5]. GOST R. 34.10-94. Standard Russian Federation. “Information Technology. 
Cryptographic Data Security”. Produce and check Procedures of Electronic Digital 
Signature based on Asymmetric Cryptographic Algorithm. Government Committee 
of the Russia for Standards, (1994). 
ABSTRACT 
DEVELOPING THE DIGITAL SIGNATURE SCHEMES BASED ON THE DISCRETE 
LOGARITHM PROBLEM 
This paper proposes methods of developing digital signature scheme based on the 
difficulty of the discrete logarithm problem. From the establishment of overview 
scheme, some digital signature schema have been proposed for practical 
applications. 
Keywords: Digital Signature, Digital Signature Schema, Discrete logarithm problem. 
Nhận bài ngày 04 tháng 02 năm 2015 
Hoàn thiện ngày 15 tháng 5 năm 2015 
Chấp nhận đăng ngày 12 tháng 06 năm 2015 
 Địa chỉ: 1Trường CĐ Kinh tế - Kỹ thuật TP Hồ Chí Minh; 
. *Email: thuynguyenduc@hotec.edu.vn; 
 2Học viện Kỹ thuật Quân sự.