CHỮ KÝ SỐ TẬP THỂ - MÔ HÌNH VÀ THUẬT TOÁN

Hội thảo quốc gia lần thứ XVIII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-TP HCM,05-06/11/2015<br /> <br /> <br /> <br /> Chữ ký số tập thể - Mô hình và thuật toán<br /> <br /> Lưu Hồng Dũng Nguyễn Đức Thụy<br /> Khoa CNTT Bộ môn Tin Học Ứng Dụng<br /> Học viện Kỹ thuật Quân sự Cao đẳng Kinh tế Kỹ thuật Thành phố Hồ Chí Minh<br /> Hà Nội, Việt Nam Hồ Chí Minh, Việt Nam<br /> Email: luuhongdung@gmail.com Email: thuyphulam2013@gmail.com<br /> <br /> Tóm tắt—Bài báo đề xuất một mô hình ứng dụng chữ<br /> ký số phù hợp cho đối tượng là các cơ quan nhà nước, đơn vị II. MÔ HÌNH VÀ THUẬT TOÁN CHỮ KÝ SỐ<br /> hành chính, doanh nghiệp,... mà ở đó các thông điệp dữ liệu TẬP THỂ<br /> cần phải được chứng thực về nguồn gốc và tính toàn vẹn ở 2<br /> cấp độ: thực thể ký và tổ chức (cơ quan, đơn vị, ...) mà thực A. Mô hình chữ ký số tập thể<br /> thể ký là thành viên của nó. Bài báo cũng đề xuất xây dựng Mô hình chữ ký số tập thể được đề xuất cơ bản<br /> lược đồ chữ ký số theo mô hình ứng dụng mới này<br /> dựa trên cấu trúc của một Hạ tầng cơ sở khóa công<br /> Từ khoá: Digital Signature, Collective Digital<br /> khai - PKI (Public Key Infrastructures) [1] nhằm bảo<br /> Signature, Digital Signature Schema đảm các chức năng về chứng thực số cho đối tượng<br /> áp dụng là các tổ chức có tư cách pháp nhân trong xã<br /> hội (đơn vị hành chính, cơ quan nhà nước, doanh<br /> I. ĐẶT VẤN ĐỀ nghiệp...). Trong mô hình này, đối tượng ký là một<br /> Trong các lĩnh vực như Chính phủ điện tử, hay một nhóm thành viên của một tổ chức, chữ ký<br /> Thương mại điện tử,… chữ ký số được sử dụng của các thành viên ở đây được gọi là chữ ký cá nhân.<br /> nhằm đáp ứng yêu cầu chứng thực về nguồn gốc và tính Cũng trong mô hình này, Cơ quan chứng thực - CA<br /> toàn vẹn của thông tin (các bản tin, thông điệp dữ (Certificate Authority) là bộ phận có chức năng bảo<br /> liệu điện tử,…) trong giao dịch điện tử. Các mô đảm các dịch vụ chứng thực số, như: chứng nhận<br /> hình ứng dụng chữ ký số hiện tại cho phép đáp ứng tốt một đối tượng ký là thành viên của tổ chức, chứng<br /> các yêu cầu về chứng thực nguồn gốc và tính toàn thực các thông điệp dữ liệu được ký bởi các thành<br /> vẹn của các thông điệp dữ liệu được tạo ra hay ký viên trong một tổ chức, mà CA là cơ quan chứng<br /> bởi những thực thể có tính độc lập. Tuy nhiên, thực thuộc tổ chức này. Tính hợp lệ về nguồn gốc và<br /> khi các thực thể ký là thành viên hay bộ phận của tính toàn vẹn của một thông điệp dữ liệu ở cấp độ<br /> một tổ chức (đơn vị hành chính, cơ quan nhà nước, của một tổ chức chỉ có giá trị khi nó đã được CA<br /> doanh nghiệp...) thì yêu cầu về việc chứng thực thuộc tổ chức này chứng thực. Trong mô hình này,<br /> nguồn gốc và tính toàn vẹn của thông tin ở cấp độ chữ ký của CA cùng với chữ ký cá nhân của các đối<br /> thực thể ký và cấp độ tổ chức mà thực thể ký là tượng ký hình thành nên chữ ký tập thể cho một<br /> một thành viên hay bộ phận của nó không được thông điệp dữ liệu. Một hệ thống cung cấp dịch vụ<br /> đáp ứng trong các mô hình ứng dụng chữ ký số chứng thực số xây dựng theo mô hình mới đề xuất sẽ<br /> hiện tại. bao gồm các hoạt động cơ bản như sau:<br /> Bài báo đề xuất phát triển lược đồ chữ k ý số 1) Phát hành, quản lý Chứng chỉ khóa công<br /> theo mô hình ứng dụng mới nhằm bảo đảm các khai.<br /> yêu cầu chứng thực về nguồn gốc và tính toàn vẹn Trong mô hình chữ ký tập thể, chứng chỉ khóa<br /> cho các thông điệp dữ liệu trong các giao dịch công khai - PKC ( Public Key Certificate) hay chứng<br /> điện tử mà ở đó các thực thể ký là thành viên hay chỉ số được sử dụng để một tổ chức chứng nhận các<br /> bộ phận của các tổ chức có tư cách pháp nhân đối tượng ký là thành viên của nó.<br /> trong xã hội. Trong mô hình này, các thông điệp Cấu trúc cơ bản của một PKC bao gồm khóa<br /> điện tử sẽ được chứng thực ở cả 2 cấp độ: thực công khai của chủ thể chứng chỉ và các thông tin<br /> thể tạo ra nó và tổ chức mà thực thể tạo ra nó là khác như: Thông tin nhận dạng của chủ thể, Trạng<br /> một thành viên hay bộ phận của tổ chức này. Ở thái hoạt động của chứng chỉ, Số hiệu chứng chỉ,<br /> đây, mô hình ứng dụng chữ ký số với các yêu cầu Thông tin nhận dạng của CA,... Không làm mất tính<br /> đặt ra như trên được gọi là mô hình chữ ký số tập tổng quát, ở đây sử dụng thuật ngữ Thông tin nhận<br /> thể (Collective Signature Model) và lược đồ/thuật dạng (IDi) của đối tượng ký để đại diện cho các<br /> toán chữ ký số xây dựng theo mô hình như thế thành phần thông tin nói trên. Trong thực tế, có thể<br /> được gọi là lược đồ/thuật toán chữ ký số tập thể sử dụng khuôn dạng chứng chỉ X.509 [2] cho chứng<br /> (Collective Signature Schema/Algorithm).<br />  Hội thảo quốc gia lần thứ XVIII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-TP HCM,05-06/11/2015<br /> <br /> <br /> chỉ khóa công khai trong mô hình chữ ký tập thể tham số và khóa, thuật toán hình thành và kiểm tra<br /> được đề xuất. chữ ký được chỉ ra sau đây:<br /> 2) Hình thành và kiểm tra chữ ký số tập thể. a) Thuật toán hình thành tham số và khóa<br /> Chữ ký tập thể được hình thành trên cơ sở chữ ký Thuật toán 1.1a: Hình thành các tham số hệ<br /> cá nhân của thực thể ký (một hoặc một nhóm đối thống.<br /> tượng ký) và chứng nhận của CA với vai trò chứng Input: lp, lq - độ dài (tính theo bit) của số<br /> thực của tổ chức đối với thông điệp dữ liệu cần ký. nguyên tố p, q.<br /> Có thể hình thành chữ ký tập thể ở 2 dạng như sau: Output: p, q, g, H(.).<br /> • Chữ ký tập thể dạng kết hợp: ở dạng này CA [1]. select p, q: len(p) = lp, len(q)= lq, q|(p-1)<br /> ký trực tiếp lên thông điệp dữ liệu như các [2]. select: h ∈ ℤp*<br /> thành viên khác, chữ ký của CA và chữ ký<br /> [3]. g ← h ( p −1)/ q mod p (1.1)<br /> cá nhân của các đối tượng ký được kết hợp<br /> với nhau theo một qui tắc nhất định để hình [4]. if (g = 1) then goto [2]<br /> thành chữ ký tập thể. [5]. select H: {0,1}* → Zq<br /> • Chữ ký tập thể dạng phân biệt: ở dạng này [6]. return {p, q, g, H(.)}<br /> chữ ký tập thể bao gồm chữ ký cá nhân của Chú thích:<br /> thực thể ký và chữ ký của CA là 2 thành - len(.) là hàm tính độ dài (theo bit) của một số.<br /> phần phân biệt hay tách biệt nhau. Thuật toán 1.1b: Hình thành khóa.<br /> Trong bài báo, chữ ký tập thể dạng phân biệt Input: p, q, g, x – khóa bí mật của đối<br /> được sử dụng do có khả năng chống lại hiệu quả các tượng ký U.<br /> kiểu tấn công tập thể từ bên trong hệ thống. Output: y – khóa công khai của đối tượng ký U.<br /> Ở lược đồ chữ ký tập thể mới đề xuất, chứng [1]. y ← g − x mod p (1.2)<br /> nhận của CA về việc một hay một nhóm đối tượng [2]. return (y)<br /> ký lên một thông điệp dữ liệu được thực hiện qua b) Thuật toán hình thành chữ ký<br /> các bước: Thuật toán 1.2: Hình thành chữ ký.<br /> • Kiểm tra tính hợp pháp của các đối tượng Input: p, q, g, H(.), k, x, M – thông điệp dữ liệu<br /> ký. cần ký.<br /> • Kiểm tra tính hợp lệ của chữ ký cá nhân. Output: (r,s) – chữ ký của U lên M.<br /> • CA chứng thực tính hợp lệ của chữ ký cá [1]. e ← H (M ) (1.3)<br /> nhân với thông điệp dữ liệu bằng cách ký lên [2]. r ← (g mod )p mod q<br /> k<br /> (1.4)<br /> bản tin được tạo ra từ thông điệp dữ liệu cần<br /> [3]. s ← k × e −1 + x × r mod q (1.5)<br /> ký và khóa công khai của các đối tượng ký.<br /> Bằng cách đó, lược đồ chữ ký tập thể mới đề [4]. return (r,s)<br /> xuất có khả năng ngăn chặn hiệu quả các dạng tấn c) Thuật toán kiểm tra chữ ký<br /> công tập thể từ bên trong hệ thống do các đối tượng Thuật toán 1.3: Kiểm tra chữ ký.<br /> ký là thành viên của chính tổ chức đó liên kết với Input: p, q, g, y, H(.), M, (r,s).<br /> nhau gây ra. Kiểm tra tính hợp lệ của chữ ký tập thể Output: (r,s) = true / false.<br /> được thực hiện qua các bước: [1]. e ← H (M ) (1.6)<br /> • Kiểm tra chứng nhận của CA. [2]. u ← (g × y mod p )mod q<br /> s .e r .e<br /> (1.7)<br /> • Kiểm tra tính hợp lệ của chữ ký cá nhân. [3]. if (u = r) then {return true} (1.8)<br /> Chú ý: else {return false}<br /> Kiểm tra chữ ký cá nhân cần phải được thực hiện<br /> sau khi kiểm tra chứng nhận của CA, nếu chứng d) Tính đúng đắn của lược đồ cơ sở<br /> nhận của CA và chữ ký cá nhân được công nhận hợp Chứng minh tính đúng đắn của lược đồ cơ sở<br /> lệ thì tính toàn vẹn của thông điệp dữ liệu cần thẩm được thực hiện dựa trên các cơ sở như sau:<br /> tra được bảo đảm, đồng thời khẳng định thông điệp Bổ đề 1.1:<br /> dữ liệu này được ký bởi các đối tượng là thành viên Cho p và q là 2 số nguyên tố với q là ước số của<br /> của tổ chức. (p-1), h là một số nguyên dương nhỏ hơn p. Nếu:<br /> g = h ( p −1) / q mod p thì: g q mod p = 1 .<br /> B. Xây dựng lược đồ chữ ký số tập thể Chứng minh:<br /> 1) Lược đồ cơ sở Ta có:<br /> Lược đồ cơ sở ở đây được xây dựng theo [5] và g q mod p = (h ( p −1) / q mod p ) mod p = h ( p −1) mod p<br /> q<br /> <br /> được sử dụng để xây dựng lược đồ chữ ký tập thể ở<br /> Theo định lý Fermat thì: h ( p−1) mod p = 1<br /> mục tiếp theo, bao gồm các thuật toán hình thành<br /> Vì vậy: g q mod p = 1 . Bổ đề được chứng minh.<br />  Hội thảo quốc gia lần thứ XVIII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-TP HCM,05-06/11/2015<br /> <br /> <br /> Bổ đề 1.2: e) Mức độ an toàn của lược đồ cơ sở<br /> Cho p và q là 2 số nguyên tố với q là ước số của Lược đồ cơ sở là một lược đồ chữ ký số xây<br /> (p -1), h là một số nguyên dương nhỏ hơn p và dựng dựa trên tính khó của bài toán logarit rời rạc –<br /> g = h ( p −1) / q mod p . Nếu: m mod q = n mod q thì: DLP (Discrete Logarithm Problem) tương tự như các<br /> g m mod p = g n mod p . lược đồ chữ ký thuộc họ ElGamal như DSA [3] hay<br /> GOST R34.10-94 [4]. Do vậy, mức độ an toàn của<br /> Chứng minh:<br /> lược đồ cơ sở xét theo khả năng chống tấn công làm<br /> Nếu: m mod q = n mod q thì: m = n + k × q hoặc:<br /> lộ khóa mật hoàn toàn phụ thuộc vào mức độ khó<br /> n = m + k × q , với k là một số nguyên. Không làm của bài toán DLP như ở DSA hay GOST R34.10-94.<br /> mất tính tổng quát, giả sử: m = n + k × q . Về khả năng chống giả mạo chữ ký của lược đồ<br /> Do đó: cơ sở, từ (1.6), (1.7) và (1.8) cho thấy 1 cặp (r,s) bất<br /> kỳ sẽ được coi là chữ ký hợp lệ với M nếu thỏa mãn<br /> g m mod p = g n+ k .q mod p = g n × g k .q mod p<br /> điều kiện: r = (g s.e × y r .e mod p )mod q (1.10)<br /> ( ) (<br /> = g n mod p × g k .q mod p mod p ) Ở đây: e = H (M ) là giá trị đại diện của thông<br /> = (g mod p )× (g )<br /> k<br /> n<br /> mod p mod p q<br /> điệp dữ liệu cần thẩm tra (M). Dễ dàng thấy rằng<br /> Theo Bổ đề 1.1 ta có: g q mod p = 1 . Nên: việc giải (1.10) để để tạo được chữ ký giả mạo thỏa<br /> mãn điều kiện hợp lệ của lược đồ cơ sở thực chất<br /> ( )<br /> g m mod p = g n mod p × 1k mod p = g n mod p<br /> cũng là việc giải bài toán DLP.<br /> Bổ đề đã được chứng minh.<br /> 2) Lược đồ chữ ký tập thể<br /> Mệnh đề 1.1:<br /> Lược đồ chữ ký tập thể ở đây được phát triển từ<br /> Cho p và q là 2 số nguyên tố với q là ước số của<br /> lược đồ cơ sở với các chức năng như sau:<br /> (p-1), h là một số nguyên dương nhỏ hơn p<br /> • Chứng nhận tính hợp pháp của các đối tượng<br /> và g = h ( p −1) / q mod p , 1 < x, k < p, 1 < e1, e2 < q.<br /> ký.<br /> Nếu: y = g − x mod p , r = (g k mod p )mod q , • Hình thành chữ ký tập thể từ chữ ký cá nhân<br /> −1<br /> s = k × e1 + x × e2 mod q thì: của một hay một nhóm đối tượng ký và chữ<br /> (g × y mod p )mod q = r .<br /> e .s<br /> 1 e .e<br /> 1 2 ký của CA. Kích thước của chữ ký tập thể<br /> Chứng minh: được tạo ra không phụ thuộc vào số lượng<br /> Thật vậy, ta có: thành viên nhóm ký.<br /> −1 • Kiểm tra chữ ký tập thể của một nhóm đối<br /> s = k × e1 + x × e2 mod q tượng được thực hiện tương tự như kiểm tra<br /> −1<br /> = e1 × (k + x × e1 × e2 ) mod q chữ ký do một đối tượng ký tạo ra.<br /> Nên: s × e1 mod q = k + x × e1 × e2 mod q Các tham số hệ thống {p, q} được lựa chọn theo<br /> phương pháp của DSA hoặc GOST R34.10-94. Giả<br /> Theo Bổ đề 1.2 ta có: sử nhóm ký gồm n-thành viên: U = {Ui| i=1,2,...,n}.<br /> g e1.s mod p = g k + x.e1 .e2 mod p Các thành viên nhóm ký có khóa bí mật là: KS = {xi|<br /> Suy ra: g e1.s × g − x.e1.e2 mod p = g k mod p i=1,2,...,n} và các khóa công khai tương ứng là: KP<br /> Hay: g e1.s × y e1 .e2 mod p = g k mod p = {yi| i=1,2,...,n}. Còn CA có cặp khóa bí mật/công<br /> khai tương ứng là: {xca, yca}.<br /> Nên ta có:<br /> (g e1.s × y e1.e2 mod p )mod q = (g k mod p )mod q a) Thuật toán hình thành khóa của các đối<br /> Do: tượng ký<br /> r = (g k mod p )mod q<br /> Thuật toán 2.1: Hình thành khóa của các đối<br /> Dẫn đến: (g e1.s × y e1.e2 mod p ) mod q = r tượng ký U = {Ui| i=1,2,.,n}.<br /> Đây là điều cần chứng minh. Input: p, g, n, KS = {xi| i = 1,2,…,n}.<br /> Chứng minh tính đúng đắn của lược đồ cơ sở là Output: KP = {yi| i = 1, 2,..,n}.<br /> chứng minh chữ ký được tạo ra bởi thuật toán hình [1]. for i = 1 to n do<br /> thành chữ ký (Thuật toán 1.2) sẽ thỏa mãn điều kiện [1.1]. y i ← g − xi mod p (2.1)<br /> (1.8) của thuật toán kiểm tra chữ ký (Thuật toán<br /> 1.3). Tính đúng đắn của lược đồ cơ sở được chứng [1.2]. K p [i ] ← y i<br /> minh như sau: [2]. return KP<br /> Đặt: e1 = e, e2 = r. Theo (1.1), (1.2), (1.3), (1.4), b) Thuật toán hình thành khóa của CA<br /> (1.5) và Mệnh đề 1.1 ta có: Thuật toán 2.2: Hình thành khóa của CA.<br /> (g s.e × y r.e mod p )mod q = r (1.9) Input: p, g, xca.<br /> Từ (1.6), (1.7) và (1.9) suy ra: u = r. Output: yca.<br /> Mệnh đề đã được chứng minh. [1]. y ca ← g − xca mod p (2.2)<br />  Hội thảo quốc gia lần thứ XVIII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-TP HCM,05-06/11/2015<br /> <br /> <br /> [2]. return yca f) Thuật toán hình thành chứng nhận của CA<br /> c) Thuật toán hình thành chứng nhận (chứng đối với chữ ký cá nhân của một hay một nhóm đối<br /> chỉ số) của CA cho các đối tượng ký Ui tượng ký lên M<br /> Thuật toán 2.3: CA chứng nhận tính hợp pháp Thuật toán 2.6: Hình thành chứng nhận của CA<br /> của đối tượng ký Ui. cho chữ ký cá nhân với thông điệp dữ liệu M.<br /> Input: IDi, yi, xca. Input: p, q, g, xca, n, KP = {yi| i =1, 2,..,n},<br /> Output: (ui,vi) – chứng nhận của CA đối với Ui. (ui,vi),{M, (r,s)}.<br /> [1]. ki ← H ( xca || yi || IDi ) Output: (uM,vM) – chứng nhận của CA đối với<br /> ( )<br /> [2]. ui ← g k i mod p mod q (2.3) {M, (r,s)}.<br /> [1]. y ← 1; for i = 1 to n do<br /> [3]. e ← H ( yi || IDi ) (2.4) [1.1]. e ← H ( yi || IDi )<br /> [4]. vi ← ki × e −1 + xca × ui mod q (2.5)<br /> ( )<br /> [1.2]. u ← g vi .e × ( yca )ui .e mod p mod q<br /> [5]. return (ui,vi); [1.3]. if (u ≠ ui) then return (0,0)<br /> d) Thuật toán kiểm tra tính hợp pháp của các [1.4]. y ← y × yi mod p<br /> đối tượng ký Ui (i=1,2,..,n)<br /> [2]. if ( r = 0 or s = 0) then {return (0,0)} else<br /> Thuật toán 2.4: Kiểm tra tính hợp pháp các đối<br /> [2.1]. e ← H (M )<br /> tượng ký.<br /> Input: yi, yca, IDi, (ui, vi). ( )<br /> [2.2]. u ← g s.e × y r .e mod p mod q<br /> Output: (ui,vi) = true / false. [2.3]. if (u ≠ r) then {return (0,0)}<br /> [1]. e ← H ( yi || IDi ) (2.6) [3]. k ← H ( xca || y || M )<br /> ( )<br /> [2]. u ← g vi .e × ( y ca )ui .e mod p mod q (2.7) [4]. u M ← (g k mod p )mod q (2.13)<br /> [3]. if (u = ui) then {return true} [5]. e ← H ( y || M ) (2.14)<br /> else {return false} [6]. vM ← k × e + xca × u M mod q<br /> −1<br /> (2.15)<br /> e) Thuật toán hình thành chữ ký cá nhân của [7]. return (uM,vM)<br /> một hay một nhóm đối tượng ký lên thông điệp dữ<br /> liệu M g) Thuật toán kiểm tra chữ ký tập thể của một<br /> Thuật toán 2.5: Hình thành chữ ký cá nhân. hay một nhóm đối tượng ký lên thông điệp dữ liệu M<br /> Input: M, n, KS = {xi| i = 1, 2,..,n}, Thuật toán 2.7: Kiểm tra chữ ký tập thể.<br /> KP = {yi| i = 1, 2,..,n}. Input: p, q, g, n, yca, KP={yi| i =1, 2,.., n},<br /> Output: (r,s) – chữ ký của Ui (i = 1, 2,..) lên M. M,{(r,s), (uM,vM)}.<br /> [1]. for i = 1 to n do Output: {(r,s), (uM,vM)} = true / false.<br /> [1.1]. k i ← H ( xi || M ) [1]. y ← 1; for i = 1 to n do<br /> y ← y × yi mod p (2.16)<br /> [1.2]. ri ← g k i mod p (2.8)<br /> [2]. if (uM = 0 or vM = 0) then return false<br /> [1.3]. Ui send ri to CA<br /> [2]. r ← 1; [2.1]. e ← H ( y || M ) (2.17)<br /> [2.1]. for i = 1 to n do ( uM .e<br /> )<br /> [2.2]. u ← g × ( yca ) mod p mod q (2.18)<br /> vM . e<br /> <br /> r ← r × ri mod p (2.9) [2.3]. if (u ≠ uM) then return false<br /> [2.2]. CA send r to Ui (i = 1, 2,.., n) [3]. if ( r = 0 or s = 0) then {return false} else<br /> [3]. for i = 1 to n do [3.1]. e ← H (M ) (2.19)<br /> [3.1]. e ← H (M ) (2.10)<br /> [3.2]. si ← ki × e −1 + xi × r mod q (2.11)<br /> ( )<br /> [3.2]. u ← g s.e × y r .e mod p mod q (2.20)<br /> [3.3]. if (u = r) then {return true}<br /> [3.3]. Ui send si to CA else {return false}<br /> [4]. s ← 1; for i = 1 to n do<br /> [4.1]. if ( ri ≠ g si .e × ( yi )ri .e mod p ) then 3) Tính đúng đắn của lược đồ chữ ký tập thể<br /> return (0,0) Tính đúng đắn của lược đồ mới đề xuất bao gồm:<br /> [4.2]. s ← s × si mod q (2.12) a) Tính đúng đắn của thuật toán chứng nhận<br /> [5]. return (r,s). và kiểm tra đối tượng ký.<br /> Chú thích: Đặt: e1 = e, e2 = ui, s = vi, x = xca, y = yca. Theo<br /> - Bước [1] và [3] được thực hiện bởi Ui (i = 1, (2.2), (2.3), (2.5) và Mệnh đề 1.1 ta có:<br /> 2,.., n). ( g vi .e × ( yca ) ui .e mod p ) mod q = ui (2.21)<br /> - Bước [2] và [4] được CA thực hiện.<br />  Hội thảo quốc gia lần thứ XVIII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-TP HCM,05-06/11/2015<br /> <br /> <br /> Từ (2.21) và (2.7) suy ra: u = ui 4) Mức độ an toàn của lược đồ chữ ký tập thể<br /> Đây là điều cần chứng minh. Mức độ an toàn của lược đồ chữ ký tập thể mới<br /> b) Tính đúng đắn của thuật toán hình thành và đề xuất được thiết lập dựa trên mức độ an toàn của<br /> kiểm tra chứng nhận của CA đối với chữ ký cá nhân lược đồ cơ sở. Do vậy, về cơ bản mức độ an toàn của<br /> của một đối tượng ký. nó được quyết định bởi mức độ khó của bài toán<br /> Đặt: e1 = e, e2 = uM, s = vM, y = yca. Theo (2.2), DLP. Ngoài ra, ở lược đồ chữ ký tập thể còn tiềm ẩn<br /> các nguy cơ tấn công giả mạo chữ ký từ ngay bên<br /> (2.13), (2.14), (2.15) và Mệnh đề 1.1, ta có:<br /> trong hệ thống do một nhóm đối tượng ký liên kết<br /> ( u .e<br /> g vM .e × ( yca ) M mod p mod q = u M (2.22) ) với nhau thực hiện. Vấn đề này được xem xét dưới<br /> Từ (2.16), (2.17), (2.18) và (2.22) suy ra: góc độ Bài toán giả mạo chữ ký nhóm như sau:<br /> u = uM a) Bài toán giả mạo chữ ký nhóm<br /> Đây là điều cần chứng minh. Cho U và U* với U ⊄ U* là hai nhóm các đối<br /> c) Tính đúng đắn của thuật toán hình thành và tượng trong hệ thống có các tham số {p, q, g}.<br /> kiểm tra chữ ký cá nhân của một nhóm đối tượng ký. Giả thiết: U* = {U*i| i=1...m*}, U' = {U'i|<br /> Mệnh đề 1.2: i=1...m'}, U*∩U' = ∅ và U*∪U' = U. (3.1)<br /> Cho p và q là 2 số nguyên tố với q là ước số của Khi này Bài toán giả mạo chữ ký nhóm có thể<br /> (p -1), h là một số nguyên dương nhỏ hơn p và được mô tả như sau:<br /> g = h ( p −1) / q mod p , 1 < xi, ki < q, 1 < e1, e2 < q. Bài toán LD(U,U*): Cho các tham số bí mật của<br /> Nếu: , ri = g k mod p , các thành viên trong U*. Khi đó với mỗi thông báo<br /> yi = g − xi mod p i<br /> <br /> M, hãy tìm cặp {r,s} được chấp nhận theo điều kiện<br /> si = ki × e1 + xi × e2 mod q<br /> −1<br /> với: i = 1, n , của thuật toán kiểm tra chữ ký (Thuật toán 2.7) với<br /> n<br />  n<br />  đầu vào là bộ tham số công khai của U.<br /> y = ∏ yi mod p , r =  ∏ ri mod p  mod q , Bài toán LD(U’,U*): Cho các tham số bí mật của<br /> i =1  i =1  các thành viên trong U*. Khi đó với mỗi thông báo<br /> n<br /> s = ∑ si mod q thì: (g e1 . s<br /> )<br /> × y e1.e2 mod p mod q = r . M, hãy tìm cặp {r’,s’} được chấp nhận theo điều kiện<br /> của thuật toán kiểm tra chữ ký (Thuật toán 2.7) với<br /> i =1<br /> Chứng minh: đầu vào là bộ tham số công khai của U’.<br /> Thật vậy, ta có: Giải thuật cho bài toán LD(U,U*) được gọi là<br /> "thuật toán giả mạo chữ ký của U lên M do U* thực<br /> (g e1 . s<br /> × y e1.e2 mod p mod q = ) hiện". Còn giải thuật cho bài toán LD(U’,U*) được gọi<br />  e1.∑<br /> n<br /> ki .e1−1 + xi .e2<br /> e1 .e2  là "thuật toán giả mạo chữ ký của U’ lên M do U*<br /> <br /> mod q<br />  n   thực hiện".<br /> =  g i =1 ×  ∏ yi mod p  mod p  mod q<br />   i =1   b) Giải thuật cho bài toán LD(U,U*)<br />  <br />  e1.∑ ki .e1−1<br /> n n n<br />  Thuật toán 3.1 Giải thuật cho bài toán LD(U,U*).<br /> e1 .∑ xi .e2 − ∑ xi .e1 .e2 .<br />   Input: p, q, g, M, (r’,s’) – chữ ký của U' lên M.<br /> =  g i =1 × g i =1 × g i =1 mod p  mod q<br />   Output: (r,s) – chữ ký của U lên M do U* tạo ra.<br />  <br /> [1]. s∗ ← 0<br />  ∑ ki <br /> n<br /> <br />    n<br />  [2]. for i = 1 to m* do<br /> =  g i =1 mod p  mod q =  ∏ g ki mod p mod p  mod q( ) (3.2)<br />    i=1  s ∗ ← s ∗ + xi∗ × r ' mod q<br />  <br />  n<br />  [3]. s ← s'+ s ∗ mod q (3.3)<br /> =  ∏ ri mod p  mod q = r [4]. r ← r ' (3.4)<br />  i=1 <br /> [5]. return (r,s);<br /> Từ đó tính đúng đắn của thuật toán hình thành và Tính đúng đắn của Thuật toán 3.1 được chứng<br /> kiểm tra chữ ký của một hoặc một nhóm đối tượng minh như sau:<br /> ký lên một thông điệp dữ liệu M được chứng minh Từ (3.2) với mọi: i = 1,2,..,m*, ta có:<br /> như sau:<br /> Đặt: e1 = e, e2 = r. Theo (2.9), (2.10), (2.12),<br /> ∗<br /> ( )<br /> g si .e × y i∗<br /> r '.e<br /> mod p = g xi .r '.e × g − xi .r '.e mod p = 1 (3.5)<br /> ∗ ∗<br /> <br /> <br /> <br /> <br /> (2.16) và Mệnh đề 1.2, ta có: Với điều kiện (3.1), dễ dàng kiểm tra được rằng:<br /> (<br /> g s .e × y r .e mod p mod q = r (2.23) ) m<br /> ∗<br /> <br /> Từ (2.23) và (2.20) suy ra: u = r y = y '× ∏ y i∗ mod p  mod q (3.6)<br /> Mệnh đề đã được chứng minh.  i =1 <br /> Từ (3.5) và (3.6) ta có:<br />  Hội thảo quốc gia lần thứ XVIII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông-TP HCM,05-06/11/2015<br /> <br /> <br /> (g s .e<br /> × y r .e mod p mod q = ) Từ (2.20), (3.11) và (3.14) suy ra:<br />   m∗ <br /> <br /> u = r’ (3.15)<br />  ∗<br />  ∑<br />  s ' + si .e   m∗  <br /> r .e<br />  Từ (3.15) cho thấy, mặc dù (r’,s’) do U* tạo ra<br /> =g ×  y '× ∏ yi∗ mod p  mod p  mod p  mod q<br />  i =1 <br /> <br />  <br /> nhưng vẫn được công nhận là chữ ký hợp lệ của U’<br />   i =1  <br />   lên M, nói cách khác Thuật toán 3.2 đã được chứng<br />   m∗ <br /> <br /> minh là đúng.<br />  ∗<br />  ∑ si  .e<br /> r .e<br />  m<br /> ∗<br />   d) Mức độ an toàn của lược đồ chữ ký tập thể<br /> =  g × ( y ') × g   ×  ∏ yi∗  mod<br /> s '.e r .e<br /> p  mod q<br /> i =1<br /> <br /> <br />   i =1   trước các tấn công giả mạo chữ ký nhóm.<br />   Từ việc xem xét Bài toán LD(U,U*) và LD(U',U*)<br /> <br /> ∗<br />  cho thấy việc xây dựng theo mô hình chữ ký tập thể<br /> m<br /> =  g s '.e × ( y ') × ∏ g si .e × yi∗<br /> r '.e ∗<br /> ( ( ) r '.e<br /> )<br /> mod p mod p  mod q dạng phân biệt, mà ở đó CA tạo chứng nhận về tính<br />  i =1  hợp lệ của chữ ký cá nhân của một đối tượng ký hay<br /> (<br /> = g s '.e × ( y ')<br /> r '.e<br /> mod p mod q = r ' ) của một nhóm đối tượng ký lên một thông điệp dữ<br /> (3.7) liệu bằng cách ký lên bản tin được tạo ra từ thông<br /> Từ (2.20), (3.4) và (3.7) suy ra: điệp dữ liệu cần ký và khóa công khai chung của<br /> nhóm đối tượng ký, vì thế lược đồ chữ ký tập thể<br /> u=r (3.8)<br /> mới đề xuất có khả năng ngăn chặn hoàn toàn các<br /> Từ (3.8) cho thấy, mặc dù (r,s) do U* tạo ra<br /> dạng tấn công giả mạo từ bên trong hệ thống đã biết<br /> nhưng vẫn được công nhận là chữ ký hợp lệ của U<br /> trong thực tế.<br /> lên M.<br /> c) Giải thuật cho bài toán LD(U',U*) III. KẾT LUẬN<br /> Thuật toán 3. 2 Giải thuật cho bài toán LD(U',U*). Bài báo đề xuất một mô hình ứng dụng chữ k ý<br /> Input: p, q, g, M, (r,s) - chữ ký của U lên M. số gọi là mô hình chữ ký tập thể và lược đồ chữ<br /> Output: (r’,s’) - chữ ký của U' lên M do k ý số theo mô hình ứng dụng này có thể áp dụng<br /> U* tạo ra. cho đối tượng là các cơ quan, đơn vị, doanh<br /> [1]. s∗ ← 0 nghiệp,... nhằm đảm bảo cho việc chứng thực các<br /> [2]. for i = 1 to m* do thông điệp dữ liệu trong các thủ tục hành chính<br /> s ∗ ← s ∗ + xi∗ × r mod q (3.9) điện tử hoàn toàn phù hợp với các thủ tục hành<br /> [3]. s ' ← s − s mod q<br /> ∗<br /> (3.10) chính trong thực tế xã hội hiện nay. Theo mô hình<br /> mới đề xuất, các thông điệp dữ liệu điện tử sẽ<br /> [4]. r ' ← r (3.11)<br /> được chứng thực về nguồn gốc và tính toàn vẹn ở<br /> [5]. return (r’,s’);<br /> cả 2 cấp độ: thực thể tạo ra thông điệp dữ liệu và<br /> Tính đúng đắn của Thuật toán 3.2 được chứng<br /> tổ chức (cơ quan, đơn vị,...) mà thực thể tạo ra nó<br /> minh như sau:<br /> là một thành viên hay bộ phận của tổ chức này.<br /> Từ (3.9) với mọi: i = 1,2,..,m*, ta có:<br /> ∗<br /> g − si .e × y i∗ ( ) − r .e ∗ ∗<br /> mod p = g − xi .r .e × g xi .r .e mod p = 1 TÀI LIỆU THAM KHẢO<br /> (3.12) [1] C. Adams, “Understanding Public Key Infrastructures”,<br /> Với điều kiện (3.1), dễ dàng kiểm tra được rằng: New Riders Publishing, Indianapolis, 1999.<br /> m <br /> ∗<br /> (3.13) [2] R. Housley, W. Polk, W. Ford, D. Solo, “Internet X.509<br /> y ' = y ×  ( y ∗ ) mod p  mod p<br /> −1<br /> ∏ i  Public Key Infrastructure Certificate and Certificate<br />  i =1  Revocation List (CRL) Profile”, RFC 3280, 2002.<br /> Từ (2.12) và (2.13) ta có: [3] National Institute of Standards and Technology, NIST FIPS<br /> PUB 186-3. Digital Signature Standard, U.S. Department of<br /> (g s '. e<br /> × ( y ')<br /> r '. e<br /> ) (<br /> mod p mod q = g (s −s ).e × ( y') mod p mod q<br /> r .e∗<br /> ) Commerce,1994.<br />   s − m∗ s∗ .e  [4] GOST R 34.10-94. Russian Federation Standard.<br />   ∑ i <br />    m∗ ∗ −1  <br /> r. e<br />  Information Technology. Cryptographic data Security.<br /> = g  i =1 <br /> ×  y ×  ∏ ( yi ) mod p  mod p  mod p  mod q Produce and check procedures of Electronic Digital<br />    i =1   <br /> Signature based on Asymmetric Cryptographic Algorithm.<br />  <br /> Government Committee of the Russia for Standards, 1994<br />   m∗ <br />  ∗  (in Russian).<br />  − ∑ si . e<br /> − r .e<br />  s. e m<br /> ∗<br />  <br /> r.e<br /> ×  ∏ y i∗  mod p  mod q<br /> i =1<br /> =  g × y × g <br /> [5] Lưu Hồng Dũng, Lê Đình Sơn, Hồ Nhật Quang, Nguyễn<br />   i =1   Đức Thụy, Developing Digital Signature Schemes Base on<br />   Discrete Logarithm Problem, Kỷ yếu Hội nghị Khoa học<br /> <br /> ∗<br />  Quốc gia lần thứ 8 về Nghiên cứu Cơ bản và Ứng dụng<br /> m<br /> (<br /> =  g s.e × y r.e × ∏ g − si .e × ( yi∗ ) mod p mod p  mod q<br /> ∗ − r. e<br /> ) Công nghệ Thông tin (FAIR 2015 – Fundamental and<br />  i =1  Applied IT Reseach) 9-10/7/2015.<br /> <br /> = (g s.e × y r.e mod p)modq = r (3.14)<br />