线性反馈移位寄存器课件

1l复习上节课的内容26 6 序列密码序列密码序列密码序列密码6.1线性同余产生器6.2线性反馈移位寄存器6.3序列密码的设计与分析6.4进位反馈移位寄存器6.5非线性反馈移位寄存器6.6设计序列密码的方法36.1 6.1 线性同余产生器线性同余产生器线性同余产生器线性同余产生器l线性同余产生器：伪随机序列产生器Xn=(aXn-1+b)modmXn为序列中第n个数，Xn-1为序列中第n-1个数变量a，b和m为常数X0为密钥或种子最大周期：m-1l不能用于密码学46.2 6.2 线性反馈移位寄存器线性反馈移位寄存器线性反馈移位寄存器线性反馈移位寄存器l移位寄存器：一个二进制位序列。需要1位时，所有位都向右移动一位，空出的最左边一位由寄存器中其他位的一个函数来计算。移位寄存器的输出为1位，通常是最低位。周期为输出序列开始重复之前的长度。l反馈移位寄存器：由一个移位寄存器和一个反馈函数组成。l线性反馈移位寄存器（LFSR）：反馈函数为寄存器中特定位的异或。这些位的列表称为一个选择序列。具有特定选择序列的LFSR会遍历所有的2n-1个内部状态，为最大周期的LFSR。bnbn-1b4b3b2b1反馈函数反馈移位寄存器6lm序列：最大周期的LFSR产生的输出序列。l最大周期的LFSR的选择序列构成的多项式加上常数1为模2的本原多项式，多项式的阶为移位寄存器的长度。ln阶本原多项式：一个不可约多项式，能整除x2n-1+1，但对任意整数d，满足d整除2n-1，多项式不能整除xd+1。l用本原多项式x32+x7+x5+x3+x2+x+1构造最大周期的LFSR：b32b7b6b5b4b3b2b132位的最长周期的LFSR输出位76.3 6.3 序列密码的设计与分析序列密码的设计与分析序列密码的设计与分析序列密码的设计与分析l线性复杂度：能够模拟产生器输出的最短的LFSR的长度n。低线性复杂度的产生器肯定是不安全的有高的线性复杂度也不一定安全l相关免疫函数86.6 6.6 进位反馈移位寄存器进位反馈移位寄存器进位反馈移位寄存器进位反馈移位寄存器l进位反馈移位寄存器（FCSR）：包括一个移位寄存器，一个反馈函数和一个进位寄存器。l进位寄存器：将选择序列的各位相加，并加上进位寄存器的内容，结果模2成为新位，结果除以2成为进位寄存器的新内容。bnbn-1b4b3b2b1和进位反馈移位寄存器和除以2和模2输出位96.7 6.7 非线性反馈移位寄存器非线性反馈移位寄存器非线性反馈移位寄存器非线性反馈移位寄存器l反馈函数可以是任意的l问题：可能会有倾向性最大周期可能很低开始值不同，可能周期不同序列可能退化106.8 6.8 设计序列密码的方法设计序列密码的方法设计序列密码的方法设计序列密码的方法l系统理论方法：尽量保证每次设计都为攻击者设置一个未知且难以解决的问题，使用一套基本的设计原则和标准。l信息论方法：尽量让攻击者对明文一无所知。l复杂性理论方法：尽量让密码系统基于或等价于一些已知的数学难题。l随机化方法：尽量通过迫使攻击者在密码分析中去检查大量无用的数据的方式来产生一个难以处理的大问题。密密密密 码码码码 学学学学 应应应应 用用用用121.密码学的数学基础密码学的数学基础2.传统密码学算法传统密码学算法3.对称钥算法对称钥算法4.公开钥算法公开钥算法5.序列密码序列密码6.程序安全程序安全7.操作系统安全操作系统安全8.数据库安全数据库安全9.网络安全网络安全10.灾难恢复计划灾难恢复计划11.11.信息隐藏与数字水印信息隐藏与数字水印目录目录目录目录137.1 7.1 保密通信保密通信保密通信保密通信1.链路加密2.端-端加密147.2 7.2 密码模式密码模式密码模式密码模式l电码本（ECB）l密文分组链接（CBC）l密文反馈（CFB）l输出反馈（OFB）15ECBECBKP1C1DESDES加密加密TIME=1(a)加密加密KP2C2DESDES加密加密TIME=2KPNCNDESDES加密加密TIME=NKP1C1DESDES解密解密TIME=1KP2C2DESDES解密解密TIME=2KPNCNDESDES解密解密TIME=N(b)解密解密16CBCCBCP1IVDES加密加密C1KP2DES加密加密C2KPNDES加密加密CNK(a)加密加密Time=1Time=2Time=N+CN1C1IVDES解密解密P1KC2DES解密解密P2KCNDES解密解密PNK(b)解密解密+CN117CFBCFB移位寄存器64j位|j位64DES加密64K选择|丢弃j位|64j位j+jP1C1j移位寄存器64j位|j位64DES加密64K选择|丢弃j位|64j位j+jP2C2j 移位寄存器64j位|j位64DES加密64K选择|丢弃j位|64j位j+jPMCMj(a)加密移位寄存器64j位|j位64DES加密64K选择|丢弃j位|64j位j+jP1C1jIV移位寄存器64j位|j位64DES加密64K选择|丢弃j位|64j位j+jP2C2j 移位寄存器64j位|j位64DES加密64K选择|丢弃j位|64j位j+jPMCMj(b)加密CM1IVCM118OFBOFB移位寄存器64j位|j位DES加密K选择|丢弃j位|64j位+P1C1IV移位寄存器64j位|j位DES加密K选择|丢弃j位|64j位+P2C2 移位寄存器64j位|j位DES加密K选择|丢弃j位|64j位+PMCM(a)加密移位寄存器64j位|j位DES加密K选择|丢弃j位|64j位+P1C1IV移位寄存器64j位|j位DES加密K选择|丢弃j位|64j位+P2C2 移位寄存器64j位|j位DES加密K选择|丢弃j位|64j位+PMCM(b)解密OM1OM119密码模式密码模式密码模式密码模式模式描述典型应用电 子 密码本（ECB）用相同的密钥分别对明文块加密单个数据的安全传输单个数据的安全传输（如一个加密密钥）密 文 块链接（CBC）加密算法的输入是上一个密文块和下一个明文块的异或普普通通目目的的的的面面向向分分组组的的传输传输认证认证文件加密文件加密密 文 反馈（CFB）一次处理J位，上一块密文作为加密算法的输入，用产生一个伪随机数输出与明文异或作为下一块的输入(J=8)普普通通目目的的的的面面向向分分组组的的传输传输认证认证输 出 反馈（OFB）与CFB基本相同，只是加密算法的输入是上一次DES的输出噪噪声声频频道道上上的的数数据据流流的的传传输（如卫星通讯）输（如卫星通讯）20单向函数单向函数单向函数单向函数lh=H（m），m为任意长消息，h为固定长度。l性质：l1.mh；l2.hm很困难；l3.给定m，很难找出另一个m，使得H（m）=H（m）。lh称为数字指纹，消息摘要,数字摘要。21MD5 Message Digest 5MD5 Message Digest 5l512bit=1632bit（M0M15）MD5128bit=432bit(A,B,C,D)l填充：L（m）+padding+64bit=512Klpadding=100message-len（64bit）lA，B，C，D初始值；22安全哈希函数安全哈希函数安全哈希函数安全哈希函数 SHASecureHashAlgorithmSHASecureHashAlgorithm l512bit=1632bit-M0M15SHA160bit=532bit-A,B,C,D,El1.填充，与MD5一样；l2.消息块从M0-M15扩展到W0-W79：lWt=mtt0，15lWt=（Wt-3Wt-8Wt-14Wt-16）1，t16，7923SHASHAl3.非线性函数：三个lft（x,y,z）=(XY)(XZ),t0，15lft（x,y,z）=XYZ,t20，39,t60,79lft（x,y,z）=(XZ)(ZY)(XY),t40，59l4.四个常数：lx0=232/4lKt=x0(1/2),=2,3,5,10.l5.五个初始变量：A，B，C，D，El6.4圈，每圈20次操作，共80个操作。247.7.44公钥数字签名公钥数字签名公钥数字签名公钥数字签名 lDSA257.57.5身份认证身份认证身份认证身份认证lkerberos协议267.5.17.5.1口令口令口令口令 l用户的口令以口令表的形式存储。277.6 7.6 密钥长度密钥长度密钥长度密钥长度l对称密码体制的密钥长度穷举攻击：如果密钥长n位，则有2n种可能的密钥悲观地看，至少应使用112位密钥。其他方法：使用网络的空闲时间使用攻击病毒28l公开密钥密码体制的密钥长度密钥长度的确定取决于因数分解的时间l两种密码体制密钥长度的对比l关于密钥长度的讨论：所保存信息的价值信息保密的时间信息的攻击者及其使用的设备和资源情况297.2 7.2 密钥管理密钥管理密钥管理密钥管理l密钥生成密钥空间密钥选择方式密钥的随机性通行短语X9.17密钥生成协议30l密钥传送两类密钥：密钥加密密钥：KEK数据加密密钥：DK把密钥分成几个不同的部分，通过不同的信道（方式）发送密钥的各部分l密钥验证验证密钥本身的特征：数字签名，KDC，电话验证其他：密钥传输期间错误的检测解密期间密钥错误的检测31l密钥使用会期密钥：控制向量CVl密钥更新：从旧密钥生成一个新密钥使用一个单向哈希函数l密钥存储：记忆、磁卡、ROM密钥、智能卡l密钥备份使用秘密共享协议使用智能卡暂存密钥32l密钥的生存期会期密钥：每天更换一次KEK：数月或一年存储文件的加密密钥：不常更换至少每两年更换一次l密钥的废止纸上：烧掉或撕碎EPROM或PROM：芯片粉碎到最碎的程度扔掉硬盘：将存储密钥的实际位多次重写，或将磁盘粉碎l公开密钥密码系统的密钥管理公钥证书分布式密钥管理33公钥体制的密钥管理公钥体制的密钥管理公钥体制的密钥管理公钥体制的密钥管理 lPKI，PublicKeyInfrastructurelKMI，KeyManagementInfrastructurelCA，CertificateAuthoritylRA，RegistrationAuthoritylCRL，CertificateRevocationListlLDAP,lightweightDirectoryAccessprotocollOCSP,Onelinecertificatestatusprotocol