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.

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 //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

‹ › ×

Tin liên quan

Xây dựng các ma trận MDS từ mã Gabidulin

13:00 | 17/02/2021

Ma trận MDS là một thành tố quan trọng trong việc xây dựng, thiết kế các mã khối an toàn. Bài báo này giới thiệu về mã Gabidulin (một mã tuyến tính trong lý thuyết mã) và cách xây dựng các mã MDS từ mã Gabidulin.

Xây dựng các ma trận MDS cặp đôi từ mã Reed-Solomon

15:00 | 24/09/2021

Bài báo này giới thiệu về MDS cặp đôi - một ma trận có dạng đối xứng đặc biệt và phương pháp xây dựng các ma trận này nhờ một mã cyclic nổi tiếng, đó là mã Reed-Solomon. Những ma trận dạng này có thể hữu ích trong việc nâng cao tốc độ xử lý hoặc hiệu quả trong thiết kế phần cứng.

SDK-AES: Thuật toán mã khối động ở cả tầng thay thế và khuếch tán

15:00 | 26/08/2019

Trong những năm gần đây, lĩnh vực mã khối động đã được nhiều nhà mật mã quan tâm nghiên cứu nhờ khả năng nâng cao độ an toàn của mã khối, chống lại nhiều loại thám mã khác nhau. Các mã khối có thể được “động hóa” ở một trong những thành phần của nó. Bài viết này giới thiệu thuật toán mã khối động SDK-AES có hai thành phần quan trọng được làm động, là tầng thay thế và tầng khuếch tán.

Tin cùng chuyên mục

INFOGRAPHIC: 6 cách bảo mật thông tin cá nhân trực tuyến

13:00 | 28/08/2024

Ngày nay, tin tức về các vụ vi phạm dữ liệu cá nhân trên không gian mạng không còn là vấn đề mới, ít gặp. Vậy làm thế nào để dữ liệu cá nhân của bạn không bị rơi vào tay kẻ xấu? Dưới đây là 6 cách để bảo vệ thông tin cá nhân khi trực tuyến.

Vai trò quan trọng của sự ngẫu nhiên thực trong Blockchain và Web3

10:00 | 22/03/2024

Với sự tương tác kinh tế, xã hội và văn hóa ngày càng diễn ra phổ biến trên Internet, nhu cầu ngày càng tăng trong vài thập kỷ qua nhằm bắt chước sự ngẫu nhiên của thế giới tự nhiên và tạo ra các hệ thống kỹ thuật số để tạo ra các kết quả không thể đoán trước. Các trường hợp sử dụng cho tính không thể đoán trước này bao gồm đưa vào sự khan hiếm nhân tạo, xây dựng các cơ chế bảo mật mạnh mẽ hơn và tạo điều kiện cho các quy trình ra quyết định trung lập đáng tin cậy. Trong bài viết này, tác giả sẽ phân tích tính ngẫu nhiên, tìm hiểu về các loại ngẫu nhiên và vai trò quan trọng của sự ngẫu nhiên đối với Blockchain và hệ sinh thái Web3.

Kỹ thuật iShutdown mới phát hiện phần mềm gián điệp trên iPhone

10:00 | 31/01/2024

Các nhà nghiên cứu tại hãng bảo mật Kaspersky đã phát triển một kỹ thuật mới có tên là iShutdown để có thể phát hiện và xác định các dấu hiệu của một số phần mềm gián điệp trên thiết bị iOS, bao gồm các mối đe dọa tinh vi như Pegasus, Reign và Predator. Bài viết sẽ cùng khám phát kỹ thuật iShutdown dựa trên báo cáo của Kaspersky.

Đảm bảo an toàn thông tin trên dịch vụ ứng dụng OTT

09:00 | 27/12/2023

Với sự phát triển mạnh mẽ của công nghệ thông tin hiện nay, các ứng dụng giải trí, nhắn tin, gọi điện đang dần trở nên phổ biến. Những dịch vụ truyền thông được cung cấp trực tiếp đến người xem thông qua Internet (Over The Top - OTT) trở thành một trong những mục tiêu bị tin tặc tấn công nhiều nhất. Bài báo đưa ra thực trạng sử dụng dịch vụ ứng dụng OTT tại Việt Nam và những thách thức trong công tác bảo đảm an ninh, an toàn thông tin trên các thiết bị di động và dữ liệu cá nhân trong thời gian qua. Từ đó, đưa ra các giải pháp nhằm nâng cao hiệu quả bảo đảm an ninh, an toàn thông tin cho dữ liệu cá nhân người dùng ứng dụng OTT trên nền tảng Internet trong thời gian tới.

Tin được quan tâm

Rò rỉ kênh kề trên điện thoại thông minh khi thực hiện mã hóa RSA

14:00 | 11/09/2024|Công nghệ PKI
Giải pháp di động hóa ứng dụng sử dụng trong mạng chuyên dùng có yếu tố bảo mật

11:00 | 03/09/2024|GP ATM

Kỹ thuật DNS Tunneling

08:00 | 26/08/2024|GP ATM
Top 5 dịch vụ lưu trữ email tốt nhất năm 2024

10:00 | 19/08/2024|Tin tức sản phẩm

Giải pháp khác

Các nhà mạng chạy đua thương mại hóa 5G

Trong cuộc đua 5G tại Việt Nam, Viettel đã vươn lên dẫn đầu khi trở thành nhà mạng đầu tiên chính thức tuyên bố khai trương mạng 5G. Trong khi đó, các nhà mạng khác cũng đang ráo riết chuẩn bị cho việc triển khai dịch vụ 5G, hứa hẹn một thị trường viễn thông sôi động và cạnh tranh trong thời gian tới.

09:00 | 29/10/2024
INFOGRAPHIC: Khám phá mô hình bảo mật Zero Trust
5G - Chìa khóa đi tới Công nghiệp 4.0
Ransomware: Phòng ngừa và giảm thiểu (Phần I)