关 杰, 卢健伟, 刘 帅

战略支援部队信息工程大学, 郑州450001

1 引言

元胞自动机[1]是一种用来模拟和分析复杂离散问题的并行计算模型, 能够由一些简单的局部规则产生较为复杂的变换, 组合后可以实现混淆和扩散[2], 也可以用于伪随机数生成器的构造[3], 因此在密码学中有许多的应用. 我们可以将元胞自动机的变换过程定义为S 盒变换, 称其为基于元胞自动机的S 盒[4].这类S 盒一般实现代价较低, 并且有良好的安全性能, 最经典的是作为SHA-3[5]标准之一的Keccak 杂凑函数[6]的S 盒. 另外, Panama[7]、RadioGatún[8]、Subterranean[9]和3Way[10]所使用的S 盒也与Keccak 的S 盒有相同的局部规则.

文献[11] 中提出了一类新的基于元胞自动机的S 盒Fnnew, 它的局部规则的作用域范围为5 个元胞,具有较小的软件与硬件成本. 该类S 盒的具体描述如下:

2 基本概念

3 的线性性质分析

那么ρf(0)=0.

引理2[14]若布尔函数f(x) 和g(x) 是互为仿射等价的, 则ρf(0)=ρg(0).

该引理揭示了对于一个布尔函数的输入变量进行可逆线性变换后, 在0 点的Walsh 谱不变. 史丹萍等人给出了一个不相交化算法(算法1[14], 具体见附录), 可以有效地将任意给定的二次布尔函数转换为不相交二次型.

引理3[14]对于不相交二次型f=xi1xi2+···+xi2k−1xi2k+xj1+···+xjs,f在0 点的Walsh谱值计算方法如下:

这里coef(xu) 表示xu在f中的系数.

引理3 提供了计算不相交二次型在0 点的Walsh 谱值的一种方法, 其中k表示f中不同二次项的个数, 根据算法1 和引理3 我们可以有效地计算出任意二次布尔函数在0 点的Walsh 谱值.

3.1 关于Fnnew 谱值取值范围的猜想证明

文献[12] 给出了针对Keccak 算法S 盒的相关结论的证……