Đề xuất phương pháp cài đặt hiệu quả cho tầng tuyến tính kích thước lớn trong mã khối

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 149
ĐỀ XUẤT PHƯƠNG PHÁP CÀI ĐẶT HIỆU QUẢ CHO TẦNG 
TUYẾN TÍNH KÍCH THƯỚC LỚN TRONG MÃ KHỐI 
Trần Hồng Thái*, Phạm Đình Trọng 
Tóm tắt: Bài báo trình bày một phương pháp cài đặt hiệu quả cho tầng tuyến 
tính có kích thước lớn. Đặc biệt, đối với tầng tuyến tính kích thước lớn phương pháp 
đề xuất cho phép giữ nguyên số phép toán cơ sở, nhưng bộ nhớ giảm một nửa so với 
cách tiếp cận tra bảng thường được áp dụng trong các mã pháp SPN hiện đại. Cách 
tiếp cận trong bài báo là sử dụng kỹ thuật tra bảng khi khai thác các tính chất của 
ma trận tuyến tính truy hồi, ma trận Hadamard và ma trận dịch vòng. 
Từ khóa: Tầng tuyến tính, Ma trận MDS, Cài đặt hiệu quả, Mã pháp SPN. 
1. GIỚI THIỆU 
Trong mật mã ứng dụng, các mã khối ngoài việc phải đảm bảo độ an toàn cần phải có 
tính chất mềm dẻo trong cài đặt trên các platform khác nhau. Hiện nay, cài đặt thường 
được áp dụng đối với các mã khối hiện đại khi kết hợp đồng thời cả hai phép tuyến tính và 
phi tuyến như AES [2, 5], GOST R 34.12-2015 [7], LED [3], ... là cách sử dụng bảng tra 
được tính trước. Nếu như trong AES sử dụng tầng tuyến tính với ma trận MDS kích thước 
4×4, thì kích thước bảng tra yêu cầu là 8 KB [2, 5], còn trong GOST R 34.11-2012 là 128 
KB đối với ma trận kích thước 16×16 [6, 8]. Đối với hai mã pháp trên, với kích thước khối 
là 128 bit, số phép truy cập bộ nhớ là 16 và số phép XOR các số 32 bit (cho AES) hoặc 64 
bit (cho GOST R 34.12-2015) tương ứng là 16 và 32. Qua đó, có thể thấy rằng khi kích 
thước tầng tuyến tính tăng lên nhằm đảm bảo độ an toàn cần thiết thì độ phức tạp tính toán 
và đặc biệt là độ phức tạp bộ nhớ tăng lên đáng kể. Điều này trở thành vấn đề tác động lên 
tính mềm dẻo khi cài đặt các mã pháp trong các môi trường với năng lực tính toán và tài 
nguyên khác nhau. 
Những năm gần đây, nhằm đạt được các lợi thế trong cài đặt chủ yếu là trong phần 
cứng, có nhiều công trình tập trung nghiên cứu xây dựng các tầng tuyến tính truy hồi [1]. 
Theo đó, ma trận tuyến tính của chúng là lũy thừa của một ma trận đồng hành có dạng đơn 
giản và dễ dàng cài đặt phần cứng. Trong [8], nhóm tác giả đã đề xuất và đưa ra một loạt 
các phương pháp khai thác tính truy hồi đối với ma trận tuyến tính trong mã pháp 
Kuznyechik của nhóm tác giả Cơ quan FSB, Liên bang Nga đề xuất. 
Đã có một số lượng lớn các nghiên cứu tập trung lên việc sinh các ma trận truy hồi 
kích thước nhỏ, thường là 4×4, có lợi thế trong cài đặt phần cứng [11, 12, 13, 14]. Tuy 
nhiên, cài đặt phần mềm khi khai thác tính truy hồi của những ma trận này dường như 
chưa được quan tâm nhiều, đặc biệt là theo khía cạnh sử dụng các bảng tra được tính 
trước. Ở một hướng nghiên cứu khác liên quan đến xây dựng tầng tuyến tính sử dụng các 
ma trận MDS có dạng đặc biệt như các ma trận dịch vòng [15], ma trận Hadamard [16, 
17]. Các ma trận này tuy không có tính truy hồi nhưng chúng lại có đặc điểm là tập các 
phần tử ở mỗi hàng hoặc mỗi cột trong ma trận tuyến tính là giống nhau mặc dù thứ tự của 
chúng là khác nhau. Trong cài đặt phần cứng tính chất này được khai thác một cách triệt 
để, còn trong cài đặt phần mềm sử dụng kỹ thuật tra bảng chủ yếu áp dụng cho những ma 
trận kích thước nhỏ, cỡ 4×4, hoặc 8×8. Khi kích thước ma trận tuyến tính tăng lên, sẽ phát 
sinh các vấn đề liên quan đến bộ nhớ cần lưu những bảng tra đã được tính trước. Điều này 
dường như là một điểm hạn chế khi cài đặt các ma trận lớn trong môi trường có năng lực 
tính toán hạn chế. Trên cơ sở khai thác tính chất các tầng tuyến tính truy hồi, các tầng 
tuyến tính sử dụng ma trận Hadamard hoặc dịch vòng, trong bài báo này chúng tôi sẽ khảo 
sát một số đặc điểm của chúng và sau đó đề xuất phương pháp cài đặt hiệu quả tổng quát 
cho các tầng tuyến tính kích thước lớn dạng này. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả  trong mã khối.” 150 
Đóng góp của chúng tôi: Đề xuất phương pháp cài đặt hiệu quả tổng quát cho các tầng 
tuyến tính truy hồi kích thước lớn, trong đó tầng tuyến tính được xây dựng sử dụng các ma 
trận truy hồi, Hadamard hoặc dịch vòng. 
Bố cục các phần còn lại của bài báo như sau: Mục 2 trình bày về tầng tuyến tính truy 
hồi, tầng tuyến tính sử dụng ma trận Hadamard hoặc dịch vòng. Mục 3 trình bày lại cách 
sử dụng bảng tra để cài đặt cho các tầng tuyến tính với biểu diễn thông qua một ma trận 
tuyến tính trên trường hữu hạn. Đề xuất phương pháp cài đặt hiệu quả tầng tuyến tính truy 
hồi và tầng tuyến tính sử dụng ma trận Hadamard hoặc dịch vòng sẽ được đưa ra ở mục 4 
của. Cuối cùng là một số kết luận và danh mục tài liệu tham khảo. 
2. MỘT SỐ CHIẾN LƯỢC THIẾT KẾ TẦNG TUYẾN TÍNH 
CHO THUẬT TOÁN MÃ KHỐI 
2.1. Tầng tuyến tính truy hồi dựa trên ma trận đồng hành 
Trong ngữ cảnh của bài báo đề này, chúng tôi xem xét tầng tuyến tính nhận được từ 
một ma trận tuyến tính M kích thước m×m trên trường hữu hạn GF(2n) và m chẵn. Tính 
truy hồi của nó được thể hiện ở việc là ma trận M được xác định bằng lũy thừa bậc m của 
một ma trận đồng hành A kích thước m×m có dạng sau: 
0
1
2
1
0 0 0
1 0 0
0 1 0
0 0 1 m
a
a
A a
a 



    

, 2 , 0 1nia GF i m (1) 
Biểu diễn của tầng tuyến tính trong bài báo này ký hiệu là : mn mnL V V , được quy 
định là phép nhân bên phải véc tơ hàng X với ma trận M, đầu ra là véc tơ hàng Y: 
((( (( ) ) ... ) ) )m
m
Y X M X A X A A A A A 

, (2) 
trong đó: 0 1 1, ,..., mY y y y , 0 1 1, ,..., mX x x x , , 2ni ix y GF . 
2.2. Tầng tuyến tính sử dụng ma trận Hadamard 
Với lợi thế trong cài đặt, các ma trận Hadamard có thể được sử dụng thiết kế tầng 
tuyến tính của các nguyên thủy mật mã. Trong mục này, chúng tôi sẽ giới thiệu ngắn gọn 
về dạng ma trận này. Ma trận Hadamard kích thước m×m là ma trận có dạng 
1 2
2 1
H H
H
H H
, 
 trong đó, các ma trận 1H và 2H là các ma trận con vuông kích thước 
2 2
m m
 . Ví dụ với 
các ma trận: 
0 1 2 3
1 2
1 0 3 2
,
a a a a
H H
a a a a
, 
có ma trận Hadamard 4×4 như sau: 
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
a a a a
a a a a
H
a a a a
a a a a
. 
2.3. Tầng tuyến tính sử dụng ma trận dịch vòng 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 151
Ma trận dịch vòng (circulant matrix) là ma trận nhận được bằng cách dịch vòng đi 1 
một phần tử ở mỗi hàng hoặc mỗi cột. Ví dụ một ma trận dịch vòng kích thước 4×4 có 
dạng sau: 
0 1 2 3
3 0 1 2
2 3 0 1
1 2 3 0
a a a a
a a a a
C
a a a a
a a a a
. 
Thấy rằng, ở hai ma trận dạng này số phần tử ở mỗi hàng hoặc mỗi cột của chúng là 
như nhau. Đây là một tích chất mà được khai thác trong các cài đặt phần cứng cũng như 
phần mềm đối với những tầng tuyến tính sử dụng dạng ma trận này. 
3. CÀI ĐẶT TẦNG TUYẾN TÍNH SỬ DỤNG CÁC BẢNG TRA 
Trong mục này, chúng tôi trình bày cách cài đặt tầng tuyến tính sử dụng kỹ thuật tra 
bảng. Tầng tuyến tính ký hiệu bởi ánh xạ tuyến tính L, được biểu diễn dưới dạng phép 
nhân bên phải một véc tơ hàng X với ma trận M trên GF(2n). Khi đó, biến đổi tuyến tính 
: mn mnL V V có thể biểu diễn dưới dạng: 
0,0 0,1 0, 1
1,0 1,1 1, 1
0 1 1
1,0 1,1 1, 1
, ,...,
m
m
m
m m m m
b b b
b b b
L X X M x x x
b b b


   

. (3) 
trong đó: ,, 2 , , 0,1,..., 1ni i jx b GF i j m . Xét biến đổi tuyến tính 
* : , 0, 1i n mnL V V i m : 
*
,0 ,1 , 1: || || ... ||n i i i i mx V L x b x b x b     , (4) 
trong đó, phép || là phép ghép nối hai véc tơ. 
Từ (3) và (4) ta có 
* * *
0 0 1 1 1 1
0 0,0 0 0,1 0 0, 1
1 1,0 1 1,1 1 1, 1
1 1,0 1 1,1 1 1, 1
( ) ( ) ( ) ... ( )
|| || ... ||
|| || ... ||
 =
|| || ... ||
m m
m
m
m m m m m m m
Y L X L x L x L x
x b x b x b
x b x b x b
x b x b x b
    
  

  


  

Như vậy, ánh xạ : mn mnL V V có thể biểu diễn thông qua m ánh xạ tuyến tính 
* *
0 1,..., mL L , mỗi ánh xạ iL có thể tính thông qua một bảng tra gồm 2
n dòng, mỗi dòng kích 
thước mn bit, các bảng tra này được sắp xếp theo thứ tự tăng dần như sau: 
,0 ,1 , 1
,0 ,1 , 1
,0 ,1 , 1
,0 ,1 , 1
0 || 0 || || 0
1 || 1 || || 1
|| || ||
2 1 || 2 1 || || 2 1
i i i m
i i i m
i i i m
n n n
i i i m
b b b
b b b
b r b r b r
b b b
  
  
  
   


 

 

, 
Công nghệ thông tin & Cơ sở toán học cho tin học 
T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả  trong mã khối.” 152 
trong đó, phép nhân ,0ib r được thực hiện trong GF(2
n), ở đây r là một phần tử của 
trường GF(2n). 
Như vậy, dòng thứ r của bảng này được xác định bởi 
 * ,0 ,1 , 1|| || ... || , 2 , 0,1,..., 1ni i i i mL r b r b r b r r GF i m     . 
Quá trình này cũng được thực hiện tương tự đối với biến đổi tuyến tính 
1 : mn mnL V V
 , nhưng khi đó sử dụng ma trận M-1. Ở đây, chúng tôi không trình bày cụ 
thể quá trình này. 
Như vậy, để cài đặt : mn mnL V V cần m phép truy cập bộ nhớ lưu m bảng tra và m 
phép XOR các từ mn bit. 
Cách sử dụng bảng tra này còn có thể áp dụng để kết hợp đồng thời hai phép biến đổi 
phi tuyến và tuyến tính cho các mã pháp dạng SPN, như trong AES [5], GOST R 34.12-
2015 [6], .... Theo đó, số lượng bảng tra cần lập ở đây là m bảng, với tổng kích thước bộ 
nhớ yêu cầu là m2×n×2n bit. Chi tiết cài đặt cho từng giá trị của m, n có thể tham khảo 
trong [2, 5, 6, 8]. 
Ví dụ với m = 32, n = 8 (áp dụng cho mã pháp SPN có kích thước khối m×n = 256 
bit), bộ nhớ yêu cầu là 322×8×28 bit = 256 KB. Nếu áp dụng cho cả quá trình giải mã thì 
bộ nhớ cần phải tăng gấp 2 lần. Trong ví dụ này nếu xét đến năng lực tính toán của các 
máy tính thông dụng thì mỗi bảng tra không thể lưu bởi các số 256 bit. Do vậy, thay vì 
phải lập 32 bảng tra, chúng ta cần lập 32×4 = 96 bảng tra, các phần tử trong mỗi bảng là 
các số 64 bit (64 bit là thanh ghi của các máy tính thông dụng hiện nay). Với việc tăng số 
lượng bảng phụ thuộc vào năng lực tính toán thực tế như vậy sẽ làm tăng số phép truy cập 
bộ nhớ, và số phép XOR các số 64 bit sẽ tăng lên rất nhiều, ít nhiều chúng sẽ ảnh hưởng 
đến tốc độ thực thi. Rõ ràng đây là một vấn đề cần tối ưu hóa trong cài đặt đối với các tầng 
tuyến tính kích thước lớn. Trong phần tiếp theo, chúng tôi sẽ đề xuất một số cách tiếp cận 
đối với dạng cụ thể của ma trận M để từ đó có thể giảm số lượng các bảng tra nói trên. 
4. MỘT CÁCH CÀI ĐẶT MỚI CHO TẦNG TUYẾN TÍNH 
SỬ DỤNG KỸ THUẬT TRA BẢNG 
4.1. Đối với tầng tuyến tính truy hồi 
Đối với tầng tuyến tính (2) thay vì lập bảng tra cho ma trận M = Am, chúng tôi đề xuất 
phương pháp cài đặt khi lập bảng tra trước cho ma trận Am/2. Để đơn giản và trực quan 
hơn, chúng tôi xét trường hợp tầng tuyến tính kích thước nhỏ, với m = 4, và n = 4. Khi đó, 
xét ma trận đồng hành có dạng sau: 
0
1
2
3
0 0 0
1 0 0
0 1 0
0 0 1
a
a
A
a
a
, với 42 ,0 3ia GF i . (5) 
Khi đó: 
0 0 3 0 0 3
1 0 1 3 1 0 1 32 4
2 1 2 3 2 1 2 3
2 2
3 2 3 3 2 3
0 0
0 0
,
1 0
0 1
a a a a a a
a a a a a a a a
A M A
a a a a a a a a
a a a a a a
  
   
  
, (6) 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 153
ở đây, là một giá trị nào đó thuộc GF(24). Chúng tôi chỉ quan tâm đến sự giống nhau của 
hai cột cuối cùng và hai cột đầu tiên tương ứng trong hai ma trận A2 và A4. Với dạng biểu 
diễn như vậy, xét phép nhân bên phải véc tơ 0 1 2 3, , ,X x x x x với ma trận A
2, có 
0 0 3
1 0 1 3* 2
0 1 2 3 0 1 2 3
2 1 2 3
2
3 2 3
0 2
1 3
2 0 0 1 1 2 2 3 3
2
3 0 3 0 0 1 3 1 1 2 3 2 2 3 3
0 0
0 0
, , , , , ,
1 0
0 1
a a a
a a a a
Y y y y y X A x x x x
a a a a
a a a
y x
y x
y a x a x a x a x
y a a x a a a x a a a x a a x
 
 
 
    
       
 (7) 
còn với ma trận A4, có 
0 0 3
1 0 1 34
0 1 2 3 0 1 2 3
2 1 2 3
2
3 2 3
0 0 0 1 1 2 2 3 3
2
1 0 3 0 0 1 3 1 1 2 3 2 2 3 3
2
3
, , , , , ,
a a a
a a a a
Y y y y y X A x x x x
a a a a
a a a
y a x a x a x a x
y a a x a a a x a a a x a a x
y
y
 
  
 
    
       
 (8) 
Từ (7) và (8) ta thấy 0 2y y
 và 1 3y y
 . Như vậy, đầu ra của tầng tuyến tính truy hồi 
có thể sử dụng ma trận A2 để tính được một nửa giá trị tọa độ của véc tơ đầu ra Y thông 
qua véc tơ Y , sau đó áp dụng tiếp ma trận A2 này lên véc tơ đầu vào có tọa độ là 
 2 3 0 1, , ,x x y y để nhận được một nửa giá trị các tọa độ còn lại của véc tơ Y. 
Trong trường hợp tổng quát, với ma trận A kích thước m×m trên trường GF(2n) nói 
trên, cách lập bảng tra và sử dụng bảng tra để tính các véc tơ đầu ra được mô tả như dưới 
đây. Có tất cả m bảng tra, ký hiệu là T0, T1, ... Tm – 1, mỗi bảng có 2
n phần tử, mỗi phần tử 
của bảng có kích thước bằng kích thước ghép nối (phép ||) một nửa số phần tử trên một 
hàng của ma trận, và bằng / 2mn bit. 
Viết lại biểu thức (2) như sau: 
 /2 /20 1 1 0 1 1, ,..., , ,...,m m mm mY y y y X A x x x A A . (9) 
Từ ma trận A có dạng (1), tính ma trận Am/2. Giả sử có dạng sau: 
0, 0, 1 0, 1
1, 1, 1 1, 1/2
1, 1, 1 1, 1
0
0
0
j j m
j j mm
m j m j m m
b b b
b b b
A
b b b
 
 
     
 
, (10) 
trong đó: , 2 , 0,1,..., 1, , 1, ..., 1
2 2
n
i j
m m
b GF i m j m . 
Công nghệ thông tin & Cơ sở toán học cho tin học 
T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả  trong mã khối.” 154 
Xét biến đổi tuyến tính *
2
: , 0, 1i n mnL V V i m : 
*
, , 1 , 1: || || ... || , / 2n i i j i j i mx V L x b x b x b j m     . (11) 
Từ những lập luận ở trên ta thấy khi nhân véc tơ X với ma trận A2 ta sẽ nhận được các 
tọa độ ở nửa đầu của véc tơ Y. Do vậy, từ công thức (9), (10), (11) ta có thể tính được nửa 
đầu của véc tơ Y như sau: 
 0 1 0 1 1
1
2
0 0, 0 0, 1 0 0, 1
1 1, 1 1, 1 1 1, 1
* * *|| || ... ||
|| || ... ||
|| || ... ||
m m
j j m
j j m
y y y L x L x L x
x b x b x b
x b x b x b
    
  

  
 


1 1, 1 1, 1 1 1, 1
,
2
|| || ... ||m m j m m j m m m
m
j
x b x b x b 

  
. (12) 
Như vậy, các giá trị tọa độ 0 1
1
2
, ,..., my y y
 có thể tính thông qua biểu thức (12) bởi m 
ánh xạ tuyến tính (11), mỗi ánh xạ tuyến tính này có thể tính thông qua một bảng gồm 2n 
phần tử, kích thước mỗi phần tử của bảng bằng kích thước ghép nối (phép ||) một nửa số 
phần tử trên một hàng của ma trận, và bằng / 2mn bit. Các bảng tra này được tính và 
sắp xếp theo thứ tự tăng dần của giá trị x. Bảng tra thứ i được tính như sau: 
, , 1 , 1
, , 1 , 1
, , 1 , 1
0 || 0 || || 0
|| || ||
2 1 || 2 1 || || 2 1
i j i j i m
i j i j i m
n n n
i j i j i m
b b b
b k b k b k
b b b
  
  
   

 

 

, (13) 
trong đó 0, 1, , 2
2
nmi m j k GF . 
Tương tự như vậy, để tính các tọa độ ở nửa sau của véc tơ Y ta chỉ việc áp dụng lặp lại 
quá trình trên khi nhân véc tơ X với ma trận A2, các tọa độ của véc tơ này là: 
1 0 1
1 1
2 2 2
, ,..., , , ,...,m m m mX x x x y y y
. 
Những tọa độ của véc tơ X chính là các địa chỉ của mỗi bảng tra (13). 
Những phân tích ở trên chỉ ra rằng, cách tiếp cận sử dụng bảng tra để tính giá trị của 
tầng tuyến tính truy hồi cho phép giảm một nửa bộ nhớ khi lưu dữ liệu tính trước so với 
phép lập bảng cho toàn bộ ma trận như trong một số tài liệu đã đề cập [2, 5, 6, 8]. Trong 
khi số phép XOR như trong biểu thức (12) chỉ là cộng theo modulo 2 các số / 2mn . 
Chú ý: Việc đánh giá số lượng bảng tra ở đây chỉ mang tính lý thuyết, bởi trong cài đặt 
thực tế, đối với tầng tuyến tính có kích thước lớn số lượng này sẽ thay đổi phụ thuộc vào 
năng lực lưu trữ (kích thước thanh ghi) cho phép của môi trường cài đặt và khả năng lưu 
trữ của trình biên dịch. Cụ thể sẽ phân tích ở bảng 1. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 155
Đối với tầng tuyến tính truy hồi dạng (2), ma trận nghịch đảo của nó cũng có dạng 
tương tự, do vậy cách tiếp cận ở trên có thể sử dụng để tính cho ánh xạ L-1. Ở đây, chúng 
tôi không trình bày chi tiết vấn đề này. 
4.2. Đối với tầng tuyến tính sử dụng ma trận dịch vòng 
Như đã phân tích ở mục 2, các ma trận dịch vòng có tập các phần tử ở trên cùng một 
hàng hoặc một cột là giống nhau. Đặc điểm này sẽ được chúng tôi khai thác để đề xuất 
phương pháp cài đặt sử dụng kỹ thuật tra bảng. Cũng như trong mục 4.1 để đơn giản ở đây 
chúng tôi xét ma trận dịch vòng C kích thước 4×4 trên GF(24) như sau: 
0 1 2 3
3 0 1 2
2 3 0 1
1 2 3 0
a a a a
a a a a
C
a a a a
a a a a
. (14) 
Khi đó, tầng tuyến tính được xác định bởi ánh xạ 
16 16
0 1 2 3
3 0 1 2
0 1 2 3 0 1 2 3
2 3 0 1
1 2 3 0
: :
, , , , , ,
L V V
a a a a
a a a a
Y y y y y X C x x x x
a a a a
a a a a
. (15) 
Từ đây có 
0 0 1 0 2 0 3 0
3 1 0 1 1 1 2 1
0 1 2 3
2 2 3 2 0 2 1 2
1 3 2 3 3 3 0 3
|| ||
|| ||
|| , ||
|| ||
|| ||
a x a x a x a x
a x a x a x a x
y y y y
a x a x a x a x
a x a x a x a x
  
   
  
 . (16) 
Thấy rằng, trong biểu thức (16) đối với công thức tính tổng XOR của 0 1||y y và 2 3||y y 
có các số hạng giống nhau đối với các hệ số của ma trận C, mà chỉ khác nhau ở thứ tự. Do 
vậy, nếu sử dụng cách lập bảng tra cho một nửa số cột của ma trận C thì ta có thể tính 
được toàn bộ các tọa độ đầu ra của véc tơ Y. Thật vậy, nếu lập 4 bảng tra cho ghép nối của 
hai cột cuối cùng của ma trận (14) như sau: 
2 3 1 2
2 3 1 20 1
4 4 4 4
2 3 1 2
0 1 3 0
0 1 3 02 3
4 4 4 4
0 1 3 0
0 || 0 0 || 0
|| ||, ,
2 1 || 2 1 2 1 || 2 1
0 || 0 0 || 0
|| ||,
2 1 || 2 1 2 1 || 2 1
a a a a
a k a k a k a kT T
a a a a
a a a a
a k a k a k a kT T
a a a a
   
    
    
   
    
    
 
 
 
 
 (17) 
Công nghệ thông tin & Cơ sở toán học cho tin học 
T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả  trong mã khối.” 156 
trong đó 40 2 1k và phép nhân được thực hiện trên GF(24). Khi đó, 0 1||y y và 2 3||y y 
được xác định bởi: 
       
       
0 1 2 0 3 1 0 2 1 3
2 3 0 0 1 1 2 2 3 3
||
||
y y T x T x T x T x
y y T x T x T x T x
   
   
 (18) 
Như vậy, trong trường hợp này ta cũng chỉ phải lập 4 bảng tra nhưng kích thước mỗi 
bảng tra giảm đi một nửa so với cách lập bảng tra cho toàn bộ ma trận như trong mục 3. 
Do đó, bộ nhớ yêu cầu giảm đi một nửa. Kết quả này cũng tương tự như kết quả so với 
tầng tuyến tính truy hồi trong mục 4.1. 
Trong trường hợp tổng quát, với ma trận A kích thước m×m trên trường GF(2n), cách 
lập bảng tra và sử dụng bảng tra để tính các véc tơ đầu ra được tổng quát hóa lại, theo đó, 
cần tất cả m bảng tra, ký hiệu là T0, T1, ... Tm – 1, mỗi bảng có 2
n phần tử, mỗi phần tử của 
bảng có kích thước bằng kích thước ghép nối (phép ||) một nửa số phần tử trên một hàng 
của ma trận, và bằng / 2mn . 
4.3. Đối với tầng tuyến tính sử dụng ma trận Hadamard 
Ma trận Hadamard kích thước m×m là ma trận có dạng 
1 2
2 1
H H
H
H H
. 
Từ đây thấy rằng, tập các phần tử ở mỗi hàng hoặc mỗi cột của ma trận này là giống 
nhau. Do vậy, có thể áp dụng các tiếp cận tương tự như đối với ma trận dịch vòng để lập 
các bảng tra cho một nửa số cột của H. Độ phức tạp tính toán, cũng như độ phức tạp về bộ 
nhớ lưu trữ cũng tương tự như tầng tuyến tính sử dụng ma trận dịch vòng. 
4.4. Một số nhận xét 
Trong mục này, chúng tôi thống kế phân tích độ phức tạp cho một số trường hợp cụ 
thể của tầng tuyến truy hồi và tầng tuyến tính dựa trên ma trận Hadamard (ký hiệu là ma 
trận H) hoặc ma trận dịch vòng (ký hiệu là ma trận C), trong đó, mỗi phần tử ở mỗi bảng 
sẽ lưu ở các số có độ lớn đến 64 bit (đây là kích thước thanh ghi của máy tính thông dụng). 
Bảng 1 dưới đây là độ phức tạp của kỹ thuật cài đặt sử dụng bảng tra cho ma trận kích 
thước m×m, với m = 2k trên trường hữu hạn GF(2n). 
Bảng 1. So sánh các tham số của hai cách cài đặt sử dụng bảng tra. 
TT 
Tham 
số 
Cách cài đặt 
sử dụng bảng 
tra 
Kích 
thước 
thanh 
ghi 
(bits) 
Kích 
thước 
bảng 
tra 
Số 
lượng 
bảng 
Số 
phép 
truy 
cập bộ 
nhớ 
Số 
phép 
XOR 
Kích 
thước 
của 
biến đổi 
tuyến 
tính 
1 
m = 4 
n = 4 
Cho ma trận M 16 128 B 4 4 4 
16 bit 
Cho ma trận 
A2, một nửa 
số cột của H 
hoặc C 
8 64 B 4 8 8 
2 
m = 4 
n = 8 
Cho ma trận M 32 4 KB 4 4 4 
32 bit 
Cho ma trận 
A2, một nửa 
số cột của H 
hoặc C 
16 2 KB 4 8 8 
3 m = 8 Cho ma trận M 32 4 KB 8 8 8 32 bit 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 157
n = 4 Cho ma trận 
A4, một nửa 
số cột của H 
hoặc C 
16 2 KB 8 16 16 
4 
m = 8 
n = 8 
Cho ma trận M 64 16 KB 8 8 8 
64 bit 
Cho ma trận 
A4, một nửa 
số cột của H 
hoặc C 
32 8 KB 8 16 16 
5 
m = 16 
n = 8 
Cho ma trận M 64 64 KB 32 32 32 
128 bit 
Cho ma trận 
A8, một nửa 
số cột của H 
hoặc C 
64 32 KB 16 32 32 
6 
m = 32 
n = 8 
Cho ma trận M 
64 
256 
KB 
128 128 128 
256 bit 
Cho ma trận 
A8, một phần 
tư số cột của 
H hoặc C 
64 64 KB 32 128 128 
7 
m = 64 
n = 8 
Cho ma trận M 
64 
1024 
KB 
512 512 512 
512 bit 
Cho ma trận 
A8, một phần 
tám số cột của 
H hoặc C 
64 
128 
KB 
64 512 512 
Trong bảng 1 thấy rằng khi kích thước tầng tuyến tính nhỏ hơn 128 bit. Khi đó, độ 
phức tạp của cách cài đặt sử dụng ma trận M và của phương pháp đề xuất khác nhau ở kích 
thước bộ nhớ cần lưu, và số lượng phép XOR của phương pháp đề xuất nhiều gấp 2 lần 
phương pháp cài đặt khi lập bảng tra cho ma trận M. 
Khi kích thước tầng tuyến tính bằng 128 bit khi đó số lượng bảng tra của phương pháp 
mới chỉ cần lập là 16 bảng, bằng một nửa so với 32 bảng của phương pháp sử dụng bảng 
tra cho ma trận M. Còn kích thước vẫn nhỏ hơn một nửa. Sự khác biệt này được giải thích 
như sau. Đối với phương pháp cài đặt sử dụng bảng tra cho ma trận M, theo như phân tích 
ở mục 3 chỉ cần lập 16 bảng, tuy nhiên, kích thước mỗi phần tử trong từng bảng bằng 128 
bit. Đối với các máy tính thông thường hiện này giá trị này cần được chia thành hai số 64 
bit. Do vậy, thay vì lập 16 bảng, chúng ta cần 32 bảng phụ thuộc vào kích thước thanh ghi 
của môi trường cài đặt phần mềm thực tế. Trong trường hợp ngược lại, phương pháp mới 
là chỉ lập bảng tra cho một nửa số cột của ma trận A8, hoặc một nửa số cột của ma trận H, 
hoặc C. Do vậy, chỉ cần 16 bảng tra cho những trường hợp này. 
Khi kích thước tầng tuyến tính tăng lên, ví dụ 256 và 512 bit, chúng tôi có thể sử dụng 
các ma trận không phài Am/2, mà tương ứng là là Am/4 = A8 và Am/8 = A8 đối với trường hợp 
tầng tuyến tính truy hồi. Đối với ma trận H hoặc C cũng tương tự như vậy, sẽ lập bảng tra 
cho 1/4 số cột hoặc 1/8 số cột của chúng. Làm như vậy để kích thước mỗi phần tử ở trong 
từng bảng phù hợp với kích thước thanh ghi 64 bit. Trong trường hợp này, kích thước bộ 
nhớ yêu cầu để lưu giảm không phải 2 lần mà tương ứng là 4 và 8 lần. Số lượng bảng cần 
lập cũng giảm trong ví dụ này tương ứng là 4 và 8 lần. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả  trong mã khối.” 158 
5. KẾT LUẬN 
Trong bài báo này chúng tôi đề xuất một phương pháp cài đặt hiệu quả đối với tầng 
tuyến tính truy hồi, tầng tuyến tính sử dụng các ma trận Hadamard hoặc dịch vòng có kích 
thước lớn. Theo đó, kỹ thuật lập bảng tra khai thác tính chất truy hồi của ma trận tuyến 
tính, tính giống nhau ở tập các phần tử trong mỗi hàng của ma trận Hadamard hoặc dịch 
vòng, cho phép thực thực thi tầng tuyến tính với độ phức tạp tính toán (số phép XOR và 
phép truy cập bộ nhớ) không đổi so với cách cài đặt tra bảng thông thường. Tuy nhiên, 
phương pháp của chúng tôi cho phép giảm đáng kể bộ nhớ lưu trữ các bảng tra cần phải 
tính trước (bảng 1). Phương pháp này cho phép cài đặt mềm dẻo hơn các tầng tuyến tính 
có kích thước lớn trong các môi trường khác nhau. 
Hướng nghiên cứu tiếp theo của bài báo là áp dụng phương pháp cài đặt trên đối với 
các mã pháp thực tế sử dụng ma trận tuyến tính truy hồi để có thể đánh giá chính xác hiệu 
quả của nó. 
TÀI LIỆU THAM KHẢO 
[1]. Augot Daniel and Matthieu Finiasz. “Direct construction of recursive MDS diffusion 
layers using shortened BCH codes”. in Fast Software Encryption. 2014. Springer. 
[2]. Daemen, Joan, and Vincent Rijmen. “The design of Rijndael: AES-the advanced 
encryption standard”. Springer Science & Business Media, 2002. 
[3]. Guo, Jian, et al. “The LED block cipher”. Cryptographic Hardware and Embedded 
Systems- CHES 2011. Springer Berlin Heidelberg, 2011. 326-341. 
[4]. Мак-Вильямс Ф. Дж., Слоен Н. Дж. А. – “Теория кодов, исправляющих ошибки: 
Пер. С англ. – М.: Связь”, 1979. – 744 с., ил. 
[5]. Зензин О. С., Иванов М. А. “Стандарт криптографической защиты” - AES. 
Конечные поля. – М. : КУДИЦ-ОБРАЗ, 2002. – 176 с. 
[6]. Mikhail Borodin, Andrey Rybkin, Alexey Urivskiy. “HighSpeed Software 
Implementation of the Prospective 128-bit Block Cipher and Streebog Hash-
Function”. CTCrypt 2014. pp. 189-198. 
[7]. GOST R 34.12–2015: “Information technology. Cryptographic data security. Block 
ciphers. Block Cipher”.  
[8]. Nikolay Borisenko, Nguyen Van Long, Alexey Bulygin. “Algorithm design 
software and hardware implementation of large size linear mapping”. CTCrypt 
2013. pp. 192-205. 
[9]. Cannon John and Wieb Bosma, “Handbook of MAGMA functions”. Edition, 2006. 2: 
p. 4350. 
[10].  
[11]. Kishan Chand Gupta and Indranil Ghosh Ray. “On Constructions of MDS Matrices 
form Companion Matrices for Lightweight Cryptography”. Security Engineering and 
Intelligence Informatics - Lecture Notes in Computer Science Volume 8128, 2013, pp 
29-43. 
[12]. Sajadieh M., Dakhilalian M., Mala H., Sepehrdad P. “Recursive Diffusion Layers for 
Block Ciphers and Hash Functions”. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 
7549, pp. 385-401. Springer, Heidelberg (2012). 
[13]. G. Zeng, K. He, and W. Han. “A trinomial type of -LFSR oriented toward software 
implementation”. In Science in China Series F-Information Sciences, volume 50, 
pages 359{372. Springer-Verlag, 2007. 
[14]. Shengbao Wu, Mingsheng Wang, and Wenling Wu. “Recursive di usion layers for 
(lightweight) block ciphers and hash functions”. In Lars R. Knudsen and Huapeng 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 159
Wu, editors, Selected Areas in Cryptography, volume 7707 of Lecture Notes in 
Computer Science, pages 355{371. Springer, 2013. 
[15]. Chand Gupta K., Ghosh Ray I. (2014) “On Constructions of Circulant MDS Matrices 
for Lightweight Cryptography”. In: Huang X., Zhou J. (eds) Information Security 
Practice and Experience. ISPEC 2014. Lecture Notes in Computer Science, vol 8434. 
Springer, Cham. 
[16]. Youssef, A.M., Mister, S., Tavares, S.E.: “On the Design of Linear Transformations 
for Substitution Permutation Encryption Networks”. In: Workshop On Selected Areas 
in Cryptography, SAC 1997, pp. 40–48 (1997). 
[17]. Sajadieh, M., Dakhilalian, M., Mala, H. et al. “On construction of involutory MDS 
matrices from Vandermonde Matrices in GF(2q)”. Des. Codes Cryptogr. (2012) 64: 
287. https://doi.org/10.1007/s10623-011-9578-x. 
ABSTRACT 
PROPOSING AN EFFICIENT IMPLEMENTATION METHOD FOR THE LARGE-
SCALE LINEAR LAYER IN BLOCK CIPHERS 
In this paper, we propose an efficient implementation method for large-scale 
linear layers. Especially for large-scale linear layers, the proposed method allows 
to retain the underlying arithmetic operations, but memory is reduced by half 
compared to the table-based approach commonly used in modern SPN ciphers. The 
approach in the paper is to use a lookup table technique when exploiting the 
properties of the recursive linear matrix, the Hadamard matrix, and the circular 
matrix. 
Key words: Linear layer, MDS matrix, Efficient implementation, SPN cipher. 
Nhận bài ngày 25 tháng 8 năm 2017 
Hoàn thiện ngày 22 tháng 9 năm 2017 
Chấp nhận đăng ngày 26 tháng 02 năm 2018 
Địa chỉ: Ban cơ yếu Chính phủ. 
*Email: thai_tranhong@gmail.com.