Xây dựng một lược đồ chữ ký số tập thể dựa hệ mật ID-based

Nghiên cứu khoa học công nghệ<br /> <br /> XÂY DỰNG MỘT LƯỢC ĐỒ CHỮ KÝ SỐ TẬP THỂ<br /> DỰA HỆ MẬT ID-BASED<br /> Đặng Minh Tuấn1*, Lê Xuân Đức2, Nguyễn Xuân Tùng3, Nguyễn Đức Toàn4<br /> Tóm tắt: Hệ mật ID-Based là hệ mật dùng khóa công khai chính là thông tin<br /> nhận dạng của thành viên, nhờ đó, không cần phải quản lý khóa công khai và làm<br /> giảm thiểu dung lượng truyển tải trên đường truyền phù hợp với mô hình có số<br /> lượng lớn người sử dụng. Bài báo đề xuất một lược đồ ký số tập thể dựa trên ID-<br /> Based sử dụng tài nguyên ít hơn một số lược đồ đã đề xuất trước đó.<br /> Từ khóa: Chữ ký số, Chữ ký số tập thể, Hệ mật ID-Based, Cặp song tuyến tính.<br /> 1. ĐẶT VẤN ĐỀ<br /> Chữ ký số có một vai trò quan trong lĩnh vực chính phủ điện tử và thương mại điện tử<br /> vì nó đảm bảo được yếu tố pháp lý cho các giao dịch được thực hiện trên mạng. Chữ ký số<br /> là một chuỗi bit dữ liệu được rút ra từ văn cần ký có vai trò tương tự như chữ ký trên giấy<br /> thông thường. Nghĩa là nó phải chứng thực được người ký, văn bản được ký và thực hiện<br /> cả tính chống chối bỏ của người ký. Chữ ký số được sinh ra bằng thuật toán và lược đồ<br /> thuật toán sử dụng các hệ mật mã khóa bất đối xứng hay còn gọi là hệ mật mã khóa công<br /> khai-khóa bí mật.<br /> Chữ ký số tập thể cũng tương tự như chữ ký số đơn nhưng cho phép một tập thể người<br /> ký cùng tham gia vào quá trình ký văn bản. Chữ ký số tập thể theo [1] cần phải có một số<br /> thuộc tính sau:<br />  Chữ ký số tập thể chung của cả nhóm sẽ có kích thước không tăng theo số lượng<br /> thành viên trong nhóm (có kích thước tương đương của từng thành viên).<br />  Chữ ký số tập thể có thể xác thực bằng khóa công cộng chung của cả nhóm mà<br /> không cần phải biết khóa công công riêng của từng thành viên.<br />  Không thể tạo được khóa công cộng chung của cả nhóm nếu không có sự cộng tác<br /> của từng thành viên trong nhóm.<br /> Lược đồ chữ ký số tập thể đầu tiên được phát triển bởi Itakura và Nakamura [2], và sau<br /> đó, một loạt các công trình khác cũng được công bố trong lĩnh vực này [3].<br /> Hệ mật ID-Based lần đầu tiên được công bố bởi Shamir vào năm 1984 [4], ưu điểm<br /> chính của hệ mật ID-Based là không cần phải xác thực khóa công khai, khóa này được dẫn<br /> xuất từ địa chỉ ID, địa chỉ email hay số chứng minh thư của người sử dụng. Đã có nhiều<br /> lược đồ chữ ký số tập thể hoặc tương đương được đề xuất dựa trên hệ mật ID-Based sử<br /> dụng cặp song tuyến tính nhưng một số trong đó có lỗi thiết kế [6], [7] hoặc hiệu năng<br /> chưa cao [9], [10]. Bài báo này đề xuất một lược đồ mới đơn giản và có những cải thiện<br /> nhất định về hiệu năng.<br /> 2. CƠ SỞ LÝ THUYẾT<br /> 2.1. Cặp song tuyến tính<br /> Nếu P là phần tử sinh của 1 với 1 là nhóm cộng có bậc là số nguyên tố q .  2 là<br /> nhóm nhân có bậc bằng bậc của nhóm 1 . Cặp song tuyết tính (Bilinear Pairing) là ánh<br /> xạ: eˆ : 1  1   2 có các thuộc tính sau [5]:<br /> 1. Ánh xạ eˆ là song tuyến tính: Với Q, W , Z  1 , chúng ta có:<br /> eˆ(Q, W  Z )  eˆ(Q, W )  eˆ(Q, Z ) và eˆ(Q  W , Z )  eˆ(Q, Z )  eˆ(W , Z ) (1)<br /> và do đó với mọi a, b  Z q thì:<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 121<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> eˆ(aQ, bW )  eˆ(Q,W ) ab  eˆ(abQ, W )  eˆ(Q, abW )  eˆ(bQ, W ) a (2)<br /> 2. Ánh xạ eˆ không bị suy biến: eˆ( P, P )  1 2 trong đó 1 2 là phần tử đơn vị của  2 .<br /> 3. Ánh xạ eˆ được tính một cách dễ dàng.<br /> Thông thường, 1 là nhóm con của nhóm các điểm nằm trên đường cong Elliptic trong<br /> trường hữu hạn E (t ) với t là số nguyên tố đủ lớn.  2 là nhóm con của nhóm nhân của<br /> trường hữu hạn liên quan.<br /> 2.2. Cặp Tate<br /> Cặp song tuyến tính được sử dụng phổ biến nhất là cặp Weil và Tate [5], cả hai cặp này<br /> đều có 1 là nhóm con của nhóm các điểm nằm trên đường cong Elliptic.<br /> Định nghĩa 2.1 (Cặp Tate): Với đường cong Elliptic trên trường hữu hạn E (t ) , cho<br /> r là số nguyên sao cho r | (t  1) và giả thuyết rằng r | (| E (t ) |) có nghĩa là trong E (t )<br /> tồn tại ít nhất 1 (và do đó r ) điểm r -xoắn. Xét P  E (t )[r ] . Coi DP là số chia có bậc<br /> 0 sao cho sum( DP )  P . rD p sau đó sẽ là số chia bậc 0 và tổng  do đó tồn tại hàm<br /> chia f P sao cho div( f P )  rDP . Với Q  E (t ) / rE ( t ) , chúng ta cũng định nghĩa số<br /> chia DQ có bậc 0 và tổng Q , tiếp theo, chúng ta cũng giải thiết rằng DP và DQ không có<br /> điểm chung, với các điều kiện trên chúng ta có cặp Tate sẽ được tính như sau:<br /> eˆr ( P, Q)  f P ( DQ )(mod (t ) r )<br /> 3. ĐỀ XUẤT CHỮ KÝ SỐ TẬP THỂ DỰA TRÊN HỆ MẬT ID-BASED<br /> 3.1. Đề xuất lược đồ chữ ký số tập thể dựa trên hệ mật định danh<br /> 3.1.1. Cài đặt<br /> Coi G1 là nhóm cộng cyclic có bậc là số nguyên tố q và phần tử sinh là P . G2 là<br /> nhóm nhân cyclic có cùng bậc q . eˆ là một ánh xạ song tuyến tính:<br /> eˆ : G1  G1  G2<br /> H1 , H 2 là các hàm băm được sử dụng cho mục đích bảo mật và được định nghĩa như sau:<br /> H1 :{0,1}*  G1 , H 2 :{0,1}*  *q .<br /> 1. Với tham số bảo mật k chọn ngẫu nhiên s   q .<br /> *<br /> <br /> <br /> 2. Tính khóa công khai của hệ thống: Ppub  sP  G1<br /> 3. Công bố tham số của hệ thống là: Params  ( k , G1 , G2 , q, eˆ, H1 , H 2 , P, Ppub )<br /> 3.1.2. Tách khóa<br /> Có n người ký tập thể IDBI với 1  i  n .<br /> 1. Khóa công khai của các thành viên: QIDB  H1 ( IDBi )  G1 .<br /> i<br /> <br /> 2. Người quản trị hệ thống sẽ tính khóa bí mật cho thành viên:<br /> S IDB  sQIDB 1  i  n .<br /> i i<br /> <br /> Người quản trị sẽ thông qua kênh bí mật gửi các khóa bí mật này cho các thành<br /> viên.<br /> <br /> <br /> <br /> 122 Đ. M. Tuấn, …, N. Đ. Toàn, “Xây dựng một lược đồ chữ ký số tập thể… hệ mật ID-Based.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 3.1.3. Hình thành chữ ký tập thể<br /> Quy ước m là văn bản cần ký.<br /> 1. Tính h  H 2 (m) .<br /> *<br /> 2. Mỗi thành viên IDBi sẽ chọn ngẫu nhiên số xi  q .<br /> 3. Tính U pi  xi P , gửi giá trị U pi đến ( n  1) các thành viên còn lại.<br /> 4. Các thành viên tính và gửi  pi  hS IDi  xi Ppub , cho người phụ trách, người này<br /> n<br /> tổng hợp và tính: U p  U<br /> i 1<br /> pi .<br /> <br /> 5. Và sau đó kiểm tra điều kiện: eˆ( P,  pi )  eˆ( Ppub , hQIDi  U pi )<br /> Nếu không thỏa mãn thì thực hiện lại từ bước 2.<br /> 6. Người phụ trách sau khi có các chữ ký thành phần sẽ tạo khóa công khai tập thể<br /> n<br /> Q pk   QIDB .<br /> i<br /> i 1<br /> n<br /> 7. Tính  p  <br /> i 1<br /> pi , sau đó chữ ký số ủy nhiệm sẽ là ( p , U p ) .<br /> <br /> 3.1.4. Xác thực chữ ký tập thể<br /> Người xác thực chữ ký ủy nhiệm sau khi nhận văn bản m ' và chữ ký ( p , U p ) sẽ<br /> tiến hành các bước sau:<br /> 1. Tính giá trị: h2  H 2 ( m) .<br /> 2. Kiểm tra điều kiện hợp lệ của chữ ký nếu thảo mãn thì chấp nhận tính hợp lệ:<br /> eˆ( P,  p )  eˆ( Ppub , h2'Q pk  U p )<br /> 3.2. Chứng minh tính đúng đắn của lược đồ chữ ký số tập thể dựa trên hệ mật định danh<br /> Định lý 3.1. [Lược đồ chữ ký số tập thể] Nếu m  m thì: eˆ( P,  p )  eˆ( Ppub , h2Q pk  U p ) .<br /> Chứng minh bằng lý thuyết: Chúng ta cần phải chứng minh rằng:<br /> eˆ( P,  p )  eˆ( Ppub , h2Q pk  U p )<br /> n<br /> eˆ( P,   pi )  eˆ( Ppub , h2Q pk  U p )<br /> i 1<br /> n<br />  <br /> eˆ  P,   h2 S pki  xi Ppub    eˆ( Ppub , h2Q pk  U p )<br />  i 1 <br /> n<br />  <br /> eˆ  P,   h2 S pki  xi sP    eˆ( Ppub , h2Q pk  U p )<br />  i 1 <br /> n<br />  <br /> eˆ  Ppub ,   h2Q pki  xi P    eˆ( Ppub , h2Q pk  U p )<br />  i 1 <br />   n  <br /> eˆ  Ppub , h2   Q pki   U p   eˆ( Ppub , h2Q pk  U p )<br />   i 1  <br /> eˆ  Ppub , h2Q pk  U p   eˆ( Ppub , h2Q pk  U p )<br /> Biểu thức cuối cùng đúng khi h2  h2 .<br /> Chứng minh qua thực nghiệm: Nhóm tác giả đã xây dựng phần mềm bằng ngôn ngữ<br /> python 3.2, có khả năng chạy được trên các hệ điều hành Windows, Linux, Mac OS. Khóa<br /> công khai của thành viên chính là địa chỉ email làm định danh. Hàm H1 được xây dựng<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 123<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> bằng cách tính theo công thức: H1 ( x)  SHA256( x)  P , với P là điểm cơ sở. Hàm H 2<br /> được định nghĩa là: H 2 ( x)  SHA256( x) . Phương trình sử dụng cho đường cong elliptic<br /> có dạng E : y 2  x 3  x  1 được định nghĩa trên trường Galois có dạng GF (3m ) , bậc của<br /> G1 cao nhất là 911-bit. Mỗi phép toán lấy cặp song tuyến tính dạng Tale sẽ thực hiện hết<br /> 3.26 giây với máy tính Intel Core2 L7500 CPU (1.60GHz) cho bậc G1 là 151-bit. Chạy<br /> thử nghiệm với kịch bản: a) kiểm tra tính đúng đắn: kiểm tra chữ ký số và bản text ký<br /> nguyên bản là tiếng Việt Unicode, kết quả phần mềm xác thực đúng và b) thay đổi 1 ký tự<br /> trong định danh email hoặc thay đổi 1 bit trong chữ ký hoặc bản gốc thì phần mềm đều chỉ<br /> ra có sự khác biệt và không chấp nhận chữ ký.<br /> 3.3. Phân tích độ an toàn lược đồ chữ ký số tập thể dựa trên hệ mật định danh<br /> Để giả mạo chữ ký số ( p , U p ) , người tấn công phải giả mạo được các giá trị  p , U p .<br /> Để tính được  p cần phải tìm đươc S IDi và xi (là khóa bí mật của thành viên). Muốn tìm<br /> được các giá trị này người tấn công bắt buộc phải giải bài toàn logarithm rời rạc (DLP) và<br /> đây là bài toán khó chưa có lời giải trong thời gian đa thức.<br /> Vì các khóa công khai thành phần U pi  xi P của thành viên U i sẽ được gửi cho người<br /> ủy nhiệm C, do đó có nhiều khả năng tin tặc sẽ thu được cặp giá trị này trên đường truyền.<br /> Tin tặc sẽ cố gằng dùng giá trị này để tìm ra khóa bí mật xi muốn vậy phải giải bài toán<br /> DLP trên đường cong elliptic, biết điểm P và tích vô hướng của điểm đó với giá trị x tìm<br /> x , đây là bài toán khó, chưa có thuật toán giải trong thời gian đa thức.<br /> 3.4. Phân tích so sánh với một số lược đồ ký số tập thể ID-Based khác<br /> - Lược đồ A. Boldyreva [6] không có thành phần ngẫu nhiên, nên mỗi lần ký cùng<br /> một văn bản sẽ cho ra một chữ ký giống nhau và đây là điểm yếu để hacker có thể<br /> tấn công gửi lại re-play.<br /> - Lược đồ Li-Chen [7], có lỗi trong thiết kế chữ ký số tập thể tại trang 441 trong công<br /> thức d ap  H1 (mw || U )d d ID  xPpub với U  xP là một điểm trên đường cong<br /> A<br /> <br /> elliptic thì không thể nối với giá trị mw là một số nguyên, ngoài ra, H1 có tham số<br /> là số nguyên và không phải là điểm trên đường cong.<br /> Bảng 1. So sánh số phép tính cho các khâu ký và xác thực.<br /> Lược đồ Tính cặp pairing Lũy thừa Nhân điểm elliptic<br /> Le- Bonnecaze [8] 2 2n 0<br /> Sahu- Padhye [9] 2n+2 n+3 2n<br /> Sahu- Padhye [10] 2n+1 1 2n<br /> Mới đề xuất 2 0 2n<br /> Qua bảng 1 có thể thấy lược đồ mới đề xuất sử dụng ít phép toán tốn tài nguyên hơn<br /> các lược đồ Sahu- Padhye [9], 10]và có thể coi gần tương đưng với lược đồ Le-<br /> Bonnecaze [8].<br /> 4. KẾT LUẬN<br /> Trong bài báo này, tác giả đã phát triển một lược đồ chữ ký số tập thể mới dựa trên<br /> song tuyến tính dùng ánh xạ cặp Tate trên đường cong Elliptic. Chữ ký số tập thể đa thành<br /> phần có độ khái quát cao, ở đó, mỗi thành viên tham gia ký có thể ký và đảm nhiệm trách<br /> nhiệm những thành phần bất kỳ trong văn bản. Lược đồ chữ ký số mới có độ mềm dẻo và<br /> linh hoạt cao, có thể áp dụng trong nhiều lớp bài toán chữ ký số tập thể trong thực tiễn. Có<br /> <br /> <br /> 124 Đ. M. Tuấn, …, N. Đ. Toàn, “Xây dựng một lược đồ chữ ký số tập thể… hệ mật ID-Based.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> thể mở rộng sang các bài toán khác như chữ ký số có phân biệt tách nhiệm, chữ ký số tập<br /> thể ủy nhiệm và tập thể ủy nhiệm mù…<br /> TÀI LIỆU THAM KHẢO<br /> [1]. L. Harn, “Digital multisignature with distinguished signing authorities,” Electron.<br /> Lett., vol. 35, no. 4, pp. 294–295, 1999.<br /> [2]. K. Nakamura and K. Itakura, “A public-key cryptosystem suitable for digital<br /> multisignatures,” NEC Research and Development, pp. 1–8, 1983.<br /> [3]. M. C. Gorantla, R. Gangishetti, and A. Saxena, “A Survey on ID-Based<br /> Cryptographic Primitives.,” IACR Cryptology ePrint …, no. 1, 2005.<br /> [4]. A. Shamir, “Identity-based Cryptosystems and Signatures Schemes,” Proc. of<br /> Crpto’84, pp. 48–53, 1984.<br /> [5]. R. Dutta, R. Barua, P. Sarkar, and B. T. Road, “Pairing-Based Cryptographic<br /> Protocols : A Survey Introduction Preliminaries Key Agreement Schemes<br /> Conclusion,” IACR Eprint archive, 2004.<br /> [6]. A. Boldyreva, “Efficient threshold signature, multisignature and blind signature<br /> schemes based on the Gap-Diffie-Hellman-group signature scheme,” Public-Key<br /> Cryptography – PKC 2003, pp. 31–46, 2002.<br /> [7]. X. Li and K. Chen, “ID-based multi-proxy signature, proxy multi-signature and<br /> multi-proxy multi-signature schemes from bilinear pairings,” Applied Mathematics<br /> and Computation, vol. 169, no. 1, pp. 437–450, 2005.<br /> [8]. D. P. Le, A. Bonnecaze, and A. Gabillon, “Multisignatures as Secure as the Diffie-<br /> Hellman Problem in the Plain Public-Key Model,” SCN ’08: Proceedings of the 6th<br /> international conference on Security and Cryptography for Networks, vol. 15, no. 1,<br /> pp. 1–18, 2008.<br /> [9]. R. A. Sahu and S. Padhye, “An ID-Based Multi-Proxy Multi-Signature Scheme,” Int’l<br /> Conf. on Computer & Communication Technology, pp. 60–63, 2010.<br /> [10].R. A. Sahu and S. Padhye, “Identity-based multi-proxy multi-signature scheme<br /> provably secure in random oracle model,” European Transactions on<br /> Telecommunications, vol. 25, no. 3, pp. 294–307, 2014.<br /> ABSTRACT<br /> DESIGNING A NEW ID-BASED MULTISIGNATURE SCHEME<br /> ID-Based cryptosystem is cryptosystem that uses the identity of a member as his<br /> public-key, so there is no need to manage the public keys and it can minimize the<br /> transmission bandwidth on the net. The article proposes an ID-based multisignature<br /> scheme that uses less resources than some of the previously proposed schemes.<br /> Keywords: Signature, Multisignature, ID-Based cryptosystem, Bilinear mapping.<br /> <br /> Nhận bài ngày 26 tháng 7 năm 2017<br /> Hoàn thiện ngày 17 tháng 8 năm 2017<br /> Chấp nhận đăng ngày 20 tháng 12 năm 2017<br /> <br /> <br /> Địa chỉ: 1 Bộ Khoa học Công nghệ;<br /> 2<br /> Viện CNTT/Viện KHCNQS;<br /> 3<br /> Công ty SmattSign;<br /> 4<br /> Trường Cao đẳng Công nghiệp Thực phẩm.<br /> *<br /> Email: dangtuan@vietkey.vn.<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 125<br />