姜 沙, 李康荃, 李宇玻, 屈龍江

1. 國(guó)防科技大學(xué)文理學(xué)院, 長(zhǎng)沙 410073

2. 商用密碼理論與技術(shù)創(chuàng)新湖南省工程研究中心, 長(zhǎng)沙 410073

1 引言

在分組密碼算法中, S 盒(S-boxes) 往往是唯一的非線(xiàn)性組件, 其性質(zhì)的好壞對(duì)密碼算法安全性至關(guān)重要. 為了抵抗差分攻擊[1]等密碼分析方法, 人們提出了密碼函數(shù)的差分均勻度[2]等安全性指標(biāo). 在實(shí)際應(yīng)用中, 密碼函數(shù)常被希望具有低差分性質(zhì). 若某函數(shù)的差分均勻度為1, 則其被稱(chēng)為是完全非線(xiàn)性的(PN); 若差分均勻度為2, 則函數(shù)被稱(chēng)為是幾乎完全非線(xiàn)性的(APN). 關(guān)于PN 和APN 函數(shù)的研究成果,可參見(jiàn)文獻(xiàn)[3,4]. 除了在密碼學(xué)中的應(yīng)用, 差分均勻度在序列設(shè)計(jì)[5,6]、編碼理論[7,8]和組合設(shè)計(jì)[9,10]中也有廣泛應(yīng)用. 進(jìn)一步, 為了評(píng)估密碼系統(tǒng)抵御差分分析變體的能力, S 盒的差分譜也引起了廣泛的關(guān)注. 此外, 差分譜也被應(yīng)用在設(shè)計(jì)理論、編碼理論等其它領(lǐng)域. 例如, 差分2-值函數(shù)可被用于構(gòu)造2-設(shè)計(jì)[11]; 線(xiàn)性碼的低重量碼個(gè)數(shù)與差分譜息息相關(guān)[7,12].

因?yàn)閷?duì)硬件低消耗等優(yōu)點(diǎn), 冪函數(shù)常被用來(lái)構(gòu)造S 盒. 又因?yàn)閮绾瘮?shù)特殊的代數(shù)結(jié)構(gòu), 其差分譜的計(jì)算吸引了大量的關(guān)注. PN 和APN 函數(shù)(偶特征域) 的差分譜是顯然的. 2010 年, Blondeau 等人[12]率先開(kāi)始研究F2n上一些4-差分冪函數(shù)的差分譜. 到目前為止, F2n上差分均勻度屬于{4,6,8} 的冪函數(shù)的差分譜計(jì)算可參考文獻(xiàn)[13–16]. 對(duì)于奇特征域, 目前已確定差分譜的冪函數(shù)僅有六類(lèi), 見(jiàn)表1.

表1 Fpn 上已確定差分譜的冪函數(shù)(p 奇數(shù))Table 1 Known differential spectrums of power functions over Fpn (p odd)

2 準(zhǔn)備工作

首先, 統(tǒng)一本文中常使用的一些記號(hào). 假設(shè)p為一奇素?cái)?shù), Fpn為包含pn個(gè)元的有限域且F?pn=Fpn{0}. 令χ(·) 表示Fpn上二次特征, 即對(duì)任意x ∈Fpn有

則分圓數(shù)(i,j) := #Cij. 對(duì)任意整數(shù)s

2.1 差分譜

令f為從Fpn到Fpn的函數(shù). 記方程

在Fpn中解的個(gè)數(shù)為Nf(a,b), 其中a ∈F?pn, b ∈Fpn. 令

其中i=0,1,··· ,η. 則f的差分譜為

根據(jù)差分譜定義, 有

2.2 一些引理

這一小節(jié)將給出證明中需要的一些引理.

分圓數(shù)是計(jì)算差分譜常用的工具. 在本文需要考慮的情形中, 分圓數(shù)的個(gè)數(shù)都是可以被完全刻畫(huà)的.

引理2[文獻(xiàn)[18]引理1] 對(duì)于i,j ∈{0,1}, 分圓數(shù)(i,j) 取值如下:

(i) 當(dāng)pn ≡1 (mod 4) 時(shí), 有:

(ii) 當(dāng)pn ≡3 (mod 4) 時(shí), 有:

線(xiàn)性函數(shù)的二次特征和是平凡的, 二次函數(shù)f(x) 的二次特征和可利用以下計(jì)算法則得到.

引理3[文獻(xiàn)[24]引理5.48] 令f(x)=ax2+bx+c ∈Fpn[x],p為奇素?cái)?shù),n為正整數(shù)且a ?=0. 設(shè)D=b2?4ac. 則

然而, 當(dāng)f(x) 的次數(shù)大于2 時(shí), 二次特征和∑x∈Fpn χ(f(x)) 還沒(méi)有明確的計(jì)算公式. 下面總是假設(shè)p ≥5 是素?cái)?shù), 定義

則

且有下述推論成立.

推論1根據(jù)上面的定義, 有

下面給出本文的主要結(jié)果.

當(dāng)pn ≡1 (mod 4) 時(shí),?1 是Fpn中平方元, 即χ(?1) = 1. 顯然, 如果x= 0 或?1 是方程(3)的解, 則b=1 或?1. 下面研究x ∈Fpn{0,?1}是方程(3)的解時(shí),b對(duì)應(yīng)的條件. 分四種情況討論:1)x ∈C00, 即χ(x+1)=1,χ(x)=1. 此時(shí), 方程(3)等價(jià)于

方程(6)的判別式為

方程(8)的判別式為

上述討論可歸結(jié)于表2,表中Di(i ∈[1,4])分別定義如式(4)、(5)、(7)和(9). 通過(guò)計(jì)算易得1,?1 /∈Di.故b=1 (resp.?1) 時(shí),x=0 (resp.?1) 為方程(3)的唯一解.

表2 方程(3)在Fpn 中的解Table 2 Solutions of Eq.(3) in Fpn

利用特征和, 可知

由引理3可知

令b ?1=x?, 則b=x?+1 且b ?4=x??3, 故

因此

類(lèi)似可得

由式(10), 可得

此結(jié)果與直接利用Magma 計(jì)算冪函數(shù)x1202差分譜的結(jié)果是一致的.

4 總結(jié)