Luận văn Nghiên cứu, phát triển các lược đồ chữ ký số tập thể

tra chữ k ý tập thể (Thuật toán 1.13) nhằm ngăn chặn việc mạo danh các đối tượng k ý. Ngoài ra, có thể kiểm tra tính hợp pháp của đối tượng k ý một cách độc lập bằng Thuật toán 1.10b. Tính đúng đắn của các thuật toán chứng nhận và kiểm tra tính hợp pháp đối tượng k ý được chứng minh như sau: Đặt: e1 = 1, e2 = ui, e3 = t, k = ki, r = ri, s = vi, x = xCA, y = yCA. Theo (2.17), (2.18), (2.20) và Mệnh đề 1.1 ta có: vi t mod n = ri . yCA -ui mod n (2.36) Từ (2.36) suy ra: ri = vi t . y CA -ui mod n (2.37) Từ (2.21) và (2.37) ta có: r* = ri (2.38) Thay (2.38) vào (2.22), ta được: u = H(ri ||yi ||IDi) (2.39) Từ (2.39) và (2.19) suy ra: u = ui. Đây là điều cần chứng minh. b) Tính đúng đắn của thuật toán hình thành và kiểm tra chữ k ý cá nhân của một đối tượng k ý. Hình thành chữ k ý cá nhân của một đối tượng k ý được thực hiện ở các 39 bước từ [1] đến [4], còn kiểm tra chữ k ý cá nhân được thực hiện ở bước thứ [5] của thuật toán hình thành chữ k ý của một hay một nhóm đối tượng lên một thông điệp dữ liệu (Thuật toán 1.11). Tính đúng đắn của thuật toán hình thành và kiểm tra chữ ký cá nhân của đối tượng k ý được chứng minh như sau: Đặt: e1 = 1, e2 = ui, e3 = t, s = si, x = xi, k = ki, y = yi , r = ri. Theo (2.16), (2.23), (2.24), (2.25), (2.26) và Mệnh đề 1.1, ta có: si t mod n = ri . yi -e mod n (2.40) Từ (2.40) suy ra: r i = si t. yi e mod n Đây là điều cần chứng minh. c) Tính đúng đắn của thuật toán chứng nhận và kiểm tra chứng nhận của CA đối với chữ k ý cá nhân của một hay một nhóm đối tượng k ý. Hình thành chứng nhận của CA đối với chữ k ý cá nhân của một hay một nhóm đối tượng ký lên một thông điệp dữ liệu được thực hiện bằng Thuật toán 1.12. Kiểm tra tính hợp lệ chứng nhận của CA được thực hiện ở bước [2] của thuật toán kiểm tra chữ ký tập thể (Thuật toán 1.13). Tính đúng đắn của thuật toán hình thành và kiểm tra chứng nhận của CA được chứng minh như sau: Đặt: e1 = 1, e2 = uM, e3 = t, s = vM, y = yCA. Theo (2.17), (2.28), (2.29), (2.30) và Mệnh đề 1.1, ta có: v M t mod n = r .yCA -u M mod n (2.41) Từ (2.41) suy ra: r = v M t . y CA -u M mod n (2.42) Từ (2.32) và (2.42) ta có: r* = r (2.43) Thay (2.43) vào (2.33), ta được: u = H(r||y ||M) (2.44) 40 Từ (2.29) và (2.44) suy ra: u = u M Đây là điều cần chứng minh. d) Tính đúng đắn của thuật toán hình thành và kiểm tra chữ k ý của một nhóm đối tượng lên một thông điệp dữ liệu. Mệnh đề 1.2: Cho p, q là 2 số nguyên tố phân biệt, n = p.q, 1 < x < n, 1 < e1, e2, e3 < (p-1).(q-1), 1 < xi, ki < n (i=1, 2,...,m). Nếu: yi = xi e3 mod n, ri = ki e3 mod n, si = ki e1. xi e2 mod n, r = Õ = m i ir 1 mod n, s = Õ = m i is 1 mod n thì: se3 mod n = re1 . ye2 mod n. Chứng minh Thật vậy, ta có: se3 mod n = (Õ = m i is 1 mod n ) e3 mod n = (Õ = m i e ik 1 1 mod n) e3 . (Õ = m i e ix 1 2 mod n) e3 mod n = (Õ = m i e ik 1 3 mod n) e1 . (Õ = m i e ix 1 3 mod n) e2 mod n = (Õ = m i ir 1 mod n) e1 . (Õ = m i iy 1 mod n) e2 mod n = re1 . ye2 mod n Chữ k ý nhóm (e,s) hay chữ k ý cá nhân của một nhóm đối tượng k ý lên một thông điệp dữ liệu (M) được hình thành bằng Thuật toán 1.11. Kiểm tra tính đúng đắn của chữ k ý nhóm được thực hiện ở bước [2] của thuật toán CA chứng nhận cho {M,(e,s)} (Thuật toán 1.12) và bước [3] của thuật toán kiểm tra chữ k ý tập thể (Thuật toán 1.13). Tính đúng đắn của thuật toán hình thành và kiểm tra chữ ký nhóm được 41 chứng minh như sau: Đặt: e1 = 1, e2 = e, e3 = t. Theo (2.24), (2.25), (2.27), (2.31) và Mệnh đề 1.2, ta có: st mod n = r . y-e mod n (2.45) Từ (2.45) suy ra: r = st . ye mod n (2.46) Từ (2.46) và (2.34) ta có: u = r (2.47) Thay (2.47) vào (2.35), ta được: v = H(r||M) (2.48) Từ (2.48) và (2.25) suy ra: v = e Đây là điều phải chứng minh. 2.3.1.5 Mức độ an toàn của lược đồ LD 1.02 Mức độ an toàn của lược đồ chữ k ý tập thể LD 1.02 được thiết lập dựa trên độ an toàn của lược đồ cơ sở LD 1.01. Vì vậy, lược đồ chữ k ý tập thể LD 1.02 cần phải tuân thủ các điều kiện an toàn đã được chỉ ra ở lược đồ cơ sở LD 1.01. Ngoài ra, ở các lược đồ chữ ký tập thể còn tiềm ẩn các nguy cơ tấn công giả mạo chữ k ý từ bên trong hệ thống [21]. Vấn đề này được xem xét dưới góc độ Bài toán giả mạo chữ ký như sau: a) Bài toán giả mạo chữ k ý nhóm Cho U và U* với U Ë U* là hai nhóm các đối tượng trong hệ thống tương ứng với cặp tham số {n,t}. Khi này Bài toán giả mạo chữ ký nhóm có thể được mô tả như sau: Bài toán LD1(U,U*): Cho các tham số bí mật của các thành viên trong U*. Khi đó với mỗi thông báo M, hãy tìm cặp {e,s} được chấp nhận theo điều kiện 42 của thuật toán kiểm tra chữ k ý (Thuật toán 1.12) với đầu vào là bộ tham số công khai của U. Mỗi giải thuật cho bài toán LD1(U,U*) được gọi là "thuật toán giả mạo chữ ký của U lên M do U* thực hiện". Để khảo sát tính an toàn của lược đồ LD 1.02, trước tiên cần xây dựng hai giải thuật toán lần lượt cho các bài toán LD1(U,U*) và LD1(U',U*) với: U* = {U*i| i=1...m*}, U' = {U'i| i=1...m'}, U*ÇU' = Æ và U*ÈU' = U. (2.49) Hai tập U* và U' thỏa mãn (2.49) còn được gọi là một phân hoạch của U và phép toán U*ÈU' còn được ký hiệu là U*+U'. Thuật toán 1.14. Thuật giải cho bài toán LD1(U,U*). Input: n, t, M, (e’,s’) – chữ ký của U' lên M. Output: (e,s) – chữ ký (giả mạo) của U lên M do U* tạo ra. [1]. s* = 1; [2]. for i = 1 to m* do s* = s*. (xi) e’mod n; (2.50) [3]. s = s’. s* mod n; (2.51) [4]. e = e’; (2.52) [5]. return (e,s); Thuật toán 1.14 cho phép U* từ chữ k ý của U’ tạo được chữ k ý của U lên M. Tính đúng đắn của Thuật toán 1.14 được chứng minh như sau: Từ (2.50) với mọi: i = 1,2,..,m*, ta có: (si*) t . (yi*) e mod n = (xi*) e.t . (xi*) -e.t mod n = 1 (2.53) Với điều kiện trong (2.49), dễ dàng kiểm tra được rằng: 43 y = (y'.Õ = *m 1i * iy ) mod n (2.54) Từ (2.53) và (2.54) ta có: st. ye mod n = (s'.Õ = *m 1i * is ) t.(y'.Õ = *m 1i * iy ) e mod n = (s')t.(y')e.Õ = *m 1i e* i t* i )y()s( mod n = (s')t. (y')e’ mod n = r' (2.55) Từ (2.55) và (2.34) suy ra: u = r’ (2.56) Thay (2.56) vào (2.35) ta được: v = H(r’||M) = e’ (2.57) Từ (2.57) và (2.52) ta có: v = e Như vậy, mặc dù (e,s) do U* tạo ra nhưng vẫn được công nhận là chữ k ý hợp lệ của U lên M, Thuật toán 1.14 đã được chứng minh là đúng. Thuật toán 1.15. Thuật giải cho bài toán LD1(U',U*). Input: n, t, M, (e,s) - chữ ký của U lên M. Output: (e’,s’) - chữ ký (giả mạo) của U' lên M do U* tạo ra. [1]. s* = 1; [2]. for i = 1 to m* do s* = s*. (xi) e mod n; (2.58) [3]. s’ = s . (s*)-1 mod n; (2.59) [4]. e’ = e; (2.60) [5]. return (e’,s’); 44 Thuật toán 1.15 cho phép U* từ chữ k ý của U tạo được chữ k ý của U’ lên M. Chứng minh tính đúng đắn của thuật toán 1.15 như sau: Từ (2.58) với mọi: i = 1,2,..,m*, ta có: (si*) - t . (yi*) - e mod n = (xi*) - e.t . (xi*) e.t mod n = 1 (2.61) Với điều kiện (2.49), dễ dàng kiểm tra được rằng: y’ = (y.Õ = - *m 1i 1* i )y( ) mod n (2.62) Từ việc các tham số mật x của mọi thành viên đều có tham số công khai y tương ứng được xác định theo (2.16), điều này có nghĩa các giá trị si*(i=1,2,..,m*) tính theo công thức (2.26) đều có giá trị nghịch đảo theo modulo n, do đó việc tính s' theo (2.59) là thực hiện được. Vì vậy, từ (2.61) và (2.62) ta có: (s')t.(y')e’ mod n = (s.Õ = - *m 1i 1* i )s( ) t .(y.Õ = - *m 1i 1* i )y( ) e mod n = (s) t .(y) e .Õ = - *m 1i 1e* i t* i ))y()s(( mod n = st. ye mod n = r (2.63) Từ (2.63) và (2.34) suy ra: u = r (2.64) Thay (2.64) vào (2.35) ta được: v = H(r||M) = e (2.65) Từ (2.65) và (2.55) ta có: v = e’ Như vậy, (e’,s’) là do U* tạo ra nhưng vẫn được công nhận là chữ k ý hợp lệ của U' lên M, nói cách khác: Thuật toán 1.15 đã được chứng minh là đúng. 45 b) Sự an toàn của lược đồ LD 1.02 trước các tấn công giả mạo chữ ký nhóm. Bài toán LD1(U,U*), LD1(U’,U*) chỉ ra khả năng tấn công giả mạo từ bên trong hệ thống do một nhóm con (U*) của một nhóm đối tượng k ý (U) gây ra. Từ đó cho thấy, việc giả mạo chữ k ý cá nhân của một hay một nhóm đối tượng ký ở lược đồ LD 1.02 là có khả năng thực hiện được. Tuy nhiên, bằng việc sử dụng chứng nhận của CA, mà thực chất là chữ k ý của CA lên thông điệp dữ liệu cần ký M và khóa công khai chung của nhóm ký, như là một phần của chữ k ý tập thể thì sự giả mạo này hoàn toàn có thể phát hiện được. Nói cách khác, lược đồ LD 1.02 có khả năng chống được các dạng tấn công giả mạo từ bên trong hệ thống đã được biết đến trong thực tế [8],[33],[34], [35],[36]. 2.3.2 Lược đồ chữ ký tập thể LD 1.03 Lược đồ chữ ký tập thể - ký hiệu LD 1.03, cũng được phát triển từ lược đồ cơ sở LD 1.01với các chức năng tương tự như lược đồ LD 1.02. Điểm khác nhau giữa 2 lược đồ là: LD 1.02 không qui định thứ tự k ý của các thành viên trong nhóm, còn ở LD 1.03 chữ ký của nhóm được hình thành từ 3 yếu tố: - Thông điệp dữ liệu cần ký M. - Khóa bí mật của các thành viên KS. - Thứ tự ký của các thành viên trong nhóm . Như vậy ở lược đồ LD 1.03, chữ k ý cá nhân của một nhóm đối tượng và do đó là chữ k ý tập thể tương ứng chỉ có thể được tạo ra khi các thành viên thực hiện đúng thứ tự k ý đã qui định. Điều đó cũng có nghĩa là, một chữ k ý tập thể do lược đồ LD 1.03 tạo ra, khi được công nhận là hợp lệ thì nó khẳng định đồng thời các yếu tố: - Tính toàn vẹn của thông điệp dữ liệu được thẩm tra. 46 - Nguồn gốc của thông điệp dữ liệu ở 2 cấp độ cá nhân của đối tượng hay nhóm nhóm đối tượng k ý và tổ chức mà các đối tượng ký là thành viên của nó. - Trình tự k ý của các thành viên trong nhóm ký. Lược đồ LD 1.03 được xây dựng với các thuật toán hình thành tham số và khóa, thuật toán chứng nhận và kiểm tra tính hợp pháp của các đối tượng k ý, thuật toán hình thành chứng nhận của CA đối với chữ k ý của một hay một nhóm đối tượng ký lên một thông điệp dữ liệu và thuật toán kiểm tra chữ k ý tập thể là hoàn toàn như các thuật toán tương ứng của lược đồ LD 1.02. Chỉ có thuật toán hình thành chữ k ý cá nhân của một hay một nhóm đối tượng lên thông điệp dữ liệu được xây dựng mới nhằm bảo đảm qui định về thứ tự k ý của các thành viên trong nhóm, đây là điểm khác biệt duy nhất giữa 2 lược đồ này. Vì vậy, mục này (2.3.2) chỉ trình bày Thuật toán hình thành chữ ký cá nhân của một hay một nhóm đối tượng k ý lên một thông điệp dữ liệu và chứng minh tính đúng đắn của nó, bao gồm cả tính đúng đắn của thuật toán kiểm tra thứ tự k ý của các thành viên trong nhóm. 2.3.2.1 Thuật toán hình thành chữ ký cá nhân của một nhóm đối tượng lên một thông điệp dữ liệu. Giả sử nhóm ký gồm m thành viên: U = {Ui| i=1,2,...,m}. Các thành viên nhóm ký có khóa bí mật là: KS = {xi| i=1,2,...,m} và các khóa công khai tương ứng là: KP = {yi| i=1,2,...,m}. Trong thực tế, thứ tự k ý của các thành viên trong nhóm được qui định bởi vai trò, chức trách (chức vụ, quyền hạn,...) của mỗi thành viên trong tổ chức. Không làm mất tính tổng quát, ở lược đồ mới đề xuất giả thiết rằng thứ tự ký của các thành viên được qui định là chỉ số i gán cho các tham số cá nhân (xi, yi, ri, si, ...) cuả mỗi thành viên trong nhóm. Cụ thể là, thành viên có chỉ số i = 1 sẽ là người ký đầu tiên, còn thành viên có chỉ số i = m sẽ ký sau cùng. 47 Cũng như ở lược đồ LD 1.02, các yêu cầu đặt ra khi hình thành chữ ký cá nhân của nhóm k ý ở đây là: - Độ dài của chữ ký không phụ thuộc số lượng thành viên nhóm ký. - Chữ ký chỉ được tạo ra khi có đủ số lượng thành viên tham gia ký. - Chữ ký được thẩm tra nhờ khóa công khai chung của nhóm, mà khóa công khai chung này được hình thành từ đầy đủ các khóa công khai riêng của mỗi thành viên . - Việc thẩm tra chữ ký của một nhóm m-đối tượng k ý thực hiện hoàn toàn như với chữ ký được tạo ra bởi 1 đối tượng k ý. Thuật toán 1.16: Hình thành chữ ký của một nhóm đối tượng lên thông điệp dữ liệu M theo kiểu k ý tuần tự. Input: n, t, M, m, KS = {xi| i=1,2,..,m}, KP = {yi| i=1,2,..,m}. Output: (e,s) – chữ k ý U lên M. [1]. for i = 1 to m do [1.1]. ki ← H(xi||M); [1.2]. ri ← (ki) t mod n; (2.66) [1.3]. send ri to {U1, U2,..., Ui-1, Ui+1,..., Um} [2]. r ← 1; for i = 1 to m do r ← r . ri mod n; (2.67) [3]. e ← H(r||M); (2.68) [4]. s0 ← 1; Y0 ← 1; R0 ← 1; [5]. for i = 1 to m do 48 [5.1]. Yi-1 ← y1 . y2 .... yi-1 mod n; (2.69) [5.2]. Ri-1 ← r1 . r2 .... ri-1 mod n; (2.70) [5.3]. if (Ri-1 ≠ ((si-1) t . (Yi-1) e mod n)) then return (0,0); (2.71) [5.4]. si ← si-1 . ki . (xi ) e mod n; (2.72) [5.5] if (i < m) then {send si to Ui+1 } else s = si ; [6]. return (e,s); Chú ý: Trường hợp hình thành chữ k ý của một đối tượng lên thông điệp dữ liệu thì chỉ cần thực hiện Thuật toán 1.16 với lựa chọn m = 1. 2.3.2.2 Tính đúng đắn của lược đồ LD 1.03 Tính đúng đắn của lược đồ mới đề xuất bao gồm:a) Tính đúng đắn của các thuật toán chứng nhận và kiểm tra tính hợp pháp của đối tượng k ý, thuật toán hình thành và kiểm tra chứng nhận của CA đối với chữ k ý của một hay một nhóm đối tượng k ý lên một thông điệp dữ liệu, thuật toán kiểm tra chữ k ý tập thể được chứng minh tương tự như các thuật toán tương ứng của lược đồ LD 1.02. b) Tính đúng đắn của thuật toán kiểm tra thứ tự k ý của các thành viên trong một nhóm k ý. Kiểm tra thứ tự k ý của các thành viên trong nhóm ký được thực hiện ở các bước từ [5.1] đến [5.3] của Thuật toán 1.16. Việc kiểm tra này cho phép một đối tượng Ui có thể khẳng định được các đối tượng: U1, U2,..,Ui-1 đã k ý hay chưa? Chứng minh tính đúng đắn của thuật toán kiểm tra thứ tự k ý được thực hiện như sau: Từ (2.72) ta có: si-1 = si-2 . ki-1.(xi-1) e mod n = k1.k2...ki-1.(x1.x2...xi-1) e mod n (2.73) 49 Đặt: e1 = 1, e2 = e, e3 = t, y = Yi-1, r = Ri-1, s = si-1. Theo (2.69), (2.70), (2.73) và Mệnh đề 1.2, ta có: (si-1) t = Ri-1 . (Yi-1) -e mod n (2.74) Từ (2.74) suy ra: Ri-1 = ((si-1) t . (Yi-1) e mod n Đây là điều phải chứng minh. c) Tính đúng đắn của thuật toán hình thành và kiểm tra chữ k ý nhóm. Từ (2.70) ta có: s = sm = k1.k2...km.x1 e . x2 e...xm e mod n = Õ = m i ik 1 . Õ = m i e ix 1 mod n (2.75) Do đó, nếu đặt: e1 = 1, e2 = e, e3 = t . Theo (2.31), (2.66), (2.67), (2.75) và Mệnh đề 1.2, ta có: st mod n = r . y-e mod n (2.76) Từ (2.76) suy ra: r = st . ye mod n (2.77) Từ (2.43) và (2.77) ta có: u = r (2.78) Thay (2.78) vào (2.35), ta được: v = H(r||M) (2.79) Từ (2.68) và (2.79) suy ra: v = e Đây là điều phải chứng minh. 50 2.3.2.3 Mức độ an toàn của lược đồ LD 1.03 Việc phân tích, đánh giá mức độ an toàn của lược đồ LD 1.03 thực hiện tương tự như với lược đồ LD 1.02. Ở lược đồ LD 1.03, thứ tự k ý của các thành viên được xem như một khía cạnh về tính an toàn của lược đồ. Thủ tục kiểm tra thứ tự k ý bao gồm các bước từ [5.1] đến [5.3] của Thuật toán 1.16, thủ tục này cho phép mỗi đối tượng k ý Ui (i = 1,2,...,m) có thể kiểm tra và khẳng định được các đối tượng có trách nhiệm k ý trước đã thực hiện xong phần công việc của mình hay chưa? Đây là yêu cầu thực tế đặt ra mà các lược đồ chữ k ý tập thể theo kiểu tuần tự cần phải bảo đảm được. 2.4 Kết luận Chương 2 Các kết quả đã đạt được ở Chương 2 bao gồm 3 lược đồ chữ ký số mới, bao gồm một lược đồ cơ sở (LD 1.01) và 2 lược đồ chữ k ý tập thể (LD 1.02, LD 1.03). Trong đó, lược đồ cơ sở LD 1.01 là một dạng lược đồ chữ k ý số mới, được xây dựng trên cơ sở bài toán khai căn trên vành số nguyên Zn=p.q với {p,q} là các số nguyên tố phân biệt. Hai lược đồ chữ k ý tập thể là kết quả được phát triển từ lược đồ cơ sở theo mô hình ứng dụng được đề xuất ở Chương 1. 51 CHƯƠNG 3 XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TẬP THỂ DỰA TRÊN HỆ MẬT ELGAMAL Nội dung Chương 3 đề xuất xây dựng lược đồ chữ ký tập thể dựa trên hệ mật ElGamal theo mô hình ứng dụng đã được trình bày ở Chương 1. 3.1 Cơ sở toán học 3.1.1 Bài toán logarit rời rạc trên trường hữu hạn nguyên tố ZP 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 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: g x mod p = y (3.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 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 (3.1): x = DLP(p,g)(y) Tương tự như bài toán RSA(n,t), 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 (3.2) 52 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 (3.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. 3.1.2 Hệ mật ElGamal Hệ mật ElGamal được xây dựng dựa trên tính khó của bài toán DLP(p,g) nói trên và do T. El Gamal đề xuất vào năm 1985 [5]. Không như RSA, hệ mật này bao gồm 2 thuật toán mật mã khóa công khai và chữ k ý số độc lập. Các chuẩn chữ k ý số DSA của Hoa Kỳ [19] và GOST R34.10-94 của Liên bang Nga [10] đều là các biến thể của thuật toán chữ k ý số El Gamal và được gọi chung là các thuật toán chữ k ý số họ ElGamal. Trên thực tế, chưa có phương pháp tấn công hiệu quả nào phá vỡ được hệ mật ElGamal nói chung và các thuật toán chữ k ý số họ ElGamal nói riêng [9],[26],[28],[29] nếu các tham số của nó được lựa chọn phù hợp. Cũng như hệ mật RSA với bài toán khai căn trên vành Zn, có thể coi hệ mật ElGamal là một đánh giá thực tế cho tính khó giải của bài toán DLP(p,g). 3.2 Xây dựng lược đồ cơ sở Lược đồ cơ sở đề xuất ở đây được xây dựng dựa trên bài toán logarit rời rạc theo cùng nguyên tắc với các thuật toán chữ k ý số họ ElGamal (DSA, GOST R34.10-94). Lược đồ này sẽ được sử dụng để xây dựng các lược đồ chữ ký tập thể theo mô hình ứng dụng được đề xuất ở Chương 1. 53 3.2.1 Lược đồ cơ sở dạng tổng quát n 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. 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ý. n Phương pháp hình thành chữ ký Dữ liệu vào: p, q, g, x, k, M. Kết quả: (r,s). Các bước thực hiện: 1. Hình thành phần thứ nhất của chữ k ý theo công thức: r = (gk mod p) mod q; 2. Hình thành phần thứ nhất của chữ k ý theo công thức: s = k.f1(M,r) -1 + x.f2(M,r) mod q; Chú thích: (i) M: thông điệp dữ liệu cần k ý. (ii) (r,s): chữ ký lên M của đối tượng sở hữu {x,y}. n Phương pháp kiểm tra chữ ký Dữ liệu vào: p, q, g, y, M, (r,s). Kết quả: Khẳng định (r,s) là chữ k ý hợp lệ ((r,s) = true) hay (r,s) là giả mạo và/hoặc M không còn toàn vẹn ((r,s) = false). Các bước thực hiện: 54 1. Tính giá trị: u = (g s.f1(M,r) . y f1(M,r).f2(M,r) mod p) mod q; 2. Nếu u = r thì (r,s) = true, ngược lại: (r,s) = false. 3.2.2 Lược đồ cơ sở LD 2.01 Lược đồ cơ sở - k ý hiệu LD 2.01, được hình thành từ lược đồ cơ sở dạng tổng quát với lựa chọn: f1(M,r) = H(M), f2(M,r) = r. 3.2.2.1 Thuật toán hình thành tham số và khóa Thuật toán 2.1a: Hình thành các tham số hệ thống. Input: lp, lq: độ dài (tính theo bit) của số nguyên tố p, q. Output: p, q, g, H(.). [1]. select p, q: len(p) = lp, len(q)= lq, q|(p-1); [2]. select h Î ℤp* ; [3]. g ← h (p-1)/q mod p (3.3) [4]. if (g = 1) then goto [2]; [5]. select H: {0,1}* → Zq ; [6]. return {p, q, g, H(.)}; Chú thích: len(.) là hàm tính độ dài (theo bit) của một số. Thuật toán 2.1b: Hình thành khóa. Input: p, q, g, x. Output: y. [1]. y ← g-x mod p; (3.4) [2]. return (y); 55 3.2.2.2 Thuật toán hình thành chữ k ý. Thuật toán 2.2: Hình thành chữ ký. Input: p, q, g, x, k , M, H(.). Output: (r,s). [1]. e ← H(M); (3.5) [2]. r ← (gk mod p) mod q; (3.6) [3]. s ← k. e-1 + x. r mod q; (3.7) [4]. return (r,s); 3.2.2.3 Thuật toán kiểm tra chữ k ý Thuật toán 2.3: Kiểm tra chữ ký. Input: p, q, g, y, H(.), M, (r,s). Output: (r,s) = true / false. [1]. e ← H(M); (3.8) [2]. u ← (gs.e. yr.e mod p) mod q; (3.9) [3]. if (u = r) then {return true;} (3.10) else {return false;} 3.2.2.4 Tính đúng đắn của lược đồ LD 2.01 Bổ đề 2.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ó: gq 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: 56 gq mod p = 1 Bổ đề đã được chứng minh. Bổ đề 2.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ì: gm mod p = gn 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 đó: gm mod p = gn + k.q mod p = gn. g k.q mod p = (gn mod p).(gk.q mod p) mod p = (gn mod p). (gq mod p)k mod p Theo Bổ đề 2.1 ta có: gq mod p = 1 Nên: gm mod p = (gn mod p). 1k mod p = gn mod p Bổ đề đã được chứng minh. Mệnh đề 2.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à g = h (p-1)/q mod p, 1 < x, k < p, 1 < e1, e2 < q. Nếu: y = g–x mod p, r = (gk mod p) mod q, s = k. e1 -1 + x. e2 mod q thì: (g e1.s . y e1.e2 mod p) mod q = r. Chứng minh: Thật vậy, ta có: s = k. e1 -1 + x. e2 mod q = e1 -1. (k + x.e1.e2) mod q 57 Nên: e1. s mod q = k + x.e1.e2 mod q Theo Bổ đề 2.2 ta có: g e1.s mod p = g k + x.e1.e2 mod p Suy ra: g e1.s . g -x.e1.e2 mod p = g k mod p Hay: g e1.s . y e1.e2 mod p = g k mod p Nên ta có: (gk mod p) mod q = (g e1.s . y e1.e2 mod p) mod q Do: r = (gk mod p) mod q Dẫn đến: (g e1.s . y e1.e2 mod p) mod q = r Đây là điều cần chứng minh. Chứng minh tính đúng đắn của lược đồ LD 2.01 là chứng minh chữ k ý được tạo ra bởi thuật toán hình thành chữ ký (Thuật toán 2.2) sẽ thỏa mãn điều kiện (3.10) của thuật toán kiểm tra chữ ký (Thuật toán 2.3). Tính đúng đắn của lược đồ LD 2.01 được chứng minh như sau: Đặt: e1 = e, e2 = r. Theo (3.3), (3.4), (3.5), (3.6), (3.7) và Mệnh đề 2.1 ta có: (gs.e . yr.e mod p) mod q = r (3.11) Từ (3.8), (3.11) ta có: (gs.e . yr.e mod p) mod q = r (3.12) Từ (3.9) và (3.12) suy ra: u = r. Đây là điều cần chứng minh. 58 3.2.2.5 Mức độ an toàn của lược đồ LD 2.01 Mức độ an toàn của lược đồ mới đề xuất được đánh giá bằng: a) Khả năng chống tấn công làm lộ khóa mật Tương tự như DSA và GOST R34.10-94, khả năng chống tấn công làm lộ khóa mật ở lược đồ mới đề xuất phụ thuộc vào mức độ khó của Bài toán DLP(p,g). Một số dạng của giải thuật DLP(p,g)(.) đã được biết đến như các thuật toán Baby-step Giant-step, Pollard’s rho, Pohlig-Hellman, Index-Calculus,... [18], [22], [28]. Trong ứng dụng thực tế, các tham số hệ thống {p,q,g} của lược đồ LD 2.01 có thể hình thành theo phương pháp của DSA đã được chỉ ra trong FIPS 186-3 [19], hay theo phương pháp hình thành tham số của GOST R34.10-94 [10]. Khi đó, từ (3.3), (3.4), (3.6), (3.7) cho thấy mức độ an toàn xét theo khía cạnh chống tấn công làm lộ khóa mật của LD 2.01 là hoàn toàn tương đương với DSA và GOST R34.10-94 nếu các điều kiện an toàn chỉ ra sau đây được tuân thủ. Điều kiện 2.1: Khóa bí mật x và k phải được chọn để việc tính: x = DLP(p,g)(y) và: k = DLP(p,g)(r) là khó. Cũng tương tự như DSA và GOST R34.10-94 nói riêng hay các lược đồ chữ k ý họ ElGamal nói chung, một điểm yếu có thể tấn công làm lộ khóa mật của LD 2.01 là khi giá trị của khóa k bị sử dụng lại trong các lần k ý khác nhau. Thật vậy, giả sử với cùng 1 giá trị của k được sử dụng để k ý hai thông điệp dữ liệu khác nhau M1 và M2, khi đó các thành phần thứ hai của chữ k ý s1, s2 sẽ là: s1 = k. e1 -1 + x. r mod q s2 = k. e2 -1 + x. r mod q 59 với: r = (gk mod p) mod q, e1 = H(M1) và e2 = H(M2). Từ hệ 2 phương trình 2 ẩn số trên đây có thể dễ dàng tính được khóa k, từ đó tính được khóa bí mật x. Như vậy, một điều kiện cần thiết nữa để LD 2.01 an toàn đối với dạng tấn công làm lộ khóa mật là: Điều kiện 2.2: Giá trị của k không được lặp lại ở các lần k ý khác nhau. b) Khả năng chống tấn công giả mạo chữ ký . Giả sử đối tượng k ý U có khóa bí mật là x và khóa công khai tương ứng là y. Một đối tượng U* có thể mạo danh U để k ý lên một thông điệp dữ liệu M bằng cách tạo ra chữ ký giả mạo (r*,s*) thỏa mãn điều kiện của thuật toán kiểm tra (Thuật toán 2.3): r* = (gs*.e. yr*.e mod p) mod q. Khi đó, (r*,s*) sẽ được công nhận là chữ k ý của U lên M, nghĩa là U* đã mạo danh U thành công. Thuật toán 2.4: Giả mạo chữ ký. Input: p, q, g, y , H(.), M. Output: (r*,s*) – chữ k ý của U lên M do U* tạo ra. [1]. e ← H(M); [2]. select r* : 1 < r* < q; [3]. r’ ← r* + k. q, k ≥ 0, r’ < p; [4]. s* ← logge r’.y –r*.e mod p; (3.13) [5]. return (r*,s*); Nhận xét: Từ (3.13) cho thấy, để thực hiện Thuật toán 2.4, U* cần phải giải được bài toán DLP(p,g). Nghĩa là, khả năng chống giả mạo chữ k ý của lược đồ LD 2.01 phụ thuộc tính khó giải của bài toán DLP(p,g). Thuật toán 2.5: Giả mạo chữ ký. Input: p, q, g, y , H(.), M. Output: (r*,s*) – chữ k ý của U lên M do U* tạo ra. 60 [1]. e ← H(M); [2]. select s* : 1 < s* < q; [3]. select r*: (r* + k.q). y– r*.e ≡ gs*.e mod p, k ≥ 0; (3.14) [4]. return (r*,s*); Nhận xét: Với Thuật toán 2.5, để chọn được (r*,s*) thỏa mãn (3.10), U* cần phải giải được (3.14). Hiện thời đây là bài toán chưa có lời giải, song cũng chưa có một kết quả nghiên cứu nào khẳng định là bài toán này không thể giải được. 3.3 Xây dựng lược đồ chữ ký số tập thể Hai lược đồ chữ ký tập thể đề xuất ở đây - k ý hiệu LD 2.02 và LD 2.03, được phát triển từ lược đồ cơ sở LD 2.01 theo mô hình đề xuất ở Chương 1 và có cùng nguyên tắc xây dựng với các lược đồ chữ k ý tập thể LD 1.02 và LD 1.03 đã được trình bày ở Chương 2. 3.3.1 Lược đồ chữ ký tập thể LD 2.02 3.3.1.1 Thuật toán hình thành tham số và khóa. Các tham số hệ thống được hình thành theo phương pháp của DSA hoặc GOST R34.10-94 [10],[19],[20]. Thuật toán 2.6a: Hình thành khóa của U = {Ui| i = 1, 2,..,n}. Input: p, g, n, KS = {xi| i = 1,2,…,n}. Output: KP = {yi| i = 1, 2,..,n}. [1]. for i = 1 to n do [1.1]. yi ← g - xi mod p; (3.15) [1.2]. KP[i] ← yi; [2]. return KP; 61 Thuật toán 2.6b: Hình thành khóa của CA. Input: p, g, x CA . Output: y CA . [1]. y CA ← g- xCA mod p; (3.16) [2]. return (y CA ); 3.3.1.2 Thuật toán chứng nhận và kiểm tra đối tượng k ý. Thuật toán 2.7a: CA chứng nhận đối tượng ký Ui (i = 1,2,…,n). Input: IDi, yi, xCA. Output: (ui,vi) – chứng nhận của CA đối với Ui. [1]. ki ← H(xCA||yi||IDi); [2]. ui ← (g ki mod p) mod q; (3.17) [3]. e ← H(yi||IDi); (3.18) [4]. vi ← ki. e -1+ x CA . ui mod q; (3.19) [5]. return (ui,vi); Thuật toán 2.7b: Kiểm tra tính hợp pháp của đối tượng Ui (i = 1,2,…,n). Input: yi, yCA, IDi, (ui,vi). Output: (ui,vi) = true / false. [1]. e ← H(yi||IDi); (3.20) [2]. u ← (gvi.e . (y CA )ui.e mod p) mod q; (3.21) [3]. if (u = ui) then {return true;} else {return false;} 62 3.3.1.3 Thuật toán hình thành và kiểm tra chữ k ý tập thể. Thuật toán 2.8: Hình thành chữ ký cá nhân của một hay một nhóm đối tượng lên thông điệp dữ liệu M. Input: M, n, KS = {xi| i = 1, 2,..,n}, KP = {yi| i = 1, 2,..,n}. Output: (r,s) – chữ k ý của Ui (i = 1, 2,..,n) hay U lên M. [1]. for i = 1 to n do [1.1]. ki ← H(xi||M); [1.2]. ri ← g ki mod p; (3.22) [1.3]. send ri to {U1, U2,...., Ui-1, Ui+1,..., Un}; [2]. r ← 1; for i = 1 to n do r ← r . ri mod n; (3.23) [3]. for i = 1 to n do [3.1]. e ← H(M); (3.24) [3.2]. si ← ki. e -1+ xi. r mod q; (3.25) [4]. s ← 1; for i = 1 to n do [4.1]. if (ri ≠ g si.e. (yi) ri.e mod p) then return (0,0); [4.2]. s ← s . si mod q; (3.26) [5]. return (r,s); Thuật toán 2.9: Hình thành chứng nhận của CA đối với chữ ký cá nhân của một hay một nhóm đối tượng lên thông điệp M. Input: p, q, g, x CA , n, KP = {yi| i = 1, 2,..,n}, (ui,vi), {M, (r,s)}. Output: (u M ,v M ) – chứng nhận của CA đối với {M, (r,s)}. [1]. y ← 1; for i = 1 to n do [1.1]. e ← H(yi||IDi); [1.2]. u ← (g vi.e . (y CA ) ui.e mod p) mod q; 63 [1.3]. if (u ≠ ui) then return (0,0); [1.4]. y ← y. yi mod p; [2]. if ( r = 0 or s = 0) then {return (0,0);} else [2.1]. e ← H(M); [2.2]. u ← (gs.e . yr.e mod p) mod q; [2.3]. if (u ≠ r) then {return (0,0);} [3]. k ← H(x CA ||y||M); [4]. u M ← (gk mod p) mod q; (3.27) [5]. e ← H(y||M); (3.28) [6]. v M ← k. e-1 + x CA . u M mod q; (3.29) [7]. return (u M ,v M ); Thuật toán 2.10: Kiểm tra chữ ký tập thể của một hay một nhóm đối tượng lên thông điệp dữ liệu M. Input: p, q, g, n, yCA, , KP = {yi| i = 1, 2,..,n}, M, {(r,s), (uM,vM)}. Output: {(r,s), (uM,vM)} = true / false. [1]. y ← 1; for i = 1 to n do [1.1]. e ← H(yi||IDi); [1.2]. u ← (g vi.e . (y CA ) ui.e mod p) mod q; [1.3]. if (u ≠ ui) then return (0,0); [1.4]. y ← y . yi mod p; (3.30) [2]. if (u M = 0 or v M = 0) then return false; [2.1]. e ← H(y||M); (3.31) [2.2]. u ← (gvM.e . (y CA )uM.e mod p) mod q; (3.32) [2.3]. if (u ≠ u M ) then return false; 64 [3]. If ( r = 0 or s = 0) then {return (0,0);} else [3.1]. e ← H(M); (3.33) [3.2]. u ← (gs.e . yr.e mod p) mod q; (3.34) [3.3]. if (u = r) then {return true;} else {return false;} 3.3.1.4 Tính đúng đắn của lược đồ LD 2.02 Tính đúng đắn của lược đồ mới đề xuất bao gồm: a) Tính đúng đắn của thuật toán chứng nhận và kiểm tra đối tượng k ý. Đặt: e1 = e, e2 = ui, s = vi, x = xCA, y = yCA. Theo (3.16), (3.17), (3.19) và Mệnh đề 2.1 ta có: (g vi.e . (y CA ) ui.e mod p) mod q = ui (3.35) Từ (3.35) và (3.21) suy ra: u = ui Đây là điều cần chứng minh. b) Tính đúng đắn của thuật toán hình thành và kiểm tra chữ k ý cá nhân. Đặt: e1 = e, e2 = ui, s = si, x = xi, k = ki, y = yi , r = ri. Theo (3.22), (3.23), (3.24), (3.25) và Mệnh đề 2.1, ta có: (g si.e . (yi) ri.e mod p) mod q = ri Đây là điều cần chứng minh. c) Tính đúng đắn của thuật toán hình thành và kiểm tra chứng nhận của CA đối với chữ k ý cá nhân của đối tượng k ý. Đặt: e1 = e, e2 = uM, s = vM, y = yCA. Theo (3.16), (3.27), (3.28), (3.29) và Mệnh đề 2.1, ta có: (gvM.e . (y CA )uM.e mod p) mod q = u M (3.36) 65 Từ (3.30), (3.31), (3.32) và (3.36) suy ra: u = u M Đây là điều cần chứng minh. d) Tính đúng đắn của thuật toán hình thành và kiểm tra chữ k ý cá nhân của một nhóm đối tượng k ý. Mệnh đề 2.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 < xi, ki < p, 1 < e1, e2 < q. Nếu: yi = g –xi mod p, ri = g ki mod p, si = ki. e1 -1 + xi. e2 mod q, y = Õ = n i iy 1 mod p, r = (Õ = n i ir 1 mod p)mod q, s = å = n i is 1 mod q thì: (g e1.s . y e1.e2 mod p) mod q = r. Chứng minh: Thật vậy, ta có: (g e1.s . y e1.e2 mod p) mod q = = (g e 1 . å = n i ik 1 . (Õ = n i iy 1 mod p) e 1 .e 2 mod p) mod q = (g e 1 . å = n i 1 ki. e1 -1 + xi. e2 . g -å = n i 1 xi .e1. e2 mod p) mod q = (g å = n i ik 1 mod p) mod q = Õ = n i ir 1 mod q = r Tính đúng đắn của thuật toán hình thành và kiểm tra chữ ký của một hoặc một nhóm đối tượng k ý lên một thông điệp dữ liệu (M) được chứng minh như sau: Đặt: e1 = e, e2 = r. Theo (3.23), (3.24), (3.26), (3.30) và Mệnh đề 2.2, ta có: (gs.e . yr.e mod p) mod q = r (3.37) 66 Từ (3.37) và (3.34) suy ra: u = r Đây là điều phải chứng minh. 3.3.1.5 Mức độ an toàn của lược đồ LD 2.02 Mức độ an toàn của lược đồ chữ k ý tập thể LD 2.02 được thiết lập dựa trên độ an toàn của lược đồ cơ sở LD 2.01. Vì vậy, lược đồ chữ k ý tập thể LD 2.02 cần phải tuân thủ các điều kiện an toàn đã được chỉ ra ở lược đồ cơ sở LD 2.01. Ngoài ra, ở các lược đồ chữ ký tập thể còn tiềm ẩn các nguy cơ tấn công giả mạo chữ k ý từ bên trong hệ thống [21],[31],[32],[33],[34],[35],[36]. Vấn đề này được xem xét dưới góc độ Bài toán giả mạo chữ ký như sau: a) Bài toán giả mạo chữ k ý nhóm Cho U và U* với U Ë U* là hai nhóm các đối tượng trong hệ thống tương ứng với cặp tham số {p,q,g}. Khi này Bài toán giả mạo chữ ký nhóm có thể được mô tả như sau: Bài toán LD2(U,U*): Cho các tham số bí mật của các thành viên trong U*. Khi đó với mỗi thông báo M, hãy tìm cặp {r,s} được chấp nhận theo điều kiện của thuật toán kiểm tra chữ k ý (Thuật toán 2.10) với đầu vào là bộ tham số công khai của U. Mỗi giải thuật cho bài toán LD2(U,U*) được gọi là "thuật toán giả mạo chữ ký của U lên M do U* thực hiện". Để khảo sát tính an toàn của lược đồ LD 2.02, trước tiên cần xây dựng hai giải thuật lần lượt cho các bài toán LD2(U,U*) và LD2(U',U*) với giả thiết: U* = {U*i| i=1...m*}, U' = {U'i| i=1...m'}, U*ÇU' = Æ và U*ÈU' = U. (3.38) 67 Thuật toán 2.11. Thuật giải cho bài toán LD2(U,U*). Input: p, q, g, M, (r’,s’) – chữ ký của U' lên M. Output: (r,s) – chữ ký (giả mạo) của U lên M do U* tạo ra. [1]. s* = 0; [2]. for i = 1 to m* do s* = s* + xi*. r’ mod q; (3.39) [3]. s = s’ + s* mod q; (3.40) [4]. r = r’; (3.41) [5]. return (r,s); Tính đúng đắn của Thuật toán 2.11 được chứng minh như sau: Từ (3.39) với mọi: i = 1,2,..,m*, ta có: g si*.e . (yi*) r’.e mod p = g xi*.r’.e . g - xi*.r’.e mod p = 1 (3.42) Với điều kiện (3.38), dễ dàng kiểm tra được rằng: y = y'. (Õ = * 1 * m i iy mod p) mod p (3.43) Từ (3.42) và (3.43) ta có: (gs.e . yr.e mod p) mod q = = (g (s' + å * = * m i is 1 ). e . (y'. (Õ = *m 1i * iy mod p) mod p) r.e mod q = (g s'.e . (y') r.e . g ( å * = * m i is 1 ). e . )( * 1 *Õ = m i iy r.e mod p) mod q = (g s'.e . (y') r’.e . (Õ = * 1 m i g si*. e . (yi*) r’.e mod p) mod p) mod q = (gs'.e . (y')r’.e mod p) mod q = r' (3.44) 68 Từ (3.34), (3.41) và (3.44) suy ra: u = r (3.45) Từ (3.45) cho thấy, mặc dù (r,s) do U* tạo ra nhưng vẫn được công nhận là chữ k ý hợp lệ của U lên M. Như vậy, Thuật toán 2.11 đã được chứng minh là đúng. Thuật toán 2.12. Thuật giải cho bài toán LD2(U',U*). Input: p, q, g, M, (r,s) - chữ ký của U lên M. Output: (r’,s’) - chữ ký (giả mạo) của U' lên M do U* tạo ra. [1]. s* = 0; [2]. for i = 1 to m* do s* = s* + xi*. r mod q; (3.46) [3]. s’ = s - s* mod q; (3.47) [4]. r’ = r; (3.48) [5]. return (r’,s’); Chứng minh tính đúng đắn của Thuật toán 2.12. Từ (3.46) với mọi: i = 1,2,..,m*, ta có: g- si*.e . (yi*) - r.e mod p = g- xi*.r.e . gxi*.r.e mod p = 1 (3.49) Với điều kiện (3.38), dễ dàng kiểm tra được rằng: y’ = y . Õ = - *m 1i 1* i )y( mod p (3.50) Từ (3.49) và (3.50) ta có: (gs’.e . (y’)r’.e mod p) mod q = (g(s - s*).e . (y’)r.e mod p) mod q = (g (s -å * = * m i is 1 ). e . (y. Õ = - *m 1i 1* i )y( mod p) r.e mod p) mod q 69 = (gs.e . yr.e. g ( -å * = * m i is 1 ). e . )( * 1 *Õ = m i iy - r.e mod p) mod q = (gs.e . yr.e . (Õ = * 1 m i g- si*.e . (yi*) - r.e mod p) mod p) mod q = (gs.e . yr.e mod p) mod q = r (3.51) Từ (3.34), (3.48) và (3.51) suy ra: u = r’ (3.52) Từ (3.52) cho thấy, mặc dù (r’,s’) do U* tạo ra nhưng vẫn được công nhận là chữ k ý hợp lệ của U’ lên M, nói cách khác Thuật toán 2.12 đã được chứng minh là đúng. b) Sự an toàn của lược đồ LD 2.02 trước các tấn công giả mạo chữ ký nhóm. Từ việc xem xét Bài toán LD2(U,U*) cho thấy nếu sử dụng mô hình chữ k ý tập thể dạng kết hợp, mà ở đó CA cũng k ý trực tiếp lên thông điệp dữ liệu như các thành viên của nhóm ký thì lược đồ chữ k ý tập thể sẽ không có khả năng chống lại các tấn công giả mạo từ bên trong hệ thống. Xây dựng theo mô hình chữ k ý tập thể dạng phân biệt, ở đó CA tạo chứng nhận bằng cách ký lên thông điệp dữ liệu cần ký M và khóa công khai chung của nhóm ký, lược đồ LD 1.02 có khả năng ngăn chặn hoàn toàn các dạng tấn công giả mạo từ bên trong hệ thống đã biết trong thực tế. 3.3.2 Lược đồ chữ ký tập thể LD 2.03 Lược đồ LD 2.03 với các thuật toán hình thành tham số và khóa, thuật toán chứng nhận và kiểm tra tính hợp pháp của các đối tượng k ý, thuật toán chứng nhận của CA đối với chữ k ý cá nhân của một hay một nhóm đối tượng và thuật toán kiểm tra chữ k ý tập thể được xây dựng hoàn toàn như các thuật toán tương ứng của lược đồ LD 2.02. Riêng thuật toán hình thành chữ k ý cá 70 nhân của một nhóm đối tượng lên một thông điệp dữ liệu được xây dựng mới với qui định về thứ tự k ý của các thành viên trong nhóm. 3.3.2.1 Thuật toán hình thành chữ ký cá nhân của một hay một nhóm đối tượng k ý. Giả sử nhóm ký gồm n-thành viên: U = {Ui| i=1,2,...,n}. Các thành viên nhóm ký có khóa bí mật là: KS = {xi| i=1,2,...,n} và các khóa công khai tương ứng là: KP = {yi| i=1,2,...,n}. Thuật toán 2.13: Hình thành chữ ký cá nhân của một hay một nhóm đối tượng lên thông điệp dữ liệu M. Input: p, q, g, M, n, KS = {xi| i = 1, 2,..,n}, KP = {yi| i = 1, 2,..,n}. Output: (r,s) – chữ ký của Ui (i = 1, 2,..,n) hay U lên M. [1]. for i = 1 to n do [1.1]. ki ← H(xi||M); [1.2]. ri ← g ki mod p; (3.53) [1.3]. send ri to {U1, U2,..., Ui-1, Ui+1,..., Un} [2]. r ← 1; for i = 1 to n do r ← r . ri mod p; (3.54) [3]. r ← r mod q; (3.55) [4]. e ← H(M); [5]. s0 ← 0, Y0 ← 1, R0 ← 1; for i = 1 to n do [5.1]. Yi-1 ← y1 . y2 .... yi-1 mod p; (3.56) [5.2]. Ri-1 ← r1 . r2 .... ri-1 mod p; (3.57) 71 [5.3]. if (Ri-1 ≠ (g si-1.e . (Yi-1) r.e mod p)) then return (0,0); (3.58) [5.4]. si ← si-1 + ki . e -1+ xi . r mod q; (3.59) [5.5] if (i < n) then {send si to Ui+1} else s = si; [6]. return (r,s); 3.3.2.2 Tính đúng đắn của lược đồ LD 2.03 Tính đúng đắn của lược đồ mới đề xuất bao gồm: a) Tính đúng đắn của các thuật toán chứng nhận và kiểm tra tính hợp pháp của đối tượng k ý, thuật toán hình thành và kiểm tra chứng nhận của CA đối với chữ k ý của một hay một nhóm đối tượng k ý, thuật toán kiểm tra chữ k ý tập thể được chứng minh tương tự như các thuật toán tương ứng của lược đồ LD 2.02. b) Tính đúng đắn của thuật toán kiểm tra thứ tự k ý của các thành viên trong một nhóm k ý. Từ (3.59) ta có: si-1 = si-2 + k1. e -1 + x1. r mod q = (k1+k2+...+ki-1). e -1+(x1+x2+...+xi-1). r mod q (3.60) Đặt: e1 = e, e2 = r, y = Yi-1, s = si-1. Theo (3.56), (3.57), (3.60) và Mệnh đề 2.2, ta có: (g si-1.e . (Yi-1) r.e mod p) = Ri-1 Đây là điều phải chứng minh. c) Tính đúng đắn của thuật toán hình thành và kiểm tra chữ k ý nhóm Từ (3.59) ta có: s = sm = (k1+k2+...+kn). e -1 + (x1+x2+...+xn). r mod q = e-1.å = n i ik 1 + r. å = n i ix 1 mod q (3.61) 72 Do đó, nếu đặt: e1 = e, e2 = r. Theo (3.34), (3.56), (3.57), (3.61) và Mệnh đề 2.2, ta có: (gs.e . yr.e mod p) mod q = r (3.62) Từ (3.34) và (3.62) suy ra: u = r Đây là điều phải chứng minh. 3.3.2.3 Mức độ an toàn của lược đồ LD 2.03 Việc phân tích, đánh giá mức độ an toàn của lược đồ LD 2.03 thực hiện tương tự như với lược đồ LD 1.03 và LD 2.02. 3.4 Kết luận Chương 3 Các kết quả đã đạt được ở Chương 3 bao gồm 3 lược đồ chữ ký số mới, trong đó có 1 lược đồ cơ sở xây dựng trên bài toán logarit rời rạc trong trường hữu hạn nguyên tố theo cùng nguyên tắc với các lược đồ chữ k ý họ ElGamal như các chuẩn chữ ký số DSS và GOST R34.10-94. Lược đồ này có ưu điểm so với các lược đồ thuộc họ El Gamal là chỉ cần sử dụng một khóa bí mật duy nhất để hình thành chữ ký, do đó đã khắc phục được yếu điểm của các lược đồ họ ElGamal khi khóa thứ hai bị sử dụng lặp lại. Hai lược đồ chữ ký tập thể là kết quả phát triển từ lược đồ cơ sở theo mô hình đã đề xuất ở Chương 1. 73 KẾT LUẬN 1. Những kết quả đã đạt được của Luận án: - Đề xuất mô hình ứng dụng chữ ký số nhằm đáp ứng các yêu cầu về chứng thực các thông điệp dữ liệu trong các giao dịch điện tử, có thể áp dụng phù hợp trong các tổ chức xã hội, cơ quan hành chính nhà nước, các doanh nghiệp,... - Xây dựng 6 lược đồ chữ ký số, trong đó có 2 lược đồ cơ sở (LD 1.01, LD 2.01) và 4 lược đồ chữ ký tập thể (LD 1.02, LD 1.03, LD 2.02, LD 2.03) theo mô hình mới đề xuất. 2. Những đóng góp mới của Luận án: - Mô hình chữ ký số tập thể: đây là mô hình ứng dụng chữ ký số nhằm đáp ứng yêu cầu xác thực nguồn gốc và tính toàn vẹn cho các thông điệp dữ liệu ở nhiều cấp độ khác nhau, ứng dụng phù hợp trong các tổ chức xã hội, các cơ quan hành chính nhà nước, các doanh nghiệp,... Kết quả này được thể hiện ở công trình số [4],[5] của Luận án. - Lược đồ cơ sở LD 1.01: đây là một dạng thuật toán chữ k ý số mới được xây dựng trên cơ sở bài toán khai căn trên vành Zn=p.q, trong đó {p,q} là các số nguyên tố phân biệt. Kết quả này được thể hiện ở công trình số [5] của Luận án. - Lược đồ cơ sở LD 2.01: được xây dựng trên cơ sở bài toán logarit rời rạc trên trường hữu hạn nguyên tố theo cùng nguyên tắc với các lược đồ chữ k ý họ ElGamal (DSS, GOST R34.10-94). Lược đồ này có ưu điểm so với các lược đồ họ El Gamal là chỉ cần sử dụng một khóa bí mật duy nhất để hình thành chữ ký, do đó đã khắc phục được yếu điểm của các lược đồ họ ElGamal khi khóa thứ hai bị sử dụng lặp lại. Kết quả này được thể hiện ở công trình số [6],[7],[8] của Luận án. 74 - Các lược đồ chữ ký số tập thể: được phát triển từ các lược đồ cơ sở (LD 1.01, LD 2.01) theo mô hình ứng dụng mới đề xuất, có thể đáp ứng yêu cầu chứng thực các thông điệp dữ liệu trong các giao dịch điện tử áp dụng cho các tổ chức xã hội, cơ quan hành chính nhà nước, các doanh nghiệp,... Kết quả này được thể hiện ở công trình số [4],[5],[6] của Luận án. 75 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ 1. Lưu Hồng Dũng, Trần Trung Dũng (2011), Xây dựng lược đồ đa chữ ký số tuần tự, Tạp chí Khoa học và Kỹ thuật (Học viện KTQS), số 141 (06- 2011). 2. Lưu Hồng Dũng (2011), Phát triển lược đồ đa chữ ký số trên cơ sở bài toán logarit rời rạc, Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng CNTT và TT (Bộ Thông tin và Truyền thông), tập V-1, số 5(25) (06-2011). 3. Lưu Hồng Dũng, Nguyễn Thị Thu Thủy (2012), Nghiên cứu xây dựng mô hình tổng quát cho các lược đồ chữ ký số phân biệt trách nhiệm, Tạp chí Khoa học và Kỹ thuật (Học viện KTQS), số 146 (02-2012). 4. Lưu Hồng Dũng (2012), Một mô hình mới cho các lược đồ chữ ký số, Tạp chí Khoa học và Kỹ thuật (Học viện KTQS), số 147 (04-2012). 5. Lưu Hồng Dũng, Hoàng Văn Việt (2012), Xây dựng lược đồ chữ ký số dựa trên hệ mật RSA, Tạp chí Khoa học và Kỹ thuật (Học viện KTQS), số 148 (06-2012). 6. Lưu Hồng Dũng (2012), Nghiên cứu xây dựng lược đồ chữ ký số tập thể, Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng CNTT và TT (Bộ Thông tin và Truyền thông), tập V-1, số 7(27) (05-2012). 7. Lưu Hồng Dũng, Tống Minh Đức, Trần Trung Dũng (2012), Nghiên cứu xây dựng hệ tích hợp mật mã khóa công khai – chữ k ý số, Tạp chí Khoa học và Kỹ thuật (Học viện KTQS), số 149 (08-2012). 8. Lưu Hồng Dũng (2012), Phát triển thuật toán mật mã khóa công khai dựa trên hệ mật ElGamal, Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng CNTT và TT (Bộ Thông tin và Truyền thông), tập V-1, số 8(28) (12-2012). 76 TÀI LIỆU THAM KHẢO 1. Adams C. (1999), Understanding Public Key Infrastructures, New Riders Publishing, Indianapolis. 2. Boeyen S., Howes T. and Richard P. (1999), Internet X.509 Public Key Infrastructure Operational Protocols – LDAP2, RFC 2559. 3. Boneh D. (1999), “Twenty Years of Attacks on the RSA Cryptosystem”, Notices of the American Mathematical Society, Vol. 46, No. 2, pp. 203- 213. 4. Boyd C. (1989), Digital multisignatures, Proc. IMA Conf. Crypto. Coding, Oxford, pp. 241–246. 5. ElGamal T. (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. 6. Fegghi, J.(1999), Digital Certificates and Applied Internet Security, Addison-Wesley Longman Inc. 7. Goldwasser S. and Bellare M. (1997), “Digital Signatures”, Lecture Notes on Cryptography 1997, pp. 96-118. 8. Goldwasser S., Micali S. and Rivest R. (1988), “A digital signature scheme secure against adaptive chosen-message attacks”, SIAM Journal of Computing, Vol.17, No. 2, pp. 281-308. 9. Gordon D. (1993), “Discrete logarithms in GF(p) using the number field sieve”, SIAM Journal on Discrete Mathematics, (6), pp. 124-138. 10. 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). 11. Hans Delfs, Helmut Knebl (2007), Introduction to Cryptography: Principle and Applications, Second Edition, Springer. 12. Housley R., Polk W., Ford W. and Solo D. (2002), Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile, RFC 3280. 13. Jonge W.D., Chaum D. (1986), “Attacks on Some RSA Signatures”,Advances in Cryptology, Crypto '85 proceedings, Lectures Notes In Computer Science, Vol. 218, Springer-Verlag, Berlin 1986, pp. 77 18-27. 14. Jonsson J., Kaliski B. (2003), Public-Key Cryptography Standards (PKCS)#1: RSA cryptography specifications, Version 2.1. Internet Request for Comments 3447 (RFC 3447), 15. Kocher P. (1996), “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,” Proceeding of CRYPTO ’96, Springer- Verlag 1996, pp. 104-113. 16. Lenstra A.K. and Verheul E.R. (2000), “Selecting Cryptographic Key Sizes”, The 2000 International Workshop on Practice and Theory in Public Key Cryptography (PKC2000), Melbourne, Australia (January 2000). 17. Maurer U.M. (1995), “Fast generation of prime numbers and secure public-key cryptographic parameters”. Journal of Cryptology, 8: 123-155. 18. Menezes A., Van Oorschot P. and Vanstone S. (1996), Handbook of Applied Cryptography, Boca Raton, Florida: CRC Press. 19. National Institute of Standards and Technology, NIST FIPS PUB 186-3. Digital Signature Standard, U.S. Department of Commerce, 1994. 20. National Institute of Standards and Technology, U.S. Department of Commerce. Secure Hash Standard, 2002. FIPS PUB 180-2. 21. Ohta K. and Okamoto T. (1999), “Multisignature schemes secure against active insider attacks”, IEICE Trans. Fundamentals, E82-A(1), pp. 21–31. 22. Pollard J. (1978), “Monte Carlo methods for index computation mod p”, Mathematics of Computation, (32), pp. 918-924. 23. Rivest R., Shamir A., Adleman L. (1978), “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Communications of the ACM, Vol. 21, No. 2, pp. 120 – 126. 24. H. Riesel (1994), Prime Numbers and Computer Methods for Factorization. Boston, Basel: BirkhÄauser. 25. RSA Laboratories (2002), PKCS #1 v2.1: RSA Encryption Standard. 26. Schnorr C. and Jakobsson M. (1976), “Security of Signed ElGamal Encryption,” In Asiacrypt ’00, LNCS Vol. 1976, pp. 73–89. 27. Shannon C.E. (1949), “Communication theory of secrecy systems”. Bell Systems Journal, 28: 656-715. 28. Stinson D.R. (2005), Cryptography: Theory and practice, third edition, Chapman & Hall/CRC. 78 29. Tsiounis Y. and Yung M. (1998), “On the Security of ElGamal Based Encryption,” In PKC ’98, LNCS Vol. 1431, pp. 117–134. 30. US Secure Hash Algorithm 1 (SHA1). Internet Request for Comments 3174 (RFC 3174), 2001. 31. Wiener M. (1990), “Cryptanalysis of short RSA secret exponents”, IEEE Transactions on Information Theory, pp 553-558. 32. Williams H.C (1982), “A p+1 Method of factoring”. Math. Comp. 39, 225-234. 33. Zhang J. (2010), “Cryptographic Analysis of the Two Structured Multi- signature Schemes”, Journal of Computational Information Systems Vol.6, No.9, pp.3127-3135. 34. Zheng Y. and Seberry J. (1992), “Practical Approaches to Attaining Security Against Adaptively Chosen Ciphertext Attacks”, Advances in Cryptology - Crypto '92, pp. 292-304. Springer Verlag 1992. 35. Zheng Y., Seberry J. (1993), “Immunizing public key cryptosystems against chosen ciphertext attacks”, IEEE Journal on Selected Areas in Communications 11, pp. 715-724. 36. Zheng Y. (1994), “Improved public key cryptosystems secure against chosen ciphertext attacks”, Technical Report 94-1 University of Wollongong, Australia.