二維仿射密碼的已知明文攻擊
問題：
我們有一個二維仿射密碼 $ n = 2,,,,\mathcal{P} = \mathcal{C} = {\mathbb{F}{16}^2} $ ， 在哪裡 $ \mathcal{K} = { A,,,b} $ 和 $ b = (0,0) $ . 加解密在 $ {\mathbb{F}{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $ . 任務是恢復密鑰的第一部分 - $ A $ 給定兩個明文-密文對： $ {e_K}((d,5)) = (7,4) $ 和 $ {e_K}((3,1)) = (d,c) $ . 應該應用已知明文攻擊來查找 $ A $ .
一些觀察：
對於一個典型的一維情況 $ {\mathbb{Z}{26}} $ 這個任務很簡單。我們需要做的就是解決 $ A $ $ {e_K}(x) - {e_K}(y) \equiv A(x - y),(\bmod ,26) $ , 考慮 $ \exists ,{(x - y)^{ - 1}} \in {\mathbb{Z}{26}} \wedge (x - y){(x - y)^{ - 1}} \equiv 1,(\bmod ,26) $ 是真的。在這種情況下，我們只需將兩邊乘以 $ {(x - y)^{ - 1}} $ 並獲得價值 $ A $ .
現在在我的情況下它更複雜。困難來自於我們需要在 $ {\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $ 純文字 - 密文數據是十六進制格式。此外，我們正在處理 $ 2 \times 2 $ 矩陣不僅僅是簡單的十進制值……
解決方案嘗試：
基於我試圖解決的一維案例 $ A $ 使用
$$ {e_K}(x) - {e_K}(y) \equiv A(x - y),(\bmod{x^4} + x + 1) $$ $ \begin{gathered} x = \left[ \begin{gathered} d \ 5 \ \end{gathered} \right] = \left[ {\begin{array}{{20}{c}} {{x^3} + {x^2} + 1} \ {{x^2} + 1} \end{array}} \right],,,,,y = \left[ \begin{gathered} 3 \ 1 \ \end{gathered} \right] = \left[ {\begin{array}{{20}{c}} {x + 1} \ 1 \end{array}} \right] \ {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{{20}{c}} {{x^2} + x + 1} \ {{x^2}} \end{array}} \right] - \left[ {\begin{array}{{20}{c}} {{x^3} + {x^2} + 1} \ {{x^3} + {x^2}} \end{array}} \right] = \left[ {\begin{array}{{20}{c}} {{x^3} + x} \ {{x^3}} \end{array}} \right] = \left[ {\begin{array}{{20}{c}} a \ 8 \end{array}} \right] \ x - y = \left[ {\begin{array}{{20}{c}} {{x^3} + {x^2} + 1} \ {{x^2} + 1} \end{array}} \right] - \left[ {\begin{array}{{20}{c}} {x + 1} \ 1 \end{array}} \right] = \left[ {\begin{array}{{20}{c}} {{x^3} + {x^2} + x} \ {{x^2}} \end{array}} \right] = \left[ {\begin{array}{{20}{c}} e \ 4 \end{array}} \right] \ {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{{20}{c}} {{x^3} + x} \ {{x^3}} \end{array}} \right] \equiv A \cdot \left[ {\begin{array}{{20}{c}} {{x^3} + {x^2} + x} \ {{x^2}} \end{array}} \right],,,(\bmod ,{x^4} + x + 1) \ \end{gathered} $
我該如何從最後一步開始？
您減去兩個已知的解決方案將是消除 $ b $ 從方程式中，並允許您僅使用 $ A $ .
然而，你已經被告知 $ b = (0,0) $ ，所以我們不需要消除它。
相反，我們知道密碼滿足關係（省略 $ b $ 因為已知為 0）：
$$ \begin{gathered} A \times \left[ \begin{gathered} d \ 5 \ \end{gathered} \right] = \left[ \begin{gathered} 7 \ 4 \ \end{gathered} \right]\end{gathered}, \begin{gathered} A \times \left[ \begin{gathered} 3 \ 1 \ \end{gathered} \right] = \left[ \begin{gathered} d \ c \ \end{gathered} \right]\end{gathered} $$ 在哪裡 $ A $ 是一個 2x2 數組，所有數學運算都在 $ GF(16) $ . 所以，如果我們更換 $ A $ 與數組 $ A = \begin{gathered} \left( \begin{gathered} x \ z \end{gathered} \begin{gathered} y \ w \end{gathered} \right) \end{gathered} $ （在哪裡 $ x, y, z, w $ 是未知值 $ GF(16) $ ， 我們有：
$$ d \cdot x + 5 \cdot y = 7 $$ $$ d \cdot z + 5 \cdot w = 4 $$ $$ 3 \cdot x + 1 \cdot y = d $$ $$ 3 \cdot z + 1 \cdot w = c $$ 通過做代數 $ GF(16) $ ，很容易求解這些聯立方程（提示：記住， $ GF(16) $ 是一個領域，所以代數就像你所期望的那樣在那里工作；你需要計算乘法和逆 $ GF(16) $ ，如果您手頭沒有任何工具來執行此操作，您可能會發現將快速程序組合在一起很有幫助。