1、3.1 序列密码的基本原理 3.2 反馈移位寄存器 3.3 基于LFSR的密钥流生成器 3.4 非线性反馈移位寄存器 习题 3.1 序列密码的基本原理序列密码的基本原理3.1.1 序列密码的设计思想序列密码的设计思想序列密码每次只对明文中的单个位(有时对字节)进行运算(加密变换)，加密过程所需的密钥流由种子密钥通过密钥流生成器产生。随着数字电子技术的发展，密钥流可以方便地利用以移位寄存器为基础的电路来产生，这促使线性和非线性移位寄存器理论迅速发展，加上有效的数学工具，从而使得序列密码理论迅速发展。序列密码的主要原理是通过随机数发生器产生性能优良的伪随机序列(密钥流)，使用该序列加密信息流(逐比
2、特加密)，得到密文序列。由于每一个明文都对应一个随机的加密密钥，因此序列密码在理论上属于无条件安全的密码体制。序列密码的基本加密过程如图3-1所示。图3-1 序列密码的加密过程按照加/解密过程中密钥流工作方式的不同，序列密码一般分为同步序列密码和自同步序列密码两种。1.同步序列密码同步序列密码在同步序列密码中，密钥流的产生完全独立于消息流(明文流或密文)，如图3-2所示。在这种工作方式下，如果传输过程中丢失一个密文字符，发送方和接收方就必须使他们的密钥生成器重新同步，这样才能正确地加/解密后续的序列，否则加/解密将失败。图3-2 同步序列密码图3-2的操作过程可以用相应的函数描述如下：(3-1
3、)其中，i是密钥流生成器的内部状态;F是状态转移函数;G是密钥流ki的产生函数;E是同步序列密码的加密变换;D是同步序列密码的解密变换。由于同步序列密码各操作位之间相互独立，因此应用这种方式进行加/解密时无错误传播，当操作过程中产生一位错误时只会影响一位，不影响后续位，这是同步序列密码的一个重要特点。),(),(),(),(1iiiiiiiiiickDmmkEckGkkF同步序列密码具有以下性质：(1)同步性。在同步序列密码中，消息的发送方和接受方必须同步才能做到正确地解密，即通信双方使用相同的密钥，并用其对同一位置进行操作。一旦由于密文字符在传输过程中被插入或删除而破坏了这种同步性，那么解密
4、过程将失败。这时只有借助于其他附加的技术来重建同步，解密过程才能够继续进行。重建同步的技术包括：重新初始化；在密文序列的规则间隔中设置特殊记号；当明文消息序列包含足够的冗余度时，也可以尝试密钥流所有可能的偏移。(2)无错误传播性。密文字符在传输过程中被修改(未被删除)并不影响其他密文字符的解密。(3)主动攻击。一个主动攻击者对密文字符进行的插入、删除或重放操作都会立即破坏系统的同步性，从而可能被解密器检测出来。同时，主动攻击者可能会有选择地对密文字符进行改动，并准确地知道这些改动对明文的影响。所以必须采用其他的附加技术保证被加密数据的完整性。2.自同步序列密码自同步序列密码与同步序列密码相比，
5、自同步序列密码是一种有记忆变换的密码，如图3-3所示。每一个密钥字符是由前面n个密文字符参与运算推导出来的，其中n为定值。即，如果在传输过程中丢失或更改了一个字符，则这一错误就要向前传播n个字符。因此，自同步序列密码有错误传播现象。不过，在收到n个正确的密文字符以后，密码自身会实现重新同步。图3-3的操作过程可以用相应的函数描述如下：(3-2)其中，i是密钥流生成器的内部状态;ci是密文;F是状态转移函数;G是密钥流ki的产生函数;E是同步序列密码的加密变换;D是同步序列密码的解密变换。),(),(),(),(111iiiiiiiiniiiiickDmmkEckGkkcccF图3-3 自同步序
6、列密码自同步序列密码具有以下性质：(1)自同步性。由于解密过程仅仅依赖于前面固定个数的密文字符，因此当密文字符被插入或删除时，密码的自同步性就会体现出来。这种密码在同步性遭到破坏时，可以自动重建正确的解密过程，而且仅有固定数量的明文字符不可恢复。(2)错误传播的有限性。假设一个自同步序列密码的状态依赖于n个前面的密文字符。在密文序列传输的过程中，当一个比特的密文字符被改动(或被插入、删除)时，那么至多会有n个比特随后的密文字符解密出错，然后会恢复正确的解密过程。(3)主动攻击。主动攻击者对密文字符的任何改动都会引发一些密文字符的解密出错，因此增加了被解密器检测出的可能性。同时，这种密码在检测主
7、动攻击者发起的对密文字符的插入、删除、重放等攻击时更加困难，所以必须采取附加的技术来保证被加密数据的完整性。(4)明文统计扩散性。每个明文字符都会影响其后的整个密文，即明文的统计学特征被扩散到了密文中。因此，自同步序列密码对利用明文的冗余度而发起的攻击有较强的抗攻击能力。在自同步序列密码系统中，密文流参与了密钥流的生成，这使得对密钥流的分析非常复杂，从而导致了对自同步序列密码进行系统的理论分析非常困难。因此，目前应用较多的流密码是自同步序列密码。序列密码系统在使用时的一个关键是要有对应的随机序列，而现实中通过随机数发生器产生的序列只能是一个伪随机序列，因此需要对生成序列的随机性进行评价。下节将
8、给出判断生成的伪随机序列具有随机性的评价指标。3.1.2 序列随机性能评价序列随机性能评价为了度量周期序列的随机性，Golomb对序列的随机性提出了三条假设。这些假设是最早出现的衡量周期伪随机序列随机性能的必要条件。当然，这些条件还不能够作为将周期序列看做随机序列的充分条件。定义定义3.1.1 令s=s0，s1，s2，是一个无穷序列，前n项组成的子序列记为sn=s0，s1，sn-1。定义定义3.1.2 如果对i0，均有si=si+N，那么序列s=s0，s1，s2，称为N周期的。如果存在正整数N，使得s是N周期的，那么序列s称为周期序列。周期序列的周期定义为使其为N周期序列的最小正整数N。如果s
9、是周期为N的周期序列，那么子序列sN为s的一个周期。定义定义3.1.3 令s是一个序列，s的一个游程是指s包含连续个0或连续个1的子序列，且其前后均为与其不同的符号。0游程称为沟，1游程称为块。定义定义3.1.4 令s=s0，s1，s2，是一个周期为N的周期序列。s的自相关系数C(t)为一个自变量取整数的函数，定义如下：(3-3)自相关系数是用来衡量序列s和s的t个位置的移位之间相似性的量，自相关系数越小，说明序列s的随机性能越好。101()(21)(21),01 Nii tiC tsstNN 定义定义3.1.5 Golmob随机性假设包括以下三个条件：(1)在序列的一个周期内，0和1的个数至
10、多相差1。(2)在序列的一个周期内，长为1的游程个数占总游程数的1/2，长为2的游程个数占总游程数的1/22，依此类推，长为i的游程个数占总游程数的1/2i，且在等长的游程中，0游程和1游程各占一半。(3)自相关系数是二值的，即对某个整数K，有 (3-4)满足上述三个条件的序列称为伪随机序列。其中条件(1)说明序列s中0和1出现的概率基本相等；条件(2)说明在已知位置n前若干位置上的值的前提下，在第n个位置上出现0和1的概率是相等的；条件(3)说明如果将si与si+t进行比较，无法得到关于序列s的实质性信息(如周期等)。10,0()(21)(21),11 Nii tiN tN C tssKtN
11、 接下来介绍对长度是n的二进制序列s=s0，s1，sn-1进行随机性检验常用的五个统计测试，它们是判断二进制序列s是否具有随机性的一些统计量。(1)频率测试。该测试的目的是确定s中0和1的个数是否相等。令n0、n1分别表示s中0和1的个数。频率测试使用的统计量为 (3-5)当n10时，该统计量近似服从自由度为1的2分布。22101)(nnnX(2)序列测试。该测试的目的是确定s的子序列00，01，10，11的个数是否相等。令n0、n1分别表示s中0和1的个数，n00、n01、n10、n11分别表示s中子序列00、01、10、11的个数。序列测试使用的统计量为 (3-6)当n21时，该统计量近似
12、服从自由度为2的2分布。1)(2)(1421202112102012002nnnnnnnnX(3)扑克测试。令m是一个满足n/m52m的正整数，且令k=n/m。将序列s分成k个互不相交的部分，每个部分的长度为m，令ni为第i种长度为m的序列出现的次数，1i2m。该测试的目的是确定每个长度为m的序列在s中出现的次数是否相等。扑克测试使用的统计量为 (3-7)该统计量近似服从自由度为2m-1的2分布。knkXmiim21232(4)游程测试。根据对序列随机性的要求，在长度为n的随机序列中，所期待的长度为i的0游程(或1游程)的个数为ei=(n-i+3)/2i+2。令k为满足ei5的i的最大整数，令
13、Bi、Gi分别为s中长度为i的0游程和1游程的个数，1ik。游程测试使用的统计量为 (3-8)该统计量近似服从自由度为2k-2的2分布。kiiiikiiiieeGeeBX12124)()(5)自相关测试。该测试的目的是检验序列s与其发生移位后所形成的序列之间的相关性。令d为一个固定的整数，1dn/2。序列s与s发生d个移位后所形成的序列中的不同比特数为，其中表示异或操作。自相关测试使用的统计量为 (3-9)当n-d10时，该统计量近似服从N(0，1)分布。10)(dnidiissdAdndndAX2)(25例例3.1 对长度为n=160比特的随机序列s：11100 01100 01000 10
14、100 11101 11100 10010 01001 11100 01100 01000 10100 11101 11100 10010 01001 11100 01100 01000 10100 11101 11100 10010 01001 11100 01100 01000 10100 11101 11100 10010 01001分别进行以下随机性测试：(1)频率测试。n0=84，n1=76，所以 (2)序列测试。n00=44，n01=40，n10=40，n11=35，所以4.0)(2101nnnX6252.01)(2)(1421202112102012002nnnnnnnnX(3)
15、扑克测试。m=3，k=53。长度为3的片断000、001、010、011、100、101、110、111出现的次数分别为5、10、6、4、12、3、6、7，所以 (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，所以6415.922123knkXmiim7913.31)()(12124kiiiikiiiieeGeeBX(5)自相关测试。取d=8，则A(d)=100，所以 对于显著性水平=0.05，相应的统计量X1、X2、X3、X4、X5的阈值分别为3.8415、5.99
16、15、14.0671、9.4877、1.96。因此通过以上计算结果可知，序列s通过了频率测试、序列测试和扑克测试，但是没有通过游程测试和自相关测试。8933.32)(25dndndAX通过对序列随机性能评价指标的介绍可知，序列密码的安全性要求越高，相应的密钥流的随机性要求就越高。因此，在设计密钥流生成方法时，不仅要考虑安全性要求，还要考虑以下两个因素：(1)生成密钥流的密钥k应该易于分配和管理。(2)密钥流生成方法应该易于快速实现。基于以上分析，本节介绍常用来生成密钥流的密钥流生成器的基本部件反馈移位寄存器(Feedback Shift Register，FSR)。3.2 反馈移位寄存器反馈移
17、位寄存器一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数。移位寄存器是一个位序列，它的长度用位表示，如果移位寄存器的长度是n位，则称为n位移位寄存器。每次运算的结果实际只改变序列中的一个值，其中移位寄存器中除最右端的位以外，其余所有位向右移一位，新的最左端位的值根据寄存器中其他位的值计算得到。移位寄存器的输出值常常是序列中的最低有效位。移位寄存器的周期是指输出序列从开始到重复时的长度。3.2.1 线性反馈移位寄存器线性反馈移位寄存器反馈移位寄存器，特别是线性反馈移位寄存器(Linear Feedback Shift Register，LFSR)，是许多密钥流生成器的基本器件。目前出现的许多
18、密钥流生成器都使用线性反馈移位寄存器，其优点如下：(1)非常适合于硬件实现；(2)可以产生大周期的序列；(3)产生的序列具有良好的统计特性；(4)在结构上具有一定的特点，便于利用代数方法对其进行分析。定义定义3.2.1 一个长度为L的线性反馈移位寄存器由0，1，L-1共L个级(或延迟单元)和一个时钟构成，每个级都有1比特的输入和1比特的输出，并且可以存储1比特字符；时钟用于控制数据的移动。每个时间单位内执行下述操作：(1)输出0级所存储的字符，作为输出序列的一部分。(2)对每个i，1iL-1，将第i级的存储内容移入第i-1级。(3)第L-1级中存储的新元素称为反馈比特sj，它由0，1，L-1级
19、中一个固定子集合的内容进行模2相加而得到。LFSR的结构如图3-4所示。其中每个ci为0或1，图中闭合的半圆表示“与”运算，反馈比特sj由那些i级的内容进行模2求和运算而得到，其中0iL-1且cL-i=1。图3-4 长度为L的线性反馈移位寄存器结构定义定义3.2.2 图3-4所示的线性反馈移位寄存器可以记为L，C(D)，其中C(D)=1+c1D+c2D2+cLDLZ2D为联结多项式。若C(D)的次数为L(即cL=1)，则称相应的LFSR为非奇异的。对于每一个i，0iL-1，若第i级的初始存储值为si0，1，则称sL-1，sL-2，s1，s0为LFSR的初始状态。如果已知线性反馈移位寄存器的结构
20、如图3-4所示，相应的初始状态为sL-1，sL-2，s1，s0，那么LFSR的输出序列s=s0，s1，s2，可以通过以下递推公式惟一确定：sj=(c1sj-1+c2sj-2+cLsj-L)mod 2,jL (3-10)例例3.2 线性反馈移位寄存器4，1+D+D4的结构如图3-5所示。图3-5 LFSR4，1+D+D4当LFSR的初始状态为0，0，0，0时，相应的输出序列为0序列。当LFSR的初始状态为0，1，1，0时，对应每一个时刻t相应的D3、D2、D1、D0各级中所存储的二进制数见表3-1。该线性反馈移位寄存器LFSR的输出序列为s=0，1，1，0，0，1，0，0，0，1，1，1，1,0
21、，1，该输出序列的周期为15。3.2.2 LFSR输出序列的周期与随机性输出序列的周期与随机性 关于由线性反馈移位寄存器产生序列的周期性有以下结论。定理定理3.1 线性反馈移位寄存器L，C(D)的每一个输出序列是周期的，当且仅当联结多项式C(D)的次数为L。在线性反馈移位寄存器L，C(D)是奇异的(即C(D)的次数小于L)情况下，并不是所有的LFSRL，C(D)输出序列都有周期。但是在忽略掉输出序列中开始的固定有限项后，得到的新序列是周期的。定理定理3.2 对于线性反馈移位寄存器L，C(D)，设C(D)Z2D是一个L次的联结多项式，则有以下结论：(1)若C(D)在Z2D上是不可约的，那么非奇异
22、的LFSRL，C(D)的2L-1个非零状态中的每一个都可以产生一个周期为N的输出序列，其中N为满足条件C(D)在Z2D中能够整除1+DN的最小正整数。(2)若C(D)为本原多项式，那么非奇异的LFSRL，C(D)的2L-1个非零状态中的每一个均能产生具有最大可能周期为2L-1的输出序列。根据以上结论，我们给出m序列的定义。定义定义3.2.3 若C(D)Z2D是一个L次的本原多项式，则L，C(D)称为最大长度LFSR。最大长度LFSR在非零状态下的输出称为m序列。根据m序列的定义，例3.2中C(D)=1+D+D4为Z2D中的一个本原多项式，所以LFSR4，1+D+D4为最大长度LFSR，相应的L
23、FSR4，1+D+D4的输出序列是一个m序列，其最大可能周期为N=24-1=15。关于m序列有以下性质：(1)设k为整数，1kL，且为s的长度为2L+k-2的任意子序列。那么 的每一个长度为k的非零子序列恰好出现2L-k次，而且 的长度为k的零子序列恰好出现2L-k-1次。也就是说，具有固定长度且长度至多为L的模型分布几乎是均匀的。sss(2)m序列满足Golomb随机性假设。下面对性质(2)进行分析。由于线性反馈移位寄存器当初始状态相同时，输出序列也是相同的，因此LFSR在产生m序列的过程中必须遍历2L-1个非0状态的每一个，然后才会出现重复。这2L-1个状态在s1位有2L-1个是1，其余的
24、2L-1个是0。所以满足Golomb随机性假设的第一个条件。由于线性反馈移位寄存器LFSR中不可能出现全0状态，因此输出序列不会出现0的L游程。而且必然有一个1的L游程，但不可能有长度大于L的1游程。因为如果出现一个1的L+1游程，必然会有两个全是1的状态相邻，根据LFSR的设计原理，这是不可能的。所以可以知道值为1、长度为L的游程必然出现在以下的情况中：0,1,1,1,1,0 位L当以上的L+2位通过移位寄存器时，会依次产生以下状态：由于0,1,1,1,1和1,1,1,1,0这两个状态只能各出现一次，因此不会有其他的1的L-1游程。同理，输出序列中会出现0的L-1游程：产生1,0,0,0,0
25、和0,0,0,0,1两个状态。0,11,1,1,1,1,1,1,1,11,1,1,1,0 位位位LLL1,10,0,0,0,1 位L当L=2时，以上分析过程已经验证了所有的情况。当L2时，设r为不大于L-2的任意一个正整数，则任何1的r游程就意味着输出序列中存在序列0,1,1,1,1,0 位r为了计算1的r游程的数目，只要计算左边的r+2个比特位的状态数目就可以了。因为任一个1的r游程总会在通过移位寄存器时处在当前的位置。其余的L-r-2比特位可以是由0和1构成的任何状态，所以1的r游程的数目是2L-r-2。于是在每一个周期中出现1的游程的数目为2212221LLrrL同样，0游程的数目也是2
26、L-2。因此m序列满足Golomb随机性假设的第二个条件。根据下面的换行定理，m序列满足Golomb随机性假设的第三个条件。换行定理：周期为2L-1的m序列，其异相自相关函数等于。以上结论表明，应用线性反馈移位寄存器产生的m序列具有良好的随机性能。121L3.3 基于基于LFSR的密钥流生成器的密钥流生成器线性反馈移位寄存器被广泛应用于序列密码的密钥流生成器中。线性反馈移位寄存器产生的序列具有较好的统计特性，非常适合用硬件来实现。此外线性反馈移位寄存器已经被人们使用代数技术分析过，因此可靠性较高。基于LFSR的序列密码的基本结构如图3-6 所示。图3-6 基于LFSR的序列密码的基本结构如果线
27、性反馈移位寄存器产生的是m序列，则算法的密钥取决于LFSR的初始状态和图3-4中参数c1，c2，cL的取值情况。鉴于LFSR对应的特征多项式是本原多项式，而L次的本原多项式共有(L)个，LFSR的非零初始状态共有2L-1个，所以应用LFSR产生m序列的算法密钥共有(L)(2L-1)个。对于以上所有可能的密钥，基于LFSR的密钥流生成器应该具备以下性质：(1)大周期；(2)大线性复杂度；(3)较好的统计特性。以上性质是密钥流生成器在密码学中被认为是计算安全的必要条件。要达到以上要求，在设计LFSR时应该考虑以下因素。为了保证密钥流生成器产生的输出序列具有大周期，设计相应的LFSR时应该始终选择最
28、大长度的LFSR。也就是说，设计的LFSR应该具有形式L，C(D)，其中C(D)Z2D是一个L次的本原多项式。由于基于线性反馈移位寄存器的密钥流生成器中的LFSR可能存在已知的或者秘密的联结多项式。对于LFSR已知的联结多项式，密钥通常由LFSR的初始内容构成。对于秘密的联结多项式，密钥流生成器的密钥通常由初始内容和联结多项式两者共同构成。所以对于长度为L而且具有秘密联结多项式的LFSR，应该从域Z2D上所有次数为L的本原多项式所组成的集合中随机均匀地选择联结多项式。在实际设计LFSR时，通常使用秘密联结多项式的形式。因为这种设计能够更好地抵御使用预计算来分析特殊联结多项式的攻击，而且采用秘密
29、联结多项式设计LFSR产生的输出序列也更能经得起统计分析。虽然采用秘密联结多项式的形式设计的LFSR需要额外的电路来完成硬件实现，但是由于这种形式的LFSR具有更好的安全性，因此以上缺点可以通过选择更短的线性反馈移位寄存器来进行弥补。最后，在设计线性反馈移位寄存器时，为了便于实现，可以选择稀疏的LFSR，也就是说，采用的联结多项式中只有很少一部分系数是非零的。这样就只需要在LFSR的各种状态之间构造很少的联结多项式来计算反馈比特。当然，某些使用稀疏的联结多项式设计的LFSR可能会受到一些特殊的攻击。以上讨论了设计基于LFSR的密钥流发生器时，设计LFSR应该考虑的因素。接下来给出基于LFSR的
30、密钥流生成器的设计方法。首先，用一个或多个LFSR，通常要求LFSR具有不同的长度和不同的联结多项式。对于采用两个LFSR的密钥流生成器，当两个LFSR的长度互素，而且它们的联结多项式是本原多项式时，密钥流生成器得到的输出序列将具有最大的长度。密钥流生成器的密钥是LFSR的初始状态，每一次取LFSR中的一位，然后将LFSR移位一次(也称为一个时钟)。密钥流生成器的输出位是LFSR中一些位的函数，该函数一般要求是非线性的，称为组合函数，相应的整个密钥流生成器也称为一个组合生成器。(如果密钥流生成器的输出位是单个LFSR的函数，则相应密钥流生成器称为过滤生成器)。下面通过介绍几种基本的组合生成器，
31、来进一步说明基于LFSR的密钥流生成器的工作原理。1.Geffe生成器生成器Geffe生成器使用了三个LFSR，它们以非线性的方式组合而成，其中两个LFSR作为复合器的输入，第三个LFSR用来控制复合器的输出。Geffe生成器的基本结构如图3-7所示。图3-7 Geffe生成器的基本结构设s1、s2、s3分别是Geffe生成器中三个LFSR的输出位，则相应的Geffe生成器的输出表示为 如果已知三个LFSR的长度分别为n1、n2、n3，那么相应的Geffe生成器的线性复杂性为(n1+1)n2+n1n3该Geffe生成器的周期是已知的三个LFSR周期的最小公倍数。所以当三个LFSR的本原联结多项
32、式的次数互素时，相应的Geffe生成器的周期就是三个LFSR的周期的乘积。Geffe生成器在密码学意义上是不安全的，因为第一个和第三个LFSR的状态信息会在Geffe生成器的输出序列中表现出来。)()(3121ssssk2.Jennings生成器生成器Jennings生成器使用了两个LFSR，通过一个复合器将两个LFSR组合起来，其基本结构如图3-8所示。在Jennings生成器中，LFSR1控制的复合器为每一个输出位选择LFSR 2的一位，用一个函数将LFSR 2的输出映射到复合器的输入。密钥流生成器的密钥是两个线性反馈移位寄存器和映射函数的初始状态。图3-8 Jennings生成器的基本结
33、构图3-9 JK触发器的基本结构3.JK触发器触发器JK触发器也使用了两个LFSR，其中LFSR 1是一个m级的线性反馈移位寄存器，LFSR 2是一个n级的线性反馈移位寄存器。JK触发器的基本结构如图3-9所示。图3-9 JK触发器的基本结构JK触发器的工作表如表3-2所示。设JK触发器中LFSR 1的输出序列为a1，a2，周期为m，LFSR 2的输出序列为b1，b2，周期为n，其中m与n互素，JK触发器的输出序列为c1，c2，。由于JK触发器的输出序列中的位一般都与其前一位有关，通常令c0=0，因此JK触发器的输出序列可以通过以下递推公式计算：cn=(an+bn+1)cn-1+an)mod
34、2JK触发器产生的输出序列虽然具有较好的随机性，但当知道输出序列的部分值时，通过一定的方法可以给出以上递推方程的部分解。例如，知道JK触发器输出序列中cn和cn+1的值时，通过递推关系有：(1)如果cn=cn+1=0，则可知an+1=0;(2)如果cn=0，cn+1=1，则可知an+1=1;(3)如果cn=1，cn+1=0，则可知bn+1=1;(4)如果cn=cn+1=1，则可知bn+1=0。上述例子说明通过cn和cn+1的值可以计算出an+1和bn+1的值，所以JK触发器密钥流生成机制也存在安全问题。上面给出了常见的基于LFSR的序列密码密钥流生成器的设计方法。由于LFSR是从初始状态通过线
35、性递推关系来产生密钥流的，因此该密钥流生成方法容易受到已知明文攻击。假设Oscar已经有了明文消息序列x1，x2，xn 和与其对应的密文消息序列y1，y2，yn，其中yi=(xi+si)mod 2，1in，s1，s2，sn为由LFSR产生的密钥流，那么Oscar就能够计算密钥流si=(xi+yi)mod 2，1in。如果Oscar再知道LFSR的级数m，那么Oscar只需要计算c0，c1，cm-1的值就能够重构整个密钥流。现在已知对于任意的i1，有sm+i=(c0si+0+c1si+1+cm-1si+m-1)mod 2以上方程是一个包含有m个未知数c0，c1，cm-1的线性方程。如果n2m，则
36、根据明文和密文消息之间的对应关系，可以得到包含以上m个未知数c0，c1，cm-1的m个线性方程，利用这些方程就可以解出这m个未知数。m个线性方程可以用矩阵形式表示如下：(3-11)12113221110221),(),(mmmmmmmmmssssssssscccsss如果方程组(3-11)的系数矩阵在模2运算的逆矩阵存在，则可得到方程组的解：当然，如果m是LFSR的级数，那么方程组(3-11)的系数矩阵在模2运算下就一定是可逆的。112113221221110),(),(mmmmmmmmmssssssssssssccc例例3.3 假设Oscar得到的密文消息为101101011110010相应
37、的明文消息为011001111111000那么Oscar能够计算出用来加密的密钥流为110100100001010假设Oscar已知使用的LFSR是5级结构，那么Oscar利用上面得到的10组不同的密钥流来构造以下方程组：0010001001100100010101011),()0,0,0,1,0(43210ccccc首先计算011011101010000010011001011111111111这样解方程组得到从而得到LFSR产生密钥流的递推公式为si+5=(si+si+3)mod 2所以，这个体制是不安全的。)0,1,0,0,1(0110111010100000100110010)0,0,
38、0,1,0(),(43210ccccc4.普勒斯生成器普勒斯生成器普勒斯生成器由8个线性反馈移位寄存器组成4个JK触发器，外加一个循环计数器联接而成。普勒斯生成器的基本结构如图3-10所示。在普勒斯生成器中，循环计数器的作用是决定在每一个时间脉冲作用下的输出单元。这个密钥流生成器的密钥是8个线性反馈移位寄存器和它们相应的初始状态，JK触发器的初始状态以及输出单元的顺序。普勒斯提出的8个线性反馈移位寄存器的级数不仅使得各个线性反馈移位寄存器对之间达到级数互素，而且达到各个JK触发器的输出周期互素，从而使得最终的输出序列的周期为以上各周期的乘积。图3-10 普勒斯生成器的基本结构定义定义3.4.1
39、 如果一个函数有n个二元输入和1个二元输出，则称该函数为包含n个变元的布尔函数。在包含n个变元的函数中共有个不同的布尔函数，所以相应的n级移位寄存器中共有个不同的反馈函数，而n级线性反馈移位寄存器对应的线性反馈函数只有2n种。因此在反馈移位寄存器中，非线性反馈函数相比于线性反馈函数，其数量特别巨大。应强调的是，并非所有这些非线性反馈函数都能产生具有良好特性的输出序列。关于一般的非线性反馈移位寄存器的研究目前仍然处于初级阶段，应用较多的仍然是在线性反馈移位寄存器的基础上进行非线性化的设计。3.4 非线性反馈移位寄存器非线性反馈移位寄存器n22n22定义定义3.4.2 长度为L的反馈移位寄存器(F
40、SR)由标号为0，1，L-1的L级(或延迟单元)构成，其中每一级均可存储1比特并且有1比特的输入和输出，而且还有一个时钟来控制数据的运动。FSR在每一个单位时间内执行以下操作：(1)将第0级中的存储内容输出，以构成输出序列的一部分。(2)对每一个i，1iL-1，将第i级的存储内容移入第i-1级。(3)第L-1级中存储的新元素为反馈比特sj=f(sj-1，sj-2，sj-L)，其中反馈函数f是一个布尔函数，而且对于1iL，si-1为第L-i级中先前存储的比特。如果对于每一个i，1iL-1，第i级中所存储的初始内容为si0，1，则相应的sL-1，sL-2，s1，s0称为该反馈移位寄存器FSR的初始
41、状态。图3-11给出了一个反馈移位寄存器的基本结构。当反馈函数f是一个线性函数时，FSR就是一个线性反馈移位寄存器；否则，FSR是一个非线性反馈移位寄存器。如果FSR的结构如图3-11所示，相应的初始状态为sL-1，sL-2，s1，s0，那么FSR的输出序列s=s0，s1，s2，可以通过以下递推公式惟一确定：sj=f(sj-1，sj-2，sj-L)，jL (3-12)图3-11 FSR的基本结构定义定义3.4.3 如果反馈移位寄存器的每一个输出序列都是周期序列，则该反馈移位寄存器称为非奇异的。当反馈移位寄存器的反馈函数为f(sj-1，sj-2，sj-L)时，该反馈移位寄存器是非奇异的，当且仅当
42、反馈函数f具有以下形式：f(sj-1，sj-2，sj-L)=sj-Lg(sj-1，sj-2，sj-L+1)其中，g是一个布尔函数。所以一个长度为L的非奇异反馈移位寄存器的输出序列的最大周期为2L。定义定义3.4.4 如果一个长度为L的非奇异反馈移位寄存器的输出序列的周期均为2L，那么该反馈移位寄存器称为de Bruijn FSR，相应的输出序列称为de Bruijn序列。例例3.4 设非线性反馈函数为f(x1，x2，x3)=1x2 x3 x1x2，则相应的反馈移位寄存器记为FSR。表3-3给出了对应初始状态为0，0，0，在每个t时间单位后，该反馈移位寄存器FSR的3级中所存储的内容。根据定义3
43、.4.4可知，反馈函数f(x1，x2，x3)=1 x2 x3 x1x2对应的FSR输出序列是一个de Bruijn序列，其周期为8，循环为0，0，0，1，1，1，0，1。1.试分析以下生成器产生的序列能够达到的最大周期是多少？对应的参数a的值应该是多少？xn+1=(axn)mod 242.以下给出一种序列密码体制。设是定义在Z26上的一个置换，密钥kZ26。对任意的i1，密钥流元素ziZ26按以下规则产生：zi=(k+i-1)mod 26加密和解密过程使用置换和对应的逆置换-1分别进行以下运算：ek(x)=(x)+z)mod 26dk(y)=-1(y-z)mod 26习习 题题现在假设置换定义
44、如下：试使用穷举式搜索法破译使用以上序列密码体制加密的如下密文：WRTCNRLDSAFARWKXFTXCZRNHNYPDTZUUKMPLUSOXNEUDOKLXRMCBKGRCCURR3.设一个4级线性反馈移位寄存器的反馈函数为f(a1，a2，a3，a4)=c4a1c3a2 c2a3 c1a4其中，c1=c4=1，c2=c3=0，反馈移位寄存器的初始状态为1，0，0，0。试给出该反馈移位寄存器的输出。4.已知3级线性反馈移位寄存器在c3=1时可以有4种不同的线性反馈函数，设对应这4种线性反馈移位寄存器的初始状态均为1，0，1。试分别求这4种线性反馈移位寄存器的输出序列及相应的周期。5.设已知一个4级的线性反馈移位寄存器的结构如图3-12所示，已知其初始状态为1，0，0，0。试求该线性反馈移位寄存器的输出序列和相应的周期。6.设n=4，反馈函数f(a1,a2,a3,a4)=a1 a4 1 a2a3，反馈移位寄存器的初始状态为1，0，1，1。试求该反馈移位寄存器的输出序列及相应的周期。
