消息认证和数字签名讲义课件

消息认证和数字签名中山大学信息科学与技术学院王常吉

副教授2006年11月.消息认证和数字签名消息认证（MessageAuthentication）验证所收到的消息确实是来自真正的发送方，并且未被篡改的消息的过程Hash函数（HashFunction）散列函数是以变长的报文作为输入，产生一个定长的散列值（也称消息摘要）作为输出.2|9/24/2020认证信息与网络安全系统一方面需要防范攻击者对系统进行被动攻击（采用加密机制来保护消息的机密性，使其不被破译），另一方面需要防范攻击者对系统进行主动攻击（如伪造，篡改信息等）。认证（authentication）是防止主动攻击的重要技术，它对于开放网络中的各种信息系统的安全性有重要作用，认证的目的：验证信息的发送者是真正的，而不是冒充的，此为信源识别；验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等.3|9/24/2020消息认证模型保密和认证是信息系统安全的两个方面，认证不能自动提供保密性，而保密性也不能自然提供认证功能。一个纯认证系统的模型如下图所示：窜扰者认证编码器认证译码器信道安全信道密钥源信宿信源.4|9/24/2020消息认证模型在这个系统中的发送者通过一个公开的无扰信道将消息发送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过篡改。系统中的密码分析者不仅要截收和破译信道中传送的密报，而且可伪造密文送给接收者进行欺诈，将其称为系统的窜扰者（tamper）更加合适。实际认证系统可能还要防止收方、发方之间的相互欺诈上述标出的认证编码器和认证译码器可抽象为认证函数一个安全的认证系统，首先要选好恰当的认证函数，然后在此基础上，给出合理的认证协议（AuthenticationProtocol）.5|9/24/2020消息认证模型消息认证和数字签名方法在功能上分为两层：下层中有产生认证符（一个用来认证消息的值）的函数，上层协议中将该函数作原语使接收方可以验证消息的真实性可用来产生认证符的函数可分为三类：消息加密：整个消息的密文作为认证符消息认证码MAC：它是消息和密钥的公开函数，产生一个固定长度的值作为认证符，MAC

=F（K，M）Hash函数：将任意长的消息映射为定长的Hash值的公开函数，以Hash值作为认证符.6|9/24/2020消息认证模型一个安全的消息认证系统，需满足意定的接收者能够检验和证实消息的合法性、真实性和完整性消息的发送者和接收者不能抵赖除了合法的消息发送者，其它人不能伪造合法的消息.7|9/24/2020消息加密（对称）消息加密本身提供了一种认证手段（消息的自身加密可以作为一个认证的度量）对称加密方式A与B共享密钥KA→B：EK[M]=CB：M=DK[C]，查看M是否为有意义的明文（如何区分真实的明文和随机的位串，解决的办法是强制明文具有某种结构）信源MEEk(M)DMKK信宿.8|9/24/2020消息加密（对称）提供保密：仅A与B共享密钥K提供一定程度的认证仅来自A传输中没有被更改要求明文具有某种易于识别，但不能复制且无需加密的的结构不提供签名接收人可以伪造报文发送人可以伪造报文.9|9/24/2020消息加密（非对称）KUb(B方的公钥)MEEKUb(M)DMKRb公钥加密：机密性MEEKRa(M)DMKRaKUa公钥加密：认证和签名.10|9/24/2020消息加密（非对称）MEEkRa(M)EEKUb(EkRa(M))KRaKUbDEkRa(M)DMKRbKUa公钥加密：机密性，可认证和签名.11|9/24/2020消息认证码MAC，也称密码校验和，是利用密钥来生成一个固定长度的短数据块，并将该数据块附加在消息之后假定通信双方A与B共享密钥K，A向B发送消息时，计算MAC=CK(M)，然后消息和MAC一起被发送给B，B对收到的消息用相同的密钥K进行相同的计算，得出新的MAC，并将接收到的MAC与B计算出的MAC进行对比，如果相等，则B可以相信消息未被篡改B可以相信消息来自真正的发送方A如果消息中含序列号，B可以相信消息的顺序正确.12|9/24/2020消息认证码MAC函数类似于加密函数，但不需要可逆性，因此在数学上比加密算法被攻击的弱点要少MAC的基本用途.13|9/24/2020消息认证码.14|9/24/2020消息认证码为什么使用消息认证码保密性与真实性是两个不同的概念，从根本上讲，信息加密提供的是保密性而非真实性加密代价大（公钥算法代价更大）认证函数与保密函数的分离能提供功能上的灵活性认证码可延长报文的保护期限，同时能处理报文内容(使用加密，当报文解密后，保护就失效了)某些信息只需要真实性，不需要保密性广播的信息难以使用加密（信息量大）网络管理信息等只需要真实性政府/权威部门的公告.15|9/24/2020消息认证码对MAC的安全要求如果一个攻击者得到M和CK(M)，则攻击者构造一个消息M-，使得CK(M-)=CK(M)应在计算上不可行CK(M)应均匀分布，即随机选择消息M和M-

，CK(M)=CK(M-)的概率是2-n，其中n是MAC的位数MAC值应平等地依赖于消息中的所有位，令M-

为M的某些变换，即M-=f(M)，例如f可以涉及M中一个或多个给定位的反转），在这种情况下，Pr[CK(M-)=CK(M)]=2-n.16|9/24/2020消息认证码DataAuthenticationAlgorithmFIPSpublication(FIPSPUB113)ANSIstandard(X9.17)有两种使用广泛的基于DES的MAC，一种按CFB模式，一种按CBC模式运行。在CBC模式下，消息按64bit分组，不足时以0补齐，初始向量为0，送入DES系统加密，但不输出密文，只取加密结果最左边的r位作为认证符，r取大小可由通信双方约定。美国联邦电信建议采用24bit[FTSC-1026]，而美国金融系统采用32bit[ABA，1986].17|9/24/2020哈希函数H（M）:输入为任意长度的消息M，输出为一个固定长度的散列值，称为消息摘要（MessageDigest），该散列值是消息M的所有位的函数并提供错误检测能力（消息中的任何一位或多位的变化都将导致该散列值的变化）又称为哈希函数、散列函数、数字指纹（Digitalfingerprint）、压缩（Compression）函数、紧缩（Contraction）函数、数据认证码DAC（Dataauthenticationcode）、篡改检验码MDC（Manipulationdetectioncode）.18|9/24/2020哈希函数H可应用于任意大小的数据块H产生定长的输出对于任意给定的x，容易计算出H（x）H是单向（one-way）函数给定h，找到满足h=H（x）的x在计算上是不可行的complexityoffindingxoutofhis2n，wherenisthenumberofbitsinthehashoutput抗弱碰撞性（Weakcollisionresistance）对于任意给定的x，找到满足x≠y且H（x）=H（y）的y在计算上是不可行的complexityofattackis2n.19|9/24/2020哈希函数强抗碰撞性（Strongcollisionresistance）找到任何满足H（x）=H（y）的偶对（x，y）在计算上是不可行的complexityis2n/2前三条是Hash函数实际应用于消息认证中所必须满足的，第四条单向性是指，由消息很容易计算出Hash码，但由Hash码却不能计算出相应的消息，第五条性质是保证不能找到与给定消息具有相同Hash值的另一消息，可以在使用时对Hash值加密的方法中防止伪造，第六条性质涉及Hash函数抗生日攻击的能力强弱.20|9/24/2020哈希函数分类根据安全水平弱无碰撞强无碰撞注：强无碰撞自然含弱无碰撞！根据是否使用密钥带秘密密钥的Hash函数：消息的散列值由只有通信双方知道的秘密密钥K来控制，此时散列值称作MAC不带秘密密钥的Hash函数：消息的散列值的产生无需使用密钥，此时散列值称作MDC.21|9/24/2020哈希函数-生日攻击如果采用传输加密的散列值和不加密的报文M，攻击者需要找到M-，使得H(M-)=H(M)，以便使用替代报文来欺骗接收者一种基于生日悖论的攻击可能做到这一点，生日问题一个教室中，最少应有多少个学生，才使至少有两人具有相同生日的概率不小于1/2？概率结果与人的直觉是相违背的实际上只需23人，即任找23人，从中总能选出两人具有相同生日的概率至少为1/2.22|9/24/2020生日攻击实例A准备两份合同M和M-，一份B会同意，一份会取走他的财产而被拒绝A对M和M-

各做32处微小变化（保持原意），分别产生232个64位hash值根据前面的结论，超过0.5的概率能找到一个M和一个M-

，它们的hash值相同A提交M，经B审阅后产生64位hash值并对该值签名，返回给AA用M-

替换MHash必须足够长（128，160，224，256，…）.23|9/24/2020Hash函数和MAC的安全性穷举攻击对MAC的穷举攻击由于需要知道消息-MAC对，穷举攻击更加困难密码分析理想的Hash函数和MAC算法要求密码分析供给所需的代价大于或等于穷举攻击所需的代价单向性2n抗弱碰撞性2n抗强碰撞性2n/2.24|9/24/2020哈希函数的构造Merkle于1989年提出通用的迭代结构构造Hash函数，几乎被所有hash函数使用RonRivest于1990年提出MD4具体做法:把原始消息M分成一些固定长度的块Yi最后一块padding并使其包含消息M长度设定初始值CV0压缩函数f，CVi=f(CVi-1,Yi-1)最后一个CVi为hash值.25|9/24/2020哈希函数的通用结构.26|9/24/2020常用的Hash算法几种重要的Hash函数MD5SHA-1RIPEMD-160消息认证码HMAC.27|9/24/2020MD5Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年，RonRivest提出MD5（RFC1321）在最近数年之前，MD5是最主要的hash算法现行美国标准SHA-1以MD5的前身MD4为基础输入：任意长度消息输出：128bit消息摘要处理：以512bit输入数据块为单位.28|9/24/2020SHA1992年NIST制定了SHA（128位）1993年SHA成为标准（FIPSPUB180）1994年修改产生SHA-1（160位）1995年SHA-1成为新的标准，作为SHA-1（FIPSPUB180-1/RFC3174），为兼容AES的安全性，NIST发布FIPSPUB180-2，标准化SHA-256，SHA-384和SHA-512输入：消息长度<264输出：160bit消息摘要处理：以512bit输入数据块为单位基础是MD4.29|9/24/2020哈希函数MD5SHA-1RIPEMD-160Digestlength128bits160bits160bitsBasicunitofprocessing512bits512bits512bitsNumberofsteps64(4roundsof16)80(4roundsof20)160(5pairedroundsof16)Maximummessagesize∞264-1bits∞.30|9/24/2020参考网址山东大学信息安全实验室/hash.htmNISTSecureHashPages/cryptval/shs.htm/CryptoToolkit/tkhash.html.31|9/24/2020消息认证的局限性消息认证可以保护信息交换双方不受第三方的攻击，但是它不能处理通信双方的相互攻击信宿方可以伪造消息并称消息发自信源方，信源方产生一条消息，并用和信源方共享的密钥产生认证码，并将认证码附于消息之后信源方可以否认曾发送过某消息，因为信宿方可以伪造消息，所以无法证明信源方确实发送过该消息在收发双方不能完全信任的情况下，引入数字签名来解决上述问题数字签名的作用相当于手写签名.32|9/24/2020数字签名在公钥体制中，用接受者的公钥加密消息得到密文，接受者用自己的私钥解密密文得到消息。加密过程任何人都能完成，解密过程只有接受者能够完成。考虑一种相反的过程，发送者用自己的私钥“加密”消息得到“密文”，然后利用发送者的公钥“解密”密文得到消息。很显然，加密只有发送者能够完成，而解密任何人都可以完成。所以，任何人都可相信是特定的发送者产生了该消息，这就相当于“签名”，证明一个消息的所属.33|9/24/2020数字签名随着计算机通信网的发展，人们希望通过电子设备实现快速、远距离的交易，数字(或电子)签名法应运而生，并开始用于商业通信系统，如电子邮递、电子转账和办公自动化等系统。随着计算机网络的发展，过去依赖于手书签名的各种业务都可用这种电子数字签名代替，它是实现电子贸易、电子支票、电子货币、电子购物、电子出版及知识产权保护等系统安全的重要保证.34|9/24/2020数字签名传统签名的基本特点与被签的文件在物理上不可分割签名者不能否认自己的签名签名不能被伪造容易被验证数字签名是传统签名的数字化能与所签文件“绑定”签名者不能否认自己的签名容易被自动验证签名不能被伪造.35|9/24/2020数字签名数字签名必须具有下述特征收方能够确认或证实发方的签名，但不能伪造，简记为R1-条件（unforgeable）发方发出签名的消息给收方后，就不能再否认他所签发的消息，简记为S-条件(non-repudiation)收方对已收到的签名消息不能否认，即有收报认证，简记作R2-条件第三者可以确认收发双方之间的消息传送，但不能伪造这一过程，简记作T-条件.36|9/24/2020数字签名与手书签名的区别：手书签名是模拟的，且因人而异。数字签名是0和1的数字串，因消息而异与消息认证的的区别：消息认证使收方能验证消息发送者及所发消息内容是否被窜改过。当收发者之间没有利害冲突时，这对于防止第三者的破坏来说是足够了。但当收者和发者之间有利害冲突时，就无法解决他们之间的纠纷，此时须借助满足前述要求的数字签名技术与消息加密区别：消息加密和解密可能是一次性的，它要求在解密之前是安全的；而一个签名的消息可能作为一个法律上的文件，如合同等，很可能在对消息签署多年之后才验证其签名，且可能需要多次验证此签名。因此，签名的安全性和防伪造的要求更高些，且要求证实速度比签名速度还要快，特别是联机在线实时验证.37|9/24/2020数字签名根据签名的内容分对整体消息的签名对压缩消息的签名按明、密文的对应关系划分确定性(Deterministic)数字签名，其明文与密文一一对应，它对一特定消息的签名不变化，如RSA、Rabin等签名；随机化的(Randomized)或概率式数字签名.38|9/24/2020数字签名算法普通数字签名算法RSAElGamal/DSS/DSAECDSA盲签名算法群签名算法.39|9/24/2020RSA签名方案密钥的生成（同加密系统）公钥Pk={e,n}；私钥Sk={d,n}签名过程(用私钥d,n)明文：M<n密文：S=Mdmodn验证过程(用公钥e,n)给定M，S，Ver(M,S)为真，当且仅当M=Semodn安全性由于只有签名者知道d，其他人不能伪造签名，但可易于证实所给任意（M，S）对是否是消息M和相应签名构成的合法对.40|9/24/2020数字签名标准美国国家标准与技术研究所NIST发布的联邦信息处理标准FIPS186，称为数字签名标准DSS(DigitalSignatureStandard)于1991年最初提出，1994年12月1日采纳为标准DSS，2000年发布DSS的扩充版，即FIPS186-2DSS为EIGamal和Schnorr签名方案的改进，其使用的算法记为DSA（DigitalSignatureAlgorithm)。此算法由D.W.Kravitz设计。DSS使用了SHA，安全性是基于求离散对数的困难性只能用于数字签名，不能用于加密或密钥分配安全性基于基于离散对数难题DSS是一个产生签名比验证签名快得多的方案，验证签名太慢！.41|9/24/2020DSA算法描述全局公钥（p，q，g）p为512～1024bit的大素数，q是（q－1）的素因子，为160比特的素数g=h(p-1)/qmodp，且1<h<(p-1)，使得h(p-1)/qmodp>1用户私钥x：x为0<x<q内的随机数用户公钥y：y=gxmodp.42|9/24/2020DSA算法描述用户每个消息用的秘密随机数k：0<k<q签名过程：对报文M，签名为（r，s）r=(gkmodp)modqs=(k-1(H(M)+xr))modq验证：w＝s-1modqa=(H(M)w)modqb=rwmodqv=((gayb)modp)modqVer（M，r，s）＝真iffv=r.43|9/24/2020数字签名标准针对DSS的主要批评意见有：DSA不能用于加密或密钥分配DSA由NSA开发的，算法中可能设有陷门

DSA比RSA慢

RSA已是一个实际上标准，DSS与现行国际标准不相容

DSA未经公开选择过程，还没有足够的时间进行分析证明DSA可能侵犯了其它专利（Schnorr签名算法，Diffie-Hellman算法由512bit所限定密钥量太小，现已改