非线性反馈移位寄存器的互馈联结

The Mutual Feedback Connection of Nonlinear Feedback Shift Registers

摘要: 本文给出了定义在有限域${\mathbb{F}}_2$ 上的任意多个非线性反馈移位寄存器的互馈联结的特征函数表达式。

Abstract: This paper presents the characteristic function expressions for the mutual feedback connections of an arbitrary number of nonlinear feedback shift registers defined over the finite field ${\mathbb{F}}_2$ .

1. 引言

移位寄存器是生成伪随机序列的重要模型，它在通信、编码、密码等领域有着广泛的应用。特别是在序列密码的设计中，人们主要使用移位寄存器作为序列源发生器，因此对移位寄存器的研究一直是序列密码设计与分析的重要内容。移位寄存器分为线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)和非线性反馈移位寄存器(Nonlinear Feedback Shift Register, NFSR)。如图1所示，每个$x_i$ 表示一个寄存器的状态，均取值于二元域，$\left(x_0,x_1,\cdots ,x_{n-1}\right)$ 称为该移位寄存器的状态向量，n元布尔函数$f^{\prime }$ 称为该移位寄存器的反馈函数。若反馈函数$f^{\prime }$ 是线性布尔函数，则该移位寄存器称为n级LFSR；若$f^{\prime }$ 是非线性布尔函数，则为n级NFSR。

Figure 1. n-Shift register

图1. n级移位寄存器

上世纪中后期，密码设计者对LFSR所产生序列的密码学性质进行了深入与系统的研究，选用了具备极大周期的m-序列作为序列密码的序列源，并对其进行非线性改造，从而得到非线性序列，以此应用于序列密码。但在本世纪初，针对基于LFSR设计的序列密码算法，人们提出了有效的相关攻击和代数攻击的思想与技术，这对基于LFSR设计的序列密码算法造成了极大的威胁。由此，以非线性序列作为序列密码的序列源成为了序列密码设计者的共识。由于NFSR可产生的de Bruijn序列具有最大周期、元素分布的平衡性等良好的密码学性质，又是非线性的生成方式，因此NFSR被认为是取代LFSR的一类理想的序列源发生器，逐渐在面向硬件实现的序列密码的设计中占据重要地位。

NFSR的研究历史可以追溯到19世纪末数学家们研究的递归序列问题。但由于非线性问题的困难性以及没有涉及密码应用，关于NFSR密码学性质的研究工作并不多。Golomb在[1]中系统整理了定义在二元域上的LFSR和NFSR的基本概念和上世纪获得的主要结果，奠定了此后关于LFSR和NFSR的研究基础。在上世纪，人们主要关注最大周期的de Bruijn序列的构造及其线性复杂度。然而，当前人们找到的de Bruijn序列的构造方式，与实际的序列密码应用偏离较大，这是至今没有一个成功的基于de Bruijn序列的序列密码算法的原因。近二十年，特别是2004年欧洲启动的eSTREAM序列密码项目最终推荐的基于NFSR设计的Grain、Trivium和MICKEY [2]-[4]三个序列密码算法，突破了传统的基于LFSR的设计思想，均使用了定义在二元域上的NFSR作为序列源发生器，算法结构简洁，同时兼顾安全性、实现速率和灵活性。以上三个序列密码算法以及由此抽象出的三类模型，即Grain模型、Trivium模型和MICKEY模型有力促进了围绕NFSR的实际应用的研究，其研究问题更加丰富与深刻，如线性子簇[5]-[8]，串联结构[9]-[11]，Galois NFSR与Fibonacci NFSR的等价性[12]等问题。

在上述的三类序列密码模型的设计中，Trivium型序列密码采用了NFSR的互馈联结模型。它是由若干多个NFSR相互驱动组成，其第i个NFSR的输出作为第i + 1个NFSR的输入，最后一个NFSR的输出作为第1个NFSR的输入。本文考察如下形式的NFSR的互馈联结。下面以两个移位寄存器的互馈联结为例，如图2所示。它是由两个移位寄存器组合起来，右侧的第一个$n_1$ 级NFSR的输出是左侧第二个$n_2$ 级NFSR的输入，参与了第二个NFSR下一时刻的输出。记上述两个NFSR的反馈函数分别为${f^{\prime }}_1$ 和${f^{\prime }}_2$ ，其特征函数为$f_1$ 和$f_2$ 。我们将这种组合方式称为移位寄存器的互馈联结，记为$\left(f_2\mapsto f_1\right)$ 。移位寄存器的互馈联结的详细描述可参见[13]。

Figure 2. The mutual feedback connection of two NFSRs

图2. 两个NFSR的互馈联结

易见，若图2中${f^{\prime }}_1$ 和${f^{\prime }}_2$ 均为非线性布尔函数，它们的互馈联结必与一个$n_1+n_2$ 级的NFSR等价，其反馈函数为非线性布尔函数，且由${f^{\prime }}_1$ 和${f^{\prime }}_2$ 唯一确定。事实上，任意有限多个NFSR的互馈联结本质上与一个级数更高的NFSR等价，因此确定多个NFSR的互馈联结的特征函数表达式是重要的基本问题。现设定义在二元域上的任意k个NFSR(i)，设$n_i$ 级非线性反馈移位寄存器NFSR(i)的反馈函数为${f^{\prime }}_i$ ，其特征函数为$f_i$ ，其中$1\le i\le k$ 。以$\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 表示NFSR(i)$\left(1\le i\le k\right)$ 的互馈联结。本文给出了互馈联结$\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 的特征函数的清晰表达式。

本文第二章介绍下文所需要的预备知识，第三章给出主要结果及其证明，第四章给出示例。

2. 预备知识

本文所研究的NFSR均定义在二元域${\mathbb{F}}_2=\left\{0,1\right\}$ 上。

二元域上具有两个代数运算，加法与乘法，定义如下[14]：

$0+0=0,0+1=1,1+1=0.$

$0\cdot 0=0,0\cdot 1=0,1\cdot 1=1.$

NFSR的模型如图1所示，其中$f^{\prime }\left(x_0,x_1,\cdots ,x_{n-1}\right)$ 是n元布尔函数，称为该NFSR的反馈函数，并称

$f\left(x_0,x_1,\cdots ,x_n\right)=f^{\prime }\left(x_0,x_1,\cdots ,x_{n-1}\right)+x_n$

为该NFSR的特征函数。

记NFSR(f)为以f为特征函数的NFSR，其输出序列$\left(a_0,a_1,a_2,\cdots \right)$ 称为NFSR序列，它满足递归关系

$a_{n+k}=f^{\prime }\left(a_k,a_{k+1},\cdots ,a_{n+k-1}\right),k=0,1,2,\cdots$

该NFSR的输出序列的全体记为$G\left(f\right)$ 。

为了描述NFSR的互馈联结的特征函数，下面引入布尔函数的星积运算。

定义1 [15] 设n和m是两个正整数，$f\left(x_0,x_1,\cdots ,x_n\right)$ 和$g\left(x_0,x_1,\cdots ,x_m\right)$ 分别是$n+1$ 元布尔函数和$m+1$ 元布尔函数，则$f\left(x_0,x_1,\cdots ,x_n\right)$ 和$g\left(x_0,x_1,\cdots ,x_m\right)$ 的星积“$\ast$ ”定义为

$f\ast g=f\left(g\left(x_0,x_1,\cdots ,x_m\right),g\left(x_1,x_2,\cdots ,x_{1+m}\right),\cdots ,g\left(x_n,x_{n+1},\cdots ,x_{n+m}\right)\right)$ .

若g是h的一个星积因子是指g和h满足$h=f\ast g$ 。特别地，g是h的一个线性星积因子是指g既满足上述等式，又是一个线性布尔函数。

g是h的非平凡星积因子是指g满足上述等式，又$g\ne x_0$ 且$g\ne h$ 。

星积有如下性质：

1) $f\ast g$ 不一定等于$g\ast f$ ，即星积不具有交换性。但是，对于线性布尔函数而言，星积具有交换性，即对任意的线性布尔函数$l_1$ 和$l_2$ ，满足

$l_1\ast l_2=l_2\ast l_1$ .

2) 星积具有左分配律，即对任意的布尔函数$f_1$ ，$f_2$ 和g都满足

$\left(f_1+f_2\right)\ast g=\left(f_1\ast g\right)+\left(f_2\ast g\right)$ ,

$\left(f_1\cdot f_2\right)\ast g=\left(f_1\ast g\right)\cdot \left(f_2\ast g\right)$ .

3) 星积运算有结合律，即对任意的n元布尔函数$f_1$ ，$f_2$ 和$f_3$ 都有

$\left(f_1\ast f_2\right)\ast f_3=f_1\ast \left(f_2\ast f_3\right)$ .

4) 对任意的布尔函数g，有

$1\ast g=1$ .

3. 主要结果

在本节中，我们研究定义在二元域上的任意k个NFSR的互馈联结，如图3所示。其中$n_i$ 级非线性反馈移位移位寄存器NFSR(i)的反馈函数为${f^{\prime }}_i$ ，记NFSR(i)的特征函数为$f_i$ ，其中$1\le i\le k$ 。现将该NFSR的互馈联结记为$\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 。我们有如下结论。

Figure 3. The mutual feedback connection of k NFSRs

图3. k个NFSR的互馈联结

定理1 对于图3所示的k个NFSR的互馈联结，设每个反馈函数${f^{\prime }}_i$ 形如

${f^{\prime }}_i\left(x_0^{\left(i\right)},x_1^{\left(i\right)},\cdots ,x_{n_i-1}^{\left(i\right)}\right)=x_0^{\left(i\right)}+{f^{″}}_i\left(x_1^{\left(i\right)},\cdots ,x_{n_i-1}^{\left(i\right)}\right)$ ,

则互馈联结$\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 的输出序列的全体为

$G\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)=G\left(x_{n_1+n_2+\cdots +n_k}+{f^{\prime }}_2\ast \left({f^{\prime }}_3\ast \left({f^{\prime }}_4\ast \cdots \ast \left({f^{\prime }}_k\ast {f^{\prime }}_1\right)\right)\cdots \right)\right)$ ,

其中$x_i$ 表示该互馈联结的第i个输出。

证明 首先证明集合$G\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 包含于集合

$G\left(x_{n_1+n_2+\cdots +n_k}+{f^{\prime }}_2\ast \left({f^{\prime }}_3\ast \left({f^{\prime }}_4\ast \cdots \ast \left({f^{\prime }}_k\ast {f^{\prime }}_1\right)\right)\cdots \right)\right)$ .

记NFSR(i)的特征函数为

$f_i\left(x_0^{\left(i\right)},\cdots ,x_{n_i-1}^{\left(i\right)},x_{n_i}^{\left(i\right)}\right)={f^{\prime }}_i\left(x_0^{\left(i\right)},\cdots ,x_{n_i-1}^{\left(i\right)}\right)+x_{n_i}^{\left(i\right)}$ ,

设NFSR(i)的初始状态为$\left(a_0^{\left(i\right)},a_1^{\left(i\right)},\cdots ,a_{n_i-1}^{\left(i\right)}\right)$ ，$1\le i\le k$ 。

记${f^{\prime }}_1$ 的输出序列为$\underset{\_}{a^{\left(k\right)}}=\left(a_{n_k}^{\left(k\right)},a_{n_k+1}^{\left(k\right)},\cdots \right)$ ，${f^{\prime }}_i$ 的输出序列为$\underset{\_}{a^{\left(i-1\right)}}=\left(a_{n_{i-1}}^{\left(i-1\right)},a_{n_{i-1}+1}^{\left(i-1\right)},\cdots \right)$ ，$i=2,3,\cdots ,k$ 。

由NFSR(i)的反馈函数所定义的递归关系，可得如下等式

$\begin{array}{c}\{\begin{array}{l}{a}_{n_1+i}^{\left(1\right)}={f^{\prime }}_2\left(a_i^{\left(2\right)},a_{i+1}^{\left(2\right)},\cdots ,a_{i+n_2-1}^{\left(2\right)}\right)\\ a_{n_2+i}^{\left(2\right)}={f^{\prime }}_3\left(a_i^{\left(3\right)},a_{i+1}^{\left(3\right)},\cdots ,a_{i+n_3-1}^{\left(3\right)}\right)\\ ⋮\\ a_{n_{k-1}+i}^{\left(k-1\right)}={f^{\prime }}_k\left(a_i^{\left(k\right)},a_{i+1}^{\left(k\right)},\cdots ,a_{i+n_k-1}^{\left(k\right)}\right)\\ a_{n_k+i}^{\left(k\right)}={f^{\prime }}_1\left(a_i^{\left(1\right)},a_{i+1}^{\left(1\right)},\cdots ,a_{i+n_1-1}^{\left(1\right)}\right)\end{array}\end{array}$

成立。

对于任意的$i\ge 0$ ，使用上述的等式，互馈联结$\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 在$n_1+n_2+\cdots +n_k+i$ 时刻的输出为

$\begin{array}{l}{a}_{n_1+n_2+\cdots +n_k+i}^{\left(1\right)}={f^{\prime }}_2\left(a_{n_2+\cdots +n_k+i}^{\left(2\right)},a_{n_2+\cdots +n_k+i+1}^{\left(2\right)},\cdots ,a_{n_2+\cdots +n_k+i+n_2-1}^{\left(2\right)}\right)\\ ={f^{\prime }}_2\left({f^{\prime }}_3\left(a_{n_3+\cdots +n_k+i}^{\left(3\right)},\cdots ,a_{n_3+\cdots +n_k+i+n_3-1}^{\left(3\right)}\right),\cdots ,{f^{\prime }}_3\left(a_{n_3+\cdots +n_k+i+n_2-1}^{\left(3\right)},\cdots ,a_{n_3+\cdots +n_k+i+n_2+n_3-2}^{\left(3\right)}\right)\right)\\ =\cdots \\ ={f^{\prime }}_2\left({f^{\prime }}_3\left({f^{\prime }}_4\left(\cdots \left({f^{\prime }}_{k-1}\left({f^{\prime }}_k\left({f^{\prime }}_1\left(a_i^{\left(1\right)},a_{i+1}^{\left(1\right)},\cdots ,a_{i+n_1-1}^{\left(1\right)}\right),\cdots ,{f^{\prime }}_1\left(a_{i+n_k+n_{k-1}+\cdots +n_2-\left(k-1\right)}^{\left(1\right)},\cdots ,a_{i+n_k+n_{k-1}+\cdots +n_1-k}^{\left(1\right)}\right)\cdots \right)\right)\right)\right)\right)\right)\end{array}$

根据有限域${\mathbb{F}}_2$ 的运算规则，上述等式改写为

$\begin{array}{l}{a}_{n_1+n_2+\cdots +n_k+i}^{\left(1\right)}\\ +{f^{\prime }}_2\left({f^{\prime }}_3\left({f^{\prime }}_4\left(\cdots \left({f^{\prime }}_{k-1}\left({f^{\prime }}_k\left({f^{\prime }}_1\left(a_i^{\left(1\right)},a_{i+1}^{\left(1\right)},\cdots ,a_{i+n_1-1}^{\left(1\right)}\right),\cdots ,{f^{\prime }}_1\left(a_{i+n_k+n_{k-1}+\cdots +n_2-\left(k-1\right)}^{\left(1\right)},\cdots ,a_{i+n_k+n_{k-1}+\cdots +n_1-k}^{\left(1\right)}\right)\right)\cdots \right)\right)\right)\right)\right)\\ =0\end{array}$

令

$\begin{array}{l}F\left(x_0,x_1,\cdots ,x_{n_1+n_2+\cdots +n_k}\right)\\ =x_{n_1+n_2+\cdots +n_k}\\ +{f^{\prime }}_2\left({f^{\prime }}_3\left({f^{\prime }}_4\left(\cdots \left({f^{\prime }}_{k-1}\left({f^{\prime }}_k\left({f^{\prime }}_1\left(a_i^{\left(1\right)},a_{i+1}^{\left(1\right)},\cdots ,a_{i+n_1-1}^{\left(1\right)}\right),\cdots ,{f^{\prime }}_1\left(a_{i+n_k+n_{k-1}+\cdots +n_2-\left(k-1\right)}^{\left(1\right)},\cdots ,a_{i+n_k+n_{k-1}+\cdots +n_1-k}^{\left(1\right)}\right)\right)\cdots \right)\right)\right)\right)\right)\\ =x_{n_1+n_2+\cdots +n_k}+{f^{\prime }}_2*\left({f^{\prime }}_3*\left({f^{\prime }}_4*\cdots *\left({f^{\prime }}_k*{f^{\prime }}_1\right)\right)\cdots \right)\end{array}$

则有

$F\left(x_0,x_1,\cdots ,x_{n_1+n_2+\cdots +n_k}\right)\left(\underset{\_}{a^{\left(1\right)}}\right)=0$ ,

即互馈联结$\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 的输出序列$\underset{\_}{a^{\left(1\right)}}$ 满足由布尔函数$F\left(x_0,x_1,\cdots ,x_{n_1+n_2+\cdots +n_k}\right)$ 所确定的递归关系，从而有

$G\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)\subseteq G\left(F\left(x_0,x_1,\cdots ,x_{n_1+n_2+\cdots +n_k}\right)\right)$ .

下面证明$G\left(F\left(x_0,x_1,\cdots ,x_{n_1+n_2+\cdots +n_k}\right)\right)\subseteq G\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 。

$\forall \underset{\_}{a}\in G\left(F\right)$ ，则有

$x_{n_1+n_2+\cdots +n_k}+{f^{\prime }}_2\ast \left({f^{\prime }}_3\ast \left({f^{\prime }}_4\ast \cdots \ast \left({f^{\prime }}_k\ast {f^{\prime }}_1\right)\right)\cdots \right)\left(\underset{\_}{a}\right)=0$

成立。对于任意的$i\ge 0$ ，

$\begin{array}{l}{a}_{n_1+n_2+\cdots +n_k+i}\\ ={f^{\prime }}_2\left({f^{\prime }}_3\left({f^{\prime }}_4\left(\cdots \left({f^{\prime }}_{k-1}\left({f^{\prime }}_k\left({f^{\prime }}_1\left(a_i^{\left(1\right)},a_{i+1}^{\left(1\right)},\cdots ,a_{i+n_1-1}^{\left(1\right)}\right),\cdots ,{f^{\prime }}_1\left(a_{i+n_k+n_{k-1}+\cdots +n_2-\left(k-1\right)}^{\left(1\right)},\cdots ,a_{i+n_k+n_{k-1}+\cdots +n_1-k}^{\left(1\right)}\right)\right)\cdots \right)\right)\right)\right)\right)\end{array}$

现由给定序列$\underset{\_}{a}\in G\left(F\right)$ ，求出NFSR(i)的初始状态，$i=2,3,\cdots ,k$ 。由于每个NFSR(i)的反馈函数形如

${f^{\prime }}_i\left(x_0^{\left(i\right)},x_1^{\left(i\right)},\cdots ,x_{n_i-1}^{\left(i\right)}\right)=x_0^{\left(i\right)}+{f^{″}}_i\left(x_1^{\left(i\right)},\cdots ,x_{n_i-1}^{\left(i\right)}\right)$ ,

则

其中$a_{n_i}^{\left(i\right)},\cdots ,a_{n_i+n_i+n_{i-1}+\cdots +n_2-i}^{\left(i\right)}$ 都由$\underset{\_}{a}$ 的相应位置唯一确定。

依次考察$a_t$ ，$n_1+n_2+\cdots +n_{i-1}\le t\le n_1+n_2+\cdots +n_i-1$ ，则由上述等式可唯一确定$a_r^{\left(i\right)}$ 的值，其中$0\le r\le n_i-1$ ，故$\underset{\_}{a^{\left(i\right)}}$ 的值都由$\underset{\_}{a^{\left(1\right)}}$ 的相应位置的值确定，从而可确定所有寄存器的初始状态。

此时，$\underset{\_}{a^{\left(1\right)}}$ 可由$\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 生成，故有

$G\left(F\right)\subseteq G\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ .

综上，$G\left(F\right)=G\left(f_k\mapsto f_{k-1}\mapsto \cdots \mapsto f_2\mapsto f_1\right)$ 。证毕。

注记 上述定理利用布尔函数的星积运算，给出了任意有限多个NFSR的互馈联结的特征函数的清晰表达式，同时也得到了其反馈函数的表达式，这为研究多个NFSR的互馈联结以及特殊形式的NFSR的互馈联结形式的分解提供了基本依据。

4. 示例

本节给出两个NFSR互馈联结的例子，以此说明定理1的结论。

设定义在二元域上的6级互馈联结如图4所示，其中右侧的NFSR的反馈函数为${f^{\prime }}_1\left(x_0,x_1,x_2\right)=x_0+x_1{x}_2$ ，左侧的NFSR的反馈函数为${f^{\prime }}_2\left(x_3,x_4,x_5\right)=x_3+x_4{x}_5$ 。

设在t时刻，该互馈联结的状态向量为$\left(t_0,t_1,t_2,t_3,t_4,t_5\right)$ ，记$t+1$ 时刻的状态向量为$\left({t^{\prime }}_0,{t^{\prime }}_1,{t^{\prime }}_2,{t^{\prime }}_3,{t^{\prime }}_4,{t^{\prime }}_5\right)$ ，则上述状态满足如下关系：

${t^{\prime }}_0=t_1,{t^{\prime }}_1=t_2,{t^{\prime }}_2=t_3+t_4{t}_5,{t^{\prime }}_3=t_4,{t^{\prime }}_4=t_5,{t^{\prime }}_5=t_0+t_1{t}_2.$

Figure 4. The mutual feedback connection between 3-NFSR and 3-NFSR

图4. 3级NFSR与3级NFSR的互馈联结

设该互馈联结的初态为(100000)，则其状态转移过程为：

$\left(\text{100001}\right)\to \left(\text{000011}\right)\to \left(\text{001110}\right)\to \left(\text{011100}\right)\to \left(\text{111001}\right)\to \left(\text{110010}\right)\to \left(\text{100101}\right)$

$\left(\text{001011}\right)\to \left(\text{011110}\right)\to \left(\text{111101}\right)\to \left(\text{111010}\right)\to \left(\text{110100}\right)\to \left(\text{101001}\right)\to \left(\text{010011}\right)$

$\to \left(\text{101110}\right)\to \left(\text{011101}\right)\to \left(\text{111011}\right)\to \left(\text{111110}\right)\to \left(\text{111100}\right)\to \left(\text{111000}\right)$

$\to \left(\text{110000}\right)\to \left(\text{100001}\right)$ .

该互馈联结生成的序列为：1000001100101101001101100001…，且是以26为周期的周期序列。

易知${f^{\prime }}_1$ ，${f^{\prime }}_2$ 满足定理1的条件，根据有限域${\mathbb{F}}_2$ 中的运算，则该互馈联结的特征函数为

$x_{6+i}+{f^{\prime }}_2\ast {f^{\prime }}_1=x_{6+i}+x_i+x_{2+i}{x}_{3+i}+x_{1+i}{x}_{3+i}{x}_{4+i}+x_{2+i}{x}_{3+i}{x}_{4+i}$ ,

其中$x_i$ 为第i个时刻的输出。

5. 结论

本文考察了定义在有限域${\mathbb{F}}_2$ 上任意有限多个非线性反馈移位寄存器互馈联结，基于布尔函数的星积运算给出了该互馈联结的特征函数的清晰表达式，为研究多个NFSR的互馈联结以及特殊形式的NFSR的互馈联结形式的分解提供了基本依据。