Симметричная криптография

Lời giải cho quyển sách [20] của Н.Н. Токарева.

Глава 3. Булевы функции. Комбинаторный подход

Bài 16. Chứng minh rằng, hàm Boolean \(f\) tuyến tính khi và chỉ khi \(f(\bm{x} \oplus \bm{y}) = f(\bm{x}) \oplus f(\bm{y})\) với mọi \(\bm{x}\), \(\bm{y}\). Tương tự kiểm tra hàm Boolean là affine khi và chỉ khi \(f(\bm{x} \oplus \bm{y}) = f(\bm{x}) \oplus f(\bm{y}) \oplus f(\bm{0})\).

Chứng minh cho hàm tuyến tính

Chiều thuận. Nếu \(f\) là hàm tuyến tính thì nó có dạng

\[f(x_1, \ldots, x_n) = a_n x_n \oplus \cdots \oplus a_1 x_1\]

nên ta tính \(f(\bm{x} \oplus \bm{y})\) như sau

\[\begin{split}f(\bm{x} \oplus \bm{y}) & = a_n (x_n \oplus y_n) \oplus \cdots \oplus a_1 (x_1 \oplus y_1) \\ & = (a_n x_n \oplus \cdots \oplus a_1 x_1) \oplus (a_n y_n \oplus \cdots \oplus a_1 y_1) \\ & = f(\bm{x}) \oplus f(\bm{y}).\end{split}\]

Chiều nghịch. Với \(f(\bm{x} \oplus \bm{y}) = f(\bm{x}) \oplus f(\bm{y})\), đặt dạng ANF của \(f\) là

\[f(x_1, \ldots, x_n) = \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} x_{i_1} \cdots x_{i_k}\right) \oplus a_0.\]

Khi đó

\[f(\bm{x} \oplus \bm{y}) = \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} (x_{i_1} \oplus y_{i_1}) \cdots (x_{i_k} \oplus y_{i_k})\right) \oplus a_0,\]

và

\[\begin{split}f(\bm{x}) \oplus f(\bm{y}) & = \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} x_{i_1} \cdots x_{i_k}\right) \oplus a_0 \oplus \left(\bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} y_{i_1} \cdots y_{i_k}.\right) \oplus a_0 \\ & = \bigoplus_{k=1}^n \bigoplus_{i_1, \ldots, i_k} a_{i_1, \ldots, i_k} (x_{i_1} \cdots x_{i_k} \oplus y_{i_1} \cdots y_{i_k}).\end{split}\]

Như vậy, khi đồng nhất hệ số \(a_{i_1, \ldots, i_k}\) của \(f(\bm{x} \oplus \bm{y})\) và \(f(\bm{x}) \oplus f(\bm{y})\) thì ta có

\[(x_{i_1} \oplus y_{i_1}) \cdots (x_{i_k} \oplus y_{i_k}) = x_{i_1} \cdots x_{i_k} \oplus y_{i_1} \cdots y_{i_k}.\]

Ở vế trái khi khai triển ra ta sẽ nhận được các đơn thức dạng \(x_{i_1} y_{i_2} y_{i_3} \cdots y_{i_k}\) khi \(k > 1\), tuy nhiên ở vế phải chỉ có đúng hai đơn thức là \(x_{i_1} \cdots x_{i_k}\) và \(y_{i_1} \cdots y_{i_k}\). Do đó các hệ số \(a_{i_1, \ldots, i_k}\) với \(k > 1\) phải bằng \(0\). Hay nói cách khác bậc của ANF là \(1\). Ngoài ra \(f(\bm{x} \oplus \bm{y})\) có hệ số tự do \(a_0\) còn \(f(\bm{x}) \oplus f(\bm{y})\) thì không có nên khi đồng nhất hệ số cũng cho ta \(a_0 = 0\). Như vậy \(f\) là hàm tuyến tính.

Chứng minh cho hàm affine

Chiều thuận. Nếu \(f\) là hàm tuyến tính thì nó có dạng

\[f(x_1, \ldots, x_n) = a_n x_n \oplus \cdots \oplus a_1 x_1 \oplus a_0\]

và ta chứng minh tương tự cho trường hợp hàm tuyến tính với lưu ý \(f(\bm{0}) = a_0\).

Chiều nghịch. Chứng minh tương tự cho trường hợp hàm tuyến tính.

Bài 17. Tìm số đỉnh và số cạnh của đồ thị \(E^n\). Có bao nhiêu vector \(\bm{x}, \bm{y} \in E^n\) sao cho \(d(\bm{x}, \bm{y}) = k\)?

Mỗi đỉnh của \(E^n\) biểu diễn một vector dạng

\[(z_1, \ldots, z_n), \quad z_i \in \{ 0, 1 \}\]

nên \(E^n\) có \(2^n\) đỉnh. Mỗi đỉnh nối với \(n\) đỉnh khác (khác nhau chỉ ở vị trí \(z_i\)) nên \(\deg v_i = n\) với \(i = \overline{1, 2^n}\). Theo định lí cơ bản về số cạnh của đồ thị (Định lý 8) thì

\[\text{số cạnh} = \dfrac{1}{2} \sum_{i=1}^{2^n} \deg v_i = \dfrac{1}{2} \cdot n \cdot 2^n = n \cdot 2^{n-1}.\]

Để \(d(\bm{x}, \bm{y}) = k\) thì đầu tiên ta chọn \(k\) vị trí khác nhau với \(C_n^k\) cách. Với mỗi vị trí khác nhau ta có hai cách chọn \(x_i\) và \(y_i\) là

\[\begin{split}\begin{cases} x_i = 1 \\ y_i = 0 \end{cases}, \quad \text{hoặc} \ \begin{cases} x_i = 0 \\ y_i = 1 \end{cases}.\end{split}\]

Do đó có \(2^k\) cách chọn cho các vị trí khác nhau, còn \(n - k\) vị trí còn lại thì chọn tùy ý nên có \(2^{n-k}\) cách.

Đáp án là \(C_n^k \cdot 2^k \cdot 2^{n-k} = C_n^k \cdot 2^n\).

Bài 18. Tìm lực lượng của mặt cầu \(S_r(\bm{x}) = \{ \bm{y} : d(\bm{x}, \bm{y}) = r \}\) và hình cầu \(B_r(\bm{x}) = \{ \bm{y} : d(\bm{x}, \bm{y}) \leqslant r \}\).

Đối với mặt cầu thì đáp án chính là bài 17, nghĩa là \(\lvert S_r(\bm{x}) \rvert = 2^r \cdot C_n^r\).

Đối với hình cầu \(B_r(\bm{x})\) ta xét tất cả giá trị từ \(0\) tới \(r\):

  • khi \(d(\bm{x}, \bm{y}) = 0\) thì có \(2^n \cdot C_n^0\) cách chọn;

  • khi \(d(\bm{x}, \bm{y}) = 1\) thì có \(2^n \cdot C_n^1\) cách chọn;

  • tương tự, khi \(d(\bm{x}, \bm{y}) = i\) thì có \(2^n \cdot C_n^i\) cách chọn;

  • cho tới khi \(d(\bm{x}, \bm{y}) = r\) thì có \(2^n \cdot C_n^r\) cách chọn.

Như vậy lực lượng của hình cầu là tổng tất cả giá trị trên:

\[\lvert B_r(\bm{x}) \rvert = 2^n \cdot (C_n^0 + C_n^1 + \cdots + C_n^r).\]