【安全课件】第18讲--序列密码的编码层次

序列密码的编码层次及几个序列密码算法量子密码研究室王滨2005年4月6日2序列密码的编码层次一、编码层次前馈逻辑、时序逻辑、筛选逻辑和控制逻辑（一）前馈逻辑主要由初始乱源发生器(线性或非线性的反馈移位寄存器等),抽头的变换以及前馈函数三部分组成。3bFSR1l2lrl()fx1、初始乱源发生器：为前馈函数f(x)提供具有良好统计特性的输入序列。在应用中,以线性反馈移位寄存器作为初始乱源发生器是最常见的，给一个n级本原线性移存器注入n比特初态，便可以产生周期为2n-1的二元序列，“代价”是非常低的，但低廉的代价，同时也导致了序列比特间“强烈的”线性制约关系,对于n级本原移存器只需截收到2n个连续信号就可求出唯一解。因此它不能直接作为密钥(乱数)输出使用。利用非线性前馈函数f(x)就可以“破坏”这种线性制约性,起到提高序列线性复杂度的作用。42、抽头变换：3、前馈函数：r个抽头l1,l2,…,lr作为前馈函数f(x)的输入,它可以由密钥因素来控制,起到增加密钥变化量的作用,它与前馈函数一起构成一个前馈网络。前馈函数f(x)是一个非线性布尔函数或多输出的非线性布尔函数，它一方面“破坏”输入序列连续比特的线性制约关系,即提高输入序列的线性复杂度；另一方面,f(x)又不能破坏输入序列良好的伪随机特性，同时还要考虑到输入信息在输出序列中的泄漏。非线性变换应满足：能将LFSR序列的良好统计特性传递给所生成的密钥序列，使输出序列的周期足够大；输出序列能抗线性逼近，且不能泄露LFSR的结构和状态。5（二）、时序逻辑时序逻辑是一种有记忆变换，使输出不仅与当前时刻的输入因素有关，而且与以前时刻的输入和输出因素有关,从而实现输入信息的纵向扩散。1、累加器变换输入为：；输出为：累加器变换定义为：；且123{,,}aaaa123{,,}bbbb1iiimma,1,2,iibmi可以看出：30123bmaaa2012bmaa101bma62、实数和序列(R.Rueppel于1985年提出)1()iiiiiiiiiizabssababs设输入序列为a、b，定义实数和序列z如下：其中s称为进位序列，假设。10s33333322121112zabsababaababb22222211zabsabab111zab则实数和序列实现数据的由低位向高位的扩散，即高位不仅受当前输入的影响，而且受以前输入的影响。7Macb3、调换存储变换调换存储区M包含个存储单元，a是输入序列,b是输出序列,c是k路控制序列。2k工作过程如下:在第i时刻，由序列c的k比特确定M中存储单元的地址，从该地址中读出的数据即为输出,然后把a中相应的值置入该存储单元中。8（三）、筛选逻辑筛选逻辑的作用就是破坏二元序列比特间的跟随关系，增加算法的复杂性。自控采样：就是控制序列对其自身进行采样，当它的某一位为1时，走两步输出；为0时，走一步输出。例如：控制序列为：11111000110111010100001001...得到的输出序列为：11100101111000101...9（四）、控制逻辑作用：控制算法中的各个编码环节，例如控制源移存器的不等距采样、抽头位置的选取、前馈函数的选择等。控制逻辑本身还起到了增加密钥变化量，提高算法复杂性的作用。10模拟的序列密码算法注：所谓n阶拉丁方阵，是一个仅含有n个不同元素的方阵，且方阵的每行和每列正好包括每个元素各一次。s线性移存器cLLo源移存器拉丁方Mgcicmc'mcab'b前馈函数f(x)调换存储控制移存器抽头11线性移位寄存器L-c是控制移存器，抽头c-g控制源移存器L-o的动作，如c-g为0时，L-o走一步输出；为1时走两步输出。抽头c-i控制从源移存器的抽头,即前馈函数f(x)的输入，如c-i为0时取L-o的第1,3,5,7,...位置上的抽头；为1时取L-o的第2,4,6,8,...位置上的抽头。a为前馈函数f(x)的输出序列(若干路)，它与L-c的输出序列c-m’(若干路)通过拉丁方变换得到序列c-m，以它作为调换存储M的地址序列。b序列即为最后的输出序列(密钥序列)。上图中，从线性控制移存器L-c抽出的各抽头序列，起到了控制作用，属于控制逻辑；源移存器L-o、抽头s以及前馈函数f(x)构成前馈逻辑；调换存储M起到了打乱序列时序的作用，属于时序逻辑；从L-c抽出的抽头c-g控制源移存器L-o的动作，对其产生的序列进行不等距采样，属于筛选逻辑。12A5/2算法密钥发生器191817141()1fxxxxx22212()1fxxx23222183()1fxxxxx1754()1fxxx13A5/2算法密钥发生器14A5/2算法密钥发生器15A5/1算法密钥发生器LFSR1LFSR2LFSR3钟控b191817141()1fxxxxx22212()1fxxx23222183()1fxxxxx16A5/1算法密钥发生器17A5/1算法密钥发生器18作业P121－6.1，6.2，6.6作业文档中的题目