[發(fā)明專利]一種搜索密碼算法線性層硬件實(shí)現(xiàn)優(yōu)化的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201911049313.5
• 申請(qǐng)日: 2019-10-31
• 公開（公告）號(hào): CN110995403B
• 公開（公告）日: 2021-06-01
• 發(fā)明（設(shè)計(jì)）人: 向澤軍;曾祥勇;張莎莎
• 申請(qǐng)（專利權(quán)）人: 湖北大學(xué)
• 主分類號(hào): H04L9/00
• 分類號(hào): H04L9/00;H04L9/06
• 代理公司: 武漢泰山北斗專利代理事務(wù)所(特殊普通合伙) 42250
• 代理人: 程千慧

1.一種搜索密碼算法線性層硬件實(shí)現(xiàn)優(yōu)化的方法，其特征在于，包括以下步驟：

S0、根據(jù)搜索密碼算法線性層硬件實(shí)現(xiàn)的特點(diǎn)，將搜索密碼算法線性層的實(shí)現(xiàn)轉(zhuǎn)換成搜索其對(duì)應(yīng)矩陣的實(shí)現(xiàn)，將二進(jìn)制數(shù)據(jù)中的0和1看成只包含兩個(gè)元素的有限域GF(2)中的元素，那么密碼算法的線性變換即為定義在GF(2)上的n維向量空間中的線性變換，因此，密碼算法的線性層可以用GF(2)上的n階可逆矩陣表示，即給定GF(2)上的n階可逆矩陣M和n維向量x，其中向量x的值對(duì)應(yīng)密碼算法線性層的輸入，則密碼算法線性層的輸出值y＝Mx，即算法線性層的輸出等價(jià)于計(jì)算矩陣M和向量x的乘法，GF(2)中的加法運(yùn)算即為異或運(yùn)算，對(duì)應(yīng)于硬件實(shí)現(xiàn)中的異或門電路；

S0.1、分解記E(i₀+j₀)…E(i_u-1+j_u-1)＝E₀…E_u-1，記記seq＝E₀…E_u-1P，記l＝u，記g＝l；其中u是M的分解中第三類初等矩陣的數(shù)量，v是M的分解中第一類初等矩陣的數(shù)量，k和l表示矩陣的行或列，E(i+j)表示一個(gè)第三類初等矩陣，E(i+j)是通過將單位矩陣的第j行加到第i行，或者將單位矩陣的第i列加到第j列得到的，記表示一個(gè)第一類初等矩陣，是通過將單位矩陣的第k行和第l行交換，或者將單位矩陣的第k列和第l列交換得到的，第一類和第三類初等矩陣的乘法滿足如下性質(zhì)：

其中，f_k，l(x)函數(shù)的定義如下：

S1、從seq中隨機(jī)挑選連續(xù)g個(gè)第三類初等矩陣E_r…E_r+g-1，0≤r≤l-g，并跳轉(zhuǎn)至S2，直到已遍歷完所有可能的矩陣選擇情況后，判斷g的大小，若g＝1，則跳轉(zhuǎn)至S7；若g＞1，則令g＝g-1并跳轉(zhuǎn)至S1；

S2、計(jì)算M′＝E_r…E_r+g-1，并跳轉(zhuǎn)至S3；

S3、分解并跳轉(zhuǎn)至S4；

S4、記將seq_a中所有第一類初等矩陣根據(jù)公式移到尾端，并記得到的結(jié)果為記并跳轉(zhuǎn)至S5；

S5、計(jì)算并跳轉(zhuǎn)至S6；所述函數(shù)Reduce(seq_p)包括以下步驟：

S5.1、將簡(jiǎn)寫為seq_p＝E₀…E_u-1，其中x＝u，記l＝u，并預(yù)設(shè)以下7種模式：

R1.E(k+i)E(k+j)E(i+j)＝E(i+j)E(k+i)，

R2.E(i+k)E(k+j)E(i+j)＝E(k+j)E(i+k)，

R3.E(i+k)E(j+k)E(i+j)＝E(i+j)E(j+k)，

R4.E(j+k)E(i+k)E(i+j)＝E(i+j)E(j+k)，

R5.E(k+j)E(k+i)E(i+j)＝E(i+j)E(k+i)，

R6.E(k+j)E(i+k)E(i+j)＝E(i+k)E(k+j)，

R7.

S5.2、依次從seq_p中挑選出三個(gè)初等矩陣E_a，E_b和E_c，并且滿足0≤a＜b＜c≤l-1，然后跳轉(zhuǎn)至S5.3；如果已經(jīng)遍歷完所有可能則跳轉(zhuǎn)至S5.7；

S5.3、判斷E_aE_bE_c是否滿足R1-R6所列模式之一；如果滿足跳轉(zhuǎn)至S5.4，否則跳轉(zhuǎn)至S5.2；

S5.4、如果矩陣E_b與矩陣E_i(i＝a+1，...，b-1)乘法可交換，并且矩陣E_c與矩陣E_j(j＝a+1，...，b-1，b+1，.，..，c-1)乘法可交換，則將seq_p等價(jià)表示成E₀…E_a-1E_aE_bE_cE_a+1…E_b-1E_b+1…E_c-1E_c+1…E_l-1，并使用R1-R6簡(jiǎn)化并更新seq_p，更新l＝l-1，然后跳轉(zhuǎn)至S5.2；否則，跳轉(zhuǎn)至S5.5；

S5.5、如果矩陣E_a與矩陣E_i(i＝a+1，...，b-1)乘法可交換，并且矩陣E_c與矩陣E_j(j＝b+1，.，..，c-1)乘法可交換，則將seq_p等價(jià)表示成E₀…E_a-1E_a+1…E_b-1E_aE_bE_cE_b+1…E_c-1E_c+1…E₀，并使用R1-R6簡(jiǎn)化并更新seq_p，更新l＝l-1，然后跳轉(zhuǎn)至S5.2；否則，跳轉(zhuǎn)至S5.6；

S5.6、如果矩陣E_a與矩陣E_i(i＝a+1，...，b-1，b+1，...，c-1)乘法可交換，并且矩陣E_b與矩陣E_j(j＝b+1，.，..，c-1)乘法可交換，則將seq_p等價(jià)表示成E₀…E_a-1E_a+1…E_b-1E_b+1…E_c-1E_aE_bE_cE_c+1…E_i-1，并使用R1-R6簡(jiǎn)化并更新seq_p，更新l＝l-1，然后跳轉(zhuǎn)至S5.2；否則，跳轉(zhuǎn)至S5.7；

S5.7、依次從seq_p中挑選出兩個(gè)矩陣E_a和E_b，并且滿足0≤a＜b≤l-1，然后跳轉(zhuǎn)至S5.8；如果已遍歷完所有可能則跳轉(zhuǎn)至S5.11；

S5.8、判斷E_aE_b是否滿足R7所列模式，如果滿足跳轉(zhuǎn)至S5.9，否則跳轉(zhuǎn)至S5.7；

S5.9、如果矩陣E_b與矩陣E_i(i＝a+1，...，b-1)乘法可交換，則將seq_p等價(jià)表示成E₀…E_a-1E_aE_bE_a+1…E_b-1E_b+1…E_l-1，并使用R7簡(jiǎn)化并更新seq_p，將此更新后的seq_p中包含的一個(gè)第一類初等變換根據(jù)公式移動(dòng)到seq_p尾端，更新l＝l-1，然后跳轉(zhuǎn)至S5.7；否則，跳轉(zhuǎn)至S5.10；

S5.10、如果矩陣E_a與矩陣E_i(i＝a+1，...，b-1)乘法可交換，則將seq_p等價(jià)表示成E₀…E_a-1E_a+1…E_b-1E_aE_bE_b+1…E_l-1，并使用R7簡(jiǎn)化并更新seq_p，將此更新后的seq_p中包含的一個(gè)第一類初等變換根據(jù)公式(1)移動(dòng)到seq_p尾端，更新l＝l-1，然后跳轉(zhuǎn)至S5.7；

S5.11、返回seq_p，l；

S6.如果l^*≥l，跳轉(zhuǎn)至S1；如果l^*＜l，記并跳轉(zhuǎn)至S1；

S7.返回seq，實(shí)現(xiàn)seq的電路即為搜索算法線性層電路，seq中第三類初等矩陣的數(shù)量即為線性層電路中異或門電路的數(shù)量。

2.根據(jù)權(quán)利要求1所述的搜索密碼算法線性層硬件實(shí)現(xiàn)優(yōu)化的方法，其特征在于，所述算法是通過計(jì)算機(jī)自動(dòng)執(zhí)行的。