Một số sai lầm trong nghiên cứu ma trận MDS
22:58 | 19/05/2015 | GP MẬT MÃ
Mã tách tuyến tính có khoảng cách cực đại (mã MDS) đã được nghiên cứu từ lâu trong lý thuyết mã sửa sai, nhưng gần đây khi mật mã hiện đại phát triển mạnh mẽ, thì việc nghiên cứu MDS để áp dụng vào mật mã đã phát triển rất nhanh chóng. Tuy nhiên, nhiều sai sót vẫn tồn tại, và rất may là chúng đã sớm được phát hiện.
1. MA TRẬN MDS
Mã MDS đã được nghiên cứu từ lâu trong lý thuyết mã sửa sai. Nếu C là mã tuyến tính với tham số [n,k,d], trong đó n là độ dài từ mã, k là độ dài bản rõ cần mã và d là khoảng cách của mã C thì người ta thấy rằng các tham số này sẽ thỏa mãn bất đẳng thức d <= k+1. Đó là giới hạn Singleton. Mã MDS là mã tuyến tính [n,k,d], trong đó d = n-k+1 nghĩa là nó tối ưu về khoảng cách mã. Mã MDS là trường hợp đặc biệt của mã Reed-Solomon.
Gắn với mã C là ma trận sinh G. Đó là ma trận có k hàng, n cột, có hạng k (k n) và khi cần mã một thông báo có độ dài k thì người ta thực hiện phép nhân véc tơ a với G như sau để được từ mã c có độ dài n: c = aG. Luôn luôn có thể đưa G về dạng G = [I | A], trong đó I là ma trận đơn vị bậc k, A là ma trận k hàng, n-k cột. Nếu C là mã MDS thì A được gọi là ma trận MDS.
Ma trận MDS được sử dụng trong tầng khuếch tán của nhiều mã khối như AES, SHARK, Square, Twofish, Anubis, KHAZAD, Manta, Hierocrypt, Camellia, trong mã dòng MUGI và hàm hash mật mã WHIRLPOOL. Đối với mã khối, độ an toàn chống lại các tấn công mạnh (như tấn công tuyến tính, tấn công lượng sai) phụ thuộc vào số nhánh của tầng khuếch tán. Số nhánh càng lớn thì độ an toàn càng cao. Điều đáng nói ở đây là, số nhánh của tầng khếch tán <= m+1, trong đó m là số đầu vào của tầng khuếch tán. Số nhánh này đạt giá trị lớn nhất nếu ma trận MDS được dùng trong tầng khuếch tán. Điều đặc biệt là, nếu số nhánh tuyến tính đạt giá trị lớn nhất thì số nhánh lượng sai cũng đồng thời đạt giá trị lớn nhất.
Do hữu ích như vậy nên ngoài cách xây dựng ma trận MDS từ mã MDS, ngày càng xuất hiện nhiều phương pháp khác được nghiên cứu để tạo ra chúng. Người ta chứng minh được rằng, ma trận A là ma trận MDS nếu và chỉ nếu mọi ma trận con, vuông của A đều không suy biến (tức là có định thức khác 0). Việc áp dụng tiêu chuẩn này cho phép nghiên cứu trực tiếp ma trận và tránh sử dụng mã MDS nhưng nếu áp dụng trực tiếp thì khá phức tạp, bởi lẽ số ma trận con của một ma trận là khá lớn. Chẳng hạn, nếu A là ma trận vuông cấp 4 thì số ma trận con vuông của nó là:
Trong nhiều nghiên cứu về ma trận MDS, đã có một số sai lầm và chúng được phát hiện nhờ tính chất nói trên. Phần sau chúng ta sẽ đề cập đến chúng.
2. MỘT SỐ SAI LẦM TRONG NGHIÊN CỨU MA TRẬN MDS
Trường hợp thứ nhất.
Trong [1], các tác giả đưa ra ma trận
và cho rằng đó là ma trận MDS. Tuy nhiên, ma trận con cấp 2 của nó:
được tạo từ các phần tử thứ 2 và thứ 4 trên dòng 1 và trên dòng 3 của ma trận ban đầu là suy biến. Vì vậy ma trận cấp 4 nói trên không là ma trận MDS.
Trường hợp thứ hai.
Trong [2], các tác giả đưa ra khái niệm ma trận mũ trực tiếp như sau:
Định nghĩa. Cho F là trường Galois. Đối với ma trận cho trước A = [aij]mxn, aij thuộc F, ta xác định
nó được gọi là ma trận mũ trực tiếp bậc e của A. Ma trận này còn được gọi là ma trận bình phương trực tiếp của A.
Sau đó, các tác giả đưa ra kết quả:
Mệnh đề. Cho F là trường Galois. Nếu:
là ma trận MDS thì A(2) cũng là ma trận MDS.
Tuy nhiên, trong [3] các tác giả đã chứng tỏ rằng mệnh đề trên là không chính xác. Để cụ thể, họ giả sử
Một mặt, họ chỉ ra rằng lập luận trong chứng minh của [2] có 2 điều không đúng.
Thứ nhất, trong [2] suy luận rằng hai dòng của ma trận S’ (có 2 dòng, 2 cột) không tỷ lệ nên nó là ma trận không suy biến. Rõ ràng suy luận này không chính xác, người ta có thể chỉ ra những ma trận cấp 2 suy biến nhưng hai hàng của nó không tỷ lệ nhau (có trong ví dụ ở dưới đây).
Thứ hai, đối với số k nào đó thuộc F, các tác giả nói rằng có thể đặt k = (k’)^2 với k’ thuộc F. Thật ra, nếu k F là thặng dư bậc hai thì tồn tại k’ như vậy. Ngược lại, sẽ không tồn tại k’ thỏa mãn k = (k’)^2 với mọi k’ thuộc F.
Mặt khác, họ đưa ra phản ví dụ để bác bỏ mệnh đề nêu trên bằng chính ma trận MDS trong AES:
Xét ma trận bình phương trực tiếp A^(2) của A. Dựa trên bảng nhân trong [4] đối với trường Galois
ta nhận được
Vì ma trận con của A^(2) ở góc trên bên trái có định thức bằng 0:
nên A^(2) không là ma trận MDS. Như vậy, tác giả của [3] kết luận rằng mệnh đề của [2] không đúng với p = 2.
Giả sử p > 2. Xét ma trận vuông bậc 3 trên GF(7):
Ta tính tất cả 19 định thức cả các ma trận con vuông bậc 1, 2 và 3 của nó và kiểm tra thấy rằng tất cả chúng đều khác 0 theo mô đun 7:
Nghĩa là, A là ma trận MDS. Mặt khác, với ma trận bình phương trực tiếp A^(2) của nó:
ta thấy rằng ma trận con
của A(2) là kỳ dị (suy biến) vì giá trị det = 0, nghĩa là ma trận A^(2) không là MDS.
của A(2) là kỳ dị (suy biến) vì giá trị det = 0, nghĩa là ma trận A^(2) không là MDS.
Phản ví dụ này chứng tỏ rằng mệnh đề nói trên của [2] nói chung không đúng đối với p > 2.
Trường hợp thứ ba.
Trong năm 2009, [5] đã đề xuất một ma trận cỡ 16x16 trên
bằng cách sử dụng ma trận Cauchy. Họ khẳng định ma trận của họ là MDS và đối hợp (involutory). Tuy nhiên trong [6] các tác giả đã chứng minh rằng ma trận đó không phải là MDS.
Trường hợp thứ tư.
Phản ví dụ trong trường hợp thứ hai có chỗ không chính xác. Đó là trường hợp ma trận MDS của AES:
Nếu áp dụng công thức do [3] dẫn ra
thì bản thân ma trận A cũng không phải là ma trận MDS, bởi ma trận con B cấp 2 ở góc trên bên trái của nó:
sẽ có định thức bằng 0, tức là suy biến. Sơ suất của [3] là ở chỗ xét việc tính toán ma trận A và ma trận bình phương trực tiếp của nó trên hai trường Galois khác nhau có cùng các phần tử.
Như vậy, đối với trường hợp GF(2^n), tính đúng đắn của mệnh đề nói trên cần được tiếp tục nghiên cứu sâu hơn.
3. KẾT LUẬN
Ma trận MDS đóng vai trò quan trọng trong mật mã, nhưng việc nghiên cứu thành công trong lĩnh vực này thật không dễ dàng. Tuy nhiên, ma trận MDS vẫn đang được tiến hành nghiên cứu mạnh mẽ. Điều đáng chú ý là, tuy những sai lầm là khó tránh khỏi nhưng chúng đã phát hiện sớm điều đó rất có ích đối với các ứng dụng mật mã.
|
TÀI LIỆU THAM KHẢO
[1]. Fatma Ahmed and Dalia Elkamchouchi, Strongest AES with S-Boxes Bank and Dynamic Key MDS Matrix (SDK-AES),International Journal of Computer and Communication Engineering, Vol. 2, No. 4, July 2013.
[2]. Murtaza G, Ikram N. Direct Exponent and Scalar Multiplication Classes of an MDS Matrix [EB/OL], (2011-01-10) [2011-04-15]. Cryptology ePrint Archive: Listing for 2011 , Available at http://eprint. iacr.orgl201 l/ 15 1.pdf.
[3]. Yang Jun, Mazhi-xia, YangJie, Cheng Jiang, On direct exponentiation of maximum distance separable matrices, Journal of Southwest University for Nationalities. Natural Science Edition, May 2011, 1003-2843(2011)03-0452-04
[4]. LIDL R, NIEDERREITER H. Finite Fields[M]. Addison-Wesley Publishing Company, 1983: 541-546.
[5]. Jorge Nakahara Jr and Elcio Abrah˜ao, A New Involutory MDS Matrix for the AES, International Journal of Network Security, Vol.9, No.2, PP.109–116, Sept. 2009
[6]. Kishan Chand Gupta and Indranil Ghosh Ray, On Constructions of Involutory MDS Matrices, Africacrypt 2013, LNCS 7918, pp. 43-60, 2013, Springer-Verlag Berlin Heidelberg
|
