ESF算法的截斷不可能差分分析*

李明明, 郭建勝, 崔競一, 徐林宏

信息工程大學, 鄭州450001

1 引言

不可能差分分析, 由Knudsen[1]和Biham[2]兩人分別獨立提出, 是目前常用的密碼分析方法之一.其基本思想是排除那些導致概率為0 的區分器的猜測密鑰.對于一條概率為0 的差分路徑, 當用正確密鑰解密密文對時, 不會得到符合該路徑的差分; 如果用猜測密鑰解密密文對, 得到符合該路徑的差分, 則該密鑰猜測值是錯誤的; 那么篩去所有的錯誤密鑰猜測值, 剩下的就是我們需要恢復的正確密鑰[3].對一個分組密碼算法進行不可能差分分析的先決條件是找到一條概率為0 的差分路徑, 即不可能差分區分器.

Kim 等人[4]提出了μ方法, 該方法可以有效找出各種算法結構中所固有的不可能差分形式, 這些固有的不可能差分只與算法的結構有關, 而與算法所采用的S盒無關, 這也就是所謂的截斷不可能差分[5].后來 Luo 等[6]在μ方法基礎上改進提出了 UID 方法.不同于μ方法, UID 方法利用中間相錯的思想將密碼算法結構分解成兩部分進行處理.此外, 孫兵等[7]基于整環上的矩陣論, 證明了 SPN 結構及嵌套SPN 的Feistel 結構的截斷不可能差分區分器的上界取決于線性層的本原指數.

ESF 算法[8]是2013 年劉宣等人基于LBlock 算法[9]改進的的輕量級分組密碼算法, 其置換層借鑒PRESENT 算法[10]中P置換的形式, 能夠使得在較少的輪數中快速擴散, 從而達到增加密碼算法抵抗攻擊的安全性.該算法分組長度為 64-bit, 密鑰長度為 80-bit, 整體采用變形 Feistel 結構, 由非線性變換S盒、P置換……