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

Công nghệ thông tin 
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ã Pohlig - Hellman.” 180 
PHÁT TRIỂN THUẬT TOÁN CHỮ KÝ SỐ DỰA TRÊN 
HỆ MÃ POHLIG - HELLMAN 
Nguyễn Vĩnh Thái1*, Lưu Hồng Dũng2 
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 Pohlig - 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ã Pohlig - Hellman. 
1. ĐẶT VẤN ĐỀ 
Hệ mã Pohlig - Hellman [1] được đề xuất và công bố bởi S. Pohlig và M. 
Hellman vào năm 1976. Đây là một hệ mã khóa bí mật đượ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ã Pohlig - 
Hellman có phương pháp mã hóa hoàn toàn như hệ mật RSA. Song do hệ mã 
Pohlig - 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ã Pohlig - 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ã Pohlig - 
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Ã 
POHLIG - HELLMAN 
2.1. Hệ mã Pohlig - 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: )1()( pp 
[3]. Chọn khóa mã hóa e là một giá trị ngẫu nhiên thỏa mãn: )(1 pe và: 
1))(,gcd( pe 
[4]. Tính khóa giải mã d theo công thức: )(mod1 ped 
[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] 
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, 12 - 2017 181
[2]. Người gửi sử dụng khóa mã hóa (e) để mã hóa bản tin: 
 pmC e mod 
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: 
pCm d mod 
[2]. Chuyển giá trị m thành bản tin ban đầu. 
Nhận xét: 
Trong hệ mã Pohlig - 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 )1()( pp . Như 
vậy, chỉ cần biết 1 trong 2 giá trị e hoặc d thì 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ệ Pohlig - Hellman là một hệ 
mã khóa bí mật. Cũng vì lí do đó, hệ Pohlig - 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ã Pohlig - 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 Zp là 
khó. 
[2]. Lựa chọn hàm băm (hash function) H: {0,1}* Zn , với: pn . 
[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: 11 pex và: 1)1,gcd( pex 
[2]. Tính giá trị: )1mod(1 ped xx 
[3]. Sử đụng thuật toán Euclide mở rộng [6] để tính 2 giá trị a và b sao cho: 
 1)1mod( pdbea xx 
[4]. Tính giá trị khóa e theo công thức: )1mod( pbee x 
 Kiểm tra nếu: 1)1,gcd( pe thì thực hiện lại từ bước [3]. 
[5]. Tính giá trị khóa d theo công thức: )1mod( padd x 
[6]. Công khai: e ; giữ bí mật: d; hủy và giữ bí mật: a, b, xd , xe . 
2.2.2. Thuật toán chữ ký số 
a) Thuật toán ký 
Công nghệ thông tin 
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ã Pohlig - Hellman.” 182 
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) 
[2]. Hình thành phần thứ nhất của chữ ký: pmS d mod 
[3]. Chữ ký số tương ứng với bản tin M là S. 
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) 
[2]. Tính giá trị m theo công thức: pSm e mod 
[3]. Kiểm tra nếu pmm mod2 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.3. 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ổ đề: 
Nếu: p là số nguyên tố, 11 pe , 1)1,gcd( pe , )1mod(1 ped và 
pm 0 thì: mpm de mod. . 
Chứng minh: 
Thật vậy, ta có: )1mod(1 ped . Nên: 1)1mod( ped 
Do đó sẽ tồn tại số nguyên k sao cho: 1)1( pked 
Theo định lý Euler [6] ta có: 1mod1 pm p 
Từ đây suy ra: 
 mpmpmpm
pmpmpmpm
pk
pkpkde
mod1modmod
modmodmodmod
1
1.11..
Bổ đề được chứng minh. 
Mệnh đề: 
Cho p là số nguyên tố, 11 pex , 1)1,gcd( pex , )1mod(
1
ped xx , 
1)1mod( pdbea xx , )1mod( padd x , )1mod( pbee x , 
1)1,gcd( pe pm 0 , pmS d mod . Nếu: pSm e mod thì: 
pmm mod2 . 
Chứng minh: 
Thật vậy, do: 
pmmpm
pmpm
pmppmpSm
xxxx
xxxxxx
dede
dbeaedbead
deede
modmod
modmod
modmodmodmod
.1.
....
.
Theo Bổ đề, ta có: mpm xx de mod. 
Từ đây suy ra: pmm mod2 . Mệnh đề đã được chứng minh. 
2.2.4. Mức độ an toàn của thuật toán MTA 17.3 - 01 
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, 12 - 2017 183
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 chố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 sao cho d 
và e không nghịch đảo với nhau theo modulo (p-1). Nghĩa là từ e không thể tính 
được d bằng phép nghịch đảo theo modulo (p-1). Ngoài ra, việc tính d bằng cách 
giải bài toán logarit rời rạc từ: pmS d mod 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 chố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 hoàn toàn như nhau. Vì vậy, 
các chứng minh và đánh giá về tính an toàn của RSA cũng 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 nmS d mod 
MTA 17.3 - 01 pmS d mod1 
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 nSm e mod 
 if )(MHm then S = true 
MTA 17.3 - 01 pSm e mod 
if pMHm mod)( 2 then S = true 
2.2.5. 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à: (Texp + Th) 
Thời gian kiểm tra chữ ký là: (Texp + Th) 
Tổng thời gian thực hiện: (2Texp + 2Th ) 
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à: (Texp + Th) 
Thời gian kiểm tra chữ ký là: (Texp + Th + Tmul) 
Tổng thời gian thực hiện: (2Texp + 2Th +Tmul ) 
Công nghệ thông tin 
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ã Pohlig - Hellman.” 184 
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 thuật toán MTA 17.3 - 01 và RSA. 
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 
và thuật toán RSA là tương đương nhau. 
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 
Pohlig - 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 
[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. 
TT Thuật toán Tổng thời gian thực hiện 
1 RSA 2Texp + 2Th 
2 MTA 17. 3 - 01 2Texp + 2Th + Tmul 
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, 12 - 2017 185
ABSTRACT 
DEVELOPING A NEW DIGITAL SIGNATURE ALGORITHM 
BASED ON POLIGH - HELLMAN EXPONENTIATION CIPHER 
In this paper, a new digital signature algorithm based on the Poligh - 
Hellman exponentiation cipher is proposed. 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.