密钥流的伪随机性：探讨与优化

显然，流密码系统的安全性取决于密钥流序列的性能。当密钥流序列是完全的随机序列时，流密码系统是不可破的。随机序列的特点主要体现为无规律性，是不可预测的。实际中应用的密钥流序列是由密钥流生成器经过确定的算法产生的，密钥流生成器本质上是一个有限状态自动机，由于有限状态自动机只有有限存储和有限复杂逻辑，其输出序列本质上还是周期序列或终归周期序列，是有规律的。为了保证密钥流体制的安全强度，密钥流伪随机序列的随机性还需要满足一定的条件，以近似地实现理想保密体制。周期、游程和自相关函数常被用于度量或检测伪随机序列的伪随机性或随机程度。

定义3.1 对无穷序列{a_i}，若存在正整数T，使得

a_i+T=a_i，i=0，1，2，…则称该序列为周期序列，满足上式的最小的正整数T被称为该序列的周期。若除了前面的有限项以外，后面剩余的所有项构成一个周期序列，即存在N，使得a_N+1，a_N+2，…为周期序列，则称该序列是终归周期的。

由密钥流生成器生成的密钥流伪随机序列都是周期序列或终归周期序列，要满足一定的随机性需要有足够长的周期。

定义3.2 序列中存在的一段连续相等的元素构成的子序列称为序列的一个游程。如序列{a_i}中存在

则（a_t，a_t+1，…，a_t+h-1）为序列{a_i}的一个长为h的游程。如果a_t-1≠a_t≠a_t+1，则（a_t）为一个长为1的游程。

游程就是一串相同的序列元素，其前导和后继都与之不同。显然，序列中长的游程数越多，可预测性越强，随机性越差。

序列的随机性还体现在同一序列的不同项之间的相关程度上，用自相关函数描述。密钥流生成器产生的密钥流序列为0-1二元序列，二元序列的自相关函数定义如下。

定义3.3 周期为T的二元序列{a_i}的自相关函数定义为

R（j）=（A-D）/T，j=0，1，…，T-1(www.xing528.com)

其中，A=|{0≤i≤T-1：k_i=k_i+j}|，D=|{0≤i≤T-1：k_i≠k_i+j}|。

定义中的A表示序列{a_i}及其平移{a_i+j}在一个周期内对应位相同的位数之和，D为对应位相异的位数之和，因此自相关函数为序列与其平移在一个周期内的相同位数与相异位数之差。显然，对于所有的j，有R（j+T）=R（j），所以只需要考虑[0，T-1]范围内的j就足够了。自相关函数在数值上越大，反映出序列的不同项之间的相关性越强，随机性越差。对于真正的随机序列，如独立均匀分布的二元随机序列，其自相关函数的期望值仅在j=0时为1，在j≠0时均为0。当j=0时，称相关为同向相关；在j≠0时称为异向相关。

基于以上三个定义，Golomb提出三条随机性假设用于度量二元周期序列的随机性，并定义伪随机序列：

1）在序列的一个周期内，0与1的个数相差至多为1。

2）在序列的一个周期内，长为1的游程数占总游程数的1/2，长为2的游程数占总游程数的1/2²，…，长为i的游程数占总游程数的1/2ⁱ，…，且在等长的游程中，0，1游程数各占一半或至多差1个。

3）序列的自相关函数为双值，即所有异相自相关函数值相等（为常数）。

满足上述三个条件的周期序列称为伪随机序列。条件1）表明序列中0与1出现的概率基本相同；条件2）表明在已知前若干位置的值的前提条件下，后续位置上出现0或1的概率基本相等；条件3）说明通过对序列的不断平移进行分析，不能获取到关于序列的周期等实质性信息。

满足Golomb的三条随机性假设的周期序列还不能完全满足密钥流序列在安全方面的要求。为了保证密钥流序列的安全强度，对于序列的随机性还有更高的要求，应使其尽可能地接近真随机序列的特征。除了具有Golomb的三条随机性假设中提出的良好的统计特征外，密钥流序列应该还具有极大的周期、良好的线性不可预测性等性质。真正的随机序列是非周期的，而按照任何确定性算法产生的序列都是周期或终归周期的，为了使其更接近随机序列，需要求其具有尽可能大的周期。二元随机序列的各项之间是相互独立的，即在已知前面有限项的情况下，后面的项是不可预测的，用条件概率公式表达即为P（a_ia₀，a₁，…，a_i-1）=P（a_i）。实际上要求在已知部分密钥的情况下，不能推出整个密钥序列。线性不可预测性就是要求不能从部分密钥通过线性关系简单地推出整个密钥序列，这要求产生密钥序列的最短线性反馈移位寄存器要有足够的长度。