NFSR代数次数估计

NFSR代数次数估计的主要方法是基于数值映射的方法与单项式预测方法（一种准确计算代数次数的方法）。数值映射的方法效率高，但基于可分性的单项式预测方法准确性更好。NFSR也称非线性反馈移位寄存器，是密码算法中一个基本组件，在流密码中比较常见，例如Trivium和ZUC等流密码的核心部件均为NFSR。NFSR在每个时刻用一个非线性的反馈函数$f$计算新的比特，并移出最早的比特。

1.数值映射方法

数值映射方法由刘美成在2017年的美密会[1]上提出。定义如下：

定义1(数值映射) 设$f(x_1,x_2,…,x_n)∈B_n$为$n$元布尔函数，存在如下映射，记为$DEG$：
$DEG:\left\{ \begin{array}{cl} \mathbb{B}_n \times \mathbb{Z}^n \to \mathbb{Z}\\ (f,\textbf{D})\mapsto \max_{a_c \neq 0 } \{\sum_{i=1}^n c_id_i\} \end{array} \right.$

其中$D=(d_1,d_2,…,d_n)∈Z^n$为$ n $维向量，且$a_c$为上述$f$的代数正规型的系数。

数值映射的核心是只保留每个状态的度数的上界，再用这些上界给出下一个状态的上界。具体来说，即反复运用以下两个平凡的上界，通过一定深度的展开对多个上界取最小，从而得到更紧的界。

值得注意的是，随着轮数的展开，运用上述的方式会得到不唯一的结果，如下图所示，这时会选择估计次数的最大值。而且状态不局限NFSR某时刻的某一比特，计算中的中间结果(不同的计算方式会产生不同的中间结果)也可以记忆化。

由于实测中不同状态的准确度不一样，这种看似累赘的拆分是有效的。在展开的轮数认为是常数时，该算法是线性的。数值映射方法另一个直接的改进是对前N轮直接计算代数标准型，从而获得准确的代数次数。在数值映射方法中仅展开了一层就能在Trivium -like的几种密码算法中达到当时最优的结果。在后续的文章中对数值映射方法做了一个简洁的改进，添加如下的平凡上界：

$degree(f(x)) \leq f(x/x') + \#x'$

注意如果反复递归计算使用该界会达到指数级的复杂度。在图中只在最后使用了这个上界，并且每步贪心的选取一个比特下降。这使总的复杂度保持在$O(n²)$ 。上述算法可以总结为如下：

其中$N_0$代表暴力计算的轮数，depBack表示展开层数，numDecent代表末尾优化时要枚举的汉明重量。

2.单项式预测方法

单项式预测方法是主流的序列密码攻击方法。2018年Todo等人提出基于可分性的立方攻击[2]，其核心思想是选择合适的指标集 $I$ , 在给定轮数下，利用可分性确定输出比特的超多项式 $p_{t_I}$ 中包含的秘密变量，这些秘密变量构成集合 $J$。然后，通过计算真值表恢复超多项式以建立代数方程组，从而恢复秘密变量。但是在实际攻击过程中，该攻击受到指标集 $I$ 和集合 $J$ 大小的限制，$|I|+|J|≥n$时, 该攻击没有意义。
在2020年亚密会上，胡凯等人将郝泳霖等人提出的无未知子集的三子集可分性理论，从密码代数结构的角度解释为单项式传播理论[3]。该理论中作者将单项式的存在性与单项式路径数量的奇偶性建立了联系，将自动化模型中的一个解对应为一条单项式路径。基于此，作者提出了单项式预测技术，通过计算单项式路径的个数来确定该单项式是否存在于超多项式中，从而可以准确计算超多项式的代数标准型。利用该技术及一些分治策略，作者首次可以计算1-834轮Trivium流密码的精确代数次数。
该方法的主要思想为：要计算一个迭代布尔函数的代数次数可以归结为判定一系列单项式是否在最后迭代的结果中出现，即进行单项式的预测。而单项式预测需要搜索代数系统中的单项式路径及单项式路径的数量。具体如下：
假设$f$是一个由一些简单函数$f^{(i)}$组合而成的复合向量布尔函数，我们记第$i$轮使用的迭代函数为$f^{(i)}$，输入为$x^{(i)}$，输出为$x^{(i+1)}$。

$f=f^((r-1))∘f^((r-2) )∘⋯∘f^((0))$

若$x^{(i+1)}$中包含$x^{(i)}$，则记为$x^{(i)} \to x^{(i+1)}$。若对于一系列单项式$(x^{(0)},x^{(1)}…,x^{(r)})$满足

$x^{(0)}\to x^{(1)}\to \cdots \to x^{(r)}$

则对于这样的一条路径称为$x^{(0)}$到$x^{(r)}$的一条单项式路径。一个主要的结论是$x^{(0)} \to x^{(r)}$当且仅当$x^{(0)}$到$x^{(r)}$的单项式路径数为奇数。因此，确定f的代数次数d只需要以下两步：

寻找到一个 $d$ 次单项式$π_{u_{(0)}}{(x^{(0)})}$，该单项式存在至少1条单项式路径，且证明$f$中不存在$>d$次的单项式$π_{u’}{(x^{(0)})}$；
对于单项式$π_{u_{(0)}}{(x^{(0)})}$，计算其单项式路径数以确认在$f$中的出现。若路径数为偶数，则重新进行这个过程；若路径数为奇数，则得到次数估计的结果，计算结束。

对单项式路径个数的求解可以使用MILP求解器，例如通过Gurobi就可以求出解的数目。Gurobi建模的方法是先列出基本操作(AND,XOR,COPY) 下的所有单项式路径，模仿对差分路径的建模（将其看成一个S盒）。或者先复合一些基本操作，之后再削减不等式个数。

另一个问题是如何高效的列出合适的单项式，对于实际的密码分析代数次数都接近上限，暴力从高汉明重量向低汉明重量枚举也不成问题。但是要谈及代数次数的上升趋势则不行。现有的方法是添加输出端单项式汉明权重为1的限制，同时最大化输入的汉明权重，在检查完当前解后若发现该单项式不存在最终的迭代函数内，就添加新的限制将该解挖去。
对于对称密码的代数次数估计中胡凯等人给出的通用解法，缺点是求解速度不能保证，对于部分场景还不能很好的运用。相对地，数值映射方法的速度更快，但是也牺牲了精度。对于实际密码的分析，还需要更多地观察其特性，以改进数值映射方法的精度或者单项式预测的速度。

3.两种代数次数估计方法的优缺点

数值映射方法

数值映射方法的优点是具有线性的时间复杂度和存储复杂度，可以对给定的cube快速得到输出比特的次数上界，且没有轮数的限制，即使对初始化轮数较高的输出比特也能够快速给出估计，但是利用数值映射对代数次数进行迭代估计时，会产生以下几个问题：
1) 不能处理两个含有相同变量的项相乘时重复变量计数的问题。当两个含有相同变量的项相乘时，会重复计算次数，导致计算结果偏高。对于这个问题，在2023年亚密会上，吴保峰等人提出了vector数值映射技术[4]，这是数值映射技术的改进。通过对某些变量的次数进行准确追踪，避免了这些变量在项相乘时被重复计算，从而一定程度上缓解了这个问题，得到了更准确的次数估计结果。
2) 不能解决多项式中的消项问题。在布尔域上，出现偶数次的单项式会抵消，但数值映射方法显然无法解决这一问题。
3) 迭代导致的估计偏差的累积。由于变量估计的过程中是通过迭代的方式计算的，因此计算误差会随着轮数的升高而越来越大。

此外，实际应用数值映射方法对Trivium-型算法进行代数次数估计时，可以发现：由于Trivium-型算法具有反馈函数二次项是相邻比特相乘的特点，数值映射对于不包含相邻变量的情形估计效果很好，对于含有相邻变量的情形估计效果较差。

单项式预测方法

对于单项式预测方法来说，由于该方法可以得到超多项式的准确代数标准型，因此可以有效解决上述数值映射方法中存在的问题。相比于数值映射方法，单项式预测方法给出的次数上界是精确的。但是可分性的传播规则和对MILP模型的求解，使得单项式预测方法存在以下问题：
1) 随着初始化轮数的增加，MILP模型中的变量和约束个数大幅增加，当初始化轮数较高时，普通PC机求解对应的MILP模型是困难的。

对于这一问题，在2021年，Stéphanie Delaune等人通过构建有向图模型来恢复超多项式[5]，通过剪枝技术实现了部分偶数单项式路径的消去，并且由于使用了有向图这一数据结构，对应的MILP模型具有更少的变量数和约束个数，加快了求解器的求解效率。他们构建的模型的恢复效率较胡凯提出的单项式预测模型提高了30～60倍，使得对这一问题有一定的改善，但是轮数较高时，对于大规模超多项式的计算依旧是困难的。

通过分析可以看出，在初始化轮数较低时，单项式预测方法相比数值映射方法，可以给出准确的次数估计结果；当初始化轮数较高时, 用单项式预测方法估计代数次数是困难的，但此时数值映射方法可以快速给出较为准确的次数估计。

上述内容仅用于非领域人员快速了解，具体实现逻辑及细节不做展示
Welcome to MinZhang’s space! If you have any questions about the following issues, you can contact me on GitHub or email- zhangmin2022@iie.ac.cn.