序列密码的编码层次.ppt

序列密码的编码层次 及几个序列密码算法,量子密码研究室 王 滨 2005年4月6日,2,序列密码的编码层次,一、编码层次,前馈逻辑、时序逻辑、筛选逻辑和控制逻辑,（一）前馈逻辑,主要由初始乱源发生器(线性或非线性的反馈移位寄存器等),抽头的变换以及前馈函数三部分组成。,3,1、初始乱源发生器：为前馈函数f(x)提供具有良好统计特性的输入序列。在应用中,以线性反馈移位寄存器作为初始乱源发生器是最常见的，给一个n级本原线性移存器注入n比特初态，便可以产生周期为2n-1的二元序列， “代价”是非常低的，,但低廉的代价，同时也导致了序列比特间“强烈的”线性制约关系, 对于n级本原移存器只需截收到2n个连续信号就可求出唯一解。因此它不能直接作为密钥(乱数)输出使用。利用非线性前馈函数f(x)就可以“破坏”这种线性制约性,起到提高序列线性复杂度的作用。,4,2、抽头变换：,3、前馈函数：,r 个抽头l1,l2,lr作为前馈函数f(x)的输入,它可以由密钥因素来控制,起到增加密钥变化量的作用,它与前馈函数一起构成一个前馈网络。,前馈函数f(x)是一个非线性布尔函数或多输出的非线性布尔函数 ，它一方面“破坏”输入序列连续比特的线性制约关系,即提高输入序列的线性复杂度；另一方面, f(x)又不能破坏输入序列良好的伪随机特性，同时还要考虑到输入信息在输出序列中的泄漏。,非线性变换应满足：能将LFSR序列的良好统计特性传递给所生成的密钥序列，使输出序列的周期足够大；输出序列能抗线性逼近，且不能泄露LFSR的结构和状态。,5,（二）、时序逻辑,时序逻辑是一种有记忆变换，使输出不仅与当前时刻的输入因素有关，而且与以前时刻的输入和输出因素有关,从而实现输入信息的纵向扩散。,1、累加器变换,输入为： ；输出为：,累加器变换定义为： ；且,可以看出：,6,2、实数和序列(R.Rueppel于1985年提出),设输入序列为a、b，定义实数和序列z如下：,其中s称为进位序列，假设 。,则,实数和序列实现数据的由低位向高位的扩散，即高位不仅受当前输入的影响，而且受以前输入的影响。,7,3、 调换存储变换,调换存储区M包含 个存储单元，a是输入序列,b是输出序列,c是k路控制序列。,工作过程如下: 在第i时刻，由序列c的k比特确定M中存储单元的地址，从该地址中读出的数据即为输出,然后把a中相应的值置入该存储单元中。,8,（三）、筛选逻辑,筛选逻辑的作用就是破坏二元序列比特间的跟随关系，增加算法的复杂性。,自控采样：就是控制序列对其自身进行采样，当它的某一位为1时，走两步输出；为0时，走一步输出。 例如：控制序列为：11111000110111010100001001. 得到的输出序列为：1 1 1 001 01 1 1 1 0001 01.,9,（四）、控制逻辑,作用：控制算法中的各个编码环节，例如控制源移存器的不等距采样、抽头位置的选取、前馈函数的选择等。控制逻辑本身还起到了增加密钥变化量，提高算法复杂性的作用。,10,模拟的序列密码算法,注：所谓n阶拉丁方阵，是一个仅含有n个不同元素的方阵，且方阵的每行和每列正好包括每个元素各一次。,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的动作，对其产生的序列进行不等距采样，属于筛选逻辑。,12,A5/2算法密钥发生器,13,A5/2算法密钥发生器,