[發明專利]一種密碼學置換的枚舉方法及系統

有效

• 申請號: 201910613016.2
• 申請日: 2019-07-09
• 公開（公告）號: CN110266471B
• 公開（公告）日: 2021-10-15
• 發明（設計）人: 童言;徐士偉;王邦菊;郭曦;趙逸之
• 申請（專利權）人: 華中農業大學
• 主分類號: H04L9/06
• 分類號: H04L9/06
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 楊采良

1.一種密碼學置換的枚舉方法，其特征在于，所述密碼學置換的枚舉方法包括以下步驟：

步驟一，獲取n的值，n為雙正形置換的維度值，取值范圍為2≤n≤4；

步驟二，選取一個次數為n的不可約多項式，并基于這個不可約多項式，構造GF(2ⁿ)上的乘法表；其中，GF(2ⁿ)表示特征為2并且通過n次擴張得到的有限域；

步驟三，基于乘法表構造一個2ⁿ-1行2ⁿ-1列的方陣，行號表示置換的輸入，列號表示置換的輸出，該方陣用于數組存儲與訪問；同時對符號進行相關定義，所述定義相關符號變量具體包括：

(1)k表示行號，k的初值為1，所述行號取值范圍為大于等于0，小于等于2ⁿ-1；

(2)P[k]表示列號，方陣中第k行第P[k]列的元素為k*P[k]，其中*為GF(2ⁿ)上的乘法；所述列號取值范圍為大于等于0，小于等于2ⁿ-1；

(3)數組flagmulti[2ⁿ]、flagfirst[2ⁿ]、flagrow[2ⁿ]表示標志位，數組pre[2ⁿ]、next[2ⁿ]、link[2ⁿ]表示一個單向靜態鏈表，數組beginning[2ⁿ]存儲初始列號初始記錄位置，beginning[k]記錄第k行的初始位置；

1)標志位flagmulti[i]＝1表示i等于之前某一行號與列號的乘積，flagmulti[i]＝0則表示相反的情況，其中1≤i≤2ⁿ-1，用于遍歷行號；

2)link為一個包含n個元素的單向靜態鏈表，并且初始化為link[0]＝0，link[2ⁿ-1]＝1,link[i]＝i+1，其中1≤i≤2ⁿ-1，用于遍歷行號；所述link鏈表表示從1到2ⁿ-1這2ⁿ-1個列號中所有的可用資源，當一個列號被使用了，則從鏈表中刪除，并重構鏈表；

3)對于每一個節點，i表示節點的行號，P[i]表示節點的列號，pre[i]表示第i行列號P[i]的前一個節點，next[i]表示第i行列號P[i]的下一個節點；

4)標志位數組flagfirst[2ⁿ]，當發現一個P[i]被選中時，如果i是1，也就是在第1行選中了列號P[1]，就將flagfirst[P[1]]置位為1，初始值是0；

5)標志位數組flagrow[2ⁿ]用于標記beginning[i]記錄的每一行的初始位置，當一行遍歷完，將flagrow[i]置為1；同時進行初始化；

步驟四，判斷k是否大于0；若大于0，則執行步驟五；否則程序終止；

步驟五，基于判斷行標志位變量flagrow[k]是否被置位從而判斷第k行的所有列號是否均已試過；若沒有則執行步驟六，否則執行步驟七；

步驟六，如果當前P[k]同時滿足兩個要求，則對各標志位數組以及鏈表做相應的處理，同時停止執行步驟六，并開始執行步驟七；如果不滿足，則取鏈表中的下一個節點為P[k]，并返回執行步驟五；

所述P[k]同時滿足的兩個要求條件具體包括：

第一：flagfirst[k]沒有被置位，或者P[k]不等于1；

第二：flagmulti[k*P[k]]沒有被置位；

所述對各標志位數組以及鏈表做相應的處理方法具體包括：

flagmulti[k*P[k]]＝1，也就是被置位；link[pre[k]]＝next[k]；

link[P[k]]＝0,表示將P[k]從鏈表中刪除；判斷行號k是否等于1，如果等于1，則將flagfirst[P[k]]置位為1；

步驟七，判斷當前k行所有的列號是否均已試過；若沒有則進一步判斷k是否等于最大行號；若有則置換i→P[i]是乘法正形置換，其中0≤i≤2ⁿ-1,用于遍歷所有的行號，并同時判斷該置換是否是加法正形置換；若是則記錄下結果，并通過對調行號和列號得到逆置換，并記錄下結果；若不是則不記錄也不對調；隨后回退兩行，將對應的兩個列號重新加入鏈表，并將k減1，取下一個節點為P[k]，然后返回執行步驟四；如果k不等于最大行號，則將k加1，進入下一行,并完成各標志位以及鏈表的處理，返回執行步驟四；如果當前k行所有的列號均已試過，執行步驟八；

所述回退兩行，將對應的兩個列號重新加入鏈表的方法具體包括：

flagmulti[(2ⁿ-2)*P[2ⁿ-2]]＝flagmulti[(2ⁿ-2)*P[2ⁿ-2]]＝0；

link[P[2ⁿ-1]]＝next[2ⁿ-1]；

link[pre[2ⁿ-1]]＝P[2ⁿ-1]；

link[P[2ⁿ-2]]＝next[2ⁿ-2]；link[pre[2ⁿ-2]]＝P[2ⁿ-2]；

所述完成各標志位以及鏈表的處理方法具體包括：

pre[k]＝pre[k-1]；

P[k]＝next[k-1]；

beginning[k]＝P[k]；

flagrow[k]＝0；

next[k]＝link[P[k]]；

步驟八中，所述將當前的P[k]添加到鏈表的方法具體包括：

flagmulti[k*P[k]]＝0；

link[P[k]]＝next[P[k]]；

link[pre[k]]＝P[k]；

步驟八，k減1，并將當前的P[k]添加到鏈表中，并取下一個節點為P[k]，返回執行步驟四；

所述步驟五和步驟七中，所述判斷當前第k行所有的列號是否均已試過具體包括：

判斷當前k行所有的列號是否均已試過，判斷flagrow[k]是否被置為1，沒有被置位即表示還有列號未被嘗試。