1. Về mã khối

Các mã khối hiện đại đều tuân thủ hai nguyên lý thiết kế, đó là nguyên lý xáo trộn (confusion) và nguyên lý khuếch tán (diffusion). Hai nguyên lý này nhằm làm cho quá trình tìm kiếm mối quan hệ thống kê giữa bản gốc và bản mã trở nên “không thể”. Bên cạnh tầng phi tuyến, tầng khuếch tán đóng một vai trò quan trọng đối với độ an toàn của mã khối. 

Mã khối có hai cấu trúc chính là cấu trúc Feistel và SPN (Substitution Permutation Networks), mỗi vòng của cấu trúc SPN gồm một tầng khuếch tán, tầng thay thế và tầng cộng khóa. Tầng khuếch tán đảm bảo rằng, sau một số vòng nhất định thì tất cả các bit đầu ra đều phụ thuộc vào tất cả các bit đầu vào, trong khi tầng thay thế hay tầng phi tuyến đảm bảo sự phụ thuộc này có tính chất phức tạp và phi tuyến. Hầu hết các tầng khuếch tán là các biến đổi tuyến tính có biểu diễn dạng ma trận trên GF(2^m) hoặc GF(2).

Một biến đổi tuyến tính cung cấp sự khuếch tán nhằm đáp ứng độ an toàn cho hàm vòng của một mã khối bằng cách xáo trộn các bit của khối đầu vào có kích cỡ cố định để tạo ra khối đầu ra tương ứng có cùng kích cỡ [3].

Nhiều mã khối sử dụng mã tách có khoảng cách cực đại (Maximum Distance Separable - MDS) và mã tuyến tính nhị phân khoảng cách cực đại (Maximum Distance Binary Linear - MDBL) cho tầng khuếch tán của chúng. Chẳng hạn, một số mã nổi tiếng như AES và Khazad sử dụng các mã MDS, Camellia và ARIA sử dụng các mã MDBL. Các tầng khuếch tán của các mã khối này được chỉ ra trong bảng dưới đây.

2. Các phương pháp đo độ khuếch tán của mã khối hiện nay

Ảnh hưởng thác đổ [2]

Sau năm 2000, dự án NESSIE (sau khi NIST tuyển chọn xong AES) đã đưa ra tiêu chuẩn về mức độ ảnh hưởng thác đổ (The avalanche effect - AC) để đánh giá các mã khối. Dự án NESSIE đánh giá thống kê mã khối, trong đó kiểm tra mức độ của tiêu chuẩn AC, ký hiệu là d_a.

Xét vectơ:

và vectơ:

đạt được bằng cách lấy phần bù bit thứ i của vectơ x (với i = 1, ..., n).

- Hàm thỏa mãn tiêu chuẩn AC:

Hàm f: (GF(2))ⁿ  -> (GF(2))^m được gọi là thỏa mãn tiêu chuẩn ảnh hưởng thác đổ nếu trung bình có ½ các bit ra thay đổi mỗi khi một bit vào đơn được thay đổi hay: 

Trọng số Hamming w(x) của x là số các thành phần khác 0 của vectơ x.

Ảnh hưởng thác đổ chặt [2]

Dự án NESSIE cũng đã đưa ra tiêu chuẩn về mức độ ảnh hưởng thác đổ chặt (The strict avalanche effect - SAC) để đánh giá các mã khối. Dự án NESSIE đánh giá thống kê mã khối, trong đó kiểm tra mức độ của tiêu chuẩn SAC, ký hiệu là d_sa.

- Hàm thỏa mãn tiêu chuẩn SAC: 

Hàm f: (GF(2))ⁿ  -> (GF(2))^m được gọi là thoả mãn tiêu chuẩn SAC nếu mỗi bit ra thay đổi với xác suất 1/2 mỗi khi một bit vào (đơn) được thay đổi, hay với mọi i = 1, ..., n và j = 1 , ..., m, ta có:

Thuộc tính đầy đủ [2]

Thuộc tính này là thuộc tính mong muốn của mỗi thuật toán mã hóa. Giả thuyết rằng, nếu chỉ có một vài bit đầu ra phụ thuộc vào một bit đầu vào, thì bằng cách quan sát một số lượng đáng kể của các cặp đầu ra, đầu vào, người thám mã có thể phát hiện được mối quan hệ thống kê và sử dụng thông tin này để tìm được khóa. Dự án NESSIE đã đưa ra tiêu chuẩn về mức độ của thuộc tính đầy đủ (the completeness property), ký hiệu là d_c.

- Hàm thỏa mãn tiêu chuẩn về thuộc tính đầy đủ:

Hàm f: (GF(2))ⁿ  -> (GF(2))^m  của n bit vào và m bit ra được gọi là thỏa mãn thuộc tính đầy đủ nếu mỗi bit ra phụ thuộc vào một bit vào, hay với mọi i = 1 ÷ n và j = 1 ÷ n ta được bit ra thứ j phụ thuộc vào bit vào thứ i tức là: tồn tại 

sao cho (f(xⁱ))_j ≠ (f(x))_j, ở đây có nghĩa là tồn tại vectơ

sao cho khi thay đổi bit vào thứ i thì sẽ làm thay đổi bit ra thứ j.

Số nhánh của biến đổi tuyến tính [1] 

Số nhánh (branch number) của một biến đổi tuyến tính L được ký hiệu là B(L), là số tối thiểu của hộp S hoạt động trong hai vòng liên tiếp bất kỳ của một mã khối có cấu trúc SPN. Trong đó, một hộp S song ánh được gọi là hoạt động nếu cả hai đầu vào và đầu ra của nó đều khác 0 trong một đặc trưng tuyến tính hoặc lượng sai.

Số nhánh được tính như sau: 

Giả sử: Z=(Z₀, Z₁,...,Zm-1) là một khối gồm mb bit được tạo thành bằng cách kết hợp m từ, mỗi từ gồm b bit. 

Giả sử

ký hiệu vectơ nhị phân độ dài m. Trong đó 

nếu Z_i ≠ 0 và =0 nếu Z_i=0

Giả sử 

định nghĩa trọng số Hamming, Số nhánh của L được ký hiệu bởi B(L) được mô tả như sau: 

Trong đó B(L) ≤ m+1.

Số nhánh B(L) là tối ưu nếu B(L)=m+1, mã tuyến tính được gắn với L sẽ có khoảng cách tối thiểu cực đại. Trong thực tế, để đạt được mã tuyến tính có khoảng cách tối thiểu cực đại, người ta xây dựng các mã MDS.

Điểm bất động trong biến đổi tuyến tính [1]

Xét các giá trị b-bit như là các phần tử thuộc trường F₂b và ký hiệu S là tập tất cả các vectơ trong F₂b với độ dài là:

Định nghĩa 

là ma trận không suy biến với các phần tử thuộc F₂q, là ma trận biểu diễn của một biến đổi tuyến tính L trên các phần tử của S. Trường  F₂q là tập con của  F₂b. Biến đổi tuyến tính L ánh xạ một phần tử

tới một phần tử

Với X = AZ được biểu diễn như sau:

Trong đó

Giả sử

biểu diễn ma trận cỡ m×m dựa trên ma trận đơn vị  

Trong đó, I₍₀₎ = I. Các phần tử của ma trận I_(l) được xác định bởi tham số dịch vòng 

trong đó

Chẳng hạn, ma trận I₍₁₎ và I₍₂₎ với m=4 được biểu diễn như sau:

Tập tất cả các điểm bất động của một biến đổi tuyến tính L được biểu diễn bởi một ma trận không suy biến A, có thể thu được bằng cách giải phương trình sau:

Với l=0, phương trình trên trở thành (A – I) Z =0. Nghiệm của phương trình này chính là các khối đầu vào mà khi đi qua biến đổi tuyến tính L sẽ cho khối đầu ra không thay đổi (bằng chính nó).

Với l>0, nghiệm của phương trình trên chính là tập các khối đầu vào thỏa mãn: khi đi qua biến đổi tuyến tính L ta chỉ cần quay vòng lb bit sang trái của khối đầu vào đó thì có thể thu được khối đầu ra. Giả sử ^Z biểu diễn các khối đầu vào thỏa mãn phương trình (5), khi đó ta có:

Số các khối đầu vào mà thỏa mãn mối quan hệ (5) được cho bởi:

Khi đó, độ khuếch tán được đo bởi phương pháp dựa trên số điểm bất động được ký hiệu bởi hệ số D(A), được định nghĩa như sau:

Trong đó, 2^-mb ≤ D(A) ≤ 1 và ma trận A biểu diễn dạng ma trận của biến đổi tuyến tính L. Hệ số D(A) biểu thị số trung bình của các khối đầu vào của L mà có mối quan hệ tuyến tính được cho bởi phương trình (5). Giá trị D(A) lớn nghĩa là có nhiều khối đầu vào không thay đổi bởi phép biến đổi tuyến tính L khi tạo khối đầu ra tương ứng. Giá trị số D(A) nhỏ nghĩa là có nhiều khối đầu vào được thay đổi hiệu quả bởi biến đổi tuyến tính L khi tạo ra các khối đầu ra tương ứng. Ngoài ra, hệ số D(A) còn biểu thị mức độ khuếch tán tốt đến đâu, nghĩa là nó có thể thể hiện biến đổi tuyến tính L thay đổi hiệu quả như thế nào các khối đầu vào khi tạo khối đầu ra tương ứng. Với phương pháp đo độ khuếch tán này, rõ ràng là không có sự khuếch tán đối với các kiểm bất động.

Kết luận

Để thiết kế một mã khối an toàn, người thiết kế phải quan tâm đến mọi thành phần của mã khối, trong đó tầng biến đổi tuyến tính vô cùng quan trọng quyết định độ an toàn của mã khối. Bài báo đã giới thiệu về tầng khuếch tán của một số mã khối và các phương pháp đánh giá mã khối cũng như đo độ khuếch tán của mã khối. Mỗi phương pháp thể hiện một góc nhìn khác nhau về toàn bộ mã khối và độ khuếch tán của tầng biến đổi tuyến tính trong mã khối và có thể là một sổ tay hữu ích cho các nhà nghiên cứu về mã khối.