Linear-Cryptanalysis
線性與非線性操作如何與密碼安全性和差分密碼分析相關？
我了解什麼是線性運算以及什麼是非線性運算，但我想具體解釋一下對輸入數據的非線性運算如何減輕差分密碼分析攻擊。請注意，我是在開發密碼的背景下提出這個問題，而不是簡單地理解一般線性與差分密碼分析。
如果你有一個線性函式 $ F $ 那麼輸入差對應的輸出差 $ d $ 是
$$ F(x\oplus d) \oplus F(x)=F(x)\oplus F(d) \oplus F(x)=F(d), $$ 對於任何值 $ x, $ 這是一個具有破壞性的微分特徵，機率為 1。 你可以採取 $ F $ 成為一個 sbox，或構成一輪的一部分的一組平行的 sbox。迭代，您可以獲得整個密碼的機率為 1 的差分特徵，因為差分特徵與密鑰添加無關。這完全破解了密碼。
現在讓 $ n $ 是輸入和輸出位長 $ F $ 然後讓 $ F $ 是一個非線性排列，即一個適當的 sbox。目標是有許多不同的輸出差分，每個保持機率很小，對應於每個輸入差分。
最好的可能情況是每個輸出差值恰好發生 $ 2 $ 在……之外 $ 2^n $ $ x $ 價值觀。請注意，在二進制中，輸出差分對應於一些 $ d $ 和一個固定的 $ x $ 也發生在 $ x’=x\oplus d, $ 即，它們成對出現。
這樣的函式稱為幾乎完美非線性 (APN)，但僅存在於 $ n $ 奇怪，因此沒有太多使用，因為字節或多字節或半字節長度的 sbox 很受歡迎。AES snoxes 具有最大微分特徵機率 $ 2^{2-n} $ 而不是最優的 $ 2^{1-n} $ APN sbox 會給出的。