Một đề xuất ma trận MDS 4×4 an toàn, hiệu quả cho tầng tuyến tính của các mã pháp dạng AES

y y y y x x x x
y y y y x x x x
    
    
     
    
    
    
 (7) 
Từ biểu thức của ma trận ta thấy 4 giá trị 00 01 02, ,y y y và 03y được tính giống 
nhau khi nhân lần lượt hàng thứ nhất của ma trận tuyến tính với lần lượt các cột 
của ma trận dữ liệu. Ví dụ với 00y có: 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 139
1
00 00 10 20 30 00 10 20 30149 2y x x x x x x x x
          . 
Như vậy, để tính được toàn bộ 00 01 02, ,y y y và 03y cần 4x1 = 4 phép Xtime và 
4x3 = 12 phép XOR. Mặt khác ta thấy 12 giá trị yij, với 1 3,0 3i j    còn lại 
được tính giống nhau bởi 3 hàng còn lại trong ma trận tuyến tính có các số hạng 
giống nhau. Ví dụ với 10y có: 
1
10 00 10 20 30 00 10 20 304 149 2 2 2y x x x x x x x x
             . 
Biểu thức này yêu cầu 3 phép Xtime và 3 phép XOR. Như vậy, việc tính toàn 
bộ 12 giá trị yij, với 1 3,0 3i j    sẽ yêu cầu 12x3 = 36 phép Xtime và 12x3 = 
36 phép XOR. 
Từ đây, ta có độ phức tạp để thực hiện toàn bộ biến đổi MixColumns là 36 + 4 
= 40 phép Xtime và 36 + 12 = 48 phép XOR. 
Tương tự, độ phức tạp cho ma trận C.like2(2,Cir(1,223,2)) cũng là 40 phép 
Xtime và 48 phép XOR. Bảng 3 dưới đây là so sánh khả năng cài đặt trên môi 
trường 8 bit của các ma trận chúng tôi đề xuất, ma trận trong AES, trong [6] và 
trong [9]. 
Bảng 3. So sánh cài đặt kiểu bit-slice các ma trận MDS 4x4. 
Ma trận XOR Xtime Ghi chú 
Cir(2, 3, 1, 1) 60 16 [1] 
Cir(4, 149, 1, 1) 48 48 [9] 
Had(1, 2, 4, 145) 80 112 [6] 
C.like1(149,Cir(1,4,149)) 48 40 Đề xuất 
C.like2(2,Cir(1,223,2)) 48 40 Đề xuất 
Qua bảng phân tích ta thấy ma trận MDS trong AES yêu cầu số phép toán ít 
nhất, còn ma trận MDS Hadamard trong [6] là không hiệu quả khi cài đặt theo kiểu 
bit-slice và không thích hợp khi sử dụng trong cài đặt trên các môi trường hạn chế 
khi so sánh với ma trận MixColumns trong AES và các ma trận MDS tựa vòng mà 
chúng tôi đề xuất. Cần phải nói thêm rằng ma trận sử dụng trong biến đổi 
MixColumns AES là ma trận tối ưu nhất trong tất cả các ma trận MDS 4x4 trên 
82
 khi cài đặt theo kiểu bit-slice, tuy nhiên khi cài đặt phần cứng như phân tích ở 
mục trước thì ma trận chúng tôi đề xuất lại là ma trận tối ưu nhất. Ma trận tựa vòng 
chúng tôi đề xuất có độ phức tạp cài đặt theo kiểu bit-slice tốt hơn nghiên cứu 
trong [9] của tác giả Hoàng Văn Quân. 
Trên thực tế khi lựa chọn ma trận ta phải xét tất cả các tính chất có thể của nó. 
Do vậy, trong phần tiếp theo chúng tôi sẽ phân tích thêm một tính chất nữa, đó là 
số lượng điểm bất động của tầng tuyến tính. 
5. ĐIỂM BẤT ĐỘNG CỦA TẦNG TUYẾN TÍNH 
Như đã phân tích ở mục trước số nhánh là tham số quan trọng nhất của tầng 
tuyến tính, khi xây dựng tầng tuyến tính theo kiểu AES mà sử dụng ma trận MDS 
4x4 trong biến đổi MixColumns ta sẽ đảm bảo được tính chất theo chiến lược vệt 
lan rộng [7]. Khái niệm số lượng điểm bất động của tầng tuyến tính đưa ra trong 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Nguyễn Ngọc Điệp, “Một đề xuất ma trận MDS 4×4 an toàn các mã pháp dạng AES.” 140 
[5] sẽ là một tham số quan trọng khi lựa chọn tầng tuyến tính, nó ảnh hưởng đến độ 
an toàn và được xem như là một tham số bổ sung cho khái niệm số nhánh của tầng 
tuyến tính. 
Tầng tuyến tính trong AES gồm 2 biến đổi: ShiftRows và MixColumns. Khi kết 
hợp ta có thể biểu diễn bởi phép nhân một ma trận 16x16 [5]. 
Gọi ma trận tuyến tính 16x16 này là A. Đối với ma trận này có   16rank A  và 
  14rank A I  . Theo đó, số lượng điểm bất động của tầng biến đổi tuyến tính 
trong AES là 
      8 16 14 16
_ 2 2 2
n rank A rank A I
Cir AESN
     . Thực hiện tương tự đối 
với ma trận Had(1, 2, 4, 145) [6], ma trận Cir(4, 149, 1, 1) [9] và hai ma trận 
chúng tôi đề xuất là C.like1(149,Cir(1,4,149)) và C.like2(2,Cir(1,223,2)) chúng tôi 
nhận được: 
 1,2,4,145 1HadN  ,  4,149,1,1 1CirN  ,   1. 149, 1,4,149 1C like CirN  và   1. 2, 1,223,2 1C like CirN  . 
Như vậy, nếu sử dụng hai ma trận này để thay thế ma trận trong biến đổi 
MixColumns trong AES thì sẽ nhận được tầng tuyến tính mà chỉ có một điểm bất 
động, đây chính là điểm véc tơ 0 tầm thường. 
6. KẾT QUẢ THỰC NGHIỆM 
Chúng tôi thực hiện các thiết kế các khối chức năng của biến đổi MixColumns 
khi sử dụng ma trận đề xuất và một số ma trận đề xuất trước đó. Chương trình 
được viết trên ngôn ngữ VHDL cho Virtex6 XC6VLX240T–2FF1156. Công cụ 
thiết kế là Xilinx ISE phiên bản 14.3. Ví dụ minh họa mô phỏng Isim cho ma trận 
trong Cir(2, 3, 1, 1) sử dụng trong AES như trong hình 2 ta thấy rằng cài đặt này 
yêu cầu 4 xung nhịp. 
Hình 2. Kết quả mô phỏng đối với ma trận trong AES Cir(2, 3, 1, 1). 
Đối với ma trận đề xuất C.like1(149,Cir(1,4,149)). Hình 3 là mô phỏng Isim 
đối với ma trận đề xuất này. Trong cài đặt này ta thấy sau 3 clock cycle ta sẽ nhận 
được kết quả đầu ra tính từ thời điểm xuất hiện tín hiệu đầu vào. 
Hình 3. Kết quả mô phòng với ma trận đề xuất C.like1(149,Cir(1,4,149)). 
Thực hiện tương tự với những ma trận khác trong bảng 3 chúng tôi có thống 
kê tài nguyên và tốc độ trong bảng 4. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 141
Bảng 4. Tham số cài đặt phần cứng trên Virtex6 XC6VLX240T–2FF1156. 
Ma trận 
Slice 
Register
s 
LUT
-FF 
pairs 
LUT
s 
Cloc
k 
cycle
s 
Maximu
m 
Frequenc
y (MHz) 
Speed 
(Mbps
) 
Cir(2, 3, 1, 1) [1] 688 530 544 4 1225.415 39213 
Cir(4, 149, 1, 1) [9] 656 520 528 3 1225.415 52284 
Had(1, 2, 4, 145) [6] 702 546 560 4 1225.415 39213 
C.like1(149,Cir(1,4,14
9)) 
632 493 504 3 1225.415 52284 
C.like2(2,Cir(1,223,2)) 632 493 504 3 1225.415 52284 
Trong bảng này, ta thấy ma trận chúng tôi đề xuất có tham số cài đặt phần cứng 
tốt nhất, tốc độ xử lý dữ liệu vượt trội so với những ma trận còn lại và tương đương 
với ma trận trong [9]. 
Bảng 5. Kết quả thực nghiệm tốc độ mã hóa của AES sử dụng ma trận đề xuất. 
Phiên bản AES Quá trình 
Tốc độ 
MB/s cpb 
AES-128 
Mã hóa 204 12 
Giải mã 221 11 
AES-192 
Mã hóa 189 13 
Giải mã 185 13 
AES-256 
Mã hóa 165 15 
Giải mã 162 15 
Chúng tôi cũng tiến hành cài đặt phần mềm cho thuật toán AES, trong đó, sử 
dụng ma trận C.like1 để thay thế cho ma trận tuyến tính của AES. Cách tiếp cận ở 
đây là sử dụng bảng tra trên môi trường với thanh ghi 32 bit. Chương trình được 
viết trên ngôn ngữ C chuẩn, biên dịch sử dụng Visual Studio v10 trên máy Intel(R) 
Core(TM) i5-6200U CPU 2.4GHz, Ram 4.00GB, Windows 10. Trong chương 
trình không sử dụng bất kỳ một lệch assembler hay các hộ trợ SSE nào. Tốc độ 
được đo bằng MegaBytes/s (MB/s). 
Kết quả cài đặt trong bảng 5 là tương đương với cài đặt của AES [1]. 
7. KẾT LUẬN 
Trong bài báo này, chúng tôi đề xuất hai ma trận tuyến tính có tính chất mật mã 
tốt có thể thay thế ma trận trong biến đổi MixColumns trong AES. Ma trận này là 
một ma trận MDS tựa vòng trên trường hữu hạn. Khi sử dụng trong biến đổi 
MixColumns của AES sẽ nhận được tầng tuyến tính đảm bảo được số nhánh theo 
chiến lược vệt lan rộng mà không có điểm bất động như trường hợp ma trận gốc 
của AES. Ma trận đề xuất có cài đặt kiểu bit-slice có thể so sánh với ma trận gốc 
trong AES, và tốt hơn nhiều so với ma trận đề xuất trong [6] và [9]. Theo quan 
điểm cài đặt phần cứng ma trận của chúng tôi không những yêu cầu tài nguyên ít 
hơn mà còn có tốc độ xử lý dữ liệu cao hơn cả ma trận gốc trong AES, ma trận đề 
xuất trong [6] và ma trận trong [9]. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Nguyễn Ngọc Điệp, “Một đề xuất ma trận MDS 4×4 an toàn các mã pháp dạng AES.” 142 
Bằng lý thuyết tìm được nhiều đa thức sinh hơn thỏa mãn điều kiện trong mệnh 
đề 2 và 3. Từ đó, cho phép tìm được nhiều hơn các ma trận MDS có tính chất cài 
đặt tốt. 
Về mặt an toàn, ma trận của chúng tôi khi sử dụng trong tầng tuyến tính của AES 
không có điểm bất động, trong khi tầng tuyến tính của AES có 216 điểm bất động. 
TÀI LIỆU THAM KHẢO 
[1]. Зензин, О. and М. Иванов, "Стардарт криптографической защиты-AES. 
Конечные поля". 2002: КУДРИЦ-ОБРАЗ М. 
[2]. Guo, J., et al., "The LED block cipher", in Cryptographic Hardware and 
Embedded Systems–CHES 2011. 2011, Springer. p. 326-341. 
[3]. ГОСТ Р 34.11-2012: "Криптографическая защита информации". 
Функция хиширования. 2012: p. 25. 
[4]. Мак-Вильямс, Ф.Д., "Теория кодов, исправляющих ошибки". 1979. 
[5]. Z'aba, M.R., "Analysis of linear relationships in block ciphers". Luận án Tiến 
sĩ của Queensland University of Technology, 2010. 
[6]. Sim, S.M., et al. "Lightweight MDS Involution Matrices". in FSE. 2015. 
[7]. Daemen, J. and V. Rijmen, "The wide trail design strategy", in Cryptography 
and Coding. 2001, Springer. p. 222-238. 
[8]. P. Junod and S. Vaudenay, “Perfect diffusion primitives for block cipher – 
Building efficient MDS matrices”. In Selected Areas in Cryptology (SAC 
2004), LNCS 3357, pp. 84-99, Springer-Verlag, 2004. 
[9]. Hoàng Văn Quân. “Đề xuất ma trận MDS đạt hiệu năng cao khi cài đặt trên 
phần cứng cho các mã pháp dạng AES”. Tạp chí Nghiên cứu KH&CN quân 
sự, Số 40, 12 – 2015. 
ABSTRACT 
A PROPOSITION FOR THE SECURE AND EFFECTIVE 4 4 MDS 
MATRICES IN THE LINEAR LAYER OF AES-LIKE BLOCK CIPHERS 
 In this paper, we proposed and evaluated the linear layer which have 
effective implemented property on the hardware based on circulant matrices 
that can be used in designing a linear layer for AES-like block ciphers, while 
still guarantee implemented property on software as the liner layer in AES. 
We have evaluated the number of fixed points in the obtained liner layer and 
compared with the linear layer in AES. 
Key words: MDS matrix, The linear layer, AES. 
Nhận bài ngày 30 tháng 9 năm 2016 
Hoàn thiện ngày 19 tháng 10 năm 2016 
Chấp nhận đăng ngày 14 tháng 12 năm 2016 
Địa chỉ: Viện Khoa học – Công nghệ mật mã, Ban Cơ yếu Chính phủ; 
 * Email: diepnngoc@yahoo.com.