5-序列密码

null回忆上次课内容回忆上次课内容数论 素数、互素、模运算、模逆元、中国剩余定理、因子分解 信息论 多余度、熵、唯一解距离 复杂度理论 算法复杂度、问题复杂度理论密码体制的分类 现代密码体制的数学理论 密码破译 香农保密理论序列密码序列密码序列密码基本概念 序列密码工作原理 序列密码特点 序列密码－密钥序列 Golomb的伪随机性公设 移位寄存器理论 线性反馈移位寄存器 密钥流发生器模型 序列密码常见算法—A5、RC4 序列密码序列密码序列密码又称为流密码（stream cipher） 原理：明文流与密钥流按顺序逐比特进行异或运算，从而产生密文流。明文流： 1 0 0 1 1 1密钥流： 0 1 0 0 1 1密文流： 1 1 0 1 0 0序列密码一直是作为军事和外交场合使用的主要密码技术之一 。序列密码工作原理序列密码工作原理序列密码特点序列密码特点加密/解密运算只是简单的模二加运算。 密码的强度主要靠密钥流的随机性。核心/关键序列密码—密钥序列序列密码—密钥序列伪随机数 使用一个确定性的算法计算出来的似乎是随机的数序，因此伪随机数实际上并不随机 。 在计算伪随机数时假如使用的开始值不变的话，那么伪随机数的数序也不变。 伪随机数的随机性可以用它的统计特性来衡量，其主要特征是每个数出现的可能性和它出现时与数序中其它数的关系。 Golomb的伪随机性公设。Golomb的伪随机性公设Golomb的伪随机性公设Golomb提出的伪随机性公设： 各元素个数至多差一； 各元素游程数相等，长为i的游程占游程总数的1/2i； 异相自相关函数是一个常数。 例：1000 1111 0101 100 1 000 1111 0 1 0 11 00100011110101100 000111101011001 左移1位 001111010110010 左移2位011110101100100 左移3位 移位寄存器理论移位寄存器理论1965年，挪威的首席密码学家Ernst Selmer提出了移位寄存器理论。 移位寄存器序列即用于密码学，也用于编码理论。 基于移位寄存器的序列密码广泛应用于军事领域的保密中。 利用移位寄存器产生伪随机序列 移位寄存器移位寄存器…rnrn-1rn-2r2r1n个寄存器， r1，r2，…，rn从右到左排列，n阶每个寄存器中能存放1位二进制数：bi所有寄存器中的数统一向右移动1位，称为进动1拍。反馈移位寄存器（FSR）反馈移位寄存器（FSR）FSR：feedback shift register反馈函数fn位寄存器中的初始值称为移位寄存器的初态。反馈函数f：n个变元的布尔函数。f(bn,bn-1,…,b2,b1)bn,bn-1,…,b2,b1取值{0,1}f也取值{0,1}null第7时刻 0 0 1第0时刻 0 0 1第1时刻 1 0 0第2时刻 1 1 0第3时刻 1 1 1 第4时刻 0 1 1第5时刻 1 0 1第6时刻 0 1 0产生序列为：1001110……例：3级LFSRf(x)=b3+b1序列周期？最大周期？线性反馈移位寄存器(LFSR)线性反馈移位寄存器(LFSR)反馈函数f异或运算n阶LFSR的有效状态为2n-1理论上能产生周期为2n-1的伪随机序列初态：100m序列m序列若一个n阶的LFSR的输出序列周期为2n-1，则称该序列为m序列。1001101001000010101110110001111100110…周期：31初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1) 本原多项式m序列有良好的随机性，50年代作为密钥序列用于军用，60年代发现不安全。密钥流发生器模型密钥流发生器模型序列密码密钥流发生器的原则是，以线性反馈移位寄存器的输出序列（m序列）为基序列，经过不规则采样、函数变换等（即非线性变换），得到实用安全的密钥流。 非线性移位寄存器序列 对线性移位寄存器序列进行非线性组合 利用非线性分组码产生非线性序列序列密码常见算法—A5序列密码常见算法—A5A5算法 欧洲数字蜂窝移动电话系统(GSM)中使用的序列密码加密算法，用于从用户手机到基站的连接加密，由法国人设计。 A5 算法(1)A5 算法(1)GSM系统空中接口加密A5算法(2)A5算法(2)由3个LFSR组成，长度为19、22和23，但抽头位较少。 3个LFSR在时钟控制下进动，三者输出异或产生输出位。 可在硬件上高效实现。缺点是寄存器太短，使穷举搜索。 序列密码常见算法—RC4序列密码常见算法—RC4RC4算法是由Ron Rivest于1987年设计的一种可变密钥长度的序列密码。 广泛应用于商业密码产品中。 该算法的速度可以达到DES加密的10倍左右，且具有很高级别的非线性。 在1994年9月，它的算法被发布在互联网上，也就不再有什么商业机密了。 补充—中国密码政策补充—中国密码政策我国的密码分级 核心密码：保护党、政、军的核心机密 普通密码：保护国家和事企业单位秘密信息 商用密码：保护国家和事企业单位敏感信息 个人密码：保护个人隐私涉密网非涉密网前三种国家密码局统一管理。我国商用密码政策： 　　　统一领导、集中管理、定点研制、专控经营、满足使用。无线局域网产品使用的SMS4密码算法，是国内官方公布的第一个商用密码算法。 官方公布商用密码官方公布商用密码无线局域网产品须采用下列经批准的密码算法： 　　1、对称密码算法：SMS4； 　　2、签名算法：ECDSA; 　　3、密钥协商算法：ECDH； 　　4、杂凑算法：SHA-256； 　　5、随机数生成算法：自行选择。 其中，ECDSA和ECDH密码算法须采用我局指定的椭圆曲线和参数。国家密码管理局公告（第 7 号）　　2006.1.6古代商用密码古代商用密码丁不勾、示不小、五不直、罪不非、吾不口、交不叉、皂不白、分不刀、馗不首、针不金 忆多娇、耳边风、散秋香、思故乡、误佳期、柳金娘、砌花台、霸陵桥、救情郎、舍利子 平头、空工、横川、睡目、缺丑、断大、半皂、分首、残丸、田心 挖、竺、春、罗、语、交、花、分、旭、田 null序列密码基本概念 序列密码工作原理 序列密码特点 序列密码－密钥序列 Golomb的伪随机性公设 移位寄存器理论 线性反馈移位寄存器 密钥流发生器模型 序列密码常见算法—A5、RC4