[發明專利]一種搜索密碼算法線性層硬件實現優化的方法

有效

• 申請號: 201911049313.5
• 申請日: 2019-10-31
• 公開（公告）號: CN110995403B
• 公開（公告）日: 2021-06-01
• 發明（設計）人: 向澤軍;曾祥勇;張莎莎
• 申請（專利權）人: 湖北大學
• 主分類號: H04L9/00
• 分類號: H04L9/00;H04L9/06
• 代理公司: 武漢泰山北斗專利代理事務所(特殊普通合伙) 42250
• 代理人: 程千慧

本發明涉及一種搜索密碼算法線性層硬件實現優化的方法，本發明的主要步驟為：首先將GF(2)中的n階可逆矩陣進行矩陣分解，即將其分解成若干初等矩陣的乘積；其次，將給定矩陣的分解轉化成矩陣的實現方案；最后，通過GF(2)中矩陣乘法的性質對矩陣分解進行簡化從而達到矩陣實現優化的目的。本發明可以獲得密碼算法線性層具有更少異或操作的實現，可以減少算法實現的代價。

技術領域

本發明涉及密碼系統領域，具體涉及一種搜索密碼算法線性層硬件實現優化的方法。

背景技術

對稱密碼，特別是分組密碼作為一種加解密速度快的密碼體制在實際中有著廣泛的應用。對稱密碼體制使用的加解密密鑰相同，主要用于大量數據的加密。分組密碼作為對稱密碼中的重要組成部分，它將需要加密的明文劃分成n比特的數據塊，然后明文塊在k比特種子密鑰的控制下將數據塊轉化成密文塊。其中，n稱為分組密碼的分組長度，k稱為分組密碼的密鑰長度，n和k均為正整數。

分組密碼的設計一般遵循香農提出的混淆和擴散原則。混淆是為了保證密文和明文以及密鑰之間的關系盡量復雜，而擴散是為了保證一個明文比特要影響盡量多的密文比特。在實際算法中，混淆一般通過非線性置換獲得，而擴散一般通過線性變換實現。

分組密碼加解密速度快的特性使其廣泛應用于實際中大量數據的加解密。隨著物聯網和微型智能設備的普及，資源受限環境下的信息安全對密碼算法提出了新的要求。優化密碼算法的實現，使其具有更小的電路面積已經在學術界和工業界引起了廣泛的興趣。密碼算法的實現優化一般和密碼算法的設計流程相結合，即通過優化密碼算法設計流程中的部件達到對整體算法進行優化的目的。

對密碼算法中線性部件的實現進行優化可以從整體上節省算法的實現開銷。密碼算法所處理的數據為計算機二進制數據，將二進制數據中的0和1看成只包含兩個元素有限域GF(2)中的元素，那么密碼算法的線性變換即為定義在GF(2)上的n維向量空間中的線性變換。因此，密碼算法的線性層可以用GF(2)上的n階可逆矩陣表示，優化密碼算法線性層的實現即為優化GF(2)上n階可逆矩陣的實現。

給定GF(2)上的n階可逆矩陣M和n維向量輸入x，計算算法的輸出y＝Mx等價于計算矩陣和向量的乘法。因為GF(2)中只包含0和1，因此輸出y的計算過程只包含GF(2)上的一系列加法運算。GF(2)中的加法運算即為異或運算，對應于硬件實現中的異或門電路。因此，密碼算法線性層的實現代價由實現對應矩陣的異或門電路數量決定，優化密碼算法線性層的實現即為尋找異或門電路數量最少的矩陣實現。

例如，給定為GF(2)上的4階方陣，x＝(x₀，x₁，x₂，x₃)^T表示算法的輸入，算法的輸出y為從輸出表達式可以得到，無優化地實現該矩陣需要6個異或運算，即6個異或門電路。但是，通過對該矩陣進行優化，發現只需要如下5個異或門電路：

給定GF(2)上的n階可逆矩陣，尋找該矩陣的最優實現已經被證明是一個NP-hard問題。因此，目前不存在高效的多項式時間算法搜索GF(2)上任意n階可逆矩陣的最優實現。針對該問題，目前有兩類啟發式搜索算法用于優化GF(2)上的n階可逆矩陣的實現。