Đề xuất mô hình chữ ký số tập thể đa thành phần tổng quát và kết hợp với một số mô hình khác

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 91 ĐỀ XUẤT MÔ HÌNH CHỮ KÝ SỐ TẬP THỂ ĐA THÀNH PHẦN TỔNG QUÁT VÀ KẾT HỢP VỚI MỘT SỐ MÔ HÌNH KHÁC Đặng Minh Tuấn* Tóm tắt: Dựa trên một số công trình đã công bố về chữ ký số tập thể đa thành phần (MultiSignature MultiSection – MSMS), tác giả đưa ra định nghĩa tổng quát về mô hình này và đề xuất mô hình kết hợp giữa MSMS với hai mô hình ký số phổ biến là chữ ký số ủy nhiệm và chữ ký số mù. Với sự kết hợp này MSMS đưa ra khả năng đáp ứng đa dạng và phong phú các ứng dụng về chữ ký số trong thực tiễn. Từ khóa: Chữ ký số, Chữ ký số tập thể, Chữ ký số tập thể đa thành phần. 1. ĐẶT VẤN ĐỀ Chữ ký số tập thể là mô hình ở đó có nhiều người cùng tham gia ký một văn bản, lần đầu tiên đưa ra bởi Nakamura và Itakura [1]. Năm 1999, Harn đưa ra khái niệm chữ ký số tập thể có phân biệt trách nhiệm [2], ở đó mỗi thành viện chịu trách nhiệm ký vào một phần duy nhất của văn bản, tuy nhiên cũng như nhiều công bố sau đó như [3], [4], mô hình này chỉ cho phép một người ký duy nhất một phần của văn bản, và một phần văn bản được ký duy nhất bởi một người. Trong thực tế một phần của văn bản có thể được ký bởi nhiều người và mỗi người có thể ký nhiều phần khác nhau của văn bản, các mô hình ký trước đây không thể đáp ứng yêu cầu này và đó là lý do đề xuất mô hình ký tập thể đa thành phần cho phép giải quyết vấn đề này. Chữ ký số tập thể đa thành phần lần đầu tiên được công bố vào năm 2011 trong [5] cho hệ mật dựa trên logarithm rời rạc, sau đó là [6] cho hệ mật dựa trên đường cong elliptic tuy nhiên chưa có một định nghĩa tổng quát về chữ ký số tập thể đa thành phần (MSMS). Trong bài báo này, tác giả đưa ra một định nghĩa tổng quát cho chữ ký số MSMS, đồng thời mở rộng khả năng ứng dụng của mô hình MSMS khi kết hợp với mô hình chữ ký số ủy nhiệm và chữ ký số mù. Phần 2 là một số định nghĩa liên quan đến mô hình ký tập thể đa thành phần tổng quát. Phần 3 là đề xuất kết hợp giữa MSMS với ký ủy nhiệm dựa trên hệ mật định danh (song tuyến tính), đây là hệ mật có nhiều ưu việt khi sử dụng email hay số chứng minh thư làm khóa công khai, phần 3.2 là đề xuất mô hình kết hợp với ký mù dựa trên hệ mật đường cong elliptic là hệ mật có độ an toàn cao hơn nhiều so với hệ mật truyền thống RSA. 2. MÔ HÌNH CHỮ KÝ SỐ TẬP THỂ ĐA THÀNH PHẦN TỔNG QUÁT Định nghĩa 2.1 [Mảng phân công ký V ] Giả sử có NSIG người ký iU ; 1 iNSIG cần ký văn bản *{0,1}m . Chia m thành NSEC phần, sao cho có thể biểu diễn m dưới dạng: 1 2 3( || || || || )m m m m m  NSEC . Định nghĩa vector ký: | [1], [ ], [ ] |, [ ] {0,1}, ..., . , 1..i i i i ij j j   V V V V VNSEC NSEC Người ký iU cần phải ký jm thì [ ] 1i j V , và [ ] 0i j V nếu iU không phải ký phần jm . Cho cả tập thể người ký, định nghĩa mảng V như sau: 1 2( || || ... || || ... || ).iV V V V VNSIG Công nghệ thông tin & Cơ sở toán học cho tin học Đặng Minh Tuấn, “Đề xuất mô hình chữ ký số tập thể kết hợp với một số mô hình khác.” 92 Định nghĩa 2.2 [Giá trị băm tổng hợp eH hoặc còn ký hiệu là e ] Từng thành viên iU sẽ chịu trách nhiệm ký một số phần của văn bản m , tính giá trị hàm băm ( )i jh m ; 1 j NSEC và gửi cho người ủy nhiệm, người này sẽ tính giá trị băm cho jm như sau:   1 [ ] ( ) ; 1j i i j i e j h m j     V NSIG NSEC 1 2( || || )eH H e e e  NSEC Định nghĩa 2.3 [Chữ ký số tập thể đa thành phần - MSMS] Giả sử văn bản m được chia thành NSEC phần, có tập thể NSIG người ký. Lược đồ chữ ký số tập thể đa thành phần là tập bộ 07 thành phần (Setup , KeyGen , KeyGenPub , Sign , SignPub , Verify , VerifyPub ) có thuật toán thực hiện trong thời gia đa thức. Ba thuật toán đầu là thuật toán xác suất.  Bộ khởi tạo Setup : Đầu vào là tham số bảo mật k và R là nguồn ngẫu nhiên, đầu ra là bộ tham số: (1 ) R kparams Setup .  Sinh khóa công khai và bí mật cho các thành viên iU , 1 iNSIG . ( , ) ( ,1 , )k ii iPK SK KeyGen params . Sau khi có khóa công khai của từng thành viên, sinh khóa công khai của cả tập thể bằng thuật toán: 1{ ( , )}i i V NSIG pub iPK KeyGenPub PK  Ký văn bản: Từng thành viên iU tham gia ký văn bản theo thuật toán dưới đây: ( , , )Ri im  ViSign SK . Người tổng hợp cần phải kiểm tra chữ ký của từng thành viên bằng thuật toán sau: 1{0,1} { ( , , , )}i i im   V NSIG iVerify PK . Nếu tất cả đều hợp lệ thì tiến hành tính chữ ký của cả tập thể, nếu không thì yêu cầu thực hiện lại bước này. 1{ ( )} R pub i i   NSIGSignPub .  Xác thực văn bản nhận được 'm : {0,1} ( , , , )pubm  VpubVerifyPub PK . 3. KẾT HỢP MÔ HÌNH MSMS VỚI MỘT SỐ MÔ HÌNH KHÁC 3.1. Kết hợp chữ ký số MSMS với chữ ký số ủy nhiệm 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 3, ,H 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  , * * * 3 :{0,1} {0,1} qH    . 1. Với tham số bảo mật k chọn ngẫu nhiên *qs . Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 93 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 3ˆ( , , , , , , , , , )pubParams k G G q e H H H P P 3.1.2. Tách khóa Người ký ủy nhiệm có định danh là ID , có n người có thể ký ủy nhiệm IB ID với 1 i n  . 1. Bất kỳ ai cũng có thể tính khóa công khai của người cần ủy nhiệm: 1 1( )IDQ H ID G  và những người được ủy nhiệm: 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 người ủy nhiệm và được ủy nhiệm: ID IDS sQ 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. 3.1.3. Hình thành chữ ký của người ủy nhiệm 1. Bất kỳ ai cũng có thể tính khóa công khai của người cần ủy nhiệm: 1 1( )IDQ H ID G  và những người được ủy nhiệm: 1 1( )B iiID B Q H ID G  . 2. Tính các giá trị: sV xP , 2 ( )H H m , s ID pubW HS xP  . 3. Chữ ký của người ủy nhiệm là ( , )s sW V  . 3.1.4. Xác thực chữ ký người ủy nhiệm 1. Với văn bản 'm và chữ ký ( , )s sW V  nhận được, người xác thực tính: 2 1( ), ( )IDH H m Q H ID   . 2. Chấp nhận chữ ký khi điều kiện sau thỏa mãn: ( , ) ( , )s ID s pube W P e H Q V P  3.1.5 Sinh khóa cho người được ủy nhiệm Trong giai đoạn này người ủy nhiệm sẽ trao đổi với người được ủy nhiệm với các quyền được ủy nhiệm. Để làm việc này người ủy nhiệm sẽ tạo ra một văn bản bảo đảm w , văn bản này sẽ kèm theo một số thông tin về văn bản, về những hạn chế của văn bản sẽ ủy nhiệm, thời gian hoặc định danh của những người sẽ ủy nhiệm. 1. {Ủy nhiệm}: Người cần ủy nhiệm chọn ngẫu nhiên *qt và tính:V tP , 2 ( )h H w , 1ID pubW hS tP G   . Chuyển giá trị ( , , )W V w với các thành viên qua kênh truyền bí mật. 2. {Kiểm tra ủy nhiệm}: mỗi thành viên iB ID sẽ tính 2 ( )h H w và kiểm tra điều kiện sau (nếu không thỏa mãn thì phải yêu cầu gửi lại hoặc hủy giao thức): ˆ ˆ( , ) ( , )ID pube W P e hQ V P  . Công nghệ thông tin & Cơ sở toán học cho tin học Đặng Minh Tuấn, “Đề xuất mô hình chữ ký số tập thể kết hợp với một số mô hình khác.” 94 3. {Sinh khóa ủy nhiệm}: mỗi thành viên iB ID sẽ tính 2 ( )h H w tính khóa bí mật ủy nhiệm: i Bi pk IDS W hS  . 3.1.6. Hình thành chữ ký ủy nhiệm Trong pha này sẽ có một người phụ trách có nhiệm vụ tập hợp hết tất cả các chữ ký thành phần. 1. Mỗi thành viên iB ID sẽ chọn ngẫu nhiên số *i qx  . 2. Mỗi thành viên iU (1 i n ) chọn NSEC số nguyên *[ ]i qx j  ; 1 j NSEC như là các khóa riêng và tính khóa công khai tương ứng theo công thức: ( ) ip i i U x P V . Với định nghĩa phép toán:   1 ( [ ] [ ]) modi i i i j x j x j q    V V NSEC . Giả thiết có n người iU ; 1 i n cần ký văn bản *{0,1}m . Chia văn bản m thành NSEC phần, sao cho có thể viết m theo dạng 1 2 3( || || || || )m m m m m  NSEC , sử dụng ký hiệu và định nghĩa mảng phân công ký V như ở Định nghĩa 2.1. Từng thành viên iU sẽ chịu trách nhiệm ký một số phần của văn bản m , tính giá trị hàm băm ( )i jh m ; 1 j NSEC và gửi cho người ủy nhiệm, người này sẽ tính giá trị băm cho jm như sau (Định nghĩa 2.2):   1 [ ] ( ) ; 1j i i j i e j h m j     V NSIG NSEC , 3 3 1 2( || || , )h H e e e w  NSEC . Bằng cách tính như trên chúng ta thu được chữ ký số tập thể có phân biệt trách nhiệm, gửi giá trị ip U đến ( 1)n  các thành viên còn lại. 3. Các thành viên tính và gửi ip  : 1 i n p p i U U   , 3 ( )i ip pk i i pubh S x P   V . 4. Người phụ trách sau khi có các chữ ký thành phần sẽ tạo khóa công khai ủy nhiệm:  i Bipk ID IDQ h Q Q V   . Và sau đó kiểm tra điều kiện: ˆ ˆ( , ) ( , ) i i ip pub pk p e P e P h Q U   , 1 i n p p i     , sau đó chữ ký số ủy nhiệm sẽ là ( , , , , )p pV w U V . 3.1.7. Xác thực chữ ký ủy nhiệm Người xác thực chữ ký ủy nhiệm sau khi nhận văn bản 'm và chữ ký ( , , , , )p pV w U V sẽ tiến hành các bước sau: 1. Kiểm tra 'm và bảo đảm w và các điều kiện liên quan. 2. Kiểm tra sự ủy quyền của n người ký. Nếu không hợp lệ thì dựng lại và từ chối chữ ký. 3. Tính các giá trị 2 ( )h H w , 3 3 ( , )h H m w  và: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 95 1 Bi n pk ID ID i Q h nQ Q nV           . 4. Kiểm tra điều kiện hợp lệ của chữ ký: 3 ˆ ˆ( , ) ( , )p pub pk pe P e P h Q U   Định lý 3.1 [Lược đồ ký ủy nhiệm tập thể đa thành phần]. Nếu m m  thì 3ˆ ˆ( , ) ( , )p pub pk pe P e P h Q U   . Chứng minh:   3 3 1 3 3 1 3 3 1 3 ˆ ˆ( , ) ( , ) ˆ ˆ( , ) ( , ) ˆ ˆ( , ( ) ) ( , ) ˆ ˆ( , ( ) ) ( , ) ˆ( , i i Bi p pub pk p p pub pk p i pk i i pub pub pk p i ID i i pub pub pk p i ID 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 W hS x P e P h Q U e P h hsQ tsP hsQ                                 V V NPSIG NPSIG NPSIG       3 1 3 3 1 3 3 1 3 1 ˆ( ) ) ( , ) ˆ ˆ( , ( ) ) ( , ) ˆ ˆ( , ) ( , ) ˆ( , Bi Bi Bi Bi ID i i pub pk p i pub ID ID i i pub pk p i pub ID ID p pub pk p i pub ID ID i x sP e P h Q U e P h hQ tP hQ x P e P h Q U e P h hQ nhQ nV U e P h Q U e P h h nQ Q                                      V V NPSIG NPSIG NPSIG   3 3 3 ˆ) ( , ) ˆ ˆ, ( , ) p pub pk p pub pk p pub pk p nV U e P h Q U e P h Q U e P h Q U                   NPSIG Biểu thức cuối cùng đúng khi 3 3h h  . Phân tích độ an toàn: Để giả mạo chữ ký số ( , , , , )p pV w U V , 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 ipkS 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. Tương tự như vậu để giả mạo được pU theo cần phải tính được ipU , người tấn công lại bắt buộc phải tìm được khóa bí mật ix và để tìm được giá trị này bắt buộc phải giải bài toán logarithm rời rạc theo và đây cũng là bài toán chưa giải được trong thời gian đa thức. Để chống tấn công từ bên trong trong lược đồ đã có các bước kiểm tra, xác thực ở mục 3.1.4 và 3.1.5. Công nghệ thông tin & Cơ sở toán học cho tin học Đặng Minh Tuấn, “Đề xuất mô hình chữ ký số tập thể kết hợp với một số mô hình khác.” 96 3.2. Kết hợp chữ ký số MSMS với chữ ký số mù dựa trên đường cong elliptic 3.2.1. Sinh khóa 1. Mỗi người ký iU (1 iNSIG ) chọn ngẫu nhiên NSEC số nguyên [ ]id j như là khóa bí mật trong khoảng [1, 1]q  ; 1 j NSEC và tính khóa công khai tương ứng như điểm: ( )i i iQ d P V và   1 ( [ ] [ ]) modi i i i j d j d j n    V V NSEC . 2. Khóa công khai của cả tập thể sẽ là: 1 i i Q Q    NSIG . 3.2.2. Giao thức lược đồ ký mù tập thể 1. Mỗi thành viên iU sinh cặp khóa một lần ( , )i ik R bằng cách chọn ngẫu nhiên [1, 1]ik q  và tính: ( ) ( , ). i i i i i k k R k P x y  V Tính ( ) i i k r c x và gửi ir tới người cần ký. 2. Người cần ký sẽ chọn hệ số mù , [1, 1]a b q  và tính điểm R trên đường cong elliptic E , tính: 1 ( , )i R R i R R x y    NSIG . Từ đó tính ( ) R r c x và tính: ( , )R RR aR bQ x y   . Tiếp theo tính giá trị ( )Rr c x và: 1( ( ) )m H m r b a r    Và gửi các giá trị ,m r tới các thành viên iU . 3. Các thành viên iU với 1 i NSIG ký văn bản mù bằng cách tính:  ( )( ) ( ) modi i i i is d m r k q    V V .Gửi giá trị này tới người cần ký. 4. Người cần ký tính: ( , ) ( ) i i ie e e i i R x y s P m r Q    , Và kiểm tra  ( ) mod ii e r c x q và tính: 1 i i s s    NSIG và  mods sa q . Chữ ký mù tập thể của văn bản m sẽ là ( , )r s . 3.2.3 Xác thực chữ ký mù tập thể Người xác thực nhận được văn bản 'm và chữ ký ( , , )r s V . Tính giá trị: ( , ) ( ( ) )e ex y sP H m r Q   . Kiểm tra điều kiện  ( ) moder c x q nếu thỏa mãn thì chữ ký hợp lệ. ( ( ) )sP H m r Q R   Định lý 3.2.1: [Lược đồ ký tập thể mù đa thành phần] Nếu m m  thì ( ( ) )sP H m r Q R   . Chứng minh: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 97             1 1 1 1 ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) i i i i i i i i i i i R aR bQ a R bQ a R m r a H m r Q a k d m r P H m r Q a s P H m r Q asP H m r Q sP H m r Q                                       V V NSIG NSIG NSIG NSIG Phân tích độ an toàn: Để giả mạo được chữ ký mù tập thể đa thành phần, người tấn công hoặc phải tìm được cửa sập của hàm một chiều của bài toán logarithm trên đường cong elliptic, tức là tìm được các khóa bí mật của các thành viên trong tập thể, Khi biết khóa công khai để tìm ra khóa bí mật, người tấn công bắt buộc giải bài toán Logarith rời rạc trên đường cong elliptic và đây là bài toán khó không giải được trong thời gian đa thức. Phương pháp tấn công thứ hai là xây dựng thuật toán để giả mạo chữ ký ( , )r s . Giá trị r có thể dễ dàng tính được thông qua các khóa công khai của các thành viên, tuy nhiên để có được thành phần s , người tấn công bắt buộc phải tìm được cả s và a . Và đây là bài toán phân tích ra thừa số, là một bài toán khó. Hoặc xây người tấn công có thể xây dựng thuật toán mới để tính s . Theo các công thức để tính được s thì cần phải tìm được các giá trị m , ,i id k và để tính được các giá trị này người tấn công buộc phải giải bài toán phân tích ra thừa số. Để tránh tấn công từ bên trong, lược đồ có phần kiểm tra và xác thực người ký tại bước 4, mục 3.2.2. 4. KẾT LUẬN Bài báo đã đưa ra định nghĩa tổng quát về chữ ký số tập thể đa thành phần đồng thời đề xuất được 02 lược đồ ký kết hợp giữa MSMS với chữ ký số ủy nhiệm và chữ ký số mù, với mô hình này một thành viên có thể ký nhiều phần khác nhau của văn bản và ngược lại một phần có thể được ký bởi nhiều người khác. Từ các kết quả này có thể mở rộng cho các hệ mật khác như hệ nhóm dàn (lattice) hay kết hợp với các mô hình chữ ký khác như chữ ký nhóm, chữ ký ngưỡng, chữ ký có cấu trúc... TÀI LIỆU THAM KHẢO [1]. K. Nakamura and K. Itakura, “A public-key cryptosystem suitable for digital multisignatures,” NEC Res. Dev., pp. 1–8, 1983. [2]. L. Harn, “Digital multisignature with distinguished signing authorities,” Electron. Lett., vol. 35, no. 4, pp. 294–295, 1999. [3]. H. F. Huang and C. C. Chang, “Multisignatures with distinguished signing authorities for sequential and broadcasting architectures,” Comput. Stand. Interfaces, vol. 27, no. 2, pp. 169–176, 2005. Công nghệ thông tin & Cơ sở toán học cho tin học Đặng Minh Tuấn, “Đề xuất mô hình chữ ký số tập thể kết hợp với một số mô hình khác.” 98 [4]. N. Tiwari, S. Padhye, and D. He, “Efficient ID-based multiproxy multisignature without bilinear maps in ROM,” Ann. des Telecommun. Telecommun., vol. 68, no. 3–4, pp. 231–237, 2013. [5]. Đ. M. Tuấn, “Lược đồ chữ ký số tập thể đa thành phần dựa trên bài toán Lô- ga-rít rời rạc,” Tạp chí Nghiên cứu KH&CN Quân sự, pp. 7–14, 2011. [6]. D. M. Tuan, “New Elliptic Curve Digital Multi-Signature Schemes for Multi- Section Messages,” IEEE RIVF, pp. 25–28, 2012. ABSTRACT A GENERAL MUILTI-SECTION MULTISIGNATURE SCHEMA AND ITS COMBINATIONS WITH OTHER TYPES OF SIGNATURES Digital signatures as well as multisignatures have significant roles in e- Government and e-Economy. The paper is to give formal definition for general mtlti-section multisignature. In this article also are proposed two combination of MSMS and proxy signature and blind signature based on ID- based cryptosystem and elliptic curve respectively. Keywords: Signature, Multisignature, Multi-Section Multisignature. Nhận bài ngày 05 tháng 9 năm 2016 Hoàn thiện ngày 27 tháng 9 năm 2016 Chấp nhận đăng ngày 26 tháng 10 năm 2016 Địa chỉ: 1 Bộ Khoa học Công nghệ. *Email : tuanvietkey@gmail.com, 098-868-6636.