2n周期优秀二元序列生成及其特性分析

牛志华,李 政,李 哲,辛明军

(上海大学计算机工程与科学学院,上海 200444)

2n周期优秀二元序列生成及其特性分析

牛志华,李 政,李 哲,辛明军

(上海大学计算机工程与科学学院,上海 200444)

定义周期为2n的线性复杂度和k错线性复杂度均高的二元序列为优秀序列,设计了遗传算法来生成2n周期优秀二元序列.对周期为8、16、32,k值为N/4的情况,匹配各种参数搜索优秀序列,用Lauder-Paterson算法对得到的结果序列的线性复杂度谱进行了分析,以说明它们确实是优秀序列.由实验结果推测周期N为2n的二元优秀序列当k取N/4、N/8时的k错线性复杂度满足规律LCk(S)≤N-2k+1(对周期为64、128、256的序列也进行了实验验证),并且优秀序列在所有同周期的二元序列中所占的比例为1/4.

流密码;周期序列;线性复杂度;k错线性复杂度

设(S)=(s0,s1,s2,…)是有限域GF(q)上的序列,若对于任意的i,有si=si+N,则称(S)为N周期序列.称(S)满足的下列线性递归关系式的最小的阶数为序列的线性复杂度,记为LC(S):

密钥流序列的线性复杂度必须足够大,因为只要知道连续2LC(S)个比特,就可以通过解线性方程组或借助BM算法[1]将整个序列完全确定.

密钥流序列不仅应该具有高的线性复杂度,而且其线性复杂度必须稳定.例如一个周期为N的二元序列(S)=(0,0,…,0,1)∞,其线性复杂度LC(S)为N,但只要把其每一周期的最后一位的1变为0,该序列的线性复杂度就立刻降为0,这样的序列是不稳定的,显然,用来作为密钥流序列是不安全的.针对这一问题,国内外学者相继提出了球体复杂度、重量复杂度[2]、k错线性……