第3章
非线性组
件
对于分组密码来说,密文随机性是衡量其是否安全的重要指标。从数学的角度解释,
就是将明文作为自变量,将密文作为因变量,因变量越随机越好。如果密码变换是线性函
数,则不安全;非线性变换相对安全,但是随着对确定型非线性函数的深入研究,简单的密
码变换也不再安全。因此,要使用非确定型非线性函数作为密码变换,例如引入密钥或参
数来增强非确定性;同时,若对于确定密钥无法列出该非线性函数的具体表达式,也能够
使密码变换足够安全。
为了更好地实现非线性强度,只能在目前计算机可承受的计算能力范围内设计足够
好的小规模非线性组件,如常用的S盒就是其中的一种,然后将这些组件通过一定的方式
组合,大多数情况下采用某个代数结构上的线性组合,进而形成输入输出规模较大的可逆
非线性函数,这样的函数经过多次重复迭代,每次迭代中加入不同密钥,最后形成具体的
分组密码方案。
分组密码的非线性组件除了S盒之外,还有一种ARX 结构,同样可以提供非线性功
能,即模加(Add )、循环移位(Rotation)和异或(Xor)3种运算组合在一起的结构,这种结
构在很多分组密码和哈希函数中用到,具有优秀的混淆、扩散作用。目前发展最成熟的非
线性组件是S盒,因此,S盒的密码指标和设计方法备受关注[71-85],本章主要从这两方面
进行介绍。
3.S盒的密码指标
1
S盒通常是分组密码和哈希函数中最重要的非线性组件之一,它的密码性能是决定
整个密码算法安全性的关键,同时S盒的工作速度与整个算法的混淆速度成正比。对S
盒的深入研究不仅有助于得到密码性能更优的非线性函数,进而提升分组密码的设计水
平,而且对于密码算法分析也有相当重要的价值。
假设S盒输入为
n
比特,输出为
m
比特,则可以表示为映
射
S(x)x),x),…,(x)):2→Fm
Fn
=(f1(f2(fm
2
简称S(x)是一个n×m
的S盒,每一个分量函数fi(x)是
n
比特输入、1比特输出的布
尔函数(1≤i≤m)。当参数
m
和
n
选择得很大时,搜索某些攻击所用的统计特性比较困
难;但是,
m
和
n
过大会给S盒的设计实现带来困难,如增加算法的存储量、降低算法执
第3章 非线性组件
行速度等。从实现设计和安全性评估两个角度折中考虑,目前比较流行的是4×4、8×8
的S盒。
S盒的设计必须满足几个主要密码指标,通常包括差分均匀度、非线性度、代数次数、
项数、代数免疫度、扩散特性和严格雪崩特性。
3.1.1 差分均匀度
差分分析和线性分析的提出给久经考验的DES密码以致命一击,尽管这两种攻击方
法需要大量的选择明文或已知明文,但至少打破了DES牢不可破的梦想,可以在远少于
强力攻击的时间内恢复主密钥,而导致分析成功的根本原因在于DES的S盒密码性能较
弱。此后,越来越多的学者开始着力设计“强”的S盒,以增强基于S盒设计的分组密码的
安全性。大量研究表明,S盒抗差分分析的能力本质上取决于它的差分分布表和差分均
匀度。定
义3-1 称2n ×2m 阶矩阵Λ(S)为n×m 的S盒的差分分布表,如果
Λ(S)=
λ00 λ01 … λ0(2m -1)
λ10 λ11 … λ1(2m -1)
. . . .
λ(2n-1)0 λ(2n-1)1 … λ(2n-1)(2m -1)
.
è
.....
.
.
÷÷÷÷÷
其中λαβ=|{x∈Fn 2|S(x)..S(x..α)=β}|,α=0,1,…,2n -1,β=0,1,…,2m -1。
显然,λ0β = 2n(β=0)
0(β≠{ 0),2|λαβ,并且Σ2m-1
β=0
λαβ = 2n。特别地,当S 为置换时,λα0 =
2n(α=0)
{0(α≠0)。
差分分析的关键在于利用了S盒差分分布表中的部分非零元素λαβ,如果这些元素值
明显大于其他各元素值,则对应的输入输出差分概率较大,即p(α→β)=λαβ
2n ,有利于进行
差分分析,为此引入差分均匀度的概念。
定义3-2 设n×m 的S盒的差分分布表为Λ(S)=(λαβ),则称
δ(S)=max{λαβ|α =1,2,…,2n -1,β=0,1,…,2m -1}
为S盒的差分均匀度。
例3-1 设S盒输入3比特,输出3比特,如表3-1所示。
表3-1 S盒的输入输出
输入000 001 010 011 100 101 110 111
输出010 101 011 111 110 100 000 001
对于每一个输入差分α 和输出差分β,遍历0≤x≤7,对满足等式S(x)..S(x..α)=
β 的x 计数,即得到λαβ。以此类推,得到Λ(S)中的所有元素。S盒的差分分布表如表3-2
所示。
35
分组密码设计与评估
表3-2 S盒的差分分布表
α\β 000 001 010 011 100 101 110 111
000 8 0 0 0 0 0 0 0
001 0 2 2 0 2 0 0 2
010 0 2 2 0 0 2 2 0
011 0 0 0 0 2 2 2 2
100 0 2 0 2 2 0 2 0
101 0 0 2 2 0 0 2 2
110 0 0 2 2 2 2 0 0
111 0 2 0 2 0 2 0 2
表3-2中输入差分为001时,输出差分为001的概率为p(001→001)=28
=14,以此
类推。容易看出,这个S盒的差分均匀度为2,输入输出差分的最大概率为14。
为了抵抗差分分析,S盒的差分均匀度应当尽可能小。对于n×m 的S盒,差分均匀
度可能达到的最小值为2n-m +1。但当m >n 时,S盒不具备正交性,因此只能寻求m <n
时δ(S)≥2n-m +1的S盒。
图3-1 采用相同S盒的两种
迭代加密结构
定义3-3 给定n×m 的S盒,若Λ(S)的每一行(第一行除外)均有相等数目(一般
为2m -1)的0和非零元,且非零元的值均为2n-m +1,则称S 为几乎完全非线性(Almost
PerfectNonlinear,APN)置换,此时δ(S)=2n-m +1。
特别地,当S 为双射函数时,称S 为APN 置换,此时δ(S)=2,达到最小值。
定理3-1 对于n×n 的S盒,当n 为奇数时有最小差分均匀度δ(S)=2,当n 为偶
数时通常有δ(S)>2。
图3-1是采用相同S盒的两种迭代加密结构,输入输
出差分为(α,β)。假设S盒输入和输出均为n 比特,差分均
匀度为σ,则这两种结构的差分概率p(α,β)并不相同。
对于图3-1(a)的结构,最大差分特征概率由S盒的差
分均匀度决定,即p(α,β)≤σ/2n ;对于图3-1(b)的结构,最
大差分特征概率由两个S盒的差分均匀度决定,即根据马
尔可夫迭代法则,为p(α,β)≤σ2/22n ,有可能小于随机函数
概率。因此,多轮迭代会减小特定差分路径的概率。
3.1.2 非线性度
非线性度的概念最初由Pieprzyk等人在1988年提出,
它是S盒的主要设计指标之一,决定了基于S盒设计的密
36
第3章 非线性组件
码算法抵抗线性分析的能力。由于n×m 的S盒都可以表示成m 个布尔函数,所以下面
先给出布尔函数f 的非线性度定义。
定义3-4 令f:Fn2
→F2 是一个n 元布尔函数,f(x)的非线性度如下表示:
Nf =min l∈Ln
dH(f,l)
其中,Ln 表示全体n 元线性和仿射函数之集,dH(f,l)为f 和l 之间的海明距离。
定理3-2 n 元布尔函数f 的非线性度上界为2n-1-2(n/2)-1,当且仅当f 为Bent函
数时达到该上界2n-1-2(n/2)-1。
在定理3-2中,n 元Bent函数是指和每个线性布尔函数的距离都是2n-1-2(n/2)-1的
n 元布尔函数。因为Nf 为正整数,所以n/2必为正整数,这说明n 为偶数。故Bent函数
存在的必要条件是n 为偶数。虽然Bent函数的非线性度最佳,但它存在一些缺陷。例
如,它不是平衡的(即输出的0、1个数不相等),还有它的代数次数不超过n/2,等等。
定义3-5 令S(x)=(f1(x),f2(x),…,fm (x)):Fn2
→Fm
2 是一个多输出函数,则
S(x)的非线性度表示为
Ns = min l(x)∈Ln
v≠0∈GF(2)m
dH(v·S(x),l(x))
S盒的非线性度指标可以由线性分布表表示,二者本质相同。非线性度考察满足
v·S(x)..u·x=1或v·S(x)..u·x=0的x 个数的最小值,线性分布表考察满足
v·S(x)..u·x=0的x 的个数,即类似于差分分布表,对于输入u 和v 的每组值,遍历
S盒输入x,计算线性分布表中的每个值:
nuv =|{x ∈ GF(2)n |v·S(x)..u·x =0}|
其中,u=0,1,…,2n -1,v=0,1,…,2m -1,点乘(·)表示两个向量的内积运算,例如:
a·b=[an-1an-2…a0]·[bn-1bn-2…b0]T =0≤i..≤n-1
aibi
将以上得到的每个值填入一个n×m 矩阵,组成S盒的线性分布表,即
L(S)=
n00 n01 … n0(2m -1)
n10 n11 … n1(2m -1)
. . . .
n(2n-1)0 n(2n-1)1 … n(2n-1)(2m -1)
.
è
.....
.
.
÷÷÷÷÷
例3-1中S盒的线性分布表如表3-3所示。
表3-3 例3-1中S盒的线性分布表
v\u 000 001 010 011 100 101 110 111
000 8 4 4 4 4 4 4 4
001 4 6 2 4 6 4 4 6
010 4 6 4 2 2 4 2 4
011 4 4 2 2 4 4 6 2
100 4 2 2 4 4 6 2 4
37
续表
分组密码设计与评估
v\u 000 001 010 011 100 101 110 111
101 4 4 4 4 6 2 2 2
110 4 4 6 2 6 6 4 4
111 4 6 4 6 4 6 4 2
表3-3中输入掩码为001时,输出掩码为001的概率为p(001→001)=28
=14
,以此
类推。根据定义3-5容易得到上述S盒的非线性度为2。
在随机情形下,输入掩码u∈Fn2
对应输出掩码v∈Fm
2 的概率p 为12
。用线性逼近
能更好地刻画等式v·S(x)=u·x 成立的有效性,即p-12
,通常称为线性逼近优
势,v·S(x)=u·x 成立的概率p 满足p-12
≤12
-NS
2n 。
1993年,Matsui提出了适用于分组密码的线性分析方法,该攻击手段本质上基于
S盒的低非线性度。给定一个n×m 的S盒,线性分析者计算以下布尔函数值为1的自
变量x 的个数:
f(x1,x2,…,xn)= a0 .. .. n
i=1(aixi) ( ) ( ) .. .. m
j=1( (bjfj(x1,x2,…,xn)))
其中a0∈Fn2
,且(a1,a2,…,an )∈Fn2
,(b1,b2,…,bm )∈Fm
2 的分量均不全为0,即计算
S盒所有分量函数的任意非零线性组合的非线性度,使之不偏离2n-1太远。
由此可见,为抵抗线性分析,S盒的非线性度越大越好。利用布尔函数非线性的有关
结论可得,4×m 的S盒和8×m 的S盒的最佳优势分别为2-2和2-4。
3.1.3 代数次数和项数
S盒的代数次数用于衡量S盒的代数非线性程度,代数次数的大小一定程度上反映
了S盒的线性复杂度,S盒线性复杂度越高,越难用线性表达式逼近。而项数分布的程度
和插值攻击密切相关。
定义3-6 设n 元布尔函数f:Fn2
→F2 的代数正规型为
f(x)=a0 ..1≤i1<Σ…<ik ≤n
1≤k≤n
ai1i2…ikxi1xi2 …xik
其中x=(x1,x2,…,xn),a0,ai1i2…ik ∈F2。f(x)的代数次数D (f)为
D (f)=max{0≤k ≤n|ai1i2…ik =1,1≤i1 < … <ik ≤n}
f(x)的代数正规型中的i 次项的个数称为f(x)的i 次项数,所有i(1≤i≤n)次项数之
和称为f(x)的项数,即代数项数N (f)为
N (f)=|{a0 =1,ai1i2…ik =1,1≤i1 < … <ik ≤n,1≤k ≤n}|
由于S盒由若干布尔函数表示,所以关于S盒的代数次数作出如下描述。
38
第3章 非线性组件
定义3-7 设n×m 的S盒
S(x)=(f1(x),f2(x),…,fm (x)):Fn2
→Fm
2
其代数次数定义为
D (S)=min{D (v·S)|v ≠0,v ∈Fm
2 }
=min{D (.. m
i=1(vifi(x))) v =(v1,v2,…,vm )≠0}
其中D (S)表示S盒的代数次数。特别地,当D (S)=k 时,称S 为k 次S盒。
与代数次数定义类似,取项数最小的f(x)=v·S(x)的项数为S盒的项数,即
N (S)=min{N (v·S)|v ≠0,v ∈Fm
2 }
=min{N (.. m
i=1(vifi(x))) v =(v1,v2,…,vm )≠0}
显然,对于非线性度最优的n×m 的S盒,其代数次数可能达到的最大值为n-1,而
且具有D (S)=n-1的S盒是存在的。
例3-2 对于如表3-1所示的S盒,假设输入为(x2,x1,x0),输出为(y2,y1,y0),对
应的真值表如表3-4所示。对于输出比特y0,容易列出其布尔表达式,进一步可写成代
数正规型:
y0 =f0(x)
=x2x1x0 ..x2x1x0 ..x2x1x0 ..x2x1x0
=x0 ..x1 ..x1x0 ..x2x0 ..x2x1
表3-4 真值表
x2 x1 x0 y2 y1 y0
0 0 0 0 1 0
0 0 1 1 0 1
0 1 0 0 1 1
0 1 1 1 1 1
1 0 0 1 1 0
1 0 1 1 0 0
1 1 0 0 0 0
1 1 1 0 0 1
同理可得y1、y2 的代数正规型:
y1 =1..x0 ..x1x0 ..x2x1
y2 =x0 ..x2 ..x2x0 ..x2x1
容易推出,将这3个代数正规型线性组合之后,代数次数最小仍为2,所以此S盒代数次
数为2。
对于一个好的S盒,每个分量布尔函数的代数次数最佳为n-1。若存在分量布尔函
数的代数次数太小,则安全性方面相应的积分性质较差,容易受积分分析的攻击。同样,
若D (S)很小,且具有D (S)次项的各组合布尔函数的项数也很少,则可用较低次的布尔
39
分组密码设计与评估
函数进行快速逼近,因此密码性能安全的S盒要有一定的代数次数和项数。
例3-3 由例3-2可知,该S盒具有代数正规型
y0 =x0 ..x1 ..x1x0 ..x2x0 ..x2x1
y1 =1..x0 ..x1x0 ..x2x1
y2 =x0 ..x2 ..x2x0 ..x2x1
ì
.
í
..
..
选择S盒的输入X 满足集合V={000,001,010,011},对S盒的3个分量布尔函数
进行积分,得
∫X ∈Vy0 =∫X ∈V (x0 ..x1 ..x1x0 ..x2x0 ..x2x1)=1
∫X ∈Vy1 =∫X ∈V (1..x0 ..x1x0 ..x2x1)=1
∫X ∈Vy2 =∫X ∈V (x0 ..x2 ..x2x0 ..x2x1)=0
即当S盒的输入X 取遍V 中所有值时,S盒输出比特中最高位之和为0,其余两位之和为
1,表示为.. X ∈V
S(X )=011。这种性质可以称为S盒在集合V 上的积分性质。
图3-2 迭代结构的积分性质
基于上述S 盒,对图3-2 的两种结构作积分分析
比较:.
对于图3-2(a)中的结构,当明文P 取遍V 中的值
时,输出密文C 的最高比特之和为0,又称为平衡
比特。
. 对于图3-2(b)中的结构,当明文P 取遍V 中的
值时,输出密文C 的任意比特之和可能都不
确定。
特殊地,因为此处S盒是一个置换,所以当输入X 取
遍23 个值时,输出值的和必为0。
假设S盒的输入为n 比特,对于图3-2(a)的结构,如
果S盒的代数次数为t,则存在明文集合V 取合适的2t 个值,对应的输出存在平衡比特;
对于图3-2(b)的结构,两个S盒迭代后的代数次数可能为t2,呈指数级增长,若明文集
合V 仍然取2t 个值,则对应的输出不一定有平衡比特。因此,多轮迭代会增加代数
次数。
对于一个理想的S盒,除了代数次数之外,每个分量布尔函数的i 次项数应该接近于
n
i
.
è .
.
. ÷
2,若项数太少,有可能提高插值攻击的成功率。
3.1.4 代数免疫度
代数免疫度是针对代数攻击而提出的,与非线性度有一定的关系。如果一个布尔函
数f 的非线性度比较低,那么它的代数免疫度就比较低;如果它的代数免疫度高,它的非
40
第3章 非线性组件
线性度将不会低,然而并不保证非线性度很高。
定义3-8 设f:Fn2
→F2 是一个n 元布尔函数,则f(x)的代数免疫度AIn (f)是使
得fg=0或(f..1)g=0成立的非零布尔函数g 的最小代数次数。
定义3-9 设n×m 的S盒
S(x)=(f1(x),f2(x),…,fm (x)):Fn2
→Fm
2
则S盒代数免疫度定义为
AI(S)=min{AI(v·S)|v ≠0,v ∈Fm
2 }
=min{AI( .. m
i=1(vifi(x))) v =(v1,v2,…,vm )≠0}
例3-4 设f:F32
→F2,f(x)=x2x3..x1x2x3,当g(x)=x1 时,显然有fg=0,所
以布尔函数f 的代数免疫度为1。
定理3-3 f(x)是n 元布尔函数,则AI(f)≤ n2
n2
表示大于n2
的最小整数
.
è .
.
. ÷
。
由定理3-3可以得到代数免疫度的计算方法。如果存在一个布尔函数g(x),g(x)≠
0,有g(x)f(x)=0或g(x)(1..f(x))=0,且deg(g)<d(其中deg(g)表示g(x)的次
数),则有AI(f)<d;如果布尔函数f(x)不存在次数小于d 的零化多项式,那么f(x)的
代数免疫度为AI(f)≥d。求解AI(f)有以下几个步骤:
第一步,令d= n2
,写出次数小于d 的n 元布尔函数表达式:
g(x)=a0 ..a1x1 .. …anxn ..a1,2x1x2 .. … ..an-1,nxn-1xn
.. … ..a1,2,…,(d-1)x1x2…xd-1
.. … ..a(n-d+2),…,(n-1),nx(n-d+2)…xn-1xn
g(x)的系数个数为Σd-1
i=0
n
i
.
è .
.
. ÷
。
第二步,对于满足f(x)=1的所有x,有g(x)=0。将x 代入g(x)=0中,得到一
个线性方程组,方程的个数为w (f),未知量个数为Σd-1
i=0
n
i
.
è .
.
. ÷
。
第三步,判断是否存在次数少于d 的非零的零化多项式g(x),归结为求上述齐次线
性方程组是否存在非零解。如果上述齐次线性方程组有非零解,则找到布尔函数f(x)
的一个次数小于d 的零化多项式。令d= n2
-1,重复第一步至第三步。如果上述齐次
线性方程组只有零解,则f(x)没有次数小于d 的零化多项式。
第四步,对于满足f(x)..1=1的所有x,重复第二步和第三步。
第五步,输出AI(f)=d。
例3-5 设f(x1,x2,x3)=x1..x3..x1x3..x2x3,则d=32
=2,即g(x)的代数次
数小于2,其真值表如表3-5所示。
41
分组密码设计与评估
表3-5 f 函数真值表
x3 x2 x1 f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
设g(x)=a0..a1x1..a2x2..a3x3,将使得f(x)=1的值001、011、100、101分别代
入g(x)=0,得
a0 ..a1 =0
a0 ..a1 ..a2 =0
a0 ..a3 =0
a0 ..a1 ..a3 =0
ì
.
í
...
...
以上方程组只有零解,继续将f(x)..1=1的值000、010、011、111代入g(x)=0,得
a0 =0
a0 ..a2 =0
a0 ..a2 ..a3 =0
a0 ..a1 ..a2 ..a3 =0
ì
.
í
...
...
以上方程组也只有零解,故f(x)的代数免疫度为2。
对于输入为n 比特的布尔函数f(x),代数免疫度最佳为n2
。若对于0≠v∈Fm
2 ,都
有AI(v·S)= n2
,则该S盒的代数免疫度达到最优。
3.1.5 扩散特性和严格雪崩特性
扩散特性和严格雪崩特性用于衡量S盒输出改变量对于输入改变量的随机性,也是
S盒设计的重要指标。
定义3-10 设f:Fn2
→F2 是一个n 元布尔函数。如果f(x..α)..f(x)是一个平衡
函数,称f (x)关于非零向量α ∈Fn2
满足扩散准则。如果对所有的向量α ∈Fn2
:1≤
W H(α)<k,f(x)满足扩散准则,称f(x)满足k 次扩散准则。
上述定义中W H(α)指α 的重量,即α 的二进制表中1的个数。
定义3-11 设n×m 的S盒S(x)=(f1(x),f2(x),…,fm (x)):Fn2
→Fm
2 ,如果各
分量函数fi(x)关于α 满足扩散准则,就称S盒关于元素α∈GF(2)n 满足扩散准则。进
42
第3章 非线性组件
一步,如果S盒关于所有α∈GF(2)n ,1≤W H (α)<k 均满足扩散准则,则称S盒满足
k 次扩散准则。
特别地,若Σx (S(x)..S(x ..e))=( Σx (f1(x)..f1(x ..e),…,Σx (fm (x)..
fm (x ..e)))=(2n-1,…,2n-1)对任意e ∈ GF(2)n ,W H (e)=1均满足扩散准则,则称
S盒满足严格雪崩准则(StrictAvalancheCriterion,SAC)。
例3-6 函数f(x1,x2,x3)=x1x2..x3 不满足严格雪崩准则。
因为f(x1..1,x2,x3)..f(x1,x2,x3)=x2 和f(x1,x2..1,x3)..f(x1,x2,x3)=
x1 是平衡的,但f(x1,x2,x3..1)..f(x1,x2,x3)=1不是平衡的,所以函数f 不满足严
格雪崩准则。
例3-7 函数f(x1,x2,x3)=x1x2..x2x3..x1x3 满足严格雪崩准则。
因为f(x1..1,x2,x3)..f(x1,x2,x3)=x2..x3、f(x1,x2..1,x3)..f(x1,x2,x3)=
x1..x3 和f (x1,x2,x3..1)..f (x1,x2,x3)=x2 ..x1 都是平衡布尔函数,所以函数
f 满足严格雪崩准则。
定义3-12 设n×m 的S盒S(x)=(f1(x),f2(x),…,fm (x)):Fn2
→Fm
2 ,S盒满足
雪崩准则是指改变S盒输入的1比特,大约有一半输出比特改变。
定义3-13 设n×m 的S盒S(x)=(f1(x),f2(x),…,fm (x)):Fn2
→Fm
2 ,S盒满足
严格雪崩准则是指改变输入的1比特,每个输出比特改变的概率为12
。
此定义是对严格雪崩准则的另一种解释,是定义3-11的特殊情形。
例3-8 如图3-3所示,哈希函数输出摘要值为160比特,输入改变1比特时,摘要值
随之改变了大约一半。当输入000变为001时,摘要值改变了79比特;当000变为010
时,摘要值改变了79比特;当001变为010时,摘要值改变了85比特。
这个哈希函数展示了良好的雪崩效应。
图3-3 哈希函数的雪崩效应
除了差分均匀度、非线性度、代数次数和项数、代数免疫度、扩散特性与严格雪崩特性
这几个主要的密码指标之外,设计S盒时还要注意能否满足可逆性、消除不动点等。值得
注意的是,S盒的某些密码指标是一致的,如差分均匀度与非线性度,某些指标有一定的
43
分组密码设计与评估
制约关系,如代数次数与扩散特性,具体设计时需要折中考虑。
3.2 S盒的设计方法
基于3.1节所述S盒的几项主要密码指标,人们提出了许多S盒设计方法。一般地,
可以将S盒的设计方法分成三大类:第一类是随机生成,便于密码系统中动态S盒替换;
第二类是基于数学函数设计,容易达到密码安全指标;第三类是基于已有组件设计,便于
软硬件实现。在轻量级算法设计中由于资源受限,S盒设计倾向于更少的逻辑电路门数
和深度,设计这一类S盒时,在保证密码指标的前提下可以通过启发式算法等方法进行逻
辑电路门数和深度搜索。
3.2.1 随机生成
利用随机生成方法设计的S盒可以使人们相信没有陷门。其基本步骤是:随机生成
一批S盒,再对它们进行测试,选出指标性能较好的进行应用。尽管这是一种完全随机的
S盒设计方法,但是用这种方法寻找好的S盒需要花费很多时间,并且要在设计者计算能
力允许的条件下进行。
例3-9 DES的S盒一般被认为是随机设计的,1976年美国NSA 披露了该S盒的设
计原则:
(1)每个S盒的每一行是整数0~15的一个全排列。
(2)每个S盒的输出都不是其输入的线性函数或仿射函数。
(3)改变S盒任意1比特的输入,其输出至少有2比特发生变化。
(4)对S盒的任意6比特输入x,S(x)与S(x..001100)至少有2比特不同。
(5)对S盒的任意6比特输入x,且α,β∈{0,1},有S(x)≠S(x..11αβ00)。
(6)保持S盒的任一位输入不变,其他5位输入任意变化时,所有4比特输出中0与
1的总数接近相等。
根据以上原则,设计者给出了8个S盒,以S1 为例,如表3-6所示。S1 包含4行,每
一行都是0~15的一个全排列。设输入Bj=b1b2b3b4b5b6,将b1b6 和b2b3b4b5 作为二进
制数,若b1b6 和b2b3b4b5 对应的十进制数分别为r 和c(0≤r≤3,0≤c≤15),则S1 中的
第r 行、第c 列处的十进制数对应的二进制形式就是S1 的输出。例如,输入110100,首
尾2比特“10”对应2所指示的行,中间4比特“1010”对应10指示的列,S1 输出为2行
10列交叉处的数字9,对应二进制形式为1001。
表3-6 DES的S1
S1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
44
第3章非线性组件
由于S1 输入6比特,输出4比特,所以平均每4个不同输入对应一个相同的输出,差
分均匀度比较大。表3-7是S1 的差分分布表。
表3-
7
S1
的差分分布表
S1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 6 0 2 4 4 0 10 12 4 10 6 2 4
2 0 0 0 8 0 4 4 4 0 6 8 6 12 6 4 2
3 14 4 2 2 10 6 4 2 6 4 4 0 2 2 2 0
4 0 0 0 6 0 10 10 6 0 4 6 4 2 8 6 2
5 4 8 6 2 2 4 4 2 0 4 4 0 12 2 4 6
6 0 4 2 4 8 2 6 2 8 4 4 2 4 2 0 12
7 2 4 10 4 0 4 8 4 2 4 8 2 2 2 4 4
8 0 0 0 12 0 8 8 4 0 6 2 8 8 2 2 4
9 10 2 4 0 2 4 6 0 2 2 8 0 10 0 2 12
10 0 8 6 2 2 8 6 0 6 4 6 0 4 0 2 10
11 2 4 0 10 2 2 4 0 2 6 2 6 6 4 2 12
12 0 0 0 8 0 6 6 0 0 6 6 4 6 6 14 2
13 6 6 4 8 4 8 2 6 0 6 4 6 0 2 0 2
14 0 4 8 8 6 6 4 0 6 6 4 0 0 4 0 8
15 2 0 2 4 4 6 4 2 4 8 2 2 2 6 8 8
16 0 0 0 0 0 0 2 14 0 6 6 12 4 6 8 6
17 6 8 2 4 6 4 8 6 4 0 6 6 0 4 0 0
18 0 8 4 2 6 6 4 6 6 4 2 6 6 0 4 0
19 2 4 4 6 2 0 4 6 2 0 6 8 4 6 4 6
20 0 8 8 0 10 0 4 2 8 2 2 4 4 8 4 0
21 0 4 6 4 2 2 4 10 6 2 0 10 0 4 6 4
22 0 8 10 8 0 2 2 6 10 2 0 2 0 6 2 6
23 4 4 6 0 10 6 0 2 4 4 4 6 6 6 2 0
24 0 6 6 0 8 4 2 2 2 4 6 8 6 6 2 2
25 2 6 2 4 0 8 4 6 10 4 0 4 2 8 4 0
26 0 6 4 0 4 6 6 6 6 2 2 0 4 4 6 8
27 4 4 2 4 10 6 6 4 6 2 2 4 2 2 4 2
45
分组密码设计与评估
续表
S1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
28 0 10 10 6 6 0 0 12 6 4 0 0 2 4 4 0
29 4 2 4 0 8 0 0 2 10 0 2 6 6 6 14 0
30 0 2 6 0 14 2 0 0 6 4 10 8 2 2 6 2
31 2 4 10 6 2 2 2 8 6 8 0 0 0 4 6 4
32 0 0 0 10 0 12 8 2 0 6 4 4 4 2 0 12
33 0 4 2 4 4 8 10 0 4 4 10 0 4 0 2 8
34 10 4 6 2 2 8 2 2 2 2 6 0 4 0 4 10
35 0 4 4 8 0 2 6 0 6 6 2 10 2 4 0 10
36 12 0 0 2 2 2 2 0 14 14 2 0 2 6 2 4
37 6 4 4 12 4 4 4 10 2 2 2 0 4 2 2 2
38 0 0 4 10 10 10 2 4 0 4 6 4 4 4 2 0
39 10 4 2 0 2 4 2 0 4 8 0 4 8 8 4 4
40 12 2 2 8 2 6 12 0 0 2 6 0 4 0 6 2
41 4 2 2 10 0 2 4 0 0 14 10 2 4 6 0 4
42 4 2 4 6 0 2 8 2 2 14 2 6 2 6 2 2
43 12 2 2 2 4 6 6 2 0 2 6 2 6 0 8 4
44 4 2 2 4 0 2 10 4 2 2 4 8 8 4 2 6
45 6 2 6 2 8 4 4 4 2 4 6 0 8 2 0 6
46 6 6 2 2 0 2 4 6 4 0 6 2 12 2 6 4
47 2 2 2 2 2 6 8 8 2 4 4 6 8 2 4 2
48 0 4 6 0 12 6 2 2 8 2 4 4 6 2 2 4
49 4 8 2 10 2 2 2 2 6 0 0 2 2 4 10 8
50 4 2 6 4 4 2 2 4 6 6 4 8 2 2 8 0
51 4 4 6 2 10 8 4 2 4 0 2 2 4 6 2 4
52 0 8 16 6 2 0 0 12 6 0 0 0 0 8 0 6
53 2 2 4 0 8 0 0 0 14 4 6 8 0 2 14 0
54 2 6 2 2 8 0 2 2 4 2 6 8 6 4 10 0
55 2 2 12 4 2 4 4 10 4 4 2 6 0 2 2 4
56 0 6 2 2 2 0 2 2 4 6 4 4 4 6 10 10
57 6 2 2 4 12 6 4 8 4 0 2 4 2 4 4 0
46
第3章 非线性组件
续表
S1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
58 6 4 6 4 6 8 0 6 2 2 6 2 2 6 4 0
59 2 6 4 0 0 2 4 6 4 6 8 6 4 4 6 2
60 0 10 4 0 12 0 4 2 6 0 4 12 4 4 2 0
61 0 8 6 2 2 6 0 8 4 4 0 4 0 12 4 4
62 4 8 2 2 2 4 4 14 4 2 0 2 0 8 4 4
63 4 8 4 2 4 0 2 4 4 2 4 8 8 6 2 2
显然,S1 的差分均匀度为16,根据3.1节其他密码指标的定义,可测得非线性度为
18,4个分量布尔函数的代数次数都为5,代数项数为[27,33,38,29],代数免疫度为[4,5,
4,5]。
3.2.2 基于数学函数设计
在大多数情况下,基于数学函数设计可以保证S盒有较好的密码性能。常用的设计
方法有下面几种。
1. 对数函数和指数函数
对数函数和指数函数互为反函数,基于有限域上的这两类函数可以构造S盒以及
S盒的逆,例如SAFER系列分组密码使用的S盒[9]。
例3-10 SAFER 系列分组密码的S盒设计采用了两个函数,分别是对数函数y=
logax 和指数函数y=ax ,具体如下:
. 对数函数为log45x。当x=0时,约定log450=128。
. 指数函数为45xmod257。当x=128时,约定45128mod257=0。
它们的差分均匀度在传统的异或运算下并不好,但是SAFER 系列分组密码的轮密
钥嵌入使用了模256加,在差分定义为模256减时,它们的差分均匀性还可以接受。指数
函数的分量布尔函数的代数次数为[7,7,7,7,7,7,6,6],代数项数为[160,138,121,130,
119,108,46,56];对数函数的分量布尔函数代数次数都为7,代数项数为[122,126,113,
123,138,110,104,110]。
2. 有限域上的逆映射
许多著名的密码算法采用伽罗瓦域上的逆映射作为S盒。例如,SHARK、Square、
AES等密码算法的S盒设计都采用了这种方法。
例3-11 SHARK 的S盒基于GF(2m )上的映射F (x)=x-1设计。差分均匀度为
4,代数次数等于m -1。然而,由于该S盒在GF(2n)中的表达式太简单,导致了SHARK
密码对插值攻击的脆弱性。
基于不同代数结构上数学函数的复合运算进行设计可以消除抗插值攻击的脆弱性,
例如AES分组密码的S盒设计。
47
分组密码设计与评估
例3-12 AES的S盒由以下两个有限域上的变换合成而得。在GF(28)中定义不可
约多项式m (x)=x8+x4+x3+x+1。
(1)对于x≠00,在GF(28)上计算x→x-1,定义00→00。
(2)对得到的逆字节进行GF(2)的仿射变换:
s7
s6
s5
s4
s3
s2
s1
s0
é
.
êêêêêêêêêêêê
ù
.
úúúúúúúúúúúú
=
1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1
1 0 0 0 1 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 0 0 0 1
é
.
êêêêêêêêêêêê
ù
.
úúúúúúúúúúúú
y7
y6
y5
y4
y3
y2
y1
y0
é
.
êêêêêêêêêêêê
ù
.
úúúúúúúúúúúú
+
01100011
é
.
êêêêêêêêêêêê
ù
.
úúúúúúúúúúúú
按上述方法构造的AES的S盒如表3-8所示。这种S盒的差分均匀度为4,非线性
度为112,都达到了最优。分量布尔函数的代数次数为[7,7,7,7,7,7,7,7],代数项数为
[110,112,114,131,136,145,133,132],代数免疫度为[4,4,4,4,4,4,4,4],也都达到了
最优。
表3-8 S盒的列表描述
S 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
4 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6 d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
A e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
B e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
C ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
D 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
E e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
F 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16
48
第3章 非线性组件
3. 有限域上的幂函数
利用有限域上的特殊函数设计S盒引起了许多研究者的关注,基于幂函数y=xa 的
设计应运而生,例如MISTY算法中使用的S盒[76]。
例3-13 MISTY算法一共有两个S盒,分别是7比特输入输出的S7 和9比特输入
输出的S9。设计S7 和S9 的三大标准如下:
(1)平均差分/线性概率足够小。
(2)硬件实现延迟小。
(3)代数次数尽可能高。
S盒的设计原则主要为利用GF(27)和GF(29)上的幂函数并进行仿射变换A..xα..
B,α 要满足(2i-1,α)=1,遍历线性变换A 和部分B,不影响差分均匀度和线性概率,但
是会影响代数次数和硬件实现效率(延迟)。值得注意的是,代数次数与α 的海明重量
一致。遍
历Si(x)=A..xα(i=7,9)的线性变换A 。对于GF(27)上的S7,通过测试得到每
个布尔函数:
. 代数次数为4时,输出比特的逻辑电路深度至少为21。
. 代数次数为3时,输出比特的逻辑电路深度至少为10。
. 代数次数为2时,输出比特的逻辑电路深度至少为1。
经折中考虑,选择代数次数为3、代数项数为13的S7。以下是其输出比特的7个布
尔表达式:
y0 =x0 ..x1x3 ..x0x3x4 ..x1x5 ..x0x2x5 ..x4x5 ..x0x1x6 ..x2x6
..x0x5x6 ..x3x5x6 ..1
y1 =x0x2 ..x0x4 ..x3x4 ..x1x5 ..x2x4x5 ..x6 ..x0x6 ..x3x6 ..x2x3x6
..x1x4x6 ..x0x5x6 ..1
y2 =x1x2 ..x0x2x3 ..x4 ..x1x4 ..x0x1x4 ..x0x5 ..x0x4x5 ..x3x4x5 ..x1x6
..x3x6 ..x0x3x6 ..x4x6 ..x2x4x6
y3 = x0 ..x1 ..x0x1x2 ..x0x3 ..x2x4 ..x1x4x5 ..x2x6
..x1x3x6 ..x0x4x6 ..x5x6 ..1
y4 =xdx3 ..x0x4 ..x1x3x4 ..x5 ..x2x5 ..x1x2x5 ..x0x3x5 ..x1x6 ..x1x5x6
..x4x5x6 ..1
y5 =x0 ..x1 ..x2 ..x0x1x2 ..x0x3 ..x1x2x3 ..x1x4 ..x0x2x4 ..x0x5
..x0x1x5 ..x3x5 ..x0x6 ..x2x5x6
y6 =x0x1 ..x3 ..x0x3 ..x2x3x4 ..x0x5 ..x2x5 ..x3x5 ..x1x3x5 ..x1x6
..x1x2x6 ..x0x3x6 ..x4x6 ..x2x5x6
S9 为GF(29)上的线性变换A..xα,选择代数次数为2,最小硬件实现逻辑电路深度
为12。以下是S9 的9个输出比特表达式:
y0 =x0x4 ..x0x5 ..x1x5 ..x1x6 ..x2x6 ..x2x7 ..x3x7 ..x3x8 ..x4x8 ..1
49
分组密码设计与评估
y1 = x0x2 ..x3 ..x1x3 ..x2x3 ..x3x4 ..x4x5 ..x1x5 ..x0x6 ..x2x6 ..x7
..x0x8 ..x3x8 ..x5x8 ..1
y2 = x0x1 ..x1x3 ..x4 ..x0x4 ..x2x4 ..x3x4 ..x4x5 ..x0x6 ..x5x6 ..x1x7
..x3x7 ..x8
y3 = x0 ..x1x2 ..x2x4 ..x5 ..x1x5 ..x3x5 ..x4x5 ..x5x6 ..x1x7 ..x6x7
..x2x8 ..x4x8
y4 = x1 ..x0x3 ..x2x3 ..x0x5 ..x3x5 ..x6 ..x2x6 ..x4x6 ..x5x6 ..x6x7
..x2x8 ..x7x8
y5 = x2 ..x0x3 ..x1x4 ..x3x4 ..x1x6 ..x4x6 ..x7 ..x3x7 ..x5x7 ..x6x7 ..x0x8
..x7x8
y6 =x0x1 ..x3 ..x1x4 ..x2x5 ..x4x5 ..x2x7 ..x5x7 ..x8 ..x0x8 ..x4x8
..x6x8 ..x7x8 ..1
y7 =x1 ..x0x1 ..x1x2 ..x2x3 ..x0x4 ..x5 ..x1x6 ..x3x6 ..x0x7 ..x4x7
..x6x7 ..x1x8 ..1
y8 =x0 ..x0x1 ..x1x2 ..x4 ..x0x5 ..x2x5 ..x3x6 ..x5x6 ..x0x7 ..x0x8
..x3x8 ..x6x8 ..1
上述两个S盒的差分均匀度都为2,属于APN 置换。然而,由于代数次数太低,采用
这两个S盒设计的MISTY1和KASUMI算法都已被理论攻破。因此,基于代数次数太
低的S盒设计密码算法,若迭代轮数不够则容易受到高阶差分分析或积分分析攻击。目
前一般不直接用幂函数作为S盒,对它的研究还在继续。
3.2.3 基于已有组件设计
1. 基于已有S 盒设计
基于一些已知的密码性能良好的S盒也可以构造新的S盒,例如Serpent算法所使
用的S盒就是基于DES的S盒构造出来的[77]。通过这种构造方法找到一个各项指标都
满足的S盒并不容易。小规模S盒组合构造的方式有很多,相对容易穷举测试;但是组合
生成的大规模S盒不一定满足所有设计指标。
例3-14 Serpent算法采用8个不同的4比特S盒,需满足以下3个准则:
(1)每个差分特性的最大概率为14
,并且只有1比特非零的输入差分将永远不会导
致只有1比特非零的输出差分。
(2)每个线性逼近的概率在12
±14
范围内,并且只有1比特非零的输入掩码与只有
1比特非零的输出掩码之间的线性关系概率在12
±18
范围内。
(3)每个分量布尔函数的非线性次数最大,即达到3。
S盒的设计原理借鉴了RC4的模式。首先设两个数组,分别是Serpent[.]和sbox
[32][16]。Serpent[.]包含“sboxesforserpent”这16个字符的ASCII码低4位值;sbox
50
第3章 非线性组件
[32][16]是32×16的二维数组,用8个DES的S盒(代码中记为sbox)对其进行初始化。
Swapentries(·,·)的作用是交换值,具体交换如算法3-1所示。如果生成的数组满足所
需的差分和线性指标,保存该数组并将其作为S盒。重复该过程,直到生成8个S盒。
算法3-1 Serpent的8个S盒生成
index :=0
repeat
currentsbox :=index modulo 32;
for i :=0 to 15 do
j :=sbox[(currentsbox+1) modulo 32][serpent[i]];
swapentries (sbox[currentsbox][i],sbox[currentsbox][j]);
if sbox[currentsbox][.]has the desired properties, save it;
index :=index +1;
until 8 S-boxes have been generated
为了更好地理解算法3-1,以下对该代码作简要解释。
符号约定:currentsbox用c表示,index用in表示,sbox用s表示,serpent用se表
示,算法3-1的流程图如图3-4所示。
图3-4 算法3-1的流程图
例3-15 分组密码Serpent数组长为16,其内容为“sboxesforserpent”这16个字符
的ASCII码低4位值,如图3-5所示。
51
分组密码设计与评估
图3-5 “sboxesforserpent”的低4位
sbox数组是由DES的8个S盒初始化而成的。下面以DES的S1 为例,它对应
sbox[4][16]共64个数。
当i=0,c=0时,进入循环。
当i=0时,j=s[1][3]=4,此时交换s[0][0]与s[0][4]的值。
当i=1时,j=s[1][2]=7,此时交换s[0][1]与s[0][7]的值。
……
一直循环到i=15,此时会产生一个新的S盒sbox[0][.],如图3-6所示。判断该
S盒是否满足标准,若满足则保存下来。最终生成的8个S盒如表3-9所示。
图3-6 新的S盒sbox[0][.]
表3-9 生成的8个S盒
S1 3 8 15 1 10 6 5 11 14 13 4 2 7 0 9 12
S2 15 12 2 7 9 0 5 10 1 11 14 8 6 13 3 4
S3 8 6 7 9 3 12 10 15 13 1 14 4 0 11 5 2
S4 0 15 11 8 12 9 6 3 13 1 2 4 10 7 5 14
S5 1 15 8 3 12 0 11 6 2 5 4 10 9 14 7 13
S6 15 5 2 11 4 10 9 12 0 3 14 8 13 6 7 1
S7 7 2 12 5 8 4 6 11 14 9 1 15 13 3 10 0
S8 1 13 15 0 14 8 2 11 7 4 12 10 9 3 5 6
关于这8个S盒的安全指标测试留作习题。
2. 基于特定结构的S 盒构造
下面基于经典的分组密码整体结构进行新的S盒构造,例如CRYPTONv0.5和
CRYPTONv1.0分别基于Feistel结构、SP结构设计了S盒[80]。
例3-16 分组密码CRYPTONv0.5中使用的S盒基于3轮Feistel结构构造,生成
的S0 和S1 互逆,如图3-7所示。
其中,s0、s1 和s2 是3个4×4的小规模S盒,不要求可逆,如表3-10所示。
52
第3章非线性组件
图35的S盒
-7CRYPTONv0.
表3-10 3
个4×4
的小规模S盒
x
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
s0 15 9 6 8 9 9 4 12 6 2 6 10 1 3 5 15
s1 10 15 4 7 5 2 14 6 9 3 12 8 13 1 11 0
s2 0 4 8 4 2 15 8 13 1 1 15 7 2 11 14 15
、1 和s2 的差分均匀度分别为2、4、4。以s0 为例,虽然其不可逆,但是并不影响差分均匀度达(s) 到最(s) 优2。由这3个小规模S盒构成的两个大规模S盒S0(0) 、S1 差分均匀度都为8。
例30中使用的S盒利用可逆SP 结构构造,如图38和表3
-17
CRYPTONv1.--11
所示,其中s0、s1 是两个4×4 的可逆S盒。
输入的8比特分两组,分别查s0、s1,输出的8比特再进行线性变换,最后经过两个小
规模S盒的逆输出。显然,新构成的S盒是对合的,即S=S-1。
图30的S盒
-8CRYPTONv1.
表3-11
两个4×4
的小规模S盒
x
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
s0 15 14 10 1 11 5 8 13 9 3 2 7 0 6 4 12
s1 11 10 13 7 8 14 0 5 15 6 3 4 1 9 2 12
53