Phát triển thuật toán chữ ký số dựa trên hệ mã Poligh - Hellman

 Công ngh ệ thông tin 
 PHÁT TRI ỂN THU ẬT TOÁN CH Ữ KÝ S Ố D ỰA TRÊN 
 HỆ MÃ POLIGH - HELLMAN 
 Nguy ễn V ĩnh Thái 1, L ưu H ồng D ũng 2 
 Tóm t ắt: Bài báo đề xu ất xây d ựng thu ật toán ch ữ ký s ố trên c ơ s ở phát 
 tri ển h ệ mã khóa bí mật Poligh – Hellman. Thu ật toán ch ữ ký m ới đề xu ất có 
 nguyên t ắc làm vi ệc t ươ ng t ự thu ật toán ch ữ ký RSA, song cho phép nhi ều đối 
 tượng ký có th ể cùng s ử d ụng chung m ột modulo p trong các thu ật toán ký và 
 thu ật toán ki ểm tra ch ữ ký. Đồng th ời, bài báo c ũng phân tích m ức độ an toàn 
 của l ược đồ m ới đề xu ất, cho th ấy kh ả n ăng ứng d ụng c ủa nó trong th ực t ế. 
Từ khóa : Ch ữ ký s ố, thu ật toán ch ữ ký s ố, l ược đồ ch ữ ký s ố, h ệ m ật khóa bí m ật, h ệ mã Poligh – Hellman. 
 1. ĐẶT V ẤN ĐỀ 
 Hệ mã Poligh – Hellman [1] được đề xu ất và công b ố b ởi S. Poligh và M. 
Hellman vào n ăm 1976. Đây là m ột h ệ mã khóa bí m ật nh ưng được xây d ựng theo 
ph ươ ng pháp c ủa các h ệ mã l ũy th ừa RSA [2] , ElGamal [3],... H ệ mã Poligh – 
Hellman có ph ươ ng pháp mã hóa hoàn toàn nh ư h ệ m ật RSA. Song do h ệ mã 
Poligh – Hellman s ử d ụng modulo p là s ố nguyên t ố nên các khóa mã hóa và gi ải 
mã ph ải được gi ữ bí m ật hoàn toàn, chính vì lý do này mà h ệ mã Poligh – Hellman 
là m ột h ệ mã khóa bí m ật và không th ực hi ện được ch ức n ăng c ủa m ột h ệ ch ữ ký 
số nh ư h ệ m ật RSA. 
 Bài báo đề xu ất m ột thu ật toán ch ữ ký s ố được phát tri ển t ừ h ệ mã Poligh – 
Hellman, l ược đồ m ới đề xu ất có nguyên t ắc làm vi ệc t ươ ng t ự l ược đồ RSA, song 
lại cho phép các đối t ượng ký cùng s ử d ụng chung m ột modulo p nguyên t ố nh ư 
các l ược đồ DSA trong chu ẩn DSS [4] của Hoa K ỳ hay GOST R34.10 – 94 c ủa 
Liên bang Nga [5]. 
 2. PHÁT TRI ỂN THU ẬT TOÁN CH Ữ KÝ S Ố D ỰA TRÊN H Ệ MÃ 
 POLIGH – HELLMAN 
 2.1. Hệ mã Poligh – Hellman 
2.1.1. Thu ật toán hình thành tham s ố và khóa 
 Thu ật toán bao g ồm các b ước nh ư sau: 
 [1]. Sinh s ố nguyên t ố p l ớn, m ạnh. 
 [2]. Tính: ϕ()p = ( p − )1 
 [3]. Ch ọn khóa mã hóa e là m ột giá tr ị ng ẫu nhiên th ỏa mãn: 1 < e < ϕ (p ) và: 
 gcd( e,ϕ (p )) = 1 
 [4]. Tính khóa gi ải mã d theo công th ức: d = e−1 mod ϕ (p ) 
 [5]. Khóa bí m ật chia s ẻ gi ữa đối t ượng g ửi/mã hóa và nh ận/gi ải mã là các 
 tham s ố: p, d và e. 
2.1.2 Thu ật toán mã hóa và gi ải mã 
a) Thu ật toán mã hóa: 
 Thu ật toán bao g ồm các b ước: 
 [1]. Bi ểu di ễn b ản tin c ần ký M thành m ột giá tr ị m t ươ ng ứng trong kho ảng 
 [0, p – 1] 
180 N.V. Thái, L.H. Dũng, “Phát tri ển thu ật toán ch ữ ký s ố dựa trên h ệ mã Poligh – Hellman.” 
 Công ngh ệ thông tin 
 [2]. Ng ười g ửi s ử d ụng khóa mã hóa ( e) để mã hóa b ản tin: 
 C = me mod p 
 Bản mã t ươ ng ứng v ới bản tin M là C. 
b) Thu ật toán gi ải mã: 
 Thu ật toán ki ểm tra bao g ồm các b ước: 
 [1]. Ng ười nh ận s ử d ụng khóa gi ải mã ( d) để gi ải mã b ản tin nh ận được: 
 m = C d mod p 
 [2]. Chuy ển giá tr ị m thành b ản tin ban đầu. 
 Nh ận xét : 
 Trong h ệ mã Poligh – Hellman, khóa mã hóa (e) và gi ải mã (d) là 2 giá tr ị 
ngh ịch đảo nhau theo modul ϕ()p . Do p là s ố nguyên t ố, nên ϕ()p = ( p − )1 . Nh ư 
vậy, ch ỉ c ần bi ết 1 trong 2 giá tr ị e ho ặc d thì hoàn toàn d ễ dàng tính được giá tr ị 
kia. Vì th ế, c ả 2 khóa e và d đều ph ải được gi ữ bí m ật và do đó h ệ Poligh – 
Hellman là m ột h ệ mã khóa bí m ật. C ũng vì lí do đó, h ệ Poligh – Hellman không 
th ể th ực hi ện vai trò c ủa m ột h ệ ch ữ ký s ố nh ư hệ m ật RSA. 
2.2. Thu ật toán ch ữ ký mới đề xu ất MTA 17.3 – 01 
 Thu ật toán ch ữ ký m ới đề xu ất, ký hi ệu MTA 17.3 – 01, được xây d ựng theo 
nguyên t ắc c ủa h ệ mã Poligh – Hellman bao g ồ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ý nh ư sau: 
2.2.1 Thu ật toán hình thành các tham s ố h ệ th ống và khóa 
a) Hình thành các tham s ố h ệ th ống 
 Hình thành tham s ố bao g ồm các b ước th ực hi ện nh ư sau: 
 [1]. Ch ọn s ố nguyên t ố p l ớn sao cho vi ệc gi ải bài toán logarit r ời r ạc trên Z p là 
 khó. 
 *
 [2]. Lựa ch ọn hàm b ăm (hash function) H: {0,1} a Zn , v ới: n < p . 
 [3]. Công khai: p, H(.) . 
 Ghi chú : Trong ứng d ụng th ực t ế, p là tham s ố h ệ th ống và do nhà cung c ấp 
dịch v ụ ch ứng th ực s ố t ạo ra. 
b) Thu ật toán hình thành khóa 
 Mỗi ng ười dùng U hình thành c ặp khóa bí m ật và công khai c ủa mình theo các 
bước nh ư sau: 
 [1]. Ch ọn giá tr ị ex th ỏa mãn: 1 < ex < p − 1 và: gcd( ex , p − )1 = 1 
 −1
 [2]. Tính giá tr ị: d x = (ex ) mod( p − )1 
 [3]. Ch ọn m ột giá tr ị ng ẫu nhiên t thỏa mãn: 1 < t < p −1 
 t
 [4]. Tính giá tr ị khóa e theo công th ức: e = ((ex ) mod p)mod( p − )1 
 Ki ểm tra n ếu: gcd( e, p − )1 = 1 thì th ực hi ện l ại t ừ b ước [3]. 
 t
 [5]. Tính giá tr ị khóa d1 theo công th ức: d1 = ((dx ) mod p)mod( p − )1 
 Ki ểm tra n ếu: gcd( d1, p − )1 = 1 thì th ực hi ện l ại t ừ b ước [3]. 
 [6]. Tính giá tr ị khóa d2 công th ức: 
 t t t t
 d2 = ((dx ) mod( p − )1 × (ex ) mod( p − )1 − (dx ) mod p × (ex ) mod p)mod( p − )1 
 Ki ểm tra n ếu: gcd( d2 , p − )1 = 1 thì th ực hi ện l ại t ừ b ước [3]. 
 Tạp chí Nghiên c ứu KH&CN quân s ự, S ố Đặc san CNTT, 12 - 2017 181 
 Công ngh ệ thông tin 
 [7]. Công khai: e ; gi ữ bí mât: d1, d2. 
2.2.2 Thu ật toán ch ữ ký s ố 
a) Thu ật toán ký 
 Thu ật toán bao g ồm các b ước: 
 [1]. Tính giá tr ị đại di ện c ủa b ản tin c ần ký (M): m = H (M) 
 d1
 [2]. Hình thành ph ần th ứ nh ất c ủa ch ữ ký: S1 = (m) mod p 
 d 2
 [3]. Hình thành ph ần th ứ hai c ủa ch ữ ký: S2 = (m) mod p 
 [4]. Ch ữ ký s ố t ươ ng ứng v ới b ản tin M là c ặp: S = (S 1, S 2). 
b) Thu ật toán ki ểm tra 
 Thu ật toán ki ểm tra bao g ồm các b ước: 
 [1]. Tính giá tr ị đại di ện c ủa b ản tin c ần th ẩm tra (M): m = H(M) 
 e
 [2]. Tính giá tr ị m theo công th ức: m = S2 × (S1 ) mod p 
 [3]. Ki ểm tra n ếu m = m thì ch ữ ký là h ợp l ệ, ngu ồn g ốc và tính toàn v ẹn c ủa 
 bản tin c ần th ẩm tra được công nh ận. 
2.2.4 Tính đúng đắn c ủa thu ật toán MTA 17.3 – 01 
 Tính đúng đắn c ủa thu ật toán ch ữ ký m ới đề xu ất được ch ứng minh qua các b ổ 
đề và m ệnh đề sau đây: 
 Bổ đề 1: 
 Nếu: p là s ố nguyên t ố, 1 < e< p −1 , gcd( e, p − )1 = 1 , d = e−1 mod( p − )1 và 
0≤ m < p thì: me. d mod p = m . 
 Ch ứng minh: 
 Th ật v ậy, ta có: d = e−1 mod( p − )1 . Nên: d× emod( p − )1 = 1 
 Do đó s ẽ t ồn t ại s ố nguyên k sao cho: d× e = k × ( p − )1 + 1 
 Theo định lý Euler [6] ta có: m( p−1) mod p = 1 
 Từ đây suy ra: 
 me. d mod p = mk.( p−1) + 1 mod p = (mk.( p−1) mod p)× mmod p
 ()p−1
 = (()mk mod p)× mmod p = 1× mmod p = m
 Bổ đề được ch ứng minh. 
 Bổ đề 2: 
 Nếu: p là s ố nguyên t ố, 1 < e< p − 1 , gcd( e, p − )1 = 1, d= e−1 mod( p − )1 , 
 t t
0≤ m < p thì: m()()e . d mod p = m . 
 Ch ứng minh: Th ật v ậy, theo B ổ đề 1 ta có: 
 t t t ()e. d t−1
 m()()()e. d mod p = m e. d mod p = (me. d mod p) mod p
 t−1 ()e. d t−2 t−2
 = m()e. d mod p = ()me. d mod p mod p = m()e. d mod p
 t 3
 ()e. d − t−3
 = ()me. d mod p mod p = m()e. d mod p 
 .......... .......... .......... .......... .......... .......... .......... .......... .......... ..
 3 ()e. d 2 2
 = m()e. d mod p = ()me. d mod p mod p = m()e. d mod p
 e. d
 = ()me. d mod p mod p = me. d mod p = m
182 N.V. Thái, L.H. Dũng, “Phát tri ển thu ật toán ch ữ ký s ố dựa trên h ệ mã Poligh – Hellman.” 
 Công ngh ệ thông tin 
 Bổ đề được ch ứng minh. 
 Mệnh đề: 
 −1
 Cho p là s ố nguyên t ố, 1 < ex < p −1, gcd( ex , p − )1 = 1, d x = (ex ) mod( p − )1 , 
 t
0 ≤ m < p , 1 < t< p −1 , e = ((ex ) mod p)mod( p − )1 , 
 t
d1 = ((d x ) mod p)mod( p − )1 , 
 t t t t
d2 = ((dx ) mod( p − )1 × (ex ) mod( p − )1 − (dx ) mod p × (ex ) mod p)mod( p − )1 , 
 d1 d 2 e
0 ≤ m < p , C1 = (m) mod p , C2 = (m) mod p . Nếu: m = C2 × (C1 ) mod p thì: 
m = m . 
 Ch ứng minh: 
 Th ật v ậy, do: 
 e
 m = C2 × (C1 ) mod p =
 e
 = ()()md 2 mod p × md1 mod p mod p = md 2 × md1 . e mod p
 ()()()()()()d t mod p−1 . e t mod p−1 − d t mod p. e t mod p mod ()p−1 
 = m( x x x x ) ×
 ()d t mod p mod ()()p−1 . e t mod p mod ()p−1
 × m()x ()x mod p
 ()()()()()d t . e t mod p−1 d t . e t
 = m x x mod p = m x x mod p
 ()()e t . d t
 Theo B ổ đề 2, ta có: m x x mod n = m 
 Từ đây suy ra: m = m 
 Mệnh đề được ch ứng minh. 
2.2.5 M ức độ an toàn c ủa thu ật toán MTA 17.3 – 01 
 Mức độ an toàn c ủa thu ật toán mới đề xu ất có th ể đánh giá qua các kh ả n ăng s ẽ 
được xem xét d ưới đây: 
a) Kh ả n ăng t ấn công làm l ộ khóa m ật 
 Với thu ật toán hình thành khóa ở mục 2.1.1 , hoàn toàn có th ể ch ọn giá tr ị c ủa t 
sao cho d1, d2 và e không ngh ịch đảo v ới nhau theo c ả modulo p và modulo (p-1). 
Ngh ĩa là t ừ e không th ể tính được d1 và d2 b ằng phép ngh ịch đảo theo modulo p và 
modulo (p-1). Ngoài ra, vi ệc tính d1, d2 b ằng cách gi ải bài toán logarit r ời r ạc t ừ: 
 d1 d 2
S1 = (m) mod p và: S2 = (m) mod p c ũng không kh ả thi, vì đây là bài toán khó 
nếu giá tr ị c ủa tham s ố p được ch ọn đủ l ớn. 
b) Kh ả n ăng t ấn công thu ật toán ch ữ ký s ố 
 Bảng 1 và 2 cho th ấy các thu ật toán ký và ki ểm tra ch ữ ký của MTA 17.3 – 01 
và c ủa thu ật toán ch ữ ký số RSA có c ơ ch ế làm vi ệc t ươ ng t ự nh ư nhau. Vì v ậy, 
các ch ứng minh và đánh giá v ề tính an toàn c ủa RSA c ũng hoàn toàn có th ể áp 
dụng đối v ới MTA 17.3 – 01. 
 Bảng 1 . Thu ật toán ký c ủa RSA và MTA 17.3 – 01 
 Thu ật toán Thu ật toán ký 
 RSA S = (m)d mod n 
 MTA 17.3 – 01 d1
 S1 = (m) mod p 
 d 2
 S2 = (m) mod p 
 Tạp chí Nghiên c ứu KH&CN quân s ự, S ố Đặc san CNTT, 12 - 2017 183 
 Công ngh ệ thông tin 
 Bảng 2. Thu ật toán ki ểm tra c ủa RSA và MTA 17.3 – 01 
 Thu ật toán Thu ật toán ki ểm tra 
 RSA m = (S )e mod n 
 if m = H (M ) then S = true 
 MTA 17.3 – 01 e
 m = S2 × (S1 ) mod p 
 if m = H (M ) then (S 1,S 2) = true 
2.2.6 Hi ệu qu ả th ực hi ện của thu ật toán MTA 17.3 – 01 
 Hi ệu qu ả th ực hi ện c ủa các thu ật toán có th ể được đánh giá thông qua s ố phép 
toán c ần th ực hi ện hay t ổng th ời gian c ần th ực hi ện các phép toán để hình thành và 
ki ểm tra ch ữ ký . Để so sánh hi ệu qu ả th ực hi ện c ủa thu ật toán mới đề xu ất v ới 
thu ật toán ch ữ ký số RSA, ở đây qui ước s ử d ụng các ký hi ệu: 
 Texp : th ời gian th ực hi ện m ột phép toán m ũ modul; 
 Th : th ời gian th ực hi ện hàm b ăm ( hash function ). 
 Tmul : th ời gian th ực hi ện m ột phép toán nhân modul; 
 a) Th ời gian th ực hi ện c ủa thu ật toán RSA: 
 Thời gian hình thành ch ữ ký là: (T exp + Th) 
 Thời gian ki ểm tra ch ữ ký là: (T exp + T h) 
 Tổng th ời gian th ực hi ện: (2Texp + 2T h ) 
 b) Th ời gian th ực hi ện c ủa thu ật toán MTA 17.3 – 01 : 
 Thời gian hình thành ch ữ ký là: (2Texp + Th) 
 Thời gian ki ểm tra ch ữ ký là: (T exp + T h + Tmul ) 
 Tổng th ời gian th ực hi ện: (3Texp + 2T h +T mul ) 
 Tổng h ợp th ời gian thực hi ện c ủa thu ật toán m ới đề xu ất MTA 17.3 – 01 và 
của RSA được ch ỉ ra trên B ảng 3 nh ư sau: 
 Bảng 3. Th ời gian th ực hi ện c ủa các thu ật toán MTA 17.3 – 01 và RSA 
 TT Thu ật toán Tổng th ời gian th ực hi ện 
 1 RSA 2Texp + 2Th 
 2 MTA 17. 3 – 01 3Texp + 2Th + T mul 
 Nh ận xét : 
 Từ B ảng 3 có th ể th ấy r ằng hi ệu qu ả th ực hi ện c ủa thu ật toán MTA 17.3 – 01 
th ấp h ơn thu ật toán RSA. 
 3. K ẾT LU ẬN 
 Bài báo đề xu ất m ột thu ật toán ch ữ ký m ới t ừ vi ệc phát tri ển h ệ mã khóa bí m ật 
Poligh – Hellman. Thu ật toán m ới đề xu ất có nguyên t ắc làm vi ệc c ơ b ản nh ư l ược 
đồ ch ữ ký RSA, song các đối t ượng ký có th ể s ử d ụng chung modulo p mà không 
ảnh h ưởng đến độ an toàn c ủa l ược đồ. M ột s ố phân tích s ơ b ộ v ề độ an toàn và 
hi ệu qu ả th ực hi ện cho th ấy kh ả n ăng ứng d ụng c ủa thu ật toán m ới đề xu ất là hoàn 
toàn th ực t ế. 
 TÀI LI ỆU THAM KH ẢO 
184 N.V. Thái, L.H. Dũng, “Phát tri ển thu ật toán ch ữ ký s ố dựa trên h ệ mã Poligh – Hellman.” 
 Công ngh ệ thông tin 
[1] Pohlig, S. and Hellman, M., ” An Improved Algorithm for Computing Logarithms over 
 GF(p) and its Cryptographic Significance ,” IEEE Trans. on Info. Theory Vol. IT-
 24(1) pp. 106-110 (Jan. 1978). 
[2] R. L. Rivest, A. Shamir, L. M. Adleman, “ A Method for Obtain ỉng Digital Signatures 
 and Public Key Cryptosystems ”, Commun. of the ACM, Voi. 21, No. 2, 1978, pp. 120-
 126. 
[3] ElGamal T., “ 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. 
[4] National Institute of Standards and Technology, NIST FIPS PUB 186-3. Digital 
 Signature Standard, US Department of Commerce, 1994. 
[5] 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). 
[6] R. Kenneth, “Elementary Number Theory and its Applications” , AT & T Bell 
 Laboratories, 4th Edition, ISBN: 0-201- 87073-8, 2000. 
[7] Mark Stamp, Richard M. Low , “ Applied cryptanalysis: Breaking Ciphers in the Real 
 World”. John Wiley & Sons, Inc., ISBN 978-0-470-1. 
[8] D. Boneh, “ Twenty Years of Attacks on the RSA Cryptosystem, Notices of the 
 American Mathematical Society ”, 46(2), 1999, pp. 203-213. 
 DEVELOPING NEW DIGITAL SIGNATURE ALGORITHM BASED ON 
 POLIGH – HELLMAN EXPONENTIATION CIPHER 
ABSTRACT — This paper proposes new digital signature algorithm based on the Poligh – Hellman 
exponentiation cipher. The proposed signature algorithm has the same working principle as the RSA signature 
algorithm, but allows multiple signatures to share the modulo p in signed algorithms and signature verification 
algorithms. In addition to information security capabilities, the new algorithm has the ability to validate the 
integrity and origin of the message is confidential. 
KEYWORDS — Public - Key Cryptosystem, Secret - Key Cryptosystem, Digital Signature Algorithm, Poligh 
– Hellman exponentiation cipher. 
 Nh ận bài ngày 16 tháng 8 n ăm 2017 
 Hoàn thi ện ngày 26 tháng 11 năm 2017 
 Ch ấp nh ận đă ng ngày 28 tháng 11 n ăm 2017 
Địa ch ỉ: 1 Vi ện CNTT, Vi ện KH và CN QS 
 2 Khoa CNTT, H ọc vi ện KTQS. 
 Email: nguyenvinhthai@gmail.com. 
 Tạp chí Nghiên c ứu KH&CN quân s ự, S ố Đặc san CNTT, 12 - 2017 185