第三章 信息加密与认证

第三章信息加密与认证技术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。密码系统（体制）一般模型明文M加密器E公开信道密文解密器D明文发送方接收方密码系统（体制）一般模型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······

KGKG

ki

ki

mi

ci

ci

mi

Eki(mi)···Dki(mi)KG:密钥流生成器kI:初始密钥流密码(streamcipher)的基本概念加法流密码：

ci=Eki(mi)=miki加法流密码：

mi=Dki(Ci)=mikiki

事实上，流密码算法其安全性依赖于简单的异或运算和随机密钥流。密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好的将其再现。密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。

如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，破译该算法就容易了。假的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)2023/2/521

基于LFSR的序列密码非常适合于硬件实现，但是不特别适合软件实现。比较常用的序列密码是A5、SEAL和RC4序列密码算法，A5是典型的基于LFSR的序列密码算法，SEAL和RC4不是基于LFSR的序列密码算法，而是基于分组密码的输出反馈模式（OFB）和密码反馈模式（CFB）来实现的。常用的流密码算法22A5有两个版本：A5/1和A5/2，前者有更高的安全性，根据相关法规限制被仅用于欧洲范围，而后者用于其它地区。A5算法从未公布于众，但因为一些疏漏，该算法被Bradford大学研究人员泄密，我国学者徐胜波、何大可和王新梅也由此于1994年率先实现A5算法。A5是欧洲数字蜂窝移动电话系统（GSM）采用的流密码算法，用于加密从用户到基站的连接A5算法23GSM会话每帧有228bitA5算法的密钥长64bit有一个22bit帧序号每次产生228bit会话密钥逐帧加密，每个帧的加密密钥不同A5算法24A5算法工作过程（1）将64比特密钥输入LFSR；（2）将22比特帧序号与LFSR反馈值模2加，再输入LFSR；（3）LFSR开始停走钟控；（4）舍去产生的100比特输出；（5）产生114比特作为密钥流；（6）舍去产生的100比特输出；（7）产生114比特作为密钥流A5算法25RC4是由Rivest于1987年开发的一种序列密码,它已被广泛应用于Windows,LotusNotes和其它软件,还被用于安全套接字(SSL)和无线通信系统等.RC4优点是算法简单、高效，特别适于软件实现，加密速度比DES大约快10倍。RC4可以支持不同密钥长度，美国政府特别限定，用于出口的RC4的密钥长度不得超过40位RC4算法26RC4使用了一个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轮迭代迭代规则为Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)（i=1,2,3…16）经过第一步变换已经得到L0和R0的值，其中符号⊕表示的数学运算是异或，f表示一种置换，由S盒置换构成，Ki是一些由密钥编排函数产生的子密钥。第三步：逆初始置换IP-1对L16R16进行交换得到R16L16对R16L16利用IP-1作逆置换，就得到了密文y。16轮迭代k1+fL0R0L1=R0L15=R14组码移位kik16+ff初始置换IP轮运算：Li

=Ri-1Ri=Li-1⊕f(Ri-1,Ki)（i=1,2,3…16）初始逆置换IP-1DES的一轮迭代Li-1

（32bit）Ri-1

（32bit）选择扩展运算E盒48bit寄存器48bit寄存器选择压缩运算S盒32bit寄存器置换运算PRi=Li-1⊕f(Ri-1,ki)（32bit）（32bit）⊕⊕Li=Ri-1轮开始：64bit分成左右两半子密钥Ki

（48bit）子密钥计算

在64位密钥中，由于不考虑每个字节的第8位(校验位)，DES密钥由64位减至56位。将这56位密钥分解成16个48位的子密钥，每个子密钥控制一次迭代过程。每个子密钥参与加密或解密运算过程，从而直接影响到加密或解密变换的结果。密钥(56位)密钥(64位)置换选择1循环左移密钥(56位)置换选择2密钥(48位)密钥计算逻辑64位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1D1置换选择2K1(48位)(56位)循环左移循环左移C16D16(56位)置换选择2(48位)K16DES实际上就是一种单字符替代，而这种字符的长度是64bit。也就是说，对于DES算法，相同的明文就产生相同的密文。这对DES的安全性来说是不利的。为了提高DES的安全性，可采用加密分组链接的方法。DES的明显缺点密文分组连接模式（CBCCipherBlockChaining）

X0Y0X1Y1X2Y2X3Y3X0Y0X1Y1X2Y2X3Y3……初始向量初始向量密钥密钥明文明文密文密文加密解密EEEEDDDD明文分组与前一个密文分组相加作为加密算法的输入（第一个明文分组则与初始设定的向量IV相加作为加密算法的第一个输入）。DES

的保密性DES的保密性仅取决于对密钥的保密，而算法是公开的。尽管人们在破译DES方面取得了许多进展，但至今仍未能找到比穷举搜索密钥更有效的方法。DES是世界上第一个公认的实用密码算法标准，它曾对密码学的发展做出了重大贡献。目前较为严重的问题是DES的密钥的长度。现在已经设计出来搜索DES密钥的专用芯片。

二重DES(DoubleDES)给定明文P和两个加秘密钥k1和k2，采用DES对P进行加密E，有密文C=EK2(EK1(P))对C进行解密D，有明文P=DK1(DK2(C))EEPXCK2K1加密图DDK2K1CXP解密图二重DES很难抵挡住中间相遇攻击法（Meet-in-the-MiddleAttack)二重DES(DoubleDES)40由

C=EK2(EK1(P))从图中可见

X=EK1(P)=DK2(C)EEPCXK1K2DDCPXK2K1加密解密若给出一个已知的明密文对（P,C)做：对256个所有密钥K1做对明文P的加密，得到一张密钥对应于密文X的一张表；类似地对256个所有可能的密钥K2做对密文C的解密，得到相应的“明文”X。做成一张X与K2的对应表。比较两个表就会得到真正使用的密钥对K1,K2。Tuchman给出双密钥的EDE模式（加密-解密-加密）：

C=EK1(DK2(EK1(P)))……对P加密

P=DK1(EK2(DK1(C)))……对C解密这种替代DES的加密较为流行并且已被采纳用于密钥管理标准（TheKeyManagerStandardsANSX9.17和ISO8732).TDEA——三重DES41到目前为止，还没有人给出攻击三重DES的有效方法。对其密钥空间中密钥进行蛮干搜索，那么由于空间太大为2112=5×1033，这实际上是不可行的。若用差分攻击的方法，相对于单一DES来说复杂性以指数形式增长，要超过1052。注意：1*.Merkle和Hellman设法创造一个条件，想把中间相遇攻击（meet-in-the-middleattack）的方法用于三重DES，但目前也不太成功。2*.虽然对上述带双密钥的三重DES到目前为止还没有好的实际攻击办法，但人们还是放心不下，又建议使用三密钥的三重DES，此时密钥总长为168bits.

C=EK3(DK2(EK1(P)))TDEA——三重DES2023/2/543IDEA瑞士联邦技术学院来学嘉（X.J.Lai）和J.L.Massey提出的第1版IDEA（internationaldataencryptionalgorithm，国际数据加密算法）于1990年公布，当时称为PES（proposedencryptionstandard，建议加密标准）。1991年，在Biham和Shamir提出差分密码分析之后，设计者推出了改进算法IPES，即改进型建议加密标准。1992年，设计者又将IPES改名为IDEA，目前已在PGP中采用。2023/2/544IDEAIDEA加密算法是在DES算法的基础上发展而来的，类似于三重DES算法，其分组长度也是64位，但密钥长度是128位，增加了破译难度。IDEA使用的运算有异或、模216加法和模（216+1）乘法算法的强度主要是通过有效的混淆和扩散特性而得以保证。IDEA可方便地通过软件和硬件实现现代计算机速度的迅速提高，使得只有56bit密钥的DES算法的安全性面临着极大的挑战。1997年，NIST公开征求AES（AdvancedEncryptionStandard）作为2001年以后的数据加密标准。1998年8月，AES召开第一次候选会，确定15个算法入围。1999年3月，AES召开第二次候选会，有5个算法入围（MARS,RC6,Rijndael,Serpent和Twofish）。2000年10月，NIST选出由比利时的JoanDaemen和VincentRijmen提交的Rijndael算法作为AES。2001年夏天，NIST颁布新的信息处理标准（FIPS），将Rijndael算法作为AES。高级加密标准(AES，AdvancedEncryptionStandard)45高级加密标准(AES，AdvancedEncryptionStandard)46分组长度（bit）128192256密钥长度（bit）128192256Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。轮数（Round）的不同取值轮数（Round）BlockLength=128BlockLength=192BlockLength=256KeyLength=128101214KeyLength=192121214KeyLength=256141414高级加密标准(AES)AES算法的每一步都是可逆的。算法有多轮相同的运算，每一轮包括4个步骤：非线性代替（S-盒）行循环左移（ShiftRow）列混合变换（MixColum）与扩展密钥相异或每一轮的子密钥从扩展密钥中取出，轮密钥长度等于分组长度密钥扩展过程同时应用了非线性变换和循环左移算法定义的所有运算都是在有限域GF(28)上进行的AES加密算法概述1.强力攻击法强力攻击可用于任何分组密码，且攻击的复杂度仅依赖于分组长度和密钥长度。工作效率包括加/解密速度、密钥扩展速度、存储空间等2.差分密码分析已知最有效的攻击迭代密码的方法之一。基本思想是通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。差分密码分析最初是针对DES加密提出的一种攻击方法，能成功破解轮数较低的DES。

对称密钥的密码分析方法493.线性密码分析本质上是一种已知明文攻击法，是对DES加密方法进行破译的主要方法。基本思想是通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统。4、差分-线性密码分析对差分密码分析和线性密码分析进行改进，是降低它们复杂度的众多改进之一。它利用的是差分密码分析和线性密码分析相结合的技术。

对称密钥的密码分析方法505、插值攻击利用了拉格朗日插值公式的思想。如果一个密码算法是固定的密钥的低次多项式函数，或项数较少的多项式，其项数可以估算出来，则通过插值法可以得到其代数表达式，从而可能恢复出密钥。对称密钥的密码分析方法51非对称密钥体制（公钥密码体制）在拥有大量用户的通信网络，若想让两两用户都能进行保密通信，即要求(1)任意一对用户共享一个会话密钥(2)不同的用户对共享的会话密钥不相同对于分配中心，N个用户则需要分配CN2个会话密钥，大量的数据存储和分配是一件很麻烦的事，在计算机网络环境下显的尤为突出。另外传统密码不易实现数字签名，也进一步限制了其发展。公开密钥算法的提出非对称密钥体制（公钥密码体制）公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见文献：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography，

IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制双钥体制的公钥可以公开，因此也称公钥算法公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了30多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用非对称密钥体制（公钥密码体制）加密与解密由不同的密钥完成已知密码算法和加密密钥，求解密密钥在计算上是不可行的两个密钥中任何一个都可以作为加密密钥，而另一个用作解密密钥公开密钥算法的基本要求

用公钥密码实现保密PKB是公开钥，SKB是秘密钥因为只有B知道SKB，所以其他人都无法对c解密。c=EPKB[m]m=DSKB[EPKB[m]]用公钥密码实现鉴别c=ESKA[m]m=DPKA[c]因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。另一方面，任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。用公钥密码体制实现认证和保密58c=EPKB[ESKA[m]]m=DPKA[DSKB[c]]公钥密码体制往往基于一个数学难题基于离散对数求解困难性（DLP）的公开密钥密码体制

离散对数难题是多个公开密钥密码算法的基础，如Diffie-Hellman的密钥交换算法和DSA数字签名算法。基于大整数分解难题（IFP）的公开密钥密码体制

第一个完全意义上的公开密钥密码体制是由RonRivest，AdiShamir和LenAdleman创设的RSA算法。这是一个基于大整数分解困难性的密码算法。非对称密钥体制（公钥密码体制）59在模p运算下，已知p和a，对任意的整数Y，存在唯一的1≤i≤P-1，使得Y≡ai(modP)，i被称为以a为底（模p）Y的离散对数，记为INDa,p(y)。模数为p=11，以a=7为底，可得数值y的离散对数的列表离散对数求解困难性60i123456789107i(mod11)75231046981设a为模p的本原根，p是一个素数，则在模p运算下底a的幂ai（i=1，2，3，…P-1）互不相同，取遍1，2，3，…P-1。如p=11,a=7y12345678910IND7,11(y)10346271985求离散对数是求幂运算的逆运算。求幂运算与其逆运算相比，前者易于计算，而后者则难计算。特别在模数很大（如100位以上的大素数）的运算中，求离散对数成为数学的难题。离散对数求解困难性61Diffie-Hellman的密钥交换算法是基于离散对数难解这一数学难题构建的。设p为一个大素数，给定模p的一个本原元a，（p,a）是公开的。A，B双方为建立共享的密钥，执行如下的协议：①AB：ax(modp)②BA：ay(modp)③A对收到的ay求(ay)x=ayx(modp)④B对收到的ax求(ax)y=axy(modp)A，B双方建立了共享的密钥K=

(ay)x(modp)=axy(modp)在该协议中，x是A的秘密密钥，y是B的秘密密钥。第三者获得ax和ay，无论由ax求x或由ay求y都是离散对数求解的难题。而无法求得x或y，就不能获得A，B的共享密钥axy(modp)。Diffie-Hellman的密钥交换算法62D-H算法可能遭受中间人攻击ManintheMiddleAttack

63YC=azYA=axYB=ayYC=azK2=azxK1=azyD-H算法没有提供关于双方身份的任何信息，容易遭受中间人攻击D-H的改进措施1992年Diffie,vanOorschot和Wiener开发了authenticatedDiffie-Hellmankeyagreementprotocol，或称为Station-to-Station(STS)协议，它用于防止在Diffie-Hellmankeyagreementprotocol上的中间人攻击。它对中间人攻击的免疫来自于两方面，一个是使用数字签名来相互认证，另一个是使用public-keycertificate。

D-H算法的改进65Diffie-Hellmankeydistributionscheme的变形能够用于安全交换密钥publishedin1985byElGamal:T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.

安全性是基于离散对数缺点：增加了消息长度（2倍）ElGamal公钥加密方案密钥建立密钥生成：选取一个大素数p及本原根a接收者Bob有一个密秘钥

XB

计算yB=aXB

modp

公开yBElGamal加密为加密M，发送者选择随机数k,0<=k<=p-1，（发送者私钥）

计算消息密钥K:K=yBkmodp

=(aXB)kmodp

计算密文对:C={C1,C2}

C1=akmodp

C2=K.Mmodp

=(aXB)kMmodp

发送到接收者k

需要永久保密ElGamal解密首先计算messagekeyKK=C1XB

modp=ak.XBmodp

计算明文:M=C2.K-1

modp

ElGamal方法是概率密码系统，即同一个明文在不同的时间由相同加密者加密会产生不同的密文①系统不需要保存秘密参数，所有的系统参数均可公开；②复杂度比RSA方法要大。

ElGamal方法的优点70RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。

RSA算法9p和q是素数 （秘密的）n=p×q

(公开密钥)

（非秘密的）(n)=(p-1)(q-1)

（秘密的）e是公开密钥(加密密钥) （非秘密的）d是秘密密钥(解密密钥） （秘密的）m是明文 （秘密的）c是密文 （非秘密的）加密算法：c=E(m)≡me(modn)解密算法：m=D(c)≡cd(modn)e满足条件：e和(p-1)(q-1)互素，即(e,

(n))=1d满足条件：ed≡1mod(p-1)(q-1)RSA描述RSA密钥产生1.随机选择两素数p和q

(长度在100位左右)2.计算公开模数：n=p×q3.计算秘密的欧拉指示函数：(n)=(p-1)(q-1)

4.选择随机数e(即加密密钥)，使之与(n)互素即gcd(e,(n))=15.计算解密密钥d=e-1mod(n)6.公布整数n和加密密钥e，并将d秘密保存为其秘密密钥。p和q

可以毁去不用，以增加其安全性。RSA加解密过程设B欲将明文m秘密传送给A1.B在公开档案库中找出A的公开密钥E(e，n)。2.将m分组为m=m1m2…mr，使得每个分组对应的十进制数小于n3.B对每一分组执行加密操作：c=me(modn)4.B将c传送给A。5.A收到密文c后，利用其私有密钥d，执行解密操作：m=cd(modn)RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。如果RSA的模数n被成功地分解为p×q，则立即获得φ(n)=(p-1)(q-1)，从而能够确定e模φ(n)的乘法逆元d，即d≡e-1modφ(n)，因此攻击成功。RSA的安全性26随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。

例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解RSA-130已于1996年4月被成功分解RSA-140已于1999年2月被成功分解RSA-155（512比特）已于1999年8月被成功分解，得到了两个78位（十进制）的素数。RSA的安全性27对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%。将来也可能还有更好的分解算法因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。RSA的安全性28RSA参数的选择1.P与q必须为强素数2.P与q的差必须很大（差几个位以上）3.p-1与q-1的最大公因子应很小4.e不可以太小5.d的长度不得小于N长度的1/4DES与RSA的比较1.处理效率方面：DES优于RSA2.密钥管理方面：RSA优于DES3.安全性方面：一样4.签名和认证方面：RSA可以RSA的安全性椭圆曲线系统第一次应用于密码学上是于1985年由Koblitz与Miller分别提出椭圆曲线密码体制在相同的安全强度下所要求的密钥强度仅是RSA的1/6，因此在运算速度和存储空间方面具有很大的优势，在实际应用中具有很大的使用价值。椭圆曲线密码79令p>3为质数，在GF(p)中的椭圆曲线E:y2=x3+ax+bmodp，其中，4a3+27b2≠0(modp)。曲线上另定义一个无穷远点O，对任一点A∈E，A+O=O+A=A。在E上定义加法运算令A=(x1，y1)与B=(x2，y2)为E上的点。若x2=x1，且y2=-y1，则A+B=O;

否则A+B=(x3，y3)，其中：x3=λ2-x1-x2，y3=λ(x1-x3)-y1，且λ=(y2-y1)/(x2-x1)在此加法运算下，E为Abel群。椭圆曲线定义80椭圆曲线密码体制是基于椭圆曲线群上的离散对数问题（ECDLP）的难解性。K=tG

[其中K,G为Ep(a,b)上的点，t为小于n（n是点G的阶）的整数]（相当于幂运算）给定t和G，根据加法法则，计算K很容易；

但给定K和G，求t就相对困难(称为椭圆曲线上的离散对数，ECDLP)椭圆曲线密码体制（ECC，EllipticCurveCryptosystem）81椭圆曲线密码体制椭圆曲线密码体制椭圆曲线密码体制一个利用椭圆曲线进行加密通信的过程：

1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。2、用户A选择一个私有密钥t，并生成公开密钥K=tG。3、用户A将Ep(a,b)和点K，G传给用户B。4、用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多），并产生一个随机整数r（r<n）。5、用户B计算点C1=M+rK；C2=rG。6、用户B将C1、C2传给用户A。7、用户A接到信息后，计算C1-tC2，结果就是点M。因为

C1-tC2=M+rK-t(rG)=M+rK-r(tG)=M8、再对点M进行解码就可以得到明文。椭圆曲线密码体制的优势85椭圆曲线密码体制的优势86混合加密算法

87如果RSA和DES结合使用，则正好弥补RSA的缺点。即DES用于明文加密，RSA用于DES密钥的加密。一种混合了非对称和对称加密算法的加密方式如图：混合加密算法

88认证又称为鉴别，是防止主动攻击（如篡改、伪造信息等）的一项重要技术，解决网络数据传输过程中可能出的非法访问与篡改、假冒伪造、拒绝服务、抵赖等安全问题。

根据认证的目的，认证可包括：消息认证：证实收到的消息来自可信的源点且数据在传输和存储过程中是否会被篡改、重放或延迟，常见的方法有：散列函数（Hash）：一个将任意长度的消息映射为定长的散列值的公共函数，以散列值作为认证码。消息认证码（MAC）：以一个消息的公共函数和用于产生一个定长值的密钥作为认证码。身份认证：验证信息的发送者是否是合法的，即实体认证，包括信源、信宿的认证与识别。常用的方法包括：数字签名身份识别技术3.5信息认证技术概述

89验证某个指定的数据是否来源于某个特定的实体。为了确定被认证的实体与一些特定数据项有着静态的不可分割的联系。包括信源、信宿的认证与识别。典型技术有数字签名技术 验证消息的完整性以及数据在传输和存储过程中是否会被篡改、重放或延迟。典型技术有Hash函数、消息认证码3.6Hash函数与消息认证90Hash函数：把可变长度的输入串M转换成固定长度的输出串h的一种函数。h＝H(M)Hash函数具备以下性质：Hash函数H可适用于任意长度的输入数据块，产生固定长度的Hash值。(数据指纹)对于每一个给定输入数据M，都能很容易计算出它的Hash值H(M)。使得硬件和软件实现成为实际可行如果给定Hash值h，要逆向推出输入数据M在计算上不可行，即Hash函数具备单向性对于给定的消息M1和其Hash值H(M1)，找到满足M2≠M1，且H（M2）＝H（M1）的M2在计算上是不可行的，即抗弱碰撞性要找到任何满足H（M1）＝H（M2）且M1≠M2的消息对（M1，M2）在计算上是不可行的，即抗强碰撞性雪崩效应：当一个输入位发生变化时，输出位将有一半会发生变化3.6Hash函数与消息认证——

Hash函数91Hash函数92Hash函数的一般结构哈希函数的核心技术——设计无碰撞的压缩函数f攻击者对算法的攻击重点是压缩函数f

的内部结构，分析过程常常需要先找出压缩函数f

的碰撞。由于是压缩函数，其碰撞是不可避免的。因此，在设计压缩函数f

时就应保证找出其碰撞在计算上是不可行的。常用的散列函数：MD5；SHA系列；Hash函数9390年代初由MIT（麻省理工学院MassachusettsInstituteofTechnology）

LaboratoryforComputerScience和RSADataSecurityinc.（RSA数码保安公司）的RonaldRivest开发出来，经MD2、MD3和MD4发展而来MD5的典型应用是对一段信息（message）产生信息摘要（message-digest），以防止被篡改

MD5还广泛用于加密和解密技术上

广泛的应用于unix系统中

MD5（Message-DigestAlgorithm5）94MD5以512位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由四个32位分组组成，将它们级联形成一个128位散列值。MD595压缩函数算法逻辑包含4个具有相似结构的“循环”，但每个循环使用不同的原始逻辑函数。每一循环都以当前的正在处理的512bit分组（Yq）和128bit的缓存值ABCD为输入，然后更新缓存的内容。每一循环还使用一个64元素表T[1…64]的四分之一，该表通过正弦函数构建。这个表提供了一个“随机化“的32bit模式集，它将消除输入数据的任何规律性。第4次循环的输出加到第1次循环的输入（CVq）上产生CVq+1。相加是缓存中4个字分别与CVq中对应的4个字以模232相加。MD596压缩函数单循环算法逻辑MD597循环原始函数g(b,c,d)1F(b,c,d)2G(b,c,d)3H(b,c,d)4I(b,c,d)每一循环由对缓存ABCD的16步操作组成。每一步操作的形式为：a←b+((a+g(b,c,d)+X[k]+T[i])<<<s)算法逻辑要点在一次循环的一步中，表T中64个32bit字元素中的每一个也只被使用一次。在每一步中，只有缓存ABCD的四个字节中的一个被更新。因此，该缓存的每个字节在这次循环中将被更新四次，然后在最后第五次产生这个分组的最后输出。注意每一循环均要使用四个不同的循环左移，且在不同的循环中使用的不同。所有这些复杂操作的意义在于使产生冲突（两个512bit分组产生相同的输出）非常困难。MD598算法由来安全散列算法（SHA）由美国国家标准和技术协会（NIST）提出，并作为联邦信息处理标准（FIPSPUB180）在1993年公布；1995年又发布了一个修订版FIPSPUB180-1，通常称之为SHA-1算法逻辑图消息的总体算法逻辑图与MD5的总体算法逻辑图类似。算法输入消息的最大长度不超过264

bit，输入是按512bit的分组进行处理的，最后产生的输出是一个160bit的消息摘要。SHA-199压缩函数算法逻辑包含四个具有相似结构的“循环”，但每循环使用不同的原始逻辑函数。每一循环都以当前正在处理的512bit（Yq）和160bit的缓存值ABCDE为输入，然后更新缓存的内容。第四循环（第80步）的输出加到第一循环的输入（CVq）产生CVq+l。相加是缓存中5个字分别与CVq中对应的5个字以模232相加。SHA-1100压缩函数单循环算法逻辑SHA-1每一循环的操作逻辑为：A,B,C,D,E←(E+f(t,B,C,D)+S5(A)+Wt+Kt),A,S30(B),C,D其中A,B,C,D,E=缓存中的5个字t=

步骤数；0≤t≤79f(t,B,C,D)=步骤t的原始逻辑函数Sk=32bit参数循环左移（旋转）k位Wt=由当前512bit输入分组导出的一个32bit字Kt=一个额外的常数；使用四个不同的值+=模232加法压缩函数单循环算法逻辑Wt前16个字的值直接取自当前分组中16个字的值。余下字的值定义如下：Wt=S1(Wt-16⊕Wt-14⊕Wt-8⊕Wt-3)SHA-1SHA-l利用Wt在压缩函数中将16个分组字扩展为80个字，这将在压缩的消息分组内引入许多冗余和相关，使寻找产生相同压缩函数输出的不同消息分组的工作更加复杂。对强行攻击的安全性：最显著和最重要的区别是SHA-1摘要比MD5摘要长32bit。使用强行技术，产生任何一个消息使其摘要等于给定消息摘要的难度对MD5是2128数量级的操作，而对SHA-l则是2160数量级的操作。此外，使用强行技术，产生具有相同消息摘要的两个消息的难度对MD5是264数量级的操作，而对SHA-1则是280数量级的操作。这样，SHA-1对强行攻击有更大的强度。对密码分析的安全性：由于MD5的设计，它易受密码分析的攻击。SHA-l显得不易受这样的攻击。由于有关SHA-1的设计标准几乎没有公开，因此很难判断其强度。速度：因为两个算法都在很大程度上依赖模232的加法，因此两者在32bit结构的机器上速度均很好。SHA-l有更多的步骤（80对64）且要处理160bit的缓存，相比之下MD5仅处理128bit的缓存。这样在相同的硬件上，SHA-l的行速度应该比MD5慢。简单性和紧凑性：两个算法均描述简单、易于实现，并且无需冗长的程序或很大的替换表。SHA-1与MD5的比较NIST已经在FIPS1820-2中颁布了三个修订的sha标准。SHA-256,SHA-384,SHA-512修订的sha标准2004年8月，在美国加州圣芭芭拉召开的国际密码大会上，并没有被安排发言的王小云教授拿着自己的研究成果找到会议主席，要求进行大会发言。就这样，王小云在国际会议上首次宣布了她及她的研究小组的研究成果——对MD5、HAVAL－128、MD4和RIPEMD等四个著名密码算法的破译结果。在MD5被王小云为代表的中国专家破译之后，世界密码学界仍然认为SHA－1是安全的。2005年2月7日，美国国家标准技术研究院发表申明，SHA－1没有被攻破，并且没有足够的理由怀疑它会很快被攻破，开发人员在2010年前应该转向更为安全的SHA－256和SHA－512算法。而仅仅在一周之后，王小云就宣布了破译SHA－1的消息。MD5和SHA-1的破解105TigerHash106TigerHash结构比MD5和SHA-1更复杂，接近于分组密码。为了适应64位处理器，Tiger选择输出位数是192位。使用了4个S盒，每个S盒将8位映射成64位。还应用了密钥扩展算法，对输入分组进行扩展

MAC实质上是一个将双方共享的密钥k和消息m作为输入的函数，如果将函数值记为MACK(M)，

，这个函数值就是一个认证标记，用δ表示。将MAC附加到消息中。接收者通过重新计算MAC来对消息进行认证。消息认证码（MAC，Messages

Authentication

Codes）107MAC应具有的性质如果对手窃取到M和MACK(M)，试图生成一个消息M’，使得MACK(M’)=MACK(M)，这在计算上不可行。MACK(M)应该能够均匀分布。对于随机选择的消息M和M’，MACK(M)=MACK(M’)的概率为2-n，其中n为MAC的比特长度。让M'为M的某种已知变换，即M'=f(M)。例如，f可能为将一个或多个特定的比特取反。在对种情况下，Pr[MACK(M)=MACK(M')]=2-n。MAC的构造方法有很多，主要类型是基于带密钥的Hash函数和基于分组密码的构造方法消息认证码利用对称分组密码体制（如DES、AES）的密码分组链接模式（CBC）一直是构造MAC的最常见的方法。如CBC-MAC、XOR-MAC、EMAC（加密的CBC-MAC）、PMAC、XECB-MAC等CBC-MAC对消息使用CBC模式进行加密，取密文的最后一块作为认证标记。被认证的数据（例如消息、记录文件或者程序）被分为连续的等长的分组：D1，D2，…，DN。基于分组密码的MAC基于DES的消息认证码基于分组密码的MACXOR-MACXOR-MAC有两种方式：无状态（XMACR）和有状态（XMACC）。在计算过程中引入索引值使得分组密码每次加密的明文各不相同，最后再将所有的密文异或。由于XOR-MAC使用异或来生成标记，这就为其带来了并行性、增量式、乱序验证等优点。攻击XOR-MAC成功的概率要比攻击CBC-MAC成功的概率低，并且这个概率跟消息长度没有关系。缺点是在算法中引入了索引信息，引起了消息的扩展，导致了加密次数的成倍增加，降低了运算速度

基于分组密码的MAC111XECB-MACXECB-MAC也可看成是XOR-MAC的一种改进，支持并行计算、增量式操作、乱序验证等特性。

XECB-MAC没有使用消息的有效位来记录消息的位置，减少了加密的次数，因此它的速度要高于XOR-MAC，但低于CBC-MAC。该方法的不足之处在于使用了两个密钥，这给密钥的存储和分发带来了困难。基于分组密码的MAC112PMAC

PMAC可以看成是对XOR-MAC的改进，具有可并行、支持消息的添加、截短和替换等优点。PMAC在计算MAC的时候不需要事先知道消息的长度，且不需要一个随机数或维持一个计数。但是，它的速度比CBC-MAC要慢，且该算法受专利保护，不能免费使用。基于分组密码的MAC113OCBOCB是在综合了PMAC和XCBC-MAC的构造方法的基础上提出来的，同时提供了加密和认证。

OCB的优点有：能处理任意长度的消息、运算速度快、支持并行处理。缺点在于算法复杂并且受专利保护，不可免费使用。基于分组密码的MAC114近几年，人们越来越感兴趣于利用哈希函数来设计MAC，这是因为像MD5、SHA-1这样的哈希函数，其软件执行速度比诸如DES这样的对称分组密码要快。基于带密钥的Hash函数的构造方法最早是由M.Bellare等人提出的。它要求所使用的Hash函数具有迭代结构（如MD5，SHA-1等），即反复地使用压缩函数f将长消息映射为短消息。然而，诸如SHA-1这样的哈希函数并不是专门为MAC而设计的，由于哈希函数不依赖于密钥，所以它不能直接用于MAC。目前，已经提出了许多方案将密钥加到现有的哈希函数中。HMAC是最受支持的方案，并且在Internet协议中（如SSL）中有应用HMAC115算法由来HMAC是针对MAC设计的，是一个将一个密钥与一个现有的散列函数结合起来的提议，是针对MAC设计的，能直接用作MAC。发表为RFC2104，已经作为IP安全中强制实行的MAC，同时也被其他的Internet协议如SSL使用。设计目标无需修改地使用现有的散列函数。特别是，散列函数的软件实现执行很快，且程序代码是公开的和容易获得的。当出现或获得更快的或更安全的散列函数时，对算法中嵌入的散列函数要能轻易地进行替换。保持散列函数的原有性能不会导致算法性能的降低。使用和处理密钥的方式很简单。基于对嵌入散列函数合理的假设，对认证机制的强度有一个易懂的密码编码分析。HMAC算法逻辑图Yi=M中的第i个分组，0≤i≤L-1K=密钥；如果密钥的长度大于b，该密钥输入散列函数产生一个n比特的密钥；推荐密钥长度大于等于nK+=在K的左边填充0，使总长度等于bipad=将00110110重复b／8次opad=将01011010重复b／8次HMACHMACK=H[(K+

⊕opad)||H[(K+

⊕ipad)||M]]和ipad异或的结果是使K中一半的比特值反转。同样的opad异或的结果也是使K中一半的比特值反转，不同的是反转的比特不同。从效果上看，Si和So通过散列函数中的压缩函数将从K产生两个伪随机密钥。对于长消息，HMAC的执行时间近似等于嵌入散列函数的执行时间。HMAC增加了三个散列压缩函数（对Si、So和从内部散列函数产生的分组）的执行时间。对HMAC攻击成功的概率等价于对嵌入散列函数进行如下攻击中的一种：攻击者能够计算出压缩函数的输出，即使对攻击来说IV是随机的，秘密的和未知的。——攻击所需运算的数量级为2n。攻击者能够找到散列函数的碰撞，即使IV是随机的和秘密的。——攻击所需运算的数量级虽为2n/2，但由于密钥的存在，需要在线观察由同一个密钥产生的2n/2个分组，这在实际中是不可能的。HMAC1183.7数字签名（DigitalSignature）技术每天都在使用签名，如签订合同，在银行取款，批复文件等等，但这些都是手写签名。数字签名以电子方式存储签名消息，是在数字文档上进行身份验证的技术。数字签名是附加在数据单元上的一些数据，或是对数据单元所做的密码变换，这些数据变换允许数据的接受者用来确认数据单元来源和数据单元的完整性，并保护数据，防止被人伪造通过电子设备实现快速、远距离交易，用于商业系统。数字签名的要求类似于手写签名，数字鉴名也应满足以下要求：(1)收方能够确认或证实发方的签名，但不能伪造(2)发方发出签名的消息送收方后，就不能再否认他所签发的消息：(3)收方对已收到的签名消息不能否认，即有收到认证。(4)第三者可以确认收发双方之间的消息传送，但不能伪造这一过程。相比于MAC，数字签名可以支持不可否认服务121数字签名的特征签名是不可伪造的：数字签名证明是签名者本人而不是别人签署了文件签名是可信的：签名使文件的接受者相信签名者慎重的签署了该文件数字签名不能重复使用：签名是文件的一部分，任何人都不能把它转移到别的文件上签名后的文件是不能改变的签名是不可否认的：签名者不能事后声称他没有签署过文件数字签名的组成签名过程：包括数字签名生成算法，以及某种将数据编码成可签名消息的方法。验证过程：包括验证算法，以及某种将消息恢复数据的解码方法。数字签名的组成122基于公钥密码体制和私钥密码体制都可以获得数字签名，目前主要是基于公钥密码体制的数字签名，包括普通数字签名和特殊数字签名普通数字签名算法有RSA、ElGamal、Fiat-Shamir、Guillou-Quisquarter、Schnorr、Ong-Schnorr-Shamir数字签名算法、DES/DSA、椭圆曲线数字签名算法和有限自动机数字签名算法等特殊数字签名有盲签名、代理签名、群签名、不可否认签名、公平盲签名、门限签名、具有消息恢复功能的签名等，它与具体应用环境密切相关数字签名的执行方法123基于公钥密码体制的数字签名124BobAlice签名验证公共信道SKBPKBsigsig只有B知道SKB，能用它对消息进行签名。传输中无法篡改。任何第三方可以用PKB验证签名。基本实现方案12023/2/5125基于公钥密码体制的数字签名改进措施采用对称密码体制对签名进行加密保护只有知道该密钥的人才能对签名进行解密，进而可以验证签名并获得消息m的内容。

AB:Ek(ESK(m))MSEDVKKPKSKM公钥加密速度比较慢2023/2/5126基于公钥密码体制的数字签名基本方案2AB:m||ESK(h(m))Alice签名验证公共信道SKBPKBsigsigh(m)同时提供了消息完整性和消息源认证功能，由于h(m)具有数据压缩功能，使得签名处理的内容减少，速度加快。RSA数字签名2023/2/5127签名发送者签名接收者原始消息mSHA-1H(m)RSA加密算法A的私钥消息m摘要RSA解密算法消息m摘要A的公钥SHA-1H(m)H’(m)？2023/2/5128ElGamal签名方案该方案是由1985年提出的签名方案,其变型已被美国国家标准技术研究所采纳为数字签名算法(DSA)。DSA同时吸收了被称为schnorr签名方案的一些思想。ElGamal签名方案是一个随机化签名方案，他对任意长度的二元消息生成数字签名，且需要一个杂凑函数h:{0,1}Zp，其中p是大素数。2023/2/5129ElGamal签名方案ElGamal签名方案的密钥生成每个实体产生各自的公钥和相应私钥，实体A：2023/2/5130ElGamal签名方案ElGamal签名生成即使对同一个消息，不同的时间签名也不同2023/2/5131ElGamal签名方案ElGamal签名验证er×rs=

(αd)

αk×αkk-1{m-dαk}=αm公布于1994年5月19日的联邦记录上，并于1994年12月1日采纳为标准DSS。DSS最初只支持DSA签名算法，是ElGamal签名方案的改进。(目前的标准增加