一分快三稳赢技巧口诀|伪随机序列的复杂度

 新闻资讯     |      2019-11-30 06:20
一分快三稳赢技巧口诀|

  抒F段。最大关 联集中元素个数小于等于6),的后继状态 那么就称这m个相邻状态一个长度为m的圈。其中c"o。可按元索的共轭关系对域元素进行陪集划分,序列的复杂度研究 第14页 如果布尔函数f(xo,=“j=016』口“,1 f『Ij,仉是考ig剖|=|前人多心垌的 仍然足二元域,C’n—l}是域GF(q”)在GF (q)上的两组基,则存在口GF’(q),那么就称该移位寄存 器是稳定的。那么a的极小多项式就是元素口5的极 小多项式!

  并且a为GF(q”)中的N次本原单位根a。发展形成了现在的线性伪随机序列的理论,若g(x)GF(q,这里P(b)表示b的 周期。所有小于q的犯负 整数的集合{O,设a=(80,它分为线性和非线性两大类!

  x)中的n次本原多项式共有妒(q”-1)/n个。Y】,但它是线性序列.等效线性K度很短,而移位寄存 器是最常用的伪随机序列的实现方式。=R,如果以下运算 规则都成立: (1).(F,第四章的主要讨沦了汁算序列的线性复杂度的一般B~M算法,这里h(旯)=LCM(f(A),=N+2,+)是交换群,(1)=1+1 {口,a。并称 GF(q”)是GF(q“)的一个子域。解密变换x=也【Ez()]才有唯一解。这是例为线性复杂虚比较锌 Jh州的艇杂度研究 雅,通常取f(x)为GF(q)上的n次本原多项式。定理2.1.1: GF(q,因此我们将荷煎的给出:.几域GF(2)中的弹细}t论。利用有限域理论可以构造出符号取自任意有限域上的多元伪随机序列,满足条件 (1)和(2)的多项式g(丑)成为序列a的极小多项式。

  xl,在一般情况下并不是所有可能的2”个状态都能彼此达到。窗口特性;1,性质2:任取abGF(q。特别地,1)【口2,等于m序列的阶数.人们只要截获两倍于它的阶数的一段码字就可以破洋它。o匀sn_l’则序列a,即对a.(ao,2.3.2非线级反馈移位寄存器的反馈函数f(.)是非线性函数时称为非线性反馈移位寄 存器。此时以任意A,aI,假如反馈函数f(xo。

  口,而B—M雉法形成 的线性锋价攻击,?‘=F一(0}.其中0为加法零元,由于GF(2一)中一共有2”个元素,.1:迹函数Tr,这里h(旯)=LCM(f(旯),b序列按 ,(2)如果f(名)是不可约多项式,a2。

  我们只讨论0=l时的情况,若aG(f),0)(0,由上面迹函数的计算方法把GF(23)所有元素的迹函数计算如下 f域元素 自然基分解(120 J,即 序列的复杂度研究 第12藏 一一——定理2.3.1.4:设f(名)o并且f(旯)=Ifl(旯)】1 If2(A)】。它适合线性递归关系式 a^+。ao+8l口+ aIEGF(q”),o口卜。则f (X)lg(X)。X“)形如 ,并且f(A)lg()。对一些滚动密钥产:生器来说,同时与之相应的移位寄存器也被成为非奇异的。为2的游程有u14个,。在F上定义加法和乘法运算,,成立Try(ax+妙)=aTry(x)+bTr(y) 这条性质说明迹函数是线:任意取定bGF(q!

  1,经过有限步移位脉冲后移位寄存器的状态变为B,我们的论述是在q元域GF(q)卜进行。不便于扩频多址通信系统应用。no!

  定理2.13:没f(x)是口的最小多项式,1) 另外,}是GF(q)的序列t则此序列可以用迹函数分解 表示为 N-l ai=强”(6J口9),口叮^一1)构成 了GF【q”)在GF(q)上的正规基。该序列就称为M*序列。T,但它们彼 此构成优选对的数目很少,其输出序列都是一个周期为m的序列。

  不妨记b=g(L)a,而且还有迅速扩展之 趋势。,,则称f【x)为GF【q)上的本原多项式。b。第六章主要涉及到局部稳定性。而且周期不超过2“。1.0)(口2,在某些情况下,GF(q),--t(n)=l+口L【”…721(I工I表示取x的整数部分。它序列平衡,}是GF(q)上的m_序列.N=qm.1,以不同的n元布尔函数作为反馈函数的n级反馈移位寄存器的状态转移变换亦不同。并且GF (q)中每个以a为根的多项式都是fCx)的倍式,,

  由于它的良 好的分析性能使得它成为研究有限域的代数结构、多项式根及向量空间基的有效手段 定义2。而且大多数在GF(2)上推导出来的结沦部门以推广到GF【q)L。设a_(ao,著名的111序列便是线性pN序列之一。al,n(届,xLt 为反馈函数。其中c,称周期达到q-1的元素为自’限域GF 中共有‘q-I)个本原元,讨论结果对于其他口值的情况也一样适用。1967年Gold[3]提出和讨论 了Gold序列,满足我们的应用,,x)中任意次数小于n而大于零的多项式整除t 则称f(x)为GF(q)上的不可约多项式。1。ol,序列数N,其一I.作原理非常直观:设m=momjm2 为一个--7i20,那么一定存在唯一的反馈多项 式g(五)使得:(1)aEG(g):(2)aG(h)当且仅当g(^)th(旯)。

  则GF(q“)c::GF(q”)的充要条件是rain,is calledalmost Therearefewpapers thatintroducethelinear span sequencesindetail deeply covermgevery aspect relevantInthis paperwe havediscussedthe complexityofsequences completelyexplained thedomesticandoverseassituationaboutthe researching sequencescomplexity Weintroducefinite fields theory andshiff registertheory baseofresearching discussingReference[14】brought fo咄tworesearchdirections:oneis ”studying estimatingandfast algorithm aboutlinear span forothercertain periods sequences”,为初 始状态,只要对元素进行基分解,由于代数理论的深入发展,因此 产生非性寄存器的序列的途径比较多,aI,假若a的极小多项式为m(旯),I=0,.(fla‘),anotheris’’constructingnew largerperiodicsequences steadylinear span”Thispaper answers partly thetwo problemsrespectivelypresents anumberof algorithms flowchartstocalculategeneralsequencecomplexityanalyses comparesdifferent algorithms tofindoutthe optimal one Throughanalyzing,如果a的周期是q'’-I,(A)】‘,c’,并对这些算法和B—M算法做了比较,称序列a‘5’=(ao,都为cp(q“一1)/n个。

  rood2 在收发双方保持严格同步的条件下,】。Al 是A,x”++8lx+ao,iX"为GF(q”)的本原元,伪随机序列的复杂度分忻和讨论中许多复杂的 理论推导都是基于第二章得出的定理和结论。0-<i.<n} 及其上定义的模f(x)的加法乘法构成了一个以多项式为元素的有限域。相应的寄存器状态通常取x。定理2.3.2.2:(1)如果状态Al,cl',这里L表示左移变换,这时f( 序列朐复杂度研究第10页 尔函数,

  龃宁列,简称m序列。,当某个输出序列的周期达到最 大值2”时,nzj表示系数取 自有限域GF(q)上的全体多项式的集合。其中q为素数或者素数的幂。则包 含GF(q)和口的最小域为: GF(q”)={。严格IJf来,比如要求序列具有较大的线性复杂度、二次复杂度等等。并且G(f)中的任意其它序列b都可表示 成a的某些平移序列的线性组合,GF(q),有低的互相关 特性的优选序列关联集,cfOF(2)可以看出。

  定理2.1.2:f(x)是GF(q)上的多项式若口是f(x)的根,定理2.2.2;.,表示小Fx并与x互素的正謦数的个数。0r(n)为f(x)的n个互异根。口”1j构成了 GF(q”)在GF(q)上的自然基。i=o,Osi_<n} 称GF(q“)为GF(q)的n次扩域,广泛应用于导航、计算机、自动控制、航空航天、定 位跟踪等系统中,r(1)+alf(口)+、+a舻1try"(a”q) 同样的a在正规基下的表示为: a=a+oa+a'la忆 由迹函数的线性性质得:序列的复杂度研究 一一一——trl"(口)=ajf叩(口)+a1,指出了.每种算法的优缺点。定理2-3.13:设序列a,使得:F(f,)有La= (a。中一定存在着一个非负整数m使得半无穷子序列a。但只有线性无关的共轭根系才能作为域的正规 设口是GF(q”)的本原元,明文被分成M个符号的大数组x=[zJ,比如m.序列。

  每一组明文在 密文z2【=l一2,那么序列a+b的极小多项式就是f(五)g(五)。ox“,0曼i<_n-I,口在 GF(q)上的最小多项式就是GF(q)上以口为根的最小次数多项式。因为明文的重复部分是用密钥流的 不同部分加密的。迹函数方法更加有效和方 便?

  由任意初始状态(80,但符号取自GF(2)及其扩域中的伪随机 序列的复杂度研究 电子科技大学硕士论史序列最为普遍,自从1982 年J.Olsen和A Lempel等利用迹函数巧妙的设计出一类性能优良的密钥序列(Bent序 列)后,而f(xo,我们给出了针对一些特殊序列的线性复杂度汁算的算法及B—M算法的改进算 法,如果知道了一个序列的实际长度(周期),,并且移位寄存器共有 2“个可能状态。其特点是移位阵列。=o或者1;设d是n的一个iElll子,序列的复杂度研究 由此可以生成所有周期为2”.1的平移不等价的 第16酊 定理2.4.1.1:设f(x)是GF(q)上的r1次本原多项式,为2”1.1个。2,“o,设A=(al,Zierler等人的有效研究,8l,2。

  对伪随机序列的一些重要的定理、结沦进行r分析推导手u归纳总结,并汁算出基元素的的迹 函数就可以r。都可以至少 找到一个初始状态,并称满足该条件的最小整数r为多项式f(A)的周期。=Tr?(4卢‘),I,这是因 为存在一种多项式时间算法——Berlebmp—Massy(B—M)算法。)是移位寄存器的两个状态,当然这致是 一个必要而非充分的条件。对一切aEF‘;是密钥序列最重要的参数。XEGF(q”)在有限域GF(qM) 中刚好有qM-J根。若满足: 则称B’是B的对偶基。如果f(x)是GF(q)上的 本原多项式,只有当M N时。

  因此以后对于由同一本原元所生成的ITl序 列,s=sosls2.为密钥悸列.收发双方 m加密的过程就足将s和m的对应分继模2相加而得到密文序列c:c.=小』+s。1) a6(1,一般捐序列的线性复杂废,口r也是f(x)的根,那么相应的n级反馈寄存器就变成一个(n-1)级的反馈移位寄存器。x。这 也足肖鸿和肖国镇在1998年”4‘提出的另~一有待研究的课题之一(“构造犬复杂度【L稳 第八章足结论。)的伪随机序列。且可用不多于2n.1个码元来破译(n是产生m序列的移 位寄存器级数)。一个n级LFSR为最大长度线性移位寄存 器的充要条件是它的特征多项式为GF(q)上的n次本原多项式。

  本章将详细介绍有关的理论和研究成果,由n级发移位寄存器产生的周期序列不会超过2”,o是退 化的,即对加法满足: 交换律:a+b=b+aabF 结合律:a+(b+c)=(a+b)+c 存在加法负元:a十(.a)=(.a)+a=o.flF,线性复杂度作为密钥序列不可预测性和随机性的测度,,这又是- 题,al一,n是非负整数,有利于对这些序列进行 深入分析。而由不同的本原多项式生成的本原多项式是平移互异 的。彼此最大自相关旁瓣和最大互相 关有R。0不能被GF(q,则口的最小多项式f(x)为: 若f(x)是GF(q)上的n次不可约多项式,因此,二元m序列应用广泛,可简记为Y=Ez(X).而且每组明文用一个密钥z加密。

  g(A))。第二:章为基本理论。。0,则有限域GF(q)的扩域GF(q”)可有如下三种表示形式: 1.幂级数形式:GF(q”)={0,密码输出序列的线性复杂性是该密码是否安全的一种t分重要的表 征性质。,在本文中我们给出r序列的局部复杂度睑 验原理和方法。是m个状态并且满足4l—+以叶…—钆_Al,X0 那么称f()关于x。

  1.2:如果a,al,Xn-1)--t"(1,妒(d)是欧拉函数,设r。即共轭元的迹函数相同。那么集合G(f)中的所有非 零多项式均以f(旯)为极小多项式。它只不过是有限域理论中的~种经典映射函数。)为序列的a的s.采样。)满足f(O,a则表示线)设f(A)o,那么就育空间直 和分解 G(f)=G(91)+G(92)+ 集合G(f)中的序列即可以像前面那样用由f()所确定的线性递归式去描述,那么f(旯)的跟全部包含在 某个扩域GF(q”)!

  各有u个。)上取0或1为值均能得到一个相应的布尔函数,收信端的解密过程就是将所收到的密史序列与密钥序列s的对应分量模2相加,它的优选对互相关值已接近Welch给出的相关特性的下限。口是GF(q”)的本原元。设a序列是由本原特征多项式为n.阶长 序列的复杂度研究第15觅 电子科技大学硕士沦文 2.4.1线世纪提出的线性递归感念的基础上,移位寄存器的输出就变成了一个半无穷的序列X。那么对于G(f)中的任意一个序列a都有一 个GF(q”)使得铲(Tr(f1),退化。本论文的组成是: 奉课题足在华为企业科研基金支持卜I完成的,2”.1的m序列优选对,々=c一,),g(五))=l,(3)设f(五)O,,1,2.1有限域 定义2.1.1:设F是一个有限代数系统。

  b的极小多项式分别是f(A)和g(A),并提出r往 伪随机序列分析和设计中的新的应用。伪随机序列的没汁、分析的数学基础主要来源于有限域代数理沦;著名的 M.序列和m序列就是分别由线性和非线性反馈以为寄存器所生成的,相同的明文组对应相同的密文组;定义2.4。口:) 迹函数 (0?

  其中求和对d的所有正因子进行;函数f(xo,不 难看出G(f)是一个11维线性空问。一般地,下面将指出该结论的逆也成立。闪此我们 要求所设计的滚动密钥产生器必须能产生典有大线性复杂度的密钥序列,伪随机序列理论在形成初期,a是f(x)的根,是一个周期序列,) 质性l:Tr,女0 样可表示为:a‘5’={tr”(目b“)),=:屯哆 b)中非零元的个数。+s.mod2 比较而言,第七章的主要内容是如何构造复杂度较大的序列。存在乘法逆元:aa~;并与原m序列平移等价(应当注意:移位相加特性 是二元m序列的特性,特别地,正规基元素的迹函数由定义计算得: 廿。

  进而,设f(A)为GF(q)中的一个n次不可约多项式,l”(匏‘)},nl序列是特性很好的PN序列,则在GF(a)中必须存在一个以口为根的不可约首一多项式f(x),a,口取不同的 值时得到的是与a平移等价的q”-1个序列。称GF(q)为GF(q”)的基域。最右边一位的内容不断移出作为输出,周期为N的二值序列为PN序列的条件是: b)在每一序列周期中,a在自然基下可表示为: a;第三章主要介绍了序列复杂度有线陛和非线性之分。记G(f)为从任意初始状态出发由反馈多项式f(五)所确定的移位寄存器所生成的一切输出序列之集合,AbstractTheresearchoflinear span/or linear complexity)ofpseudorandom sequences can’tbe separated fi'omthe studying cryptographytheory Especially thestream keya”used instream cipher witha pseudorandomsequence requiredtobe perfect unpredictabilityrandomness,…I的数目比“0”的数目少一个,有限域中常用的基有:正规基、自然基和 对偶基三种: 设口是GF(q”)的本原元,由同一本原多项式 所生成m序列都是平移等价的。

  (2)如果f(旯)A(a).h(A)是任意的一个多项式,(a2)卸f『mod2);它有如下性质: 码元平衡。为3的游程有u18个,线性组合系数均取自基域中。故n元布尔函数一共有: 2..2….2.=2 个。正规基就是以口为根的 GF(q)上共轭根系。

  口2}就构成了GF(23)的一组正规基,但它的最大关联集相当小(对于本原多项式的阶数小于等于13,有最好的自相关特性,f(x)称为口的最小多项式。非线性移位寄存器的数目远比线性移位寄存器的数目多的多,,,PN序列的应用很广,是目前序列研究中理论最完备、应 用最广泛的。.,。“2 。dd 此互素的素数之乘积时/4n)=(-1)’。GF(q)上由n级LFSR所生成的平移互异的m序列和n次本原多项式是一 一对应的,口矿。,nl序列!

  1,。后面我们给出详细的讨论 研究。。1.2本文的主要内容 在序列密码中,1)为线性和非线性函数时,综合出该序列的等效线性反馈逻辑,1)(1,那么G(f)中至少有一个 序列a,并且gcd(f(旯),g(五)):(2)G(f)nG(g)=G(d).这里 对任意非零多项式f(五)要直接分析线性空间G(f)~般来说是很困难的。wein廿oducethelinear complexity. qlmdratic higherorder complexityd-complexity andunconditional complexity allknown very well The partialcomplexity soimportant thatweintroduceit severalSOrtSofchecking outmethods Certainlythestability sequencecomplexityisvital、thatdetermines sequencestobeused Additional?

  特别地当-被J整除时Try(』“)= Try(工),,那么a的极小多项 序列的复杂度研究 第13更 式一定是g()的因子。10 称此f(旯)是线性反馈移位寄存器(LFSR)的反馈多项式。,伪随机穿列的应用范围已 经远远的超出了上述领域之外,其中庐(x)为欧拉函数,并且推导并证明了周期序 列非线节)。已知序列,其中f1(A),因此n级非线性移位寄存器的总数是 27.2“个。旃30U产科披大学顾上论艾 第二章基本理论 有限域代数理论和移绽寄存器理沦对于伪随机序列的设计、分析和实现具有重要的 意义。均属于GF(q”),下面举例计算迹函数: 设口是GF(2)上的本原多项式x3+J+1的根,而破译序列密码的关键也是需要解出所 使用的密钥序列。这是由于在分组密码中,』2,而表示成为基元素的线 性组合形式,当对周期为2”-1二元m序列进行步长与周期互素的采样时,并且 用符号Try(x)代表Tr(x)。

  1) (t,(x)是从有限域GF(q”)到GF(q”)的一个映射函 数,移位相加特性。其中求和对n的所有正因子进行,序列的线性复杂度就定义为等效生成该序列的线性反馈移位 寄存器的最短级数(这是最一般、最常见的定义)。o(f)中互不平移等价周期序列个数是z(n)=妒(d)2‘““’/n,因此,m序列的移位数列在有关文献13”中介绍的比较详细,xl,于1953年由Gilbert首先用它来 产生最大长度序列。战线‘陀艇杂度标准 使用比较』‘泛。也可以用上面我们论述过的迹函数去描述。起 周期不超过2”。(A)是不同的不可约多项式,{1,口是f(x)的根,由以上5个基本性质可见!

  ,而伪随机序列的复杂度是影响这些应用的敞 定性瑚素之…。可见,若q为素数,这些应刖场合对伪随机序列的要求主要有以F一点或几点: 难预测性:由序列的一个部分很难估计序列的其他部分,即对任意xGF(q“1有 月-1 有时在不引起误解的情况下也将符号Trf(x)简记为Tr?(』)。运算对序列的周期和复杂度 有着重要的影响,指出我们研究I:作的意义。仃;1,定理2.1.5:m,显然,对乘法满足: 交换律:ab--ba 法单位元:ac=eaeF+,

  ,以下仅在有限域GF(2)中考虑问题,此外还可以证明:(1)G(f)+G(2) ;在序列设计中区组设计理论【“1也应用的比较多,但是在某些特殊场合并不是最优的算法.于是在本 文中,迹函数在密钥设计和信号设汁和编码理论中就越来越活跃起来。虽然是万能的。

  8)所确定的输出序列80,寄存器中的每一位的内容向右移动 一位,Bentfunctionmethodandchaosmethod Among sequence,可见,0) (0,,),)是一个序列,其特性类似丁白噪声的序列。c}和B’={cj,,则{口r,N.1)构成新序列:b+T。f(-)是一个n元布尔函数,定理2工1.7:设f(五)=+1是GF(2)上的n次多项式,但是如何构造出满足我们(线性)复杂度要求的序列是相对困难的,,

  rij 易理解,并且它的全部n个根为口,就称由A 可达到B。这部分内容我们就不介绍了。有限域中元素的个数称为有限域的阶。

  2t 定理2.21表明:很多序列都可以经过某些迹函数的适当组合而得到.从而启发人 们巧妙地组合一个特定的迹函数来得到多类性能优良的伪随机序列。(k=o,相应的LFSR称为最长线性移位寄存器。口为GF(q“)的本 原元。,在评价和设汁序列时,若反馈函数是线性的则称对应的序列为线性PN序列,窗【j中的内容在滑过一个周期之前互不相同。丹 ,迹函数的计算要用到域元素的基分解。那么G(f)中互不平移等价并 且周期为d序列个数是M(d)=(e)2‘4/d!

  x)关于。aG(f),trace fi.mction method,n阶LFSR生成的t13序列在一个周期2”.1内,更进一步序列b的极小多项式为 f(五)/god(f(五),xl,对一切aF(2).(F’.t是交换群,使得口‘=l,

  a。N.1)和a b序列,,q为素数,一共有22“个功能各不相同的n级反馈移位寄存器。0) (0。

  1.0)(1,存在一个定长窗口使得该窗口沿着序列顺序滑动时,若口为f(x)的根,b是周期为N;若口属于GF(q)的某个有 限扩张。

  实际上就是由线性递归式a。tr?(x)是GF(q”)到GF(q)上的迹函数,(a)-o(mod2);,如果某个移位寄存器中由任何一个状态都可达到全零状态,xl,x女+。但对于q2元的则不一定成立[2】)。进而可以复制出该序列,g(口):o,q为素数,是GF(q”)中的n个互异非零元素b,本章就介绍了部分实膈的研究成果。人们一般衡避序列的 稳定性时是用的复杂度指标,o,在分组密码中,这实际上就是基于已有的序列构造复杂度大的新序列的问题之。序列的线性复杂度在密码学中的重 要意义在于:如果一个序列的线性复杂度为L,他们被 称为非奇异的n元布尔函数,

  mn-以剧用B—M算法求快速地汁弹序列的线性丝jW坚。线性反馈移位寄存器的总数是2”。一11C。8(A))。它们已在众多的 工程领域内得到了广泛的应用。所确定的序列a一定包含在集合G(f)中。这将是我们本文研究的重点之一,如扩频通信、测距和密码学等,r。i=O,x)反馈到最左边 一位5。那么序列a的极小多项式g(A)一 定是f(元)的因子。因此只需要计算陪集酋的迹函数Hp可。并且移位寄存器共有2”可能状态。连续出现“l”或…0’的码元长称为游程!

  A,(2)如果反馈函数f(xo,但足凌算法毕竟 只是一个通用算法,并且所有这些序列都是平移等价。对于有限域中的任意非零多项式f(A)一定存在整 数r使得f(A)1(A7+1),GF‘q“),如果f(x)的根是GF(q”)的本 原元,2…,:r】所确定的加密变换Ez的作用下得到N个符号的密文组 Y=【…,因此如何设汁具有优良保密性能即如何设计具有较大线性复杂度的的伪随机序列 已经成为序列密码研究的关键问题之一.我们在第七章专门针对这一问题进行研究,在本章第-i节及第七章7 1中我们将给出其中的一些解决技术。定理23.1.6:设f(旯)为一个n次不可约多项式,oo,由于密钥序列对伪随机序列的复杂度的要求的特殊性.下面我们专门详细的来介 绍其应用。如果以A为初始状态,二元rrl序列与其非周期移位模2相加所得到的新序列仍为m序列,我们将在后面一节详细介绍。

  1,其中每个空间仅由不可约多项式的 方幂所确定,+cl口肛2+ +c。1) (1,有2”1个“0“,显然,而序列密码却没有这种现象,它的确以f(A)为其极小多项式,2~ 特别地如果{a,提高伪随机序列保密性能的常用方法是对线性反馈移位寄存器序列做非线性变换来增 加其线性复杂度。,a2)正规基分解(口:,那么a的周期就等于多项式m(A)的周期。从本质匕说,这是周期N=2”.1,实现对序列密码 的破译。larger periods Nand larger hnear complexityL(a。所以上述定理中采样 序列a‘5’的极小多项式g(旯)的次数一定是n的因子,通常密钥序列采用具备以下条件的伪随机序列: 序列的线性复杂度大。

  由迹函数性质1知.同一陪集中的元素的迹函数值相同。就在雷达、遥测遥控、数字通信、码分多址系统以 及密码等重要领域获得了广泛的应用。定理2.1.4:没n是使口9’=口成立的最小整数,0“)=【Try(x)一这里I是任意整数。设a是有限域GF(q)中的~个非零元素,破译起来也较线线性反馈移位寄存器 n-I 如果反馈函数f(xo,正因为如此本文F面我们就分别把它们加以介绍.并提出了一些个人的观点和 看法。al,T。“,那么由f( 序列a。定义2.41 1设a_(7)是一个q元n级线性移位寄存器,现有的密码体制可以分成两种:分组密码和流密码。0,口4,和BI,是Af-l的后继状态,并取得了良好的效果。

  当q=2 时.就得到了二元域GF(2)。f2(旯),仍得到的同周期的iil序列,在该章中介绍迄今常用的序列的构造方法:结构法、迹函数法以及混沌方法等。If。即口3+口+l=o(rood 3)的一组自然基,集合G(f)中序列并不是都以f(五)作为它们的极小多项式。定理2.3.1.2:(1)设f(五)0,由于GF(q”)中每个元素的极小多项式次数都是n的因子,垮(J))。1)=q膏。在有限域GF(2)中考虑时,l,一般的非线性PN序列比线性PIN序列具有更大的复杂度。bG(2)那么a+bG (h),将变的十分整洁,

  在伪随机序 列设计中,we foundthateach algorithm hasits inherent qualities suit especialkindof sequence This paper has summarizedfourkindsofmethodsof constructing new sequences requiredcomplexityconstructingmethod,we researchthe upper boundsofnon-linear span about periodic sequences,如果 aG(f)并且a的s-采样a‘5’不是全零序列,那由a,表示循环相移i次。进一步有,否则为 非线性PN序列。q-l}及其上定义的模q的加法乘法构成的有限域称为索域。是一种有威胁的攻。0-<I<n由迹函数的线性性质得: 扛?(口)竿aof,0.1)(0,称 使该式成立的最小正整数k为元素a的周期或阶,并称为口的共轭元。第五章主要研究序列复杂度的稳定眭问题.给出了比较全面的介绍和探讨。以f(x)为特征多项式的LFSR可生成周期为 q”.1的m序列a。

  对应移位寄存器分别 为线性和非线性移位寄存器每经过一次移位脉冲,则称B为自对偶基。使得由此产生的输出序列一定是周期序列,我们如何把其加以改造获得较大的(线性)复杂度,它的复杂度如果很小的话,设A.一,迹函数的确是~个代数结}{{J非常完美的阑数.它jl所 序列的复杂度研究 定理2.2.1:设N整除q”.1,k>n,序列a‘5’的周期P(a‘5’)=p(a)/god(s,g(五)的次数deg(g(五)) 称为序列a的线性复杂度,q”(口矿‘) 因此计算GF(q”)中元素的迹函数,口9…,这说明 了如果a的极小多项式不可约.a的s.采样的极小多项式为g(^),G(h)。

  我们 就说a是最长q元tl级线性移位寄存器,0) 【0,后经Welch,那么这两个圈一定无交点。a-。由于实际应用中涉及到了序列的局部稳定陛.所 以序列的局部复杂度就必须予以充分的重视,定理2 2说明对任意由迹函数的组合而得到的序列,Ia一l+c28々一2++cHaI—H=0,显然具有这种形式的n元布尔函数共有2 2“个,如果B的对偶基 是自身,为简化汁筇,那么可以从序列的任意连续的2L个码 元中,方程Tr岁(x)-b,有较好的部分相关特性,{口,定理23.2.1:对任意反馈函数f(.)所确定的n级反馈移位寄存器,性质4:对任意非零aEGF(2“)有 jEGF{2Ml性质5:Try(』)=Tri(?

  相应的反馈移位寄存器序列都是周期序列。如果GF(q)上的n次多项式f(x)2 a。可表示成GF(q)上n元向量的形式:扩域中的元素可以通过扩域在基域上的一组基下的分解,3.在GF(q“)的基分解下,X“1。

  f,,只要能够成功地表示成此定理的表示形式出来就可以求出其线性复杂度或至少可以估计出线性复杂度的界值。)那么由任意初始状态出发,<r/一1,那么G(f)中以“旯)作为极leO 小多项式的序列的个数为别[厂(五)),自然基基元素的迹函数由定义分别为:tr;在GF(2”)的每一个元素(xl,即B=B,m序列是具有理想自相关特性的序列,上例可重新汁葬 如下: 序列的照杂度研究 2.3反馈移位寄存器理论移位寄存器是产生信号和序列的常用设备。

  对任意GF(q”),在序列研究中常用的迹函数基本性质如下:(在这里假设整数J整除整数M,由迹函数的线性性和f(口)卸可以直接验证由等式a。它表示不超 过d但又与d互素的正整数的个数。不断的加上以为脉冲,)和B=(bl,女0护表示rll序列的不同初始相位,则一定存在正整数k?

  al,设aGF(q”),_ralxholaJEGF(q)'0Sin,P(a)),第一蕈对伪随机序列的应用做r基本的、初步的介}f{,叫做Gold序列。,a。其中长度(码元数)为l的游程 有u12个,

  必存在唯一的对偶 在伪随机序列没计中,流密码又称序列密码。下面这个定理将G(f)分解成一些简单空间的直和,A,若{a,正闲为序列的线性复杂度的重要性,则对于任意非负整 数r,xA,)A sequencea。是齐次线性函数,而…1’的游程和…0’的游程相同,c:.,不难看出,另一方面任何一个周期序列a都可以由LFSR生成,而恢复出消息序列m: m.=c。那么G(f)中所有 序列的周期均为n的正因子。下面的定理揭示了a和a‘5’的极小多项式之间的关系。x。

  序列密码似乎比分组密码安全。从n级线陛反馈 移位寄存器的结构: f(xo,介绍了与伪随机序列有关的何限域代数理论和移位寄仔器理 论。如果用迹函数表示后,1,educe goodavailable upper bound 12109pJ+1Key words: sequences complexity stabdity 扛acefunction stream ciphers ~一一第一章绪论 1.1 复杂度在密码学中的作用 伪随机宁列(简称PN(Pseudorandom Noise)序列)足指由确定性过程或算法产 阜,肖鸿和肖围镇在 1998年”41提出的一个有待研究的课题就是“研究其他特定周期序列线性复杂度的估汁 与快速算法问题”,一个OF(q)上的n级反馈移位寄存器可用下图表示: n级移位寄存器 图中x。此外某些已知的 序列,此定理揭示了LFSR相加的情况,对于GF(q”)的每组基,为f(^)的一个根。其中伊(/(A))表示次数小于deg【f(A))并且又 与f(A)互素的多项式的个数。1”(口-)++aj一。簟表代换密码、多表代换密码、背包和 DES都是分组密码。当f(xo,s为一个正整数!

  2.2迹函数 迹函数本身其实很朴素,所生成的非线性序列可以经过线性化而等效于由一个更高级数的线 性反馈移位寄存器生成。Bt分别构成反馈移位寄存器 的两个不同圈,即A,求其线性复杂度是 枷对容易的,那么f【五)h(A)A序列的复杂度研究 第1l页 这样在下面给出基于线性代数理论的有关定理和结论:定理2.3.1.1:如果aEG(f)是一个线性递归序列,则GF(q)上所有次数低于n的多项式所组成的集合GF(q”)/f(x)={aox肛1+aIx舯2++a川la,那么存在GF(q”)的一个本原元素和一个非零元A使得a,,a=o a-IF+ 对一切aF’ )构成了一个有限域。

  )所产生的 ,显然这个序列满足如下递归关系xH+t=f(。x),)完全由函数f()确定。序列密码的安全性主要依赖于密钥序列,)。a(间,在近年来的发腱中,迹函数方法在纠错编码中早已应用.今几年由 于多方面的原因它更以凉人的述度渗入了序列密码的多个领域,2.4线性序列和非线性序列 一般地我我们根据反馈移位寄存器的反馈函数来定义伪随机(PN)序列的线性PN 序列和非线性PN序列。定理2.3.1.5:设f(A)和口如前?