Tài liệu 15.bài 15_103_110

Nghiên cứu khoa học công nghệ 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 DLP( p , g ) đượ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: (1.1) g x mod p  y 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 DLP( p , g ) (.) 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): x  DLP( p , g ) ( y ) 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 DLP( p , g ) 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  x  ( p  1) , tính và công khai tham số: y  g x mod p (1.2) Chú ý: (i) Bài toán DLP( p , g ) 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 DLP( p , g ) đều khó, chẳng hạn những y  g x mod p 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 DLP( p , g ) ( y ) đề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. Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 103 Công nghệ thông tin & Khoa học máy tính 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*: g  h ( p 1) / q mod p , với: 1  h  p (2.1) 2. Tính khóa công khai: y  g  x mod p 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: 1  x  q .  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: 1  k  q . Tính giá trị r theo công thức: r  g k mod p (2.2) (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: e  r mod q (2.4) hoặc: e  f1 ( M , r ) mod q (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: (2.6) s  [ k . f 2 ( M , r ) 1  x. f 3 ( M , r )] mod q hoặc: s  k .[ f 2 ( M , r )  x. f 3 ( M , r )]1 mod q (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) f1 (M , r ), f 2 ( M , r ), f3 ( M , r ) : là các hàm của M, r và thỏa mãn điều kiện: 1  f1 ( M , r ), f 2 ( M , r ), f 3 ( M , r )  q  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ả 104 N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký … logarit rời rạc.” Nghiên cứu khoa học công nghệ 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: u  g s . f 2 ( M , r )  y f 2 ( M , r ). f 3 ( M , r ) mod p (2.8), nếu s được tính theo (2.6) hoặc: u  g s . f 2 ( M , r )  y s. f 3 ( M , r ) mod p (2.9), nếu s được tính theo (2.7) 2. Tính giá trị v: v  u mod q (2.10), nếu e được tính theo (2.4) hoặc: v  f1 (M , u ) mod q (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: g  h ( p 1 / q mod p thì: g q mod p  1 . Chứng minh: Ta có: g q mod p  (h ( p 1) / q mod p )q mod p  h( p 1) mod p Theo định lý Fermat thì: h( p 1) mod p  1 Vì vậy: g q mod p  1 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à g  h ( p 1 / q mod p . Nếu: m mod q  n mod q thì: g m mod p  g n mod p Chứng minh: Nếu: m mod q  n mod q 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 đó: g m mod p  g n  k .q mod p  g n  g k .q mod p  ( g n mod p ).( g k .q mod p) mod p  ( g n mod p ).( g q mod p ) k mod p Theo Bổ đề 1.1 ta có: g q mod p  1 Nên: g m mod p  g n .1k mod p  g n mod p Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 105 Công nghệ thông tin & Khoa học máy tính 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 1  x , k  q . Nếu: nhỏ hơn p và g  h ( p 1 / q mod p , y  g  x mod p , r  g k mod p , e  r mod q hoặc: e  f1 ( M , r ) mod q , s  [ k . f 2 ( M , r ) 1  x. f 3 ( M , r )] mod q với: 1  f1 ( M , r ), f 2 ( M , r ), f 3 ( M , r )  q , u  g s . f 2 ( M , r )  y f 2 ( M , r ). f 3 ( M , r ) mod p , v  u mod q hoặc: v  f1 ( M , u ) mod q thì: v e. Chứng minh: Thật vậy, ta có: s  [ k . f 2 ( M , r ) 1  x. f 3 ( M , r )] mod q  f 2 ( M , r ) 1 .[k  x. f 2 ( M , r ). f 3 ( M , r )] mod q Nên: s. f 2 ( M , r ) mod q  [k  x. f 2 ( M , r ). f 3 ( M , r )] mod q Theo Bổ đề 2.2 ta có: g s. f 2 ( M , r ) mod p  g k  x . f 2 ( M , r ). f 3 ( M , r ) mod p Suy ra: g s. f 2 ( M ,r )  g  x . f 2 ( M , r ). f 3 ( M , r ) mod p  g k mod p Hay: g s. f 2 ( M , r )  y f 2 ( M , r ). f 3 ( M , r ) mod p  g k mod p Từ (2.3) và (2.13) ta có: u  r Do đó: v  u mod q  r mod q v  f1 ( M , u ) mod q  f1 ( M , r ) mod q hoặc: Từ (2.4) và (2.14) hoặc từ (2.5) và (2.15) suy ra: ve (2.13) (2.14) (2.15) Đâ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à g  h ( p 1 / q mod p , , 1  x , k  q . Nếu: y  g x mod p e  f1 ( M , r ) mod q , e  r mod q hoặc: r  g k mod p , 1 s  k .[ f 2 ( M , r )  x. f 3 ( M , r )] mod q với: 1  f1 ( M , r ), f 2 ( M , r ), f 3 ( M , r )  q , u  g s . f 2 ( M , r )  y s. f 3 ( M , r ) mod p , v  u mod q hoặc: v  f1 ( M , u ) mod q thì: v  e . Chứng minh: Thật vậy, từ (2.7) ta có: k  s.[ f 2 ( M , r )  x. f 3 ( M , r )] mod q (2.16) Theo Bổ đề 2.2 và (2.16) suy ra: g s. f 2 ( M , r )  g x. s. f 3 ( M , r ) mod p  g k mod p hay: g s. f 2 ( M , r )  y s . f 3 ( M , r ) mod p  g k mod p (2.17) Từ (2.3) và (2.17) ta có: ur Do đó: v  u mod q  r mod q v  f1 ( M , u ) mod q  f1 ( M , r ) mod q hoặc: Từ (2.4) và (2.18) hoặc từ (2.5) và (2.19) suy ra: v  e (2.18) (2.19) Đây là điều cần chứng minh. 106 N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký … logarit rời rạc.” Nghiên cứu khoa học công nghệ 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: f 2 ( M , r )  H ( M ) mod q , f 3 ( M , r )  ( g k mod p ) mod q , ở đâ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: y  g  x mod p . 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: 1  k  q [2]. r  g k mod p [3]. e  r mod q [4]. s  [k .H ( M ) 1  x.e ] mod q [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. (3.1) (3.2) (3.3) 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]. u  g s . H ( M )  y e. H ( M ) mod p [2]. v  u mod q [3]. if ( v  e ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 1.01 (3.4) (3.5) Đặt: f 2 ( M , r )  H ( M ) mod q , f 3 ( M , r )  e . 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à: v  e . 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: f1 (M , r )  f 2 (M , r )  H ( M || r ) mod q , f3 ( M , r )  H ( M ) , khóa công khai được tính theo công thức: y  g  x mod p . 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: 1  k  q [2]. r  g k mod p Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 (4.1) 107 Công nghệ thông tin & Khoa học máy tính [3]. e  H ( M || r ) mod q [4]. s  [ k .e 1  x.H ( M )] mod q [5]. return (e,s) Chú ý: “||” : toán tử nối 2 xâu bit. b) Thuật toán kiểm tra chữ ký (4.2) (4.3) 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]. u  g s .e  y e. H ( M ) mod p (4.4) [2]. v  H ( M || u ) mod q (4.5) [3]. if ( v  e ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 1.02 Đặt: f1 (M , r )  f 2 ( M , r )  e và: f 3 ( M , r )  H ( M ) . Theo (4.1), (4.2), (4.3), (4.4), (4.5) và Mệnh đề 1.1 ta có: v  e . Đâ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: f 2 ( M , r )  H (M ) , f 3 ( M , r )  r , khóa công khai được tính theo công thức: y  g x mod p . 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: 1 k  q [2]. r  g k mod p [3]. (5.1) e  r mod q (5.2) 1 [4]. s  k .[ H ( M )  x.r ] mod q [5]. return (e,s) (5.3) 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]. u  g s .H ( M )  y s .e mod p (5.4) [2]. v  u mod q (5.5) [3]. if ( v  e ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 2.01 Đặt: f 2 ( M , r )  H ( M ) , f 3 ( M , r )  r . Theo (5.1), (5.2), (5.3), (5.4), (5.5) và Mệnh đề 1.2 ta có: v  e . Đây là điều cần chứng minh. 2.3.4. Lược đồ thứ tư LD 2.02 108 N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký … logarit rời rạc.” Nghiên cứu khoa học công nghệ 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: f1 (M , r )  f 2 (M , r )  H ( M || r ) mod q , f3 ( M , r )  1 , khóa công khai được tính theo công thức: y  g x mod p . 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: 1  k  q [2]. r  g k mod p [3]. e  H ( M || r ) mod q [4]. s  k .[e  x]1 mod q [5]. return (e,s) (6.1) (6.2) (6.3) 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]. u  g s .e  y s mod p (6.4) [2]. v  H ( M || u ) mod q (6.5) [3]. if ( v  e ) then {return true } else {return false } c) Tính đúng đắn của lược đồ LD 2.02 Đặt: f1 (M , r )  f 2 (M , r )  H ( M || r ) mod q , f3 ( M , r )  1 . Theo (6.1), (6.2), (.3), (.4), (.5) và Mệnh đề 1.2 ta có: v  e . Đâ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: y  g  x mod p . 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 e  ( g s. H ( M )  y e. H ( M ) mod p ) mod q LD 1.02 e  H ([ g s .e  y e. H ( M ) mod p] || M ) mod q LD 2.01 e  ( g s .H ( M )  y s .e mod p) mod q LD 2.02 e  H ([ g s .e  y s mod p ] || M ) mod q Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 109 Công nghệ thông tin & Khoa học máy tính 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: [email protected]; 2 Học viện Kỹ thuật Quân sự. 110 N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký … logarit rời rạc.”