序列密码中密钥流生成器的安全性研究与分析.pdf

《序列密码中密钥流生成器的安全性研究与分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、序列密码中密钥流生成器的安全性研究与分析孙菁，傅德胜南京信息工程大学计算机与软件学院,南京210044摘要：序列密码设计的核心在于密钥流生成器的设计，本文分析了基于线性反馈移位寄存器的序列密码密钥流生成器的工作机制，在研究Geffe和收缩式非线性组合生成器模型的重构条件之基础上，给出了一般情况下非线性组合生成器整体的重构条件。本文的工作对构建安全序列密码体制有很好的指导意义。关键词：序列密码，LFSR，组合生成器中图分类号TN918ResearchandanalysisonthesecurityofkeygeneratorSUNJing,FUDe-shengSchoolofco

2、mputerandsoftware,Nanjinguniversityofinformationscienceandtechnology,Nanjing210044Abstract:Designofkeygeneratoristhecoreprocessinstreamcipher.ThispaperbasedontheresearchofstreamcipherandthereconstructionconditionofGeffeandshrinkinggenerator,proposedthereconstructionconditionforgeneralnonline

3、arcombininggenerator,whichwouldgiveguidingsignificancetothedesignforthesecurestreamciphersystem.KeyWords:streamcipher;LFSR;combininggenerator0引言序列密码密钥流生成器有多种结构，多数是用一个或多个具有最大周期的线性反馈移位寄存器（Linear_feedback_shift,LFSR）作驱动器来产生一系列状态序列，使之周期最长、统计特性良好；然后这些状态序列经过一个非线性组合函数f后得到高线性复杂度的密钥序列{ki}i≥0。自从线性移位寄存

4、器的有效综合算法提出后[1],，人们对单个LFSR的复杂度及相关攻击进行了大量研究，包括序列的周期，线性复杂度等代数特性和相关函数，0-1分布及游程分布等统计特性[2],[3],[4]，但是这些研究只反映了单个LFSR的安全状态，并没有涉及整个组合生成器的安全策略。本文主要研究密钥流生成器在多个LFSR下的整体安全状态，在研究Geffe和收缩钟控式非线性组合生成器模型的重构条件之基础上，给出了一般情况下非线性组合生成器整体的重构条件。1线性反馈移位寄存器1.1LFSR的工作机制线性反馈移位寄存器由n个存储器与一个线性反馈函数组成，移位寄存器每次向右移动一位，新的最左边的位根据反

5、馈函数计算得到，移位寄存器输出的位是最低位[5]。反馈函数是寄存器中某些位的线性函数。每一存储器称为LFSR的一级（或抽头），这些级的内容n构成该LFSR的状态，每一状态对应于GF（2）上的一个n维向量，共有2种可能的状态。n理论上n级LFSR在重复之前最多能产生2-1位长的状态（除去全零状态），但只有具有一n定抽头序列LFSR才能循环的通过所有2-1位长的状态，这种序列称为m序列。为了使LFSR有最大周期，抽头必须符合一定规则或者LFSR的特征多项式必须是本原n(21)多项式，不同级数下本原多项式系数见下表1。N次本原多项式的个数(n)，n其中为欧拉函数。已经证明，

6、对于任意的正整数n，至少存在一个n次本原多项式，所以对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。m序列有密码学很多优良特性，如平衡性、移位可加性，它是最常采用的扩谱码序列，也是攻击者们致力于分析的序列。表1本原多项式系数表n本原多项式系数n本原多项式系数201C6873253FADF213074B5F95935892EDAC734015A02FC75874527D99F781D275073E876C9DCD9755BEC81BD6CE836B601FB7B391826A7E396521A762CC0F6015D57704E055031A9E62660FF7

7、5824EC073FB02B82A49F8016428CF31D321B4DB6B1B853189E29C9F12E75B82CDD51.2LFSR内部特性[5]定理1：GF（p）上的n级LFSR产生的m序列z具有以下性质：n（1）z最小周期为p-1，线性复杂度为n。（2）若LFSR的初始状态为全零，则输出z为全零序列。（3）若LFSR的初始状态为全1，则输出z与输出位的奇偶性相关。nn（4）对任意XGF(p),X0,在z的一个周期内X出现p次，0出现p-1次。（5）如果zj