随机数具有广泛的应用，例如被广泛用于统计采样、蒙特卡罗模拟、数值分析、密码学、博弈论、彩票系统、摇号系统等。密码学中，随机数可用于密钥生成、数字签名、认证协议、零知识协议等。在很多私钥密码算法和公钥密码算法、数字签名和认证协议中，都要用随机数作为密钥。因此，在很多密码应用中随机数的安全决定着系统的安全。

目前，已有很多度量随机序列安全性的指标特征，例如，周期较大、线性复杂度较大、理想的游程分布、较好的随机性和不可预测性等。在随机性方面，一般认为随机序列应具有较好的统计性质，通常有两个评价标准^[1]： 分布一致和独立。分布一致指序列中的随机数的分布应该是均匀的，即出现的频率相等。独立指序列中任何数不能由其他数推导出。不可预测性包括前向不可预测性和后向不可预测性。前向不可预测指由先前的序列不能推导出后续的序列。后向不可预测指由已知序列不能推出前面的序列。

线性同余发生器(LCG)是使用很广的一类随机数发生器^[2]。但是，这类随机数发生器有一些弱点。当LCG的乘数、增量和模未知时，文^[3]指出，只需知道其产生的一些序列，就可预测后续序列。当LCG产生的随机数的一些低比特不可用时，文^[4]指出可以推出其产生的序列。文^[5]基于洗牌法思想设计了一种新的LCG。为克服LCG的缺陷，得到安全性更好的随机数，可组合多个LCG产生随机数，此时称为组合线性同余发生器CLCG。文^[6]和文^[7]分别独立地提出两类CLCG。文^[8]证明了这两类CLCG产生序列的相关性质^{[8, 9]}。文^[9]提出一个CLCG，它由4个LCG组合而成。文^[10]提出另外一种CLCG，并研究了其周期性和统计性质。

由于CLCG的高效性，近年来，CLCG广泛用于产生彩票系统和摇号系统中的随机数。在这些应用中，序列的不可预测非常重要，必须要满足不可预测，而CLCG在设计时并没有考虑此问题。据作者所知，目前未见有公开文献对文^[6]和文^[7]提出的两类CLCG的不可预测性进行分析。为此，本文对文^[6]和文^[7]提出的一类CLCG的安全性进行了分析，研究了其不可预测性，给出了前向预测和后向预测这类CLCG的输出序列的数据复杂度和时间复杂度，并以重要文献^{[6, 7, 8]} 中提出的5个CLCG为例，给出了前向预测与后向预测的分析结果与建议。结果显示，这类CLCG在一些推荐参数下会遭受前向预测和后向预测攻击，不适宜作密码用途。本文提出的方法具有普适性，而并不仅针对于特定的CLCG算法。对于新的CLCG算法，若符合本文的分析模型，仍可能遭受此类攻击。

1 线性同余发生器

线性同余发生器利用同余来产生随机数，其产生随机数过程通常为：

$\left\{ \begin{align} & {{x}_{n}}\equiv \left( a{{x}_{n-1}}+c \right)\left( \bmod m \right), \\ & {{r}_{n}}={{x}_{n}}/m. \\ \end{align} \right.$

其中： 第1式表示模同余，m为模，a为乘数，c为增量，x₀为初始值或称种子，r_n(n≥1)为产生的随机数序列。m为正整数，a、 c和x₀是区间［0,m)上的整数。易见，x_n是区间［0,m)上的整数，因此，上述LCG产生的序列r_n∈［0,1)。设r_n是以十进制表示的小数，该LCG的最终输出为r_n小数部分的某段数字。

一般地，当c=0时称为乘线性同余发生器(multiplicative LCG，MLCG)，当c≠0时称为混合线性同余发生器。

欲使LCG产生的随机序列在性能和安全性方面较好，参数m、 a、 c和x₀的选择很重要。显然，x₀≠0。其他参数的选择应遵循以下原则^{[1, 2]}。

1) m的选择。

m一般都很大，这是由于LCG产生序列的周期不超过m。一个常见的评价标准是m与给定计算机的字长w接近相等。考虑到效率和安全性，通常有3种选择m的方法：

a) m=w±1；

b) m=w；

c) m是小于w的最大素数。

例如，对于32位机，一种常见取法是取m为略小于2³¹的素数。

2) a的选择。

显然，a应该不小于2。一般要求a与m互素。LCG产生的序列达到最大周期m的充要条件为：

a) gcd(c,m)，gcd表示最大公因子；

b) m的每个素因子整除a-1；

c) 若m是4的倍数，a-1也是4的倍数。

据此，当m是不同素数的乘积时，仅当a=1时LCG才能产生最大周期为m的序列，但a不小于2。因此当m是不同素数的乘积时，LCG产生的序列周期不能达到最大m。当c=0时，MLCG产生的序列也不能达到最大周期m。

MLCG产生的序列最大可能的周期为λ(m)，这里λ(m)表示模m的最大可能的阶，即本原元的阶。当gcd(x₀,m)=1且a是模m的本原元时，MLCG产生的序列达到最大周期λ(m)。MLCG产生最大周期序列有如下3种情况。

a) m是素数，当a是模m的本原元时，MLCG可得到最大周期为m-1的序列；

b) m=2^f(f≥4)且x₀是奇数，当a≡3或 5(mod8)时，MLCG可得到最大周期为2^f-2的序列；

c) m=10^f(f≥5)且x₀不是2或5的倍数，MLCG可得到最大周期为5×10^f-2的序列，当 a mod 200 等于以下32个值之一时： 3,11,13,19,21,27,29,37,53,59,61,67,69,77,83,91,109,117,123,131,133,139,141,147,163,171,173,179,181,187,189,197。

由LCG的递归表达式易得^[2]：

xn+k≡(akxn+(ak-1)c/(a-1))(mod m),

则对于MLCG有： x_n+k≡a^kx_n(mod m)。

2 组合线性同余发生器的不可预测性分析 2.1 组合线性同余发生器

考虑一类常见的CLCG^{[6, 7, 8, 9]}。设有J(J≥2)个MLCG组成的CLCG，每个MLCG的模m_j是不同的素数，且每个MLCG产生的序列具有最大周期m_j-1，即乘数a_j是模m_j的本原元。设s_j,i表示第j个MLCG在第i步的状态，即每个MLCG基于以下递归式：

sj,i≡ajsj,i-1(mod mj).

设δ₁,…，δ_J是任意非零整数且对每个j，gcd(δ₁δ₂…δ_J,m₁)=1(为方便，文^[7]中取 δ_j=(-1)^j-1)。定义一类CLCG如下：

$\left\{ \begin{align} & {{z}_{i}}\equiv \sum\limits_{j=1}^{J}{{{\delta }_{i}}}{{s}_{j,i}}\left( \bmod {{m}_{1}} \right), \\ & {{u}_{i}}={{z}_{i}}/{{m}_{1}}. \\ \end{align} \right.$

(1)

已证明，该CLCG产生的输出序列u_i的周期为

lcm(m1-1,…，mJ-1)，

这里lcm表示最小公倍数。

J的取值应该较小。当给定计算机为32位机时，文^[7] 推荐J取2。

2.2 组合线性同余发生器的不可预测性分析

本节研究上节给出的组合线性同余发生器的前向不可预测性和后向不可预测性，为此，先给出两个引理。

引理1 设矩阵

$A=\left[ \begin{matrix} {{\delta }_{1}} & {{\delta }_{2}} & \cdots & {{\delta }_{J}} \\ {{\delta }_{1}}{{a}_{1}} & {{\delta }_{2}}{{a}_{2}} & \cdots & {{\delta }_{J}}{{a}_{J}} \\ \vdots & \vdots & \ddots & \vdots \\ {{\delta }_{1}}a_{_{1}}^{J-1} & {{\delta }_{2}}a_{_{2}}^{J-1} & \cdots & {{\delta }_{J}}a_{_{J}}^{J-1} \\ \end{matrix} \right]$

则 A 的行列式

$\left| A \right|={{\delta }_{1}}{{\delta }_{2}}\cdots {{\delta }_{J}}\prod\limits_{1\le k<i\le J}{\left( {{a}_{i}}-{{a}_{k}} \right)}$

证明 下面给出作者的一个证法。设

$B=\left[ \begin{matrix} 1 & 1 & \cdots & 1 \\ {{a}_{1}} & {{a}_{2}} & \cdots & {{a}_{J}} \\ \vdots & \vdots & \ddots & \vdots \\ a_{_{1}}^{J-1} & a_{_{2}}^{J-1} & \cdots & a_{_{J}}^{J-1} \\ \end{matrix} \right],$

$C=\left[ \begin{array}{*{35}{l}} {{\delta }_{1}} & 0 & 0 & \cdots & 0 \\ 0 & {{\delta }_{2}} & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & {{\delta }_{J}} \\ \end{array} \right],$

则 A= BC 。 A 的行列式 |A|= |B| · |C| 。 B 是Vandermonde矩阵，由文^[11]，其行列式

$\left| B \right|=\prod\limits_{1\le k<i\le J}{\left( {{a}_{i}}-{{a}_{k}} \right)}.$

C 是对角矩阵，其行列式为 |C|=δ₁δ₂…δ_J。因此，A 的行列式 $\left| A \right|={{\delta }_{1}}{{\delta }_{2}}\cdots {{\delta }_{J}}\prod\limits_{1\le k<i\le J}{\left( {{a}_{i}}-{{a}_{k}} \right)}$。■

引理2 设线性同余方程组为

D x≡ b (mod m)，

其中，

$D=\left[ \begin{matrix} {{a}_{11}} & {{a}_{12}} & \cdots & {{a}_{1n}} \\ {{a}_{21}} & {{a}_{22}} & \cdots & {{a}_{2n}} \\ \vdots & \vdots & \ddots & \vdots \\ {{a}_{n1}} & {{a}_{n2}} & \cdots & {{a}_{nn}} \\ \end{matrix} \right],x=\left[ \begin{matrix} {{x}_{1}} \\ {{x}_{2}} \\ \vdots \\ {{x}_{n}} \\ \end{matrix} \right],b=\left[ \begin{matrix} {{b}_{1}} \\ {{b}_{2}} \\ \vdots \\ {{b}_{n}} \\ \end{matrix} \right],$

a_ij、 b_i均为［0,m)上的整数。设 |D| ≠0，记 D _j表示将 D 的第j列用 b 来代替所得的矩阵，即

${{D}_{j}}=\left[ \begin{array}{*{35}{l}} {{a}_{11}} & \cdots & {{a}_{1,j-1}} & {{b}_{1}} & {{a}_{1,j+1}} & \cdots & {{a}_{1n}} \\ {{a}_{21}} & \cdots & {{a}_{2,j-1}} & {{b}_{2}} & {{a}_{2,j+1}} & \cdots & {{a}_{2n}} \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ {{a}_{n1}} & \cdots & {{a}_{n,j-1}} & {{b}_{n}} & {{a}_{n,j+1}} & \cdots & {{a}_{nn}} \\ \end{array} \right],$

j=1,2,…n。则有：

1) 若gcd( | D | ,m)=1，则方程组存在唯一一组解(对模m来说)

xj≡ | D | -1 | Dj | (mod m)，

这里 | D | ^-1表示 | D | 模m的逆；

2) 若gcd( | D | ,m)=d，且d| | D_j | ，则方程组有解，解数为dⁿ； 若d | D_j |，方程组无解。

证明 下面给出作者的一个证法。根据Cramer法则有

| Dj | xj≡ | Dj |(mod m),j=1,2,…,n.

(2)

a) 若gcd( | D | ,m)=1，则 |D |模m的逆| D | ^-1存在，此时式(2)存在唯一一个解

xj≡| D | -1 | Dj |(mod m)，

原方程组的唯一解为

$x\equiv \left[ \begin{matrix} {{\left| D \right|}^{-1}}\left| {{D}_{1}} \right| \\ {{\left| D \right|}^{-1}}\left| {{D}_{2}} \right| \\ \vdots \\ {{\left| D \right|}^{-1}}\left| {{D}_{n}} \right| \\ \end{matrix} \right]\left( \bmod m \right).$

b) 若gcd( | D | ,m)=d，且d| | D _j| ，若x_0,j是式(2)的一个解，则式(2)有d个解，d个解为

${{x}_{j}}\equiv {{x}_{0,j}}+\frac{m}{d}t\left( \bmod m \right),t=0,\cdots ,d-1.$

设 |D|=dd′，m=dm′，gcd(m′,d′)=1,|D _j |=dd_j。则式(2)等价于

d′xj≡dj(modm′).

(3)

由于gcd(m′,d′)=1，由1)中结论知，式(3)存在唯一一个解

${{x}_{0,j}}\equiv {{\left( \frac{\left| D \right|}{d} \right)}^{-1}}\cdot \frac{\left| {{D}_{j}} \right|}{d}\left( \bmod \frac{m}{d} \right).$

因此式(2)的d个解为

$\begin{align} & {{x}_{j}}\equiv {{\left( \frac{\left| D \right|}{d} \right)}^{-1}}\cdot \frac{\left| {{D}_{j}} \right|}{d}+\frac{m}{d}t\left( \bmod m \right), \\ & t=0,\cdots ,d-1. \\ \end{align}$

因此，原方程组共有dⁿ个解。

若d $\left| {{D}_{j}} \right|$，式(2)无解，则原方程组无解。■

符号约定： 在下文中，$\left\lfloor n \right\rfloor $表示不超过n(n∈$\mathbb{R}$)的最大整数，记$\underset{1\le j\le J}{\mathop{\max {{m}_{j}}}}\,=M$。

下面讨论由方程组(1)定义的CLCG的前向不可预测性，给出如下定理。

定理1 设有2.1节定义的CLCG，记号同2.1节。则已知J个连续的输出序列u_i，u_i+1，…，u_i+J-1中每个序列的连续x位(0≤x≤1+$\left\lfloor \lg {{m}_{1}} \right\rfloor $)，能在时间复杂度为

$O\left( \text{l}{{\text{b}}^{2}}M\cdot {{\left( {{a}_{2}}{{a}_{3}}\cdots {{a}_{J}} \right)}^{\frac{\left( J-1 \right)\cdot J}{2}}}\cdot {{10}^{J\cdot \left( 1+\left\lfloor \lg {{m}_{1}} \right\rfloor -x \right)}} \right)$

下预测后续输出序列。

证明 由递归关系式得

sj,i+k≡ajksj,i(mod mj),k≥0,j=1,…,J.

已知J个连续的输出序列u_i，u_i+1，…，u_i+J-1，可得由J个线性同余方程组成的关于未知数s₁,s_2,i,…,s_J,i的线性同余方程组

$\left\{ \begin{align} & \sum\limits_{j=1}^{J}{{{\delta }_{j}}}{{s}_{j,i}}\equiv {{m}_{1}}{{u}_{1}}\left( \bmod {{m}_{1}} \right), \\ & \sum\limits_{j=1}^{J}{{{\delta }_{j}}\left( a_{j}^{t}{{s}_{j,i}}-{{k}_{j,i+t}}{{m}_{j}} \right)\equiv {{m}_{1}}{{u}_{i+t}}\left( \bmod {{m}_{1}} \right).} \\ \end{align} \right.$

其中： t=1,…,J-1，k_j,i+t≥0，j=1,…,J。将上述方程组进一步化简得：

$\left\{ \begin{align} & \sum\limits_{j=1}^{J}{{{\delta }_{j}}}{{s}_{j,i}}\equiv {{m}_{1}}{{u}_{1}}\left( \bmod {{m}_{1}} \right), \\ & \sum\limits_{j=1}^{J}{{{\delta }_{j}}\left( a_{j}^{t}{{s}_{j,i}}-\sum\limits_{j=2}^{J}{{{\delta }_{j}}}{{k}_{j,i+t}}{{m}_{j}} \right)\equiv {{m}_{1}}{{u}_{i+t}}\left( \bmod {{m}_{1}} \right).} \\ \end{align} \right.$

(4)

其中： k_j,i+t≥0，j=2,…,J，m₁u_i,…,m₁u_i+J-1是属于(0,m₁)之间的整数，s_j,i、 a_j^ts_j,i-k_j,i+tm_j是属于(0,m_j)之间的整数。

由a_j^ts_j,i-k_j,i+tm_j∈{1,…,m_j-1}推出

$\frac{a_{j}^{t}}{{{m}_{j}}}-1<{{k}_{j,i+t}}< \frac{a_{j}^{t}\left( {{m}_{j}}-1 \right)}{{{m}_{j}}}.$

猜测

kj,i+t(j=2,…,J，t=1,…,J-1)，

对每个k_j,i+t，最多有略小于a_j^t个整数，最多共猜测约有

$\prod\limits_{j=2}^{J}{\prod\limits_{t=1}^{J-1}{a_{j}^{t}=}}{{\left( {{a}_{2}}{{a}_{3}}\cdots {{a}_{J}} \right)}^{\frac{\left( J-1 \right)\cdot J}{2}}}$

个整数。

方程组(4)的系数矩阵为

$A=\left[ \begin{matrix} {{\delta }_{1}} & {{\delta }_{2}} & \cdots & {{\delta }_{J}} \\ {{\delta }_{1}}{{a}_{1}} & {{\delta }_{2}}{{a}_{2}} & \cdots & {{\delta }_{J}}{{a}_{J}} \\ \vdots & \vdots & \ddots & \vdots \\ {{\delta }_{1}}a_{_{1}}^{J-1} & {{\delta }_{2}}a_{_{2}}^{J-1} & \cdots & {{\delta }_{J}}a_{_{J}}^{J-1} \\ \end{matrix} \right],$

满足 | A | ≠0(否则，A 的行向量之间存在线性关系，因此u_i,u_i+1，…,u_i+J-1之间存在仿射关系，独立性较差，则此CLCG的输出将无法通过常规的随机性检测)。由引理1知，

$\left| A \right|={{\delta }_{1}}{{\delta }_{2}}\cdots {{\delta }_{J}}\prod\limits_{1\le k<i\le J}{\left( {{a}_{i}}-{{a}_{k}} \right)}$

因此，gcd( | A |,m₁)=1。由引理2知，对每个固定k_j,i+t，方程组(4)关于未知数s_1,i,s_2,i,…s_J,i有唯一一组解。因此，

${{z}_{i+J}}\equiv \sum\limits_{j=1}^{J}{{{\delta }_{j}}\cdot \left( a_{_{j}}^{J}{{s}_{j,i}}\left( \bmod {{m}_{j}} \right) \right)}\left( \bmod {{m}_{1}} \right)$

可得出。故u_i+J及后续序列都可得出，即输出序列u_i+J及后续序列可预测出。解方程组的时间复杂度为O(lb²m₁)，计算z_i+J的时间复杂度为O(lb²M)。因此时间复杂度为

$O\left( \text{l}{{\text{b}}^{2}}M\cdot {{\left( {{a}_{2}}{{a}_{3}}\cdots {{a}_{J}} \right)}^{\frac{\left( J-1 \right)\cdot J}{2}}} \right)$

由1/p发生器的性质^[12]： 知道p，任意给定z_i/p的连续1+$\left\lfloor \lg p \right\rfloor $位(表示为十进制)，就能推出前面和后面的位。因此，只需知道u_i的任意连续 1+$\left\lfloor \lg {{m}_{1}} \right\rfloor $位，就能知道u_i。 在已知u_i的任意连续x位条件下，猜测前面或后续连续1+$\left\lfloor \lg {{m}_{1}} \right\rfloor $-x位，时间复杂度为10^{1+$\left\lfloor \lg {{m}_{1}} \right\rfloor $-x}。因此，在已知连续输出序列u_i，u_i+1，…,u_i+J-1任意连续x位条件下，能够预测后续输出序列。预测输出序列的总时间复杂度为

$O\left( \text{l}{{\text{b}}^{2}}M\cdot {{\left( {{a}_{2}}{{a}_{3}}\cdots {{a}_{J}} \right)}^{\frac{\left( J-1 \right)\cdot J}{2}}}\cdot {{10}^{J\cdot \left( 1+\left\lfloor \lg {{m}_{1}} \right\rfloor -x \right)}} \right)$

方程组(1)定义的CLCG的后向不可预测性，可类似分析，有以下定理。

定理2 设有2.1节定义的CLCG，记号同2.1节。已知J个连续输出序列u_i+1，…，u_i+J中每个序列的连续x位，能在时间复杂度为

$O\left( \text{l}{{\text{b}}^{2}}M\cdot {{\left( {{a}_{2}}{{a}_{3}}\cdots {{a}_{J}} \right)}^{\frac{\left( J-1 \right)\cdot J}{2}}}\cdot {{10}^{J\cdot \left( 1+\left\lfloor \lg {{m}_{1}} \right\rfloor -x \right)}} \right)$

下预测u_i+1前面的输出序列。

证明 已知输出序列u_i+1，…，u_i+J,根据上面同样的方法可恢复出s_j,i+1，j=1,…J。然后由

sj,i+1≡ajsj,i(modmj)

可得：s_j,i≡a_j^-1s_j,i+1(modm_j)，进而得到u_i。因此u_i及前面的序列都可预测出。由于计算s_j,i的时间复杂度为O(lb²m_j) ,因此后向预测的时间复杂度同前向预测。■

注： 定理1和定理2均可推广至各个u_i不连续的情况，当已知各个u_i的相对位置时，由关系式

sj,i+k≡ajksj,i(modmj)(k为正整数)，

同理可进行分析。

3 例子与分析

本节利用定理1和定理2对几个常用的CLCG例子进行分析，以给出预测的分析结果。

设前向预测和后向预测这类CLCG输出序列的时间复杂度为

$y=O\left( \text{l}{{\text{b}}^{2}}M\cdot {{\left( {{a}_{2}}{{a}_{3}}\cdots {{a}_{J}} \right)}^{\frac{\left( J-1 \right)\cdot J}{2}}}\cdot {{10}^{J\cdot \left( 1+\left\lfloor \lg {{m}_{1}} \right\rfloor -x \right)}} \right)$

当J=2时，时间复杂度为

$y=O\left( {{a}_{^{2}}}\cdot 1{{\text{b}}^{2}}M\cdot {{10}^{2\cdot \left( 1+\left\lfloor \lg {{m}_{1}} \right\rfloor -x \right)}} \right).$

当J=3时，时间复杂度为

$y=O\left( 1{{\text{b}}^{2}}M\cdot {{\left( {{a}_{2}}{{a}_{3}} \right)}^{3}}\cdot {{10}^{3\cdot \left( 1+\left\lfloor \lg {{m}_{1}} \right\rfloor -x \right)}} \right).$

例I-1 文^[8]中给出了一个CLCG的构造：

J=2，m1=101，m2=97， a1=51，a2=58，δ1=1，δ2=-1.

CLCG为：

$\left\{ \begin{align} & {{z}_{i}}\equiv \left( {{s}_{1,i}}-{{s}_{2,i}} \right)\left( \bmod 101 \right), \\ & {{u}_{i}}={{z}_{i}}/101. \\ \end{align} \right.$

该CLCG产生序列的周期为

lcm(m1-1,m2-1)=2 400。

例I-2 文^[7]推荐了一个CLCG^{[7, 8]}：

J=2，m1=2 147 483 563，m2=2 147 483 399， a1=40 014，a2=40 692，δ1=1，δ2=-1.

CLCG为：

$\left\{ \begin{align} & {{z}_{i}}\equiv \left( {{s}_{1,i}}-{{s}_{2,i}} \right)\left( \bmod 2 147 483 563 \right), \\ & {{u}_{i}}={{z}_{i}}/2 147 483 563. \\ \end{align} \right.$

该CLCG产生序列的周期为

$\frac{\left( {{m}_{1}}-1 \right)\left( {{m}_{2}}-1 \right)}{2}\approx 2.306\times {{10}^{18}}.$

例I-3 文^[8]给出了另一个CLCG：

J=2，m1=2 147 483 647，m2=2 145 483 479， a1=26 756，a2=30 318，δ1=1，δ2=-1.

CLCG为：

$\left\{ \begin{align} & {{z}_{i}}\equiv \left( {{s}_{1,i}}-{{s}_{2,i}} \right)\left( \bmod 2 147 483 647 \right), \\ & {{u}_{i}}={{z}_{i}}/2 147 483 647. \\ \end{align} \right.$

该CLCG输出序列的周期为

$\frac{\left( {{m}_{1}}-1 \right)\left( {{m}_{2}}-1 \right)}{2}\approx 2.30\times {{10}^{18}}.$

已知2个连续输出序列u_i和u_i+1中每个序列的连续x位，能在时间复杂度为y下预测前面的和后面的输出序列。这3例中的x和y对应的值分别见表1、表2和表3。

由表1、 表2和表3可看出，例I-1中的CLCG完全可以前向预测和后向预测，而且数据复杂度和时间复杂度都很低。因此，不适合作密码应用。例I-2和例I-3中的CLCG在取适当的值时，前向预测和后向预测此CLCG的数据复杂度和时间复杂度较低。因此，也都不适合作密码应用。

例II-1 文^[6]推荐了一个CLCG^{[6, 8]}：

J=3，m1=30 269，m2=30 307，m3=30 323,a1=171， a2=172，a3=170,δ1=δ2=δ3=1.

CLCG为：

$\left\{ \begin{align} & {{z}_{i}}\equiv \left( {{s}_{1,i}}+{{s}_{2,i}}+{{s}_{3,i}} \right)\left( \bmod 30 269 \right), \\ & {{u}_{i}}={{z}_{i}}/30 269. \\ \end{align} \right.$

该CLCG输出序列的周期为

$\frac{\left( {{m}_{1}}-1 \right)\left( {{m}_{2}}-1 \right)\left( {{m}_{3}}-1 \right)}{4}\approx 6.95\times {{10}^{12}}.$

例II-2 文^[7]推荐了另一个CLCG^{[7, 8]}：

J=3，m1=32 363，m2=31 727，m3=31 657, a1=157， a2=146，a3=142,δ1=-δ2=δ3=1.

CLCG为：

$\left\{ \begin{align} & {{z}_{i}}\equiv \left( {{s}_{1,i}}-{{s}_{2,i}}+{{s}_{3,i}} \right)\left( \bmod 32 363 \right), \\ & {{u}_{i}}={{z}_{i}}/32 363. \\ \end{align} \right.$

该CLCG输出序列的周期为

$\frac{\left( {{m}_{1}}-1 \right)\left( {{m}_{2}}-1 \right)\left( {{m}_{3}}-1 \right)}{4}\approx 8.125\times {{10}^{12}}.$

已知3个连续输出序列u_i、 u_i+1和u_i+2中每个序列的连续x位，能在时间复杂度为y下预测前面的和后面的输出序列。例II-1和例II- 2中的x和y对应的值分别见表4和表5。

由表4和表5可看出，在x取恰当的值时，进行前向预测和后向预测这两个CLCG的数据复杂度较低。不建议这两个CLCG应用在安全性要求较高的场合。

4 结 论

一些重要文献推荐的一类CLCG尽管能达到周期大等良好性质，但在抗预测攻击方面尚欠研究。本文对这类CLCG抵抗预测攻击的能力进行了刻画。对3篇重要文献中的5个CLCG例子进行前向预测和后向预测的分析结果，表明对有些推荐的CLCG进行前向预测与后向预测，数据复杂度和时间复杂度较低。因此，在一些推荐参数下，这类CLCG抗前向预测与后向预测攻击的能力较弱，不适合作密码应用。