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