Xây dựng một lược đồ chữ ký số tập thể dựa hệ mật ID-Based - Đặng Minh Tuấn

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