Phương pháp xây dựng thuật toán chữ ký số dựa trên một dạng bài toán khó mới

M ,Z , y , y )]mod q
 2 3 1 2 
 (1.8) 
 3 
 Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
Bảng 1.1 . Thu ật toán sinh khóa 
 [9]. v ← (u × w4 + x2 × w5 )mod q 
 Input : p – s ố nguyên t ố, lq – độ dài (tính theo u
 [10]. r ← (x1 ) mod p 
 bit) c ủa s ố nguyên t ố q. 
 v
 [11]. s ← (x1 ) mod p 
 Output : q, x1, x 2, y1,y 2. 
 [12]. return ( r,s) 
 [1]. generate q: len(q) = lq, q|(p-1) 
 : 
 [2]. select α: 1 < α < p Chú thích
 (i) M: b ản tin c ần ký, v ới: M ∈ }1,0{ ∞ . 
 ( p−1) / q
 [3]. x1 ← α mod p 
 (ii) (r,s): ch ữ ký c ủa U lên M. 
 [4]. if (x1 = 1) then goto [2] 
 [5]. select x2: 1 < x2 < q Bảng 1.3. Thu ật toán ki ểm tra ch ữ ký 
 x
 [6]. ← x2 , ← 1 
 y1 (x1) mod p y2 (x2 ) mod p Input : p, y1, y2, M, (r,s ). 
 (2.1) Output : true / false . 
 [7]. return {q, x 1, x 2, y1, y 2} 
 [1]. Z ← f(,) r s 
Chú thích : 
 [2]. w ← f (,,,)M Z y y 
 - len(.) là hàm tính độ dài (theo bit) c ủa một 1 1 1 2
 [3]. 
 số nguyên. w2 ← f2 (,,,)M Z y1 y 2
 [4]. 
 - q, x 1, x 2: Khóa bí m ật. w3 ← f3 (,,,)M Z y1 y 2
 - y1, y2: Khóa công khai c ủa đối t ượng ký. [5]. A ← (s)w1 mod p 
 [6]. B ← (r)w2 × (y )w3 mod p 
Bảng 1.2. Thu ật toán ký 1
 [7]. if ( A = B ) then { return true } 
 Input : p, q, x1, x 2, y1, y2, M. 
 Output : (r,s). else { return false } 
 [1]. select k: 1 < k < q Chú thích : 
 - M, (r,s): b ản tin, ch ữ ký c ần th ẩm tra. 
 [2]. Z ← (x )k mod p 
 1 - Nếu k ết qu ả tr ả v ề là true thì tính toàn v ẹn và 
 [3]. w1 ← f1(M ,,,Z y1y 2 ) 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à 
 [4]. w2 ← f2 (,,,)M Z y1 y 2 
 tính toàn v ẹn. 
 [5]. 
 w3 ← f3 (,,,)M Z y1 y 2
 2) Một số thu ật toán ch ữ ký xây d ựng theo 
 −1
 [6]. w4 ← (w1 ) × w2 mod q phươ ng pháp mới đề xu ất 
 −1 
 [7]. w5 ← (w1 ) × w3 mod q a) Thu ật toán MTA 18.9 –01 
 −1 Thu ật toán ch ữ ký th ứ nh ất đề xu ất ở đây – ký 
 [8]. u ← (w4 +1) × (k − x2 × w5 )mod q 
 hi ệu: MTA 18.9 – 01 , được xây d ựng theo các 
 4 
 Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
Bảng 1.1, 1.2 và 1.3 ở mục A v ới l ựa ch ọn các hàm 
nh ư sau: + Tính đúng đắn c ủa thu ật toán được đề xu ất 
 , , 
 f1(,,,)M Z y1 y 2 = H(M ) f2 (,,,)M Z y1 y 2 = y2 Điều c ần ch ứng minh ở đây là: Cho p, q là 2 số 
 . ∗
f3 (,,,)M Z y1 y 2 = Z a
 nguyên t ố v ới q|( p-1), H :{} 0,1 Z n , q < n < p , 
 Khi đó, các thu ật toán ký và ki ểm tra ch ữ ký ( p−1) / q
 1 < α < p , x1 = α mod p , 1 < k, x2 < q , 
của thu ật toán được mô t ả trong các B ảng 2.1 và 
 x
 y = (x )x2 mod p , y = (x ) 1 mod p , E = H(M ) , 
Bảng 2.2 d ưới đây: 1 1 2 2
 = k , 
 Bảng 2.1 . Thu ật toán k ý Z (x1 ) mod p
 −1 −1 −1 , 
 Input : p, q, x1, x 2, y2, M . u = (y2 × E + 1) × (k − x2 × Z × E )mod q
 −1 u
 Output : (r,s). v = E × (u × y2 + x2 × Z )mod q , r = (x1 ) mod p , 
 v . N ếu: , E , 
 [1]. E ← H()M s = (x1 ) mod p Z =r × smod p A = (s) mod p
 B = (r)y2 × (y )Z mod p thì: A = B . 
 [2]. select k: 1 < k < p −1 1
 Tính đúng đắn c ủa thu ật toán mới đề xu ất 
 [3]. Z ← (x )k mod p (2.2) 
 1 được ch ứng minh nh ư sau: 
 −
 [4]. ← × −1 + 1 × − × × −1 (2.3) 
 u (y2 E 1) (k x2 Z E )mod q Từ (2.2), (2.3), (2.4) và (2.6) ta có: 
 E v. E
 [5]. −1 (2.4) A = ( s ) mod p = ( x ) mod p =
 v ← E × (u× y2 + x2 × Z )mod q 1
 −1 (2.9) 
 ()()u. y2+ x 2 ... Z E E
 = ()x1 mod p
 [6]. r ← (x )u mod p (2.5) 
 1 u. y2+ x 2 . Z
 = ()x1 mod p
 [7]. v (2.6) 
 s ← (x1 ) mod p Với: 
 −1 −1 −1 
 [8]. return ( r,s) u = (y2 × E +1) × (k − x2 × Z × E )mod q
 Từ (2.3), (2.4), (2.5) và (2.6) ta có: 
 Z =r × s mod p = (x )u × (x )v mod p
 Bảng 2.2 . Thu ật toán ki ểm tra 1 1
 u+ v
 = ()x1 mod p
 −1 −1 −1 −1
 Input : p, y1, y2, M, (r,s). ()()y2 . E + 1 .k− x2 . Z . E E...() u y2+ x 2 Z
 = ()x1 × ()x1 mod p
 −1 −1 −1
 ()()y2 . E .+ 1 .k− x2 . Z . E (2.10) 
 Output : true / false . = ()x1 ×
 −  − −1 − 
 E1. ()() y . E 1+ 1 .k− x . Z . E1 . y+ x . Z 
  2 2 2 2 
 × ()x1 mod p
 [1]. E ← H(M ) −1 −1 −1 −1 −1
 k.() y2 . E + 1 −x2 . Z . E .() y2 . E + 1
 = ()x1 × ()x1
 −1 −1 −1 −1 −1 −1 −1
 E E.() y2 . E + 1 .k . y2 −E.() y2 . E + 1 .x2 . Z . E . y2
 [2]. A ← (s) mod p × ()x1 × ()x1
 −1
 E−1.. x Z k.()() y . E −1 + 1 .y . E−1+ 1
 × ()()x 2 mod p = x 2 2
 [3]. ← × (2.7) 1 1
 Z r s mod p −1 −1 −1 −1 −1
 −x2 . Z . E .()() y2 . E + 1 .y2 . E + 1 E.. x2 Z
 × ()x1 × ()x1 mod p
 y Z k −x.. Z E −1 E−1.. x Z
 2 2 2
 [4]. B ← (r) × (y1 ) mod p (2.8) = ()()() x 1 × x 1 × x 1 mod p
 k
 = ()x1 mod p = Z
 [5]. if ( A = B ) then { return true } 
 Thay (2.1), (2.3), (2.5), (2.7) và (2.10) vào (2.8) 
 else return
 { false } ta l ại có: 
 5 
 Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
 y2 Z được công nh ận là ch ữ ký h ợp l ệ v ới m ột b ản tin M 
 w1 = (r) ×(y1 ) mod p =
 (2.11) 
 u. y2 x2 . Z
 = ()()x1 × x1 mod p nếu th ỏa mãn điều ki ện: 
 u. y+ x. Z
 2 2 E y (r . s ) mod p
 = ()x1 mod p 2
 (s) ≡ (r) ×(y1 ) mod p (2.12) 
 Với: Từ (2.12), n ếu ch ọn tr ước r r ồi tính s thì khi đó 
 −1 −1 −1
 u = (y2 × E + 1) × (k − x2 × Z × E )mod q điều ki ện (2.12) s ẽ có d ạng: 
 Từ (2.9) và (2.11) suy ra điều c ần ch ứng minh: (s)E ≡ a(s. r) mod p mod p (2.13) 
 A = B Còn n ếu ch ọn tr ước s r ồi tính r thì khi đó điều 
+ Mức độ an toàn c ủa thu ật toán được đề xu ất ki ện (2.12) s ẽ tr ở thành: 
 y (r. s) mod p
 Mức độ an toàn c ủa lược đồ m ới đề xu ất có th ể (r) 2 ≡ (b) mod p (2.14) 
đánh giá qua kh ả n ăng nh ư: Với a, b là h ằng s ố, dễ th ấy r ằng vi ệc gi ải 
 - Chống t ấn công khóa bí m ật (2.13) và (2.14) là khó tươ ng đươ ng v ới DLRP. 
 b) Thu ật toán MTA 18.9 – 02 
 Ở thu ật toán m ới đề xu ất, cặp tham s ố x1, x 2 
cùng được s ử d ụng làm khóa bí m ật để hình thành Thu ật toán ch ữ ký th ứ hai đề xu ất ở đây – ký 
 hi ệu: MTA 18.9 – 02, cũng được xây d ựng theo 
ch ữ k ý. Vì th ế, thu ật toán ch ỉ b ị phá v ỡ n ếu c ả 2 
 ph ươ ng pháp t ươ ng t ự MTA 18.9 – 01 v ới m ột s ố 
tham s ố này cùng b ị l ộ, nói cách khác là k ẻ t ấn công 
 thay đổi nh ư sau: 
ph ải gi ải được bài toán logarit r ời r ạc k ết h ợp khai 
 Các giá tr ị: x1, x2, y2 được s ử d ụng làm khóa bí 
căn trên Zp. Do đó, m ức độ an toàn c ủa thu ật toán 
 mật c ủa đối t ượng ký, khóa công khai được tính 
mới đề xu ất xét theo kh ả n ăng ch ống t ấn công làm 
 theo: 
lộ khóa m ật được đánh giá b ằng m ức độ khó c ủa 
 y = (y )y2 mod p (3.1) 
vi ệc gi ải được DLRP. C ần chú ý, DLRP là m ột 1
dạng bài toán khó m ới, mà ngay c ả khi có các gi ải Và đẳng th ức ki ểm tra được gi ả thi ết là: 
 E y Z
thu ật th ời gian đa th ức cho FRP và DLP c ũng không (s) ≡ (r) × (y) mod p 
có ngh ĩa là s ẽ gi ải được bài toán này. Ngoài ra, Khi đó, các thu ật toán ký và ki ểm tra ch ữ ký 
tham s ố q c ũng được s ử d ụng v ới vai trò khóa bí của thu ật toán được mô t ả trong các B ảng 3.1 và 
mật trong thu ật toán ký. Nh ư v ậy, để phá v ỡ tính an Bảng 3.2 d ưới đây: 
toàn c ủa thu ật toán, k ẻ tấn công còn ph ải gi ải được Bảng 3.1 . Thu ật toán k ý 
bài toán tìm b ậc c ủa x . Tuy nhiên, vi ệc tìm b ậc c ủa 
 1 Input : p, q, x 1, x 2, y2, y, M . 
x là không th ể th ực hi ện được, vì x ở đây là 1 tham 
 1 1 Output : (r,s). 
số bí m ật. 
 [1]. E ← H()M 
 - Chống gi ả m ạo ch ữ ký 
 [2]. select k: 1 < k < p −1 
 Từ thu ật toán ki ểm tra (B ảng 2.2) c ủa thu ật 
 [3]. Z ← (x )k mod p (3.2) 
toán mới đề xu ất cho th ấy, m ột c ặp (r,s) gi ả m ạo s ẽ 1
 [4]. −1 −1 −1 
 u ← (y × E + 1) × (k − x2 × y2 × Z × E )mod q
 6 
 Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
 (3.3) − 1 , u , 
 v = E × (u × y + x2 × y2 × Z )mod q r = (x1 ) mod p
 [5]. −1 (3.4) v . N ế u: , E , 
 v ← E × (u × y + x2 × y2 × Z )mod q s = (x1 ) mod p Z =r × smod p A = (s) mod p
 u B = (r)y × (y)Z mod p thì: A = B . 
 [6]. r ← (x1 ) mod p (3.5) 
 Tính đúng đắn c ủa thu ật toán mới đề xu ất 
 [7]. v (3.6) 
 s ← (x1 ) mod p
 được ch ứng minh nh ư sau: 
 [8]. return (r,s) 
 Từ (3.2), (3.3), (3.4) và (3.6) ta có: 
 E v. E
 A = (s) mod p = (x1 ) mod p =
 ()()+ −1
 Bảng 3.2 . Thu ật toán ki ểm tra u..... y x2 y 2 Z E E (3.9) 
 = ()x1 mod p
 u... y+ x2 y 2 Z
 Input : p, y, M, (r,s). = ()x1 mod p
 Output : true / false . Với: 
 −1
 u = (y × E −1 + 1) × (k − x × y × Z × E −1 )mod q 
 [1]. E ← H(M ) 2 2
 Từ (3.3), (3.4), (3.5) và (3.6) ta có: 
 E
 [2]. A ← (s) mod p u v
 Z =r × s mod p = (x1 ) × (x1 ) mod p
 = ()x u+ v mod p
 [3]. Z ← r× s mod p (3.7) 1 
 −1 −1 −1
 ()()y. E + 1 .k− x2 . y 2 . Z . E
 = ()x1 ×
 y Z E−1....() u y+ x y Z
 [4]. B ← (r) × (y) mod p (3.8) 2 2 
 × ()x1 mod p
 −1
 ()()y. E .−1+ 1 .k− x . y . Z . E −1
 = ()x 2 2 ×
 [5]. if ( A = B ) then {return true } 1
 −  − −1 − 
 E1. ()() y . E 1+ 1 .k− x . y . Z . E1 . y+ x . y . Z 
  2 2 2 2 
 × ()x1 mod p
 else { return false } −1 −1 −1 − 1 −1
 k.() y . E + 1 −x2. y 2 . Z . E .() y . E + 1
 = ()x1 × ()x1
 −1 − 1 −1 −1 − 1 −1 −1
 E.() y . E + 1 .k . y −E.() y . E + 1 .x2 . y 2 . Z . E . y
 × ()x1 × ()x1
 −1 −1 −1 −1
 E... x2 y 2 Z k.()() y . E + 1 .y . E + 1
 Nh ận xét : × ()()x1 mod p = x1
 −1
 −x. y . Z . E−1 .()() y . E − 1+ 1 .y . E−1+ 1 E−1... x y Z
 × 2 2 × 2 2
 Từ vi ệc xây d ựng các thu ật toán MTA 18.9 – 01 ()x1 ()x1 mod p
 k −x... y Z E−1 E−1... x y Z
 = ()()()x × x 2 2 × x 2 2 mod p
và MTA 18.9 – 02 cho th ấy ph ươ ng pháp m ới đề xu ất 1 1 1
 = ()x k mod p = Z (3.10) 
ở đây có th ể t ạo ra các thu ật toán ch ữ ký với nhi ều 1
 Thay (3.1), (3.3), (3.5), (3.7) và (3.10) vào (3.8) 
khóa bí m ật và 1 ho ặc 2 khóa công khai là hoàn toàn 
 ta l ại có: 
tùy thu ộc vào ý định thi ết k ế. 
 y Z
 w1 = (r) × (y) mod p =
+ Tính đúng đắn c ủa thu ật toán được đề xu ất (3.11) 
 u. y x2.. y 2 Z
 = ()()x1 × x1 mod p
 Điều c ần ch ứng minh ở đây là: Cho p, q là 2 số u... y+ x2 y 2 Z
 = ()x1 mod p
 ∗ a
nguyên t ố v ới q|( p-1), H :{} 0,1 Z n , q < n < p , Với: 
 ( p−1) / q −1 −1 −1 
1 < α < p , x1 = α mod p , 1 < k, x2 < q , u = (y × E +1) × (k − x2 × y2 × Z × E )mod q
 x
 x2 1 y2 Từ (3.9) và (3.11) suy ra điều c ần ch ứng minh: 
y1 = (x1 ) mod p , y2 = (x2 ) mod p , y = (y1 ) mod p , 
 k A = B 
E = H(M ) , Z = (x1 ) mod p , 
 + Mức độ an toàn c ủa thu ật toán được đề xu ất 
 −1 −1 −1
u = (y × E + 1) × (k − x2 × y2 × Z × E )mod q , 
 Mức độ an toàn c ủa lược đồ m ới đề xu ất có th ể 
 7 
 Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
đánh giá qua kh ả n ăng nh ư: 
 - Chống t ấn công khóa bí m ật TÀI LI ỆU THAM KH ẢO 
 [1] Lưu H ồng D ũng, Nguy ễn Đức Th ụy, Nguy ễn V ăn Phúc và 
 Tươ ng t ự MTA 18.9 – 01, mức độ an toàn c ủa Đỗ Anh Tu ấn, “Một ph ươ ng pháp xây d ựng thu ật toán ch ữ 
 ký s ố”, H ội th ảo l ần th ứ I: M ột s ố v ấn đề ch ọn l ọc v ề an 
thu ật toán m ới đề xu ất xét theo kh ả n ăng ch ống t ấn toàn, an ninh thông tin (SoIS 2016), 11/2016. 
 [2] Nguyen Duc Thuy and Luu Hong Dung, “A New 
công làm l ộ khóa m ật cũng được đánh giá b ằng m ức Construction Method of Digital Signature Algorithms”, 
 IJCSNS International Journal of Computer Science and 
độ khó c ủa vi ệc gi ải được bài toán DLRP. Network Security. Vol. 16 No. 12 pp. 53-57, December 
 2016. ISSN: 1738 - 7906. 
 - Chống gi ả m ạo ch ữ ký [3] 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 
 Từ thu ật toán ki ểm tra (B ảng 3.2) c ủa thu ật Telecommunications , vol. 24, pp. 61-65, January 2001. 
toán mới đề xu ất cho th ấy, một c ặp (r,s) gi ả m ạo s ẽ [4] Z. Y. Shen and X. Y. Yu, "Digital signature scheme based 
 on discrete logarithms and factoring", Information 
được công nh ận là ch ữ ký h ợp l ệ v ới m ột b ản tin M Technology , vol. 28,pp. 21-22, June 2004. 
 [5] Shimin Wei, “Digital Signature Scheme Based on Two 
nếu th ỏa mãn điều ki ện: Hard Problems”, IJCSNS International Journal of 
 Computer Science and Network Security , VOL.7 No.12, 
 (s)E ≡ (r)y ×(y)(r . s ) mod p mod p (3.12) December 2007. 
 [6] Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A 
 Từ (3.12), n ếu ch ọn tr ước r r ồi tính s thì khi đó New Digital Signature Scheme Based on Factoring and 
 Discrete Logarithms”, Journal of Mathematics and 
điều ki ện (3.12) s ẽ có d ạng: Statistics, 04/2008; 12(3). DOI: 
 10.3844/jmssp.2008.222.225 Source:DOAJ. 
 E (s. r) mod p
 (s) ≡ a mod p (3.13) [7] Qin Yanlin , Wu Xiaoping,“ New Digital Signature Scheme 
 Based on both ECDLP and IFP”, Computer Science and 
 Còn n ếu ch ọn tr ước s r ồi tính r thì khi đó điều Information Technology, 2009. ICCSIT 2009. 2nd IEEE 
 International Conference on , 8-11 Aug. 2009, E-ISBN : 
ki ện (3.12) s ẽ tr ở thành: 978-1-4244-4520-2, pp 348 - 351. 
 y (r. s) mod p [8] Swati Verma1, Birendra Kumar Sharma, “A New Digital 
 (r) ≡ (b) mod p (3.14) Signature Scheme Based on Two Hard Problems”, 
 International Journal of Pure and Applied Sciences and 
 Với a, b là h ằng s ố, cũng dễ th ấy r ằng vi ệc gi ải Technology , ISSN 2229 – 6107, Int. J. Pure Appl. Sci. 
 Technol., 5(2) (2011), pp. 55-59. 
(3.13) và (3.14) là khó tươ ng đươ ng v ới bài toán 
 [9] Sushila Vishnoi , Vishal Shrivastava, ”A new Digital 
DLRP. Signature Algorithm based on Factorization and Discrete 
 Logarithm problem”, International Journal of Computer 
 Trends and Technology , volume 3, Issue 4, 2012. 
 III. KẾT LU ẬN [10] A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, 
 "Cryptoschemes Based on Difficulty of Simultaneous 
 Bài báo đề xu ất m ột ph ươ ng pháp xây d ựng thu ật Solving Two Different Difficult Problems", Computer 
 Science Journal of Moldova, vol.21, no.2(62), 2013. 
toán ch ữ k ý s ố m ới d ựa trên bài toán logarit r ời r ạc [11] T. ElGamal, “A public key cryptosystem and a signature 
 scheme based on discrete logarithms”, IEEE Transactions 
kết h ợp khai c ăn trên Zp. M ức độ an toàn c ủa các on Information Theory, Vol. IT-31, No. 4. pp.469–472. 
thu ật toán xây d ựng theo ph ươ ng pháp này s ẽ được [12] N.A. Moldovyan, "Digital Signature Scheme Based on a 
 New Hard Problem", Computer Science Journal of 
đảm b ảo b ằng m ức độ khó c ủa vi ệc gi ải bài toán Moldova, vol.16, no.2(47), 2008. 
trên. Ở đây, bài toán logarit r ời r ạc k ết h ợp khai c ăn 
trên tr ường Zp là m ột d ạng bài toán khó m ới, l ần đầu 
được đề xu ất và ứng dụng trong vi ệc xây d ựng thu ật 
toán ch ữ ký s ố. T ừ ph ươ ng pháp m ới đề 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 ế. 
 8 
Hội th ảo l ần th ứ III: M ột s ố v ấn đề ch ọn l ọc v ề an toàn an ninh thông tin – Đà N ẵng, 07/12/2018 
 9