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ệ 
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.