单圈T函数输出序列k-错线性复杂度研究

该文对单圈T函数输出序列的k-错线性复杂度进行了深入研究,利用多项式理论和Chan Games算法,分析得到了当n=2t时,单圈T函数输出序列线性复杂度的n个下降点及其对应位置的k-错线性复杂度,并给出了k-错线性复杂度的分布和k-错线性复杂度曲线。     

单圈T函数序列与M序列研究

在SETA 2006会议上,ZHANG Wenying和WUChuan-kun对关于变元数n=2t的单圈T函数序列的线性复杂度进行了计算。计算任意变元数的单圈T函数序列的线性复杂度和1-错线性复杂度,并且证明任意变元数为n的单圈T函数序列的最小周期为n2n。进一步推出变元数n=2t的单圈T函数序列的2n-1-错线性复杂度为n2n-2+n-1。推出的另一个结果是当n大于1时,变元数为n的单圈T函数序列不可能为M序列。最后,研究单圈函数序列与M序列之间的关系。     

2n-周期二元序列的3-错误序列分布

线性复杂度和k- 错线性复杂度是度量密钥流序列密码强度的重要指标。为了更好地研究序列的随机性,该文通过将序列的k-错线性复杂度的计算转化为求Hamming重量最小的错误序列的方法,讨论了序列不同k-错线性复杂度条件下对应的k-错误序列的分布情况。基于Games-Chan算法,该文给出了线性复杂度为2n的2n-周期二元序列的3错误序列的计数公式,计算机编程验证了该文方法的正确性。     

单圈函数序列研究

在流密码的设计中,通常要用一个随机源。常用线性反馈移位寄存器作为随机源。在Klimov A和Shamir A提出单圈T函数的概念后,许多学者在设计流密码时用单圈T函数作为随机源。为了得到新的随机源,单圈T函数的概念被扩展,单圈函数和单圈函数序列的概念被定义,单圈函数序列的最小周期被计算,有限域上分圆多项式的表达式被给出,与分圆多项式相关的两个定理被介绍。以这两个定理为基础,单圈函数序列的线性复杂度的下界被推导,猜测在许多情况下,单圈函数序列的线性复杂度远远大于这个下界。     

二元周期序列的4-错线性复杂度

 k-错线性复杂度是衡量序列伪随机性的重要指标之一.对线性复杂度第一下降点为4的以2的方幂为周期的二元序列,本文通过分析Games-Chan算法,给出了其4-错线性复杂度的所有可能取值形式以及具有给定4-错线性复杂度的序列的计数.更进一步,给出了其4-错线性复杂度的期望.结果表明,其4-错线性复杂度的期望与线性复杂度相差不大.     

Fp上pn-周期序列的1-错线性复杂度

周期序列的线性复杂度和k-错线性复杂度是衡量密钥流序列随机性的两个重要指标.该文给出了Fp上pn-周期的序列所有可能的1-错线件复杂度的值以及具有给定1-错线性复杂度的序列个数.更进一步,该文给出了Fp上pn-周期的序列1-错线性复杂度的期望.     

自相关性和线性复杂度的关系

自相关性和线性复杂度是衡量序列伪随机性质的两个独立的指标.针对周期为2^<em>n的伪随机序列,本文首次指出了自相关性和线性复杂度之间存在的一个关系.该关系可应用于以下两个方面:(1)由序列的线性复杂度来估计/确定序列的自相关函数值;(2)通过线性复杂度来检验给定序列族的互相关性质.进一步的,针对一类周期为2^<em>n的伪随机序列,我们指出这类序列的自相关函数值和线性复杂度以及k-错线性复杂度存在着关系.     

计算有限域GF(q)上2pn-周期序列的k-错线性复杂度及其错误序列的算法

序列的k-错线性复杂度是序列线性复杂度稳定性的重要评价指标。在求得一个序列k-错线性复杂度的同时,也需要求出是哪些位置的改变导致了序列线性复杂度的下降。该文提出一个在GF(q)上计算2pn-周期序列s的k-错线性复杂度以及对应的错误序列e的算法,这里p和q是素数,且q是一个模p2的本原根。该文设计了一个追踪代价向量的trace函数,算法通过trace函数追踪最小的代价向量来求出对应的错误序列e,算法得到的序列e使得(s+e)的线性复杂度达到k-错线性复杂度的值。     

单圈 T-函数的 2-adic 复杂度和 1-错 2-adic 复杂度

研究了由 上单圈T-函数所导出权位序列的2-adic复杂度,设 为整数, 。结论表明,第 权位序列2-adic复杂度的上界为 。另外,讨论了与所有单圈 T-函数所导出第 权位序列相对应的2-adic整数的分布,分布情况说明这个上界是可以达到的。最后,研究了权位序列的1-错2-adic复杂度。研究结果表明对所有 ,权位序列 的1-错2-adic 复杂度都与其2-adic复杂度相同。     

基于猫群优化算法的2~n周期优秀二元序列的研究与分析

密码学上强的序列不仅应该具有高的线性复杂度而且线性复杂度应该稳定,该文称此类序列为优秀序列。猫群优化算法是一种智能的全局优化搜索算法,能够根据给定的合理条件,自动生成所希望得到的结果。该文通过设计合理有效的适应度函数和恰当的参数选择,将猫群优化算法用于求解优秀序列,得到了周期N为32,64,128,256,512,1024等,错误数k小于等于N/4的二元优秀序列。并且结合大量实验数据,分析推测周期为N的二元优秀序列k-错线性复杂度满足规律LCk(S)￡N-2k+1。     

Linear complexity of sequences produced by single cycle T-function

Four kinds of sequences generated by single cycle triangular function(T-function)are investigated to check the possibility for a single cycle T-function to be a cryptographic component in stream ciphers.Based on the special properties of single cycle T-function and an algorithm due to Wei,linear complexities of these four kinds of sequence are all acquired.The results show that single cycle T-function sequences have high linear complexity.Therefore,T-function satisfies the essential requirements being a basic component of stream cipher.     

二元周期序列的k错误线性复杂度

随着k的增大,序列k错误线性复杂度的值会从线性复杂度递减到0.对于周期为2的方幂的二元序列,Kurosawa讨论了线性复杂度和k错误线性复杂度的关系,给出了使得序列的k错误线性复杂度严格小于序列的线性复杂度最小的k值.本文利用多项式的权重关系给出了使得序列k错误线性复杂度再次减小的最小k值.     

THE 2-ERROR LINEAR COMPLEXITY OF 2^n-PERIODIC BINARY SEQUENCES WITH LINEAR COMPLEXITY 2^n -1

Linear complexity and k-error linear complexity of the stream cipher are two important standards to scale the randomicity of keystreams. For the 2n -periodicperiodic binary sequence with linear complexity 2n 1and k = 2,3,the number of sequences with given k-error linear complexity and the expected k-error linear complexity are provided. Moreover,the proportion of the sequences whose k-error linear complexity is bigger than the expected value is analyzed.     

关于求周期序列k错线性复杂度的Stamp-Martin算法

在k错线性复杂度的实际应用中,误差向量的计算是非常重要的。因此改进了Stamp-Martin算法中cost向量的结构,从而使该算法求周期为2n的二元序列k错线性复杂度更加简洁且容易理解,同时给出了求相应误差向量的算法,即在该误差向量下,能够实现最小的k错线性复杂度。     

随机周期序列☆错线性复杂度的期望上界

周期序列的k错线性复杂度是衡量流密码系统的安全性能的一个重要指标。本文给出了周期序列k错线性复杂度上界的一个更强的结果,从而给出了几种不同情形下随机周期序列k错线性复杂度的期望的上界。特别地,还给出了周期N=pv,随机周期序列满足一定条件时1错线性复杂度的期望更紧的结果。     

The 2-error Linear Complexity of 2n-Periodic Binary Sequences

Linear complexity and k-error linear complexity of the stream cipher are two important standards to scale the randomicity of key sequences. For a random 2n-periodic binary sequence, the number of sequences with given 2-error linear complexityis provided. Then the expected 2-error linear complexity of a random 2n-periodic binary sequence is given.