Sơ đồ chữ ký đồng thời an toàn dựa trên mã BCH ghép tầng

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, 11 - 2018 55
SƠ ĐỒ CHỮ KÝ ĐỒNG THỜI AN TOÀN DỰA TRÊN 
 MÃ BCH GHÉP TẦNG 
Phạm Khắc Hoan1*, Nguyễn Văn Hải1, Vũ Sơn Hà2 
 Tóm tắt: Chữ ký đồng thời là sơ đồ chữ ký có tính chất đặc biệt cho phép trao 
đổi thông tin giữa hai thực thể một cách ngang hàng mà vẫn đảm bảo tính riêng tư 
của mỗi bên. Bài báo đề xuất một sơ đồ chữ ký số kháng lượng tử dựa trên mã BCH 
ghép tầng cho phép rút gọn kích thước khóa và đảm bảo các yêu cầu an ninh của 
chữ ký đồng thời. 
Từ khóa: Chữ ký dựa trên mã hóa; Chữ ký đồng thời; Mã BCH ghép tầng. 
1. ĐẶT VẤN ĐỀ 
Các sơ đồ chữ ký số hiện nay chủ yếu sử dụng hệ mật khóa công khai dựa 
trên bài toán phân tích thừa số hay logarit rời rạc và có thể bị phá vỡ bởi máy tính 
lượng tử nhờ sử dụng thuật toán của Shor [1]. Trước những nguy cơ đó, cần xây 
dựng các hệ mật khóa công khai mới có thể chống lại các cuộc tấn công của máy 
tính lượng tử và máy tính cổ điển, được gọi là hệ mật kháng lượng tử (post-
quantum cryptosystem). Mật mã dựa trên mã hóa (Code-based cryptography) là 
một trong những hướng nghiên cứu tiềm năng cho mật mã kháng lượng tử. Hệ mật 
này có ưu điểm cơ bản so với các hệ mật mã khóa công khai khác là quá trình thực 
hiện mã hóa và giải mã nhanh hơn và với việc tăng kích thước khóa giúp tăng tính 
bảo mật một cách nhanh chóng. Tuy nhiên điểm yếu cơ bản của hệ mật dựa trên 
mã hóa là kích thước ma trận khóa công khai và khóa bí mật khá lớn [2]. 
Trong các ứng dụng thực tế xuất hiện yêu cầu chữ ký có tính chất đặc biệt 
như chữ ký tập thể, chữ ký mù, chữ ký đồng thời...Trong sơ đồ chữ ký số đồng 
thời (concurrent signature) người ký gốc và người ký kết hợp có thể trao đổi thông 
tin mà không cần thực thể tin cậy thứ ba. Ví dụ khi thực hiện bỏ thầu điện tử B có 
hợp đồng và A, C muốn đề xuất giá bỏ thầu, khi đó A gửi giá đề xuất của mình kết 
hợp với một khóa chủ bí mật, B gửi một sơ đồ chữ ký đồng thời khác cho A để xác 
nhận rằng B chấp nhận đề xuất của A. B không thể cung cấp cho C giá bỏ thầu của 
A vì chữ ký của A là mờ và C không thể nhận biết được A hay B đề xuất giá thầu. 
Một số sơ đồ chữ ký đồng thời đã đề xuất dựa trên bài toán khó của lý thuyết số, 
tuy nhiên có rất ít sơ đồ chữ ký đồng thời có khả năng chống lại tấn công từ máy 
tính lượng tử [3, 4]. Mặt khác sơ đồ chữ ký đồng thời dựa trên mã hóa vẫn chưa 
đạt được thành tựu đáng kể do vẫn có nhược điểm cơ bản là thuật toán ký phải lặp 
lại quá trình giải mã khoảng t! lần cho đến khi giải mã thành công [5]. 
Bài báo đề xuất một sơ đồ chữ ký đồng thời dựa trên mã BCH ghép tầng đảm 
bảo an toàn với các tấn công giải mã và tấn công cấu trúc trên máy tính cổ điển và 
máy tính lượng tử, giảm kích thước khóa đồng thời giảm độ phức tạp của quá trình 
ký và xác nhận. 
Công nghệ thông tin 
P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời  dựa trên mã BCH ghép tầng.” 56 
Phần còn lại của bài báo được tổ chức như sau. Trong phần 2 xem xét hệ mật 
dựa trên mã BCH ghép tầng, phần 3 đề xuất phương pháp xây dựng sơ đồ chữ ký 
đồng thời dựa trên hệ mật mới, trong phần 4 tiến hành phân tích, đánh giá độ an 
toàn và độ phức tạp của sơ đồ chữ ký được đề xuất. 
2. HỆ MẬT DỰA TRÊN MÃ BCH GHÉP TẦNG 
Giả sử kết hợp các mã thành phần, ma trận kiểm tra của mã được sử dụng 
trong hệ mật có dạng [6]: 
.
0
X Y
H
Z
 (1) 
Trong đó: X là ma trận kiểm tra của mã BCH và các biến thể với khoảng 
cách mã dx (sau đây để thuận tiện ta gọi là mã X), Y là ma trận kiểm tra của một 
mã BCH mở rộng với khoảng cách mã dy, Z là ma trận kiểm tra của mã ghép tầng 
có ghép xen (interleaved concatenated code) được cấu trúc từ các mã thành phần là 
các mã BCH, BCH mở rộng C1, C2 với ma trận hoán vị П. Kích thước của các mã 
thành phần được chọn sao cho ny = nz, rx = ry (có thể sử dụng độn bit để đảm bảo 
điều kiện này). Ma trận kiểm tra của mã BCH ghép tầng có ghép xen có dạng: 
1 2
1 2
. .
. .. .
. .
H H
Z
H H
 
(2) 
Số lượng ma trận 2H trên đường chéo chính bằng 1n , còn số ma trận 1H 
trên đường chéo chính được chọn bằng 
2r , các phần tử còn lại bằng 0. Vì vậy các 
tham số của mã Z thỏa mãn: 
1 2.Zn n n , 1 2.zr r r . Mã kết hợp có chiều dài 
x zn n n ; số bit kiểm tra x zr r r . Ma trận Π kích thước 1 2 1 2n r n r . 
Hệ mật dựa trên mã BCH ghép tầng gồm các thủ tục sau. 
Tạo khóa 
Chọn ma trận các khả nghịch Q ((N –K) (N –K)), ma trận P(N N). 
Trong đó ma trận P có dạng 
...
,
...
x
z
P
P
P
 với xP , zP là các ma trận 
hoán vị cấp ,x zn n tương ứng. 
Xây dựng ma trận kiểm tra H của mã ghép tầng như mô tả trên. 
Tính H’ = Q.H.P. 
 Khóa công khai là (H’, t). 
 Khóa bí mật (Q, P, X, Y, П, H1, H2). 
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, 11 - 2018 57
Mã hóa: 
Để mã hóa bản rõ cho trước, biểu diễn bản tin x zM M M sao cho bản tin 
xM có độ dài xn , trọng số không quá xt ; bản tin zM có độ dài zn , trọng 
số không quá zt sử dụng thuật toán bổ sung, người gửi tính: c = H’.m
T. 
Giải mã: 
Để giải mã bản mã c, sử dụng thuật toán giải mã Dg dựa trên phương pháp 
chuẩn syndrome giải mã BCH [6, 7]. 
Tính 1' Tc Q c HPm ; 
Tìm m’=P.mT từ c’ khi áp dụng thuật toán giải mã Dg. 
Tìm: 
1.Tm P m 
3. SƠ ĐỒ CHỮ KÝ ĐỒNG THỜI DỰA TRÊN MÃ BCH GHÉP TẦNG 
Trong phần tiếp theo, đề xuất phương pháp tạo chữ ký đồng thời dựa trên hệ 
mật sử dụng mã BCH ghép tầng. 
*Setup: 
- Chọn hai mã BCH ghép tầng có ghép xen C (N, K, t), ma trận kiểm tra của 
mã C xác định theo công thức (2) là ,A BH H . 
- Hàm hàm băm đầu ra có N-K bit g: {0,1}*→ {0,1}N-K. 
- Chọn h là hàm tạo chuỗi giả ngẫu nhiên N bit từ N – K bit. 
- Khóa công khai Para ={N, K, ,A BH H , t, g} 
* KGen: 
- Chọn ngẫu nhiên vector nhị phân κ độ dài N trọng số không quá t, là khóa 
chủ bí mật (keystone) 
Khóa chủ cố định (keystone fix): 
'( . ).TAx h H  
*ASign 
 Tạo chữ ký mờ: 
- Người ký A chọn số ngẫu nhiên r dài N – K bit, với bản tin cần ký M, tính 
( , , , ) ;TA B Bg r M H H H x 
1( ). .A Ay Dec Q P 
 (3) 
Nếu không giải mã được thì chọn r khác và lặp lại thủ tục ký. Chữ ký của M 
là θ = (r, x, y). 
*AVer 
Xác nhận chữ ký 
Cho Para, AH , BH chữ ký θ là hợp lệ khi và chỉ khi 
' ( , , , )T TA B A BH y H x g r M H H với trọng số của x và y không quá t. 
Người ký phối hợp B nhận được chữ ký θ = (r, x, y) là hợp lệ hay không nhờ 
thuật toán AVer. 
Công nghệ thông tin 
P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời  dựa trên mã BCH ghép tầng.” 58 
*Xác nhận chữ ký đồng thời 
Cho chữ ký θ = (r, x, y) và khóa chủ κ chữ ký đồng thời hợp lệ 
khi '( . ) ,TAh H x 
' ( , , , )T TA B A BH y H x g r M H H 
với trọng số của x và y không quá t. 
4. PHÂN TÍCH AN NINH CỦA SƠ ĐỒ CHỮ KÝ ĐỒNG THỜI ĐÃ ĐỀ XUẤT 
4.1. Tính đúng đắn của sơ đồ chữ ký 
Tính đúng đắn của sơ đồ ký được đảm bảo vì 
' 1 '
1 '
1 '
' '
. . . ( ).
. . . . ( )
.
( , , , )
( , , , )
T
T T T
A B A A A A A B
T
T T
A A A A A B
T
A A B
T T
A B B B
A B
H y H x Q H P Dec Q P H x
Q H P P Dec Q H x
Q Q H x
g r M H H H x H x
g r M H H
Nếu θ = (r, x, y) là chữ ký hợp lệ của thông điệp M thì quan hệ sau thỏa 
mãn: ' ( , , , )T TA B A BH y H x g r M H H . 
Nếu chữ ký được tạo ra bởi người ký B tính đúng đắn cũng đảm bảo một 
cách hoàn toàn tương tự. 
4.2. Phân tích các yêu cầu bảo mật của sơ đồ chữ ký đồng thời 
Các yêu cầu bảo mật cơ bản của chữ ký đồng thời gồm: không thể giả mạo, 
tính làm mờ và tính công bằng. 
Không thể giả mạo chữ ký: Không ai có thể tạo ra khóa chủ cố định hợp lệ 
trừ người ký ban đầu do không biết khóa chủ bí mật κ và khóa riêng của A là ma 
trận HA theo bài toán giải mã syndome. Khi chọn N-K đủ lớn không thể tạo ra chữ 
ký giả mạo θ’. 
Tính chất mờ của chữ ký: Rõ ràng với thực thể C nào đó với chữ ký θ = (r, x, 
y) không thể xác định được chữ ký do A hay B tạo ra. Với các tham số 
, , ,A Br M H H đã cho trước, người ký i chọn ri ngẫu nhiên thuộc [1, 2
N-K] tạo ra chữ 
ký (ri, x, yi). Xác suất để người ký i tạo ra chữ ký mờ bằng 2
K-N, người ký j cũng có 
cùng xác suất như vậy. Vì vậy xác suất mà C phán đoán chữ ký được tạo ra bởi 
người ký i hoàn toàn giống như xác suất chữ ký tạo ra bởi người ký j, nghĩa là C 
phán đoán người ký thực của chữ ký mờ với xác suất bằng 1/2. 
Tính công bằng của chữ ký: 
Trước hết chỉ người có khóa chủ bí mật κ mới có thể tạo ra chữ ký. Giả sử 
địch thủ C tạo ra chữ ký θ* = (r*, x*, y*) của bản tin M* với khóa chủ κ*. Theo thuật 
toán xác nhận chữ ký Ver điều đó tương đương với '( . ).TAx h H 
 Xác suất địch 
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, 11 - 2018 59
thủ C có thể tạo ra cặp (κ*, x*) sao cho '( . )TAh H x
 không quá 2K-N là có thể bỏ 
qua khi N- K đủ lớn. 
Mặt khác mỗi chữ ký mờ được tạo ra bởi cùng khóa chủ cố định x sẽ được 
kết nối lại để tạo ra chỉ một chữ ký đồng thời θ = (r, x, y). Giả sử C tạo ra chữ ký θ’ 
= (r’, x*, y’) là một chữ ký hợp lệ khác của bản tin M’ với khóa công khai ,A BH H . 
Khi đó θ’ thỏa mãn thuật toán Aver trong khi θ’ không thỏa mãn thuật toán xác 
nhận Ver với đầu vào (κ*, θ*). Vì θ* là chữ ký hợp lệ nên nó phải thỏa mãn thuật 
toán Aver, theo thuật toán này rút ra 
'( . ).TAx h H 
Điều này mâu thuẫn với giả thiết θ’ ≠ θ*. 
4.3. Đánh giá chất lượng của sơ đồ chữ ký đã đề xuất 
An ninh của hệ mật và sơ đồ chữ ký đã đề xuất dựa trên bài toán giải mã theo 
syndrome. Bài toán giải mã syndrome về bản chất là tìm vector lỗi theo syndrome 
khi cấu trúc của ma trận kiểm tra đã được làm ngẫu nhiên không theo cấu trúc đại 
số của mã. Bài toán này đã được chứng minh là NP-đầy đủ. Các tấn công phổ biến 
và hiệu quả nhất vào các hệ mật mã dựa trên mã hóa là tấn công giải mã ISD và tấn 
công cấu trúc [8]. Tấn công vét cạn không hiệu quả bởi vì từ khóa công khai là ma 
trận H’để tìm được khóa bí mật là ma trận H cần duyệt tất cả các ma trận hoán vị P 
và ma trận Q. Số lượng ma trận P có thể có là ! !x zn n , số lượng ma trận Q có thể 
có là 22(N-K), với xn ≥ 1000, N-K≥160, tấn công vét cạn phức tạp hơn nhiều lần so 
với tấn công giải mã ISD. 
Xét ảnh hưởng của thuật toán lượng tử đến hệ mật sử dụng mã BCH ghép 
tầng. Khi sử dụng giải mã ISD lượng tử với thuật toán Grover, độ phức tạp giải mã 
được xác định theo công thức sau [11]. 
0,29
K
N
Q decode inv itK
N t
C
WF c c c
C 
 (4) 
Trong đó : 
2
2log ( )decodec N N : Chi phí giải mã các qubit đầu vào. 
3 21 ( )
2
invc K N K K : Chi phí tính toán thực hiện việc nghịch đảo các cột 
của ma trận. 
itc K : Số lượng các phép toán bit cần thiết để thực hiện một lần lặp của 
thuật toán giải mã. 
Để minh họa các tham số của hệ mật dựa trên mã BCH ghép tầng được chọn 
như sau: 
Công nghệ thông tin 
P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời  dựa trên mã BCH ghép tầng.” 60 
Mã Z: 
1(16,7,8)C , 2 (128,106,8)C , 1 2. 9.22 198zr r r ; X mã BCH 
 127,85,13 , Y mã BCH mở rộng 2048,2003,10 , 42, 45x yr r . Để phối hợp 
kích thước, ma trận X được bổ sung thêm ba hàng gồm toàn bit 0. Do đó tham số 
của mã ghép tầng 2175x yN n n , 243y zr r r , 1932,K 30t độ phức 
tạp tấn công giải mã từ máy tính thông thường vào hệ mật 992 . Khi sử dụng thuật 
toán giải mã ISD kết hợp với thuật toán Grover trên máy tính lượng tử theo công 
thức (4) độ phức tạp tấn công ISD từ máy tính lượng tử đạt 281,6. 
Dưới đây đánh giá độ an toàn của sơ đồ chữ ký đồng thời đã đề xuất. Trong 
sơ đồ này cả 2 người ký đều chọn bộ tham số của mã ghép tầng như trên nhưng các 
mã thành phần có ma trận kiểm tra khác nhau (có thể đạt được bằng thay đổi đa 
thức sinh hoặc thay đổi trường hữu hạn). 
Hàm một chiều g là hàm băm, ví dụ SHA-3. 
( , , , ) ( )A B A Bg r M H H g r M H H , trong đó các ma trận ,A BH H được biểu 
diễn việc ghép bởi các vector hàng của chúng. 
Giả sử hàm băm được dùng là SHA-3 có độ dài giá trị băm là 256 bit. Để 
đảm bảo tương thích với kích thước ma trận, giá trị băm được cắt bỏ đi 13 bit, tức 
là một cách hình thức hàm băm trong sơ đồ trên có độ dài giá trị băm 243 bit. 
Mặc dù chưa thể đánh giá hết ảnh hưởng của tấn công từ máy tính lượng tử 
đến hàm băm, có thể tìm được giới hạn của độ dài giá trị băm. Với tấn công ngày 
sinh nhật tổng quát trên máy tính thông thường, để tìm được một xung đột, thời 
gian yêu cầu xấp xỉ /22r . Với máy tính lượng tử có thể tìm được một xung đột trong 
thời gian /32 .r Với sơ đồ chữ ký số dựa trên mã BCH ghép tầng được đề xuất đảm 
bảo mức an ninh 81 bit với tấn công vào hàm băm từ máy tính lượng tử. 
Chú ý rằng thuật toán giải mã hai giai đoạn cho phép giải mã được mọi cấu 
hình lỗi trong khả năng sửa, nên ở bước tạo chữ ký chỉ ký lại khi mã X không giải 
mã được, tỷ lệ các vector lỗi trong khả năng sửa lỗi của mã X khoảng 1/6!. 
Chữ ký gồm 3 thành phần x, y và r, trong đó x, y là các vector dài N bit có trọng 
số không quá t nên mỗi thành phần này cần 2log
t
NC 223 bit, còn r có thể mã hóa 
bằng N – K bit 
Trong bảng 1 trình bày kết quả so sánh chữ ký được đề xuất với sơ đồ được 
đề xuất trong [10]. Trong sơ đồ chữ ký đồng thời sử dụng mã Goppa để đảm bảo 
an ninh của hệ mật chống tấn công ngày sinh nhật tổng quát cần chọn N = 222, t = 9 
[8]. Như vậy với cùng mức an ninh số lần ký lặp lại giảm 576 lần, sơ đồ đề xuất 
cho phép rút gọn kích thước khóa 1470 lần. Độ dài chữ ký tăng khoảng 24% do số 
lỗi sửa được tăng lên, số cấu hình lỗi có thể có tăng lên. Sơ đồ đề xuất tạo ra chữ 
ký đồng thời an toàn với tấn công từ máy tính thông thường và máy tính lượng tử. 
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, 11 - 2018 61
Bảng 1. So sánh sơ đồ đề xuất với sơ đồ chữ ký đồng thời dựa trên mã Goppa. 
 Số lần ký 
lặp lại 
Kích thước 
khóa (KB) 
Độ dài chữ ký (bit) 
Sơ đồ chữ ký 
dựa trên mã 
Goppa 
9! 101376 557 
Sơ đồ đề xuất 6! 69 689 
5. KẾT LUẬN 
Bài báo đề xuất sơ đồ chữ ký đồng thời sử dụng cấu trúc kết hợp mã BCH 
mở rộng với mã BCH ghép tầng. Sơ đồ chữ ký được đề xuất đảm bảo các yêu cầu 
bảo mật đặc trưng của chữ ký đồng thời và an toàn với các phương pháp tấn công 
giải mã, tấn công cấu trúc mới được nghiên cứu gần đây. Mặt khác sơ đồ chữ ký 
đồng thời dựa trên mã BCH ghép tầng cho phép giảm kích thước khóa và độ 
phức tạp nhiều lần do chiều dài mã giảm đi khoảng 2000 lần nên thời gian ký và 
xác nhận đều giảm đi đáng kể và áp dụng giải mã hai giai đoạn cho mã BCH 
ghép tầng. 
TÀI LIỆU THAM KHẢO 
[1]. P.W.Shor. Polynomial-time algorithms for prime factorization and discrete 
logarithms on a quantum computer. SIAM Journal on Computing, 26:1484–
1509, 1997. 
[2]. McEliece, R.J. A Public-Key Cryptosystem Based on Algebraic Coding 
Theory, The Deep Space Network Progress Report, DSN PR 42–44, pp. 114-
116, 1978. 
[3]. D. J. Bernstein, J. Buchmann, E. Dahmen. Post-quantum cryptography, 
Springer-Verlag Berlin Heidelberg, 2009. 
[4]. Z. Huang, K. Chen, X. Len, R. Huang. Analysis and improvements of two 
identity based perfect concurrent signature schemes. Informatica, Vol. 18, 
No. 3, pp 375-394, 2007. 
[5]. K. Morozov, P. Roy, R. Steinwandt, R. Xu. On the sceurity of Courtois-
Finiasz-Senderier signature. Open math , pp 161-167, 2018. 
[6]. Pham Khac Hoan, Le Van Thai, Pham Duy Trung: A secure McEliece 
cryptosystem’s variant based on interleaved concatenated BCH codes, 2016 
International Conference on Advanced Technologies for Communications 
(ATC 2016), pp 513-518. 
[7]. Phạm Khắc Hoan, Lê Văn Thái, Nguyễn Anh Tuấn. Xây dựng sơ đồ chữ ký số 
dựa trên hệ mật sử dụng mã BCH ghép tầng. Hội thảo quốc gia REV-EICT, 
2016. 
Công nghệ thông tin 
P. K. Hoan, N. V. Hải, V. S. Hà, “Sơ đồ chữ ký đồng thời  dựa trên mã BCH ghép tầng.” 62 
[8]. M. Finiasz, N. Sendrier. Security Bounds for the Design of Code-Based 
Cryptosystems, Advances in Cryptology ASIACRYPT 2009, Volume 5912 of 
the series Lecture Notes in Computer Science pp 88-105. 
[9]. Becker, A., Joux, A., May, A., and Meurer, A. Decoding random binary 
linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding. In 
Advances in Cryptology - EUROCRYPT 2012, Lecture Notes in Comput. 
Sci., Springer, 2012. 
[10]. M. R. Asaar, M. Salmasizadeh, M. A. Aref. A Provably secure code-based 
concurrent signature scheme. 
[11]. Vries S. D. Achieving 128-bit security against quantum attacks in OpenVPN, 
Master’s thesis, August 2016. 
ABSTRACT 
A SECURE CONCURRENT SIGNATURE 
BASED ON CONCATENATED BCH CODES 
A concurrent signature scheme allows the exchange of information 
between two entities fairly while ensuring the privacy. In this paper, a post-
quantum signature scheme based on concatenated BCH codes is proposed. 
For the proposed scheme, the key size is reduced dramatically while the 
security requirements of the concurrent signature are complied with. 
Keywords: Code-based signature; Concurrent signature; Concatenated BCH codes. 
Nhận bài ngày 29 tháng 06 năm 2018 
Hoàn thiện ngày 09 tháng 10 năm 2018 
Chấp nhận đăng ngày 05 tháng 11 năm 2018 
Địa chỉ: 1Khoa VTĐT - Học viện KTQS; 
2Viện CNTT - Viện KHCN quân sự. 
*Email: hoanpk2012@gmail.com.