1. Giới thiệu

1.1. Giới thiệu

Trung tâm của stream cipher và block cipher là các hàm boolean.

Ở những bài viết ở phần "Đại số boolean và mật mã học" này mình sẽ mô tả các đặc trưng khi xây dựng các hệ mật mã dạng dòng (stream cipher) và khối (block cipher) từ các hàm boolean.

Nhắc lại, hàm boolean \(n\) biến là ánh xạ \(f\) từ \(\{ 0, 1 \}^n\) tới \(\{ 0, 1 \}\). Ở phần này mình sẽ sử dụng kí hiệu trường \(\mathbb{F}_2\). Như vậy hàm boolean trên \(n\) biến là ánh xạ

\[f: \mathbb{F}_2^n \to \mathbb{F}_2, \quad f(x_1, x_2, \ldots, x_n) = y.\]

Tiếp theo, khi "ghép" các hàm boolean lại ta có hàm boolean vector (hay vectorial Boolean function). Như vậy hàm boolean vector là ánh xạ

\[F: \mathbb{F}_2^n \to \mathbb{F}_2^m, \quad f(x_1, x_2, \ldots, x_n) = (y_1, y_2, \ldots, y_m) \in \mathbb{F}_2^m.\]

Như vậy chúng ta có thể coi mỗi hàm \(y_i = f_i(x_1, \ldots, x_n)\) là một hàm boolean nên khi ghép cạnh nhau chúng ta có hàm boolean vector.

\(x_1\)

\(x_2\)

\(\cdots\)

\(x_n\)

\(f_1(\bm{x})\)

\(f_2(\bm{x})\)

\(\cdots\)

\(f_m(\bm{x})\)

\(0\)

\(0\)

\(\cdots\)

\(0\)

\(f_1(0, \ldots, 0)\)

\(f_2(0, \ldots, 0)\)

\(\cdots\)

\(f_m(0, \ldots, 0)\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

\(\vdots\)

\(1\)

\(1\)

\(\cdots\)

\(1\)

\(f_1(1, \ldots, 1)\)

\(f_2(1, \ldots, 1)\)

\(\cdots\)

\(f_m(1, \ldots, 1)\)

Ở đây \(\bm{x} = (x_1, \ldots, x_n) \in \mathbb{F}_2^n\).

1.2. Bảng kí hiệu

Kí hiệu

Ý nghĩa

\(\mathcal{F}_n\)

Tập hợp tất cả hàm boolean \(n\) biến

\(\mathcal{L}_n\)

Tập hợp tất cả hàm boolean affine \(n\) biến

\(\mathcal{L}_n\)

Tập hợp tất cả hàm boolean tuyến tính \(n\) biến

\(\deg f\)

Bậc của hàm boolean \(f\) ở dạng chuẩn tắc đại số (ANF)

\(\mathrm{wt}(f)\)

Trọng số của hàm boolean \(f\)

\(N_f\)

Nonlinearity của hàm boolean \(f\)

\(W_f(\bm{a})\)

Hệ số Walsh của hàm \(f\) ứng với vector \(\bm{a}\)

1.3. Các tính chất mật mã của hàm boolean

1.3.1. Bậc đại số cao

Tham số \(\deg f\) phải cao. Điều này đặc biệt quan trọng trong các stream cipher sử dụng LFSR.

1.3.2. Nonlinearity cao

Nonlinearity cực kì quan trọng trong việc chống phá mã tuyến tính (linear cryptanalysis). Nonlinearity càng cao, dấu vết tuyến tính càng thấp.

Hàm boolean có nonlinearity cực đại được gọi là hàm bent (hay bent function).

Theo phần đại số boolean ở trước thì

\[N_f \leqslant 2^{n-1} - \dfrac{1}{2} \cdot 2^{n / 2 - 1}\]

khi \(n\) chẵn.

Điều kiện cần và đủ để tồn tại hàm boolean \(n\) biến là \(n\) chẵn.

Nếu \(n\) lẻ thì không tồn tại hàm bent \(n\) biến. Tuy nhiên chúng ta vẫn có thể xem xét các hàm có nonlinearity \(N_f\) lớn nhất và gọi chúng là Almost Bent (AB).

Khi đó

\[N_f \leqslant 2^{n-1} - 2^{(n-1) / 2}.\]

1.3.2.1. Bài tập

  1. Chứng minh rằng khoảng cách từ hàm boolean \(f\) với \(n\) biến tới hàm boolean affine

\[l_{\bm{a}, b}(\bm{x}) = a_1 x_1 \oplus \ldots \oplus a_n x_n \oplus b\]

với \(\bm{a} = (a_1, \ldots, a_n) \in \mathbb{F}_2^n\) và \(b \in \mathbb{F}_2\) được tính theo công thức:

\[ \begin{align}\begin{aligned}d(f, l_{\bm{a}, 0} (\bm{x})) = 2^{n-1} - \frac{1}{2} W_f(\bm{a}),\\d(f, l_{\bm{a}, 1} (\bm{x})) = 2^{n-1} + \frac{1}{2} W_f (\bm{a}).\end{aligned}\end{align} \]

  1. Chứng minh rằng nonlinearity của hàm boolean \(f\) bất kì được tính bởi công thức

\[N_f = 2^{n-1} - \frac{1}{2} \max_{\bm{y}} \lvert W_f (\bm{y}) \rvert.\]

  1. Chứng minh rằng hàm boolean \(f\) là hàm bent khi và chỉ khi \(W_f(\bm{y}) = \pm 2^{n/2}\) với mọi vector \(\bm{y}\).

1.3.3. Balanced

Hàm boolean được gọi là balanced (hay cân bằng, сбалансированный) nếu nhận giá trị \(0\) và \(1\) nhiều như nhau. Như vậy nếu hàm boolean \(f\) trên \(n\) biến cân bằng khi và chỉ khi

\[\mathrm{wt}(f) = 2^{n-1}.\]

Bài tập: Xác định số lượng hàm boolean cân bằng có \(n\) biến.

1.3.4. \(r\)-resillient

Đặt \(r\) là số nguyên không âm nhỏ hơn \(n\). Hàm boolean \(f\) với \(n\) biến được gọi là \(r\)-resillient (hay \(r\)-устойчивой) nếu với mọi hàm con mà nhận được từ việc cố định \(r\) biến thì đều là hàm cân bằng.

Hàm boolean này có độ an toàn cao hơn so với hàm cân bằng, giúp chống lại cách tấn công correlation cryptanalysis.

1.3.5. Correlation immune

Hàm boolean \(f\) với \(n\) biến được gọi là correlation immune of order \(r\) (корреляционно-иммунной порядка \(r\), tạm dịch là kháng tương quan bậc \(r\)) với \(1 \leqslant r \leqslant n\) nếu với mọi hàm con \(f^{a_1, \ldots, a_r}_{i_1, \ldots, i_r}\) nhận được từ việc cố định \(r\) biến thì đều thỏa đẳng thức

\[\mathrm{wt} (f^{a_1, \ldots, a_r}_{i_1, \ldots, i_r}) = \frac{\mathrm{wt}(f)}{2^r}.\]

1.3.5.1. Bài tập

  1. Chứng minh rằng hàm boolean \(f\) là \(r\)-resillient khi và chỉ khi nó cân bằng và correlation immune bậc \(r\).

  2. (Định lí Siegenthaler I, 1984). Chứng minh rằng nếu hàm boolean \(f\) là correlation immune bậc \(r\) thì \(\deg f + r \leqslant n\).

  3. (Định lí Siegenthaler II) Chứng minh rằng nếu hàm boolean \(f\) là \(r\)-resillient và \(r \leqslant n - 2\) thì \(\deg f + r \leqslant n - 1\).

Chứng minh cho các định lí Siegenthaler có thể tìm ở [13].

  1. Chứng minh rằng hàm boolean \(f\) là correlation immune bậc \(r\) khi và chỉ khi \(W_f(\bm{y}) = 0\) với mọi vector \(\bm{y}\) thỏa \(1 \leqslant \mathrm{wt} (\bm{y}) \leqslant r\).

Năm 2007 Д. Г. Фон–Дер–Флаасс tìm được chặn trên cho correlation immune của hàm boolean không cân bằng.

  1. (Định lí Д. Г. Фон–Дер–Флаасс, [14]). Gọi \(f\) là hàm boolean không cân bằng có correlation immune bậc \(r\) khác \(0\). Chứng minh rằng \(r \leqslant (2n/3) - 1\).

  2. Chứng minh rằng với hàm boolean \(r\)-resillient \(f\) sao cho \(r \leqslant n-2\) thì ta có bất đẳng thức \(N_f \leqslant 2^{n-1} - 2^{r+1}\) [15].

1.3.6. Algebraic immune

Tính chất này được giới thiệu vào năm 2004.

Algebraic immune (tạm dịch là kháng đại số) của hàm boolean \(f\) là số \(d\) nhỏ nhất sao cho tồn tại hàm boolean \(g\) bậc \(d\), không đồng nhất với \(0\), thỏa mãn \(f g = 0\) hoặc \((f \oplus \bm{1}) g = 0\).

Algebraic immune của hàm \(f\) được kí hiệu là \(\mathsf{AI}(f)\).

Ví dụ algebraic immune hàm \(f(\bm{x}) = x_1 x_2 x_3 \oplus x_1\) bằng \(1\), vì ta có thể chọn \(g(\bm{x}) = x_1 \oplus 1\). Khi đó \(f g = (x_1 x_2 x_3 \oplus x_1) (x_1 \oplus 1) = 1\).

1.3.6.1. Bài tập

  1. Chứng minh rằng algebraic immune của hàm boolean \(f\) bất kì với \(n\) biến không vượt quá giá trị \(\lceil n/2 \rceil\).

  2. Chứng minh một số tính chất cơ bản của algebraic immune:

    • \(\mathsf{AI}(f) \leqslant \deg f\);

    • \(\mathsf{AI}(f \cdot g) \leqslant \mathsf{AI}(f) + \mathsf{AI}(g)\);

    • \(\mathsf{AI}(f \oplus g) \leqslant \mathsf{AI}(f) + \mathsf{AI}(g)\);

    • \(\mathsf{AI}(f) = \mathsf{AI}(g)\) nếu \(g\) nhận được từ \(f\) qua một biến đổi affine trên các biến, nghĩa là \(g(\bm{x}) = f(\bm{A} \bm{x} \oplus \bm{b})\) với \(\bm{A}\) là ma trận khả nghịch bậc \(n\) và \(\bm{b}\) là vector.

  3. Xác định giá trị của \(\mathsf{AI}(f)\) với các hàm boolean sau và tìm hàm \(g\) tương ứng:

    • \(f(\bm{x}) = x_1 x_2 x_4 \oplus x_1 x_2 \oplus 1\);

    • \(f(\bm{x}) = 0\);

    • \(f(\bm{x}) = 1\);

    • \(f(\bm{x}) = x_1 \cdots x_k\) với \(k = 1, 2, \ldots, n\);

    • \(f(\bm{x}) = x_1 \oplus \ldots \oplus x_n\);

    • \(f(\bm{x}) = x_1 x_2 \oplus \ldots \oplus x_{n-1} x_n\) (tổng tất cả cặp tích);

    • \(f(\bm{x}) = x_1 x_2 x_3 x_4 \oplus x_5 x_6\).

  4. Cho ví dụ hàm boolean \(f\) với giá trị algebraic immune nhỏ nhất, nghĩa là \(\mathsf{AI}(f) = d\) với \(d = 1, 2, \ldots, k\).

1.3.7. Differentially \(\delta\)-uniform

1.3.7.1. Differential \(\delta\)-uniform

Khái niệm này lần đầu được định nghĩa trong [16].

Hàm boolean vector \(F : \mathbb{F}_2^n \to \mathbb{F}_2^n\) gọi là differentially \(\delta\)- uniform nếu với mọi vector \(\bm{a}\) khác không và vector \(\bm{b}\) bất kì thì phương trình

\[F(\bm{x}) \oplus F(\bm{x} \oplus \bm{a}) = \bm{b}\]

có không quá \(\delta\) nghiệm với \(\delta\) là số nguyên dương.

Để ý rằng nếu phương trình có nghiệm là \(\bm{x}\) thì cũng có nghiệm \(\bm{x} \oplus \bm{a}\). Số \(\delta\) càng nhỏ thì phép biến đổi của thuật toán mã hóa càng ít có dấu hiệu vi sai, tăng khả năng kháng phá mã vi sai.

Một cách tổng quát ta có định nghĩa sau.

Định nghĩa 1.60 (Differential \(\delta\)-uniform)

Hàm boolean vector từ \(\mathbb{F}_p^n\) tới \(\mathbb{F}_p^m\) được gọi là differential \(\delta\)- uniform nếu với mọi \(\bm{a} \in \mathbb{F}_p^n\) khác không và với mọi \(\mathbb{F}_p^m\) thì phương trình

\[F(\bm{x} + \bm{a}) - F(\bm{x}) = \bm{b}\]

có không quá \(\delta\) nghiệm.

Trong mật mã học thường dùng \(p = 2\). Thông thường các hàm boolean tập trung vào việc xây dựng các S-box nên \(n\) thường là \(4\) hoặc \(8\).

1.3.7.2. Perfect Nonlinear và Almost Perfect Nonlinear

Định nghĩa 1.61 (Hàm Perfect Nonlinear)

Hàm boolean vector \(F\) từ \(\mathbb{F}_p^n\) tới \(\mathbb{F}_p^m\) được gọi là hàm Perfect Nonlinear (PN) nếu phương trình

\[F(\bm{x} + \bm{a}) - F(\bm{x}) = \bm{b}\]

có đúng \(p^{n-m}\) nghiệm với mọi vector \(\bm{a} \in \mathbb{F}_p^n\) khác không và \(\bm{b} \in \mathbb{F}_p^m\).

Số lượng hàm PN rất ít. Đối với các giá trị \(n\) và \(p\) thường được sử dụng trong mật mã thậm chí không tồn tại hàm PN. Do đó chúng ta sẽ nới lỏng điều kiện thành hàm Almost Perfect Nonlinear (APN).

Định nghĩa 1.62 (Hàm Almost Perfect Nonlinear)

Hàm boolean vector \(F\) từ \(\mathbb{F}_p^n\) tới \(\mathbb{F}_p^m\) được gọi là hàm Almost Perfect Nonlinear (APN) nếu phương trình

\[F(\bm{x} + \bm{a}) - F(\bm{x}) = \bm{b}\]

có không quá hai nghiệm với mọi \(\bm{a} \in \mathbb{F}_p^n\) khác không và với mọi \(\bm{b} \in \mathbb{F}_p^m\).

Bài toán khó hiện nay là xây dựng hàm APN là song ánh với số biến \(n\) chẵn. Đặc biệt là \(n\) có dạng lũy thừa của \(2\).

Như vậy, theo định nghĩa có thể thấy điều tương đương sau

  • APN là differential \(2\)-uniform.

  • PN là differential \(1\)-uniform khi \(n = m\).

1.3.7.3. Hoán vị APN

Từ trước tới nay có ba phương pháp xây dựng hoán vị APN trên \(\mathbb{F}_2^n\). Tuy nhiên cả ba phương pháp chỉ hoạt động trên \(n\) lẻ. Câu hỏi về việc xây dựng hoán vị APN tới giờ vẫn là vấn đề mở với \(n\) chẵn, dặc biệt là \(n\) có dạng lũy thừa của \(2\) như đã nói ở trên.

1.3.7.4. Bài tập

Chứng minh hàm \(S : \mathbb{F}_2^8 \to \mathbb{F}_2^8\) của S-box trong thuật toán AES là differentially \(4\)-uniform.

Bài tập này cho thấy rằng S-box tốt thì \(\delta\) sẽ nhỏ nhất có thể nhằm kháng phá mã vi sai.