第三章信息加密与认证

第三章信息加密与认证技术1授课人：肖敏专业：卓越班2本章内容概述对称密码技术公钥密码技术信息认证单向Hash函数与消息认证码的基本概念和原理数字签名的原理和技术身份认证的典型技术密码学(Cryptology):是研究信息系统安全保密的科学密码学包括密码编码学和密码分析学密码编码学研究密码体制的设计密码分析学研究密码体制的破译（密码分析科学家的工作则是评估一种密码算法的安全性，寻找更安全的密码算法）密码编码和密码分析是既相互对立的又是相互依存的。密码学的发展过程就是编码与分析互相斗争的过程。一个密码体制的推出，给密码分析提出新的挑战；一个密码体制的破译，导致一个新的密码体制的诞生。这样的过程不断反复，就构成了密码的历史。密码学概念3密码系统（体制）一般模型4明文明文密文加密算法解密算法加密密钥解密密钥原有的消息（待加密的消息）（Plaintext，简称P）密码系统（体制）一般模型5明文明文密文加密算法解密算法加密密钥解密密钥用某种方法伪装消息以隐藏它的内容的过程称为加密(Encrtption)对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm)密码系统（体制）一般模型6明文明文密文加密算法解密算法解密密钥被加密的消息（Ciphertext，简称C）加密密钥密码系统（体制）一般模型7明文明文密文加密算法解密算法加密密钥解密密钥把密文转变为明文的过程称为解密(Decryption)接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm)密码系统（体制）一般模型8明文明文密文加密算法解密算法加密密钥解密密钥为了有效控制加密、解密算法的实现，在这些算法的实现过程中，需要有某些只被通信双方所掌握的专门的、关键的信息参与，这些信息就称为密钥。用作加密的称加密密钥(EncryptionKey)，用作解密的称作解密密钥(DecryptionKey)。在授权方之间的密钥关系的建立和维护，是密码系统有效的关键点之一，相关的技术和过程，称为密钥管理。加密密钥和解密密钥可能相同，也可能不同密码系统（体制）一般模型9明文明文密文加密算法解密算法加密密钥解密密钥密码系统（体制）可以形式化表达为一个五元组（P,C,K,E,D)：（1）M是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k∈K,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x,这里x∈M。DdkEekCekM:M:Cdk密码系统（体制）一般模型明文M加密器E加密密钥Ke公开信道密文(M)ECeK破译者解密器D解密密钥Kd明文)(dCDMK发送方接收方密码系统（体制）一般模型11明文明文密文加密算法解密算法加密密钥解密密钥在一个密码系统中，算法是固定不变的运算规则和步骤的集合，密钥是可变的一定长度的数字、符号序列。在一个密码体制之下，以相同的明文作为输入，密钥不同则输出的密文不同。收信方收到密文之后，用与发方约定的密码算法和共享的密钥，对密文作逆向的密码变换得到明文。而对于未授权的不知密钥或密码算法与密钥都不知道的第三者，密文是无意义的乱码，这正是加密变换要达到的目的。防窃听假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：1.唯密文攻击：Oscar具有密文串y.2.已知明文攻击:Oscar具有明文串x和相应的密文y.3.选择明文攻击：Oscar可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串y，并构造出相应的明文x.这一切的目的在于破译出密钥或密文密码分析学12无条件安全（Unconditionallysecure）无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性计算上安全（Computationallysecure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期密码分析学13对称密码体制加密密钥和解密密钥一样，即加解密共用一把密钥根据加密针对的数据单元，对称密码体制又可分为：分组密码——每次对一块数据加密，多数网络加密应用，主要算法有DES、IDEA、TDEA、MD5、RC5、AES等流（序列）密码——每次对一位或一字节加密，多数手机加密应用，如One-timepadding,Vigenére,Vernam，RC4非对称密码体制加密密钥和解密密钥不一样，即加解密各用不同的密钥大部分是分组密码，只有概率密码体制属于流密码，如，RSA,ECC,ElGamal主要的现代密码体制14将明文划分成字符(单个字母)，或其编码的基本单元(0,1数字)字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现kI安全信道kI······KGKGkikimicicimiEki(mi)···Dki(mi)KG:密钥流生成器kI:初始密钥流密码(streamcipher)的基本概念加法流密码：ci=Eki(mi)=miki加法流密码：mi=Dki(Ci)=mikiki事实上，流密码算法其安全性依赖于简单的异或运算和随机密钥流。密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好的将其再现。密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，破译该算法就容易了。假的Alice得到一份密文和相应的明文，她就可以将两者异或恢复出密钥流。现在，无论她再拦截到什么密文消息，她都可以用她所拥有的密钥流进行解密。另外，她还可以解密，并阅读以前截获到的消息。一旦Alice得到一明文/密文对，她就可以读懂任何东西了。流密码(streamcipher)的基本概念16这就是为什么所有序列密码也有密钥的原因。密钥流发生器的输出是密钥的函数。这样，Alice有一个明文/密文对，但她只能读到用特定密钥加密的消息。更换密钥，攻击者就不得不重新分析。流密码(streamcipher)的基本概念17流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术同步流密码(SSC:synchronousstreamcipher)产生密钥序列的算法与明文、密文无关.只要通信双方的密钥序列产生器具有相同的“种子序列”和相同的“初始状态”,就能产生相同的密钥序列.通信双方必须保持精确同步,才能正确解密.容易检测插入、删除、重播等主动攻击.没有差错传播.流密码的分类18ciE(zi,mi)mizi密钥流生成器k自同步流密码(SSSC:self-synchronousstreamcipher)产生密钥序列的算法与以前的密文有关密钥流生成器是一种有记忆变换器密钥流与明文符号有关：i时刻的密文不仅取决于i时刻的明文，而且与i时刻之前的l个明文符号有关具有有限的差错传播具有自同步能力把明文每个字符扩散在密文多个字符中,强化了抗统计分析的能力流密码的分类19E(zi,mi)mizi密钥流生成器kci产生密钥序列的最重要部件是线性反馈移位寄存器，是因为:(1)LFSR非常适合于硬件实现;(2)能产生大的周期序列;(3)能产生较好统计特性的序列;(4)其结构能应用代数方法进行很好的分析.GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成。线性反馈移位寄存器(LFSR)20每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列“a1,a2,…,an”n维向量“(a1,a2,…,an)”来表示，其中ai是第i级存储器的内容。初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并计算f(a1,a2,…,an)作为下一时刻的an。线性反馈移位寄存器(LFSR)2019/12/1921基于LFSR的序列密码非常适合于硬件实现，但是不特别适合软件实现。比较常用的序列密码是A5、SEAL和RC4序列密码算法，A5是典型的基于LFSR的序列密码算法，SEAL和RC4不是基于LFSR的序列密码算法，而是基于分组密码的输出反馈模式（OFB）和密码反馈模式（CFB）来实现的。常用的流密码算法22A5有两个版本：A5/1和A5/2，前者有更高的安全性，根据相关法规限制被仅用于欧洲范围，而后者用于其它地区。A5算法从未公布于众，但因为一些疏漏，该算法被Bradford大学研究人员泄密，我国学者徐胜波、何大可和王新梅也由此于1994年率先实现A5算法。A5是欧洲数字蜂窝移动电话系统（GSM）采用的流密码算法，用于加密从用户到基站的连接A5算法23GSM会话每帧有228bitA5算法的密钥长64bit有一个22bit帧序号每次产生228bit会话密钥逐帧加密，每个帧的加密密钥不同A5算法24A5算法工作过程（1）将64比特密钥输入LFSR；（2）将22比特帧序号与LFSR反馈值模2加，再输入LFSR；（3）LFSR开始停走钟控；（4）舍去产生的100比特输出；（5）产生114比特作为密钥流；（6）舍去产生的100比特输出；（7）产生114比特作为密钥流A5算法25RC4是由Rivest于1987年开发的一种序列密码,它已被广泛应用于Windows,LotusNotes和其它软件,还被用于安全套接字(SSL)和无线通信系统等.RC4优点是算法简单、高效，特别适于软件实现，加密速度比DES大约快10倍。RC4可以支持不同密钥长度，美国政府特别限定，用于出口的RC4的密钥长度不得超过40位RC4算法26RC4使用了一个28字节大小的非线性数据表(简称S表),S表的值S0,S1,…,S255是数字0到255的一个排列。对S表进行非线性变换,得到密钥流RC4算法271.I=0,J=02.I=I+1(mod256);3.J=J+SI(mod256);4.交换SI和SJ;5.t=SI+SJ(mod256);6.z=St.RC4输出密钥流字节z的算法对称密码体制——分组密码28分组密码以一个固定长度的明文分组为加密变换单元。加密变换采用多层迭代方式，即同一结构的变换多次地使用。加密变换在密钥参与之下进行多层迭代变换中，各层的变换除所加的层密钥不同之外，其他的运算皆不变。分组密码算法的一个重要特点就是：当给定一个密钥后，若明文分组相同，那么所变换出密文分组也相同，且密文分组和明文分组长度相同。分组密码的一个重要优点是不需要同步一个分组密码有三个指标：分组长度（如64，128，256）密钥长度（如56，112，128，256）变换层数（如8，10，16，32）三个主要算法加密算法解密算法密钥扩展算法要求：1分组长度足够大，防止穷举攻击；2密钥空间足够大，但不能太长，以便于密钥的管理；3算法要足够复杂，充分实现明文和密钥的扩散；没有简单的关系可寻对称密码体制——分组密码29采用分组密码体制；用64bit密钥来加密64bit数据的方法；DES的安全性不依赖于算法的保密，安全性仅以加密密钥的保密为基础；DES(DataEncryptionStandard)加密算法30DES算法的实现步骤第一步：初始置换IP对给定的64位比特的明文x，首先通过一个置换IP表来重新排列x，从而构造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位。第二步：16轮迭代