Một lược đồ chữ ký tập thể xây dựng trên tính khó của việc giải bài toán phân tích số và khai căn trên Zn

ên Zn.” 46 
- Chọn hàm băm SHA – 1 với kích thước dữ liệu ra 160 bit. 
Với các tham số như trên, thuật toán ký của lược đồ cơ sở cần thực hiện 3 phép 
lũy thừa: một phép lũy thừa với kích thước số mũ 16 bit (   nkR t mod ), phép lũy 
thừa thứ hai có kích thước số mũ 160 bit ( nx
E
mod1 ) và phép lũy thừa thứ 3 có 
kích thước 2048 bit ( naS x mod2 , với:   nxka E mod1 ), trong khi đó thuật 
toán ký của RSA chỉ thực hiện 1 phép tính lũy thừa duy nhất với kích thước số mũ 
2048 bit ( nmS d mod ). Tuy phải thực hiện nhiều hơn 2 phép lũy thừa so với 
RSA, song do kích thước số mũ của 2 phép lũy thừa đầu khá nhỏ so với kích thước 
số mũ 2048 bit của phép lũy thừa thứ 3 trong lược đồ cơ sở cũng như kích thước số 
mũ của phép lũy thừa trong RSA, nên có thể coi tốc độ thực hiện thuật toán ký của 
lược đồ cơ sở và RSA là tương đương. Ở thuật toán kiểm tra, lược đồ cơ sở cũng 
phải thực hiện 3 phép lũy thừa có kích thước số mũ như ở thuật toán ký (16 bit, 
160 bit và 2048 bit), còn RSA chỉ phải thực hiện 1 phép lũy thừa duy nhất với số 
mũ có kích thước 16 bit ( nS e mod ), vì vậy tốc độ thực hiện thuật toán kiểm tra 
của lược đồ cơ sở là khá chậm so với RSA. Đây chính là chi phí phải trả cho việc 
nâng cao độ an toàn của lược đồ cơ sở, khi mà độ an toàn của RSA sẽ bị phá vỡ 
hoàn toàn nếu kẻ tấn công chỉ cần giải được 1 trong 2 bài toán IFP(n) hoặc 
RSAP(n,e) , song muốn phá vỡ được độ an toàn của lược đồ cơ sở thì kẻ tấn công 
buộc phải giải được đồng thời cả 2 bài toán này. Ngoài ra, việc thực hiện các phép 
toán lũy thừa với kích thước số mũ 2048 bit hay 4096 bit như ở lược đồ RSA và 
lược đồ cơ sở là hoàn toàn khả thi trong các ứng dụng thực tế. 
2.3. Lược đồ chữ ký tập thể 
Lược đồ chữ k ý tập thể ở đây được phát triển từ lược đồ cơ sở được đề xuất ở 
mục 2.2 với các chức năng như sau: 
- Hình thành chữ ký tập thể từ chữ ký cá nhân của một hay một nhóm đối 
tượng ký và chữ ký của CA. Kích thước của chữ k ý không phụ thuộc vào số 
lượng thành viên nhóm k ý. 
- Kiểm tra chữ ký tập thể của một nhóm đối tượng, được thực hiện tương tự 
như chữ ký do một đối tượng k ý tạo ra. 
Giả sử nhóm ký gồm N-thành viên: U = {Ui| i=1,2,...,N}. Các thành viên nhóm 
ký có khóa bí mật là: KS = {xi| i=1,2,...,N} và các khóa công khai tương ứng là: KP 
= {yi| i=1,2,...,N}. Còn CA có cặp khóa bí mật/công khai tương ứng là: {xca, yca}. 
2.3.1. Thuật toán hình thành tham số và khóa của CA 
Thuật toán 2.1: Hình thành tham số hệ thống và khóa của CA. 
Input: lp, lq – độ dài (tính theo bit) của số nguyên tố p, q. 
Output: n, t, xca, yca. 
[1]. Chọn 1 cặp số p, q nguyên tố với: len(p) = lp, len(q)= lq sao cho bài 
toán phân tích số trên Zn =p.q là khó giải. 
[2]. Tính: qpn  và: )1()1()(  qpn 
[3]. Chọn t thỏa mãn: 1),gcd( nt 
[4]. Chọn khóa công khai yca trong khoảng (1, φ(n)) và gcd (yca , φ(n)) = 1 
[5]. Tính khóa bí mật xca theo:   )(mod1 nyx caca 

 
[6]. Chọn hash function H:   hZ

1,0 , với: h < n 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 47
2.3.2. Thuật toán hình thành khóa của các đối tượng k ý 
Thuật toán 2.2: Hình thành khóa của U = {Ui| i=1,2,.,N}. 
Input: n, t, KS = {xi| i = 1,2,,N}. 
Output: KP = {yi| i = 1, 2,..,N}. 
[1]. for i = 1 to N do 
 [1.1].   nxy tii mod

 
 [1.2]. 
ip yiK ][ 
[2]. return KP 
2.3.3. Thuật toán hình thành chữ k ý 
Thuật toán 2.3: Hình thành chữ ký tập thể. 
Input: n, t, M, KS = {xi| i = 1, 2,..,N}, KP = {yi| i = 1, 2,..,N}. 
Output: (E,S) – chữ k ý của U lên M. 
[1]. for i = 1 to N do 
 [1.1]. )||( MxHk ii  
 [1.2].   nkR tii mod 
 [1.3]. send Ri to CA 
[2]. R ← 1; for i = 1 to N do 
 nRRR i mod 
[3]. )||( RMHE  , send E to {U1, U2,...., Ui,..., UN}; 
[4]. for i = 1 to N do 
 [4.1].    nxkS Eiii mod 
 [4.2]. send Si to CA 
[5]. Su ← 1; for i = 1 to N do 
 [5.1]. if (     nysr Ei
t
ii mod ) then {return (0,0)} 
 [5.2].   nSSS iuu mod 
[6].   nSS caxu mod 
[7]. return (E,S) 
Chú thích: 
+ Các bước [1], [4] được thực hiện bởi các đối tượng ký. 
+ Các bước [2], [3], [5], [6] và [7] được thực hiện bởi CA. 
 2.3.4. Thuật toán kiểm tra chữ k ý 
Thuật toán 2.4: Kiểm tra chữ ký tập thể 
Input: n, t, yca, KP = {yi| i =1,2,..,N}, M, (E,S). 
Output: (E,S) = true / false. 
[1]. if ( E = 0 or S = 0) then {return false} 
[2]. y ← 1; for i = 1 to N do 
 pyyy i mod 
[3]. nSu cay mod 
[3].   nyuv Et mod 
[4]. )||( vMHE  
[5]. if ( EE  ) then {return true} 
 else {return false} 
Công nghệ thông tin 
P. V. Hiệp, V. S. Hà, L. H. Dũng, “Một lược đồ chữ ký tập thể  khai căn trên Zn.” 48 
2.3.5. Tính đúng đắn của lược đồ chữ k ý tập thể 
Với các tham số và khóa được hình thành bởi Thuật toán 2.1 và 2.2, chữ k ý tập 
thể (E,S) được sinh bởi Thuật toán 2.3 và giá trị E được tạo bởi Thuật toán 2.4 thì 
điều cần chứng minh ở đây là EE  . 
Thật vậy, theo các Thuật toán 2.1, 2.2 và 2.3 ta có: 
nyy
N
i
i mod
1


 , nRR
N
i
i mod và: nSS
N
i
iu mod 
Nên: 
    
 
.
1
mod mod mod
mod mod
ca
ca ca
ca ca
yy x
u
N
x y
u u i
i
u S n S n n
S n S S n

 
  
Do đó: 
     
     
   
       
   RnnRnnk
nknxxk
nnxnxnk
nnnxnnxk
nnynSnySnyuv
N
i
i
N
i
t
i
N
i
t
i
N
i
N
i
Et
i
Et
i
N
i
t
i
EN
i
t
i
tN
i
E
i
tN
i
i
EN
i
t
i
tN
i
E
ii
EN
i
i
tN
i
i
Et
u
Et




























































 




 









modmodmodmod
modmod
modmodmodmod
modmodmodmodmod
modmodmodmodmod
11
11 1
..
1
111
11
11
Từ đây suy ra điều cần chứng minh: ERMHvMHE  )||()||( 
2.3.6. Tính an toàn của lược đồ chữ k ý tập thể 
Mức độ an toàn của lược đồ chữ k ý tập thể ở đây được thiết lập dựa trên mức độ 
an toàn của lược đồ cơ sở đã đề xuất ở mục 2.1. Do vậy, về cơ bản mức độ an toàn 
của nó cũng được quyết định bởi mức độ khó của bài toán IFP(n) và RSAP(n,e). Tuy 
nhiên, thuật toán hình thành chữ ký ở lược đồ ký tập thể có điểm khác cơ bản với 
lược đồ cơ sở đó là thành phần R và Su được tạo ra từ nhiều cặp giá trị (Ri, Si) của 
các thành viên nhóm ký, mà không phải từ 1 cặp giá trị (R,S) duy nhất như lược đồ 
cơ sở. Nói cách khác, chữ ký tập thể ở đây được tạo ra từ nhiều chữ ký cá nhân của 
các thành viên, vì thế tấn công giả mạo chữ ký cá nhân của các đối tượng ký trong 
thủ tục hình thành chữ ký tập thể sẽ là một nguy cơ mất an toàn tiềm ẩn đối với 
lược đồ chữ ký tập thể mới đề xuất. Vấn đề này hoàn toàn có thể giải quyết bằng 
việc CA xác thực chữ ký cá nhân của các thành viên nhóm ký ở bước [5.1] trong 
Thuật toán 2.3. Song đây chỉ là một trong các nguy cơ tấn công giả mạo đối với 
lược đồ mới đề xuất, mà quá trình phát triển tiếp theo và ứng dụng vào thực tế sẽ 
cần phải được tiếp tục phát hiện và giải quyết. 
3. KẾT LUẬN 
Bài báo đề xuất một lược đồ chữ k ý số tập thể có thể áp dụng cho đối tượng 
là các cơ quan, đơn vị, doanh nghiệp,... nhằm đảm bảo cho việc chứng thực các 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 49
thông điệp dữ liệu trong các thủ tục hành chính điện tử hoàn toàn phù hợp với 
các thủ tục hành chính trong thực tế xã hội. Với lược đồ mới đề xuất, các thông 
điệp dữ liệu điện tử sẽ được chứng thực về nguồn gốc và tính toàn vẹn ở hai 
cấp độ khác nhau: thực thể tạo ra thông điệp dữ liệu cần chứng thực và tổ chức 
mà thực thể tạo ra nó là một thành viên hay bộ phận của tổ chức này. Lược đồ 
mới đề xuất ở đây được phát triển từ một dạng lược đồ chữ ký mới xây dựng 
dựa trên tính khó của việc giải hai bài toán phân tích số và khai căn trên Zn. Vì 
thế, tính an toàn của lược đồ về khía cạnh tấn công giả mạo là một vấn đề cần 
được chú ý nghiên cứu trong quá trình phát triển và ứng dụng tiếp theo. 
TÀI LIỆU THAM KHẢO 
[1]. Phạm Văn Hiệp, Lưu Hồng Dũng, “Chữ ký số - Mô hình ứng dụng và thuật 
toán”, Hội nghị Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng CNTT 
(FAIR 11), Hà Nội 9/8/2018. 
[2]. Adams C., Understanding Public Key Infrastructures, New Riders Publishing, 
Indianapolis, 1999. 
[3]. Rivest R., Shamir A., Adleman L. (1978), “A Method for Obtaining Digital 
Signatures and Public Key Cryptosystems”, Communications of the ACM, Vol. 
21, No. 2, pp. 120 – 126. 
[4]. National Institute of Standards and Technology, NIST FIPS PUB 186 – 4. 
Digital Signature Standard, U.S. Department of Commerce, 2013. 
[5]. National Institute of Standards and Technology, NIST FIPS PUB 180 – 4. 
Secure Hash Standard (SHS), U.S. Department of Commerce, 2015. 
ABSTRACT 
A COLLECTIVE DIGITAL SIGNATURE SCHEMES BASED 
ON THE DIFFICULTY OF INTEGER FACTORIZATION 
AND FINDING ROOT PROBLEMS ON THE Zn 
This paper proposes a collective digital signature schemes application for 
government agencies, administrative units, enterprises, etc., where data messages 
need to be authenticated. Origin and integrity at two levels: entity sign and 
organization (agency, unit, ...) that the entity signing is its member. At the same 
time, the paper also suggests digital signature schemes based on this application 
model. The proposed new scheme was developed from a digital signature scheme 
formulated based on the difficulty of integer factorization and finding root problems 
based on ring Zn. 
Keywords: Digital Signature; Collective Signature; Digital Signature Schemes; Collective Digital Signature 
Schemes. 
Nhận bài ngày 11 tháng 12 năm 2018 
Hoàn thiện ngày 12 tháng 3 năm 2019 
Chấp nhận đăng ngày 25 tháng 3 năm 2019 
Địa chỉ: 1 ĐH Công Nghiệp Hà Nội; 
 2 Viện KHCNQS; 
 3 Học viện Kỹ thuật Quân sự; 
 4 Trung tâm tin học, Trường Đại học Nội vụ Hà Nội. 
 * Email: hieppv@haui.edu.vn.