基于密碼結構完全置換多項式的構造

劉靜琰，肖同飛，聶 順，雷 卓，彭 昶，胡道歡，謝小雨，曹曉玉，許小芳*

(1.湖北理工學院 數理學院，湖北 黃石 435003；2.黃石市第十六中學，湖北 黃石 435000)

0 引言

完全置換多項式是一類特殊的置換多項式, 具有完全平衡性、雪崩特性等良好的密碼學性質。因此，人們積極嘗試將完全置換多項式應用于密碼、編碼及其組合設計等領域，如基于完全置換多項式的Lay-Massey密碼結構[1]、流密碼Loiss[2]、分組密碼算法SM4[3]、秘鑰擴展算法[4]等。我國基于完全置換多項式研發的SM4分組密碼算法在2021年6月25日正式成為了ISO/IEC國際標準[3]。因此，研究完全置換多項式的構造具有重要的理論以及實際意義。

1942年Mann提出了完全置換多項式的定義，主要用于構造正交拉丁方[5]。1957年，Hall和Paige研究了有限群上的完全置換[6]。1982年，Niederreiter和Robinson首次詳細地討論了有限域上的完全置換多項式[7]。隨著完全置換多項式的應用領域越來越廣泛，其研究成果越來越多，主要集中在完全置換多項式的構造方面。比較有代表性的是：含有較少項數的稀疏型完全置換多項式[8-10]、形如(xpm-x+δ)s+L(x)的基于線性化多項式的完全置換多項式[11]以及完全置換多項式的遞歸構造。有關完全置換多項式的其他研究成果可參考文獻[12]。

1 基礎知識

符號F2m表示元素個數為2m的有限域，其中m是正整數。

定義1[3]如果有限域F2m上的多項式f(x)誘導的從F2m到其自身的映射f:c→f(c)是有限域F2m上的雙射，則稱f(x)為有限域F2m上的置換多項式。若f(x)和f(x)+x都是F2m上的置換多項式,則稱f(x)為F2m上的完全置換多項式。

下面給出本文證明給定多項式為置換多項式所使用的準則。

引理1[3]有限域F2m上的多項式f(x)是F2m上的置換多項式，當且僅當下列條件之一成立:

1)對任意的y∈F2m,方程f(x)=y在F2m中恰有1個解。

2)對任意的y∈F2m,方程f(x)=y在F2m中至少有1個解。

圖1 1輪Feistel結構 圖2 1輪L-MISTY結構 圖3 1輪R-MISTY結構

2 基于4路兩重Feistel結構和MISTY結構完全置換多項式的構造

在Feistel 結構、L-MISTY以及R-MISTY結構的基礎上采用4路兩重Feistel和MISTY結構來構造完全置換多項式。

圖4 省略輪秘鑰的一類4路兩重Feistel和L-MISTY結構

(1)

(2)

圖5 省略輪秘鑰的一類4路兩重Feistel和R-MISTY結構

不同于圖4的另一類省略輪秘鑰的4路兩重Feistel和L-MISTY結構如圖6所示。

圖6 另一類省略輪秘鑰的4路兩重Feistel和L-MISTY結構

(3)

(4)

(5)

3 總結