Đề 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.