混合異或與模加法
有兩個已知的常數 A 和 B，以及一個未知的 X，我們可以求解以下方程：
(A xor X)+ X=B
其中 xor 是按位異或運算符，+ 是模加法。例如，A,B 和 X 可以屬於集合 {0,1,…,255}，因此加法是模 256。這個等式可以替代流密碼使用的經典異或運算。如果這個等式不能確定性地求解，那麼就不能對密碼進行已知的純文字攻擊來推斷密鑰流……
對於任何 $ n>0 $ 和任何固定的 $ A $ 功能 $ f_A : x \mapsto (A \oplus x) + x \bmod 2^n $ 在具有 2 個元素的場上仿射，即 $ f_A(x\oplus y) = f_A(x)\oplus f_A(y)\oplus A $ （作為 $ A = f_A(0) $ ).
模擬地圖的證明 $ g_A : x \mapsto (A \oplus x) - x \bmod 2^n $ 是仿射的，您可以在Louis Goubin的 CHES 2001 論文A Sound Method for Switching between Boolean and Arithmetic Masking中找到。為了 $ f_A $ 我不知道任何已發表的參考資料。
$ f_A(x) = B $ 相當於 $ f_A(x)\oplus A = B\oplus A $ ，所以你必須找出向量是否 $ B\oplus A $ 在圖像中 $ \mathbb F_2 $ - 線性地圖 $ x\mapsto f_A(x)\oplus A $ ，如果是，原像 $ x $ . 這是線性代數，因此從復雜性理論的角度來看很容易。
為了求解線性方程，您首先要檢查是否 $ B\oplus A $ 是一個鹼基圖像的線性組合，所以取鹼基 $ 1, 2, 4, 8, 16, \dots $ 你必須看看是否 $ B\oplus A $ 可以寫成向量子集的總和 $ f_A(1)\oplus A=((A\oplus 1)+1\bmod 2^n)\oplus A $ , $ f_A(2)\oplus A=((A\oplus 2)+2\bmod 2^n)\oplus A $ , $ f_A(4)\oplus A=((A\oplus 4)+4\bmod 2^n)\oplus A, \dots $ 使用諸如高斯消除之類的東西。
如果是的話，讓我們說，因為 $ I\subseteq {0, 1, \dots, n-1} $ 你得到 $ B\oplus A = \bigoplus_{i\in I} (f_A(2^i)\oplus A) $ ， 然後 $ x = \bigoplus_{i\in I} 2^i $ 是你的解決方案。**編輯：**通常，您將以這種方式獲得所有解決方案。線性代數告訴我們解的集合要麼是空的，要麼是仿射子空間，即，形式為 $ {x_0+v| v\in W} $ 在哪裡 $ x_0 $ 是任何解決方案並且 $ W $ 是一個 $ \mathbb{F}_2 $ - 的子空間 $ n $ -維向量空間 $ n $ 位向量。
因此，從安全的角度來看，我不希望使用這個等式（**編輯：）**進行改進，因為可以有效地計算和描述解決方案集（使用一個解決方案和一個基礎 $ W $ 有秩序的 $ \le n $ ).
對於任意 $ A $ 和 $ B $ ，我們找不到唯一的 $ X $ .
**範例：**讓 $ A $ 和 $ B $ 是 $ (00001111)_2 $ 和 $ (00001111)_2 $ 分別。的幾種解決方案 $ X $ 在等式中 $ ((A \oplus X)+ X) \pmod {256}=B $ 如下面所述：
$ (00000000)_2 $ , $ (00000001)_2 $ , $ (00000010)_2 $ , $ (00000011)_2 $ , $ (00000100)_2 $ , $ (00000101)_2 $ , $ (00000110)_2 $ , $ (00000111)_2 $ , ….
讓 $ A_i $ 成為 $ i $ - 第一點 $ A $ . 等式真值表如下：
$ \begin{matrix}A_i& X_i&((A_i \oplus X_i)+ X_i) \pmod {2^n}=B_i\ \hline 0&0&0\0&1&0+carry\1&0&1\1&1&1\ \end{matrix} $
所以， $ B_i=A_i $ 什麼時候 $ A_i $ 是 $ 1 $ ， 的價值 $ X_i $ 不能影響方程。