Nghiên cứu xây dựng lược đồ chữ ký số tập thể

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 49 - 
Abstract: This paper proposed two new digital 
signature schemes has the option of using keys as 
follows: use a unique key; use two keys, both of 
which key value does not change; use two keys, 
primary key is fixed, subkey change with each time 
to sign. The paper also offers analysis on the safety 
of the proposed schemes, has shown the ability to 
apply it in practice. 
I. ĐẶT VẤN ĐỀ 
Chữ ký số (Digital Signature) được sử dụng để 
chứng thực các văn bản trong các giao dịch điện tử, 
nhằm đáp ứng các yêu cầu về: tính xác thực, tính toàn 
vẹn và tính chống chối bỏ trách nhiệm [1,2]. Ở các 
lược đồ chữ ký số như ElGamal, Schnorr, chuẩn chữ 
ký số DSS của Mỹ hay GOST R34.10-94 của Liên 
bang Ngay,... khóa bí mật được sử dụng với mục đích: 
xác thực và chống giả mạo chữ ký. Do đó nó phải 
được giữ cố định đối với mọi văn bản ký, nhưng việc 
phải được giữ cố định sẽ làm cho nó có thể bị bẻ một 
cách dễ dàng. Để chống lại việc bẻ khóa, các lược đồ 
dạng trên phải sử dụng một khóa bí mật thứ hai, khóa 
này cần phải được thay đổi theo từng văn bản ký, hơn 
nữa giá trị của nó cho mỗi lần ký không được trùng 
với các giá trị đã sử dụng ở những lần ký trước đó. 
Như vậy, có thể nói rằng các lược đồ nói trên thuộc 
dạng sử dụng khóa một lần, trước mỗi lần ký đều phải 
sinh khóa mới, trên thực tế giá trị của khóa thứ 2 trước 
mỗi lần ký được tạo ra bởi một bộ sinh số ngãu nhiên. 
Bài báo này đề xuất một giải pháp mà có thể đưa các 
lược đồ trên về dạng sử dụng một khóa cho nhiều lần 
ký khác nhau, điều đó có thể giúp cho việc triển khai 
thực hiện được thuận tiện hơn mà không làm giảm độ 
an toàn của các lược đồ này. 
II. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TẬP 
THỂ 
Các lược đồ chữ ký số được đề xuất ở đây xây 
dựng trên cơ sở bài toán logarit rời rạc tương tự như 
các hệ chữ ký số Elgamal [3], chuẩn chữ ký số DSS 
của Mỹ [4], hay chuẩn chữ ký số của Liên bang Nga 
GOST R34.10-94 [5]. Trong đó, lược đồ chữ ký tập 
thể được phát triển từ lược đồ chữ ký cơ sở có dạng 
như sau: 
1. Lược đồ chữ ký cơ sở - LD 1.01 
1.1. Thuật toán hình thành và kiểm tra chữ ký số 
a) Hình thành các tham số công khai: 
+ Phát sinh cặp số nguyên tố p và q đủ lớn và: q|(p – 
1). 
+ Phát sinh pg qp mod/)1( −= α , là phần tử sinh có 
bậc q của nhóm *pZ , nghĩa là: pg <<1 và: 
pg q mod1≡ . Ở đây: *pZ∈α . 
Các giá trị (p, q, g) là các tham số công khai trong 
quá trình hình thành và kiểm tra chữ ký. 
b) Hình thành khóa công khai: 
Thủ tục hình thành khóa công khai bao gồm các 
bước thực hiện sau: 
1- Khóa bí mật x là một giá trị được chọn ngẫu 
nhiên trong khoảng: 11 −<< qx . 
2- Khóa công khai được tính theo công thức: 
pgy x mod−= . 
 3- Công khai y. 
c) Hình thành chữ ký số: 
Thủ tục hình thành chữ ký được thực hiện theo các 
bước như sau: 
 1- Chọn k thỏa mãn: 11 −<< qx .Tính r theo công 
thức: 
Nghiên cứu xây dựng lược đồ chữ ký số tập thể 
Research and Construction of Digital Multi-Signature Schemes 
Lưu Hồng Dũng 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 50 - 
pgr Mkh mod)||(= ; 
 2- Thành phần thứ nhất e của chữ ký được tính theo 
công thức : 
qMrhe mod)||(= 
 3- Thành phần thứ hai s của chữ ký được tính theo 
công thức: 
qexMkhs mod.)||( += 
 4- Cặp giá trị ),( se là chữ ký vào văn bản M. 
Chú ý: 
+ h() là hàm băm kháng va chạm mạnh. Ví dụ: nếu 
chọn |q| = 160 bit thì hàm băm có thể chọn là SHA-1. 
+ Toán tử || là phép nối xâu. 
 d) Kiểm tra chữ ký số: 
 Thủ tục kiểm tra được thực hiện qua các bước sau: 
 1- Tính: 
pygr es mod.'= ; 
 2- Tính: 
qMrhe mod)||'('= 
 3- Kiểm tra nếu: e’ = e thì tính hợp lệ của chữ ký 
và tính toàn vẹn của văn bản cần thẩm tra được công 
nhận. Ngược lại, chữ ký đã bị giả mạo hoặc nội dung 
văn bản đã bị sửa đổi. 
1.2. Tính đúng đắn của lược đồ được đề xuất 
Tính đúng đắn của lược đồ được đề xuất ở đây là 
sự phù hợp giữa thuật toán hình thành chữ ký với thuật 
toán xác minh chữ ký. Điều cần chứng minh là: Phù 
hợp với lược đồ LD 1.01 tồn tại tồn tại đẳng thức: 
ee =' . 
Chứng minh: 
Từ tính hợp lệ của chữ ký (e,s) ta có: 
rpg
pggg
pgg
pygr
Mkh
exexMkh
exqexMkh
es
==
=
=
=
−
−+
mod
mod..
mod).(
mod.'
)||(
..)||(
mod.)||(
Từ tính toàn vẹn của văn bản M suy ra: 
eqMrh
qMrhe
==
=
mod)||(
mod)||'('
Đây là điều cần chứng minh. 
1.3. Mức độ an toàn của lược đồ mới đề xuất 
Ở lược đồ mới đề xuất, có thể thấy rằng công thức 
tính thành phần thứ hai (s) của chữ ký tương tự như 
GOST R34.10-94 hay lược đồ chữ ký Schnorr. Tuy 
nhiên, ở lược đồ mới đề xuất đã sử dụng giá trị 
)||( Mkh thay cho k như trong lược đồ chữ ký 
Schnorr hay thay cho )(. Mhk trong GOST R34.10-
94. Vì vậy, nếu giá trị )||( Mkh tương đương với giá 
trị k trong lược đồ chữ ký Schnorr hay tương đương 
với )(. Mhk trong GOST R34.10-94 thì mức độ an 
toàn của lược đồ mới đề xuất sẽ hoàn toàn tương 
đương với 2 lược đồ chữ ký kia. 
Ta xét việc chọn k theo 3 phương án như sau: 
- Chọn k = x: Trường hợp này ta có lược đồ chỉ sử 
dụng một khóa với một lần chọn duy nhất. Dễ dàng 
thấy rằng, giá trị )||( Mkh là sự kết hợp của 3 yếu tố: 
bí mật (khóa mật x), ngẫu nhiên (văn bản cần M) và 
một chiều (hàm băm h()) nên giá trị )||( Mxh hoàn 
toàn thỏa mãn các yêu cầu thay thế cho giá trị k được 
sinh ra bằng một thuật toán sinh số ngẫu nhiên. Một 
điều rõ ràng là không ai có thể tính được giá trị này 
ngoài người ký (chỉ người ký mới biết khóa mật x), 
giá trị này thay đổi theo từng văn bản ký và quan trọng 
nhất: nó là duy nhất đối với mọi văn bản (mỗi văn bản 
chỉ được ký một lần), hơn nữa với số lượng văn bản 
cần ký M không đủ lớn thì không thể tính được 
)||( Mx từ )||( Mxh (tấn công hàm băm theo kiểu 
“ngày sinh” ) để từ đó có thể tính ra x. 
- Chọn xk ≠ nhưng cũng chỉ cần chọn một lần duy 
nhất và giữ cố định như x. Cách này hoàn toàn tương 
tự như cách thứ nhất. 
- Chọn ngẫu nhiên k bằng cách sử dụng một bộ sinh số 
ngẫu nhiên tương tự như trong DSS hay GOST 
R34.10-94,...thì giá trị )||( Mxh hoàn toàn tương 
đương với k về khía cạnh an toàn. 
Ta thấy rằng, do thành phần r được tính theo công 
thức: 
pgr Mkh mod)||(= 
nên để tính )||( Mkh từ r, rồi từ đó tính khóa x, theo 
công thức: 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 51 - 
qexMkhs mod.)||( += 
kẻ tấn công buộc phải giải bài toán logarit rời rạc. 
Mặt khác, với công thức tính thành phần thứ hai s 
của chữ ký: 
qexMkhs mod.)||( += 
kẻ tấn công cũng không thể giải được hệ phương trình: 
qexMkhs mod.)||( 111 += 
qexMkhs mod.)||( 222 += 
cho dù giá trị của k được giữ nguyên, để từ đó có thể 
tính được khóa bí mật x. ở đây: ),( 11 se và ),( 22 se là 
chữ ký tương ứng với 2 văn bản M1 và M2. 
Như vậy, để ký vào các văn bản khác nhau người 
ký cần chọn một cặp khóa ),( kx , trong đó khóa chính 
x được giữ cố định, khóa phụ k có thể là cố đinh hoặc 
thay đổi theo từng văn bản ký. Trường hợp, nếu chọn 
k thay đổi theo từng văn bản ký thì cũng không cần 
thiết phải sử dụng bộ sinh số ngẫu nhiên như ở các 
lược đồ khác, vì lược đồ này cho phép sử dụng các giá 
trị của k trùng nhau mà không làm giảm độ an toàn 
của lược đồ. Hơn nữa nếu chọn xk = thì lược đồ chỉ 
cần duy nhất 1 khóa bí mật mà không làm giảm mức 
độ an toàn, nếu so sánh với các lược đồ như Schnorr 
hay GOST R34.10-94. 
2. Lược đồ chữ ký tập thể- LD 1.02 
Giả thiết rằng nhóm người có thẩm quyền ký gồm 
n thành viên, để ký vào văn bản M. Cần lưu ý rằng, 
trong lược đồ này đại diện nhóm không nhất thiết và 
nói chung không phải là một thành viên trong nhóm, 
trên thực tế vai trò của đại diện nhóm có thể do một cơ 
quan chuyên trách đảm nhiệm. 
2.1. Thuật toán hình thành và kiểm tra chữ ký 
a) Hình thành các tham số công khai: 
Các giá trị (p, q, g) là các tham số công khai được 
hình thành tương tự như ở lược đồ LD 1.01 
b) Hình thành khóa công khai tập thể: 
Thủ tục hình thành khóa công khai tập thể bao 
gồm các bước như sau: 
1- Mỗi thành viên chọn khóa bí mật ix thỏa mãn: 
]11 −<< qxi và tính khóa công khai cá nhân 
tương ứng: 
 pgy ixi mod
−
= , i = 1, 2, ..., n. 
2- Khóa công khai tập thể được đại diện nhóm tính 
theo công thức: 
 ∏
=
=
n
i
i pyY
1
mod . 
3- Công khai Y. 
Chú ý: 
Để chống giả mạo trong việc hình thành khóa 
công khai tập thể Y thì các khóa công khai cá nhân iy 
cần phải được công khai trong nhóm và mọi thành 
viên của nhóm ký đều phải tham gia tính khóa công 
khai tập thể Y, chỉ khi nào có sự xác nhận của tất cả 
các thành viên thì Y mới được công bố làm khóa công 
khai tập thể của nhóm ký. 
c) Hình thành chữ ký tập thể: 
Thủ tục hình thành chữ ký tập thể bao gồm các 
bước như sau: 
1 - Mỗi thành viên chọn ik thỏa mãn ]11 −<< qki 
và tính thành phần thứ nhất của chữ ký cá nhân 
theo công thức: 
 pgr Mkhi i mod
)||(
= , i = 1, 2, ..., n. 
 rồi gửi cho đai diện. Ở đây: h() là hàm băm được 
chọn đủ an toàn, chẳng hạn: SHA-1 và toán tử || là 
phép nối 2 xâu. 
2- Đại diện nhóm tính: 
prR
n
i
i mod
1
∏
=
= , 
rồi tính thành phần thứ nhất của chữ ký tập thể: 
 qMRhE mod)||(= 
Sau đó đại diện nhóm gửi giá trị E cho các thành 
viên trong nhóm 
3- Các thành viên trong nhóm tính phần thứ hai của 
chữ ký cá nhân theo công thức: 
qExMkhs iii mod.)||( += , i = 1, 2, ..., n. 
rồi gửi is cho đại diện nhóm. Cặp giá trị ),( ii sr là 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 52 - 
chữ ký cá nhân của thành viên thứ i vào văn bản M. 
 4- Sau khi nhận được tất cả chữ ký cá nhân ( , )i ir s 
của các thành viên, đại diện nhóm kiểm tra sự 
hợp lệ của các chữ ký này bằng cách tính: 
pgyr isEii mod.
'
= , i = 1, 2, ..., n. 
và: 
prR
n
i
i mod'
1
'∏
=
= 
Kiểm tra nếu: RR =' thì tính hợp lệ các chữ ký cá 
nhân của các thành viên được công nhận, đại diện 
nhóm sẽ tính thành phần thứ hai của đa chữ ký theo 
công thức: 
 qsS
n
i
i mod
1
∑
=
= 
5- Phát hành ),( SE cùng văn bản M. 
Chú ý: 
+ Để chống giả mạo trong việc tính R thì các giá 
trị ir cần phải được công khai trong nhóm và mọi 
thành viên của nhóm ký đều phải tham gia tính R, chỉ 
khi nào có sự xác nhận của tất cả các thành viên thì R 
mới được sử dụng để tính thành phần thứ nhất E của 
chữ ký tập thể.. 
+ Có thể sử dụng cặp ),( SR làm chữ ký của 
nhóm lên M thay cho cặp ),( SE . Tuy nhiên cần lưu ý 
đến độ dài của chữ ký trong 2 trường hợp như sau: Giả 
sử chọn |p| = 1024 bit và |q| = 160 bit, khi đó nếu chọn 
cặp ),( SR là chữ ký thì độ dài của chữ ký sẽ là: |p| + 
|p| = 1024 bit + 1024 bit = 2048 bit. Còn nếu chọn cặp 
),( SE làm chữ ký thì độ dài của chữ ký trong trương 
hợp này là: |p| + |q| = 1024 bit + 160 bit = 1184 bit. Rõ 
ràng việc chọn cặp ),( SE làm chữ ký đã giúp cho độ 
dài của chữ ký được rút ngắn đáng kể. 
+ Tương tự như lược đồ LD 1.01, lược đồ được đề 
xuất ở đây có 3 phương án sử dụng khóa như sau: 
- Sử dụng một khóa duy nhất: khi chọn ii xk = , i = 
1, 2,...,n. 
- Sử dụng 2 khóa với giá trị được chọn khác nhau, 
nhưng đều được giữ cố định. 
- Sử dụng 2 khóa: trong đó khóa thứ nhất (xi) được 
giữ cố định, còn khóa thứ hai (ki) thay đổi ở mỗi 
lần ký như các lược đồ hiện tại (DSS, GOST 
R34.10-94,...) đang dùng. 
d) Kiểm tra đa chữ ký số: 
Thủ tục kiểm tra được thực hiện qua các bước sau: 
1- Từ cặp (E,S) nhận được tính: 
 pYgR ES mod.'' = 
 2- Tính: 
 qMRhE mod)||''('= 
 3- Kiểm tra nếu: EE =' thì chữ ký là hợp lệ và tính 
toàn vẹn của văn bản được bảo đảm. Ngược lại, chữ 
ký đã bị giả mạo hoặc nội dung của văn bản đã bị thay 
đổi. 
2.2. Tính đúng đắn của lược đồ mới xây dựng 
Tính đúng đắn của lược đồ mới đề xuất thể hiện 
qua tính đúng đắn của thủ tục kiểm tra chữ ký cá nhân 
và tính đúng đắn của thủ tục kiểm tra chữ ký tập thể 
như sau: 
a) Tính đúng đắn của thủ tục kiểm tra chữ ký cá nhân 
Tính đúng đắn của thủ tục kiểm tra chữ ký cá nhân 
là sự phù hợp giữa phương pháp hình thành chữ ký cá 
nhân với phương pháp kiểm tra tính hợp lệ của chữ ký 
cá nhân mà lược đồ đã đề xuất. Điều cần chứng minh 
ở đây là: 
Với: 
prR
n
i
i mod'
1
'∏
=
= 
trong đó: pysr Ei
s
i
i mod.' = , i = 1, 2, ..., n. 
Nếu: RR =' thì chữ ký cá nhân của tất cả các 
thành viên trong nhóm là hợp lệ. Nói cách khác là 
không có bất kỳ sự giả mạo nào trong các chữ ký cá 
nhân của các thành viên trong nhóm. 
Chứng minh: 
 Thật vậy, theo định nghĩa: 
∏
=
=
n
i
i prR
1
mod 
và: 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 53 - 
prR
n
i
i mod'
1
'∏
=
= 
Vì vậy, nếu RR =' thì: ii rr =' với: i = 1,2,...n. 
Giả sử thành phần thứ 2 của chữ ký cá nhân cần 
thẩm tra là: qExMkhs iii mod'.)'||'( += 
Nên: 
pggg
pgg
pygr
ExExMkh
ExqExMkh
E
i
s
i
iii
iii
i
mod..
mod.
mod.
.'.)''||(
.mod'.)''||(
'
−
−+
=
=
=
Nếu: )'( ii rr = với: i = 1,2,...n. thì: 
pg
pggg
Mkh
ExExMkh
i
iii
mod
mod..
)||(
.'.)''||(
=
−
 (1) 
Từ (1) suy ra: 
 ii xx =' , ii kk =' và M’ = M. 
Như vậy ( ir , is ) thực sự là chữ ký cá nhân của 
thành viên thứ i, nói cách khác chữ ký này là hợp lệ. 
b) Tính đúng đắn của thủ tục kiểm tra chữ ký tập thể 
Tính đúng đắn của thủ tục kiểm tra chữ ký tập thể 
là sự phù hợp giữa phương pháp hình thành chữ ký tập 
thể với phương pháp kiểm tra tính hợp lệ của chữ ký 
tập thể và tính toàn ven của văn bản được ký mà lược 
đồ đã đề xuất. Điều cần chứng minh ở đây là: 
Với: 
pYgR ES mod.'' = 
và: 
qMRhE mod)||''('= 
Nếu: EE =' thì chữ ký là hợp lệ và tính toàn vẹn 
của văn bản cần thẩm tra được bảo đảm. 
Chứng minh: 
Theo định nghĩa ta có: 
 qMRhE mod)||(= 
và: 
 qMRhE mod)||''('= 
Nếu EE =' thì suy ra: 
qMRhqMRh mod)||(mod)||''( = (2) 
Từ (2) suy ra văn bản cần thẩm tra cũng chính là 
văn bản được ký hay tính toàn vẹn của văn bản được 
bảo đảm và: RR ='' . 
Xét thành phần S của chữ ký cần thẩm tra, theo 
định nghĩa S sẽ có dạng: 
qExqMkh
qExMkh
qsS
n
i
i
n
i
i
i
n
i
i
n
i
i
mod'.mod)||'(
mod'.)||'(
mod
11
1
1
∑∑
∑
∑
==
=
=
+=
+=
=
Nên: 
Mặt khác, theo định nghĩa ta có: 
pgprR
n
i
i qMxhn
i
i modmod 1
mod)||(
1
∑
==
=
=
∐ 
Vì vậy, nếu RR ='' thì: 
qg
pggg
n
i
i
n
i
i
n
i
i
n
i
i
qMkh
qExqExqMkh
mod
mod..
1
111
mod)||(
mod.mod'.mod)'||(
∑
=
∑∑∑
=
===
−
Từ đây suy ra: 
 ii xx =' và ii kk =' , với: i = 1,2,....n. 
Như vậy (E,S) hợp lệ, đây là điều cần phải chứng 
minh. 
2.3. Mức độ an toàn của lược đồ mới xây dựng 
Mức độ an toàn của các lược đồ chữ ký số được 
đánh giá bằng khả năng chống lại các kiểu tấn công 
khác nhau: 
- Tấn công bằng cách tính khóa mật. 
- Tấn công theo kiểu giả mạo chữ ký. 
Ở kiểu tấn công thứ nhất, kẻ tấn công phải giải bài 
toán logarith rời rạc mà khả năng thành công là rất 
thấp nếu các tham số (p, q) được lựa chọn thích hợp. 
Ở kiểu tấn công thứ 2, tồn tại một số phương pháp giả 
mạo như sau: 
pggg
pgg
pYgR
n
i
i
n
i
i
n
i
i
n
i
i
 ... 
pggggg
ggggg
pyyyyy
gR
nmm
MkhMkhMkh
MkhMkhExEx
ExExExMkhExMkh
ExMkhExMkhExMkh
Exxxxx
sssss
E
nmm
sssss
nmm
mm
nnmm
mmx
nmm
nmm
nmm
==
=
=
=
=
+−
−−
−−++
+++
−−−−−
+−
++++++
+−
+−
++
−−
+−
+−
+−
mod........
mod....
....mod.
........
.....
mod)........(
.........
mod)........(
.''
1132
)||()||()||(
)||()||(..
...)||(.)||(
.)||(.)||(.)||(
1132
)......(
11
3211
3211
11332
1132
1132
1132
Nếu văn bản không bị sửa đổi, ta có: 
EqMRh
qMRhE
==
=
mod)||(
mod)'||''('
Chữ ký đã được xác nhận là hợp lệ. Bằng cách đó 
thành viên thứ nhất đã mạo danh được thành viên thứ 
m, và nói chung là có thể mạo danh được bất kỳ thành 
viên nào trong nhóm ký. Hơn nữa, phương pháp giả 
mạo này có thể áp dụng cho bất kỳ lược đồ chữ ký tập 
thể nào. 
Về mặt toán học, phương pháp giả mạo này là 
hoàn toàn đúng. Tuy nhiên, ta hãy xét tính thực tiễn 
của nó, ở đây có 2 vấn đề: 
 Thứ nhất, việc tính khóa công khai cá nhân của kẻ 
mạo danh: pyy m mod
1
1
−
= là không thể thực hiện 
được nếu có một cơ chế kiểm tra chặt chẽ khi hình 
thành khóa công khai tập thể Y. Giả sử việc tính khóa 
công khai cá nhân của kẻ mạo danh )( 1y như trên 
không bị phát hiện thì kẻ mạo danh cũng chỉ có thể 
thực hiện giả mạo được với thành viên thứ m, mà 
không thể giả mạo với các thành viên khác được, vì 
khóa công khai tập thể Y sau khi đã được công bố thì 
không thể tùy ý thay đổi theo từng văn bản ký. 
Thứ hai, ta thấy rằng điều kiện tiên quyết để 
phương pháp này thực hiện được là kẻ mạo danh phải 
biết được chữ ký cá nhân của thành viên mà chúng 
muốn giả mạo chữ ký. Chính điều đó đã hạn chế khả 
năng ứng dụng của phương pháp này trong thực tiễn. 
Vì rằng, kẻ mạo danh chỉ có thể biết được chữ ký cá 
nhân của những thành viên mà chúng muốn giả mạo 
chữ ký khi họ đã đồng ý ký vào văn bản và gửi chữ ký 
cá nhân của mình cho nhóm. Nhưng giả mạo chữ ký 
của thành viên đã ký vào văn bản là một việc làm vô 
nghĩa và không đúng với bản chất của sự giả mạo. 
Hơn nữa, không thể lấy chữ ký cá nhân của một thành 
viên lên văn bản này để giả mạo chữ ký của họ với các 
văn bản khác được, vì thành phần s của chữ ký cá 
nhân phụ thuộc vào giá trị băm (bản tóm lược) của văn 
bản được ký, khi nội dung văn bản bị thay đổi thì chữ 
ký cá nhân của các thành viên mà chúng muốn mạo 
danh không còn phù hợp để tạo chữ ký cho văn bản đã 
bị sửa đổi nữa, điều đó đồng nghĩa với việc kẻ giả mạo 
không có được chữ ký cá nhân của những thành viên 
mà chúng muốn mạo danh, do đó không thể thực hiện 
việc giả mạo theo phương pháp này được. 
Phương pháp thứ 3: 
Ta cũng xét trường hợp kẻ mạo danh là thành viên 
thứ nhất muốn giả mạo chữ ký của thành viên thứ m 
trong nhóm. Kẻ mạo danh sẽ thực hiện các bước sau: 
1- Tính thành phần thứ nhất của chữ ký cá nhân: 
prgr m
Mkh
mod.)||(1 1= 
2- Tính thành phần thứ 2 của chữ ký cá nhân: 
qsExMkhs m mod.)||( 111 ++= 
Do đó: 
∏
=
+−
=
=
=
+
−
n
i
i
MkhMkhMkh
MkhMkhMkh
nmm
pr
pggg
ggg
prrrrrR
nmm
m
1
)||()||()||(
)||()||()||(
1121
mod
mod......
.....
mod........
1
121
Và: 
∑∑
==
++
−−
+−
=+=
++
+++
+++++
++++=
+++++=
n
i
i
n
i
ii
nn
mm
mmmm
nmm
qsqExMkh
qExMkh
ExMkh
ExMkhExMkh
ExMkhExMkh
psssssS
11
11
11
2211
1121
modmod.)||(
mod.)||(
....)||(
.)||(.)||((
....)||(.)||(
mod......
Điều đó cho thấy rằng, nhóm ký vẫn tạo ra được 
chữ ký hợp lệ với đầy đủ n thành viên mà không cần 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 56 - 
sự có mặt của thành viên thứ m. Tuy nhiên, phương 
pháp giả mạo này đã thực hiện không đúng với yêu 
cầu của lược đồ đưa ra. Xem xét lại công thức tính R 
và S của lược đồ: ∏
=
=
n
i
i prR
1
mod 
và: ∑
=
=
n
i
i qsS
1
mod 
Các công thức trên đã chỉ ra một cách rõ ràng 
rằng, chữ ký tập thể phải được tạo ra từ n chữ ký cá 
nhân của các thành vên trong nhóm và nó chỉ được tạo 
ra khi có đầy đủ số lượng chữ ký cá nhân của các 
thành viên. Ở mức thực thi bằng chương trình, việc 
tính R và S có thể được thực hiện bằng các vòng lặp 
như sau: 
 R := 1; 
For i := 1 to n do 
 R := R * ri ; 
Hay: 
 S:=0; 
 i := 1; 
While (i <=n) do 
 Begin 
 S := S + si ; 
 i := i +1 ; 
 End 
Rõ ràng là 2 vòng lặp trên không thể kết thúc được 
nếu không có đủ số lượng chữ ký cá nhân của các 
thành viên trong nhóm, nghĩa là chữ ký tập thể không 
được tạo ra nếu không đủ số lượng thành viên tham 
gia ký. Như vậy, nếu ở mức giao thức và mức thực thi 
(bằng phần cứng hay phần mềm) có cơ chế kiểm soát 
tốt việc thực hiện các yêu cầu mà lược đồ đã chỉ ra thì 
phương pháp giả mạo trên sẽ không thể áp dụng được. 
Phương pháp này có ưu điểm là kẻ mạo danh 
không cần phải tính khóa công khai cá nhân của mình 
theo khóa công khai cá nhân của thành viên mà chúng 
muốn mạo danh như ở phương pháp thứ hai, điều đó 
làm cho phương pháp giả mạo này phù hợp với thực tế 
hơn. Tuy nhiên, về bản chất phương pháp này cũng 
giống như phương pháp thứ hai, kẻ mạo danh chỉ thực 
hiện giả mạo được chữ ký của những thành viên trong 
nhóm khi chúng biết được chữ ký cá nhân mà chúng 
đang muốn giả mạo. Trường hợp dù có được chữ ký 
cá nhân ở những lần ký trước đó của thành viên mà 
chúng đang muốn giả mạo thì kẻ mạo danh cũng 
không thể áp dụng phương pháp giả mạo này được. Ta 
xét một trường hợp cụ thể, mà ở đó kẻ mạo danh có 
thể là n-1 thành viên muốn giả mạo chữ ký của thành 
viên thứ n trong nhóm. Kẻ mạo danh được chọn là 
một thành viên, chẳng hạn thành viên thứ 1, kẻ mạo 
danh chọn cho mình (r1,s1) của lần ký mới này như 
sau: 
1- Tính thành phần thứ nhất của chữ ký cá nhân: 
prr rnn mod)(' 1= 
2- Tính thành phần thứ 2 của chữ ký cá nhân: 
qrss nn mod.' 1= 
Với lưu ý: ở đây người giả mạo chỉ cần lấy rn , sn 
cũ của lần 1 lần ký trước đó mà thành viên m đã ký 
(có mang thông tin về xn ), chứ không phải của lần ký 
này. 
Nhóm n-1 người thay cặp (rn’ , sn’) mới qua mặt 
người thứ n, còn n-1 thành viên, cả thứ 1, vẫn không 
thay đổi. Hệ ký vẫn tỏ ra đủ n thành viên, có sử dụng 
khóa công khai Y vẫn hợp lý, hệ (R’,S’,Y,g) mới vẫn 
hợp lệ, tạo được sự thuyết phục rằng m thành viên đã 
ký vào văn bản, và hậu quả như thế nào? 
Ta biết rằng, trước khi hình thành chữ ký tập thể, 
thì chữ ký cá nhân của các thành viên phải được kiểm 
tra về tính hợp, trong trường hợp này, chữ ký cá nhân 
của thành viên thứ n được kiểm tra như sau : 
1- Tính: pygr En
s
n
n mod.'' '= 
2- Kiểm tra nếu ''' nn rr = thì )','( nn sr là hợp lệ, 
ngược lại )','( nn sr là giả mạo. 
Theo giả thiết: prr rnn mod)(' 1= 
Và: qrss nn mod.' 1= 
Ở đây: nr và ns là chữ ký cá nhân của thành viên 
thứ n trong 1 lần ký trước nào đó mà kẻ mạo danh (ở 
đây là thành viên thứ 1) có được. 
Do: qExMkhs nnn mod*.*)||( += 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 57 - 
Nên: qrExMkhs nnnn mod*)..*)||((' += 
Cần lưu ý rằng, văn bản của lần ký hiện tại là M 
và thành phần thứ nhất của chữ ký tập thể tương ứng 
là E, còn M* là văn bản của lần ký trước nào đó và E* 
thành phần thứ nhất của chữ ký tập thể tương ứng M*. 
Vì vậy: 
pggr
pggr
pggg
pgg
pygr
ExrEx
n
ExrExr
n
ExrExrMkh
ExrExMkh
E
n
s
n
nn
nn
nnn
nnn
n
mod.'.
mod..)(
mod..
mod).(
mod.''
..*.
..*.
..*.*).||(
*)..*)||((
'
1
11
11
1
−
−
−
−+
=
=
=
=
=
Kết quả cho thấy là: ''' nn rr ≠ , như vậy là sự giả 
mạo đã bị phát hiện trước khi hình thành chữ ký tập 
thể. Chúng ta lại giả sử rằng, sự giả mạo này không bị 
phát hiện (nếu đại diện nhóm cũng tham gia vào việc 
giả mạo này), khi đó chữ ký tập thể sẽ được hình 
thành như sau: 
pgg
pggg
prrrprrrR
Mkh
qMkh
rMkhMkhMkh
r
nn
n
n
i
i
n
mod.
mod.....
mod)...(.mod'....
*)||*(mod)||(
*).||*()||()||(
2121
1
1
121
1
∑
=
=
==
−
=
 qMRhE mod)||(= 
qExxE
qMkhMkh
qExMkh
ExMkhExMkh
qrsss
qsssS
n
n
i
i
n
n
i
i
nn
n
n
mod*)..(
mod*))||*()||((
mod*.*)||*(
....)||(.)||(
mod....
mod'...
1
1
1
1
2211
121
21
++
+=
++
++++=
++=
++=
∑
∑
−
=
−
=
Ký hiệu *nk để chỉ rằng đây là giá trị của k của 
thành viên n trong lần ký trước. Việc kiểm tra tính hợp 
lệ của chữ ký và tính toàn vẹn của văn bản đươc thực 
hiện như sau: 
1- Tính: pYgR ES mod.'' = 
 và: qMRhE mod)||''('= 
2- Kiểm tra nếu: EE =' thì chữ ký là hợp lệ và tính 
toàn vẹn của văn bản cần thẩm tra được bảo đảm. 
Từ (E,S) cần thẩm tra, ta tính ''R như sau: 
pgggg
pggg
ggpYgR
ExExMkh
qMkh
E
x
Ex
xE
Mkh
qMkh
ES
nnn
n
i
i
n
i
i
n
n
i
i
n
n
i
i
mod...
mod).(..
..mod.''
.*.*)||*(mod)||(
*.
.
*)||*(mod)||(
1
1
1
1
1
1
1
−
−
∑
=
∑∑
∑
==
−
=
=
−
=
−
=
Do đó: 
qMpg
ggh
qMRhE
EEn
Mkh
qMkh
n
n
n
i
i
mod)||)mod
..((
mod)||''('
)*(
*)||*(mod)||(
1
1
−
∑
=
==
−
=
Trong khi đó: 
qMpg
gh
qMRhE
Mkh
qMkh
n
n
i
i
mod)||)mod
.((
mod)||(
*)||*(
mod)||(
1
1
∑
=
=
−
=
Như vậy là: EE ≠' nên tính hợp lệ của chữ ký và 
tính toàn vẹn của văn bản cần thẩm tra đã không được 
công nhận. 
Có thể xem xét thêm một tình huống ứng dung 
phương pháp tấn công giả mạo này. Trong ví dụ này, 
các khóa công khai ym của các thành viên giả thiết 
không thay đổi sau một số lần ký, và N-1 thành viên 
muốn qua mặt thành viên thứ N, giả sử là A, họ trao 
cho một thành viên trong nhóm, giả sử là B, ví dụ 
người đại diện là không trung thực trong nhóm, tấn 
công A như sau: Giả sử lần ký mới này, văn bản là M’ 
có giá trị hàm băm H(M’)=m’, còn văn bản lần trước 
M có hàm băm H(M)=m. 
Người B sẽ thực hiện: 
a) Do q nguyên tố rất lớn, nên với xác suất hầu chắc 
chắn, xảy ra (m’, q)=1 nên tồn tại m’-1 mod q. 
b) chọn t tùy ý sao cho 0< t < q để t nguyên tố cùng 
nhau với q, p. Từ đó hệ phương trình đồng dư Trung 
hoa sau (i) có nghiệm: 
 r’N = (rN)t mod p (i1) 
 r’N = rN. t.m.m’
-1
 mod q (i2) 
 Từ (i2) suy ra: 
 (ii) r’N.m’ = rN. t.m. mod q 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 58 - 
Chi tiết hơn, chẳng hạn nếu có xN lẻ, (-1)xN mod p 
=-1 và g(p-1)/2 = -1 mod p (khi p =3 mod 4), nghĩa là 
thay vào (i1) với t=(p-1)/2 sẽ có r’N=(rN)t = -1 mod p, 
ta có thể lấy đơn giản r’N = p-1 thỏa phương trình (i). 
Bây giờ B lấy hệ biểu diễn (*): 
 (iii) r’N = (rN)t mod p, 
 s’N = sN.t mod q , 
c) Trước hết, giả thiết trường hợp đơn giản nhất là với 
hệ N chữ ký mới lần này cho văn bản M’, N-1 thành 
viên vẫn được phép sử dụng các giá trị cũ r1,,..,rN-1, 
(chỉ s1,...,sN-1 là thay đổi), còn thành viên thứ N (bị 
qua mặt bởi N-1 thành viên kia) bị thay bởi cặp 
(r’N,s’N) bởi thành viên B nào đó, khi đó với hai lần 
ký- hiện tại và trước đây ta có: 
 (iv) E’ = r1.r2...rN-1.r’N. m’ mod q 
 và E = r1.r2...rN-1rN. m mod q 
Ta sẽ kiểm chứng hệ thức sau vẫn thỏa mãn: 
(v) r’N = g s’N . yN E’ mod p 
- Trước hết, do (ii) và (iv) ta có 
 (vi) E’ =E.t mod q, 
 - Sử dụng đẳng thức này và (iii), do 
 sN=kN+xN.E mod q của lần ký trước, ta được: 
 s’N =sN.t = (kN+ xN.E).t mod q 
 = kN.t + xN.E’ mod q ,từ đó: 
 r’N = (rN)t = g kN.t = gs’N – xN .E’ 
= gs’N . yN E’ mod p, do vậy yêu cầu (v) thỏa mãn. 
 - Và nếu cần - từ 1 cặp (r’N,s’N) này, người B đi lấy 
tham số chữ ký khác qua mặt A theo kiểu tấn công thứ 
3, sẽ có thể lấy cặp (r’N,s’N) khác nữa - cho cùng lần 
ký mới này. Từ đó suy ra cách mà sơ đồ vẫn hoạt động 
mà không cần có thành viên N. 
Đây cũng là ví dụ về cách áp dụng tấn công (kiểu 
thứ 3) thoạt đầu có vẻ là đúng đắn, tuy nhiên nếu xem 
xét kỹ thì chúng ta sẽ thấy rằng nó chỉ có ý nghĩa toán 
học thuần túy. Bởi vì trong trường hợp này, phương 
pháp chỉ thành công được với giả thiết: “ ... trường 
hợp đơn giản nhất là với hệ N chữ ký mới lần này 
cho văn bản M’, N-1 thành viên vẫn được phép sử 
dụng các giá trị cũ r1, ..., rN-1, (chỉ s1, ..., sN-1 là thay 
đổi),..”. Nhưng đây lại là một giả thiết rất không thực 
tế. Vì rằng, việc sử dụng r cũ thì cũng đồng nghĩa với 
việc dùng lại giá trị cũ của k, chỉ cần như thế thôi thì 
kẻ tấn công đã tìm ngay được x rồi, mà không cần 
dùng đến phương pháp nào nữa cả. 
Từ những phân tích trên đây có thể thấy rằng lược 
đồ mới xây dựng là an toàn với các kiểu tấn công giả 
mạo đã biết trên thực tế. 
III. KẾT LUẬN 
Các lược đồ chữ ký số được đề xuất trong bài báo, 
ngoài phương án sử dụng 2 khóa như các lược đồ hiện 
tại, còn cho phép giữ cố định giá trị cho khóa thứ 2 
hay chỉ sử dụng một khóa duy nhất khi ký vào các văn 
bản khác nhau mà tính an toàn của lược đồ vẫn được 
đảm bảo. Điều đó rất có ý nghĩa khi một người ký 
tham gia vào nhiều nhóm khác nhau và mỗi nhóm phải 
ký nhiều văn bản khác nhau. Hơn nữa, việc sử dụng 
một khóa cho các lần ký khác nhau sẽ cho phép việc 
triển khai ứng dụng lược đồ trong thực tế được thuận 
tiện hơn. 
Bài báo cũng đưa ra những phân tích về mức độ 
an toàn của các lược đồ được đề xuất, cho thấy khả 
năng ứng dụng chúng là hoàn toàn có thể trên thực tế. 
TÀI LIỆU THAM KHẢO. 
[1] D.R Stinson, Cryptography: Theory and Practice, 
CRC Press 1995. 
[2] WENBO MAO, “Modern Cryptography: Theory and 
Practice”, Prentice Hall PTR, 2003, p. 648. 
[3] T. ElGamal. A public key cryptosystem and a signature 
scheme based on discrete logarithms. IEEE 
Transactions on Information Theory. 1985, Vol. IT-31, 
No. 4. pp.469–472. 
[4] National Institute of Standards and Technology, NIST 
FIPS PUB 186-3. Digital Signature Standard, U.S. 
Department of Commerce,1994. 
[5] GOST R 34.10-94. Russian Federation Standard. 
Information Technology. Cryptographic data Security. 
Produce and check procedures of Electronic Digital 
Signature based on Asymmetric Cryptographic 
Algorithm. Government Committee of the Russia for 
Standards, 1994 (in Russian). 
[6] K. ITAKURA and K. NAKAMURA, “A public key 
cryptosystem suitable for digital multisignatures”, 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 7 (27), tháng 5/2012 
 - 59 - 
NEC Research and Development, Vol. 71, 1983, pp 1-
8. 
[7] TATSUAKI OKAMOTO, “A digital multisignature 
scheme using bijective public-key cryptosystems”, 
ACM Trans. Comput. Syst., Vol.6, No. 8, 1988, pp 
432–441. 
[8] M. BURMESTER, Y. DESMEDT, H. DOI, M. 
MAMBO, E. OKAMOTO, M. TADA and Y. 
YOSHIFUJI, “A structured ElGamal-type 
multisignature scheme”, Proceedings of Third 
International Workshop on Practice and Theory in 
Public Key Cryptosystems (PKC 2000), Springer-
Verlag, 2000, pp. 466-483. 
[9] Jun ZHANG, “Cryptographic Analysis of the Two 
Structured Multi-signature Schemes”, Journal of 
Computational Information Systems 6:9 (2010) 3127-
3135. 
Nhận bài ngày:18/05/2011 
SƠ LƯỢC VỀ TÁC GIẢ 
LƯU HỒNG DŨNG 
Sinh năm 1966. 
Tốt nghiệp Đại học chuyên ngành 
Vô tuyến điện tử năm 1989 và Cao 
học ngành Kỹ thuật Điện tử và 
Thông tin liên lạc năm 2000 tại 
Học viện Kỹ thuật Quân sự. 
Hiện là giảng viên Khoa Công nghệ Thông tin, Học 
viện Kỹ thuật Quân sự. 
Lĩnh vực nghiên cứu: An toàn và bảo mật thông tin, 
An ninh mạng máy tính. 
Email: luuhongdung@gmail.com