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<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 11 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 />