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

序列密码中密钥流生成器的安全性研究与分析
孙菁，傅德胜
南京信息工程大学计算机与软件学院,南京210044

摘要：序列密码设计的核心在于密钥流生成器的设计，本文分析了基于线性反馈移位寄存器的序列密码密
钥流生成器的工作机制，在研究Geffe和收缩式非线性组合生成器模型的重构条件之基础上，给出了一般
情况下非线性组合生成器整体的重构条件。本文的工作对构建安全序列密码体制有很好的指导意义。

关键词：序列密码，LFSR，组合生成器
中图分类号TN918
Researchandanalysisonthesecurityofkeygenerator
SUNJing,FUDe-sheng
Schoolofcomputerandsoftware,Nanjinguniversityofinformationscienceandtechnology,
Nanjing210044
Abstract:Designofkeygeneratoristhecoreprocessinstreamcipher.Thispaperbasedontheresearchof
streamcipherandthereconstructionconditionofGeffeandshrinkinggenerator,proposedthereconstruction
conditionforgeneralnonlinearcombininggenerator,whichwouldgiveguidingsignificancetothedesignforthe
securestreamciphersystem.
KeyWords:streamcipher;LFSR;combininggenerator

0引言

序列密码密钥流生成器有多种结构，多数是用一个或多个具有最大周期的线性反馈移
位寄存器（Linear_feedback_shift,LFSR）作驱动器来产生一系列状态序列，使之周期最长、
统计特性良好；然后这些状态序列经过一个非线性组合函数f后得到高线性复杂度的密钥序

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

1线性反馈移位寄存器

1.1LFSR的工作机制

线性反馈移位寄存器由n个存储器与一个线性反馈函数组成，移位寄存器每次向右移动
一位，新的最左边的位根据反馈函数计算得到，移位寄存器输出的位是最低位[5]。反馈函
数是寄存器中某些位的线性函数。每一存储器称为LFSR的一级（或抽头），这些级的内容
构成该LFSR的状态，每一状态对应于GF（2）上的一个n维向量，共有2n种可能的状态。
理论上n级LFSR在重复之前最多能产生2n-1位长的状态（除去全零状态），但只有具有一
定抽头序列LFSR才能循环的通过所有2n-1位长的状态，这种序列称为m序列。
为了使LFSR有最大周期，抽头必须符合一定规则或者LFSR的特征多项式必须是本原

(2n1)
多项式，不同级数下本原多项式系数见下表1。N次本原多项式的个数(n)，
n

其中为欧拉函数。已经证明，对于任意的正整数n，至少存在一个n次本原多项式，所以

对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。m序列有密码学很
多优良特性，如平衡性、移位可加性，它是最常采用的扩谱码序列，也是攻击者们致力于分

析的序列。

表1本原多项式系数表

n本原多项式系数n本原多项式系数

201C6873253FADF21

3074B5F95935892EDAC73

4015A02FC75874527D99F781D27

5073E876C9DCD9755BEC81BD6CE836B

601FB7B391826A7E396521A762CC0F6015D57

704E055031A9E62660FF75824EC073FB02B82A49F

8016428CF31D321B4DB6B1B853189E29C9F12E75B82CDD5

1.2LFSR内部特性

定理1：GF（p）上的n级LFSR产生的m序列z具有以下性质[5]：

（1）z最小周期为pn-1，线性复杂度为n。

（2）若LFSR的初始状态为全零，则输出z为全零序列。