第3章序列密码

主讲人：侯红霞通信与信息工程学院第3章序列密码序列密码也叫做流密码（StreamCipher），它是一种基本的对称密码体制，一直是作为军事和外交场合使用的主要密码技术之一。序列密码的设计思想图3-1序列密码的加密过程种子密钥随机数发生器明文流加密变换密文流密钥流序列密码的主要原理通过随机数发生器产生性能优良的伪随机序列(密钥流)，使用该序列加密信息流(逐比特加密)，得到密文序列。•按照加/解密过程中密钥流工作方式的不同，序列密码一般分为：序列密码（StreamCipher）同步序列密码(SynchronousStreamCipher)自同步序列密码（Self-SynchronousStreamCipher）图3-2同步序列密码加密交换密钥流生成器解密交换安全信道公开信道密钥流生成器种子密钥种子密钥同步序列密码自同步序列密码图3-3自同步序列密码加密交换密钥流生成器解密交换安全信道公开信道密钥流生成器种子密钥种子密钥同步序列密码性质：1.同步性2.无错误传播性3.主动攻击自同步序列密码性质：1.自同步性2.错误传播的有限性3.主动攻击4.明文统计扩散性序列随机性能评价为了度量周期序列的随机性，Golomb对序列的随机性提出了三条假设。这些假设是最早出现的衡量周期伪随机序列的随机性能的必要条件。Golomb定义3.1.1：令,,,210ssss是一个无穷序列，前n项组成的子序列记为：110,,,nnssss。定义3.1.2：序列,,,210ssss称为N周期的，如果对0i，均有Niiss。如果存在正整数N，使得s是N周期的，那么序列s称为周期序列。周期序列的周期定义为使其为N周期序列的最小正整数N。如果s是周期为N的周期序列，那么子序列Ns为s的一个周期。定义3.1.3：令s是一个序列，s的一个游程是指s的包含连续个0或连续个1的子序列，且其前后均为与其不同的符号。0游程称为沟，1游程称为块。定义3.1.4：令,,,210ssss是一个周期为N的周期序列。s的自相关系数)(tC为一个自变量取整数的函数，定义如下：101()(21)(21),01NiitiCtsstNN自相关系数越小，说明序列s的随机性能越好。序列随机性能评价1.在序列的一个周期内，0和1的个数至多相差1。2.在序列的一个周期内，长为1的游程个数占总游程数的，长为2的游程个数占总游程数的，依此类推，长为的游程个数占总游程数的，且在等长的游程中，0游程和1游程各占一半。3.自相关系数是二值的。即对某个整数K，有10,0()(21)(21),11NiitiNtNCtssKtN满足上述三个条件的序列称为伪随机序列。定义3.1.5：Golmob随机性假设包括以下三个条件：21221i21进行随机性检验常用的五个统计测试：1.频率测试2.序列测试3.扑克测试4.游程测试5.自相关测试统计测试令10,nn分别表示s中0和1的个数。频率测试使用的统计量为：22101)(nnnX（3-5）当10n时，该统计量近似服从自由度为1的2分布。频率测试：该测试的目的是确定中0和1的个数是否相等。令10,nn分别表示s中0和1的个数，11100100,,,nnnn分别表示s中子序列00，01，10，11的个数。序列测试使用的统计量为：1)(2)(1421202112102012002nnnnnnnnX（3-6）当21n时，该统计量近似服从自由度为2的2分布。序列测试：该测试的目的是确定的子序列00，01，10，11的个数是否相等。令m是一个满足mmn25的正整数，且令mnk。将序列s分成k个互不相交的部分，每个部分的长度为m，令in为第i种长度为m的序列出现的次数，mi21。扑克测试使用的统计量为：knkXmiim21232（3-7）该统计量近似服从自由度为12m的2分布。扑克测试：该测试的目的是确定每个长度是的序列在中出现的次数是否相等。令k为满足5ie的i的最大整数，令iiGB,分别为s中长度为i的0游程和1游程的个数，ki1。游程测试使用的统计量为：kiiiikiiiieeGeeBX12124)()(（3-8）该统计量近似服从自由度为22k的2分布。游程测试：根据对序列随机性的要求，在长度为的随机序列中，所期待的长度为的0游程（或1游程）的个数为。令d为一个固定的整数，2/1nd。序列s与s发生d个移位后所形成的序列中的不同比特数为10)(dnidiissdA，其中表示异或操作。自相关测试的统计量为：dndndAX2)(25（3-9）当10dn时，该统计量近似服从)1,0(N分布。自相关测试：该测试的目的是检验序列与其发生移位后所形成的序列之间的相关性。•例3.1对于长度为比特的随机序列：1110001100010001010011101111001001001001111000110001000101001110111100100100100111100011000100010100111011110010010010011110001100010001010011101111001001001001160ns（1）频率测试：76,8410nn，所以：4.0)(2101nnnX（2）序列测试：35,40,40,4411100100nnnn，所以：6252.01)(2)(1421202112102012002nnnnnnnnX6415.922123knkXmiim（3）扑克测试：–长度为3的片断000，001，010，011，100，101，110，111出现的次数分别为：5，10，6，4，12，3，6，77913.31)()(12124kiiiikiiiieeGeeBX(4)游程测试：e1=20.25，e2=10.0625,e3=5,k=3长度为1，2，3的1游程的个数分别为25，4，5，长度为1，2，3的0游程的个数分别为8，20，12，所以：因此通过以上计算结果可知，序列通过了频率测试、序列测试和扑克测试，但是没有通过游程测试和自相关测试。8933.32)(25dndndAX(5)自相关测试：–取d=8，则A(d)=100，所以：–对于显著性水平a=0.05，相应的统计量的阈值分别为3.8415，5.9915，14.0671，9.4877，1.96。在设计密钥流生成方法时，不仅要考虑安全性要求，还要考虑以下两个因素：生成密钥流的密钥应该易于分配和管理。密钥流生成方法应该易于快速实现。k反馈移位寄存器（FSR:FeedbackShiftRegister）。一个反馈移位寄存器由两部分组成：反馈移位寄存器移位寄存器和反馈函数线性反馈移位寄存器线性反馈移位寄存器（LFSR:LinearFeedbackShiftRegister），是许多密钥流生成器的基本器件。LFSR的优点有：非常适合于硬件实现；可以产生大周期的序列；产生的序列具有良好的统计特性；结构上具有一定的特点，便于利用代数方法对其进行分析。定义3.2.1：一个长度为L的线性反馈移位寄存器（LFSR）由1,,1,0L共L个级（或延迟单元）和一个时钟构成，每个级都有1比特的输入和1比特的输出，并且可以存储1比特字符；时钟用于控制数据的移动。每个时间单位内执行下述操作：（1）输出0级所存储的字符，作为输出序列的一部分。（2）对每个i，11Li，将第i级的存储内容移入第1i级。（3）第1L级中存储的新元素称为反馈比特js，它由1,,1,0L级中的一个固定的子集合的内容进行模2相加而得到。图3-4长度为L的线性反馈移位寄存器结构L-1级C1L-2级C21级CL-10级CL…输出……“与”运算Ci为0或1定义3.2.2：图3-4所示的线性反馈移位寄存器可以记为：)(,DCL，其中][1)(2221DZDcDcDcDCLL为联结多项式。若)(DC的次数为L（即1Lc），则称相应的线性移位寄存器LFSR为非奇异的。对于每一个i，10Li，若第i级的初始存储值为}1,0{is，则称],,,,[0121ssssLL为线性移位寄存器LFSR的初始状态。如果已知线性反馈移位寄存器LFSR的结构如图3-4所示，相应的初始状态为：],,,,[0121ssssLL，那么输出序列,,,210ssss可以通过以下递推公式惟一确定：LjscscscsLjLjjj,2mod)(2211（3-10）例3.2线性移位寄存器LFSR41,4DDD=D3D03级3D2级2D1D0D1级0级输出tD3D2D1D0001100110D3D2D1D0+0D30100112100130100401005000161000711008111091111100111111011120101131010141101150110输出序列s=0.1.1.0.0.1.0.0.0.1.1.1.1.…周期为150011+0D31D3=D0D3+LFSR输出序列的周期与随机性线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。L级线性反馈移位寄存器最多有2L个不同的状态。若其初始状态为0，则其后续状态恒为0；若其初始状态不为0，则其后续状态不会为0。因此，L级线性反馈移位寄存器的输出序列的周期不大于21L（不考虑0状态）。定理3.1：线性反馈移位寄存器LFSR)(,DCL的每一个输出序列是周期的，当且仅当联结多项式)(DC的次数为L。定理3.2：对于线性反馈移位寄存器LFSR)(,DCL，设][)(2DZDC是一个L次的联结多项式。则有以下结论：（1）若)(DC在][2DZ上是不可约的，那么非奇异的LFSR)(,DCL的12L个非零状态中的每一个都可以产生一个周期为N的输出序列，其中N为满足条件：)(DC在][2DZ中能够整除ND1的最小正整数。（2）若)(DC为本原多项式，那么非奇异的LFSR)(,DCL的12L个非零状态中的每一个均能产生具有最大可能周期为12L的输出序列。定义3.2.3：若][)(2DZDC是一个L次的本原多项式，则)(,DCL称为最大长度LFSR。最大长度LFSR在非零状态下的输出称为m序列。m序列有以下性质：具有固定长度且长度至多为L的模型分布几乎是均匀的m序列满足Golomb随机性假设基于LFSR的生成器基于LFSR的序列密码的基本结构明文密文输出基于LFSR的密钥流生成器应该具备以下性质：大周期；大线性复杂度；较好的统计特性。要达到以上要求，在设计线性反馈移位寄存器LFSR时应该考虑以下因素。为了保证密钥流生成器产生的输出序列具有大周期，设计相应的LFSR时应该始终选择最大长度的LFSR应该从域Z2[D]上所有次数为L的本原多项式所组成的集合中随机均匀地选择联结多项式。在实际设计线性反馈移位寄存器时，通常使用秘密联结多项式的形式。密钥流生成器的设计方法•首先，用一个或多个线性反馈移位寄存器，通常要求LFSR具有不同的长度和不同的联结多项式。•密钥流生成器的密钥是LFSR的初始状态，每一次取LFSR中的一位，然后将LFSR移位一次（也称为一个时钟）。•密钥流生成器的输出位是LFSR中一些位的函数，该函数一般要求是非线性的，称为组合函数，相应的整个密钥流生成器也称为一个组合生成器。主要的生成器有：（1）Geffe生成器（2）Jennings生成器（3）J－K触发器（4）普勒斯（Pless）体制Geffe生成器Geffe生成器使用了三个线性反馈移位寄存器它们以非线性的方式组合而成其中两个LFSR作为复合器的输入第三个LFSR用来控制复合器的输出。Geffe生成器的基本结构LFSR2LFSR3