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

ều kiện 
)1(| pq , phg qp mod/)1(  với: ph 1 ,   tZH 

1,0: với: ptq  , qkx  ,1 , 
pgy x mod , pgr k mod , qMrHe mod)||( , qekxs mod)(1   . Nếu: 
pygu se mod  và   qMrHv mod|| thì: ev  . 
Công nghệ thông tin 
N. T. Giang, L. H. Dũng, “Phát triển lược đồ chữ ký số mù dựa trên bài toán logarit rời rạc.” 50 
Thật vậy, từ (2.2), (2.4), (2.5) và (2.6) ta có: 
pgpg
pggpygu
kexs
sxese
modmod
modmod
.
.




 (2.8) 
Từ (2.3) và (2.8), suy ra: ru  (2.9) 
Thay (2.9) vào (2.7) ta được: 
  qMrHqMuHv mod)||(mod||  (2.10) 
Từ (2.4) và (2.10), suy ra điều cần chứng minh: ev  
3.1.3. Mức độ an toàn của lược đồ cơ sở 
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: 
- Chống tấn công làm lộ khóa mật. 
- Chống tấn công giả mạo chữ ký. 
Về khả năng chống tấn công làm lộ khóa mât: Từ (2.2) cho thấy mức độ an 
toàn của lược đồ cơ sở phụ thuộc vào mức độ khó giải của bài toán logarit rời rạc 
tương tự như với các lược đồ chữ ký DSA trong chuẩn chữ ký DSS [9] của Hoa kỳ 
hay chuẩn chữ ký GOST R34.10-94 [10] của Liên bang Nga, 
Về khả năng chống tấn công giả mạo chữ ký: Từ (2.4), (2.6) và (2.7) của lược đồ 
cơ sở cho thấy, một cặp (e,s) bất kỳ (không được tạo ra bởi Thuật toán ký 2.2 của 
lược đồ và từ khóa bí mật x của người ký) nhưng vẫn sẽ được công nhận là chữ ký 
hợp lệ của đối tượng sở hữu khóa công khai y lên bản tin M nếu thỏa mãn điều kiện: 
 qMpygHe se mod)||)mod((   (2.11) 
Như vậy, mức độ an toàn xét theo khả năng chống tấn công giả mạo chữ ký của 
lược đồ cơ sở phụ thuộc vào độ khó của việc giải (2.11). Để giải (2.11), giả sử 
chọn trước M và e rồi tìm s. Khi đó, việc giải (2.11) sẽ trở thành tìm s từ: 
 qMpyHN s mod)||mod( (2.12) 
ở đây: N là hằng số. Rõ ràng việc giải (2.12) là khó hơn (2.1) nếu các tham số p, 
q và kích thước đầu ra hàm băm H(.) được chọn đủ lớn. Ngoài ra, cũng có thể chọn 
trước M và s rồi tìm e, khi đó việc giải (2.11) sẽ trở thành: 
qMpNgHe e mod)||mod(  (2.13) 
trong đó: e là ẩn số cần tìm và N là hằng số. Dễ thấy rằng việc giải (2.13) còn 
khó hơn giải (2.12). Như vậy, nếu không có một giải thuật hiệu quả cho (2.11) thì 
việc giải (2.12) và (2.13) để tìm được 1 cặp (e,s) thỏa mãn điều kiện kiểm tra của 
lược đồ cơ sở là khó hơn việc giải bài toán logarit rời rạc DLP(g,p). 
3.2. Xây dựng lược đồ chữ k ý số mù 
Lược đồ chữ k ý mù ở đây được phát triển từ lược đồ cơ sở ở mục 2.1. Giả sử A 
là người người k ý và B là người tạo ra bản tin M được k ý, các tham số hệ thống và 
khóa của A, B được hình thành theo Thuật toán 2.1 của lược đồ cơ sở. Khi đó, 
thuật toán ký và kiểm tra chữ ký của lược đồ được chỉ ra như sau: 
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 51
3.2.1. Thuật toán k ý 
Thuật toán 3.1: 
Input: p, q, g, x, y, α, β, k , M. 
Output: (e,s). 
[1]. pgr ka mod (3.1) 
[2].   pygrr ab mod
.  (3.2) 
[3]. qMrHe b mod)||( (3.3) 
[4]. qeeb mod)(
1    (3.4) 
[5].   qekxs ba mod
1   (3.5) 
[6].   qss a mod  (3.6) 
[7]. return (e,s) 
Chú thích: 
- Các bước [1], [5] do người ký A thực hiện. 
- Các bước [2], [3], [4], [6] và [7] do người có bản tin cần k ý B thực hiện. 
- Tham số k do A lựa chọn thỏa mãn: 1< k < q. 
- Tham số α, β do B lựa chọn thỏa mãn: 1 < α, β < q. 
- {x,y} là cặp khóa bí mật/công khai của A. 
3.2.2. Thuật toán kiểm tra 
 Thuật toán 3.2: 
Input: p, q, g, y, M, (e,s). 
Output: (e,s) = true / false . 
[1]. pygu se mod  (3.7) 
[2].   qMuHv mod|| (3.8) 
[3]. if ( ev  ) then {return true } 
 else {return false } 
Chú thích: 
- Nếu kết quả trả về true thì tính hợp lệ của chữ ký (e,s) được công nhận, do đó 
tính toàn vẹn của bản tin cần thẩm tra M và danh tính của người ký (A) được 
khẳng định. 
- Nếu kết quả trả về là false thì chữ ký (e,s) là giả mạo, hoặc nội dung bản tin 
M đã bị sửa đổi. 
3.2.3. 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ố thỏa mãn điều kiện 
)1(| pq , phg qp mod/)1(  với: ph 1 ,   tZH 

1,0: với: ptq  , 
qkx  ,1 , q  ,1 , pgy x mod , pgr ka mod ,   pygrr ab mod
.  , 
Công nghệ thông tin 
N. T. Giang, L. H. Dũng, “Phát triển lược đồ chữ ký số mù dựa trên bài toán logarit rời rạc.” 52 
qMrHe b mod)||( ,   qeeb mod
1    ,   qekxs ba mod
1   , 
  qss a mod  . Nếu: pygu
se mod  và   qMuHv mod|| thì: ev  . 
Thật vậy, từ (3.4), (3.5), (3.6) và (3.7) ta có: 
   pgg
pggpygu
bb
ab
ekxxe
sxese
mod
modmod
....
).(..
1 






    
    pggg
pggggg
pgggg
kx
ekxe
ekxxxe
bb
bb
mod
mod
mod
.
...
).(..... 1







 
 (3.9) 
Từ (2.2), (3.1) và (3.9) ta có: 
    
  pygr
pgggu
a
kx
mod
mod
.
.



 (3.10) 
Từ (3.2) và (3.10), suy ra: bru  (3.11) 
Thay (3.11) vào (3.8) ta có: 
   qMrHqMuHv b mod)||(mod||  (3.12) 
Từ (3.2) và (3.12), suy ra: ev  . Đây là điều cần chứng minh. 
3.2.4. Khả năng chống tấn công làm lộ nguồn gốc bản tin được ký 
 Khả năng chống tấn công làm lộ khóa mật và chống giả mạo chữ ký của lược 
đồ mới đề xuất có thể phân tích tương tự như với lược đồ cơ sở ở mục 3.1.3. 
Từ thuật toán ký (Thuật toán 3.1) của lược đồ cho thấy nếu tính được các tham 
số (α,β) và giá trị của các tham số {sa,ra,eb} được lưu trữ ở mỗi lần ký cùng với 
định danh của những người yêu cầu k ý: IDB = {IDBi)| i=0,1,2,N}, thì người k ý A 
hoàn toàn có thể xác định được mối quan hệ giữa {M,(e,s)} với IDBi, nghĩa là có 
thể xác định được nguồn gốc bản tin bằng một trong các thuật toán sau: 
Thuật toán 3.3 
Input: {(rai,IDBi)| i=0,1,2,N}, M, (e,s), α, β. 
Output: IDBi. 
[1]. i = 0 
[2]. select: ),( Biai IDr 
[3].   pygrr aibi mod*
.  
[4]. qMrHe bi mod)||*(
 
[5]. if ee  then 
 [5.1]. 1 ii ; 
 [5.2]. goto [2]; 
[6]. return IDBi 
Hoặ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 53
Thuật toán 3.4 
Input: {(ebi,IDBi)| i=0,1,2,N}, M, (e,s), α, β. 
Output: IDBi. 
[1]. i = 0 
[2]. select: ),( Bibi IDe 
[3]. qeebi mod)(
1    
[4]. if bibi ee 
 then 
 [4.1]. 1 ii ; 
 [4.2]. goto [2]; 
[5]. return IDBi 
Từ thuật toán ký (Thuật toán 3.1) của lược đồ cho thấy, chỉ có thể thiết lập mối 
quan hệ giữa mỗi (sai,ebi) thuộc: {(sai,ebi)| i=0,1,2,N} với một {M,(e,s)} thông 
qua một cặp (α,β) nhờ (3.4) và (3.6) như sau: 
 



 
qss
qee
ai
bi
mod
mod)(1

 (3.13) 
Tuy nhiên, giải (3.13) sẽ không chắc chắn nhận được cặp (α,β) mong muốn. Bởi 
vì với mỗi (sai,ebi) thuộc: {(sai,ebi)| i=0,1,2,N} sẽ luôn tìm được một cặp (α,β) 
tương ứng. Do đó, việc ứng dụng các thuật toán như trên để tấn công làm lộ nguồn 
gốc bản tin là không khả thi đối với lược đồ mới đề xuất. 
4. KẾT LUẬN 
Từ việc phân tích điểm yếu của một số lược đồ chữ k ý số mù đã được công bố, 
bài báo đề xuất lược đồ chữ k ý số mù mới được phát triển từ lược đồ chữ k ý cơ sở 
xây dựng dựa trên tính khó của bài toán logarit rời rạc, lược đồ mới này có mức độ 
an toàn cao hơn các lược đồ đã biết về khả năng chống tấn công làm lộ nguồn gốc 
của bản tin được ký. Đây là một yếu tố quan trọng cho phép lược đồ mới đề xuất 
có tính khả thi trong các ứng dụng thực tế. 
TÀI LIỆU THAM KHẢO 
[1]. D. Chaum, “Blind Signature Systems”, Advances in Cryptology, Crypto’ 83, 
Plenum Press, pp. 153. 
[2]. D. Chaum, A. Fiat, M. Naor, “Untraceable Electronic Cash”, Advances in 
Cryptology,Crypto’ 88, LNCS 403, Springer Verlag, pp. 319-327. 
[3]. D. Chaum, “Privacy Protected Payment”, SMART CARD 2000, Elsevier 
Science Publishers B.V., 1989, pp. 69-93. 
[4]. N. Ferguson, “Single Term Off-line Coins”, Advances in Cryptology, 
Eurocrypt’93, LNCS 765, Springer Verlag, pp. 318-328. 
Công nghệ thông tin 
N. T. Giang, L. H. Dũng, “Phát triển lược đồ chữ ký số mù dựa trên bài toán logarit rời rạc.” 54 
[5]. D. Chaum, B. den Boer, E. van Heyst, S. Mjolsnes, A. Steenbeek, “Efficient 
Offline Electronic Checks”, Advances in Cryptology, Eurocrypt’89, LNCS 
434, Springer Verlag, pp. 294-301. 
[6]. Nguyễn Tiền Giang, Nguyễn Vĩnh Thái, Lưu Hồng Dũng, “Lược đồ chữ ký số 
mù xây dựng trên bài toán khai căn”, Chuyên san Công nghệ thông tin và 
Truyền thông (Học viện Kỹ thuật Quân sự) số 5 (10 – 2014), trang 102 - 114 
[7]. Nikolay A. Moldovyan, “Blind Collective Signature Protocol”, Computer 
Science Journal of Moldova, vol.19, no.1(55), 2011. 
[8]. T. ElGamal, “ A public key cryptosystem and a signature scheme based on 
discrete logarithms”, IEEE Transactions on Information Theory. 1985, Vol. 
IT-31, No. 4. pp.469–472. 
[9]. National Institute of Standards and Technology. NIST FIPS PUB 186-
3(2013). Digital Signature Standard, U.S. Department of Commerce. 
[10]. GOST R 34.10-94. Russian Federation Standard. Information 
Technology(1994). Cryptographic data Security. Produce and check 
procedures of Electronic Digital Signature based on Asymmetric 
Cryptographic Algorithm. Government Committee of the Russia for 
Standards (in Russian). 1994. 
ABSTRACT 
DEVELOP BLIND DIGITAL SIGNATURE SCHEMA BASED 
ON DISCRETE LOGARITHM PROBLEM 
 This paper proposes a blind signature schema developed from a digital 
signature scheme based on the difficulty of the discrete logarithm problem. 
The new blind 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; Blind Digital Signature; Digital Signature Schema; Blind Digital Signature Schema. 
Nhận bài ngày 28tháng 06 năm 2018 
Hoàn thiện ngày 28 tháng 09 năm 2018 
Chấp nhận đăng ngày 05 tháng 11 năm 2018 
Địa chỉ: 1 Cục CNTT, BQP; 
 2 Khoa CNTT, Học viện KTQS. 
 *Email: luuhongdung@gmail.com.