Page 219 - 《软件学报》2021年第9期

尚方舟 等:概率积分及其在 PUFFIN 算法中的应用 2843

经过 P64 后,活跃位置将位于同一列:
12 50 24 0 33 56 8 61 36 32 23 55 13 17 20 11
1 26 6 48 52 19 51 29 16 43 54 38 3 53 34 28
59 9 31 46 15 47 5 27 57 45 62 14 4 41 39 42
49 35 60 18 21 40 30 10 7 58 37 22 25 44 2 63

再经过第 1 轮的非线性层γ后,状态为:
0 4 0 y 12 16 20 24 28 32 36 40 44 48 52 56 60
1 5 1 y 13 17 21 25 29 33 37 41 45 49 53 57 61
2 6 2 y 14 18 22 26 30 34 38 42 46 50 54 58 62
3 7 3 y 15 19 23 27 31 35 39 43 47 51 55 59 63

记这 4 个位置的变量分别为 y 0 ,y 1 ,y 2 ,y 3 ,再利用算法 2 运算得到经过前 5 轮加密以及第 6 轮非线性层和密钥
加运算后每一比特位置概率布尔多项式具体表达式.
算法 2. 概率布尔多项式求解过程.
输入:state[8]=y 0 ,state[9]=y 1 ,state[10]=y 2 ,state[11]=y 3 ,其余 state[i]=0.5;
输出:state[j](j=0,1,…,63).
1: for i=1 to 5 do
2: P(state); //对 state 进行线性变换
3: Gamma(state); //对 state 每一列通过 S 盒变换
4: Add-key(state); //对 state 每一比特进行密钥异或运算
5: end for
算法 2 中,state 的每一个比特位置均用概率布尔多项式表示,初始状态的第 8 个~第 11 个位置设为变量,其
余位置为常数 0.5.依次经过第 1 轮线性变换、第 2 轮~第 5 轮轮函数以及第 6 轮非线性层和密钥加运算.其中,S
盒具体表示如图 3 所示.运算均遵循概率布尔多项式运算法则,密钥异或操作是将概率布尔多项式中常数项重
置为 0.5.由于在加密过程中将所有轮密钥视作随机的,取值为 0 或为 1 的概率相同,均为 0.5,因此对于密钥加过
程置常数为 0.5 这一操作,使得该方法适用于所有密钥.为验证该步骤的正确性,基于密钥扩展算法,我们进行了
10 000 000 次实验,每次实验随机选定种子密钥,计算所有轮密钥每一比特位置为 1 的概率,并将该概率代入算
法 2 中进行实验,得到的结果与“常数重置”方法基本完全一致,误差小于 0.1%.这是由于该方法主要利用概率布
尔多项式的首项系数,因此末尾常数项对于首项系数影响很小.为简化算法,故而密钥异或操作是将概率布尔多
项式中的常数项重置为 0.5.
3 x 2 x 1 x 0 x

3 y 2 y 1 y 0 y
Fig.3 Input and output of S box
图 3 S 盒的输入输出
该算法的计算复杂度主要集中在 Gamma 函数中概率布尔多项式之间的乘法,由于 PUFFIN 算法采用 4 比
33
特 S 盒,由算法 1 可知,每次乘法的计算复杂度至多为 2 2 41+ + 1 = 2 .该 S 盒共包含 29 次乘法运算,故求解 PUFFIN
33
算法输出每一比特概率布尔多项式表达式的计算复杂度至多为 5×16×29×2 ≈2 44.18 .本文在具体实现过程中,通
过设置阈值的方式降低复杂度,即概率低于 0.000 5 时,将此概率置为 0.阈值越小,算法误差越小,但复杂度越大.