一類冪函數(shù)的差分譜*

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

1. 國防科技大學文理學院, 長沙 410073

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

1 引言

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

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

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

2 準備工作

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

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

2.1 差分譜

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

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

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

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

2.2 一些引理

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

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

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

(i) 當pn ≡1 (mod 4) 時, 有:

(ii) 當pn ≡3 (mod 4) 時, 有:

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

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

然而, 當f(x) 的次數(shù)大于2 時, 二次特征和∑x∈Fpn χ(f(x)) 還沒有明確的計算公式. 下面總是假設p ≥5 是素數(shù), 定義

則

且有下述推論成立.

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

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

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

方程(6)的判別式為

方程(8)的判別式為

上述討論可歸結(jié)于表2,表中Di(i ∈[1,4])分別定義如式(4)、(5)、(7)和(9). 通過計算易得1,?1 /∈Di.故b=1 (resp.?1) 時,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, 故

因此

類似可得

由式(10), 可得

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

4 總結(jié)