什麼是線性化攻擊
我知道
在密碼學中，線性化攻擊是一種對分組密碼進行密碼分析的方法
我正在尋找一個線性化攻擊的例子在網上找不到
任何人都可以用一個例子來解釋它嗎？
密碼系統可以用多元方程表示，分析器試圖有效地求解這些方程，以進行代數攻擊。眾所周知，這是一個 NP-hard 問題。
線性化是一種解決這些問題的方法，其中單項式的次數最多為 2。它首先出現在Kipnis 和 Shamir的重新線性化對 HFE 公鑰密碼系統的密碼分析中。它只是重命名變數並解決新系統，然後確定原始問題的真正解決方案。
線性化在Bard 的書中寫得很好
給定一個二次系統 $ m $ 方程在 $ n $ 變數；
$$ \begin{align*} x_1 + x_2 x_3 &= 1\ x_1 x_2 + x_1 x_3 + x_1 & = 0\ x_2 x_3 + x_2 & = 0\ x_1 x_2 + x_1 + x_3 + x_2 & = 0\ x_1 + x_1 x_2 + x_3 & = 0\ x_2 x_3 + x_1 + x_2 &=1 \end{align*} $$
我們正在重命名總數 $ {n \choose 2} $ 二次單項式和 $ n $ 線性單項式。帶重命名（線性化）；
$$ \begin{align*} x_1 &= y_1\ x_2 &= y_2\ x_3 &= y_3\ x_1 x_2 &= y_4\ x_1 x_3 &= y_5\ x_2 x_3 &=y_6 \end{align*} $$
我們得到一個線性系統；
$$ \begin{align*} y_1 + y_6 &= 1 \ y_4 + y_5 + y_1 &= 0\ y_6 + y_2 &= 0\ y_4 + y_1 + y_3 + y_2 &= 0\ y_1 + y_4 + y_3 &= 0\ y_6 + y_1 + y_2 &= 1 \end{align*} $$
現在可以執行高斯消去法得到； $$ \begin{align*} y_1 & = 1\ y_2 & = 0\ y_3 & = y_5\ y_4 & = y_5 + 1\ y_5 & = \text{free}\ y_6 & = 0\ \end{align*} $$
這給出了兩種解決方案 $ (1, 0, 0, 1, 0, 0) $ 和 $ (1, 0, 1, 0, 1, 0) $ . 一個有效，一個無效（留給讀者）。這是因為線性化會破壞資訊。所以;
- 原方程組的解也是其線性化的解，但反過來是不正確的。
線性化有什麼好處？
- 如果可以給 $ m = (n^2+n)/2 $ 方程線性化將產生一些候選解。
- 如果 $ m \approx n’ \approx n^2/2 $ 那麼系統將有太多的資訊，會產生許多虛假的解決方案。
您需要閱讀有關理論 XSL 攻擊的維基百科頁面： https ://en.wikipedia.org/wiki/XSL_attack
…從理論上講，它實現了對分組密碼的線性化攻擊。但是請注意，雖然這是提議的，但它從未被證明有效。它背後的理論表明，無論如何，它與關鍵空間的普通蠻力一樣計算密集（工作因素）。