Phát triển lược đồ chữ ký số mù

 −e x. x−1 .( k+ e )
làm l ộ khóa m ật c ủa l ược đồ cơ s ở phụ thu ộc vào m ức độ khó u = g × y mod p = g × g mod p (2.7b) 
gi ải c ủa bài toán logarit r ời r ạc, hoàn toàn t ươ ng t ự nh ư v ới = g e+ k − e mod p = g k mod p
các l ược đồ ch ữ ký DSA [9] , GOST R34.10-94 [10 ] và Từ (2.2b) và (2.7b), suy ra: u = r (2.8b) 
Schnorr [13 ]. Thay (2.8b) vào (2.6b) ta được: 
 Về kh ả n ăng ch ống t ấn công gi ả m ạo ch ữ ký : T ừ (2.3a), v = H( u || M )mod q = H( r || M )mod q (2.9b) 
(2.5a) và (2.6a) c ủa l ược đồ cơ s ở cho th ấy, một cặp ( e,s ) b ất Từ (2.3b) và (2.9b), suy ra: v = e 
kỳ (không được t ạo ra b ởi Thu ật toán ký 2.2a c ủa l ược đồ và Đây là điều c ần ch ứng minh. 
từ khóa bí m ật x c ủa ng ười ký) nh ưng v ẫn s ẽ được công nh ận e) M ức độ an toàn c ủa l ược đồ c ơ s ở LD 15.01B 
 ISBN: 978-604-67-0635-9 115 
 H ội Th ảo Qu ốc Gia 2015 v ề Điện t ử, Truy ền Thông và Công Ngh ệ Thông Tin (ECIT 2015) 
 Tươ ng t ự l ược đồ LD 15.01A, m ức độ an toàn xét theo , . N ếu: 
 sa = (k + x× eb )mod q s = (α × sa + β )mod q
kh ả n ăng ch ống t ấn công làm l ộ khóa m ật c ủa lược đồ LD-
 s e và thì: . 
15.01B ph ụ thu ộc vào m ức độ khó gi ải c ủa bài toán logarit r ời u = ()g × (y) mod p v = H( u || M )mod q v = e
rạc, còn kh ả n ăng ch ống t ấn công gi ả m ạo ch ữ ký ph ụ thu ộc Th ật v ậy, t ừ (3.4a), (3.5a), (3.6a) và (3.7a) ta có: 
vào độ khó c ủa vi ệc gi ải (2.10b): u = g s × ye mod p = g (.)(.)α sa + β × y α eb +β mod p
 −e s α .(k+ x . e )+β − x.(α . e + β )
 e = H(( g × y mod p) ||M )modq (2.10b) = g b × g b mod p (3.9a) 
3.2. Xây d ựng l ược đồ ch ữ k ý s ố mù = g k.α × g x.. eb α × g β × g − x.. eb α × g −x.β mod p
3.2.1. Lược đồ ch ữ ký s ố mù LD 15.02A k α − x β β
 Lược đồ ch ữ k ý s ố mù ở đây được phát tri ển t ừ l ược đồ = ()()g × g × g mod p
 α β β α β
cơ s ở LD 15.01A. Gi ả s ử A là ng ười ng ười k ý có khóa công = ()ra × y × g mod p = ()ra × (y× g) mod p
khai được hình thành theo Thu ật toán 2.1a c ủa l ược đồ c ơ s ở Từ (2.1a), (3.1a) và (3.9a) ta có: 
 ườ ạ ả đượ đ ậ −β −x β −k α
và B là ng i t o ra b n tin M c k ý. Khi ó, thu t toán ký u = g × (g ) × (g ) mod p (3.10a) 
và ki ểm tra ch ữ ký c ủa l ược đồ được ch ỉ ra nh ư sau: 
 = r α × g −β × y β mod p
a) Thu ật toán k ý ()a
 Thu ật toán 3.1a: Từ (3.2) và (3.10), suy ra: u = rb (3.11a) 
 Input : p, q, g, x, y, α, β, k , M. Thay (3.11a) vào (3.8a) ta có: 
 Output : (e,s). 
 v = H( u || M )mod q = H( rb || M ) mod q (3.12a) 
 [1]. r g k mod p (3.1a) 
 a ← Từ (3.2a) và (3.12a), suy ra: v = e . Đây là điều c ần ch ứng 
 [2]. α β (3.2a) 
 rb ← (ra ) × (y× g) mod p minh. 
 [3]. e ← H( r ||M )modq (3.3a) d) Mức độ an toàn c ủa l ược đồ LD 15.02A 
 b Tươ ng t ự nh ư v ới l ược đồ c ơ s ở, m ức độ an toàn c ủa l ược 
 [4]. −1 (3.4a) 
 eb ← α ×(e − β )mod q đồ ch ữ ký mù mới đề xu ất cũng được đánh giá qua các kh ả 
 [5]. (3.5a) 
 sa ← (k + x× eb )mod q năng: 
 - Ch ống t ấn công làm l ộ khóa m ật. 
 [6]. s ← (α × s + β )mod q (3.6a) 
 a - Ch ống gi ả m ạo ch ữ ký. 
 [7]. return (e,s) 
 Ngoài ra, v ới m ột l ược đồ ch ữ ký số mù, m ức độ an toàn 
 Chú thích : của nó còn được đánh giá qua kh ả n ăng ch ống t ấn công làm l ộ 
 - Các b ước [1], [5] do ng ười ký A th ực hi ện. ngu ồn g ốc b ản tin sau khi được ký. Yêu c ầu đặt ra đối v ới 
 - Các b ước [2], [3], [4], [6] và [7] do ng ười có b ản tin lược đồ mới đề xu ất là b ản tin M sau khi đã được ký, thì ng ười 
 cần k ý B th ực hi ện. ký A hay b ất k ỳ m ột đối t ượng s ử d ụng nào khác c ũng hoàn 
 - Tham s ố k do A l ựa ch ọn th ỏa mãn: 1< k < q. toàn không th ể bi ết được b ản tin M được t ạo ra t ừ đối t ượng 
 - Tham s ố α, β do B lựa ch ọn th ỏa mãn: 1 < α, β < q. B. 
 - {x,y} là c ặp khóa bí m ật/công khai c ủa A. Kh ả n ăng ch ống t ấn công làm l ộ khóa m ật và gi ả m ạo ch ữ 
b) Thu ật toán ki ểm tra ký 
 Thu ật toán 3.2a: Mức độ an toàn c ủa l ược đồ ch ữ ký mù mới đề xu ất được 
 Input : p, q, g, y, M – b ản tin c ần th ẩm tra, (e,s) – ch ữ thi ết l ập d ựa trên m ức độ an toàn c ủa l ược đồ c ơ s ở . Xét theo 
 ký c ủa A. kh ả n ăng ch ống t ấn công làm l ộ khóa m ật và kh ả n ăng ch ống 
 Output : (e,s) = true / false . gi ả m ạo ch ữ ký, có th ể th ấy r ằng m ức độ an toàn c ủa 2 l ược 
 đồ này là t ươ ng đươ ng nh ư nhau. 
 [1]. s e (3.7a) 
 u ← g × y mod p Kh ả n ăng ch ống t ấn công làm l ộ ngu ồn g ốc c ủa b ản tin 
 [2]. v ← H( u || M )mod q (3.8a) được ký 
 [3]. if ( v = e ) then { return true } Thu ật toán k ý c ủa l ược đồ mới đề xu ất cho th ấy, n ếu ở m ỗi 
 else { return false } lần ký b ằng vi ệc l ưu tr ữ các tham s ố {s a,r a,e b,k} cùng v ới định 
 Chú thích : danh c ủa ng ười yêu c ầu k ý (ID B), ng ười k ý A có th ể xác định 
 - N ếu k ết qu ả tr ả v ề true thì tính h ợp l ệ c ủa ch ữ ký (e,s) được m ối quan h ệ gi ữa {M,(e,s)} v ới ID B, ngh ĩa là t ừ b ản tin 
được công nh ận, do đó tính toàn v ẹn c ủa b ản tin c ần th ẩm tra M và ch ữ k ý t ươ ng ứng ( e,s ) có thể xác định được danh tính 
M và danh tính c ủa ng ười ký (A) được kh ẳng định. của ng ười yêu c ầu k ý B, v ới điều ki ện ng ười k ý A bi ết được 
 - N ếu k ết qu ả tr ả v ề là false thì ch ữ ký (e,s) là gi ả m ạo, ho ặc các tham s ố ( α,β). Th ật v ậy, khi bi ết ( α,β) ng ười k ý A hoàn 
nội dung b ản tin M đã b ị s ửa đổi. toàn có th ể xác định được ID B b ằng Thu ật toán 3.3a nh ư sau: 
c) Tính đúng đắn c ủa l ược đồ LD 15.02A Thu ật toán 3.3a: 
 Điều c ần ch ứng minh ở đây là: cho p, q là 2 s ố nguyên t ố Input : {(rai ,e bi ,s ai ,k i,ID Bi )| i=0,1,2,N}, M, (e,s), α, β. 
th ỏa mãn điều ki ện q (| p − )1 , g = h(p− 1) / q mod p v ới: Output : ID Bi . 
 [1]. m ← H ()M , i = 0 
 ∗ a
1< h < p , H :{} 0,1 Z q , 1 < x, k < q , 1 < α, β < q , 
 [2]. select : (,,,,rai e bi s aik i IDBi ) 
 − x , k , α β , 
 y = g mod p ra = g mod p rb = (ra ) ×(y × g) mod p α β
 [3]. rbi * ← (rai ) × (g× y) mod p 
 , −1 , 
e = H( rb ||M ) mod q eb = α × (e − β )mod q
 ISBN: 978-604-67-0635-9 116 
 H ội Th ảo Qu ốc Gia 2015 v ề Điện t ử, Truy ền Thông và Công Ngh ệ Thông Tin (ECIT 2015) 
 [4]. ∗ [3]. (3.3b) 
 e ← H( rbi *||M )modq e ← H( rb ||M ) mod q
 ∗ [4]. −1 (3.4b) 
 [5]. if e ≠ e then eb ← α × (e + β ) mod q
 [5]. (3.5b) 
 [5.1]. i ← i +1; sa ← x × (k + eb )mod q
 [5.2]. goto [2]; [6]. s ← α × (sa + β )mod q (3.6b) 
 [6]. ∗ −1 
 ebi ← α × (e − β ) mod q [7]. return (e,s) 
 ∗ Chú thích
 [7]. if e ≠ e then : 
 bi bi - Các b ước [1], [5] do ng ười ký A th ực hi ện. 
 [7.1]. i ← i +1; - Các b ước [2], [3], [4], [6] và [7] do ng ười có b ản tin c ần k ý 
 [7.2]. goto [2]; B th ực hi ện. 
 [8]. ∗ 
 sai ← (ki +x × ebi )mod q - 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. 
 [9]. if s ≠ s then 
 ai ai - {x,y} là c ặp khóa bí m ật/công khai c ủa A. 
 [9.1]. i ← i +1; b). Thu ật toán ki ểm tra 
 [9.2]. goto [2]; 
 ∗ Thu t toán 3.2b
 [10]. s ← (α × s + β )mod q ậ : 
 ai Input
 ∗ : p, q, g, y, M – b ản tin c ần th ẩm tra, (e,s) – 
 [11]. if s ≠ s then ch ữ ký c ủa A. 
 [11.1]. i ← i +1 ; Output : (e,s) = true / false . 
 [11.2]. goto [2]; [1]. u ← g −e × y s mod p (3.7b) 
 [12]. return ID Bi 
 [2]. v ← H( u || M )mod q (3.8b) 
 Nh ận xét : 
 [3]. if ( v = e ) then { return true } 
 Thu ật toán 3.3a có th ể xác định được danh tính c ủa ng ười 
 else { return false } 
yêu c ầu ký B n ếu bi ết được các tham s ố bí m ật ( α,β) do B t ạo 
ra. Nói cách khác, m ức độ an toàn c ủa l ược đồ mới đề xu ất xét Chú thích : 
theo kh ả n ăng gi ữ bí m ật ngu ồn g ốc c ủa b ản tin ph ụ thu ộc vào - Nếu k ết qu ả tr ả v ề true thì tính h ợp l ệ c ủa ch ữ ký (e,s) 
mức độ khó c ủa vi ệc tìm được các tham s ố bí m ật ( α,β). T ừ được công nh ận, do đó tính toàn v ẹn c ủa b ản tin c ần 
thu ật toán ký c ủa l ược đồ mới đề xu ất cho th ấy t ại th ời điểm th ẩm tra M và danh tính c ủa ng ười ký (A) được kh ẳng 
 định. 
ký A ch ỉ bi ết được các tham s ố r a, e b, s a. Điều đó có ngh ĩa là 
để tính được ( α,β), A c ần ph ải gi ải (3.13a): - 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. 
 −1 α β 
 eb = α ×(H (( ra ) ×(g× y) mod p || M) modq − β) modq c) Tính đúng đắn c ủa l ược đồ LD 15.02B 
 (3.13a) Đ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 q p , g = h(p− 1) / q mod p v ới: 1 < h < p , 
 Tuy nhiên, từ các k ết qu ả nghiên c ứu đã được công b ố có (| − )1
 ∗ a
th ể th ấy r ằng (3.13a) là m ột d ạng bài toán khó ch ưa có l ời gi ải H :{ 0,1} Zt với: q< t< p , 1 < x, k < q , 1 < α, β < q , 
 −1
nếu các tham s ố p, q được ch ọn đủ l ớn để ph ươ ng pháp vét y = g x mod p , r = g k mod p , r = (r )α × g β × y α. β mod p , 
cạn là không kh ả thi trong các ứng d ụng th ực t ế. a b a
 , −1 , , 
 e = H( rb ||M ) mod q eb = α × (e + β )mod q sa =x × (k+ eb )mod q
 Mặt khác, do m ỗi b ước th ực hi ện c ủa thu ật toán ký ( Thu ật 
 s = α × s + β mod q . N ếu: u = g −e × y s mod p và 
toán 3.1 ) đều s ử d ụng 2 tham s ố bí m ật (α,β) do B t ạo ra nên ( a )
các d ạng t ấn công làm l ộ ngu ồn g ốc b ản tin nh ư các thu ật toán v = H( u|| M )mod q thì: v = e . 
đã ch ỉ ra ở M ục 2 ( Thu ật toán 1.1, 1.2, 1.3 và 1.4 ) là không Th ật v ậy, t ừ (3.4b), (3.5b), (3.6b) và (3.7b) ta có: 
 −1
kh ả thi đố i v ới l ược đồ m ới đề xu ất. u = g −e× y s mod p = g β− α.eb × g x .α .( β +sa ) mod p 
 β− α.e x −1...α() β +x() k + e
3.2.2. Lược đồ ch ữ ký s ố mù LD 15.02B = g b × g b mod p
 Lược đồ ch ữ k ý s ố mù, k ý hi ệu LD-15.02B, được phát −1 −1
 = g β × g −eb .α × g x ..α β × g x.α . x .( k+ eb ) mod p
tri ển t ừ l ược đồ c ơ s ở LD-15.01B. Cũng giả thi ết r ằng A là (3.9b) 
 −1 α. β α
ng ười k ý có khóa công khai được hình thành theo Thu ật toán = g β × g −eb .α × ()g x × ()g k × gα .eb mod p
 −1 α. β α
2.1b c ủa l ược đồ c ơ s ở LD 15.01B và B là ng ười t ạo ra b ản tin = g β × ()g x × ()g k mod p
M được ký. Khi đó, thu ật toán ký và ki ểm tra ch ữ ký c ủa l ược Từ (2.1b), (3.1b) và (3.9b) ta có: 
đồ được ch ỉ ra nh ư sau: −1 α. β α
 β x k (3.10b) 
a) Thu ật toán k ý u= g × (g ) × (g ) mod p
 = ()r α × g β × y α. β mod p
 Thu ật toán 3.1b : a
 ừ
 Input : p, q, g, x, y, α, β, k , M. T (3.2) và (3.10), suy ra: u = rb (3.11b) 
 Output : (e,s). Thay (3.11) vào (3.8) ta có: 
 [1]. k (3.1b) 
 ra ← g mod p v = H( u || M )mod q = H( rb || M ) mod q (3.12b) 
 [2]. α β α. β (3.2b) 
 rb ← (ra ) × g × y mod p
 ISBN: 978-604-67-0635-9 117 
 H ội Th ảo Qu ốc Gia 2015 v ề Điện t ử, Truy ền Thông và Công Ngh ệ Thông Tin (ECIT 2015) 
 Từ (3.2b) và (3.12b), suy ra: v = e . Đây là điều c ần ch ứng IV. KẾT LU ẬN 
minh. Từ vi ệc phân tích điểm y ếu c ủa m ột s ố l ược đồ ch ữ k ý s ố 
d) Mức độ an toàn c ủa l ược đồ LD 15.02B mù đã được công b ố, bài báo đề xu ất 2 l ược đồ ch ữ k ý s ố mù 
 Tươ ng t ự l ươ c đồ LD 15.02A, khả n ăng ch ống t ấn công làm mới được phát tri ển t ừ các l ược đồ ch ữ k ý c ơ s ở xây d ựng d ựa 
lộ ngu ồn g ốc c ủa b ản tin sau khi ký của l ược đồ LD-15.02B trên tính khó c ủa bài toán logarit r ời r ạc, 2 lược đồ m ới này có 
cũng có th ể được đánh giá qua phân tích kh ả n ăng th ực hi ện mức độ an toàn cao h ơn các l ược đồ đã bi ết v ề kh ả n ăng ch ống 
một s ố thu ật t ấn công nh ư sau: tấn công làm l ộ ngu ồn g ốc c ủa b ản tin được ký. Đây là m ột 
 Thu ật toán 3.3b : yếu t ố quan tr ọng cho phép l ược đồ m ới đề xu ất có tính kh ả 
 Input : {(rai ,e bi ,sai,ki,ID Bi )| i=0,1,2,N}, M, (e,s), α, β. thi trong các ứng d ụng th ực t ế. 
 Output : ID Bi . 
 [1]. m ← H (M ) , i = 0 
 TÀI LI ỆU THAM KH ẢO 
 [2]. select : (,,,,r e s k ID ) 
 ai bi ai i Bi [1] D. Chaum, Blind Signature Systems, Advances in Cryptology, Crypto’ 
 [3]. α β α. β 83, Plenum Press, pp. 153. 
 rbi * ← (rai ) × g × y mod p
 [4]. ∗ [2] D. Chaum, A. Fiat, M. Naor, “ Untraceable Electronic Cash ”, Advances 
 e ← rbi *×H(M )modq in Cryptology,Crypto’ 88, LNCS 403, Springer Verlag, pp. 319-327. 
 [5]. if e∗ ≠ e then [3] D. Chaum, “ Privacy Protected Payment ”, SMART CARD 2000 , Elsevier 
 Science Publishers B.V., 1989, pp. 69-93. 
 [5.1]. i ← i +1 ; [4] N. Ferguson, “ Single Term Off-line Coins ”, Advances in Cryptology, 
 [5.2]. goto [2]; Eurocrypt’93, LNCS 765, Springer Verlag, pp. 318-328. 
 [5] D. Chaum, B. den Boer, E. van Heyst, S. Mjolsnes, A. Steenbeek, 
 [6]. e∗ ←α −1 ×(e + β)modq 
 bi “Efficient Offline Electronic Checks ”, Advances in Cryptology, 
 ∗ Eurocrypt’89, LNCS 434, Springer Verlag, pp. 294-301. 
 [7]. if ebi ≠ ebi then 
 [6] B. C. Rivest R., Shamir A., Adleman L. (1978), “ A Method for 
 [7.1]. i ← i +1 ; Obtaining Digital Signatures and Public Key Cryptosystems”, 
 [7.2]. goto [2]; Communications of the ACM, Vol. 21, No. 2, pp. 120 – 126. 
 [8]. s∗ ← x × (k + e )mod q [7] K. Nyberg, R. A. Rueppel, A New Signature Scheme Base on the DSA 
 ai i bi Giving Message Recovery , 1st ACM conference on Computer and 
 ∗ Communications Security, November 3 – 5, Fairfax, Virginia. 
 [9]. if sai ≠ sai then 
 [8] Jan L. Camenisch, Jean-Marc Piveteau, Markus A. Stadler , Blind 
 [9.1]. i ← i +1 ; Signatures Base on Discrete Logarithm Problem , Swiss KWF 
 [9.2]. goto [2]; Foundation, grant no. 2724.1. 
 [10]. s∗ ← α × (s + β )mod q [9] Nikolay A. Moldovyan, Blind Collective Signature Protocol , Computer 
 ai Science Journal of Moldova, vol.19, no.1(55), 2011. 
 ∗
 [11]. if s ≠ s then [10] National Institute of Standards and Technology, NIST FIPS PUB 186-3. 
 Digital Signature Standard, U.S. Department of Commerce, 1994. 
 [11.1]. i ← i +1 ; 
 [11] GOST R 34.10-94. Russian Federation Standard. Information 
 [11.2]. goto [2]; Technology. Cryptographic data Security . Produce and check 
 [12]. return ID Bi procedures of Electronic Digital Signature based on Asymmetric 
 Cryptographic Algorithm . Government Committee of the Russia for 
 Nh ận xét : Standards, 1994 (in Russian). 
 Thu ật toán 3.3b cho phép A có th ể xác đị nh được danh [12] Kharin Yu.S., Bernik V.I., Matveev G.V., Aguievich S.V. Mathematic 
tính c ủa B nếu có th ể tính ( α,β) nh ờ gi ải (3.13b) : and computer foundations of cryptology , Novoe znanie, Minsk, 2003. 
 381 p. (in Russian). 
 −1 α β α. β 
 eb = α × (H((( ra ) × g × y mod p) ||M ) mod q + β ) mod q [13] C. P. Schnorr, “ Efficient signature generation by smart cards ”, Journal 
 of Cryptology, vol. 4, pp. 161 – 174, 1991. 
 (3.13b) 
 [14] T. ElGamal, “ A public key cryptosystem and a signature scheme based 
 Tuy nhiên, (3.13b) là m ột d ạng bài toán khó n ếu các tham on discrete logarithms ”, IEEE Transactions on Information Theory. 
số p, q được ch ọn đủ l ớn. Mặt khác, các d ạng t ấn công làm l ộ 1985, Vol. IT-31, No. 4. pp.469–472. 
ngu ồn g ốc b ản tin nh ư các thu ật toán đã ch ỉ ra ở M ục 2 ( Thu ật 
toán 1.1, 1.2, 1.3 và 1.4 ) là không kh ả thi đố i v ới lược đồ m ới 
đề xu ất. 
 ISBN: 978-604-67-0635-9 118