上海交大密码学课件--第二讲：序列密码.ppt

2.1序列密码 流密码(也称序列密码)：将被加密的消息m分成连续的符号(一般为比特串)，m=m1m2m3……；然后使用密钥流k=k1k2k3……中的第i个元素ki对ｍ的第i个元素mi执行加密变换，i=1,2,3,……；所有的加密输出连接在一起就构成了对m执行加密后的密文。 第二讲　序列密码 2.1.1 流密码简单结构 如何生成一个可以作为密钥流的“随机”比特序列，要求易于使用，但又不能太短以至于不安全 通常加、解密所需要的这种序列是由一个确定性(deterministic)的密钥流生成器(key generator)产生的，该生成器的输入是一个容易记住的密钥，称之为密钥流生成器的初始密钥或种子(seed)密钥 安全性: 流密码的安全性完全取决于密钥的安全等级. 实用的流密码以少量的、一定长度的种子密钥经过逻辑运算产生周期较长、可用于加解密运算的伪随机序列。 2.1.2同步流密码与自同步流密码 同步流密码:密钥流的产生与明文消息流相互独立 自同步流密码: 密钥流的产生与之前已经产生的若干密文有关，其加密过程形如： ２.１.3线性反馈移位寄存器 密钥流的生成方法: 有多种产生同步密钥流生成器的方法，最普遍的是使用一种称为线性反馈移位寄存器(linear feedback shift register, LFSR)。 LFSR的结构非常适合硬件实现；LFSR的结构便于使用代数方法进行理论分析；产生的序列的周期可以很大；产生的序列具有良好的统计特性。 反馈移位寄存器 如图为一个反馈移位寄存器的流程图，信号从左到右。a_i表示存储单元，取值为0或1，a_i的个数n称为反馈移位寄存器的级。在某一时刻，这些级的内容构成该反馈移位寄存器的一个状态，共有个2^n个可能的状态，每一个状态对应于与F2上的一个n维向量，用(a_1, a_2,…,a_n)表示。函数f是一个n元布尔函数，称之为反馈函数。 线性反馈移位寄存器 如果反馈函数形如 : LFSR中反馈函数的系数取值的不同，这样的反馈函数有2^n种。令表示t时刻第i级寄存器的内容，则第t+1时刻寄存器的内容为： 例. 如图所示为一4级线性反馈移位寄存器，状态转移关系为： 例2.2 如图所示是一个联接多项式为 从初始状态开始，沿着箭头所指示的路径依次取出最左边的分量便得到该LFSR的输出序列：1110100 1110100 ……，周期为7(=23-1)。 若以状态转移图中任一状态作为初始状态，沿箭头所指示的路径依次取出最左边的分量还可得到另外6个序列：1101001 1101001……；1010011 1010011……；0100111 0100111 ……；1001110 1001110……；0011101 0011101……；0111010 0111010……。全部7个序列取自同一个状态转移图上，将这7个序列之一经过适当的移位可以得到其余任一序列，称这7个序列是移位等价的。 例4. 如图为一个4级LFSR，其联接多项式为 如取初始状态为(a1, a2, a3, a4)=(0,0,0,1)，其状态转移图为： 如取初始状态为(a1, a2, a3, a4)=(1,0,1,0)，其状态转移图为： m序列与最大周期移位寄存器 根据LFSR的状态转移图可以看出，一个n级LFSR序列的周期最大只能为2n-1 ＧF(2)上n次多项式 为联接多项式的n级LFSR所产生的非零序列的周期为2n-1，称这个序列是n级最大周期线性移位寄存器序列，简称m序列 . 如果一个n级LFSR产生了m序列，则该LFSR的状态转移图仅由2个圈构成，其中一个是由全零状态构成的长度为1的圈，另一个是由全部其余2n-1个状态构成的长度为2n-1的圈。 一个n级LFSR为最长移位寄存器的充要条件是它的联接多项式为F2上的n次本原多项式 2n-1为素数时，F2上的每一个n次不可约多项式均为n次本原多项式 2.1.4 伪随机序列 1. 随机序列 假定抛掷一枚硬币，倘若出现正面，就记为1，出现反面则记为-1。反复抛掷硬币就得到一个二元随机变量序列： 由于每次试验的结果与以前各次试验不发生任何关系，因此这种序列是独立试验的结果 性质: 1) 1出现的次数与-1出现次数近乎相等。用概率论的语言来说就是1与-1出现的概率是相等的，都是 2)联在一起的1的一段，它的两端都是-1，叫做1的游程 ,其中1的个数叫做游程的长度 .类似地，能够定义-1的游程 .类似可以定义长度为k的游程 Golomb随机性假设 在每一周期内，0的个数与1的个数近似相等； 在每一周期内，长度为i的游程数占游程总数的 定义自相关函数为 　　这是一个二值函数：