Một phương pháp xây dựng lược đồ chữ ký số dựa trên bài toán logarit rời rạc

Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”; Cần Thơ, ngày 4-5/8/2016 
DOI: 10.15625/vap.2016.00055 
 MỘT PHƯƠNG PHÁP XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN 
 BÀI TOÁN LOGARIT RỜI RẠC 
 Lưu Hồng Dũng 1, Nguyễn Đức Thụy2, Lê Đình Sơn3, Nguyễn Thị Thu Thủy4 
 1 Khoa Công nghệ thông tin, Học viện Kỹ thuật Quân sự 
 2 Khoa Công nghệ thông tin, Cao đẳng Kinh tế - Kỹ thuật Tp. Hồ Chí Minh 
 3 Phòng SĐH, Học viện Kỹ thuật Quân sự 
 4 Khoa Cơ bản, Cao đẳng Kinh tế - Kỹ thuật Quảng Nam 
 luuhongdung@gmail.com, thuyphulam2013@gmail.com, sonld2004@gmail.com, thuytoankhcb@gmail.com 
TÓM TẮT— Bài báo đề xuất mộ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. Từ 
phương pháp được đề xuất có thể triển khai ra các lược đồ chữ ký khác nhau để lựa chọn phù hợp cho các ứng dụng trong thực tế. 
Từ khóa— Chữ ký số, lược đồ chữ ký số, thuật toán chữ ký số, bài toán logarit rời rạc. 
 I. ĐẶT VẤN ĐỀ 
 Lƣợc đồ chữ k‎ý số xây dựng trên bài toán logarit rời rạc lần đầu tiên đƣợc T. ElGamal [1] đề xuất vào năm 1985. 
Phƣơng pháp xây dựng lƣợc đồ chữ k‎ý của ElGamal đã đƣợc sử dụng trong nhiều lƣợc đồ chữ k‎ý phát triển sau đó, mà 
quan trọng nhất là lƣợc đồ chữ k‎ý Schnorr [2] với việc cải tiến các tham số hệ thống nhằm cho phép rút gọn độ dài chữ ký 
và giảm độ phức tạp tính toán trong các thủ tục sinh và kiểm tra chữ ký. Các chuẩn chữ k‎ý số của Hoa Kỳ [3], Nga [4],  
đều đƣợc xây dựng trên cơ sở kết hợp phƣơng pháp của ElGamal và Schnorr. Các lƣợc đồ chữ k‎ý này đƣợc gọi chung là 
họ chữ k‎ý ElGamal. Trong [5] các tác giả đề xuất một phƣơng pháp xây dựng lƣợc đồ chữ k‎ý số đƣợc phát triển từ 
phƣơng pháp xây dựng của họ chữ k‎ý ElGamal, ƣu điểm của phƣơng pháp đề xuất là có thể phát triển đƣợc nhiều lƣợc đồ 
chữ k‎ý khác nhau cho các ứng dụng thực tế. 
 Trong bài báo này, nhóm tác giả tiếp tục đề xuất mộ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, tuy nhiên phƣơng pháp đề xuất ở đây có nguyên tắc thiết kế hoàn toàn khác với phƣơng pháp 
xây dựng của họ chữ k‎ý ElGamal. Tƣơng tự [5], ƣu điểm của phƣơng pháp mới đề xuất ở đây là từ đó có thể phát triển 
đƣợc nhiều lƣợc đồ chữ ký khác nhau để lựa chọn phù hợp với yêu cầu của các ứng dụng trong thực tế. Hiện tại, chƣa có 
các kết quả nghiên cứu tƣơng tự đƣợc công bố ở trong và ngoài nƣớc. 
 II. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC 
A. Phương pháp xây dựng lược đồ chữ ký trên bài toán logarit rời rạc 
 1. Bài toán logarit rời rạc 
 *
 Cho p là số nguyên tố, g là phần tử sinh của nhóm ℤp . Khi đó bài toán logarit rời rạc trên trƣờng hữu hạn nguyên 
tố DLP(p,g) đƣợc phát biểu nhƣ sau: 
 *
 Bài toán DLP(g,p) : Với mỗi số nguyên dƣơng y ℤp , hãy tìm x thỏa mãn phƣơng trình: 
 g x mod p y (1.1) 
 Giải thuật cho bài toán DLP(g,p) có thể đƣợc viết nhƣ một thuật toán tính hàm DLP(g,p)(.) 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): 
 x DLP(g, p) (y) (1.2) 
 Dạng lƣợc đồ chữ ký xây dựng theo phƣơng pháp mới đề xuất ở đây cho phép các thực thể k‎ý trong cùng một 
hệ thống có thể dùng chung bộ tham số {g, p}, trong đó 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< x < (p-1), tính và công khai tham số: 
 y g x mod p (1.3) 
 Chú ý: 
 *
 (i) Mặc dù bài toán DLP(g,p) là khó, tuy nhiên không phải với mọi y ℤp thì việc tính DLP(g,p) (y) đều khó, chẳng 
hạn những , 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 tham số mật x phải đƣợc lựa chọn sao cho việc tính DLP(g,p) (y) đều khó. 
 (ii) Với lựa chọn x nêu trên, chỉ có ngƣời ký U biết đƣợc giá trị x, vì vậy việc biết đƣợc x đủ để xác thực đó là U. 
454 MỘT PHƢƠNG PHÁP XÂY DỰNG LƢỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC 
B. Xây dựng lược đồ chữ ký số trên bài toán DLP(p,g) 
 Dạng lƣợc đồ mới đề xuất ở đây xây dựng dựa trên tính khó giải của bài toán DLP(g,p) 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ố DSS (Digital Signature Standard) của 
Hoa Kỳ [3] hay GOST R34.10-94 [4] của Liên bang Nga. Giả sử rằng khóa bí mật của ngƣời k‎ý là x đƣợc chọn ngẫu 
nhiên trong khoảng (1, p) và khóa công khai tƣơng ứng y đƣợc hình thành từ x theo (1.3): 
 y g x mod p 
 *
 Ở đây p là số nguyên tố đƣợc chọn sao cho việc giải bài toán DLP(g,p) (y) là khó, g là phần tử sinh của nhóm ℤp 
có bậc là q, với q|(p-1). 
 Giả sử (r,v) là chữ k‎ý lên bản tin M, u là 1 giá trị: 1 < u < q và r đƣợc tính từ u theo công thức: 
 r gu mod p (1.4) 
 và v là một giá trị đƣợc tính từ s theo công thức: 
 v g s mod p (1.5) 
 Cũng giả thiết rằng phƣơng trình kiểm tra của lƣợc đồ có dạng: 
 f M , f r,s f M , f r,s f M , f r,s 
 v 1  r 2 y 3 mod p 
 Ở đây f (r, s) là hàm của r và s. Do (1.5), nên f (r,s) có thể biểu diễn dƣới dạng hàm của r và v: f (r,s) F(r,v) 
và đƣợc lựa chọn khác nhau trong các trƣờng hợp cụ thể, ví dụ nhƣ: F(r,v) r v 1 , F(r,v) r 1 v , F(r,v) r v2 , 
 F(r,v) r 2 v , 
 Xét trƣờng hợp: f (r,s) F(r,v) r vmod p r g s mod p (1.6) 
 và: f (r, s) F(r,v) gk mod p (1.7) 
 với k đƣợc chọn ngẫu nhiên trong khoảng (1,q) . Đặt: g k mod p Z , khi đó ta có: f (r, s) F(r,v) Z , nên có 
thể đƣa phƣơng trình kiểm tra về dạng: 
 s. f M ,Z u. f M ,Z x. f M ,Z 
 g 1  g 2 g 3 mod p (1.8) 
 Từ (1.1), (1.3), (1.4) và (1.8) ta có: 
 s f1(M,Z)  u f2 (M,Z) x f3 (M,Z) modq (1.9) 
 Từ (1.9) suy ra: 
 1 1
 s u f1(M, Z) f2 (M, Z) x f1(M, Z) f3 (M, Z) mod q (1.10) 
 Mặt khác, từ (1.6) và (1.7) ta có: 
 s u modq k (1.11) 
 Từ (1.10) và (1.11) ta có: 
 1 1
 u f1(M, Z) f2 (M, Z) x f1(M, Z) f3 (M, Z) u mod q k 
 hay: 
 1 1
 u ( f1(M,Z) f2 (M,Z) 1) x f1(M,Z) f3 (M,Z) modq k 
 suy ra: 
 1 1 1
 u f1(M, Z) f2 (M, Z) 1) (k x f1(M, Z) f3 (M, Z) mod q (1.12) 
 Từ (1.12), thành phần thứ nhất của chữ ký đƣợc tính theo (1.4): 
 r g u mod p 
và thành phần thứ 2 đƣợc tính theo (1.10): 
 Từ đây, một dạng lƣợc đồ chữ ký tƣơng ứng với trƣờng hợp: F(r,v) r vmod p g k mod p đƣợc chỉ ra nhƣ 
các Bảng 1, Bảng 2 và Bảng 3 dƣới đây. 
Lƣu Hồng Dũng, Nguyễn Đức Thụy, Lê Đình Sơn, Nguyễn Thị Thu Thủy 455 
 Bảng 1. Thuật toán hình thành tham số và khóa 
 Input: p, q, x. 
 Output: g, y. 
 [1]. select h: 1 h p 
 [2]. g  h p 1 / q mod p 
 [3]. if ( g = 1) then goto [1] 
 [4]. y  g x mod p 
 [5]. return {g,y} 
Chú ‎thích: 
 (i) p,q: các số nguyên tố thỏa mãn điều kiện: p N q 1, N=1,2,3,. 
 (ii) x,y: khóa bí mật, công khai của đối tƣợng ký U. 
 Bảng 2. Thuật toán hình thành chữ ký 
 Input: p, q, g, x, M. 
 Output: (r,s). 
 [1]. select k: 1 k q 
 [2]. Z  g k mod p (1.13) 
 [3]. w1  f1(M, Z) 
 1
 [4]. w1  w1 modq 
 [5]. w2  f 2 (M,Z) 
 [6]. w  w1 w2 
 [7]. if (gcd(w 1,q) 1) goto [1] 
 [8]. 
 w3  f3 (M,Z)
 1
 [9]. u  w 1 k x w1 w3 mod q (1.14) 
 [10]. r  g u mod p (1.15) 
 [11]. s  u w x w1 w3 mod q (1.16) 
 [12]. return (r,s) 
Chú ‎thích: 
 (i) M: bản tin cần ký, với: M {0,1} . 
 (ii) (r,s): chữ ký của U lên M. 
 ‎‎ Bảng 3. Thuật toán kiểm tra chữ ký 
 Input: p, q, g, y, {M,(r,s)}. 
 Output: true / false . 
 [1]. Z  f (r,s) 
 [2]. w1  f1 (M,Z) 
 [3]. w2  f 2 (M,Z) 
 [4]. 
 w3  f3 (M,Z)
 [5]. A  g s.w1 mod p (1.17) 
 [6]. B  r w2 yw3 mod p (1.18) 
 [7]. if ( A B ) then {return true } 
 else {return false } 
 Chú ‎thích: 
 (i) M, (r,s): bản tin, chữ ký cần thẩm tra. 
 (ii) 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. 
456 MỘT PHƢƠNG PHÁP XÂY DỰNG LƢỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC 
1. Tính đúng đắn của dạng 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), 1 h p, g h( p 1) / q mod p , 
 x k 1
1 k, x q , y g mod p , Z f (r, s) g mod p, w1 f1(M,Z) , w1 w1 modq , w2 f2 (M,Z), w w1 w2 , 
 , , 1 , u , . 
gcd(w 1,q) 1 w3 f3(M,Z) u w 1 k x w1 w3 mod q r g mod p s u w x w1 w3 mod q
 s.w
Nếu: A g 1 mod p , B r w2 yw3 mod p thì: A B . 
 Tính đúng đắn của lƣợc đồ dạng tổng quát có thể đƣợc chứng minh nhƣ sau: 
 Từ (1.17) và (1.18) ta có: 
 A g s.w1 mod p g s. f1(M ,Z ) mod p
 u. f (M ,Z ) 1. f (M ,Z ) x. f (M ,Z ) 1. f (M ,Z ) . f (M ,Z ) (1.19) 
 g 1 2 1 3 1 mod p
 g u. f2 (M ,Z ) x. f3 (M ,Z ) mod p
 Từ (1.14) và (1.19) ta lại có: 
 w2 w3 u. f2 (M ,Z ) x. f 3(M ,Z )
 B r y mod p g g mod p (1.20) 
 g u. f2 (M ,Z ) x. f3 (M ,Z ) mod p
 Từ (1.19) và (1.20) suy ra: A B . Đây là điều cần chứng minh. 
C. Một lược đồ chữ ký phát triển theo phương pháp mới đề xuất 
 Lƣợc đồ chữ ký LD 16.5-01 
 Lƣợc đồ chữ ký - ký hiệu LD 16.5-01, đƣợc phát triển từ dạng lƣợc đồ mới đề xuất với các lựa chọn: 
 f1(M,Z) Z , f2 (M, Z) H(M) , f3 (M, Z) Z , ở đây H(.) là hàm băm và H(M) là giá trị đại diện của bản tin 
 M. Các thuật toán hình thành tham số và khóa, thuật toán ký và kiểm tra chữ ký của lƣợc đồ đƣợc mô tả 
 trong các Bảng 4, Bảng 5 và Bảng 6 dƣới đây. 
 Bảng 4. Thuật toán hình thành tham số và khóa 
 Input: p, q, x. 
 Output: g, y, H(.). 
 [1]. select h: 
 [2]. g  h p 1 / q mod p 
 [3]. if ( g = 1) then goto [1] 
 [4]. y  g x mod p (2.1) 
 [5]. select H : 0,1 Zt , q t p 
 [6]. return {g,y,H(.)} 
 Bảng 5. Thuật toán k‎ý 
 Input: p, q, g, x, M – bản tin cần ký. 
 Output: (r,s) – chữ ký của U lên M. 
 [1]. E H(M) 
 [2]. select k: 1 k q 
 [3]. Z  g k mod p (2.2) 
 [4]. if ((gcd(Z,q) 1) OR (gcd(Z 1 E 1,q) 1) ) then goto [2] 
 1
 [5]. u  Z 1 E 1 k x modq 
 [6]. r  g u mod p (2.3) 
 [7]. s  u Z 1 E x modq (2.4) 
 [8]. return (r,s) 
 Bảng 6. Thuật toán kiểm tra 
 Input: p, q, g, y, M, (r,s). 
 Output: true / false . 
 [1]. E H(M) 
 [2]. W  r g s mod p 
 [3]. A  g s.W mod p (2.5) 
 [4]. B  r E yW mod p (2.6) 
 [5]. if ( A B ) then {return true } 
 else {return false } 
Lƣu Hồng Dũng, Nguyễn Đức Thụy, Lê Đình Sơn, Nguyễn Thị Thu Thủy 457 
2. Tính đúng đắn của lƣợc đồ LD 16.5 - 01 
 Điều cần chứng minh ở đây là: Cho p, q là 2 số nguyên tố với q|(p-1), H : 0,1 Zn , q n p , 
 k 1
1 k, x q , y g x mod p , Z g mod p , E H M , u Z 1 E 1 k x modq , r g u mod p , 
s u Z 1 E x modq . Nếu: W r g s mod p, A g s.W mod p , B r E yW mod p thì: A B . 
 Tính đúng đắn của lƣợc đồ mới đề xuất đƣợc chứng minh nhƣ sau: 
 Từ (2.2), (2.3), (2.4) và (2.5) ta có: 
 s
 A g s.W mod p g s. g .r mod p mod p
 g s. r.v mod p mod p g s.Z mod p (2.7) 
 1
 g u.Z .E x .Z mod p g u.E x.Z mod p
 Từ (2.1), (2.2), (2.3) và (2.6) ta lại có: 
 E W u.E x. g s .r mod p 
 B r y mod p g g mod p (2.8) 
 g u.E g x. r.vmod p mod p g u.E x.Z
 Từ (2.7) và (2.8) suy ra: A B 
 Đây là điều cần chứng minh. 
3. Mức độ an toàn của lƣợc đồ LD 16.5-01 
 Ở dạng lƣợc đồ mới đề xuất, khóa công khai đƣợc hình thành từ khóa bí mật dựa trên tính khó giải của bài toán 
logarit rời rạc trên trƣờng hữu hạn nguyên tố DLP(g,p). Vì vậy, nếu các tham số {p,q,g} đƣợc chọn để bài toán DLP(g,p) 
là khó thì mức độ an toàn của lƣợc đồ mới đề xuất xét theo khả năng chống tấn công làm lộ khóa mật sẽ đƣợc đánh giá 
bằng mức độ khó của bài toán DLP(g,p) . Cần chú ý rằng, để bài toán DLP là khó thì các tham số {p,q,g,n} cần phải 
đƣợc lựa chọn tƣơng tự nhƣ DSA [3] hay GOST R34.10-94 [4], với: | p | 512bit , | q | 160bit , | n | 160bit . 
 Từ Thuật toán kiểm tra (Bảng 6) của lƣợc đồ LD 16.5-01 cho thấy, một cặp (r,s) bất kỳ sẽ đƣợc công nhận là 
chữ ký hợp lệ của U lên một bản tin M nếu thỏa mãn điều kiện: 
 s s
 g s. g .r mod p  r E y g .r mod p mod p (2.9) 
 Ở đây: U là đối tƣợng ký sở hữu khóa công khai y và E H(M) là giá trị đại diện của bản tin cần thẩm tra M. 
Từ các kết quả nghiên cứu đã đƣợc công bố, có thể thấy rằng việc tìm đƣợc một cặp (r,s) giả mạo thỏa mãn (2.9) là một 
dạng bài toán khó chƣa có lời giải nếu các tham số {p,q,n} đƣợ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ế. 
 III. KẾT LUẬN 
 Bài báo đề xuất một phƣơng pháp thiết kế lƣợc đồ chữ số‎mới dựa trên tính khó giải của bài toán logarit rời rạc và 
có thể đƣợc sử dụng để phát triển các lƣợc đồ lƣợc đồ chữ k‎‎ý khác nhau cho các ứng dụng thực tế. Bài báo cũng đề xuất 
một lƣợc đồ chữ ký xây dựng theo phƣơng pháp này (lƣợc đồ LD 16.5 – 01), đã cho thấy tính khả thi của phƣơng pháp 
đƣợc đề xuất. Mức độ an toàn và hiệu quả thực hiện của các lƣợc đồ chữ k‎‎ý phát triển theo phƣơng pháp đề xuất ở đây 
phụ thuộc vào việc lựa chọn các hàm f (r,s), F(r,v) , f1,2,3(M,Z) và các tham số hệ thống, nếu việc lựa chọn nói trên 
là hợp lý thì khả năng ứng dụng của các lƣợc đồ dạng này trong thực tế là rất khả quan. Tuy nhiên, mục tiêu của bài báo 
chỉ giới hạn ở việc đề xuất một phƣơng pháp xây dựng lƣợc đồ chữ k‎‎ý mới, nên ở đây việc triển khai ứng dụng phƣơng 
pháp mới đề xuất để tạo ra các lƣợc đồ chữ ký có độ an toàn và hiệu quả thực hiện cao, ví dụ nhƣ việc lựa chọn các 
hàm , , ,... đã không đƣợc đặt ra, đây sẽ là những vấn đề cần đƣợc nghiên cứu tiếp theo. 
 TÀI LIỆU THAM KHẢO 
[1] 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. 
[2] C. P. Schnorr (1991). “Efficient signature generation by smart cards”. J. Cryptol., 4(3):161–174. 
[3] National Institute of Standards and Technology, NIST FIPS PUB 186-3. Digital Signature Standard, U.S. Department of 
 Commerce, 1994. 
[4] GOST R 34.10-94. Russian Federation Standard. 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 (in Russian). 
[5] Luu Hong Dung, Le Dinh Son, Ho Nhat Quang, Nguyen Duc Thuy (2015). “DEVELOPING DIGITAL SIGNATURE 
 SCHEMES BASED ON DISCRETE LOGARITHM PROBLEM”. Hội nghị khoa học Quốc gia lần thứ VIII về Nghiên cứu cơ 
 bản và ứng dụng Công nghệ thông tin (FAIR 2015). ISBN: 978-604-913-397-8. 
458 MỘT PHƢƠNG PHÁP XÂY DỰNG LƢỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC 
 A NEW CONSTRUCTION METHOD OF DIGITAL SIGNATURE SCHEME 
 BASED ON DISCRETE LOGARITHM PROBLEM 
 Luu Hong Dung, Nguyen Duc Thuy, Le Dinh Son, Nguyen Thi Thu Thuy 
ABSTRACT—This paper proposes methods for developing digital signature scheme based on the difficulty of the discrete logarithm 
problem. With the new method proposed, can develop some signature schemes for practical applications. 
Keywords— Digital Signature, Digital Signature Schema, Digital Signature Algorithm, Discrete Logarithm Problem. 
.