1.3. Difference và differential

Ở phần này, kí hiệu \(\boxplus\) là phép cộng modulo \(2^n\), \(\boxminus\) là phép trừ modulo \(2^n\), và \(\oplus\) là toán tử bitwise-XOR.

Nếu số nguyên \(a\) có \(n\) bit và biểu diễn dưới dạng

\[a = a_0 + 2 a_1 + 2^2 a_2 + \cdots + 2^{n-1} a_{n-1}\]

thì số nguyên \(a\) tương đương với vector

\[(a_0, a_1, a_2, \ldots, a_{n-1}) \in \mathbb{F}_2^n.\]

Như vậy, phần tử \(a \in \mathbb{Z}_{2^n}\) tương đương phần tử \((a_0, a_1, \ldots, a_{n-1}) \in \mathbb{F}_2^n\) và các bạn cần lưu ý rằng phép \(\boxplus\) và \(\boxminus\) thực hiện trên \(\mathbb{Z}_{2^n}\), còn phép XOR thực hiện trên \(\mathbb{F}_2^n\).

Cụ thể hơn, giả sử

\[\begin{split}a & = a_0 + 2 a_1 + 2^2 a_2 + \cdots + 2^{n-1} a_{n-1}, \\ b & = b_0 + 2 b_1 + 2^2 b_2 + \cdots + 2^{n-1} b_{n-1},\end{split}\]

thì ta có

\[\begin{split}a \boxplus b = a + b \bmod 2^n, \quad a \boxminus b = a - b \bmod 2^n, \\ a \oplus b = c = c_0 + 2 c_1 + \cdots 2^{n-1} c_{n-1}, \ \text{với} \ c_i = a_i \oplus b_i.\end{split}\]

Ví dụ, với \(n = 4\), xét các số nguyên \(4\) bit là \(a = 9\) và \(b = 11\). Khi đó

\[a \boxplus b = 4, \ a \boxminus b = 14, \ a \oplus b = 2.\]

1.3.1. Difference (hiệu)

Giả sử ta có hàm \(f: \mathbb{Z}_{2^n} \to \mathbb{Z}_{2^m}\), khi đó với hai phần tử \(a, b \in \mathbb{Z}_{2^n}\) thì ta nói

• \(b \boxminus a\) là hiệu đầu vào;

• \(f(b) \boxminus f(a)\) là hiệu đầu ra.

Dưới góc độ phá mã, với \(\delta \in \mathbb{Z}_{2^n}\) và \(\Delta \in \mathbb{Z}_{2^m}\) cố định, ta xem xét có bao nhiêu cặp \(a, b \in \mathbb{Z}_{2^n}\) mà

\[b \boxminus a = \delta, \quad f(b) \boxminus f(a) = \Delta.\]

Chuyển vế ta có các đẳng thức trên tương với

\[b = a \boxplus \delta \Longrightarrow f(b) = f(a \boxplus \delta) = f(a) \boxplus \Delta.\]

Nói cách khác, ta xem xét xác suất

\[\mathrm{adp}^f(\delta \mapsto \Delta) = \Pr\left[f(a \boxplus \delta) = f(a) \boxplus \Delta\right]\]

với mọi \(a \in \mathbb{Z}_{2^n}\).

Tổng quát, nếu ta xét \(k\) hiệu đầu vào \(\alpha_0\), \(\alpha_1\), ..., \(\alpha_{k-1}\) và hiệu đầu ra \(\alpha_k\) thì ta quan tâm xác suất

\[\mathrm{adp}^f(\alpha_0, \alpha_1, \ldots, \alpha_{k-1} \mapsto \alpha_{k}) = \Pr\left[f(x_0 \boxplus \alpha_0, x_1 \boxplus \alpha_1, \ldots, x_{k-1} \boxplus \alpha_{k-1}) = f(x_0, x_1, \ldots, x_{k-1}) \boxplus \alpha_{k}\right].\]

Ví dụ 1.33

Xét hàm \(f(x, y) = x \oplus y\) với \(x, y \in \mathbb{Z}_{2^n}\). Với \(\alpha\), \(\beta\) và \(\gamma\) thuộc \(\mathbb{Z}_{2^n}\) ta xem xét

\[\mathrm{adp}^f(\alpha, \beta \mapsto \gamma) = \Pr\left[(x \boxplus \alpha) \oplus (y \boxplus \beta) = (x \oplus y) \boxplus \gamma\right].\]

1.3.2. Differential (vi sai)

Giả sử ta có hàm \(f: \mathbb{Z}_{2^n} \to \mathbb{Z}_{2^m}\), khi đó với hai phần tử \(a, b \in \mathbb{Z}_{2^n}\) thì ta nói

• \(b \oplus a\) là vi sai đầu vào;

• \(f(b) \oplus f(a)\) là vi sai đầu ra.

Ở đây cần lưu ý rằng, vi sai bản chất là phép trừ, nhưng trên \(\mathbb{F}_2^n\) thì phép trừ cũng chính là phép cộng \(\oplus\).

Tương tự, dưới góc độ phá mã, với \(\delta \in \mathbb{Z}_{2^n}\) và \(\Delta \in \mathbb{Z}_{2^m}\) cố định, ta xem xét có bao nhiêu cặp \(a, b \in \mathbb{Z}_{2^n}\) mà

\[b \oplus a = \delta, \quad f(b) \oplus f(a) = \Delta.\]

Chuyển vế ta có các đẳng thức trên tương với

\[b = a \oplus \delta \Longrightarrow f(b) = f(a \oplus \delta) = f(a) \oplus \Delta.\]

Nói cách khác, ta xem xét xác suất

\[\mathrm{xdp}^f(\delta \mapsto \Delta) = \Pr\left[f(a \oplus \delta) = f(a) \oplus \Delta\right]\]

với mọi \(a \in \mathbb{Z}_{2^n}\).

Tổng quát, nếu ta xét \(k\) hiệu đầu vào \(\alpha_0\), \(\alpha_1\), ..., \(\alpha_{k-1}\) và hiệu đầu ra \(\alpha_k\) thì ta quan tâm xác suất

\[\mathrm{adp}^f(\alpha_0, \alpha_1, \ldots, \alpha_{k-1} \mapsto \alpha_{k}) = \Pr\left[f(x_0 \oplus \alpha_0, x_1 \oplus \alpha_1, \ldots, x_{k-1} \oplus \alpha_{k-1}) = f(x_0, x_1, \ldots, x_{k-1}) \oplus \alpha_{k}\right].\]

Ví dụ 1.34

Xét hàm \(f(x, y) = x \boxplus y\) với \(x, y \in \mathbb{Z}_{2^n}\). Với \(\alpha\), \(\beta\) và \(\gamma\) thuộc \(\mathbb{Z}_{2^n}\) ta xem xét

\[\mathrm{xdp}^f(\alpha, \beta \mapsto \gamma) = \Pr\left[(x \oplus \alpha) \boxplus (y \oplus \beta) = (x \boxplus y) \oplus \gamma\right].\]

1.3.3. Một số lưu ý và nhận xét

Một số nguyên \(n\) bit cũng có thể xem xét dưới dạng vector \(n\) phần tử, do đó cho phép chúng ta xem xét hai dạng vi sai theo phép XOR và theo phép cộng modulo \(2^n\).

Ở đây, \(\mathrm{adp}\) là viết tắt của addition differential probability (xác suất vi sai theo phép cộng) và \(\mathrm{xdp}\) là viết tắt của xor differential probability (xác suất vi sai theo phép xor).

Trong nhiều thuật toán mã khối, các phép biến đổi có thể sử dụng phép XOR lẫn phép cộng modulo \(2^n\), do đó việc nghiên cứu mối liên hệ giữa các toán tử trên nhằm đưa ra đánh giá vi sai nào đạt được xác suất mong muốn là việc quan trọng. Tuy nhiên hiện chưa có nhiều nghiên cứu cho việc này, ví dụ như phép cộng modulo \(2^n\) sẽ có xác suất như thế nào đối với vi sai là phép XOR, và ngược lại.

Lý do đơn giản nhất của ứng dụng vi sai là loại bỏ sự có mặt của khóa trong mỗi vòng.

Ví dụ thứ nhất, rất phổ biến, là hệ mã DES. Nếu ta xét một S-box vòng thì biến đổi trên nửa phải có dạng

\[F(R, K) = \mathsf{SBox}(R \oplus K)\]

với \(R\) là nửa phải đầu vào và \(K\) là khóa ở vòng hiện tại, thì ta có vi sai đầu vào là

\[\delta = R \oplus R' = (R \oplus K) \oplus (R' \oplus K)\]

và vi sai đầu ra là

\[\Delta = \mathsf{SBox}(R \oplus K) \oplus \mathsf{SBox}(R' \oplus K).\]

Ở đây, vi sai đầu vào không phụ thuộc vào khóa \(K\).

Ví dụ thứ hai là round function của hệ mã Magma. Nếu ta lấy S-box của Magma có dạng

\[F(R, K) = \mathsf{SBox}(R \boxplus K)\]

thì vi sai đầu vào là

\[\delta = R' \boxminus R = (R' \boxplus K) \boxminus (R \boxplus K)\]

và vi sai đầu ra là

\[\Delta = \mathsf{SBox}(R' \boxplus K) \boxminus \mathsf{SBox}(R \boxplus K).\]

Ở đây ta cũng có vi sai đầu vào không phụ thuộc vào khóa \(K\) nhưng đối với toán tử hiệu \(\boxminus\), không phải hiệu \(\oplus\).