基于密碼結(jié)構(gòu)完全置換多項(xiàng)式的構(gòu)造

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

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

0 引言

完全置換多項(xiàng)式是一類特殊的置換多項(xiàng)式, 具有完全平衡性、雪崩特性等良好的密碼學(xué)性質(zhì)。因此，人們積極嘗試將完全置換多項(xiàng)式應(yīng)用于密碼、編碼及其組合設(shè)計等領(lǐng)域，如基于完全置換多項(xiàng)式的Lay-Massey密碼結(jié)構(gòu)[1]、流密碼Loiss[2]、分組密碼算法SM4[3]、秘鑰擴(kuò)展算法[4]等。我國基于完全置換多項(xiàng)式研發(fā)的SM4分組密碼算法在2021年6月25日正式成為了ISO/IEC國際標(biāo)準(zhǔn)[3]。因此，研究完全置換多項(xiàng)式的構(gòu)造具有重要的理論以及實(shí)際意義。

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

1 基礎(chǔ)知識

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

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

下面給出本文證明給定多項(xiàng)式為置換多項(xiàng)式所使用的準(zhǔn)則。

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

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

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

圖1 1輪Feistel結(jié)構(gòu) 圖2 1輪L-MISTY結(jié)構(gòu) 圖3 1輪R-MISTY結(jié)構(gòu)

2 基于4路兩重Feistel結(jié)構(gòu)和MISTY結(jié)構(gòu)完全置換多項(xiàng)式的構(gòu)造

在Feistel 結(jié)構(gòu)、L-MISTY以及R-MISTY結(jié)構(gòu)的基礎(chǔ)上采用4路兩重Feistel和MISTY結(jié)構(gòu)來構(gòu)造完全置換多項(xiàng)式。

圖4 省略輪秘鑰的一類4路兩重Feistel和L-MISTY結(jié)構(gòu)

(1)

(2)

圖5 省略輪秘鑰的一類4路兩重Feistel和R-MISTY結(jié)構(gòu)

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

圖6 另一類省略輪秘鑰的4路兩重Feistel和L-MISTY結(jié)構(gòu)

(3)

(4)

(5)

3 總結(jié)