Z₄上一类四元广义分圆序列的线性复杂度

Linear Complexity of a Class of Quaternary Sequence Generated by Generalized Cyclotomic Class over Z₄

摘要: 序列的线性复杂度与序列的安全性息息相关。本文利用Galois理论，研究了一类在有限域F₄上具有较高线性复杂度的四元序列，得到了其在Galois环Z₄上的线性复杂度的确切值。结果显示，这类序列在Galois环Z₄上也具有较高的线性复杂度，可以较好地抵抗Reeds-Sloane算法的攻击。

Abstract: The linear complexity of a sequence is closely related to its cryptographic security. In this paper, we employ Galois theory to investigate a class of quaternary sequence over the finite field F₄ with high linear complexity, and determine the exact value of its linear complexity over the Galois ring Z₄. The results demonstrate that such sequence maintain relatively high linear complexity in the Galois ring Z₄, thereby exhibiting strong resistance against attacks by the Reeds-Sloane algorithm.

1. 引言

在密码学中，序列的线性复杂度是指能够生成该序列的最短线性反馈移位寄存器(LFSR, Linear Feedback Shift Register)的阶数[1]，是刻画序列伪随机性的重要指标，同时反映了序列抵抗特定类型攻击的能力。具有高线性复杂度的四元序列在密码学中有着广泛应用。文献[2]指出，在流密码体制中，具有高线性复杂度的密钥流序列可以分别在有限域及Galois环上有效抵抗B-M算法、Reeds-Sloane算法的已知明文攻击。文献[3]指出，在信息隐藏系统中，采用具有高线性复杂度的序列作为密钥或掩码，可以确保嵌入的信息不易被察觉或提取。因此，研究四元序列的线性复杂度可以帮助我们构造适用于不同场景的安全序列，在密码学中具有应用意义。

近些年，学者们利用分圆类和广义分圆类构造了许多四元序列。2008年，文献[4]利用分圆类构造了一类四元序列，2011年，文献[5]计算出了这类序列在有限域F₄上线性复杂度的确切值，结果表明此类序列在有限域F₄上具有较大线性复杂度，可以有效地抵抗B-M算法的攻击。

但是只研究序列在有限域上的线性复杂度是远远不够的。研究表明，由于有限域和Galois环是两种不同的代数结构，常会出现同一序列在其二者上具有不同的线性复杂度的情况。在Galois环上具有较低线性复杂度的四元序列容易受到Reeds-Sloane算法的攻击：Reeds-Sloane算法可利用部分序列片段，通过伴随式计算、建立线性方程组、求解多项式的根等一系列代数步骤，快速恢复整条序列。因此，讨论文献[4]中所构造的四元序列在Z₄上的线性复杂度是十分必要的。但是由于环结构中零因子的存在，使得这一问题成为了序列密码研究中的难点。

本文以文献[4]中所构造的四元序列为研究对象，由于在Galois环上无法根据多项式的整除关系判断多项式的根，所以区别于域上的研究方法，我们根据文献[6]中的引理2 (本文的引理4)，利用扩环的单位元判断了环上多项式的整除关系，借助Galois理论和广义分圆类的性质，在Z₄上计算出了其线性复杂度的确切值，结果表明，这类序列在Z₄上具有较高的线性复杂度，可以较好的抵抗Reeds-Sloane算法的攻击。

若无特殊说明，本文中的多项式及运算都是定义在Z₄[x]上的。

2 预备知识

2.1. 序列构造

设p为奇素数，g为奇数，并且g是一个模p和模2p的公共本原元。定义

$D_0^p=\left\{g^{2k}\left(\mathrm{mod}p\right):k=0,1,\cdots ,\frac{\phi \left(p\right)}{2}-1\right\},$

$D_1^p=g\cdot D_0^p=\left\{ga\left(\mathrm{mod}p\right):a\in D_0^p\right\},$

$D_0^{2p}=\left\{g^{2k}\left(\mathrm{mod}2p\right):k=0,1,\cdots ,\frac{\phi \left(p\right)}{2}-1\right\},$

$D_1^{2p}=g\cdot D_0^{2p}=\left\{ga\left(\mathrm{mod}2p\right):a\in D_0^{2p}\right\},$

其中$\phi (\cdot )$ 为欧拉函数，由此得到$Z_{2p}$ 的一个划分：

$Z_{2p}=D_0^{2p}\cup D_1^{2p}\cup 2D_0^p\cup 2D_1^p\cup \left\{0,p\right\}$ .

文献[4]中，Kim等人构造了一类周期为2p的四元序列S，构造方法如下：

$s_i=\{\begin{array}{l}0,i=0,\hfill \\ 2,i=p,\hfill \\ 0,i\in D_0^{2p},\hfill \\ 1,i\in D_1^{2p},\hfill \\ 2,i\in 2D_0^p,\hfill \\ 3,i\in 2D_1^p.\hfill \end{array}$

2.2. 四元序列在Z₄上的线性复杂度

线性复杂度(LC, Linear Complexity)是指能够生成给定序列的最短线性反馈移位寄存器(LFSR, Linear Feedback Shift Register)的长度。当在环而不是域上考虑线性复杂度时，由于环可能包含零因子(即两个非零元素相乘可以得到零)，这会导致问题变得复杂。环上序列的线性复杂度定义如下：

设S是一条周期为N的四元序列，$S=\left(s_0,s_1,\cdots ,s_{N-1}\right)$ ，如果S在环Z₄上满足如下线性递归关系：

$s_{j+L}+c_1{s}_{j+L-1}+\cdots +c_L{s}_j=0,j\ge 0,$

$\left(c_1,c_2,\cdots ,c_L\in Z_4\right)$ ，则称使上式成立的L的最小值为序列S在Z₄上的线性复杂度。多项式 $C\left(x\right)=1+c_{1}x+\cdots +c_L{x}^L$ 称为序列S的联结多项式。

引理1 [3] 设周期为N的四元序列S的序列多项式为：$s\left(x\right)=s_0+s_{1}x+\cdots +s_{N-1}{x}^{N-1}$ ，则$C\left(x\right)$ 为$s\left(x\right)$ 的联结多项式当且仅当$C\left(x\right)s\left(x\right)\equiv 0\left(\mathrm{mod}{x}^N-1\right)$ ，其中$C\left(x\right)\in Z_4\left[x\right]$ 且满足$C\left(0\right)=1$ 。

定义1 [7] 设$S=\left(s_0,s_1,\cdots ,s_{N-1}\right)$ 是周期为N的四元序列，S在Z₄上的线性复杂度(记为($L{C}_R\left(S\right)$ )定义为：$L{C}_R\left(S\right)=\text{min}\left\{\text{deg}\left(C\left(x\right)\right):C\left(x\right)\in Z_4\left[x\right]�S的��多�式\right\}$ 。

文献[3]强调，在流密码中，通常认为，当序列的线性复杂度LC不小于周期的一半时，可以有效抵抗Reeds-Sloane算法的攻击。

例：如果序列u为：

$u=\left(132120023030\right)$

则序列多项式为：$u\left(x\right)=1+3x+2x^2+x^3+2x^4+2x^7+3x^8+3x^{10}$ ，其最低次数的联结多项式为：

$c\left(x\right)=1+2x+2x^2+x^3+x^4+x^5+3x^6+3x^7+x^8$ ，因此称序列u的线性复杂度为8，并且由于$8>\frac{12}{2}$ ，故称序列u属于高线性复杂度的范畴。

3. 序列S的线性复杂度

这一部分我们将利用Galois理论以及分圆类的性质计算序列S在环上的线性复杂度，在证明本文的主要结果之前，我们需要以下引理。

引理2 [4] 设符号与第一部分相同，如果$a\in D_i^{2p}$ ，则$a\cdot D_j^{2p}=D_{i+j\left(\mathrm{mod}2\right)}^{2p}$ ，$a\cdot 2D_j^p=2D_{i+j\left(\mathrm{mod}2\right)}^p$ ；如果$a\in 2D_i^p$ ，则$a\cdot D_j^{2p}=2D_{i+j\left(\mathrm{mod}2\right)}^p$ ，$a\cdot 2D_j^p=2D_{i+j\left(\mathrm{mod}2\right)}^p$ 。

引理3 [5] $2\in D_0^p$ 当且仅当$p\equiv \pm 1\left(\mathrm{mod}8\right)$ ，并且$2\in D_1^p$ 当且仅当$p\equiv \pm 3\left(\mathrm{mod}8\right)$ 。

下面介绍一些本文需要用到的Galois环理论的相关内容。

设p是一个奇数，r表示2模p的阶数，$GR\left(4,4^r\right)$ 代表的是阶为$4^r$ 且特征为4的Galois扩环。在GR$\left(4,4^r\right)$ 内，所有的单位构成一个群，将此群记作$G{R}^{*}\left(4,4^r\right)$ ，显然$G{R}^{*}\left(4,4^r\right)$ 中存在一个循环子群，其阶为$2^r-1$ 。因为$p|2^r-1$ ，设$\xi \in G{R}^{*}\left(4,4^r\right)$ 阶为p，则$\eta =3\xi \in G{R}^{*}\left(4,4^r\right)$ 的阶为2p。

根据定义1，我们能够通过分析序列多项式$s\left(x\right)$ 的根(即$s\left({\eta }^j\right)$ ，$j=0,1,\cdots ,2p-1$ 的值)来探讨其因式分解的形式，进而计算序列S的线性复杂度。但是文献[8]强调，在环中，零因子的存在使得多项式的因式分解变得尤为复杂。例如，虽然1和3是$2x-2\in Z_4\left[x\right]$ 的根，但是$2x-2$ 并不能被$\left(x-1\right)\left(x-3\right)$ 整除。因此，在环$Z_4\left[x\right]$ 中，多项式根的个数可能会高于它的次数。下面的引理说明了环中多项式的根与其因式分解之间的关系。

引理4 [7] 设$p\left(x\right)\in Z_4\left[x\right]$ 为一非常数多项式，若$\gamma \in GR\left(4,4^r\right)$ 是$p\left(x\right)$ 的一个根，则 $p\left(x\right)=\left(x-\gamma \right)Q_1\left(x\right)$ ，其中$Q_1\left(x\right)\in G{R}^{*}\left(4,4^r\right)\left[x\right]$ 。若$\eta \in GR\left(4,4^r\right)$ 是$p\left(x\right)$ 的另一个根，且 $\eta -\gamma \in G{R}^{*}\left(4,4^r\right)$ ，则$p\left(x\right)=\left(x-\gamma \right)\left(x-\eta \right)Q_2\left(x\right)$ ，其中$Q_1\left(x\right)=\left(x-\eta \right)Q_2\left(x\right)$ 。

引理5 若$a\in Z_p^{*}$ ，则

${\displaystyle {\sum }_{i\in D_0^P}{\xi }^{ai}}+{\displaystyle {\sum }_{i\in D_1^P}{\xi }^{ai}}=3$ 。

证明 因为$\xi \in G{R}^{*}\left(4,4^r\right)$ 阶为p，即${\xi }^p=1$ ，则有：

${\displaystyle {\sum }_{i\in Z_p}{\xi }^{ai}}=\frac{1-{\xi }^{ap}}{1-\xi }=\frac{1-{\left({\xi }^p\right)}^a}{1-\xi }=0$ ，

即${\displaystyle {\sum }_{i\in D_0^P}{\xi }^{ai}}+{\displaystyle {\sum }_{i\in D_1^P}{\xi }^{ai}}=3$ 。 证毕。

令$Z_{2p}=\left\{0,1,2,\cdots ,2p-1\right\}$ ，$E=\left\{0,2,\cdots ,2p-2\right\}$ ，$O=\left\{1,3,\cdots ,2p-1\right\}$ ，显然有$Z_{2p}=E\cup O$ 。

引理6 ${\displaystyle {\sum }_{i\in E}{\xi }^i}\in G{R}^{*}\left(4,4^r\right)\left[x\right]\ne 0$ 。

证明 由引理5可知：${\displaystyle {\sum }_{i\in E}{\eta }^i}+{\displaystyle {\sum }_{i\in O}{\eta }^i}=3$ ，而${\displaystyle {\sum }_{i\in O}{\eta }^i}=\eta \cdot {\displaystyle {\sum }_{i\in E}{\eta }^i}$ ，即

${\displaystyle {\sum }_{i\in E}{\eta }^i}+\eta \cdot {\displaystyle {\sum }_{i\in E}{\eta }^i}={\displaystyle {\sum }_{i\in E}{\eta }^i}\left(1+\eta \right)=3$ ，故 ${\displaystyle {\sum }_{i\in E}{\xi }^i}\ne 0$ 。 证毕。

引理7 当$p\equiv \pm 1\left(\mathrm{mod}8\right)$ 时，

${\displaystyle {\sum }_{i\in D_0^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_0^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_0^P}{\eta }^{i+1}}+{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}$ ,

当$p\equiv \pm 3\left(\mathrm{mod}8\right)$ 时，

${\displaystyle {\sum }_{i\in D_0^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_0^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_0^P}{\eta }^i}-{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}$ ,

当$p\equiv \pm 1\left(\mathrm{mod}8\right)$ 时，

${\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{ai}}+{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}$ ,

当$p\equiv \pm 3\left(\mathrm{mod}8\right)$ 时，

${\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}$ .

证明 我们只给出当$p\equiv \pm 3\left(\mathrm{mod}8\right)$ 时，${\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}$ 的证明，其他情况同理。而要证明${\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}$ ，只需证明$D_1^{2P}\cup 2D_0^P=D_1^P\cup \left\{D_1^P+p\right\}$ 即可。

当$0<g^{2k+1}\left(\mathrm{mod}2p\right)<p$ 时，有$g^{2k+1}\left(\mathrm{mod}2p\right)=g^{2k+1}\left(\mathrm{mod}p\right)$ ；当$p<g^{2k+1}\left(\mathrm{mod}2p\right)<2p$ 时，有$0<g^{2k+1}\left(\mathrm{mod}2p\right)-p<p$ ，即$g^{2k+1}\left(\mathrm{mod}2p\right)=g^{2k+1}\left(\mathrm{mod}p\right)+p$ 。因此可得：$D_1^{2P}\in D_1^P\cup \left\{D_1^P+p\right\}$ 。

当$0<2\cdot g^{2k}\left(\mathrm{mod}2p\right)<p$ 时，由于$2\in D_1^P$ ，所以 $2\cdot g^{2k}\left(\mathrm{mod}2p\right)=2\cdot g^{2k}\left(\mathrm{mod}p\right)=g^{2m+1}\cdot g^{2k}=g^{2n+1}\left(\mathrm{mod}p\right)$ ；当$p<2\cdot g^{2k}\left(\mathrm{mod}2p\right)<2p$ 时， $2g^{2k}\left(\mathrm{mod}2p\right)=2g^{2k}\left(\mathrm{mod}p\right)+p=g^{2n+1}\left(\mathrm{mod}p\right)+p$ ，因此可得：$2D_0^P\in D_1^P\cup \left\{D_1^P+p\right\}$ 。

综上可得：$D_1^{2P}\cup 2D_0^P\in D_1^P\cup \left\{D_1^P+p\right\}$ ，又易证集合$D_1^{2P}\cup 2D_0^P$ 与$D_1^P\cup \left\{D_1^P+p\right\}$ 中元素个数相同，且集合$D_1^{2P}\cup 2D_0^P$ 中元素互异，因此$D_1^{2P}\cup 2D_0^P=D_1^P\cup \left\{D_1^P+p\right\}$ 。 证毕。

下面是本文的主要研究结论。

定理1 四元序列S的线性复杂度为：

$L{C}_R\left(S\right)=\{\begin{array}{l}p+1,p\equiv 1\left(\mathrm{mod}8\right),\hfill \\ p,p\equiv -1\left(\mathrm{mod}8\right),\hfill \\ 2p-1,p\equiv 3\left(\mathrm{mod}8\right),\hfill \\ 2p,p\equiv -3\left(\mathrm{mod}8\right).\hfill \end{array}$

证明 S的生成多项式为：

$s\left(x\right)=2x^p+{\displaystyle {\sum }_{i\in D_1^{2P}}{x}^i}+2{\displaystyle {\sum }_{i\in 2D_0^P}{x}^i}+3{\displaystyle {\sum }_{i\in 2D_1^P}{x}^i}$ ，

那么：

$s\left({\eta }^j\right)=2{\eta }^{jp}+{\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^{ij}}+2{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^{ij}}+3{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^{ij}}$ ，

当$j=0$ 时，$s\left({\eta }^j\right)=3p+1$ ，

$3p+1=\{\begin{array}{l}2,p\equiv 3\left(\mathrm{mod}8\right),p\equiv -1\left(\mathrm{mod}8\right),\\ 0,p\equiv -3\left(\mathrm{mod}8\right),p\equiv 1\left(\mathrm{mod}8\right).\end{array}$

当$j=p$ 时，$s\left({\eta }^j\right)=2p-4\ne 0$ 。

当$j\in D_0^{2P}$ 时，$s\left({\eta }^j\right)={\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}+{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}$ 。根据引理7，$p\equiv \pm 1\left(\mathrm{mod}8\right)$ 时，有：

${\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}$ ，故：

$s\left({\eta }^j\right)={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}=0$ 。

$p\equiv \pm 3\left(\mathrm{mod}8\right)$ 时，有：

${\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}$ ，故：

$s\left({\eta }^j\right)={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}+{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}=3-2{\displaystyle {\sum }_{i\in D_0^P}{\xi }^i}\ne 0$ ，因为${\left(3-2{\displaystyle {\sum }_{i\in D_0^P}{\xi }^i}\right)}^2\ne 0$ 。

当$j\in D_1^{2P}$ 时，$s\left({\eta }^j\right)={\displaystyle {\sum }_{i\in D_0^{2P}}{\eta }^i}+{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}$ 。根据引理7，$p\equiv \pm 1\left(\mathrm{mod}8\right)$ 时，有：

${\displaystyle {\sum }_{i\in D_0^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_0^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_0^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}$ ，故：

$s\left({\eta }^j\right)={\displaystyle {\sum }_{i\in D_0^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_0^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}+{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}=0$ 。

$p\equiv \pm 3\left(\mathrm{mod}8\right)$ 时，有：

${\displaystyle {\sum }_{i\in D_1^{2P}}{\eta }^i}={\displaystyle {\sum }_{i\in D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_1^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}$ ，故：

$s\left({\eta }^j\right)={\displaystyle {\sum }_{i\in D_0^P}{\eta }^i}+{\displaystyle {\sum }_{i\in D_0^P}{\eta }^{i+1}}-{\displaystyle {\sum }_{i\in 2D_1^P}{\eta }^i}+{\displaystyle {\sum }_{i\in 2D_0^P}{\eta }^i}=3-2{\displaystyle {\sum }_{i\in D_1^P}{\xi }^i}\ne 0$ ，因为${\left(3-2{\displaystyle {\sum }_{i\in D_1^P}{\xi }^i}\right)}^2=1\ne 0$ 。当$j\in 2D_0^P\cup 2D_1^P$ 时，$s\left({\eta }^j\right)=3{\displaystyle {\sum }_{i\in E}{\xi }^i}$ ，根据引理6可知$s\left({\eta }^j\right)\ne 0$ 。 证毕。

4. 例子

如果$p=7$ ，$g=3$ ，此时

$D_0^7=\left\{1,4,5\right\},D_1^7=3\cdot D_0^7=\left\{2,3,6\right\},$

$D_0^{14}=\left\{1,3,12\right\},D_1^{14}=3\cdot D_0^{14}=\left\{4,6,9\right\},$

则根据文献[1]中的构造方法所构造的四元序列为：

$S=\left\{0,3,1,2,3,1,2,0,2,1,1,3,0,2\right\}$ .

且该序列的线性复杂度为$L{C}_R\left(S\right)=7$ 。此结果与本文定理1相符，并且属于高线性复杂度的范畴，利用Reeds-Sloane算法不易还原整条序列。

5. 结论

本文探讨了一类基于广义分圆类构造的四元序列。我们通过对Z₄及其扩环上的零因子问题的讨论，利用分圆类的特性精确计算了文献[1]中四元序列在环Z₄上线性复杂度的值，结果表明，此类序列在Z₄上具有较高的线性复杂度，可以有效抵抗Reeds-Sloane算法攻击。本文的探究方法具有一定的推广性，可以用来计算其他多元分圆序列在Galois环上的线性复杂度。

NOTES

^*通讯作者。