Nghiên cứu ứng dụng mã BCH xây dựng hệ mật

SCIENCE TECHNOLOGY 
Số 51.2019 ● Tạp chí KHOA HỌC & CÔNG NGHỆ 3
NGHIÊN CỨU ỨNG DỤNG MÃ BCH XÂY DỰNG HỆ MẬT 
A SECURE NIEDREITER CRYPTOSYSTEM’S VARIANT BASE ON BCH CODES 
Lê Văn Thái 
TÓM TẮT 
Nội dung bài báo đề xuất giải pháp sử dụng ghép các mã BCH thành phần 
nhằm giảm kích thước khóa của hệ mật mã dựa trên mã. Để mở rộng khả năng sửa 
lỗi của mã BCH và ứng dụng vào xây dựng hệ mật, bài báo sử dụng phương pháp 
chuẩn syndrome giải mã mã BCH. Hệ mật đề xuất có kích thước khóa công khai 
giảm 5,7 lần so với hệ mật Niederreiter trong đề xuất gốc ở cùng mức an ninh và 
đảm bảo an toàn chống lại các cuộc tấn công cấu trúc và tấn công giải mã. 
Từ khóa: Hệ mật McEliece, hệ mật Niederreiter, chuẩn syndrome, mã BCH,
hệ mật dựa trên mã. 
ABSTRACT 
In this paper, we propose a solution to merge BCH codes into chained BCH 
codes and applications to build the cryptosystem. The proposed method reduced 
the key size by 5.7 times compared to the Niederreiter cryptosystem at the same 
level of security. The proposed cryptosystem guarantees security against 
structural attacks and decryption attacks. At the same time, the article also 
presented the norm-syndrome based decoding method of BCH code. This 
method has increased the ratio of the number of syndromes that can be decoded 
out of the total number of possible syndromes, extending the application range 
of the BCH code. 
Keywords: McEliece Cryptosystem, Niderrreiter Cryptosystem, Norm 
syndrome, BCH Codes, Code based cryptosystem. 
Trường Đại học Công nghiệp Hà Nội 
Email: thailv@haui.edu.vn 
Ngày nhận bài: 15/01/2019 
Ngày nhận bài sửa sau phản biện: 03/4/2019 
Ngày chấp nhận đăng: 25/4/2019 
1. ĐẶT VẤN ĐỀ 
Hệ thống mã hóa khóa công khai hiện nay hầu hết dựa 
trên độ khó của các bài toán lý thuyết số như bài toán phân 
tích ra thừa số, bài toán logarit rời rạc trên trường hữu hạn. 
Kết quả nghiên cứu của Peter Shor năm 1994 và thuật toán 
tìm kiếm trên dữ liệu không có cấu trúc của Grover năm 
1996 đã cảnh báo các hệ mật khóa công khai RSA, 
ElGamal, sẽ không an toàn khi máy tính lượng tử với quy 
mô đủ lớn xây dựng thành công [1]. Hệ mật mã dựa trên 
mã McEliece được giới thiệu năm 1978 [2]. Đây là sơ đồ hệ 
mật đầu tiên sử dụng tính ngẫu nhiên trong mã hóa. An 
ninh của hệ mật này dựa trên độ khó của bài toán giải mã 
theo syndrome và đã được chứng minh là bài toán NP đầy 
đủ [3]. Đề xuất ban đầu sử dụng mã nhị phân Goppa và 
thuật toán giải mã Patterson. Ưu điểm của hệ mật này là 
tính bảo mật cao, thời gian thực hiện mã hoá và giải mã 
nhanh, yêu cầu thiết bị thực hiện đơn giản. Hơn nữa, hệ 
mật này được chứng minh là có khả năng chống lại sự tấn 
công lượng tử [4]. Tuy nhiên, hệ mật này chưa được áp 
dụng trong thực tế xuất phát từ nhược điểm cơ bản của nó 
là tỷ lệ mã hóa thấp, kích thước khóa khá lớn. 
Năm 1986, biến thể của hệ mật McEliece là hệ mật 
Niederreiter được đề xuất [5]. Hệ mật Niederreiter sử dụng 
ma trận kiểm tra H để làm khóa và sử dụng vector lỗi để 
giải mã. An ninh của hệ mật McEliece và hệ mật 
Niederreiter khi sử dụng mã nhị phân Goppa được chứng 
minh là hoàn toàn tương đương [6]. Ưu điểm của hệ mật 
Niederreiter là có khả năng áp dụng để xây dựng sơ đồ chữ 
ký số, ứng dụng trong thực tế [7]. 
Trong quá trình phát triển của hệ mật mã dựa trên mã. 
Đã có nhiều đề xuất thay thế mã Goppa trong hệ mật gốc 
bằng các mã khác nhằm giảm kích thước khóa. Năm 1994, 
Sidelnikov đã đề xuất sử dụng mã Reed-Muller áp dụng cho 
hệ mật Niederreiter. Năm 1996, Heeralal Janwa và Oscar 
Moreno đã đề xuất hệ mật sử dụng mã AG (algebraic-
geometric). Năm 2005, Berger và Loidreau đã đề xuất sử 
dụng mã quasi-cyclic alternant làm ẩn cấu trúc khóa mật. 
Những năm gần đây có nhiều đề xuất sử dụng các họ mã 
và phương pháp giải mã mới nhằm làm giảm kích thước 
khóa. Monico và cộng sự đề xuất sử dụng mã kiểm tra mật 
độ thấp (LDPC). Năm 2007, Baldi và cộng sự đề xuất một 
biến thể mới dựa trên mã quasi-cyclic (QC-LDPC). Năm 
2013, Misoczki và cộng sự đề xuất sử dụng mã kiểm tra mật 
độ trung bình (QC-MDPC). Năm 2016, Moufek đã đề xuất 
kết hợp mã QC-LDPC và QC-MDPC và sử dụng bộ tạo số giả 
ngẫu nhiên để tạo ma trận sinh. Tuy nhiên, các nghiên cứu 
mới về tấn công đã chỉ ra các đề xuất này không an toàn 
với tấn công cấu trúc [8 , 9 , 10]. 
Trong bài báo này, tác giả đề xuất sử dụng ghép các mã 
BCH thành chuỗi mã và áp dụng cho biến thể Niederreiter 
để xây dựng hệ mật. Sơ đồ hệ mật đề xuất cho phép giảm 
kích thước khóa, đả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. Đồng thời trong bài báo, tác giả cũng 
đề xuất phương pháp chuẩn syndrome giải mã mã BCH 
nhằm mở rộng khả năng sửa lỗi và phạm vi ứng dụng của 
mã BCH, cho phép ứng dụng mã BCH để xây dựng hệ mật 
mã dựa trên mã. 
Phần còn lại của bài báo được tổ chức như sau: trong 
phần 2, trình bày giải pháp nâng cao hiệu quả sửa lỗi của 
 CÔNG NGHỆ 
 Tạp chí KHOA HỌC & CÔNG NGHỆ ● Số 51.2019 4
KHOA HỌC
mã BCH sử dụng phương pháp chuẩn syndrome. Phần 3, 
đề xuất xây dựng hệ mật sử dụng mã ghép BCH. Phần này 
cũng giới thiệu về hệ mật McEliece và Niederreiter. Phần 4, 
đánh giá độ phức tạp và độ an toàn của hệ mật đề xuất. 
2. NÂNG CAO HIỆU QUẢ CỦA MÃ BCH SỬ DỤNG 
PHƯƠNG PHÁP CHUẨN SYNDROME 
Các hệ mật dựa trên mã sửa lỗi không thể áp dụng để 
mã hóa cho một bản tin bất kỳ. Bởi vì một syndrome ngẫu 
nhiên hầu như tương ứng với vector lỗi có trọng lượng lớn 
hơn khả năng sửa lỗi của mã. Do đó, để áp dụng mã BCH 
vào xây dựng hệ mật, nhiệm vụ đầu tiên là xây dựng 
phương pháp giải mã để nâng cao hiệu quả sửa lỗi của mã. 
Trong nội dung tiếp theo tác giả xây dựng phương pháp 
giải mã mã BCH theo chuẩn syndrome (Norm Syndrome). 
Khi phân hoạch các vector lỗi thành các lớp không giao 
nhau có chuẩn syndrome phân biệt cho phép mở rộng khả 
năng sửa lỗi của mã BCH. 
Tham số chuẩn syndrome được xây dựng dựa trên cấu 
trúc của mã BCH và các biến thể. Đặc điểm của chuẩn 
syndrome là tính bất biến với tác động của nhóm các dịch 
vòng. Syndrome của các nhóm khác nhau thì khác nhau. 
Khi sử dụng chuẩn syndrome để giải mã, có thể sửa được 
lỗi ngẫu nhiên và lỗi cụm. Vì khi chọn đa thức sinh thích 
hợp thì chuẩn syndrome của các vector lỗi ngẫu nhiên và 
một số cấu hình lỗi cụm độ dài nhỏ, lỗi cụm đồng pha là 
không trùng nhau. 
Giả thiết σ là phép thế dịch vòng, dưới tác động của σ, 
vector lỗi dịch phải một vị trí. Tập hợp tất cả các vector khác 
nhau đôi một i(e) với 0 i n-1 của vector lỗi e bất kỳ 
được gọi là -orbit của nó. Các phần tử của -orbit chuyển 
hóa lẫn nhau dưới tác động của phép dịch vòng. Mỗi 
-orbit có một vector sinh, tọa độ đầu tiên của vector này 
luôn khác 0. 
Ta có (e) = e với  là số tự nhiên 1  n. Với một 
vector lỗi e bất kỳ -orbit chứa k phần tử trong đó  = n 
hoặc  là ước của nó. Khi đó cấu trúc của -orbit có dạng: 
 ( ) , ( ),..., ( )λ 1σ e e e σ e σ e = = (1) 
Hai vector lỗi tùy ý e và e’ thì các -orbit , hoặc 
là trùng nhau hoặc không giao nhau. Do vậy dưới tác động 
của nhóm các phép dịch vòng không gian vector lỗi phân 
chia thành các lớp -orbit không giao nhau. 
Ma trận kiểm tra của mã BCH tổng quát với  = 2t + 1 có 
dạng [11]: 
 –, , , ....,
Tb 1 i b δ 2 ibiH β β 0 i nβ 1+ + = (2) 
Giả sử hạng của ma trận kiểm tra là m(-1), tức là các 
hàng của ma trận H là độc lập tuyến tính. Khi đó, syndrome 
của vector lỗi e gồm -1 thành phần trong trường GF(2m) có 
dạng S(e) = (s1,s2,,s-1). 
Cho e là vector lỗi tùy ý, với mã BCH có ma trận kiểm tra 
(2) ta có: 
( ( )) ( , ,..., ).b b 1 b δ 21 2 δ 1S σ e β s β s β s
+ + 
 = (3) 
Như vậy, chuẩn syndrome là vector N(S) có 2 1C tọa độ 
Nij(1 ≤ i ≤ j ≤ -1), được xác định theo công thức [12]: 
( )/ ( )/
/ , gcd( , );
 ; ;
 .
ij ijb i 1 h b j 1 h
ij j i i ij
ij j i
ij i j
N s s if s 0 h b i 1 b j 1
N if s 0 s 0
N if s s 0
+ + 
= = + + 
= =
= = = 
(4) 
Tính chất của chuẩn syndrome là tính bất biến của nó 
với phép thế dịch vòng. Từ công thức (3, 4) ta có, đối với 
mọi mã vector lỗi e của mã BCH luôn thỏa mãn: 
( ( ( ))) ( ( ))N s σ e N s e= (5) 
Bản chất của phương pháp giải mã theo chuẩn 
syndrome là các phần tử của -orbit chuyển hóa lẫn nhau 
dưới tác động của phép dịch vòng. Chuẩn syndrome sẽ chỉ 
ra -orbit mà vector lỗi nằm trong đó. Do đó xác định được 
vector sinh e0 tương ứng, so sánh syndrome nhận được S và 
S(e0) ta xác định được lượng dịch vòng để biến đổi e0 thành 
e, do đó sẽ tìm được chính xác vector lỗi [12]. 
Các bước thực hiện giải mã theo phương pháp chuẩn 
syndrome: 
+ Tính syndrome S(e) = (s1,s2,,st) với si là phần tử của 
trường Galoa GF(2m). 
+ Tính bậc của chuẩn syndrome N: Tính degsj, degsi là 
bậc thành phần sj, si của syndrome S(e) = (s1,s2,,si,sj,,st) 
với 1 i j t . Chuẩn syndrome của syndrome S(e) tính 
theo công thức (4), xác định bậc của nó deg Nịj. 
+ Theo deg Nịj xác định vector sinh và bậc i0 của thành 
phần syndrome đầu tiên s0i ứng với vector sinh. 
+ Tính số thứ tự bit lỗi đầu tiên theo công thức 
Li = (degsi - degs0i) mod n. 
+ Tìm vector lỗi e bằng cách dịch vòng vector sinh đi 
Li nhịp. 
+ Sửa tín hiệu nhận được: Cộng tín hiệu nhận được với 
vector lỗi e. 
Khảo sát trên trường GF(2m) với các đa thức sinh khác 
nhau, dựa trên phương pháp chuẩn syndrome, chúng ta có 
thể phân hoạch tập các vector lỗi thành các tập con không 
giao nhau. Khi đó mã BCH và biến thể của nó có thể sửa được 
một số cấu hình lỗi ngoài khoảng cách mã. Vì vậy khi sử dụng 
phương pháp chuẩn syndrome giải mã mã BCH ta có thể áp 
dụng mã BCH để xây dựng hệ mật mã dựa trên mã [13]. 
3. ĐỀ XUẤT XÂY DỰNG HỆ MẬT SỬ DỤNG MÃ BCH 
3.1. Hệ mật McEliece và Niederreiter 
Hệ mật mã khóa công khai McEliece [2]: 
Tạo khóa: Chọn một mã tuyến tính nhị phân C có khả 
năng sửa được t lỗi. Ma trận sinh G kích thước K×N. Chọn 
một ma trận nhị phân khả nghịch Q kích thước K×K. Chọn 
một ma trận hoán vị ngẫu nhiên P kích thước N×N. Tính 
toán khóa công khai G’ = Q.G.P kích thước K×N. Các ma trận 
(Q, G, P) là khóa bí mật. 
Mã hóa: Khi muốn gửi bản tin M tới bên nhận thông qua 
khóa công khai (G’,t). Biểu diễn bản tin M như một chuỗi 
SCIENCE TECHNOLOGY 
Số 51.2019 ● Tạp chí KHOA HỌC & CÔNG NGHỆ 5
nhị phân có độ dài k bit. Tạo một vector e ngẫu nhiên có độ 
dài N và có trọng số w(e) ≤ t. Tính toán bản mã c = MG’ + e 
và gửi cho bên nhận. 
Giải mã: Sau khi nhận được c, bên nhận thực hiện giải 
mã bản tin. Tính cP-1 = M(QGP)P-1 + eP-1 = MQG + eP-1. Sử 
dụng thuật toán giải mã sửa lỗi đối với cP-1 để tìm được MQ. 
Tính M = (MQ)Q-1, xác định được bản tin gốc ban đầu. 
Hệ mật khóa công khai Niederreiter [5]: 
Hệ mật Niederreiter là một biến thể của hệ mật McEliece. 
Điểm khác là nó sử dụng ma trận kiểm tra H của mã Goppa 
để làm khóa thay thế cho ma trận sinh G trong hệ mật 
McEliece gốc. Sơ đồ hệ mật được thể hiện trên hình 1. 
Hình 1. Sơ đồ hệ mật mã khóa công khai Niederreiter 
Tạo khóa: Chọn mã Goppa (N,K) có khả năng sửa t lỗi, có 
ma trận kiểm tra H kích thước (N-K)×N. Chọn ma trận khả 
nghịch Q kích thước (N-K)×(N-K). Chọn ma trận chuyển vị 
P(N×N). Tính khóa công khai H’ = Q.H.P. Các ma trận (Q, H, P) 
là các khóa bí mật. 
Mã hóa: Với khóa công khai (H’, t), bản tin M cho dưới 
dạng chuỗi nhị phân dài N bit có trọng số nhỏ hơn hoặc 
bằng t, bên gửi sẽ thực hiện tính bản mã: c = H’.MT. 
Giải mã: Bên nhận sở hữu khóa mật tiến hành thực hiện 
tính: 
c’ = Q-1c = Q-1H’.MT = Q-1.Q.H.P.MT = H.P.MT; 
Trong đó, c’ là một trong các syndrome của mã Goppa 
được sử dụng. 
Sử dụng thuật toán giải mã theo syndrome cho mã (N,K) 
ta tìm được M’ = P.MT. 
Tính bản tin MT = P-1.M’ và xác định bản tin gốc M. 
3.2. Xây dựng hệ mật sử dụng mã BCH 
Để giảm kích thước khóa, khắc phục nhược điểm của hệ 
mật Niederreiter, tác giả đề xuất sử dụng giải pháp ghép các 
mã BCH thành phần. Các mã thành phần với chiều dài và 
kích thước mã không lớn, sử dụng phương pháp giải mã dựa 
trên chuẩn syndrome mở rộng khả năng sửa ngoài giới hạn 
khoảng cách mã, nâng cao được tỷ lệ số syndrome có thể 
giải mã được trên tổng số syndrome có thể có của mã BCH. 
 Để xây dựng một hệ mật mã dựa trên mã ghép BCH, cần 
sử dụng một họ mã tuyến tính với đặc điểm mã hóa tốt. Mỗi 
mã của mã ghép này cần có một thuật toán giải mã với độ 
phức tạp đa thức. Ký hiệu  là họ mã tuyến tính. Một mã 
Ci  sẽ được định nghĩa bởi độ dài ni, số bit thông tin ki và 
khả năng sửa lỗi ti. Mã ghép này phải đủ lớn để chống lại tấn 
công vét cạn và mỗi mã Ci của mã ghép được xác định bởi ma 
trận kiểm tra Hi. Hệ thống xây dựng được từ các mã thành 
phần này được gọi là mã ma trận kiểm tra tổng. Giả thiết họ 
này có  mã, ma trận kiểm tra có dạng là một ma trận đường 
chéo chính với các phần tử là các ma trận Hi (i = 1   ). 
Giả sử dụng các mã BCH nhị phân và các biến thể (mã 
BCH thuận nghịch và mở rộng) làm các mã thành phần. Các 
giá trị chuẩn syndrome và vector sinh được sắp xếp trong 
các bảng. Để giải mã từ mã, thực hiện tính syndrome và 
chuẩn syndrome của nó. Từ chuẩn syndrome ta tìm được 
vector sinh và dựa vào bậc của syndrome thành phần s1 ta 
tính được số lượng dịch vòng. Do đó ta xác định vector lỗi 
tương ứng. Các thuật toán sử dụng trong hệ mật đề xuất 
như sau: 
Tạo khóa: Chọn một họ  mã BCH và mã BCH mở rộng, 
Hi là ma trận kiểm tra và ti là số lỗi có thể sửa được, với 
i =1   . Ma trận kiểm tra của các mã thành phần được sắp 
xếp theo đường chéo chính tạo thành ma trận kiểm tra H 
có cấu trúc như sau: 
 ( )
1
i
H 0 0
H N K N 0 H 0
0 0 H
 = 
 
 (6) 
- Chọn một ma trận khả nghịch Q[(N-K)×(N-K)], và chọn 
một ma trận hoán vị P[N× N] trong trường GF(2). Trong đó 
ma trận P là ma trận đường chéo chính với các thành phần 
Pi (i = 1   ) là các ma trận hoán vị cấp ni. 
- Tính khóa công khai H’: H’ = Q.H.P. Đây là ma trận kiểm 
tra của một mã tương đương với mã ghép BCH. 
- Khóa công khai là (H’,t). Trong đó t là tổng số lỗi có thể 
sửa được t = ti (i = 1   ). 
- Khóa mật là các ma trận (Q,H,P). Trong đó H là ma trận 
kiểm tra của mã ghép BCH. 
Mã hóa: Bản tin cần truyền đi M được biểu diễn dưới 
dạng chuỗi nhị phân dài N bit có cấu trúc dạng 
M1||M2||||Ml với độ dài đoạn Mi là ni bit có trọng số nhỏ 
hơn hoặc bằng ti. Phía gửi thực hiện tính bản mã c = H’.MT. 
Giải mã: Để giải mã bản mã c, Phía nhận sử dụng khóa 
mật và phương pháp chuẩn syndrome thực hiện giải mã 
theo các bước sau: 
- Tính c’ = Q-1.c = H.P.MT; c’ là một trong các syndrome 
của mã được sử dụng. 
- Từ c’ thực hiện tính M’ = P.MT. Sử dụng thuật toán giải 
mã BCH dựa theo chuẩn syndrome. 
- Từ M’ xác định bản tin MT: MT = P-1.M’. Từ đó ta khôi 
phục bản tin gốc M. 
4. ĐÁNH GIÁ ĐỘ PHỨC TẠP VÀ AN NINH HỆ MẬT 
4.1. Lựa chọn tham số 
Hệ mật sử dụng mã ghép BCH đề xuất, cho phép sử 
dụng các bộ mã với các tham số mã thành phần ni, ki, ti khác 
nhau. Tuy nhiên thuật toán giải mã phải đảm bảo có độ 
phức tạp đa thức và các tham số của bộ mã tổng phải đảm 
bảo đủ lớn để chống lại tấn công vét cạn. Việc đánh giá độ 
an toàn bảo mật và độ phức tạp thực hiện của hệ mật phụ 
 CÔNG NGHỆ 
 Tạp chí KHOA HỌC & CÔNG NGHỆ ● Số 51.2019 6
KHOA HỌC
thuộc vào bộ tham số lựa chọn. Qua khảo sát sự phụ thuộc 
của các tham số m ... thức (7): 
it
j
Syndrome n
j 1
T C n
=
  (7) 
Việc thực hiện tính toán chuẩn syndrome tương đương 
với việc phải sử dụng một bộ nhớ có dung lượng m.2m = 
n.log2n. Trong sơ đồ hệ mật dựa trên mã ghép BCH với họ 
mã sử dụng gồm  mã thành phần. Do đó, độ phức tạp để 
thực hiện giải mã cho  mã thành phần được xác định theo 
công thức (8): 
i it t
j j
1 n 2 n 2
j 1 j 1
WF .( C n).n.log n . C .log n
= =
= =   (8) 
Phần còn lại là các phép nhân ma trận nhị phân với độ 
phức tạp (N)2/2 và (N-K)2/2 phép toán nhị phân, trong đó 
N = ni, K = ki với i = 1   . Do đó độ phức tạp thực hiện 
của hệ mật đề xuất là: 
it 2 2 2
j
ghep n 2
j 1
(n. ) (n k) .WF . C .log n
2 2=
= + +
 
 (9) 
Với bộ tham số đề xuất lựa chọn, ước lượng độ phức tạp 
thực hiện của hệ mật sử dụng mã ghép BCH xác định theo 
công thức (9) , .24 6ghepWF 2= 
 4.3. Đánh giá độ bảo mật của hệ mật đề xuất 
4.3.1. Tấn công giải mã 
Thuật toán tấn công hiệu quả nhất với hệ mật mã dựa 
trên mã là giải mã tập thông tin ISD (Information-Set 
Decoding). Giải pháp thực hiện của thuật toán ISD được mô 
tả như sau: 
Phía tấn công không biết cấu trúc của mã bí mật vì vậy 
phải giải mã một mã ngẫu nhiên. Để thực hiện tấn công, 
phía tấn công chọn ngẫu nhiên k trong n tọa độ của c và ký 
hiệu là vector ck (k bit). Ký hiệu G’k và ek lần lượt là k cột của 
G’ và các vị trí tương ứng của e. Ta có ck = MG’k + ek hay 
(ck + ek)(G’k)-1 = M. Nếu k thành phần của ek bằng 0 thì ta có 
ck(G’k)-1 = M và có thể khôi phục lại thông điệp gốc mà 
không cần giải mã. 
Lee và Brickell là các tác giả đầu tiên phân tích an ninh 
của hệ mật mã dựa trên mã. Trên cơ sở tính toán khoảng 
cách mã tối thiểu Leon đã phát triển cách tấn công này 
bằng cách tìm kiếm từ mã trọng số thấp. Phương pháp này 
tiếp tục được Stern tối ưu bằng cách chia tập thông tin 
thành 2 phần, do đó làm tăng được tốc độ tìm kiếm các từ 
mã có trọng số thấp dựa trên thuật toán tấn công ngày 
sinh nhật. Một số cải tiến khác cũng đã được đề xuất: 
Canteaut và Chabaud [14], Bernstein và các cộng sự [15], 
Finiasz và Sendrier [16]. Trong [17] đã chỉ ra xác suất để 
thực hiện giải mã thành công cho một lần lặp của thuật 
toán tương ứng với các trọng số khác nhau của Lee và 
Brickell (PLB), Leon (PL), Stern (PS), công thức (10): 
 / .. .
, , 
2p t 2pp t p p t p n k vk 2k n k k n k v
LB L St t t
n n n
C CC C C CP P P
C C C
 = = = (10) 
Thuật toán giải mã Canteaut-Chabaud 
Cho C là một mã có chiều dài n trên trường F2 và y 2
nF
có khoảng cách t so với một từ mã c C, thì y-c là phần tử 
trọng số t của mã C+{0,y}. Vì vậy nếu C là mã dài n trong F2 
với khoảng cách mã tối thiểu lớn hơn t, thì một phần tử 
e C+{0,y} trọng số t không thể thuộc mã C, cho nên nó phải 
thuộc mã C+{y}; nghĩa là y-c là một phần tử của mã C có 
khoảng cách t so với y. Bản mã của hệ mật McEliece y 2
nF
có khoảng cách t với từ mã gần nhất c C có khoảng cách 
mã tối thiểu ít nhất là 2t+1. Phía tấn công biết khóa công 
khai của hệ mật McEliece là ma trận sinh của C và có thể tìm 
y với tập các ma trận sinh của C+{0,y}. Chỉ có từ mã trọng số t 
trong C+{0,y} là y-c bằng cách tìm từ mã này phía tấn công 
tìm được c và từ đó dễ dàng khôi phục được bản rõ. 
Tình huống tương tự có thể áp dụng với hệ mật 
Niederreiter với khóa công khai là ma trận kiểm tra của C. 
Bằng các biến đổi tuyến tính phía tấn công sẽ dễ dàng tìm 
được ma trận sinh của C và tiến hành xử lý bằng phương 
pháp như trên. Với bản mã đã cho của hệ mật Niederreiter 
sử dụng đại số tuyến tính phía tấn công tìm từ mã thỏa 
mãn khi nhân với ma trận kiểm tra tạo ra bản mã đặc biệt. 
Điểm mấu chốt của các tấn công trên là tìm từ mã có trọng 
số t trong C+{0,y}. Giới hạn dưới độ phức tạp WF (work 
factor) của thuật toán Canteaut-Chabaud được trình bày 
theo công thức (11) [17]: 
 , 
t
pn
2 k/2t 2pp
n k
C3.WF(n,k,t) min log C .
2 C 
 = 



 (11) 
SCIENCE TECHNOLOGY 
Số 51.2019 ● Tạp chí KHOA HỌC & CÔNG NGHỆ 7
Tấn công ngày sinh nhật 
Bài toán giải mã syndrome (Computational Syndrome 
Decoding - CSD): Cho trước ma trận H {0,1}(n-k)×n, một từ 
s {0,1}(n-k) và một số nguyên dương t, tìm từ e {0,1}n với 
trọng số Hamming nhỏ hơn t sao cho H.eT = s. 
Ký hiệu bài toán trên là CSD(H,s,t). Bài toán này tương 
đương với giải mã sửa t lỗi bằng mã có ma trận kiểm tra H. 
Bài toán giải mã syndrome như vậy đã được chứng minh là 
NP-đầy đủ [3]. Với tấn công ngày sinh nhật giới hạn dưới độ 
phức tạp được xác định bởi công thức (12) [16]: 
 , t (n k)/2BA nWF n,k,t 2Llog 2.t.L L min C ,2 = (12) 
Với t lẻ và /t 2nC L
 , công thức (12) chỉ là giới hạn dưới, 
tính toán chính xác được xác định theo công thức (13): 
2t/2 22 n
BA 2 t/2
n
C LLWF n,k, t 2L log 2.t. , L
L 2C
+ 
 = 
 (13) 
Cho tới nay đã có nhiều thuật toán mới tấn công vào hệ 
mật mã dựa trên mã. Mặc dù chưa có thuật toán nào thực 
sự hiệu quả, song có thể giúp các nhà mật mã học có 
những lựa chọn các tham số bảo mật một cách phù hợp 
cho từng mục đích ứng dụng. 
Đánh giá độ phức tạp của tấn công giải mã vào mã 
tổng hệ mật đề xuất: 
Với hệ mật dựa trên mã ghép BCH, phía tấn công 
không biết độ dài của các mã thành phần và khả năng sửa 
lỗi của chúng (ni,ti), không biết mã thành phần nào được 
sử dụng. Phía tấn công biết được khóa công khai là ma 
trận kiểm tra H’ tham số t là tổng trọng số của từ mã. 
Nghĩa là chỉ biết các tham số (N,K,t). Do đó, khi áp dụng 
thuật toán tấn công Canteaut-Chabaud, hay tấn công 
ngày sinh nhật, có thể áp dụng các công thức đánh giá độ 
phức tạp tấn công cho một mã. 
Hệ mật đề xuất khi sử dụng bộ tham số lựa chọn như 
trên, khi đó N = 568 và K = 408. Áp dụng phương pháp giải 
mã theo chuẩn syndrome cho từng mã thành phần, cho 
phép mở rộng khả năng sửa lỗi của mã tổng lên đến t = 41. 
Khi đó, độ phức tạp của tấn công giải mã theo thuật toán 
giải mã Canteaut-Chabaud công thức (11) có giá trị đạt tới 
,84 2WF 2= và độ phức tạp của tấn công theo thuật toán tấn 
công ngày sinh nhật công thức (12,13) có độ phức tạp lên 
tới 127WF 2= . 
Đánh giá độ phức tạp của tấn công giải mã vào các mã 
thành phần: 
Xét độ an toàn của hệ mật dựa trên mã ghép BCH, khi 
tấn công giải mã vào các mã thành phần. Giả sử trong 
trường hợp tồi nhất kẻ tấn công xác định được các tham số 
ni, ki, ti từ tham số công khai của hệ mật. Với mỗi mã thành 
phần, phía tấn công sử dụng tấn công giải mã ISD với độ 
phức tạp thực hiện là WF(ni, ki, ti ). Xác suất chọn được ki tọa 
độ không lỗi trong đoạn ni bit theo tấn công Canteaut-
Chabaud, công thức (10) là: 
 / .
i
i i ii
i
i
2
t 2pp
n kk 2
i t
n
C C
p
C

= (14) 
Biến đổi qua công thức (11) khi n nhỏ giá trị tối ưu p = 2, 
ta có: 
( )i
i
i
kPp
WF
= (15) 
trong đó P(ki) là chi phí thực hiện một lần lặp được xác 
định: 
   i i
2 2
2k /i 2 k /2P( ) 3C .log Ck (16) 
Do đó xác suất chọn được K = ∑ki với i = 1   tọa độ 
không lỗi là: 
( )i
i
i 1 i 1 i
kP
p p
WF= =
= = 
 
 (17) 
Từ đó suy ra độ phức tạp tấn công ISD với hệ mật dựa trên 
chuỗi mã theo kiểu tấn công vào từng mã thành phần là: 
( )
( )
( )
 ( ). (, , ).
( )
i
ac
i 1
i 1 i
i i
i1
i
i
k
n
WFP
k
KWF P K
p P
1WF P K
P
t
k
=
= =
= =
=

 

  (18) 
Với bộ mã gồm 10 mã thành phần lựa chọn trên độ 
phức tạp của tấn công vào từng mã thành phần theo công 
thức (18) WFac = 287,8. Độ phức tạp này cao hơn so với 
trường hợp tấn công vào mã tổng WF = 284,2. 
Xét với bộ mã khác: Giả sử chọn bộ mã gồm 14 mã 
thành phần với các tham số mã cụ thể như sau: một mã 
C6(32,21), bốn mã C8(32,16), một mã C8(64,45), ba mã 
C8(128,106), năm mã C10(32,11). Khi đó, ta có N = 768, K = 
503, t = 55. Sử dụng công thức (18) để đánh giá độ an toàn 
của hệ mật đối với tấn công vào từng mã thành phần khi sử 
dụng bộ mã gồm 14 mã kết quả WFac = 297,3. Trong khi đó 
độ phức tạp tấn công Canteaut-Chabaud là WF = 293,5 khi 
tấn công vào hệ mật với tham số tổng. 
Như vậy, việc tấn công vào từng mã thành phần có độ 
phức tạp cao hơn so với tấn công vào mã tổng. Trong cả 
hai trường hợp, hệ mật đề xuất đảm bảo được độ phức tạp 
tấn công trên 280, đáp ứng yêu cầu về độ bảo mật của một 
hệ mật. 
4.3.2. Tấn công cấu trúc 
Độ phức tạp của tấn công cấu trúc đối với khóa công 
khai của sơ đồ hệ mật dựa trên mã ghép BCH đề xuất có 
thể định lượng bằng cách dò tìm toàn bộ tổ hợp có thể có 
của ma trận hoán vị P(N!), mã bí mật và ma trận khả nghịch 
Q(0,29×2(N-K)). 
Giả sử tấn công cho phép xác định được ma trận H và Q, 
khi đó phía tấn công sẽ tìm được ma trận P. Tiếp theo với 
mỗi khóa mật phải kiểm tra cho tới khi khóa này là khóa 
đúng. Đối với sơ đồ hệ mật đề xuất, độ phức tạp của 
phương pháp tấn công này sẽ tăng theo độ phức tạp của 
các mã BCH. Bởi vì các mã thành phần: mã BCH, mã BCH mở 
 CÔNG NGHỆ 
 Tạp chí KHOA HỌC & CÔNG NGHỆ ● Số 51.2019 8
KHOA HỌC
rộng, mã thuận nghịch có độ dài khác nhau với các đa thức 
sinh khác nhau. Ngoài ra, trong hệ mật đề xuất có thể áp 
dụng hoán vị đối với các mã BCH thành phần để tăng thêm 
độ phức tạp tấn công. 
Để tấn công cấu trúc trong trường hợp thuận lợi nhất là 
xác định được tham số ni, ki của mỗi mã thành phần, từ đó 
xác định được việc sử dụng các mã thành phần. 
Giả sử thay đổi tham số b để bí mật ma trận mã BCH 
thành phần (có khoảng cách cấu trúc d = 5, 7), cho công 
khai các đa thức sinh của trường GF(2m), m = 5, 6, 7. Ngoài 
ra ở đây còn sử dụng các biến thể như mã BCH mở rộng, 
mã thuận nghịch và mở rộng của nó nên số lượng mã có 
thể chọn có thể tăng đột biến. Mặt khác tương ứng có 6; 6; 
14 đa thức nguyên thủy bậc 5, 6, 7. Các mã được sắp xếp 
thành chuỗi theo một thứ tự ngẫu nhiên. Vì vậy, số lượng 
mã thành phần khác nhau là 10668 mã. Khi đó, độ phức tạp 
tấn công để xác định cấu trúc của 10 mã thành phần có giá 
trị lên tới 2137. 
Bảng 1. So sánh sơ đồ hệ mật dựa trên mã ghép BCH với sơ đồ Niederreiter 
Sơ đồ hệ mật N K t Kích thước khóa (bytes) 
Tấn công 
ISD (bit) 
Hệ mật Niederreiter [18] 2048 1751 27 65.006 81 
Hệ mật sử dụng mã BCH 568 408 41 11.360 84,3 
Bảng 1 thể hiện kết quả so sánh kích thước khóa của hệ 
mật sử dụng mã ghép BCH đề xuất mới và hệ mật 
Niederreiter ở cùng một mức an ninh. Trong đó kích thước 
khoá của hệ mật đề xuất là 11.360 bytes giảm 5,7 lần so với 
kích thước của hệ mật Niederreiter 65.006 bytes. Hệ mật sử 
dụng mã ghép BCH đã đề xuất, khi kết hợp sử dụng 
phương pháp giải mã theo chuẩn syndrome cho phép tăng 
tỷ lệ mã hóa, nâng cao được số lỗi có thể sửa của các mã 
thành phần, do đó khắc phục được nhược điểm của hệ mật 
gốc Niederreiter. 
Hệ mật đề xuất an toàn với các tấn công giải mã và tấn 
công cấu trúc. Độ bảo mật của hệ mật đề xuất được khẳng 
định thông qua kết quả khảo sát các dạng tấn công điển 
hình vào hệ mật: Độ phức tạp của tấn công giải mã 284,2 và 
tấn công cấu trúc 2137. Hệ mật đề xuất, mặc dù chi phí cho 
việc giải mã các mã thành phần (độ phức tạp thực hiện) 
còn khá lớn 224,6; tuy nhiên với ưu điểm kích thước khóa đã 
được giảm nhỏ và khả năng sửa lỗi của mã được nâng cao, 
do đó có thể áp dụng hệ mật để xây dựng sơ đồ chữ ký số 
ứng dụng trong thực tế. 
5. KẾT LUẬN 
Bài báo đề xuất hệ mật mã dựa trên mã, biến thể mới của 
hệ mật Niederreiter dựa trên cấu trúc ghép các mã BCH thành 
phần có độ dài và kích thước khác nhau. Hệ mật đề xuất cho 
phép giảm được kích thước khóa 5,7 lần so với hệ mật 
Niederreiter ở cùng một mức an ninh. Bài báo ứng dụng 
phương pháp chuẩn syndrome giải mã mã BCH đã cho phép 
tăng tỷ lệ số lượng các syndrome có thể giải mã được trên 
tổng số các syndrome có thể có. Do đó, nâng cao hiệu quả 
sửa lỗi của mã BCH và khi áp dụng vào xây dựng hệ mật đã 
khắc phục được nhược điểm căn bản của hệ mật Niederreiter. 
TÀI LIỆU THAM KHẢO 
[1]. Mosca M., 2015. "Cybersecurity in an era with quantum computers: will 
we be ready?". The IACR Cryptology ePrint Archive Report 2015/1075. 
[2]. McEliece R. J., 1978. A Public-Key Cryptosystem Based on Algebraic 
Coding Theory. The Deep Space Network Progress Report, pp: 114-116. 
[3]. Berlekamp E., McEliece R., Tilborg H.v., 1978. "On the Inherent 
Intractability of Certain Coding Problems". IEEE Transactions on Information 
Theory, 24(3), pp: 384-386. 
[4]. Bernstein D. J., Lange T., and Peters C., 2008. Attacking and defending 
the McEliece cryptosystem. Post-Quantum Cryptography, Second International 
Workshop, PQCrypto2008, Cincinnati, OH, USA, pp: 31-46. 
[5]. Niederreiter H., 1986. "Knapsack-type Cryptosystems and Algebraic 
Coding Theory". Problems of Control and Information Theory, 15(2), pp: 159-166. 
[6]. Li Y. X., Deng R. H., and Wang X. M., 1994. "On the equivalence of 
McEliece's and Niederreiter's public-key cryptosystems". IEEE Transactions on Infor-
mation Theory, 40(1), pp: 271-273. 
[7]. Courtois N., Finiasz M., Sendrier N., 2001. How to achieve a mceliece 
based digital signature scheme. Advances in Cryptology - ASIACRYPT 2001, 
Lecture Notes in Computer Science, pp: 157-174. 
[8]. Minder L., Shokrollahi A., 2007. Cryptanalysis of the Sidelnikov Cryptosystem. 
Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on 
the Theory and Applications of Cryptographic Techniques, Barcelona, Spain 2007. 
Lecture Notes in Computer Science, pp: 347-360. 
[9]. Otmani A., Tillich J.-P., and Dallot L., 2010. "Cryptanalysis of Two 
McEliece Cryptosystems Based on Quasi-Cyclic Codes". Mathematics in Computer 
Science, Vol 3(2), pp: 129-140. 
[10]. Wieschebrink C., 2010. Cryptanalysis of the Niederreiter public key 
scheme based on GRS subcodes. Post-Quantum Cryptography, Third International 
Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010, pp: 61-72. 
[11]. Moon T. K., 2005. "Error correction coding mathematical methods and 
algorithms". John Wiley & Sons Ltd. 
[12]. Липницкий В. А., and Конопелько В. К., 2007. Норменное 
декодирование помехоустойчивых кодов и алгебраические уравнения. Минск 
: Изд. центр БГУ. 
[13]. Pham Khac Hoan, Le Van Thai, Vu Son Ha, 2013. Simultaneous 
correction of random and burst errors using norm syndrome for BCH codes. Hội 
thảo quốc gia REV- KC01 2013, tháng 12/2013, Tr 154-158. 
[14]. Canteaut A., and Chabaud F., 1998. "A new Algorithm for Finding 
Minimum Weight Words in a Linear Code: Application to McEliece’s Cryptosystem 
and to Narrow-Sense BCH Codes of Length 511". IEEE Transactions on Information 
Theory, 44(1), pp: 367-378. 
[15]. Bernstein D. J., Lange T., and Peters C., 2008. Attacking and defending 
the McEliece cryptosystem. Post-Quantum Cryptography, Second International 
Workshop, PQCrypto2008, Cincinnati, OH, USA, October 17-19, 2008, pp: 31-46. 
[16]. Finiasz M., and Sendrier N., 2009. Security Bounds for the Design of 
Code-Based Cryptosystems. Advances in Cryptology ASIACRYPT 2009, Lecture 
Notes in Computer Science, pp: 88-105. 
[17]. Bernstein D. J., Buchmann J., and Dahmen E., 2009. Post-quantum 
cryptography. Springer-Verlag Berlin Heidelberg, pp: 95-145. 
[18]. Siim S., 2015., "Study of McEliece cryptosystem". The MTAT. 07.022 
Research Seminar in Cryptography, Spring 2015. 
AUTHOR INFORMATION 
Le Van Thai 
Hanoi University of Industry