Phát triển lược đồ chữ ký số trên bài toán logarit rời rạc - Nguyễn Đức Thụy

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 103 PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC Nguyễn Đức Thụy1*, Hồ Nhật Quang2, Lưu Hồng Dũng2 Tóm tắt: Bài báo đề xuất phương pháp xây dựng lược đồ chữ ký số dựa trên tính khó giải của bài toán logarit rời rạc. Từ dạng lược đồ tổng quát được xây dựng, một số lược đồ chữ k ý đã được đề xuất cho các ứng dụng trong thực tế. Từ khoá: Digital Signature, Digital Signature Schema, Discrete logarit problem. 1. MỞ ĐẦU Trong các giao dịch điện tử (Chính phủ điện tử, Thương mại điện tử,), chữ ký số được sử dụng nhằm đáp ứng yêu cầu chứng thực về nguồn gốc và tính toàn vẹn của thông tin. Hiện nay chữ k ý số đã được ứng dụng rộng rãi trong các lĩnh vực Chính phủ điện tử, Thương mại điện tử, trên thế giới cũng như đã bước đầu được triển khai ở Việt Nam. Do đó, việc nghiên cứu - phát triển các lược đồ chữ k ý số mới cho mục đích thiết kế - chế tạo các sản phẩm, thiết bị an toàn và bảo mật thông tin trong nước luôn là vấn đề cần thiết được đặt ra. Bài báo đề xuất phương pháp xây dựng lược đồ chữ k ý số dựa trên tính khó của bài toán logarit rời rạc và một số lược đồ chữ ký số được phát triển theo phương pháp chung này. 2. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC 2.1. Bài toán logarit rời rạc Cho p là một số nguyên tố và g là phần tử sinh của nhóm ZP*. Khi đó bài toán logarit rời rạc - DLP (Discrete Logarithm Problem) trên trường ZP hay còn gọi là bài toán ),( gpDLP được phát biểu như sau: Bài toán DLP(p,g): Với mỗi số nguyên dương y ℤp *, hãy tìm x thỏa mãn phương trình sau: ypg x mod (1.1) Giải thuật cho bài toán logarit rời rạc với các tham số {p, g} công khai có thể được viết như một thuật toán tính hàm (.)),( gpDLP với biến đầu vào là y còn giá trị hàm là nghiệm x của phương trình (1.1): )(),( yDLPx gp Trong một hệ thống giao dịch điện tử ứng dụng chứng thực số để xác thực nguồn gốc và tính toàn vẹn thông tin cho các thông điệp dữ liệu, bài toán ),( gpDLP là khó theo nghĩa không thể thực hiện được trong thời gian thực. Ở đó, mỗi thành viên U của hệ thống tự chọn cho mình khóa bí mật x thỏa mãn: )1(1  px , tính và công khai tham số: pgy x mod (1.2) Chú ý: (i) Bài toán ),( gpDLP là khó theo nghĩa không thể thực hiện được trong thời gian thực, tuy nhiên không phải với mọi yZP* thì việc tính ),( gpDLP đều khó, chẳng hạn những pgy x mod với x không đủ lớn thì bằng cách duyệt dần x = 1, 2, ... cho đến khi tìm được nghiệm của (1.2) ta sẽ tìm được khóa bí mật x, do đó các giá trị của khóa mật x phải được lựa chọn sao cho việc tính )(),( yDLP gp đều khó. (ii) Với lựa chọn x như trên thì không có ai ngoài U biết được giá trị x, vì vậy việc biết được x đủ để xác thực đó là U. Công nghệ thông tin & Khoa học máy tính N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký logarit rời rạc.” 104 Hiện tại, bài toán trên vẫn được coi là bài toán khó [1,2] do chưa có giải thuật thời gian đa thức cho nó và hệ mật ElGamal [3] là một chứng minh thực tế cho tính khó giải của bài toán này. 2.2. Xây dựng lược đồ dạng tổng quát Lược đồ dạng tổng quát được sử dụng để phát triển các lược đồ chữ k ý số cho các ứng dụng thực tế. Lược đồ dạng tổng quát đề xuất ở đây được xây dựng trên cơ sở tính khó giải của bài toán logarit rời rạc và được thiết kế theo dạng lược đồ sinh chữ ký 2 thành phần tương tự như DSA trong chuẩn chữ k ý số của Mỹ (DSS) [4] hay GOST R34.10-94 của Liên bang Nga [5], bao gồm các phương pháp hình thành tham số, phương pháp hình thành và kiểm tra chữ ký được chỉ ra dưới đây.  Phương pháp hình thành tham số và khóa Dữ liệu vào: p, q , x . Kết quả: g, y, H(.). Các bước thực hiện: 1. Tính phần tử sinh g của Zp*: phg qp mod/)1(  , với: ph 1 (2.1) 2. Tính khóa công khai: pgy x mod (2.2) 3. Chọn hàm băm H: {0,1}* → Zq ; Chú thích: (i) p, q: 2 số nguyên tố thỏa mãn q|(p-1). (ii) x: khóa bí mật của đối tượng ký thỏa mãn: qx 1 .  Phương pháp hình thành chữ ký Dữ liệu vào: p, q, g, x, M. Kết quả: (e,s). Các bước thực hiện: 1. Chọn giá trị k thỏa mãn: qk 1 . Tính giá trị r theo công thức: pgr k mod (2.3) 2. Thành phần thứ nhất e của chữ k ý được chọn theo một trong hai dạng: qre mod (2.4) hoặc: qrMfe mod),(1 (2.5) 3. Thành phần thứ hai s của chữ k ý được hình thành theo một trong các dạng sau: qrMfxrMfks mod)],(.),(.[ 3 1 2   (2.6) hoặc: qrMfxrMfks mod)],(.),(.[ 132  (2.7) Chú thích: (i) M: thông điệp dữ liệu cần k ý. (ii) (e,s): chữ ký lên M của đối tượng sở hữu {x,y}. (iii) ),(),,(),,( 321 rMfrMfrMf : là các hàm của M, r và thỏa mãn điều kiện: qrMfrMfrMf  ),(),,(),,(1 321  Phương pháp kiểm tra chữ ký Dữ liệu vào: p, q, g, y, M, (e,s). Kết quả: Khẳng định (e,s) là chữ k ý hợp lệ ((e,s) = true) hay (e,s) là giả Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 105 mạo và/hoặc M không còn toàn vẹn ((e,s) = false). Các bước thực hiện: 1. Tính giá trị u: pygu rMfrMfrMfs mod),().,(),(. 322  (2.8), nếu s được tính theo (2.6) hoặc: pygu rMfsrMfs mod),(.),(. 32  (2.9), nếu s được tính theo (2.7) 2. Tính giá trị v: quv mod (2.10), nếu e được tính theo (2.4) hoặc: quMfv mod),(1 (2.11), nếu e được tính theo (2.5) 3. Kiểm tra nếu: v = e (2.12), thì: (e,s) = true, ngược lại: (e,s) = false.  Tính đúng đắn của lược đồ dạng tổng quát Điều cần chứng minh ở đây là: nếu tham số và khóa được hình thành theo (2.1) và (2.2), chữ k ý được hình thành theo các công thức từ (2.3) đến (2.7), còn kiểm tra chữ k ý được thực hiện theo (2.8) đến (2.11) thì điều kiện chỉ ra bởi (2.12) sẽ được thỏa mãn. Bổ đề 1.1: Cho p và q là 2 số nguyên tố với q là ước số của (p-1), h là một số nguyên dương nhỏ hơn p. Nếu: phg qp mod/1(  thì: 1mod pg q . Chứng minh: Ta có: phpphpg pqqpq modmod)mod(mod )1(/)1(   Theo định l ý Fermat thì: 1mod)1(  ph p Vì vậy: 1mod pg q Bổ đề đã được chứng minh. Bổ đề 1.2: Cho p và q là 2 số nguyên tố với q là ước số của (p -1), h là một số nguyên dương nhỏ hơn p và phg qp mod/1(  . Nếu: qnqm modmod  thì: pgpg nm modmod  Chứng minh: Nếu: qnqm modmod  thì: m = n + k.q hoặc: n = m + k.q, với k là một số nguyên. Không làm mất tính tổng quát, giả sử: m = n + k.q. Do đó: ppgpg ppgpg pggpgpg kqn qkn qknqknm mod)mod).(mod( mod)mod).(mod( modmodmod . ..     Theo Bổ đề 1.1 ta có: 1mod pg q Nên: pgpgpg nknm modmod1.mod  Công nghệ thông tin & Khoa học máy tính N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký logarit rời rạc.” 106 Bổ đề đã được chứng minh. Mệnh đề 1.1: Cho p và q là 2 số nguyên tố với q là ước số của (p-1), h là một số nguyên dương nhỏ hơn p và phg qp mod/1(  , qkx  ,1 . Nếu: pgy x mod , pgr k mod , qre mod hoặc: qrMfe mod),(1 , qrMfxrMfks mod)],(.),(.[ 3 1 2   với: qrMfrMfrMf  ),(),,(),,(1 321 , pygu rMfrMfrMfs mod),().,(),(. 322  , quv mod hoặc: quMfv mod),(1 thì: ev  . Chứng minh: Thật vậy, ta có: qrMfrMfxkrMfqrMfxrMfks mod)],().,(..[),(mod)],(.),(.[ 32 1 23 1 2   Nên: qrMfrMfxkqrMfs mod)],().,(.[mod),(. 322  Theo Bổ đề 2.2 ta có: pgpg rMfrMfxkrMfs modmod ),().,(.),(. 322  Suy ra: pgpgg krMfrMfxrMfs modmod),().,(.),(. 322   Hay: pgpyg krMfrMfrMfs modmod),().,(),(. 322  (2.13) Từ (2.3) và (2.13) ta có: ru  Do đó: qrquv modmod  (2.14) hoặc: qrMfquMfv mod),(mod),( 11  (2.15) Từ (2.4) và (2.14) hoặc từ (2.5) và (2.15) suy ra: ev  Đây là điều cần chứng minh. Mệnh đề 1.2: Cho p và q là 2 số nguyên tố với q là ước số của (p-1), h là một số nguyên dương nhỏ hơn p và phg qp mod/1(  , qkx  ,1 . Nếu: pgy x mod , pgr k mod , qre mod hoặc: qrMfe mod),(1 , qrMfxrMfks mod)],(.),(.[ 132  với: qrMfrMfrMf  ),(),,(),,(1 321 , pygu rMfsrMfs mod),(.),(. 32  , quv mod hoặc: quMfv mod),(1 thì: ev  . Chứng minh: Thật vậy, từ (2.7) ta có: qrMfxrMfsk mod)],(.),(.[ 32  (2.16) Theo Bổ đề 2.2 và (2.16) suy ra: pgpgg krMfsxrMfs modmod),(..),(. 32  hay: pgpyg krMfsrMfs modmod),(.),(. 32  (2.17) Từ (2.3) và (2.17) ta có: ru  Do đó: qrquv modmod  (2.18) hoặc: qrMfquMfv mod),(mod),( 11  (2.19) Từ (2.4) và (2.18) hoặc từ (2.5) và (2.19) suy ra: ev  Đây là điều cần chứng minh. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 107 2.3 Một số lược đồ chữ ký số phát triển từ lược đồ dạng tổng quát 2.3.1 Lược đồ thứ nhất LD 1.01 Lược đồ LD 1.01 được phát triển từ dạng tổng quát với các lựa chọn: qMHrMf mod)(),(2  , qpgrMf k mod)mod(),(3  , ở đây H(.) là hàm băm và H(M) là giá trị đại diện của bản tin được ký M. Khóa công khai được tính theo công thức: pgy x mod . Các thuật toán hình thành tham số, hình thành và kiểm tra chữ ký được mô tả trong các bảng 1.1 và bảng 1.2 dưới đây: a) Thuật toán hình thành chữ k ý Bảng 1.1 Input: p, q, g, x, M. Output: (e,s) – chữ ký của U lên M. [1]. select k: qk 1 [2]. pgr k mod (3.1) [3]. qre mod (3.2) [4]. qexMHks mod].)(.[ 1   (3.3) [5]. return (e,s) Chú ý: (i) U: đối tượng k ý sở hữu khóa bí mật x. (ii) M: Bản tin được k ý bởi đối tượng U. b) Thuật toán kiểm tra chữ k ý Bảng 1.2: Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. Output: (e,s) = true / false . [1]. pygu MHeMHs mod)(.)(.  (3.4) [2]. quv mod (3.5) [3]. if ( ev  ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 1.01 Đặt: qMHrMf mod)(),(2  , erMf ),(3 . Theo (3.1), (3.2), (3.3), (3.4), (3.5) và Mệnh đề 1.1 ta dễ dàng có được điều cần chứng minh ở đây là: ev  . 2.3.2 Lược đồ thứ hai LD 1.02 Lược đồ LD 1.02 được phát triển từ dạng tổng quát với các lựa chọn: qrMHrMfrMf mod)||(),(),( 21  , )(),(3 MHrMf  , khóa công khai được tính theo công thức: pgy x mod . Các thuật toán hình thành tham số, hình thành và kiểm tra chữ ký được mô tả trong các bảng 2.1 và bảng 2.2 dưới đây. a) Thuật toán hình thành chữ k ý Bảng 2.1 Input: p, q, g, x, M. Output: (e,s) – chữ ký của U lên M. [1]. select k: qk 1 [2]. pgr k mod (4.1) Công nghệ thông tin & Khoa học máy tính N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký logarit rời rạc.” 108 [3]. qrMHe mod)||( (4.2) [4]. qMHxeks mod)](..[ 1   (4.3) [5]. return (e,s) Chú ý: “||” : toán tử nối 2 xâu bit. b) Thuật toán kiểm tra chữ k ý Bảng 2.2 Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. Output: (e,s) = true / false . [1]. pygu MHees mod)(..  (4.4) [2]. quMHv mod)||( (4.5) [3]. if ( ev  ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 1.02 Đặt: erMfrMf  ),(),( 21 và: )(),(3 MHrMf  . Theo (4.1), (4.2), (4.3), (4.4), (4.5) và Mệnh đề 1.1 ta có: ev  . Đây là điều cần chứng minh. 2.3.3 Lược đồ thứ ba LD 2.01 Lược đồ LD 2.01 được phát triển từ dạng tổng quát với các lựa chọn: )(),(2 MHrMf  , rrMf ),(3 , khóa công khai được tính theo công thức: pgy x mod . Các thuật toán hình thành tham số, hình thành và kiểm tra chữ ký được mô tả trong các bảng 3.1 và bảng 3.2 dưới đây. a) Thuật toán hình thành chữ k ý Bảng 3.1 Input: p, q, g, x, M. Output: (e,s) – chữ ký của U lên M. [1]. select k: qk 1 [2]. pgr k mod (5.1) [3]. qre mod (5.2) [4]. qrxMHks mod].)(.[ 1 (5.3) [5]. return (e,s) b) Thuật toán kiểm tra chữ k ý Bảng 3.2 Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. Output: (e,s) = true / false . [1]. pygu esMHs mod.)(.  (5.4) [2]. quv mod (5.5) [3]. if ( ev  ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 2.01 Đặt: )(),(2 MHrMf  , rrMf ),(3 . Theo (5.1), (5.2), (5.3), (5.4), (5.5) và Mệnh đề 1.2 ta có: ev  . Đây là điều cần chứng minh. 2.3.4. Lược đồ thứ tư LD 2.02 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 109 Lược đồ LD 2.02 được phát triển từ dạng tổng quát với các lựa chọn: qrMHrMfrMf mod)||(),(),( 21  , 1),(3 rMf , khóa công khai được tính theo công thức: pgy x mod . Các thuật toán hình thành tham số, hình thành và kiểm tra chữ ký được mô tả trong các bảng 4.1 và bảng 4.2 dưới đây. a) Thuật toán hình thành chữ k ý Bảng 4.1 Input: p, q, g, x, M. Output: (e,s) – chữ ký của U lên M. [1]. select k: qk 1 [2]. pgr k mod (6.1) [3]. qrMHe mod)||( (6.2) [4]. qxeks mod].[ 1 (6.3) [5]. return (e,s) b) Thuật toán kiểm tra chữ k ý Bảng 4.2. Input: p, q, g, y, M – Bản tin cần thẩm tra, (e,s) – Chữ k ý của U lên M. Output: (e,s) = true / false . [1]. pygu ses mod.  (6.4) [2]. quMHv mod)||( (6.5) [3]. if ( ev  ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 2.02 Đặt: qrMHrMfrMf mod)||(),(),( 21  , 1),(3 rMf . Theo (6.1), (6.2), (.3), (.4), (.5) và Mệnh đề 1.2 ta có: ev  . Đây là điều cần chứng minh. 2.4 Mức độ an toàn của các lược đồ mới đề xuất Mức độ an toàn của một lược đồ chữ k ý số nói chung được đánh giá qua các khả năng sau: a) Chống tấn công làm lộ khóa mật Ở các lược đồ mới đề xuất, khóa công khai của người k ý được hình thành từ khóa bí mật tương ứng theo: pgy x mod . Như vậy, khả năng chống tấn công làm lộ khóa mật của các lược đồ này phụ thuộc vào tính khó giải của bài toán logarit rời rạc. b) Chống tấn công giả mạo chữ ký Từ thuật toán kiểm tra của các lược đồ mới đề xuất cho thấy, một cặp (e,s) giả mạo sẽ được công nhận là chữ k ý hợp lệ với một bản tin M nếu thỏa mãn điều kiện được chỉ ra trong bảng 5 như sau: Bảng 5. Lược đồ Điều kiện để (e,s) là chữ k ý hợp lệ với bản tin M LD 1.01 qpyge MHeMHs mod)mod( )(.)(.  LD 1.02 qMpygHe MHees mod)||]mod([ )(..  LD 2.01 qpyge esMHs mod)mod( .)(.  LD 2.02 qMpygHe ses mod)||]mod([ .  Công nghệ thông tin & Khoa học máy tính N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký logarit rời rạc.” 110 Bản chất của việc tìm các (e,s) thỏa mãn điều kiện được chỉ ra trong bảng 5 là giải bài toán logarit rời rạc. Từ các kết quả nghiên cứu đã được công bố, có thể thấy rằng đây là một dạng bài toán khó nếu các tham số hệ thống được chọn đủ lớn để phương pháp vét cạn là không khả thi trong các ứng dụng thực tế. 3. KẾT LUẬN Bài báo đề xuất phương pháp phát triển lược đồ chữ k ý số dựa trên bài toán logarit rời rạc bằng việc xây dựng lược đồ dạng tổng quát, từ đó phát triển một số lược đồ có thể ứng dụng trong thực tế. Mức độ an toàn của các lược đồ mới đề xuất được đánh giá bằng mức độ khó giải của bài toán logarit rời rạc. Tuy nhiên, cũng cần phải thấy rằng, để sử dụng trong thực tế, các lược đồ này cần được đánh giá kỹ càng cả về mức độ an toàn cũng như khía cạnh hiệu quả thực hiện. TÀI LIỆU THAM KHẢO [1]. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", CRC Press, (1996). [2]. Hans Delfs, Helmut Knebl (2007), “Introduction to Cryptography: Principle and Applications”, Second Edition, Springer. [3]. T. ElGamal (1985), "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Transactions on Information Theory, 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. Standard Russian Federation. “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). ABSTRACT DEVELOPING THE DIGITAL SIGNATURE SCHEMES BASED ON THE DISCRETE LOGARITHM PROBLEM This paper proposes methods of developing digital signature scheme based on the difficulty of the discrete logarithm problem. From the establishment of overview scheme, some digital signature schema have been proposed for practical applications. Keywords: Digital Signature, Digital Signature Schema, Discrete logarithm problem. Nhận bài ngày 04 tháng 02 năm 2015 Hoàn thiện ngày 15 tháng 5 năm 2015 Chấp nhận đăng ngày 12 tháng 06 năm 2015 Địa chỉ: 1Trường CĐ Kinh tế - Kỹ thuật TP Hồ Chí Minh; . *Email: thuynguyenduc@hotec.edu.vn; 2Học viện Kỹ thuật Quân sự.