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

13:00 | 17/02/2021 | GP MẬT MÃ

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.

Trong tài liệu [1], tác giả Thierry P. Berger và các cộng sự đưa ra phương pháp xây dựng các mã MDS bằng cách mở rộng các mã Gabidulin. Phương pháp này sử dụng các mã tối ưu trên một trường cơ sở bên dưới.

Khoảng cách hạng

Khoảng cách hạng được giới thiệu bởi E. Gabidulin vào năm 1985, chi tiết về độ đo này được trình bày trong [2].

Cho K = GF(q^m) là một mở rộng bậc m của trường hữu hạn GF (q), q = p^r không cần là nguyên tố, trường GF(q) được xét như “trường cơ sở” trong phương pháp này. Cho E = Kⁿ là không gian vectơ n chiều trên K.

Định nghĩa 1 ([1]). Với Xây dựng các ma trận MDS từ mã Gabidulin

trọng số hạng rk (a) của a là số chiều của không gian vectơ được sinh bởi { a₁,...a_n}, tức là bằng số các phần tử của a độc lập tuyến tính.

Vì

nên

với

Tương đương, trọng số hạng của a là hạng của ma trận m x n trên GF(q) được tạo bằng cách mở rộng mọi tọa độ a_itrên cơ sở của K/ GF (q). Giá trị của trọng số hạng là độc lập với cơ sở được chọn.

Ví dụ 1. Cho Xây dựng các ma trận MDS từ mã Gabidulin

(mở rộng của GF(2) theo đa thức x³ + x +1). Khi đó, nếu

là nghiệm của đa thức đó thì

. Cho n = 5. Đặt

. Trong các thành phần của a, chỉ có hai trong chúng là độc lập tuyến tính, vì vậy rk(a) =2.

Xét ma trận do khai triển mỗi tọa độ a_i theo cơ sở của K là Xây dựng các ma trận MDS từ mã Gabidulin

(viết theo cột):

nó cũng có hạng là 2.

Cho a và b là hai phần tử của E. Quan hệ d_r(a,b) = rk (a - b) xác định một khoảng cách trên E. Theo định nghĩa này, có thể định nghĩa khoảng cách hạng tối thiểu d_r của một mã C, cũng giống như độ đo Hamming. Nếu d_h chỉ khoảng cách Hamming truyền thống, thì với mọi a,b trong E, khoảng cách hạng thoả mãn bất phương trình: Xây dựng các ma trận MDS từ mã Gabidulin

Như vậy, với mọi Xây dựng các ma trận MDS từ mã Gabidulin

, hạng của x thoản mãn

Tồn tại một giới hạn đối với khoảng cách hạng tối thiểu của một mã, tương tự như giới hạn Singleton đối với khoảng cách Hamming:

Mệnh đề 1 ([2]): Nếu C là một mã tuyến tính độ dài n, số chiều k và khoảng cách hạng d_r, thì:

Nếu

Một mã khoảng cách hạng cực đại (MRD) là một mã đạt được giới hạn trên, Lưu ý rằng, nếu Xây dựng các ma trận MDS từ mã Gabidulin

thì mã MRD cũng là một mã MDS.

Mã Gabidulin

Trong bài [2], Gabidulin đã mô tả một lớp các mã MRD với Xây dựng các ma trận MDS từ mã Gabidulin

, còn được gọi là mã Gabidulin.

Định nghĩa 2 ([1]). Cho Xây dựng các ma trận MDS từ mã Gabidulin

với

và chúng độc lập tuyến tính trên GF (q). Mã Gabidulin

có giá

và số chiều k, là một mã được sinh bởi ma trận:

trong đó

Định nghĩa này gần với mã Reed-Solomon (RS): tập các phần tử khác nhau được thay thế bởi một tập các phần tử độc lập tuyến tính và lũy thừa truyền thống Xây dựng các ma trận MDS từ mã Gabidulin

được thay thế bởi “lũy thừa Frobenius” . Mã

đã được xem như ước lượng của các đa thức bậc nhỏ hơn k trên một tập gồm n phần tử. Có thể có sự giải thích tương đương về mã Gabidulin như là ước lượng của các đa thức tuyến tính hóa trên một tập gồm n phần tử độc lập tuyến tính:

Định nghĩa 3 ([1]). Một đa thức tuyến tính hóa Xây dựng các ma trận MDS từ mã Gabidulin

là một đa thức có dạng:

Nếu bậc của đa thức tuyến tính hóa f(X) là [r], thì r được gọi là bậc tuyến tính của f(X) và được ký hiệu là Xây dựng các ma trận MDS từ mã Gabidulin

Tập các đa thức được tuyến tính hóa là đẳng cấu với tập các ứng dụng tuyến tính - GF(q) của K vào chính nó [3].

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

là tập các giá trị từ

trong đó f(X) là đa thức tuyến tính hóa bất kỳ với bậc tuyến tính nhỏ hơn k (f(X) là biểu diễn của thông báo: Từ mã =”thông báo”.

Các tác giả đưa ra chứng minh ngắn gọn của định lý sau ([84]):

Định lý 1 ([1]). Mã Gabidulin Xây dựng các ma trận MDS từ mã Gabidulin

là MRD.

Chứng minh:

Cho

là một phần tử của

gắn với đa thức tuyến tính hóa f(X). Cho

là nhân của

và

là không gian vectơ trên GF(q) được sinh bởi

. Hạng của x là số chiều của

Vì bậc tuyến tính của f(X) nhỏ hơn k nên số chiều của V nhỏ hơn k. Điều này kéo theo Xây dựng các ma trận MDS từ mã Gabidulin

. Khoảng cách hạng của mã này là lớn hơn hoặc bằng n - k +1 , nghĩa là

. Từ giới hạn của Mệnh đề 1, suy ra

Mở rộng của mã Gabidulin

Độ dài của các mã Gabidulin tương đối ngắn (độ dài của mã nhiều nhất bằng m) so với q^m Mục tiêu của các tác giả trong [1] là mở rộng các mã Gabidulin bằng cách thêm vào điểm ước lượng của đa thức tuyến tính hóa.

Cho

là một tập gồm n phần tử khác nhau (tập a chưa chắc độc lập tuyến tính). Có thể n>m. Xét một mã tuyến tính C_a,k nhận được bằng cách ước lượng các đa thức được tuyến tính hóa với bậc tuyến tính nhỏ hơn k trên tập a:

: đa thức tuyến tính hóa,

Đặt

(Giả thiết rằng Xây dựng các ma trận MDS từ mã Gabidulin

Mệnh đề 2 ([1]). Khoảng cách hạng d_r của mã Xây dựng các ma trận MDS từ mã Gabidulin

Chứng minh:

Không mất tính tổng quát, giả sử rằng vectơ Xây dựng các ma trận MDS từ mã Gabidulin

có hạng

(tập á độc lập tuyến tính). Khi đó mã C_ák là một mã Gabidulin với khoảng cách hạng là r - k +1. Vì tất cả các cột ma trận sinh của C_ak là các tổ hợp tuyến tính trên GF(q) của các cột trong ma trận sinh của C_ák, khi đó khoảng cách hạng tối thiểu của C_ak sẽ bằng với khoảng cách hạng tối thiểu của C_ák.

Khoảng cách hạng là cực đại nếu a là một hệ sinh của K, nghĩa là rk(a) = m. Tuy nhiên khoảng cách hạng của các mã như vậy bị chặn trên bởi m - k + 1.

Đối với khoảng cách Hamming khoảng cách hạng được mở rộng hơn, bởi vì Xây dựng các ma trận MDS từ mã Gabidulin

Hệ quả 1 ([1]). Khoảng cách Hamming d_h của mã C_ak lớn hơn hoặc bằng rk(a) - k +1.

Tuy nhiên, có thể xây dựng một mã C_ak với khoảng cách Hamming tốt.

Bổ đề 1 ([1]). Giả sử f(X) là một đa thức tuyến tính hóa và Xây dựng các ma trận MDS từ mã Gabidulin

. Trọng số Hamming của f(a) bằng n - s, trong đó s là số lượng các phần tử của a trong V.

Các tác giả tiếp tục đưa ra mệnh đề sau:

Mệnh đề 3 ([1]). Khoảng cách Hamming tối thiểu của mã C_a,k là d_h = n - s, trong đó s là số lượng cực đại của các phần tử của a được chứa trong cùng không gian vectơ V với số chiều k-1.

Chứng minh:

Giả sử rằng chính xác Xây dựng các ma trận MDS từ mã Gabidulin

phần tử của a là trong cùng không gian vectơ V với số chiều k -1. Định nghĩa

, là một đa thức tuyến tính hóa với bậc tuyến tính là k-1. Rõ ràng f(a) là nằm trong C_ak . Từ bổ đề 1, có

. Điều này có nghĩa rằng

Ngược lại, giả sử Xây dựng các ma trận MDS từ mã Gabidulin

là một phần tử của C_ak và

. Nếu

là số lượng các phần tử của a trong V, khi đó

. Vì

nên

. Kéo theo

, khi đó ta có d_h = n-s.

Định lý sau đây khẳng định đặc trưng của các mã C_ak để là MDS.

Định lý 2 ([1]). Một mã C_ak là MDS nếu và chỉ nếu tập bất kỳ gồm k phần tử của a là độc lập tuyến tính.

Chứng minh:

Nếu tập bất kỳ gồm k phần tử của a là độc lập tuyến tính thì số lượng cực đại của các phần tử của a được chứa trong một không gian vectơ k-1 chiều bằng s=k-1. Khi đó, khoảng cách tối thiểu của một mã như thế sẽ bằng d_h=n-(k-1) = n-k+1. Do vậy, đây là một mã MDS.

Ngược lại, nếu C_ak là mã MDS thì dh =n-(k-1). Có nghĩa là s=k-1 , hay không gian vectơ k-1 chiều bất kỳ V chứa nhiều nhất k-1 phần tử của a. Điều này tương đương với khẳng định “tập bất kỳ k phần tử của a là độc lập tuyến tính”.

Xây dựng ma trận MDS có tính chất MRD

Cố định q=2 và m=2r. Chọn cơ sở B={b₁,b₂,...b_m} của K trên F=GF(2) và n=m. Khi đó mã Gabidulin G_B,r là mã MRD và có các tham số [m=2r,r,r+1] (G_B,r cũng là mã MDS) trên K (r là độ dài tin k).

Nếu A là ma trận vuông cỡ r trên K sao cho [I_r,A] là ma trận sinh chuẩn của G_B,r thì A là ma trận MDS trên K. Ma trận này cho độ khuếch tán cực đại trên r khối có cỡ m=2r nhưng lại có thêm tính chất MRD.

Ví dụ 2. Chọn m=8, r=4. Giả sử

là nghiệm của đa thức nguyên thủy x⁸+x⁴+x³+x²+1. Đặt B={1,a, a²,…, a⁷} là cơ sở của K trên F. Ma trận MDS A được xác định từ mã Gabidulin G_B,4 là:

Ma trận A này có cùng các tham số như MixColumns, r=4 là cỡ cực đại của ma trận MDS có tính chất MRD trên GF(2⁸).

Có thể chọn n<m điểm độc lập tuyến tính của K, khi đó ta nhận được ma trận khuếch tán r x r trên K với n = 2r. Ví dụ nếu cố định m=16, có thể thiết lập ma trận khuếch tán MDS có cỡ Xây dựng các ma trận MDS từ mã Gabidulin

Giả sử n>m và n=2k, khi đó mã MRD không nhất thiết là MDS (nói chung không là MDS). Trước đây, người ta đã thiết lập mã MDS có độ dài n>m bằng cách mở rộng các điểm ước lượng của đa thức tuyến tính hóa. Tuy nhiên, các mã này không còn là MRD nữa, các tham số của chúng bị hạn chế nên không thể vượt qua tỷ lệ ½ (tức là mã tuyến tính có n=2k). Những mã Gabidulin mở rộng này dường như không thích hợp để xây dựng các tầng khuếch tán MDS và không có tính chất bổ sung so với mã Reed-Solomon.

So sánh các phương pháp xây dựng ma trận MDS từ mã MDS

Sau đây, tác giả bài báo đưa ra bảng so sánh hai phương pháp xây dựng các ma trận MDS từ các mã MDS, bao gồm mã RS và mã Gabidulin.

Bảng 1. So sánh phương pháp từ mã RS và mã Gabidulin

Kết luận

Bài báo này giới thiệu một phương pháp xây dựng các mã MDS bằng cách mở rộng các mã Gabidulin để từ đó có thể trích rút ra được các ma trận MDS từ các mã MDS này. Phương pháp này sử dụng các mã tối ưu trên một trường cơ sở bên dưới do tác giả Thierry P. Berger và các cộng sự đã đưa ra trong tài liệu [1]. Bài báo cũng đưa ra so sánh các phương pháp xây dựng ma trận MDS từ các mã MDS như mã RS và mã Gabidulin. Việc nghiên cứu các phương pháp khác nhau trong việc xây dựng các ma trận MDS sẽ hữu ích cho các nhà nghiên cứu để tìm ra những ma trận MDS tốt nhất theo nhiều tiêu chí khác nhau nhằm xây dựng các mã khối an toàn, hiệu quả trong thực thi.

TÀI LIỆU THAM KHẢO

[1] Thierry P. Berger, Alexei V. Ourivski, Construction of new MDS codes from Gabidulin codes, LACO, University of Limoges, France, 2013.

[2] E. M. Gabidulin. Theory of codes with maximal rank distance. Problems of Information Transmission, 21:1-12, July 1985.

[3] R. Lidl, H. Niederreiter. Finite ﬁelds and their applications. Cambridge University Press.

[4] R. F. Babindamana and C. T. Gueye, Gabidulin Codes that are Generalized Reed Solomon Codes, International Journal of Algebra, Vol. 4, 2010, no. 3, Insert Cell After119 – 142.

TS. Trần Thị Lượng (Học viện Kỹ thuật mật mã)

‹ › ×

Tin liên quan

Ma trận các mối đe dọa chỉ ra các tấn công hệ thống học máy

17:00 | 19/11/2020

Gầy đây, các nhà nghiên cứu bảo mật đã tạo ra phiên bản đầu tiên của “Ma trận các mối đe dọa tấn công hệ thống ML”, giúp các nhà phân tích bảo mật phát hiện và ứng phó với các mối đe dọa tấn công hệ thống học máy mới nổi.

Một số sai lầm trong nghiên cứu ma trận MDS

22:58 | 19/05/2015

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.

Tin cùng chuyên mục

Tần số vô tuyến: Mối đe dọa trên không đối với các tổ chức doanh nghiệp

08:00 | 20/10/2020

Ngày nay, khi chính phủ các nước cam kết bảo vệ quốc gia và các tổ chức/doanh nghiệp tăng cường bảo vệ an toàn không gian mạng, thì mối đe dọa thầm lặng và lén lút vẫn còn, đó là gián điệp tần số vô tuyến.

Information Leakage Through Electromagnetic Radiation of PS/2 Keyboard

08:00 | 19/06/2020

CSKH02.2019 - (Abstract) - Computer keyboards are often used to enter data for a computer system, data could be normal information or confidential information such as password, key. Keyboards use electronic components so they will generate electromagnetic radiation that can reveal information. This article presents the acquisition of electromagnetic emanating from the PS/2 keyboards through different paths (in space, through power line or via LAN cable). After acquisition we develop a program on MATLAB to recover the keystroke signal from data which is obtained in the near field of PS/2 keyboard. The result of this side channel attack is recovered an average of more than 70% of the keystrokes in near field of PS/2 keyboards. Our best attack can recover up to more than 90% of the keystrokes. From this result, we conclude that PS/2 keyboards generate electromagnetic radiations which can cause the loss of information and they are not safe to use when entering confidential information.

Phương thức xây dựng và quản lý hệ thống mạng zero-trust

15:00 | 20/05/2020

Trong khi đội ngũ hệ thống mạng là đội ngũ chịu trách nhiệm chính trong việc triển khai các thành phần của hệ thống mạng zero-trust cho tổ chức/doanh nghiệp (TC/DN), thì đội ngũ bảo mật cần tham gia vào việc phát triển nền tảng zero-trust tổng thể.

p-giá trị và những điều cần biết

15:00 | 20/04/2020

Ngẫu nhiên hay các bộ tiêu chuẩn thống kê kiểm tra tính ngẫu nhiên của một dãy bit nhị phân (hoặc của một nguồn nhị phân) là điều thường được nhắc đến trong mật mã [1]. Trong kiểm định giả thiết thống kê, các nhà khoa học mật mã thường dùng đến một đại lượng được gọi là p-giá trị. Bài viết này sẽ giới thiệu đôi nét về lịch sử phát triển, cách sử dụng và ý nghĩa của p-giá trị.