[發明專利]對稱密碼系統代數次數評估方法

有效

• 申請號: 201710659243.X
• 申請日: 2017-08-04
• 公開（公告）號: CN107395347B
• 公開（公告）日: 2021-06-15
• 發明（設計）人: 韋永壯;史佳利;葉濤;武小年;張潤蓮
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: H04L9/08
• 分類號: H04L9/08;H04L9/06;H04L9/00
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 楊雪梅

本發明公開了一種對稱密碼系統代數次數評估新方法，利用對對稱密碼系統代數次數的迭代評估，擴展了一種新的對代數次數精確評估的優化算法。基于這個算法框架，提出一種尋找代數次數下界并且具體有效的算法。該算法不僅可以快速評估計算，而且可以對分析輪數進行準確評估，也是第一個用于有效精確評估對稱密碼系統代數次數的下界。若取值適當，不僅可以計算出布爾函數代數次數的下界，甚至可以輸出布爾函數的最大項。它也可應用于密鑰恢復攻擊和更多的加密基元。因此，代數次數的精確評估對設計或分析對稱密碼系統均有十分重要的意義。

技術領域

本發明涉及信息安全領域，具體是一種對稱密碼系統代數次數評估新方法。

背景技術

布爾函數的代數次數在密碼基元的安全中扮演著十分重要的角色，例如：對稱密碼系統包括基于NFSR的加密系統、分組密碼，流密碼可以通過包含秘密變量(key bits)和公開變量(plaintext bits or IV bits)的弱密鑰布爾函數表示；分組密碼將輸入的明文視為變量。而事實上，低代數次數的密碼基元容易被許多密碼分析方法進行分析。

對于現代的對稱密碼系統，準確計算其代數次數是非常困難的，雖然，現在有一些理論工具已經用于估計迭代置換的代數次數的上界，并且現在已經應用于分析迭代密碼算法，但仍有很大的改善空間。例如：積分區分器可以由代數次數評估進行構建，這種方法經常應用于高階差分分析，代數次數可以通過算法的布爾函數進行評估。

若一個加密算法的布爾函數表達式或其代數次數可知，便可以利用這一條件建立區分器，進而恢復密鑰。已有的許多攻擊方法都直接或間接的利用了布爾函數的代數表達式，如：代數攻擊、高階差分攻擊、Cube攻擊、積分攻擊等。

1994年，Knudsen提出積分區分器可以由普遍用于高階差分的代數次數評估構建，并且代數次數可以通過ANF進行評估。2002年，Canteaut和Videau為了改善迭代分組密碼的安全，抵抗線性分析，展示了可以找到的布爾部件的積的上界的函數的一些性質。2009年，Dinur和Shamir提出立方攻擊解決類似防碰撞散列函數的多項式，是相對于已經發表的同類攻擊的一個重大改進。只要滿足作為黑匣子提供的(即使不知道其內部結構)、至少一個輸出位可以由(未知)秘密變量和公共變量相對較低的代數次數的多項式表示，立方體攻擊就可以應用于任何分組密碼，流密碼或MAC。2011年，Dinur和Shamir在理論上利用動態立方攻擊對全輪的Grain-128進行分析，動態立方攻擊可以用較低的代數次數表示給定的密碼算法，這使得可以攻擊所有先前抵抗已知攻擊的方案。2012年，Boura和Canteaut提出了一個關于迭代排列的代數程度被看作多元多項式的研究，結果表明階數取決于迭代的逆置換的代數次數。2015年，Todo提出一種利用可分性構建積分區分器的算法，而可分性是以考慮雙射函數(如雙射S盒)的代數度估計為基礎的，然而，因為代數次數被高估，算法不能確定是否存在其他的積分區分器。2016年，Todo和Morii將可分性應用于SIMON，并在理論上證明了SIMON32積分區分器的正確性。同時，對于分組長度大于32的算法，文中也給出了區分器上界的評估。2017年，劉美成提出一種利用數字映射對基于NFSR密碼算法代數次數的上界進行評估的算法。

目前，在對稱密碼的分析中，所使用的最多的布爾函數的性質為代數次數，也已經出現了許多或直接、或間接的利用布爾函數及其代數次數的分析方法。利用這些對對稱密碼系統代數次數評估的方法，可以改進現有的分析方法，例如：代數攻擊、高階差分攻擊、Cube攻擊、積分攻擊等，與此同時，對對稱密碼算法進行分析，也可以得到更好的分析結果。但是，這些方法對代數次數的評估都不夠精確，目前還沒有對代數次數精確評估的方法，所以，迫切需要一種可以對對稱密碼系統代數次數精確評估的方法。

發明內容

針對上述不足，本發明所要解決的技術問題是提供一種對稱密碼系統代數次數評估的新方法，引入對稱密碼系統的輸出布爾函數，深入研究對稱密碼系統的算法結構，提出一種對對稱密碼系統代數次數評估的新方法。