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

1. 国防科技大学文理学院, 长沙 410073

2. 商用密码理论与技术创新湖南省工程研究中心, 长沙 410073

1 引言

在分组密码算法中, S 盒(S-boxes) 往往是唯一的非线性组件, 其性质的好坏对密码算法安全性至关重要. 为了抵抗差分攻击[1]等密码分析方法, 人们提出了密码函数的差分均匀度[2]等安全性指标. 在实际应用中, 密码函数常被希望具有低差分性质. 若某函数的差分均匀度为1, 则其被称为是完全非线性的(PN); 若差分均匀度为2, 则函数被称为是几乎完全非线性的(APN). 关于PN 和APN 函数的研究成果,可参见文献[3,4]. 除了在密码学中的应用, 差分均匀度在序列设计[5,6]、编码理论[7,8]和组合设计[9,10]中也有广泛应用. 进一步, 为了评估密码系统抵御差分分析变体的能力, S 盒的差分谱也引起了广泛的关注. 此外, 差分谱也被应用在设计理论、编码理论等其它领域. 例如, 差分2-值函数可被用于构造2-设计[11]; 线性码的低重量码个数与差分谱息息相关[7,12].

因为对硬件低消耗等优点, 幂函数常被用来构造S 盒. 又因为幂函数特殊的代数结构, 其差分谱的计算吸引了大量的关注. PN 和APN 函数(偶特征域) 的差分谱是显然的. 2010 年, Blondeau 等人[12]率先开始研究F2n上一些4-差分幂函数的差分谱. 到目前为止, F2n上差分均匀度属于{4,6,8} 的幂函数的差分谱计算可参考文献[13–16]. 对于奇特征域, 目前已确定差分谱的幂函数仅有六类, 见表1.

表1 Fpn 上已确定差分谱的幂函数(p 奇数)Table 1 Known differential spectrums of power functions over Fpn (p odd)

2 准备工作

首先, 统一本文中常使用的一些记号. 假设p为一奇素数, Fpn为包含pn个元的有限域且F∗pn=Fpn{0}. 令χ(·) 表示Fpn上二次特征, 即对任意x ∈Fpn有

则分圆数(i,j) := #Cij. 对任意整数s

2.1 差分谱

令f为从Fpn到Fpn的函数. 记方程

在Fpn中解的个数为Nf(a,b), 其中a ∈F∗pn, b ∈Fpn. 令

其中i=0,1,··· ,η. 则f的差分谱为

根据差分谱定义, 有

2.2 一些引理

这一小节将给出证明中需要的一些引理.

分圆数是计算差分谱常用的工具. 在本文需要考虑的情形中, 分圆数的个数都是可以被完全刻画的.

引理2[文献[18]引理1] 对于i,j ∈{0,1}, 分圆数(i,j) 取值如下:

(i) 当pn ≡1 (mod 4) 时, 有:

(ii) 当pn ≡3 (mod 4) 时, 有:

线性函数的二次特征和是平凡的, 二次函数f(x) 的二次特征和可利用以下计算法则得到.

引理3[文献[24]引理5.48] 令f(x)=ax2+bx+c ∈Fpn[x],p为奇素数,n为正整数且a ̸=0. 设D=b2−4ac. 则

然而, 当f(x) 的次数大于2 时, 二次特征和∑x∈Fpn χ(f(x)) 还没有明确的计算公式. 下面总是假设p ≥5 是素数, 定义

则

且有下述推论成立.

推论1根据上面的定义, 有

下面给出本文的主要结果.

当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)的判别式为

上述讨论可归结于表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), 可得

此结果与直接利用Magma 计算幂函数x1202差分谱的结果是一致的.

4 总结