Một lược đồ chữ ký xây dựng 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ố

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 57
MỘT LƯỢC ĐỒ CHỮ KÝ XÂY DỰNG 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Ố 
Nguyễn Vĩnh Thái1, Lưu Hồng Dũng2* 
Tóm tắt: Bài báo đề xuất một lược đồ chữ ký số xây dựng 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 trên Zp với phân tích một số nguyên 
lớn ra các thừa số nguyên tố. Vì thế, thuật toán chữ ký mới đề xuất ở đây có thể đáp 
ứng được các ứng dụng có yêu cầu cao về độ an toàn trong thực tế. 
Từ khóa: Logarit rời rạc; Phân tích số; Khai căn; Thuật toán khóa mật mã; Hệ thống mã khóa khóa công khai. 
1. ĐẶT VẤN ĐỀ 
Nâng cao độ an toàn cho các thuật toán mật mã khóa công khai và 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 [1-8]. Trong bài báo này, 
cũng với mục đích nâng cao độ an toàn cho thuật toán trước một số dạng tấn công 
trong thực tế, nhóm tác giả đề xuất một lược đồ chữ ký số được xây dựng 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 trên Zp (bài toán logarit 
rời rạc) và bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố (bài toán 
phân tích số). Ngoài việc nâng cao độ an toàn cho thuật toán như [1-8], lược đồ 
chữ ký được đề xuất ở đây còn cho phép các thực thể cuối (người ký) trong cùng 
một hệ thống có thể sử dụng chung một bộ tham số (tham số miền) do nhà cung 
cấp dịch vụ tạo ra. Do đó, có thể sử dụng lược đồ mới đề xuất trong việc xây dựng 
các giao thức mật mã nhằm chống lại các dạng tấn công giả mạo rất hiệu quả. 
2. MỘT SỐ BÀI TOÁN KHÓ ỨNG DỤNG TRONG MẬT MÃ 
2.1. Bài toán phân tích số 
Bài toán phân tích số được phát biểu như sau: Cho số  ∈ ℕ, hãy tìm biểu diễn: 
 = Π
 
 với:  ≥ 1 ( = 1,  , ) nguyên dương; 
  ≥ 1 ( = 1,  , ) nguyên tố. 
Một trường hợp riêng của bài toán phân tích số được ứng dụng để xây dựng hệ 
mật RSA mà ở đó  là tích của hai số nguyên tố  và . Khi đó, bài toán phân tích 
số hay còn gọi là bài toán () được phát biểu như sau: 
Với mỗi số nguyên dương , hãy tìm số nguyên tố  hoặc  thỏa mãn phương 
trình sau:  ×  =  
Giải thuật cho bài toán () có thể được viết như một thuật toán tính hàm 
(.) với biến đầu vào là , còn giá trị hàm là  hoặc  của phương trình sau: 
 = () hoặc:  = () 
Trong hệ mật RSA [10], bài toán phân tích số được sử dụng trong việc hình 
thành cặp khóa công khai/bí mật cho mỗi thực thể ký. Với việc giữ bí mật các tham 
số (, ) thì việc tính được khóa bí mật () từ khóa công khai () và () 
là một bài toán khó nếu ,  được chọn đủ lớn và mạnh. Hiện tại bài toán trên vẫn 
Công nghệ thông tin 
N. V. Thái, L. H. Dũng, “Một lược đồ chữ ký xây dựng trên tính khó  và phân tích số.” 58 
được coi là bài toán khó do chưa có giải thuật thời gian đa thức hay đa thức xác 
suất cho nó và hệ mật RSA là một minh chứng thực tế cho tính khó giải của bài 
toán này. Trong thực tế, các tham số ,  có thể chọn theo FIPS 186 - 4 [9] của 
Hoa Kỳ cho hệ mật RSA. 
2.2. Bài toán logarit rời rạc trên  
Cho cặp số nguyên dương (, ) với  là số nguyên tố, còn  là một phần tử 
của nhóm 
∗ . Khi đó, bài toán logarit rời rạc trên Z hay còn gọi là bài toán 
DLP(,) được phát biểu như sau: 
Với mỗi số nguyên dương  ∈ ℤ
∗ , hãy tìm  thỏa mãn phương trình sau: 
   =  
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à , còn giá trị hàm là  của phương trình sau: 
 = DLP(,)() 
Bài toán DLP(,) là cơ sở để xây dựng nên hệ mật ElGamal [11]. Hiện tại chưa 
có giải thuật hiệu quả (thời gian đa thức hay đa thức xác suất) cho DLP(,) và độ 
an toàn của thuật toán DSA trong chuẩn chữ ký số DSS của Hoa Kỳ là một minh 
chứng thực tế cho tính khó giải của bài toán này. 
3. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ 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Ố 
3.1. Thuật toán hình thành tham số và khóa 
Các tham số hệ thống hay tham số miền được nhà cung cấp dịch vụ chứng thực 
số hình thành bằng thuật toán như sau: 
a) Thuật toán 1. Hình thành các tham số hệ thống 
Input: ,  - độ dài (tính theo bit) của các số nguyên tố , . 
Output: , , . 
Bước 1. Chọn cặp số ,  nguyên tố với: 
() = , () =  sao cho |( − 1) 
Bước 2. Chọn  là phần tử sinh của nhóm 
∗ theo: 
 = 

   , với  ∈ (1, ) 
Chú thích: (. ): hàm tính độ dài (theo bit) của một số. 
Mỗi thực thể cuối/người sử dụng trong hệ thống hình thành khóa của mình bằng 
thuật toán như sau: 
b) Thuật toán 2. Hình thành khóa 
Input: , , , ,  - độ dài (tính theo bit) của các số nguyên tố , . 
Output: , , , . 
Bước 1. Chọn cặp số ,  là các nguyên tố vớ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 59
() = , () =  
Bước 2. Tính  = . , nếu  ≤  thì thực hiện lại Bước 1. 
Bước 3. Tính () = ( − 1). ( − 1) 
Bước 4. Chọn giá trị bí mật thứ nhất  trong khoảng (1, ) 
Bước 5. Tính giá trị y theo: 
 = ()()

   (1) 
Kiểm tra nếu:  ≥ () hoặc: gcd (, ()) ≠ 1 thì thực hiện lại từ Bước 4. 
Bước 6. Tính giá trị bí mật thứ hai  theo: 
 = 
  () (2) 
Bước 7. Chọn hàm băm : {0,1}∗ →  với  < ℎ <  
Chú thích: 
- p, q, g: Tham số hệ thống (tham số miền). 
- x1, x2: Khóa bí mật. 
- y, n: Khóa công khai. 
3.2. Thuật toán ký 
a) Thuật toán 3: Sinh chữ ký 
Input: p, q , g, (), ,   - bản tin cần ký 
 Output: , - chữ ký 
Bước 1. Chọn ngẫu nhiên giá trị  trong khoảng (1, ) 
Bước 2. Tính giá trị: 
 =    (3) 
Bước 3. Tính thành phần thứ nhất  của chữ ký theo: 
 = (‖)   (4) 
Bước 4. Tính thành phần thứ hai  của chữ ký theo: 
 = ( × ( + )  )
   (5) 
Chú thích: toán tử "||": phép nối 2 xâu bit. 
b) Thuật toán 4: Kiểm tra chữ ký 
Input: p, q , g, y, n, y, M - bản tin cần thẩm tra. 
 Output: (, ) = / 
Bước 1. Tính giá trị: 
 = (()()
  × ())   (6) 
Bước 2. Tính giá trị: 
  =    (7) 
Công nghệ thông tin 
N. V. Thái, L. H. Dũng, “Một lược đồ chữ ký xây dựng trên tính khó  và phân tích số.” 60 
Bước 3. Nếu  =  thì (, ) = true; nếu  ≠  thì (, ) = false 
Chú thích: 
+ (, ) = true: chữ ký hợp lệ, bản tin M được xác thực về nguồn gốc và tính 
toàn vẹn. 
+ (, ) = false: chữ ký hoặc/và bản tin bị giả mạo. 
3.3. Tính đúng đắn của thuật toán mới đề xuất 
Điều cần chứng minh ở đây là: Cho p, q , ,  là các số nguyên tố thỏa mãn: 
|( − 1),  =  × ,  > , 1 <  < ,  = 

  , 
() = ( − 1) × ( − 1), 1 <  < ,  = 
()

  , 
 = ()
  (), 1 <  < (),  =   , 
: {0,1}∗ →  với  < ℎ < ,  = (‖)  , 
 = ( × ( + )  )
  . 
Nếu:  = ()()
  × ()   ,  = (‖)   thì  = . 
Chứng minh: 
Thật vậy, từ (1), (2), (3), (5) và (6) ta có: 
  = ()()
  × ()     
 = ()()

 
((.()  )
  )  
× ()    (8) 
 = ()()

 
.() 
× ()   
 = ()()
..()
× ()   
 = ()()
× ()   =    =  
Từ (4), (7) và (8) suy ra điều phải chứng minh: 
  = (‖)   = (‖)   =  
3.4. Mức độ an toàn của thuật toán mới đề xuất 
+ Tấn công khóa bí mật 
Ở thuật toán mới đề xuất, khóa bí mật là tích của cặp giá trị bí mật (, ), tính 
an toàn của lược đồ sẽ bị phá vỡ khi cặp giá trị này có thể tính được bởi một hay 
các đối tượng không mong muốn. Từ Thuật toán 1 và 2 cho thấy, để tìm được 
 theo (2) cần phải tính được tham số (), nghĩa là phải giải được (), còn 
để tính được  theo (1) cần phải giải được DLP(,). Chú ý rằng, để tính  và  
thì kẻ tấn công cần phải giải được (4). Như vậy, để tìm được cặp khóa bí mật này 
kẻ tấn công cần phải giải được bài toán () và DLP(,). Nói cách khác, độ an 
toàn về khóa của thuật toán được đảm bảo bằng độ khó của việc giải đồng thời 2 
bài toán () và DLP(,). 
+ Tấn công giả mạo chữ ký 
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 61
Từ điều kiện của Thuật toán 3, một cặp (, ) bất kỳ sẽ được coi là chữ ký hợp 
lệ của đối tượng sở hữu các tham số công khai (, ) lên bản tin M nếu thỏa mãn: 
 = (‖(() × ()  )  ) (9) 
Từ (9) dễ thấy rằng, nếu H(.) được chọn là hàm băm có tính kháng va chạm cao 
(SHA 256/512,...) thì việc tạo ngẫu nhiên được cặp (, ) thỏa mãn điều kiện của 
thuật toán kiểm tra là không khả thi trong các ứng dụng thực tế. 
4. VÍ DỤ 
a) Sinh tham số và khóa (Thuật toán 1) 
Input:  = 512 ,  = 160  . 
Output: p, q, g. 
 - Giá trị của : 
6858573634744140043864051060196712237037265262414147418846336002493917
70216806087892612458049447003300037760640716543717785944770214754537295604
2876888251 
- Giá trị của : 
1444125853144354424502004519548090639867409116997 
- Giá trị của : 
3497993977523090272943160771514751474419981070156148850534702931082372
53505790988846063652173362632743770735595978202181871488219496284748996457
0361083060 
b) Sinh tham số và khóa (Thuật toán 2) 
Input: , , ,  = 512 ,  = 512  . 
Output: , , , . 
- Giá trị của : 
7117013613810786406784266560984396928363531519896578037730893999461553
58827637950909852737949050747550785316108672123212667809081183861310965127
3978117011 
- Giá trị của : 
1334329757731294897401625580595445900545276917576694146992975210732330
77203724545701715845873549340068538458719610888573016173616470844401997450
51845491769 
- Giá trị của : 
9496443051086474210661085099332286031499892570755668623556339140829830
67857255444633271373994095701666145877674939894089690303568644414305945512
45477646353048055518808855111677947695365926531411430169792686305328172810
77258448295744503914580919743972488076409470800668743109784502677096844185
5024379919382459 
- Giá trị của : 
1251548569695557205558738755380301729107167948542 
- Giá trị của : 
2070674479402476292663411626561047511804694262936235504384953725137336
64749422286934000414725802220904361550868131157437337076902047181778561665
6853358639 
- Giá trị của : 
Công nghệ thông tin 
N. V. Thái, L. H. Dũng, “Một lược đồ chữ ký xây dựng trên tính khó  và phân tích số.” 62 
7084594550467275179564825937655456519597843612096402022737348480403951
06713029728945831538264951046555207726417829261440149777182252053924379384
18383741571836103986780074090265630227377458627089439216002525154665295549
96624335302391847286787951325315556174550371818709966190513611023804670687
2101153968183999 
c) Sinh chữ ký (Thuật toán 3) 
Input: p, q , g, n, , ,  
 Output: ,  
- M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
- Giá trị của k: 
1169201076494603411307255601541973824292894850079 
- Giá trị của R tính được: 
5054068794150077099617350666961421672507933164624429930219452280818704
12498455503011748256774799384029100954833672799686782817963045293593781022
3496441786 
- Giá trị của E tính được: 
627576451934184254727264502918899024375785781807 
- Giá trị của S tính được: 
3253259338151369568744793552444228814714137618496059246175229799981389
03878515475775960657880732167452158278405817354321802165708789187563969708
00396426231562976547352301617131307106384994313040974512175645789343779805
71673000456643405285871045118267681702714137327479298344759845004407361054
0621904481369519 
d) Kiểm tra chữ ký (Thuật toán 4) 
Input: p, q, g, n, y, M, (E,S) 
+ Trường hợp 1: 
- Bản tin cần kiểm tra: 
M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
- Giá trị của  cần kiểm tra: 
627576451934184254727264502918899024375785781807 
- Giá trị của  cần kiểm tra: 
3253259338151369568744793552444228814714137618496059246175229799981389
03878515475775960657880732167452158278405817354321802165708789187563969708
00396426231562976547352301617131307106384994313040974512175645789343779805
71673000456643405285871045118267681702714137327479298344759845004407361054
0621904481369519 
- Giá trị của  tính được: 
5054068794150077099617350666961421672507933164624429930219452280818704
12498455503011748256774799384029100954833672799686782817963045293593781022
3496441786 
- Giá trị của  tính được: 
627576451934184254727264502918899024375785781807 
Output: (E,S) = true. 
+ Trường hợp 2: Bản tin bị giả mạo. 
- Bản tin cần kiểm tra: 
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 63
M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM ” 
- Giá trị của  cần kiểm tra: 
627576451934184254727264502918899024375785781807 
- Giá trị của  cần kiểm tra: 
8021657087891875639697080039642623156297654735230161713130710638499431
30409745121756457893437798057167300045664340528587104511826768170271413732
74792983447598450044073610540621904481369519 
- Giá trị của  tính được: 
5054068794150077099617350666961421672507933164624429930219452280818704
12498455503011748256774799384029100954833672799686782817963045293593781022
3496441786 
- Giá trị của  tính được: 
950375168932516035853278712792326895469172097430 
Output: (E,S) = false. 
+ Trường hợp 3: Thành phần S của chữ ký bị giả mạo. 
- Bản tin cần kiểm tra: 
M = “THIS IS A NEW DIGITAL SIGNATURE ALGRITHM !” 
- Giá trị của  cần kiểm tra: 
627576451934184254727264502918899024375785781807 
- Giá trị của  cần kiểm tra: 
8021657087891875639697080039642623156297654735230161713130710638499431
30409745121756457893437798057167300045664340528587104511826768170271413732
74792983447598450044073610540621904481369510 
- Giá trị của  tính được: 
5054068794150077099617350666961421672507933164624429930219452280818704
12498455503011748256774799384029100954833672799686782817963045293593781022
3496441786 
- Giá trị của  tính được: 
950375168932516035853278712792326895469172097430 
Output: (E,S) = false. 
5. KẾT LUẬN 
Bài báo đề xuất xây dựng một lược đồ chữ ký có độ an toàn được đảm bảo bằng 
mức độ khó của việc giải đồng thời 2 bài toán: bài toán phân tích một số nguyên 
lớn ra các thừa số nguyên tố và bài toán logarit rời rạc. Có thể khẳng định rằng 
không có bất kỳ kiểu tấn công nào vào lược đồ thành công được mà không phải 
giải được đồng thời 2 bài toán khó nêu trên, do đó lược đồ mới đề xuất có thể phù 
hợp với các ứng dụng yêu cầu cao về độ an toàn 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. 
Công nghệ thông tin 
N. V. Thái, L. H. Dũng, “Một lược đồ chữ ký xây dựng trên tính khó  và phân tích số.” 64 
[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]. National Institute of Standards and Technology, NIST FIPS PUB 186-4. Digital 
Signature Standard, U.S. Department of Commerce, 2013. 
[10]. R. L. Rivest, A. Shamir, and L. M. Adleman, “A Method for Obtaining Digital 
Signatures and Public Key Cryptosystems”, Commun. of the ACM, Vol. 21, No. 2, 
1978, pp. 120-126. 
[11]. 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. 
ABSTRACT 
A NEW DIGITAL SIGNATURE SCHEME BASED ON FACTORING 
AND DISCRETE LOGARITHMS 
The paper proposes a digital signature scheme based on the difficulty of 
simultaneous solving two discrete logarithm problems with integer factoring 
problems. Therefore, the new signature algorithm proposed here can meet 
applications with high security demands on actual security. 
Keywords: Digital Signature Algorithm; Public - Key Cryptography Algorithm; Public - Key CryptoSystem; 
Discrete Logarithm Problem; Integer Factoring Problems. 
Nhận bài ngày 21 tháng 12 năm 2018 
Hoàn thiện ngày 12 tháng 3 năm 2019 
Chấp nhận đăng ngày 25 tháng 3 năm 2019 
Địa chỉ: 1Viện CNTT, Viện KH và CNQS; 
 2 Khoa CNTT, Học viện KTQS. 
 * Email: luuhongdung@gmail.com.