Security Analysis and Improvements of Hierarchical IdentityBased Authenticated Key Agreement Scheme

1.   引言

线性复杂度和周期是衡量序列伪随机性的两个重要指标。序列的线性复杂度已经在很多文献中被研究过^[1]，比如文献[1]研究了一种特殊2元序列的线性复杂度，文献[2-4]讨论了周期不同的2元广义分圆序列的线性复杂度，文献[5,6]研究了不同周期的4元广义分圆序列的线性复杂度，文献[7,8]分别讨论了2元割圆序列和广义割圆序列的线性复杂度，文献[9,10]讨论了不同周期序列的线性复杂度。本文主要研究的是新型自缩控序列的线性复杂度，自缩序列有许多密码学优点，比如构造方式简单、周期较大、线性复杂度较高、对驱动序列有强力保护，而成为密码学中一类重要的伪随机序列。文献[11]定义了自缩序列的构造方式，给出了其线性复杂度的上界值等于周期的上界值：${2^{n - 1}}$，文献[12]给出了自缩序列线性复杂度的一个上界值：${2^{n - 1}} -$$(n - 2)$，此界值较文献[11]中更精确，文献[13]提出通过模加来构造一种新的自缩序列，这虽然提高了生成序列的安全性能，但与文献[11,12]相比，其给出的周期和线性复杂度的上界并没有更精确，如何使得生成的自缩序列周期更大，线性复杂度更高且更精确，一直是研究自缩序列生成方式的一个重要问题，文献[14-16]分别在${\rm{GF}}(3)$上构造了不同的自缩序列模型，虽然得到的周期比文献[11-13]中的更大，但线性复杂度并没有突破文献[12]中的界值。而本文在${\rm{GF}}(3)$上构造的新型自缩控序列模型，不但更大地提高了生成序列的周期和线性复杂度，而且得到了生成序列线性复杂度更精确的一个上界，给出新型自缩控序列的周期上界：${3^n}$，下界：${3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor }}$；线性复杂度的上界：${3^n} - \left\lfloor {{{(n - 3)} / 4}} \right\rfloor - 1$，下界：${3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}$。

下面定义新型自缩控序列。

定义1　设${a^\infty } = ({a_0},{a_1},{a_2}, ··· )$是一$n$级$m$-序列，将序列${a^\infty }$的输出比特依次按照如式(1)方式分组

若${a_{3k}} \oplus {a_{3k + 1}} \oplus {a_{3k + 2}} = 0$，则放弃输出；若${a_{3k}} \oplus {a_{3k + 1}} \oplus {a_{3k + 2}} = 1$，则输出${a_{3k + 1}}$；若${a_{3k}} \oplus$${a_{3k + 1}} \oplus {a_{3k + 2}} = 2$，则输出${a_{3k + 1}}$, ${a_{3k + 2}}$；这样得到的输出序列为${s^\infty } = ({s_0},{s_1},{s_2}, ··· )$，称为由序列${a^\infty }$导出的新型自缩控序列(Self-Shrinking Control sequence, SSC)，以下简记为SSC(模3)-序列。

2.   SSC(模3)-序列的理论基础

引理1^[17]　设${a^\infty } = ({a_0},{a_1},{a_2}, ··· )$是${\rm{GF}}(3)$上一$n$级$m$-序列，对于$0 < k \le n$，设${\rm{GF}}(3)$上任意$k$元组$({b_1},{b_2}, ··· ,{b_k})$在${a^\infty }$的一个周期中出现的次数

证明：考虑在序列${a^\infty }$的一个周期圆中，每个非0的$n$元组($n$维向量)只出现1次，对每个非0的$k$维向量扩充为$n$维向量共有${3^{n - k}}$种扩充方式，同样对于$k$长的0向量也有${3^{n - k}}$种扩充为$n$维向量的方式，但要去掉一个全0的$n$维向量(这是因为$n$级$m$-序列无$n$长0向量)，故此时有${3^{n - k}}$$- 1$种方式。证毕

引理2^[17]　设${a^\infty } = ({a_0},{a_1},{a_2}, ··· )$是${\rm{GF}}(3)$上一$n$级$m$-序列，则有：

(1) 序列${a^\infty }$的最小周期是${3^n} - 1$；

(2) 序列${a^\infty }$是平衡的，即在序列${a^\infty }$的一个最小周期内，1, 2各出现${3^{n - 1}}$次，0出现${3^{n - 1}} - 1$次。

证明　由$n$级$m$-序列的定义知序列${a^\infty }$的最小周期为${3^n} - 1$，即(1)成立；(2)的结果由引理$1$中$k = 1$即可得。

为了得到SSC(模3)-序列线性复杂度更精确的上界值，先从序列的特征多项式入手来展开讨论。设序列${u^\infty }$是${\rm{GF}}(3)$上周期整除$3{}^n$的一个序列，则$1 - {x^{{3^n}}} = {(1 - x)^{{3^n}}}$是序列${u^\infty }$的一个特征多项式，则序列的极小多项式可表示为${(1 - x)^a}$，其中$0 \le a$$\le {3^n}$，若$0 \le L \le {3^n} - \left\lfloor {{{(n - 3)} / 4}} \right\rfloor - 1$，这里$L$表示序列的线性复杂度，则只需证${(1 - x)^{{3^n} - \left\lfloor {{{(n - 3)} / 4}} \right\rfloor - 1}}$是序列${u^\infty }$的一个特征多项式，由特征多项式的定义知：只需证明

即等价于证明

其中$v = {3^n} - \left\lfloor {{{(n - 3)} / 4}} \right\rfloor - 1$。所以也需要下面的引理。

引理3^[18]　设$T$是${\rm{GF}}({3^n})$到${\rm{GF}}(3)$上的任一线性投射，则存在$c \in {\rm{GF}}({3^n})$，使$T(x) = {\rm{Tr}}(cx)$，其中对任意$x \in {\rm{GF}}({3^n})$，满足${\rm{Tr}}(x) = \displaystyle\sum\nolimits_{i = 0}^{n - 1} {{x^{{3^i}}}}$。

证明　为了证明简便，不妨设$F = {\rm{GF}}({3^n}) K =$${\rm{GF}}(3) T(x) \triangleq {L_c}(x) {\rm{Tr}}(x) \triangleq {{\rm{Tr}}_{{F / K}}}(x) {L_c}$是线性变换(线性投射)，则$T(x) = {\rm{Tr}}(cx)$等价于${L_c}(x) =$${{\rm{Tr}}_{{F / K}}}(cx)$，本文先来证明$c \ne d$时，有${L_c} \ne {L_d}$。由于${{\rm{Tr}}_{{F / K}}}$是$F$到$K$上的线性变换，所以$\exists x \in F$使得${{\rm{Tr}}_{{F / K}}}((c - d)x) \ne 0$，因此有${L_c}(x) - {L_d}(x){\rm{ = }} {{\rm{Tr}}_{{F / K}}}$$((c - d)x) \ne 0$，从而${L_c} \ne {L_d}$。这样$\{ {L_c}:c \in F\}$共给出了${3^n}$个线性变换。但由于$F \to$$K$的任何一个线性变换都可以由该变换作用在某一组基上的像完全确定，而且这些像可以在$K$中任意取值，因此$F \to K$的线性变换共有${3^n}$个，所以$\{ {L_c}:c \in F\}$就是线性变换的全体。即$F$到$K$的任一线性变换都可以写成${L_c}(x) = {{\rm{Tr}}_{{F /K}}}(cx)$的形式，也即可以写成$T(x) = {\rm{Tr}}(cx)$的形式。证毕

定义2^[18]　设$i$是任一正整数，${w_3}(i)$表示$i$的三进制展开中非0位的个数。

定义3^[18]　设$R$表示次数小于${3^n}$的多项式环，对所有的非负整数$k$，定义：${P_3}(k) = \{ \displaystyle\sum\nolimits_{i = 0}^{{3^n} - 1} {{a_i}} {x^i}$$\in R|$当${w_3}(i) \ge k{\rm{ + }}1$时，${a_i} = 0\}$; ${P_3}^ * (k) =\{ \displaystyle\sum\nolimits_{i = 0}^{{3^n} - 1}$${{a_i}} {x^i} \in R|$当${w_3}(i) \ge k{\rm{ + }}1$时，${a_i} = 0{\rm{ }}$${a_0}$$= 0\}$。

引理4^[18]　设$T$是${\rm{GF}}({3^n})$到${\rm{GF}}({\rm{3}})$上的任意一个线性投射，则$T \in P_3^ * (1)$。

证明　由引理3知$\exists c \in {\rm{GF}}({3^n})$有$T(x) = {\rm{Tr}}(cx)$，且${\rm{Tr}}(cx) = \displaystyle\sum\nolimits_{j = 0}^{n - 1} {{c^j}{x^{{3^j}}}}$ ${a_{{3^j}}} = {c^j}$，所以只有当${\rm{Tr}}(cx)$的系数是第${3^i}$项时非0，即${w_3}(i) \ge 2$时${a_i} = 0$且${a_0} = 0$，所以 $T \in P_3^ * (1)$。证毕

引理5^[18]　设$f \in {P_3}({k_1})$$g \in {P_3}({k_2})$，则有$fg \in$${P_3}({k_1} + {k_2})$，如果$f \in P_3^ * ({k_1})$$g \in {P_3}({k_2})$，则$fg \in P_3^ *$$({k_1} + {k_2})$。

证明　$f$, $g$中$x$的次数有以下情况：当${i_1} +$${i_2} \le {3^n} - 1$时，有${x^{{i_1}}}{x^{{i_2}}} = {x^{{i_1} + {i_2}}}$；当${i_1} + {i_2} \ge {3^n}$时，有${x^{{i_1}}}{x^{{i_2}}} = {x^{{i_1} + {i_2} - {3^n} + 1}}$，其中当${i_1} + {i_2} \le {3^n} - 1$时，${w_3}({i_1} + {i_2}) \!\le\! {w_3}({i_1}) + {w_3}({i_2}) \!\le\! {k_1} + {k_2}$，当${i_1} + {i_2}$$\ge {3^n}$时，${w_3}($${i_1} + {i_2} - {3^n} + 1) \le {w_3}({i_1} + {i_2}) - 1 + 1 \le$${k_1} + {k_2}$，得$fg \in {P_3}({k_1} + {k_2})$；

当$f \in {P_3}^ * ({k_1})$时，$f(0) = 0$且$fg(0) =$$f(0)g(0)$$= 0$，所以 $fg \in P_3^*({k_1} + {k_2})$。证毕

引理6^[18]　设$\alpha \in {\rm{GF}}({3^n})$是一个本原元，$f \in P_3^ * (k)$，则存在一个元素$g \in {P_3}(k)$，对所有的$i \in \{ 0,1, ··· ,{3^n} - 2\}$，有$g({\alpha ^i}) = \displaystyle\sum\nolimits_{j = 0}^i {f({\alpha ^j})}$。

证明　若$k \le n - 1$，设$f = \displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}} {x^r} (f \in$$P_3^ * (k))$，设$g(x) \!=\! \left(\displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}\frac{{{\alpha ^r}}}{{{\alpha ^r} - 1}}} {x^r}\right) \!-\! \displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}}$$\dfrac{1}{{{\alpha ^r} - 1}} g({\alpha ^i}) = \left(\displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}} \frac{{{\alpha ^r}}}{{{\alpha ^r} - 1}}{\alpha ^{ir}}\right) - \displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}} \frac{1}{{{\alpha ^r} - 1}} =$$\displaystyle\sum\nolimits_{j = 0}^i {\left(\displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}{{({\alpha ^j})}^r}} \right)} = \displaystyle\sum\nolimits_{j = 0}^i {f({\alpha ^j})}$ 。证毕

引理7^[18]　设$f \;\in\; P_3^{\rm{*}}\;(k)$ $(k < n)$，则$\displaystyle\sum\nolimits_{x \in {\rm{GF}}({3^n})\backslash \{ 0\} } {f(x)} = 0$ 。

证明　因为$f \in P_3^{\rm{*}}(k)$，所以$f(0) = 0$，设$f = \displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}} {x^r}$(${a_0} = 0 {a_{{3^n} - 1}} = 0$) $\displaystyle\sum\nolimits_{{\alpha ^k} \in {\rm{GF}}({3^n})}$${f({\alpha ^k})}$=$\displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}}\left(\dfrac{{{\alpha ^r}}}{{{\alpha ^r} - 1}}{\alpha ^{({3^n} - 2)r}} - \dfrac{1}{{{\alpha ^r} - 1}}\right) =$$\displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}} \left(\dfrac{1}{{{\alpha ^r} - 1}} - \frac{1}{{{\alpha ^r} - 1}}\right) = 0$ 。

引理8 设${f_1}$ ${f_2} \;\in\; P_3^{\rm{*}}(k)$$(k \;<\; n)$ ，则$\displaystyle\sum\nolimits_{x \in {\rm{GF}}({3^n})\backslash \{ 0\} } {{f_1}(x){\rm{ + }}2{f_2}(x) = 0}$ 。

证明　因为${f_1}$ ${f_2} \in P_3^ * (k)$，所以${f_1}(0) = 0$ ${f_2}(0) = 0$，若要证明$\displaystyle\sum\nolimits_{x \in {\rm{GF}}({3^n})\backslash \{ 0\} } {f_1}(x) {\rm{ + }}2{f_2}(x) = 0$成立，则等价于证明$\displaystyle\sum\nolimits_{x \in {\rm{GF}}({3^n})} {f_1}(x){\rm{ + }} 2{f_2}(x) = 0$成立即可。设${f_1}(x) = \displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2} {{a_r}{x^r}}$${f_2}(x) = \displaystyle\sum\nolimits_{r = 1}^{{3^n} - 2}$${{b_r}{x^r}}$，其中${a_r} {b_r} \in {\rm{GF}}({3^n})$，由$1 \le r \le {3^n} - 2$，得$\displaystyle\sum\nolimits_{x \in {\rm{GF}}({3^n})} {{x^r}} = 0$，(见参考文献[19])，因此有

证毕

为了得到周期为${3^n}$的序列线性复杂度更精确的上界值，本文引入${\rm{GF}}({3^n})$到${\rm{GF}}(3)$上两个非0的线性映射${T_1}$ ${T_2}$具体定义如下。

定义4　设$n$是任一正整数，设${T_1}$ ${T_2}$分别是${\rm{GF}}({3^n})$$\to {\rm{GF}}(3)$上两个不同的，且非0的线性映射，设$\alpha \in {\rm{GF}}({3^n})$是$n$次本原多项式的根，则定义

由以上${T_1}$, ${T_2}$和$\alpha$的定义，通过以下方式可得到${\rm{GF}}({3^n})$中周期为${3^n}$的序列${u^\infty }$：

当$0 \le i < {3^{n - 1}}$时，定义${u_i}$为序列$1,\alpha ,{\alpha ^2}, ··· ,$${\alpha ^{{3^n} - 2}}$中使${T_1}(x) = 1$的第$i + 1$个元素；当${3^{n - 1}} \le$$i <$$2 \cdot {3^{n - 1}}$时，定义${u_i}$为序列$1,\alpha ,{\alpha ^2}, ··· ,{\alpha ^{{3^n} - 2}}$中使${T_2}(x) = {a_{n - 2}} = 2$，${u_i} = 2 \cdot {u_{i - {3^{n - 1}}}}$的${3^{n - 1}}$个元素；当$2 \cdot {3^{n - 1}} \le i <$${3^n}$时，定义${u_i}$为序列$1,\alpha ,{\alpha ^2}, ··· , {\alpha ^{{3^n} - 2}}$中使${T_2}(x) = {a_{n - 1}} = 2$的第$2 \cdot {3^{n - 1}} - i + 1$个元素。

定理1　设${u_i}$是上述序列${u^\infty }$中的元素，且${u_i} \in {\rm{GF}}({3^n})$，则

其中，$v = {3^n} - \left\lfloor {{{(n - 3)} / 4}} \right\rfloor - 1$。

证明　${u_i}$是式(7)中的被加项当且仅当$i$满足$\left(\!\! {\begin{array}{*{20}{c}} {{3^n} - \left\lfloor {({{n - 3)} /4}} \right\rfloor - 1} \\ i \end{array}} \!\!\right)\boldsymbolod 3 \ne 0$，等价于$\left\lfloor {(n - 3)} /$$4 \right\rfloor$的三进制展开中的第$k$位是2时，$i$的三进制展开中的第$k$位是0; $\left\lfloor {{{(n - 3)} / 4}} \right\rfloor$的三进制展开中的第$k$位是1时，$i$的三进制展开中的第$k$位是1或0。对于式(7)中被加项的系数：$\left( {\begin{array}{*{20}{c}} v \\ i \end{array}} \right){( - 1)^{v - i}}\boldsymbolod 3$，在${\rm{GF}}(3)$上有$\left( {\begin{array}{*{20}{c}} v \\ i \end{array}} \right){( - 1)^{v - i}}\boldsymbolod 3{\rm{ = }}1$或2，当被加项系数为1时，记此时对应的被加项为${u_{{t_i}}}$；当被加项系数为2时，记此时对应的被加项为${u_{{t_j}}}$，则要证明式(7)成立，即要证明式(8)成立

即等价于证明式(9)成立

为了证明式(9)成立，需要定义以下两个映射，设${\sigma _1}$为${\rm{GF}}({3^n}) \to {\rm{GF}}({3^n})$的一个映射，具体定义如下：当$x = u{}_{{t_i}}$为式(9)中的被加数时，有${\sigma _1}(x) = x$，此时被加项对应的系数为1；其他情形时，有${\sigma _1}(x) = 0$。同样定义${\sigma _2}$如下：当$x = u{}_{{t_j}}$为式(9)中的被加数时，${\sigma _2}(x) = x$，此时被加项对应的系数为2；其他情形时，有${\sigma _2}(x) = 0$。由${\sigma _1} {\sigma _2}$的定义可得

则由引理8知，要证明式(10)成立，只需证明${\sigma _1}(x) \in P_3^ * ({z'_1})$ ${\sigma _2}(x) \in P_3^ * ({z'_2})$ ${z'_1},{z'_2} = n - 1$，即可证明式(10)成立，那么说明式(7)也是成立的，下面来证${\sigma _1}(x) \in P_3^ * ({z'_1}) {\sigma _2}(x) \in P_3^ * ({z'_2})$，其中${z'_1},{z'_2} = n - 1$。

定义函数${\kappa _k}(x):{\rm{GF}}({3^n}) \to {\rm{GF}}({3^n})$，具体定义如下：当$x = {u_{{t_i}}}$或$x = {u_{{t_j}}}$时，且此时${t_i} {t_j}$被${3^k}$整除，有${\kappa _k}(x) = 1$；其他情形时，有${\kappa _k}(x) = 0$。为了证明方便，把${u_{{t_i}}} {u_{{t_j}}}$统一记为${u_i}$，下面用数学归纳法来证${\kappa _k}(x) \in P_3^ * ({3^k})$，当$k = 0$时，${\kappa _0}(x) = {T_1} \in P_3^*(1) {\rm{ = }}$$P_3^*({3^0})$，此时结论成立；下面假设有${\kappa _{k{\rm{ - }}1}} \in P_{\rm{3}}^ * ({3^{k - 1}})$，则由引理6知，存在$g(x) \in {P_3}({3^{k - 1}})$，使得$g({\alpha ^i}){\rm{ = }}$$\displaystyle\sum\nolimits_{j = 0}^i {{\kappa _{k - 1}}} ({\alpha ^j})$，再由${\kappa _k}(x) = 1$$\Leftrightarrow {\kappa _{k{\rm{ - }}1}}(x) = {\rm{1}}$，且$g(x) \ne 0$，则可得到${\kappa _k}(x) = {\kappa _{k - 1}}(x){g^2}(x)$，那么由引理5可知${\kappa _k}(x) \in P_3^ * ({3^k})$。

设${\sigma _k}(x) = 1 + {g^2}(x)$${\sigma _k}(x) \in P_3^{}(2 \cdot {3^{k - 1}})$，$i$的三进制展开中的第$k$位非零时，有${\sigma _k}{\rm{(}}{u_i}){\rm{ = 1}}$，其他情形时，${\sigma _k}({u_i}) = 0$，再记${h_{1k}}{\rm{ = }}{\sigma _{1k}}$，其中$1k$表示$\left\lfloor {{{(n - 3)} / 4}} \right\rfloor$的三进制展开中的第$k$位是1时的下标；${h_{2k}} = {\sigma _{2k}}$，其中$2k$表示$\left\lfloor {{{(n - 3)} / 4}} \right\rfloor$的三进制展开中的第$k$位是2时的下标，设$n - 3$的三进制表示为：$n - 3 = \displaystyle\sum\nolimits_{i = 0}^{n - 4} {{a_i}{3^i}}$，其中${a_i} \in \{ 0,1,2\}$，(注意此处$n - 3 < {3^{n - 3}}$，所以该定义有意义。)则可得到两个函数：

其中，$X$是恒同映射，${T_1} {T_{\rm{2}}}$是定义4中的映射。且有$\displaystyle\prod {{{({h_{1k}} + 1)}^2}} \displaystyle\prod {\left({h_{2k}^4} + 1\right)} \in P_3^ * ({z_1})$，其中${z_1} = n - 3$，再由引理5知，${P_1} \in P_3^ * ({z'_1})$，其中${z'_1} = {z_1} + 2 =$$n - 1$，则${P_1}(x) = x$的充要条件为${T_1}(x) = {\rm{1}} \displaystyle\prod ({h_{1k}}$$+ 1)^2 = 1 \displaystyle\prod \left({h_{2k}^4} + 1\right) = 1$，即充要条件为${T_1}(x) = 1$${h_{1k}}(x) \ne 2 {h_{2k}}(x) = 0$。由此可以看出${P_1}(x) = {\sigma _1}(x)$，且${P_1}(x) = {\sigma _1}(x) \in P_3^ * ({z'_1})$；同样对于${P_2}(x)$，有$\displaystyle\prod {{{({h_{1k}} + 1)}^2}} \displaystyle\prod {\left({h_{2k}^4} + 1\right)} \in P_3^ * ({z_2})$，其中${z_2} \!=\! n \!-\! 3$，再由引理5知${P_2} \in P_3^ * ({z'_2})$，其中${z'_2} = {z_2} + 2 =$$n - 1$，则有${P_2}(x) = x$的充要条件是${T_2}(x) = 2$$\displaystyle\prod {{{({h_{1k}} + 1)}^2} = 1} \displaystyle\prod \left({h_{2k}^4} + 1\right) = {\rm{1}}$，即${T_2}(x) = 2 {h_{1k}}$$(x) \ne 2 {h_{2k}}(x) = 0$。由此可得到${P_2}(x) = {\sigma _2}(x) {P_2}(x) =$${\sigma _2}(x) \in P_3^ * ({z'_2})$，则由引理8得$\displaystyle\sum\nolimits_{x \in {\rm{GF}}({3^n})\backslash \{ 0\} } {\sigma _1}(x) +$$2{\sigma _2}(x) = 0$，那么则有等式$\displaystyle\sum\nolimits_{i = 0}^v \left( {\begin{array}{*{20}{c}} v \\ i \end{array}} \right){{( - 1)}^{v - i}}$${\rm{mod}} 3 \cdot {u_i} = 0$成立，其中的$v$为${3^n} - \left\lfloor {{{(n - 3)} / 4}} \right\rfloor - 1$。

证毕

3.   SSC(模3)-序列的周期和线性复度

本部分给出${\rm{GF}}(3)$上SSC(模3)-序列的周期与线性复杂度的界，为叙述方便，本文用$P(\cdot)$来表示序列的最小周期，用$L(\cdot)$来表示序列的线性复杂度。

3.1   周期

设${a^\infty } = ({a_0},{a_1},{a_2}, ··· )$是${\rm{GF}}(3)$上一$n$级$m$-序列，将序列${a^\infty }$的输出比特依次分组如下：$({a_0},{a_1},$${a_2}),\;({a_3},\;{a_4},\;{a_5}), ··· ,\;({a_{{3^n} - 2}},\;{a_0},\;{a_1}),\;({a_2},\;{a_3},\;{a_4}), ···$, $({a_{{3^n} \!- 3}},{a_{{3^n} \!- 2}},{a_0}),({a_1},{a_2},{a_3}), ··· , ({a_{{3^n} - 4}},{a_{{3^n} \!- 3}},{a_{{3^n} \!- 2}})$, ${({a_0},{a_1},{a_2}), ··· }$

由此看到，把序列${a^\infty }$的3个周期段内输出的比特依次重排后，$({a_0},{a_1},{a_2})$将会重复出现，所以SSC(模3)-序列${s^\infty }$是周期的。

定理2　设${a^\infty } = ({a_0},{a_1},{a_2}, ··· )$是${\rm{GF}}(3)$上一$n$级$m$-序列，序列${s^\infty }$为${a^\infty }$导出的SSC(模3)-序列，则${s^\infty }$是平衡的且$P({s^\infty })|{3^n}$。

证明　由新型自缩控序列的定义知，只有当${a_{3k}} \oplus {a_{3k + 1}} \oplus {a_{3k + 2}} = 1$或2时，才会有输出比特作为序列${s^\infty }$的元素，由引理1知，每个3元组 (0, 0, 1)(1, 0, 0)(0, 1, 0)(2, 0, 2)(0, 2, 2)(2, 2, 0)(1, 1, 2)(1, 2, 1)(2, 1, 1)各出现${3^{n - 3}}$次，此时${a^\infty }$输出$9 \cdot {3^{n - 3}}$个比特,其中0 1 2个数均为$3 \cdot {3^{n - 3}}$；每个3元组(0, 0, 2)(0, 2, 0)(2, 0, 0)(1, 1, 0)(1, 0, 1)(0, 1, 1)(2, 2, 1)(2, 1, 2)(1, 2, 2)各出现${3^{n - 3}}$次，此时${a^\infty }$输出$9 \cdot 2 \cdot {3^{n - 3}}$个比特，其中0, 1, 2个数均为$3 \cdot$$2 \cdot {3^{n - 3}}$；

故$9 \!\cdot\! {3^{n - 3}}{\rm{ + }}9 \!\cdot\! 2 \!\cdot\! {3^{n - 3}} \!=\! {3^n}$是序列${s^\infty }$的一个周期，且0, 1, 2均出现${3^{n - 1}}$次。如果记${s^\infty }$的最小周期为$P({s}^{\infty })$，则序列${s^\infty }$是平衡的且$P({s^\infty })|{3^n}$。证毕

定理3　对于任意正整数$n \ge 3$，SSC(模3)-序列${s^\infty }$的最小周期满足$P({s}^{\infty })\ge {3}^{2\cdot \lfloor n/3\rfloor }$。

证明　设$m = 3 \cdot \left\lfloor {{n / 3}} \right\rfloor$，当$n = 3k$时，$m = n$；当$n = 3k{\rm{ + 1}}$时，$m = n - 1$；当$n = 3k{\rm{ + 2}}$时，$m =$$n - 2$。因为${a^\infty }{\rm{ = (}}{a_{\rm{0}}}{\rm{,}}{a_1}{\rm{,}}{a_2}{\rm{,}} ··· {\rm{)}}$为$n$级$m$-序列，所以$a(3t) = ({a_{3t}},{a_{3t + 1}}, ··· ,{a_{3t + m - 1}})$跑遍${\rm{GF}}{(3)^m}$上所有向量，特别跑遍了如下形式的向量：

(1) $({a_0},\,{b_0},\,{c_0}),\,({a_1},{b_1},{c_1}), \,··· ,\,({a_{{m / 3} - 1}},\,{b_{{m / 3} - 1}},$${c_{{m / 3} - 1}})$，其中${a_i} \oplus {b_i} \oplus {c_i} = 1(\boldsymbolod 3)$, $i = 0,1, ··· ,$${m / 3} - 1$。

(2) $({a'_0},\,{b'_0},\,{c'_0}),\,({a'_1},\,{b'_1},\,{c'_1}),\, ··· ,\,({a'_{{m / 3} - 1}},\,{b'_{{m / 3} - 1}},$${c'_{{m / 3} - 1}})$，其中${a'_i} \oplus {b'_i} \oplus {c'_i} = 2(\boldsymbolod 3)$, $i = 0,1, ··· ,$${m / 3} - 1$。

在第(1)种情况下，$z(t) = ({b_0},{b_1}, ··· ,{b_{{m / {\rm{3}}} - 1}})$$t = 0,1, ··· ,$跑遍${\rm{GF}}{(3)^{{m / 3}}}$上所有向量，所以此时有$P({s^\infty }) \ge {3^{{m / 3}}} = {3^{\left\lfloor {{n / 3}} \right\rfloor }}$；在第(2)种情况下，$z(t) =$$({b'_0},\,{c'_0},\,{b'_1},\,{c'_1},\, ··· ,\,{b'_{{m / 3} - 1}},\,{c'_{{m / 3} - 1}}) t = 0,1, ···$，跑遍${\rm{GF}}$${(3)^{{{2m} / 3}}}$上所有向量，所以此时有$P({s^\infty }) \ge {3^{{{2m} / 3}}} =$${3^{2\left\lfloor {{n / 3}} \right\rfloor }}$。综上有$P({s^\infty }) \ge {3^{2\left\lfloor {{n / 3}} \right\rfloor }}$。证毕

由上述定理可知${3}^{2\cdot \lfloor n/3\rfloor }\le P({s}^{\infty })\le {3}^{n}$，且SSC(模3)-序列的周期上界可以达到。

3.2   线性复杂度

设${a^\infty } = ({a_0},{a_1},{a_2}, ··· )$是${\rm{GF}}(3)$上一$n$级$m$-序列，则存在非0元$c \in {\rm{GF}}({3^n})$和本原元$\alpha \in {\rm{GF}}($${3^n})$使得${a_i} = {\rm{Tr}}(c{\alpha ^i})$，对所有的非负整数$i$成立，设序列${s^\infty }$是由序列${a^\infty }$导出的自缩控序列，记

则有

当$0 \le i < {3^{n - 1}}$${s_{im}} = {a_{3\tau (i) + 1}}$，其中$\tau (i)$是序列${a_0} \oplus {a_1} \oplus {a_2}({\rm{mod}} 3)$${a_3} \oplus {a_4} \oplus {a_5}({\rm{mod}} 3)$···中使得下面3项和，即${a_{3\tau (i)}} \oplus {a_{3\tau (i) + 1}} \oplus {a_{3\tau (i) + 2}}({\rm{mod}} 3)$为1的第$i + 1$个1，这里令$m = 0$；

当${3^{n - 1}} \le i < 2 \cdot {3^{n - 1}} {s_{im}} = {a_{3\tau (i) + 1}}$，其中$\tau (i)$是序列${a_0} \oplus {a_1} \oplus {a_2}({\rm{mod}}) 3 a_3 \oplus {a_4} \oplus {a_5}({\rm{mod}}3)$···中使得下面3项和，即${a_{3\tau (i)}} \oplus {a_{3\tau (i) + 1}} \oplus {a_{3\tau (i) + 2}} ({\rm{mod}}3)$为2的第$i - {3^{n - 1}} + 1$个2，这里令$m = 0$；

当$2 \cdot {3^{n - 1}} \le i < {3^n} {s_{im}} = {a_{3\tau (i) + 2}}$，其中$\tau (i)$是序列${a_0} \oplus {a_1} \oplus {a_2}({\rm{mod}} 3) {a_3} \oplus {a_4} \oplus {a_5}({\rm{mod}} 3) ···$中使得下面3项和，即${a_{3\tau (i)}} \oplus {a_{3\tau (i) + 1}} \oplus {a_{3\tau (i) + 2}}({\rm{mod}} 3)$为2的第$i - 2 \cdot {3^{n - 1}} + 1$个2，这里令$m = 1$。

为了更方便地来表示序列的线性复杂度，下面我们利用迹映射的相关性质和上述${u^\infty }$来重新定义。

设$T:{\rm{GF}}({3^n}) \to {\rm{GF}}(3)$, $T(x) = {\rm{Tr}}(({c^{{3^{n - 1}}}} + (c\alpha {\rm{ + }}$$c{\alpha ^2})^{{3^{n - 1}}})x)$，因为迹映射在3次方自同构下不变，所以有${\rm{Tr}}(x) = {\rm{Tr}}({x^3})$，则有

设${T_1}^{'}:{\rm{GF}}({3^n}) \to {\rm{GF}}(3)$, ${T_1}^{'}(x) = {\rm{Tr}}({(c\alpha )^{{3^{n - 1}}}}x)$，则有

设${T_2}^{'}:{\rm{GF}}({3^n}) \!\to\!\! {\rm{GF}}(3)$, ${T_2}^{'}(x) \!=\! {\rm{Tr}}({(c{\alpha ^{m + 1}})^{{3^{n - 1}}}} x)$，则有

其中，$m = 0$或1。

以下为了叙述方便，当$m = 0$时，记${T'_2}$为${T'_{20}}$；当$m = 1$时，记${T'_2}$为${T'_{21}}$；重新记

对所有的非负整数$i$有：当${\rm{0}} \!\le\! i \!<\! {3^{n - 1}}$时，有${s_{im}} =$${T'_1}({u_{im}})$；当${3^{n - 1}} \le i < 2 \cdot {3^{n - 1}}$时，有${s_{im}} = {T'_{20}}( {u_{im}})$；当${\rm{2}} \cdot {3^{n - 1}} \le i < {3^n}$时，${s_{im}} = {T'_{2{\rm{1}}}}({u_{im}})$。若我们重新记${s^\infty } = ({s_0},{s_1},{s_2}, ··· ,{s_{3k}},{s_{3k + 1}},{s_{3k + 2}}, ··· )$和${u^\infty } =$$({u_0},{u_1},{u_2}, ··· ,{u_{3k}},{u_{3k + 1}},{u_{3k + 2}}, ··· )$分别与上述所记的${s^\infty }$和${u^\infty }$一一对应，则此时有：当${\rm{0}} \le i < {3^{n - 1}}$时，有${s_i} = {T'_1}({u_i})$；当${3^{n - 1}} \le i < 2 \cdot {3^{n - 1}}$时，有${s_i} = {T'_{20}}({u_i})$；当${\rm{2}} \cdot {3^{n - 1}} \le i < {3^n}$时，有${s_i} = {T'_{2{\rm{1}}}}({u_i})$。

由前述定理1和上边的记法可得下面的式子是成立的，即有

由以上的讨论可以得到以下定理4。

定理4　新型自缩控序列(SSC(模3)-序列)${s^\infty }$的线性复杂度上界为

定理5　新型自缩控序列(SSC(模3)-序列)${s^\infty }$的线性复杂度下界为$L({s^\infty }) > {3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}$。

证明　设$g(x)$为序列${s^\infty }$的极小多项式，利用序列的极小多项式整除特征多项式，来证$L({s^\infty }) >$${3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}$，若有$L({s^\infty }) \!\le\! {3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}$，那么由$1 \!-\! {x^{{3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}}}$$= {(1 - x)^{{3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}}}$，且$g(x)|{(1 - x)^{{3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}}}$，得$P({s^\infty }) \le$${3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}$，与已知的$P({s^\infty }) \ge {3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor }}$相矛盾，所以$L({s^\infty }) > {3^{2 \cdot \left\lfloor {{n / 3}} \right\rfloor - 1}}$。证毕

本文从上边讨论的结果中可以看出：与文献[12-16]中的序列相比，本文中的新型自缩控序列(SSC(模3)-序列)${s^\infty }$不但周期有更大的提高，而且线性复杂度也有较大的提高，且有以下几点优势。

(1) 文献[13]中改进的自收缩序列模型是由${a_{3k}} \oplus$${a_{3k + 1}}$的值来决定该括号内输出比特的个数，但是该序列模型当${a_{3k}} \oplus {a_{3k + 1}} = 1$时，只输出1个比特，而在本文的模型上，不仅增加了元素相加的项，而且还分类输出，当${a_{3k}} \oplus {a_{3k + 1}} \oplus {a_{3k + 2}} = 1$时，输出1个比特；当${a_{3k}} \oplus {a_{3k + 1}} \oplus {a_{3k + 2}} = 2$时，输出2个比特，因而得到的序列周期提高很多；

(2) 文献[15]中${\rm{GF}}(3)$上多位自收缩序列的模型，只是由${a_{3k}}$的值来决定所在分组是否有输出，但${a_{3k}}$的所在分组中至多输出1个比特，且当${a_{3k}} = 0$时，没有输出；而本文中的模型是根据${a_{3k}} \oplus {a_{3k + 1}} \oplus$${a_{3k + 2}}$的取值来决定该括号内的输出比特个数，更好地弥补${a_{3k}} = 0$时${a^\infty }$收缩过多的不足，所得到的自缩控序列整体上的平衡性更优；

(3) 本文中的自缩控序列(SSC(模3)-序列)的周期整除${3^n}$，这里是对文献[12,18]的研究方法进行改进，并在取最小周期为${3^n}$的情况下，通过探究，得到了自缩控序列(SSC(模3)-序列)线性复杂度更精确的上界值：${3^n} - \left\lfloor {{{(n - 3)} / 4}} \right\rfloor - 1$。

(4) 通过此种方式得到的自缩控序列的信息利用率更高，达到${{\rm{1}} / {\rm{3}}}$，与之前了解过的自缩序列模型相对比，信息利用率明显提高，使原来的数据得到了更充分的利用。

4.   结束语

伪随机序列在通信加密、雷达信号设计和编码技术等很多领域中有着广泛的应用。在这些应用中，通常要求序列具有大的周期和高的线性复杂度。衡量伪随机性的指标主要有周期、平衡性、线性复杂度和自相关性等。本文所设计的密码序列，主要是从周期、线性复杂度这两个安全指标来分析所构造序列的安全性，本文基于$m$-序列构造的新型自缩控序列，从整体上研究了该序列的周期及线性复杂度，分析结果发现新型自缩控序列具有更大的周期和较高的线性复杂度。虽然输出不规则，但是破坏了序列的代数结构，由此输出的序列隐蔽性较好且防攻击能力较强，从安全性指标来看，新型自缩控序列具有较好的密码学性质，是一种较好的伪随机序列。接下来可以进一步研究新型自缩控序列的游程分布、自相关性等密码学特性，完善理论结果，为自缩控序列在各领域的应用提供更好的理论基础。