密碼學/線性密碼分析

在密碼學中，線性密碼分析是一種通用的密碼分析形式，它基於尋找對密碼動作的仿射近似。已針對分組密碼和流密碼開發了攻擊方法。線性密碼分析是兩種最常用的分組密碼攻擊之一；另一種是差分密碼分析。

該發現歸功於松井充，他首先將該技術應用於 FEAL 密碼（松井和山岸，1992）。隨後，松井發表了對資料加密標準 (DES) 的攻擊，最終導致了在公開社群中報告的第一個對該密碼的實驗性密碼分析（松井，1993；1994）。對 DES 的攻擊通常不切實際，需要 2⁴³ 個已知明文。

已經提出了對該攻擊的各種改進，包括使用多個線性近似或合併非線性表示式，從而導致廣義的劃分密碼分析。新的密碼設計通常需要針對線性密碼分析的安全性證據。

概述

線性密碼分析有兩個部分。第一部分是構建將明文、密文和金鑰位相關聯的線性方程，這些方程具有高偏差；也就是說，它們的保持機率（在所有可能的值空間中）儘可能接近 0 或 1。第二部分是將這些線性方程與已知的明文-密文對結合起來推匯出金鑰位。

構建線性方程

為了進行線性密碼分析，線性方程表示兩個表示式的相等性，這些表示式由二進位制變數與異或 (XOR) 運算組合而成。例如，以下來自假設密碼的方程指出，第一個和第三個明文位的 XOR 和（如分組密碼的塊中）與第一個密文位相等，等於金鑰的第二位

$P_{1}\oplus P_{3}\oplus C_{1}=K_{2}.$

在理想密碼中，任何將明文、密文和金鑰位相關聯的線性方程的保持機率都將為 1/2。由於線性密碼分析中處理的方程在機率上會有所不同，因此更準確地將它們稱為線性近似。

構建近似的過程對於每個密碼都是不同的。在最基本型別的分組密碼（替換-置換網路）中，分析主要集中在 S 盒上，這是密碼中唯一非線性的部分（即，S 盒的操作無法用線性方程表示）。對於足夠小的 S 盒，可以列舉將 S 盒的輸入和輸出位相關聯的每個可能的線性方程，計算它們的偏差並選擇最佳方程。然後，必須將 S 盒的線性近似與密碼的其他動作（如置換和金鑰混合）結合起來，以得出整個密碼的線性近似。堆積引理是這種組合步驟的有用工具。還有一些技術可以迭代地改進線性近似（松井 1994）。

推匯出金鑰位

在獲得以下形式的線性近似後

$P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots$

然後，我們可以應用一個簡單的演算法（松井演算法 2），使用已知的明文-密文對來猜測參與近似的金鑰位的取值。

對於右側金鑰位值的每一組（稱為部分金鑰），統計近似在所有已知的明文-密文對上保持成立的次數；將此計數稱為T。T 與明文-密文對數量的一半的絕對差值最大的部分金鑰被指定為這些金鑰位的最可能取值集。這是因為假設正確的部分金鑰將導致近似以高偏差保持成立。偏差的大小在這裡很重要，而不是機率本身的大小。

該過程可以使用其他線性近似重複執行，以獲得對金鑰位取值的猜測，直到未知金鑰位的數量足夠低，可以使用暴力破解進行攻擊。

參考文獻

• 松井，M. 和山岸，A. "一種對 FEAL 密碼進行已知明文攻擊的新方法"。密碼學進展 - EUROCRYPT 1992。 
• 松井，M. "DES 密碼的線性密碼分析方法" (PDF)。密碼學進展 - EUROCRYPT 1993。已從 原始位置 歸檔於 2006-04-10. http://web.archive.org/web/20060410133750/http://homes.esat.kuleuven.be/~abiryuko/Cryptan/matsui_des.PDF. 檢索於 2007-02-22. 
• 松井，M. "資料加密標準的第一個實驗性密碼分析"。密碼學進展 - CRYPTO 1994。