Nghiên cứu xây dựng lược đồ chữ ký số tập thể

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> <br /> Nghiên cứu xây dựng lược đồ chữ ký số tập thể<br /> Research and Construction of Digital Multi-Signature Schemes<br /> Lưu Hồng Dũng<br /> <br /> Abstract: This paper proposed two new digital II. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TẬP<br /> signature schemes has the option of using keys as THỂ<br /> follows: use a unique key; use two keys, both of Các lược đồ chữ ký số được đề xuất ở đây xây<br /> which key value does not change; use two keys, dựng trên cơ sở bài toán logarit rời rạc tương tự như<br /> primary key is fixed, subkey change with each time các hệ chữ ký số Elgamal [3], chuẩn chữ ký số DSS<br /> to sign. The paper also offers analysis on the safety của Mỹ [4], hay chuẩn chữ ký số của Liên bang Nga<br /> of the proposed schemes, has shown the ability to GOST R34.10-94 [5]. Trong đó, lược đồ chữ ký tập<br /> apply it in practice. thể được phát triển từ lược đồ chữ ký cơ sở có dạng<br /> như sau:<br /> I. ĐẶT VẤN ĐỀ<br /> 1. Lược đồ chữ ký cơ sở - LD 1.01<br /> Chữ ký số (Digital Signature) được sử dụng để<br /> chứng thực các văn bản trong các giao dịch điện tử, 1.1. Thuật toán hình thành và kiểm tra chữ ký số<br /> nhằm đáp ứng các yêu cầu về: tính xác thực, tính toàn a) Hình thành các tham số công khai:<br /> vẹn và tính chống chối bỏ trách nhiệm [1,2]. Ở các + Phát sinh cặp số nguyên tố p và q đủ lớn và: q|(p –<br /> 1).<br /> lược đồ chữ ký số như ElGamal, Schnorr, chuẩn chữ<br /> + Phát sinh g = α ( p −1) / q mod p , là phần tử sinh có<br /> ký số DSS của Mỹ hay GOST R34.10-94 của Liên<br /> 1 < g < p và:<br /> *<br /> bang Ngay,... khóa bí mật được sử dụng với mục đích: bậc q của nhóm Zp , nghĩa là:<br /> xác thực và chống giả mạo chữ ký. Do đó nó phải g q ≡ 1 mod p . Ở đây: α ∈Z<br /> *<br /> p .<br /> được giữ cố định đối với mọi văn bản ký, nhưng việc<br /> Các giá trị (p, q, g) là các tham số công khai trong<br /> phải được giữ cố định sẽ làm cho nó có thể bị bẻ một<br /> quá trình hình thành và kiểm tra chữ ký.<br /> cách dễ dàng. Để chống lại việc bẻ khóa, các lược đồ<br /> b) Hình thành khóa công khai:<br /> dạng trên phải sử dụng một khóa bí mật thứ hai, khóa<br /> Thủ tục hình thành khóa công khai bao gồm các<br /> này cần phải được thay đổi theo từng văn bản ký, hơn<br /> bước thực hiện sau:<br /> nữa giá trị của nó cho mỗi lần ký không được trùng<br /> 1- Khóa bí mật x là một giá trị được chọn ngẫu<br /> với các giá trị đã sử dụng ở những lần ký trước đó.<br /> nhiên trong khoảng: 1 < x < q − 1 .<br /> Như vậy, có thể nói rằng các lược đồ nói trên thuộc<br /> dạng sử dụng khóa một lần, trước mỗi lần ký đều phải 2- Khóa công khai được tính theo công thức:<br /> sinh khóa mới, trên thực tế giá trị của khóa thứ 2 trước y = g − x mod p .<br /> mỗi lần ký được tạo ra bởi một bộ sinh số ngãu nhiên. 3- Công khai y.<br /> Bài báo này đề xuất một giải pháp mà có thể đưa các c) Hình thành chữ ký số:<br /> lược đồ trên về dạng sử dụng một khóa cho nhiều lần Thủ tục hình thành chữ ký được thực hiện theo các<br /> ký khác nhau, điều đó có thể giúp cho việc triển khai bước như sau:<br /> thực hiện được thuận tiện hơn mà không làm giảm độ 1- Chọn k thỏa mãn: 1 < x < q − 1 .Tính r theo công<br /> an toàn của các lược đồ này. thức:<br /> <br /> <br /> <br /> - 49 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> r = g h ( k || M ) mod p ; 1.3. Mức độ an toàn của lược đồ mới đề xuất<br /> 2- Thành phần thứ nhất e của chữ ký được tính theo Ở lược đồ mới đề xuất, có thể thấy rằng công thức<br /> công thức : tính thành phần thứ hai (s) của chữ ký tương tự như<br /> GOST R34.10-94 hay lược đồ chữ ký Schnorr. Tuy<br /> e = h(r || M ) mod q<br /> nhiên, ở lược đồ mới đề xuất đã sử dụng giá trị<br /> 3- Thành phần thứ hai s của chữ ký được tính theo<br /> h(k || M ) thay cho k như trong lược đồ chữ ký<br /> công thức:<br /> s = h(k || M ) + x.e mod q Schnorr hay thay cho k .h( M ) trong GOST R34.10-<br /> <br /> 4- Cặp giá trị (e, s ) là chữ ký vào văn bản M. 94. Vì vậy, nếu giá trị h(k || M ) tương đương với giá<br /> <br /> Chú ý: trị k trong lược đồ chữ ký Schnorr hay tương đương<br /> + h() là hàm băm kháng va chạm mạnh. Ví dụ: nếu với k .h( M ) trong GOST R34.10-94 thì mức độ an<br /> chọn |q| = 160 bit thì hàm băm có thể chọn là SHA-1. toàn của lược đồ mới đề xuất sẽ hoàn toàn tương<br /> + Toán tử || là phép nối xâu. đương với 2 lược đồ chữ ký kia.<br /> d) Kiểm tra chữ ký số: Ta xét việc chọn k theo 3 phương án như sau:<br /> Thủ tục kiểm tra được thực hiện qua các bước sau: - Chọn k = x: Trường hợp này ta có lược đồ chỉ sử<br /> 1- Tính: dụng một khóa với một lần chọn duy nhất. Dễ dàng<br /> r ' = g s . y e mod p ; thấy rằng, giá trị h(k || M ) là sự kết hợp của 3 yếu tố:<br /> 2- Tính: bí mật (khóa mật x), ngẫu nhiên (văn bản cần M) và<br /> e' = h(r ' || M ) mod q một chiều (hàm băm h()) nên giá trị h( x || M ) hoàn<br /> 3- Kiểm tra nếu: e’ = e thì tính hợp lệ của chữ ký toàn thỏa mãn các yêu cầu thay thế cho giá trị k được<br /> và tính toàn vẹn của văn bản cần thẩm tra được công sinh ra bằng một thuật toán sinh số ngẫu nhiên. Một<br /> nhận. Ngược lại, chữ ký đã bị giả mạo hoặc nội dung điều rõ ràng là không ai có thể tính được giá trị này<br /> văn bản đã bị sửa đổi. ngoài người ký (chỉ người ký mới biết khóa mật x),<br /> giá trị này thay đổi theo từng văn bản ký và quan trọng<br /> 1.2. Tính đúng đắn của lược đồ được đề xuất nhất: nó là duy nhất đối với mọi văn bản (mỗi văn bản<br /> Tính đúng đắn của lược đồ được đề xuất ở đây là chỉ được ký một lần), hơn nữa với số lượng văn bản<br /> sự phù hợp giữa thuật toán hình thành chữ ký với thuật cần ký M không đủ lớn thì không thể tính được<br /> toán xác minh chữ ký. Điều cần chứng minh là: Phù<br /> ( x || M ) từ h( x || M ) (tấn công hàm băm theo kiểu<br /> hợp với lược đồ LD 1.01 tồn tại tồn tại đẳng thức:<br /> “ngày sinh” ) để từ đó có thể tính ra x.<br /> e' = e .<br /> - Chọn k ≠ x nhưng cũng chỉ cần chọn một lần duy<br /> Chứng minh:<br /> nhất và giữ cố định như x. Cách này hoàn toàn tương<br /> Từ tính hợp lệ của chữ ký (e,s) ta có:<br /> tự như cách thứ nhất.<br /> r ' = g s . y e mod p - Chọn ngẫu nhiên k bằng cách sử dụng một bộ sinh số<br /> = g h ( k || M )+ x.e mod q .( g − x ) e mod p ngẫu nhiên tương tự như trong DSS hay GOST<br /> = g h ( k || M ) .g x.e .g − x.e mod p R34.10-94,...thì giá trị h( x || M ) hoàn toàn tương<br /> = g h ( k || M ) mod p = r đương với k về khía cạnh an toàn.<br /> Ta thấy rằng, do thành phần r được tính theo công<br /> Từ tính toàn vẹn của văn bản M suy ra:<br /> thức:<br /> e' = h(r ' || M ) mod q<br /> r = g h ( k || M ) mod p<br /> = h(r || M ) mod q = e<br /> nên để tính h(k || M ) từ r, rồi từ đó tính khóa x, theo<br /> Đây là điều cần chứng minh.<br /> công thức:<br /> <br /> - 50 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> s = h(k || M ) + x.e mod q 1- Mỗi thành viên chọn khóa bí mật xi thỏa mãn:<br /> kẻ tấn công buộc phải giải bài toán logarit rời rạc. 1 < xi < q − 1] và tính khóa công khai cá nhân<br /> Mặt khác, với công thức tính thành phần thứ hai s<br /> tương ứng:<br /> của chữ ký:<br /> s = h(k || M ) + x.e mod q yi = g − xi mod p , i = 1, 2, ..., n.<br /> kẻ tấn công cũng không thể giải được hệ phương trình: 2- Khóa công khai tập thể được đại diện nhóm tính<br /> theo công thức:<br /> s1 = h(k || M 1 ) + x.e1 mod q<br /> n<br /> s 2 = h(k || M 2 ) + x.e2 mod q Y = ∏ y i mod p .<br /> i =1<br /> cho dù giá trị của k được giữ nguyên, để từ đó có thể<br /> 3- Công khai Y.<br /> tính được khóa bí mật x. ở đây: (e1 , s1 ) và (e2 , s 2 ) là<br /> Chú ý:<br /> chữ ký tương ứng với 2 văn bản M1 và M2. Để chống giả mạo trong việc hình thành khóa<br /> Như vậy, để ký vào các văn bản khác nhau người công khai tập thể Y thì các khóa công khai cá nhân y i<br /> ký cần chọn một cặp khóa ( x, k ) , trong đó khóa chính<br /> cần phải được công khai trong nhóm và mọi thành<br /> x được giữ cố định, khóa phụ k có thể là cố đinh hoặc<br /> viên của nhóm ký đều phải tham gia tính khóa công<br /> thay đổi theo từng văn bản ký. Trường hợp, nếu chọn<br /> khai tập thể Y, chỉ khi nào có sự xác nhận của tất cả<br /> k thay đổi theo từng văn bản ký thì cũng không cần<br /> các thành viên thì Y mới được công bố làm khóa công<br /> thiết phải sử dụng bộ sinh số ngẫu nhiên như ở các<br /> khai tập thể của nhóm ký.<br /> lược đồ khác, vì lược đồ này cho phép sử dụng các giá<br /> c) Hình thành chữ ký tập thể:<br /> trị của k trùng nhau mà không làm giảm độ an toàn<br /> Thủ tục hình thành chữ ký tập thể bao gồm các<br /> của lược đồ. Hơn nữa nếu chọn k = x thì lược đồ chỉ bước như sau:<br /> cần duy nhất 1 khóa bí mật mà không làm giảm mức<br /> 1 - Mỗi thành viên chọn k i thỏa mãn 1 < k i < q − 1]<br /> độ an toàn, nếu so sánh với các lược đồ như Schnorr<br /> và tính thành phần thứ nhất của chữ ký cá nhân<br /> hay GOST R34.10-94.<br /> theo công thức:<br /> 2. Lược đồ chữ ký tập thể- LD 1.02<br /> ri = g h ( ki || M ) mod p , i = 1, 2, ..., n.<br /> Giả thiết rằng nhóm người có thẩm quyền ký gồm<br /> n thành viên, để ký vào văn bản M. Cần lưu ý rằng, rồi gửi cho đai diện. Ở đây: h() là hàm băm được<br /> trong lược đồ này đại diện nhóm không nhất thiết và chọn đủ an toàn, chẳng hạn: SHA-1 và toán tử || là<br /> nói chung không phải là một thành viên trong nhóm, phép nối 2 xâu.<br /> trên thực tế vai trò của đại diện nhóm có thể do một cơ 2- Đại diện nhóm tính:<br /> n<br /> quan chuyên trách đảm nhiệm. R = ∏ ri mod p ,<br /> i =1<br /> 2.1. Thuật toán hình thành và kiểm tra chữ ký<br /> a) Hình thành các tham số công khai: rồi tính thành phần thứ nhất của chữ ký tập thể:<br /> Các giá trị (p, q, g) là các tham số công khai được E = h( R || M ) mod q<br /> hình thành tương tự như ở lược đồ LD 1.01 Sau đó đại diện nhóm gửi giá trị E cho các thành<br /> b) Hình thành khóa công khai tập thể: viên trong nhóm<br /> Thủ tục hình thành khóa công khai tập thể bao 3- Các thành viên trong nhóm tính phần thứ hai của<br /> gồm các bước như sau: chữ ký cá nhân theo công thức:<br /> si = h(k i || M ) + xi .E mod q , i = 1, 2, ..., n.<br /> rồi gửi s i cho đại diện nhóm. Cặp giá trị (ri , si ) là<br /> <br /> <br /> - 51 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> chữ ký cá nhân của thành viên thứ i vào văn bản M. - Sử dụng 2 khóa: trong đó khóa thứ nhất (xi) được<br /> 4- Sau khi nhận được tất cả chữ ký cá nhân (ri , si ) giữ cố định, còn khóa thứ hai (ki) thay đổi ở mỗi<br /> của các thành viên, đại diện nhóm kiểm tra sự lần ký như các lược đồ hiện tại (DSS, GOST<br /> hợp lệ của các chữ ký này bằng cách tính: R34.10-94,...) đang dùng.<br /> d) Kiểm tra đa chữ ký số:<br /> ri' = y iE .g si mod p , i = 1, 2, ..., n.<br /> Thủ tục kiểm tra được thực hiện qua các bước sau:<br /> và: 1- Từ cặp (E,S) nhận được tính:<br /> n<br /> R ' = ∏ ri' mod p R ' ' = g S .Y E mod p<br /> i =1 2- Tính:<br /> Kiểm tra nếu: R ' = R thì tính hợp lệ các chữ ký cá E ' = h( R ' ' || M ) mod q<br /> nhân của các thành viên được công nhận, đại diện<br /> 3- Kiểm tra nếu: E ' = E thì chữ ký là hợp lệ và tính<br /> nhóm sẽ tính thành phần thứ hai của đa chữ ký theo<br /> toàn vẹn của văn bản được bảo đảm. Ngược lại, chữ<br /> công thức:<br /> ký đã bị giả mạo hoặc nội dung của văn bản đã bị thay<br /> n<br /> S = ∑ s i mod q đổi.<br /> i =1<br /> 2.2. Tính đúng đắn của lược đồ mới xây dựng<br /> 5- Phát hành ( E , S ) cùng văn bản M. Tính đúng đắn của lược đồ mới đề xuất thể hiện<br /> Chú ý: qua tính đúng đắn của thủ tục kiểm tra chữ ký cá nhân<br /> + Để chống giả mạo trong việc tính R thì các giá và tính đúng đắn của thủ tục kiểm tra chữ ký tập thể<br /> trị ri cần phải được công khai trong nhóm và mọi như sau:<br /> thành viên của nhóm ký đều phải tham gia tính R, chỉ a) Tính đúng đắn của thủ tục kiểm tra chữ ký cá nhân<br /> khi nào có sự xác nhận của tất cả các thành viên thì R Tính đúng đắn của thủ tục kiểm tra chữ ký cá nhân<br /> mới được sử dụng để tính thành phần thứ nhất E của là sự phù hợp giữa phương pháp hình thành chữ ký cá<br /> chữ ký tập thể.. nhân với phương pháp kiểm tra tính hợp lệ của chữ ký<br /> + Có thể sử dụng cặp ( R, S ) làm chữ ký của cá nhân mà lược đồ đã đề xuất. Điều cần chứng minh<br /> ở đây là:<br /> nhóm lên M thay cho cặp ( E , S ) . Tuy nhiên cần lưu ý<br /> Với:<br /> đến độ dài của chữ ký trong 2 trường hợp như sau: Giả n<br /> sử chọn |p| = 1024 bit và |q| = 160 bit, khi đó nếu chọn R ' = ∏ ri' mod p<br /> i =1<br /> cặp ( R, S ) là chữ ký thì độ dài của chữ ký sẽ là: |p| +<br /> |p| = 1024 bit + 1024 bit = 2048 bit. Còn nếu chọn cặp trong đó: ri = s . y mod p , i = 1, 2, ..., n.<br /> ' si<br /> i<br /> E<br /> <br /> <br /> ( E , S ) làm chữ ký thì độ dài của chữ ký trong trương Nếu: R ' = R thì chữ ký cá nhân của tất cả các<br /> hợp này là: |p| + |q| = 1024 bit + 160 bit = 1184 bit. Rõ thành viên trong nhóm là hợp lệ. Nói cách khác là<br /> ràng việc chọn cặp ( E , S ) làm chữ ký đã giúp cho độ không có bất kỳ sự giả mạo nào trong các chữ ký cá<br /> nhân của các thành viên trong nhóm.<br /> dài của chữ ký được rút ngắn đáng kể.<br /> Chứng minh:<br /> + Tương tự như lược đồ LD 1.01, lược đồ được đề<br /> Thật vậy, theo định nghĩa:<br /> xuất ở đây có 3 phương án sử dụng khóa như sau:<br /> n<br /> - Sử dụng một khóa duy nhất: khi chọn k i = xi , i = R = ∏ ri mod p<br /> i =1<br /> 1, 2,...,n.<br /> và:<br /> - Sử dụng 2 khóa với giá trị được chọn khác nhau,<br /> nhưng đều được giữ cố định.<br /> <br /> <br /> - 52 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> n bảo đảm và: R ' ' = R .<br /> R ' = ∏ ri' mod p Xét thành phần S của chữ ký cần thẩm tra, theo<br /> i =1<br /> định nghĩa S sẽ có dạng:<br /> Vì vậy, nếu R ' = R thì: ri ' = ri với: i = 1,2,...n. n<br /> <br /> Giả sử thành phần thứ 2 của chữ ký cá nhân cần S = ∑ s i mod q<br /> i =1<br /> thẩm tra là: si = h( k i ' || M ' ) + xi '.E mod q n<br /> = ∑ h(k i ' || M ) + xi '.E mod q<br /> Nên: i =1<br /> n n<br /> ri = g . y mod p<br /> ' si<br /> i<br /> E<br /> = ∑ h(k i ' || M ) mod q + ∑ xi '.E mod q<br /> i =1 i =1<br /> = g h ( ki '||M ') + xi '.E mod q .g − xi .E mod p<br /> Nên:<br /> = g h ( ki '||M ') .g xi '.E .g − xi . E mod p<br /> Nếu: (ri ' = ri ) với: i = 1,2,...n. thì: R ' ' = g S .Y E mod p<br /> n n n<br /> <br /> g h ( ki '||M ') .g xi '.E .g − xi . E mod p ∑ h ( ki '|| M ) mod q + ∑ xi '.E mod q − ∑ xi mod q<br /> (1) = g i =1 i =1<br /> .( g i =1<br /> ) E mod p<br /> =g h ( k i || M )<br /> mod p n n n<br /> <br /> ∑ h ( xi '|| M ) mod q ∑ xi '.E mod q − ∑ xi . E mod q<br /> Từ (1) suy ra: = g i =1 .g i =1 .g i =1<br /> mod p<br /> xi ' = xi , k i ' = k i và M’ = M.<br /> Như vậy ( ri , s i ) thực sự là chữ ký cá nhân của Mặt khác, theo định nghĩa ta có:<br /> n<br /> <br /> thành viên thứ i, nói cách khác chữ ký này là hợp lệ. n ∑ h ( xi || M ) mod q<br /> b) Tính đúng đắn của thủ tục kiểm tra chữ ký tập thể R = ∐ ri mod p = g i=1 mod p<br /> i =1<br /> Tính đúng đắn của thủ tục kiểm tra chữ ký tập thể<br /> Vì vậy, nếu R ' ' = R thì:<br /> là sự phù hợp giữa phương pháp hình thành chữ ký tập n n n<br /> <br /> thể với phương pháp kiểm tra tính hợp lệ của chữ ký ∑ h ( ki '|| M ) mod q ∑ xi '.E mod q − ∑ xi . E mod q<br /> g i=1 .g i=1 .g i=1 mod p<br /> tập thể và tính toàn ven của văn bản được ký mà lược<br /> n<br /> đồ đã đề xuất. Điều cần chứng minh ở đây là: ∑ h ( ki || M ) mod q<br /> Với: = g i=1 mod q<br /> R' ' = g S .Y E mod p Từ đây suy ra:<br /> và: xi ' = xi và k i ' = k i , với: i = 1,2,....n.<br /> E ' = h( R ' ' || M ) mod q Như vậy (E,S) hợp lệ, đây là điều cần phải chứng<br /> Nếu: E ' = E thì chữ ký là hợp lệ và tính toàn vẹn minh.<br /> của văn bản cần thẩm tra được bảo đảm. 2.3. Mức độ an toàn của lược đồ mới xây dựng<br /> Chứng minh: Mức độ an toàn của các lược đồ chữ ký số được<br /> Theo định nghĩa ta có: đánh giá bằng khả năng chống lại các kiểu tấn công<br /> E = h( R || M ) mod q khác nhau:<br /> và: - Tấn công bằng cách tính khóa mật.<br /> E ' = h( R ' ' || M ) mod q - Tấn công theo kiểu giả mạo chữ ký.<br /> Ở kiểu tấn công thứ nhất, kẻ tấn công phải giải bài<br /> Nếu E ' = E thì suy ra:<br /> toán logarith rời rạc mà khả năng thành công là rất<br /> h( R ' ' || M ) mod q = h( R || M ) mod q (2)<br /> thấp nếu các tham số (p, q) được lựa chọn thích hợp.<br /> Từ (2) suy ra văn bản cần thẩm tra cũng chính là<br /> Ở kiểu tấn công thứ 2, tồn tại một số phương pháp giả<br /> văn bản được ký hay tính toàn vẹn của văn bản được<br /> mạo như sau:<br /> <br /> - 53 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> Phương pháp thứ nhất: Như vậy là chữ ký không hợp lệ và việc giả mạo<br /> Xét trường hợp kẻ mạo danh muốn giả mạo chữ đã bị thủ tục kiểm tra phát hiện. Tuy nhiên, cũng cần<br /> ký của thành viên thứ m trong nhóm, Do không biết phải thấy rằng việc giả mạo như trên chỉ thực hiện<br /> ( x m , k m ) kẻ mạo danh sẽ phải thực hiện như sau: được khi kẻ mạo danh là đại diện nhóm. Trong trường<br /> hợp kẻ mạo danh không phải là đại diện nhóm thì<br /> 1- Chọn k m* ∈ [1, q − 1] thay cho k m của thành<br /> việc giả mạo sẽ bị phát hiện bởi thủ tục kiểm tra tính<br /> viên thứ m và tính: hợp lệ của chữ ký cá nhân như sau:<br /> rm* = g h ( k m || M ) mod p ;<br /> *<br /> <br /> rm' = y mE .g sm mod p<br /> 2- Khi đó thành phần R sẽ là : = ( g − xm ) E .g h ( k m || M ) + xm . E mod q mod p<br /> * *<br /> <br /> <br /> <br /> R = r1 .r2 ... rm* ... rn mod p<br /> = g − xm . E .g h ( k m || M ) .g xm .E mod p<br /> * *<br /> <br /> <br /> và E sẽ là: E = h( R || M ) mod q<br /> = r j* .g − xm . E .g xm .E mod p ≠ rm*<br /> *<br /> <br /> <br /> 3- Kẻ mạo danh giả thành phần thứ 2 trong chữ ký<br /> n<br /> R ' = ∏ ri' mod p ≠ R<br /> cá nhân của thành viên thứ m như sau:<br /> Do đó:<br /> s = h(k || M ) + x .E mod q<br /> *<br /> m<br /> *<br /> m<br /> *<br /> m i =1<br /> <br /> Việc giả mạo đã bị phát hiện do không thỏa mãn<br /> Ở đây x m* là giá trị giả mạo.<br /> điều kiện của thủ tục kiểm tra chữ ký cá nhân.<br /> 4- Thành phần S của chữ ký tập thể khi đó sẽ là: Phương pháp thứ hai:<br /> S = s1 + s 2 + ... + s m* + ... + s n mod q Giả sử kẻ mạo danh là thành viên thứ nhất muốn<br /> Cặp ( E , S ) là chữ ký tập thể lên văn bản M, mà giả mạo chữ ký của thành viên thứ m trong nhóm. Kẻ<br /> mạo danh sẽ thực hiện các bước sau:<br /> trong đó có chứa chữ ký giả mạo (rm* , s m* ) .<br /> 1- Tính khóa công khai cá nhân:<br /> Khi thẩm tra chữ ký, thủ tục kiểm tra sẽ phát hiện<br /> y1 = y m−1 mod p<br /> sự giả mạo này như sau:<br /> 2- Tính thành phần thứ nhất của chữ ký cá nhân:<br /> Theo định nghĩa, ta có:<br /> n r1 = rm−1 mod p<br /> S = ∑ si mod q = h(k1 || M ) + h(k 2 || M ) + ...<br /> i =1<br /> 3- Tính thành phần thứ 2 của chữ ký cá nhân:<br /> + h(k n || M ) + ( x1 + x 2 + ... + x n ).E mod q s1 = − s m mod q<br /> n n<br /> = ∑ h(k i || M ) + ∑ ( x1 + x2 + ... + x n ).E mod q Do đó:<br /> i =1 i =1 Y = y1 . y 2 ... y m ... y n mod p<br /> Nên: = y 2 ... y m −1 . y m +1 ... y n mod p<br /> R' ' = g .Y mod p =<br /> S E<br /> R = r1 .r2 ...rm ...rn mod p<br /> h ( k1 || M ) + h ( k 2 || M ) +...+ h ( k m* || M ) +...+ h ( k n || M ) + ( x1 + x2 +...+ xm* +...+ xn ). E<br /> g . = r2 ...rm −1 .rm +1 ...rn mod p<br /> ( − x1 − x2 −...− xm −...− xn ). E<br /> g mod p = S = s1 + s 2 + ... + s m + ... + s n mod p<br /> g h ( k1 || M ) + h ( k 2 || M ) +...+ h ( k m* || M ) +...+ h ( k n || M )<br /> . = s 2 + ... + s m −1 + s m+1 + ... + s n mod p<br /> g ( x1 + x2 +...+ xm +...+ xn ).E .g −( x1 + x2 +...+ xm +...+ xn ).E mod p =<br /> *<br /> Chữ ký (E,S) được tạo ra hoàn toàn phù hợp với<br /> thủ tục kiểm tra. Thật vậy, khi tính R ' ' bằng công<br /> = R.g xm .g − xm mod p ≠ R<br /> *<br /> <br /> <br /> thức: R ' ' = g S .Y E mod p , ta sẽ có:<br /> Do đó: E ' = h( R ' ' || M ) mod q ≠ h( R || M )<br /> hay: E' ≠ E<br /> <br /> - 54 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> R' ' = g ( s2 + s3 +...+ sm −1 + sm +1 +...+ sn ) . chữ ký khi họ đã đồng ý ký vào văn bản và gửi chữ ký<br /> cá nhân của mình cho nhóm. Nhưng giả mạo chữ ký<br /> ( y 2 . y 3 ... y m−1 . y m+1 ... y n ) E mod p<br /> của thành viên đã ký vào văn bản là một việc làm vô<br /> = g s2 .g s3 ...g sm −1 .g sm +1 ...g sn . nghĩa và không đúng với bản chất của sự giả mạo.<br /> ( g − x2 .g − x3 ...g − xm −1 .g − xm +1 ...g − xn ) E mod p Hơn nữa, không thể lấy chữ ký cá nhân của một thành<br /> viên lên văn bản này để giả mạo chữ ký của họ với các<br /> = g h ( k2 || M ) + x x .E .g h ( k3 || M ) + x3 . E ...g h ( km −1 || M )+ xm −1 .E .<br /> văn bản khác được, vì thành phần s của chữ ký cá<br /> g h ( k m +1|| M ) + xm +1 . E ...g h ( k n || M )+ xn .E .g − x2 . E .g − x3 . E ... nhân phụ thuộc vào giá trị băm (bản tóm lược) của văn<br /> g − xm −1 . E .g − xm +1 . E mod p = g h ( k 2 || M ) .g h ( k3 || M ) ... bản được ký, khi nội dung văn bản bị thay đổi thì chữ<br /> g h ( k m −1 || M ) .g h ( k m +1|| M ) ...g h ( k n || M ) mod p ký cá nhân của các thành viên mà chúng muốn mạo<br /> danh không còn phù hợp để tạo chữ ký cho văn bản đã<br /> = r2 .r3 ...rm−1 .rm +1 ...rn mod p = R<br /> bị sửa đổi nữa, điều đó đồng nghĩa với việc kẻ giả mạo<br /> Nếu văn bản không bị sửa đổi, ta có: không có được chữ ký cá nhân của những thành viên<br /> E ' = h( R ' ' || M ' ) mod q mà chúng muốn mạo danh, do đó không thể thực hiện<br /> = h( R || M ) mod q = E việc giả mạo theo phương pháp này được.<br /> Chữ ký đã được xác nhận là hợp lệ. Bằng cách đó Phương pháp thứ 3:<br /> thành viên thứ nhất đã mạo danh được thành viên thứ Ta cũng xét trường hợp kẻ mạo danh là thành viên<br /> m, và nói chung là có thể mạo danh được bất kỳ thành thứ nhất muốn giả mạo chữ ký của thành viên thứ m<br /> viên nào trong nhóm ký. Hơn nữa, phương pháp giả trong nhóm. Kẻ mạo danh sẽ thực hiện các bước sau:<br /> mạo này có thể áp dụng cho bất kỳ lược đồ chữ ký tập 1- Tính thành phần thứ nhất của chữ ký cá nhân:<br /> thể nào. r1 = g h ( k1 || M ) .rm mod p<br /> Về mặt toán học, phương pháp giả mạo này là<br /> 2- Tính thành phần thứ 2 của chữ ký cá nhân:<br /> hoàn toàn đúng. Tuy nhiên, ta hãy xét tính thực tiễn<br /> s1 = h(k1 || M ) + x1 .E + s m mod q<br /> của nó, ở đây có 2 vấn đề:<br /> Thứ nhất, việc tính khóa công khai cá nhân của kẻ Do đó:<br /> mạo danh: y1 = y m−1 mod p là không thể thực hiện R = r1 .r2 ...rm −1 .rm +1 ...rn mod p<br /> được nếu có một cơ chế kiểm tra chặt chẽ khi hình = g h ( k1|| M ) .g h ( k 2 || M ) ...g h ( k m −1|| M ) .<br /> thành khóa công khai tập thể Y. Giả sử việc tính khóa .g h ( k m || M ) .g h ( k m +1 || M ) ....g h ( k n || M ) mod p<br /> công khai cá nhân của kẻ mạo danh ( y1 ) như trên n<br /> = ∏ ri mod p<br /> không bị phát hiện thì kẻ mạo danh cũng chỉ có thể i =1<br /> thực hiện giả mạo được với thành viên thứ m, mà Và:<br /> không thể giả mạo với các thành viên khác được, vì<br /> S = s1 + s 2 + ... + s m −1 + s m +1 ... + s n mod p<br /> khóa công khai tập thể Y sau khi đã được công bố thì<br /> = h(k1 || M ) + x1 .E + h( k 2 || M ) + x 2 .E + ...<br /> không thể tùy ý thay đổi theo từng văn bản ký.<br /> Thứ hai, ta thấy rằng điều kiện tiên quyết để + h((k m −1 || M ) + x m −1 .E + h(k m || M ) + x m .E +<br /> phương pháp này thực hiện được là kẻ mạo danh phải + h( k m +1 || M ) + x m +1 .E + ...<br /> biết được chữ ký cá nhân của thành viên mà chúng + h(k n || M ) + x n .E mod q<br /> muốn giả mạo chữ ký. Chính điều đó đã hạn chế khả n n<br /> <br /> năng ứng dụng của phương pháp này trong thực tiễn. = ∑ h(k i || M ) + x i .E mod q = ∑ s i mod q<br /> i =1 i =1<br /> Vì rằng, kẻ mạo danh chỉ có thể biết được chữ ký cá<br /> Điều đó cho thấy rằng, nhóm ký vẫn tạo ra được<br /> nhân của những thành viên mà chúng muốn giả mạo<br /> chữ ký hợp lệ với đầy đủ n thành viên mà không cần<br /> <br /> <br /> - 55 -<br /> Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012<br /> <br /> sự có mặt của thành viên thứ m. Tuy nhiên, phương nhóm khi chúng biết được chữ ký cá nhân mà chúng<br /> pháp giả mạo này đã thực hiện không đúng với yêu đang muốn giả mạo. Trường hợp dù có được chữ ký<br /> cầu của lược đồ đưa ra. Xem xét lại công thức tính R cá nhân ở những lần ký trước đó của thành viên mà<br /> n chúng đang muốn giả mạo thì kẻ mạo danh cũng<br /> và S của lược đồ: R = ∏ ri mod p không thể áp dụng phương pháp giả mạo này được. Ta<br /> i =1<br /> n<br /> xét một trường hợp cụ thể, mà ở đó kẻ mạo danh có<br /> và: S = ∑ s i mod q thể là n-1 thành viên muốn giả mạo chữ ký của thành<br /> i =1 viên thứ n trong nhóm. Kẻ mạo danh được chọn là<br /> Các công thức trên đã chỉ ra một cách rõ ràng một thành viên, chẳng hạn thành viên thứ 1, kẻ mạo<br /> rằng, chữ ký tập thể phải được tạo ra từ n chữ ký cá danh chọn cho mình (r1,s1) của lần ký mới này như<br /> nhân của các thành vên trong nhóm và nó chỉ được tạo sau:<br /> ra khi có đầy đủ số lượng chữ ký cá nhân của các 1- Tính thành phần thứ nhất của chữ ký cá nhân:<br /> thành viên. Ở mức thực thi bằng chương trình, việc<br /> rn ' = (rn ) r1 mod p<br /> tính R và S có thể được thực hiện bằng các vòng lặp<br /> 2- Tính thành phần thứ 2 của chữ ký cá nhân:<br /> như sau:<br /> R := 1; s n ' = s n .r1 mod q<br /> For i := 1 to n do Với lưu ý: ở đây người giả mạo chỉ cần lấy rn , sn<br /> R := R * ri ; cũ của lần 1 lần ký trước đó mà thành viên m đã ký<br /> Hay: (có mang thông tin về xn ), chứ không phải của lần ký<br /> S:=0; này.<br /> i := 1; Nhóm n-1 người thay cặp (rn’ , sn’) mới qua mặt<br /> While (i