《密码学基础》课件 （张薇） 第5-7章　公钥密码与RSA、数字签名、消息认证与Hash函数

公钥密码学与RSA6学时对称密码的弱点及公钥密码的原理MH背包公钥密码Diffie-Hellman密钥交换RSA密码主要内容密钥量大密钥管理困难：传递、换发、保存无法实现网络中的签名、认证等应用对称密码的弱点第一节公钥密码的原理密钥量大对称密码的弱点设系统中共有n个用户，两两进行保密通信，总共需要多少个密钥？当n=5时，C（5，2）=10当n=1000时，C（1000，2）=499500密钥量大对称密码的弱点设系统中共有n个用户，两两进行保密通信，每个用户有多少个密钥？n-1个密钥管理困难对称密码的弱点对称密码的弱点无法适应网络应用数字签名身份认证消息认证公钥密码的原理基本原理使用两个不同的密钥，一个用于加密，一个用于解密用于加密的密钥Ek可以公开，用于解密的密钥Dk保密Ek与Dk之间有联系，但不能由Ek很容易地算出Dk公钥密码的原理加密与解密公钥密码的原理c=Ek(m)m=Dk(c)公钥密码的优点密钥数量大大减少密钥管理方便公钥密码的原理公钥密码的安全性公钥密码的原理计算复杂性理论公钥密码的原理如何构造陷门单向函数：利用困难问题背包问题离散对数问题整数分解问题椭圆曲线离散对数问题公钥密码的原理典型公钥密码背包密码RSA密码Rabin密码ElGamal密码椭圆曲线密码背包密码1978年，Merkle和Hellman提出了基于背包问题的公钥密码体制。如何解决背包问题：穷举法背包问题当物品个数为100时，有2100≈1.27×1030种可能性。把全世界所有的5亿台计算机全部联网来求解这个问题，需要1000万年！

背包密码的安全性破译方法： Shamir方法 L3格基归约方法：由AKLenstra,HWLenstra&LLovasz提出

Lagarias-Odlyzko-Brickell的方法Diffie-Hellman密钥交换功能：在没有秘密信道的情况下，让两个用户共享一个秘密密钥理论基础：离散对数问题方法：利用用户的公钥和私钥Diffie-Hellman密钥交换计算Diffie-Hellman问题（CDH问题）：已知ga和gb，计算gab如果CDH问题是容易的，则gab可以由p,g,ga,gb计算得到。背景数学基础加密解密过程安全性及应用第二节RSA密码复习：欧拉定理

如果a,n互素，则有a

Ф(n)≡1modn设n=pq,p,q均为素数，且a,n互素，则Ф(n)=(p-1)(q-1)aФ(n)=a

(p-1)(q-1)≡1modn

第二节RSA密码

选择p,qp,q均为素数且p≠q

计算n=pq

计算Ф(n)=(p-1)(q-1)

选择e1<e<Ф(n)且gcd(e,Ф(n))=1

计算dd≡e-1modФ(n)

公开n,e

保密d系统构造对明文m=374加密计算c≡memodn≡37431mod2173=446解密：计算cd≡446671mod2173=374RSA：Example选择p=53,q=41,n=pq=2173,Ф(n)=2080选择e=31,计算出d=671将n,e公开，d保密加密：模幂运算解密：模幂运算正确性：欧拉定理安全性：分解大整数参数选择RSA小结数字签名4学时

数字签名的概念数字签名与手写签名的区别数字签名的特征

数字签名的原理数字签名分类

直接数字签名仲裁数字签名主要内容数字签名(DigitalSignature)：以电子化形式，使用密码方法，在数字消息中嵌入一个秘密信息，以验证这个秘密信息是否正确来达到识别的目的，其实质是一种密码变换。第一节数字签名概述手写签名的特点：

(1)签名不可伪造。签名中包含了签名者个人所特有的一些信息，如写字习惯、运笔方法等，是别人很难仿造的。

(2)签名不可重用。一个签名只能对一份文件起作用，不可能移到别的不同的文件上。第一节数字签名概述手写签名

(3)文件内容不可改变。在文件签名后，文件的内容就不能再变。

(4)签名不可抵赖。签名和文件都是物理的实体，签名者不能在签名后还声称他没签过名。手写签名应用：网络中的身份认证和消息认证。特征：

(1)不可否认性：签名者事后不能否认。

(2)可验证性：接收者能验证签名，而任何其他人都不能伪造签名。

(3)可仲裁性：当双方发生争执时，可以由一个公正的第三方出面解决争端。第一节数字签名概述数字签名的特征构成：签名者、验证者、密钥、算法、待签名消息签名系统的参数包括：

——消息空间M，所有可能的消息的集合

——签名空间S，所有可能的签名的集合

——密钥空间K，所有可能的密钥的集合

——签名者的密钥，包括公钥pK和私钥sK两部分

——算法：保密的签名算法S(.)和公开的验证算法V(..)第一节数字签名概述数字签名的原理(1)A→B：EKRa(M)提供鉴别与签名只有A具有KRa传输中没有被篡改任何第三方可以用KUa验证签名(1’)A→B：EKUb[EKRa(M)]

提供保密、鉴别与签名第一节数字签名概述直接数字签名（DSS）(2)A→B：M||EKRa[H(M)]

提供鉴别及数字签名H(M)受到密码算法的保护只有A能够生成EKRa[H(M)](2’)A→B：EKUb[M||EKRa(H(M))]

提供保密性、鉴别和签名第一节数字签名概述直接数字签名（DSS）验证模式依赖于发送方的保密密钥发送方要抵赖发送某一消息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名对策：要求被签名的信息包含一个时间戳（日期与时间），并要求将已暴露的密钥报告给一个授权中心X的某些私有密钥确实在时间T被窃取，敌方可以伪造X的签名及早于或等于时间T的时间戳第一节数字签名概述直接数字签名的缺点引入仲裁者所有从发送方X到接收方Y的签名消息首先送到仲裁者A，A将消息及其签名进行一系列测试，以检查其来源和内容，然后将消息加上日期并与已被仲裁者验证通过的指示一起发给Y。第一节数字签名概述仲裁数字签名（ADS）当X否认时，通过以下方法解决纠纷：

Y：向A发送EKay[IDx||M||EKax[IDx||H(M)]]

A：用Kay恢复IDx，M，和签名（EKax[IDx||H(M)]），然后用Kax解密签名并验证散列码第一节数字签名概述仲裁数字签名（ADS）Y不能直接验证X的签名，Y认为消息正确，只因为它来自A。因此，双方都需要高度相信A:X必须信任A没有暴露Kax，并且没有生成错误的签名

Y必须信任A仅当散列值正确并且签名确实是X产生的情况下才发送消息（2）双方都必须信任A能公正地处理争议第一节数字签名概述仲裁数字签名（ADS）(b)单密钥加密方式，消息对仲裁者不可见

(1)XA：IDx||EKxy[M]||EKax[IDx||H(EKxy[M])] (2)AY：EKay[IDx||EKxy[M]||EKax[IDx||H(EKxy[M])]||T]X与Y之间共享密钥Kxy

第一节数字签名概述仲裁数字签名（ADS）(c)公钥加密方式，消息对仲裁者不可见

(1)XA：IDx||EKRx[IDx||EKUy(EKRx[M])] (2)AY：EKRa[IDx||EKUy[EKRx[M]]||T]X：对消息M双重加密：首先用X的私有密钥KRx，然后用Y的公开密钥KUy。双重加密的消息对A以及对除Y以外的其它人都是保密的。A：检查X的公开/私有密钥对是否仍然有效，是则确认消息。第一节数字签名概述仲裁数字签名（ADS）(c)与(a)(b)相比具有以下好处：

1、在通信之前各方之间无须共享任何信息，从而避免了联手作弊；

2、即使KRx暴露，只要KRa未暴露，就不会有时间戳不正确的消息被发送；

3、从X发送给Y的消息的内容对A和任何其他人是保密的。第一节数字签名概述仲裁数字签名（ADS）掌握数字签名的基本概念理解数字签名的特征理解数字签名的原理及分类方法小结数字签名算法第二节RSA签名算法ElGamal签名算法DSA概述DSA签名过程主要内容Alice的公开密钥：nA,eA；秘密密钥：dA；消息m签名算法：验证算法：Alice要对秘密信息签名时，先用私钥计算签名，再用公钥加密。第二节常见签名算法RSA签名签名：对信息m签名时，首先选取随机数k(1≤k≤p-2)，k与p-1互素，计算

r=gk

modps=k-1(m-xr)modp-1或m=xr+ksmodp-1验证：验证者A验证等式是否成立：gm=yrrs

modp

若正确，则(r，s)为m的合法签名，否则为非法签名。第二节常见签名算法ElGamal签名1991年美国国家标准局NIST将数字签名算法DSA作为其数字签名标准(DigitalSignatureStandard，DSS)，DSA是ElGamal数字签名算法的变形。使用了安全散列函数SHA-1，以长度小于264bits的明文作为输入，产生160bit的消息摘要作为DSA的输入。验证签名时必须使用相同的散列函数。数字签名算法DSA签名：对明文m

(1,q)，签名者选取随机整数k，1≤k≤p-2且k与p-1互素，计算r=(gk

modp)modqs=k-1(H(m)+xr)modq其中kk-1modq≡1(r，s)即为消息m的数字签名。数字签名算法DSA验证：计算w=s-1modq

u1=H(m)wmodqu2=rwmodqv=[(gu1yu2)modp]modq检验v=r是否成立。数字签名算法DSA签名者对消息m=1234签名：选择随机数k=50，得k-1(mod101)=99计算签名：r=(17050(mod7879)(mod101)=2518(mod101)=94s=(1234+75*94)99(mod101)=97签名为(1234,94,97)Example数字签名算法DSA掌握RSA签名算法掌握ElGamal签名算法理解随机数在签名中的作用理解DSA签名过程小结椭圆曲线签名第三节ECDSA算法ECDSA中的阈下信道ECDSA算法的变形主要内容ECDSA(EllipticCurveDigitalSignatureAlgorithm)——DSA算法在椭圆曲线上的模拟。1992年，作为NIST所征集的DSS候选算法之一，ScottVanstone提出了ECDSA算法。后来被各标准化组织广泛接受，1998年被ISO作为ISO14888-3标准，1999年被ANSI作为ANSIX9.62标准，2000年被IEEE作为IEEE1363-2000标准，同年被FIPS作为FIPS186-2标准。ECDSA简介1.方案建立设U为签名方，V为验证方：(1）U建立椭圆曲线域参数T=(p，a，b，G，n，h)；(2）U建立自己的密钥对（dU,QU），QU

=dUG；(3）U选择一个Hash函数；(4）U

通过可靠的方式将所选择的Hash函数和建立的椭圆曲线域参数T传递给V。算法描述2.签名算法(1）选择临时密钥对(k，R)，其中R=kG=(xR，yR)与域参数T相关(2）令r=xR

(modn)，如果r=0,返回1(3）计算待签消息的hash值H=Hash(M)，将H转换成整数e(4）计算s

k-1(e+rdU)(modn)，如果s=0,返回1(5）输出S=(r，s)为数字签名算法描述3.验证算法(1）如果r,s

[1,n-1],验证失败(2）计算待签消息的hash值H=Hash(M)，将H转换成整数e(3）计算u1

es-1(modn)，u2

rs-1(modn)(4）计算R=(xR，yR)=u1G+u2QU，如果R=O,验证失败(5）令v=

xR

(modn)，如果v=r，验证成功，否则验证失败算法描述对ECDLP的攻击ECDSA算法的安全性基于ECDLP问题的困难性。如果一种攻击能够从签名者U的公钥恢复出私钥，攻击者就可以伪造出U对任何消息的数字签名。目前，当基点的阶为大素数时，素数域上的ECDLP是不可解的。对密钥生成的攻击在密钥生成过程中用到了秘密随机或伪随机数，不安全的随机或伪随机数生成器将直接导致密码被攻破。攻击思路对哈希函数的攻击签名和验证阶段使用的哈希函数必须具备单向和抗冲突的特性。如果哈希函数不能抵抗冲突，攻击者可能会发现消息(M1;M2)的碰撞，在U对消息M1签名后可以伪造出对消息M2的签名。基于无效域参数和无效公钥的攻击ECDSA的安全性依赖于U使用的有效域参数，无效的域参数对Pohlig-Hellman攻击不免疫。U应该确保所采用的域参数是有效的。V在验证之前也应该检验这些参数的有效性。攻击思路阈下信道——在密码协议中，存在一些特殊的编码方法或数学结构，可以用于传输秘密消息。阈下信道主要存在于数字签名和认证协议中。签名者（发送方）可以将秘密信息隐藏在数字签名之中，验证者（接收方）通过事先约定的某种协议或参数恢复出阈下信息，这种秘密通信方式很难被第三方检测到。与一般的加密传输相比，阈下信道具有更高的安全性。ECDSA中的阈下信道如果签名中的附加数据量为αbit，其中βbit用来保证签名的安全性，则理论上最大可以传递α-β

bit的阈下信息。利用了全部或几乎全部α-βbit的附加数据的阈下信道为宽带阈下信道，只利用了一小部分的为窄带阈下信道。恢复阈下信息时需要签名者密钥的方式定义为方式I，不需要的定义为方式Ⅱ。在方式I中，签名者的密钥同时也是该阈下信道的恢复密钥。ECDSA中的阈下信道在ECDSA中，由于s

k-1

(e+rdU)(modn)，可得k

s-1

(e+rdU)(modn)，（r,s）和e为签名对于验证者V来说，只要事先知道签名者U的私钥dU就可以恢复出k来。于是以k作为阈下信息，可以实现方式I的阈下信道。ECDSA中的阈下信道在数字签名协议中补充以下步骤，就能设计出阈下通信协议：信道建立U为发送方，V为接收方:(1）U执行方案建立协议。建立参数T,(dU,QU),Hash。(2）U将私钥dU,秘密传输给V。ECDSA中的阈下信道阈下信息隐藏(1）U对秘密消息编码，得到一整数k。(2）U建立临时密钥对(k，R)，其中R=kG=(xR，yR)和域参数T相关。(3）U执行以上签名算法。ECDSA中的阈下信道阈下信息恢复(1）V执行验证协议。(2）V计算

k

s-1(e+rdU)(modn)，恢复阈下信息。(3)V对k解码恢复原始的秘密信息。ECDSA中的阈下信道ECDSA算法中的签名附加数据量为（logn+logp）bit，而阈下信息k为lognbit，该信道是一种宽带信道。按照目前对椭圆曲线参数的安全要求，通过这个信道可传输192bit以上的阈下信息。ECDSA中的阈下信道签名算法(1）选择临时密钥对(k，R)，其中R=kG=(xR，yR)和域参数T相关。(2）令r=xR(modn)，如果r=0,返回1。 (3）计算待签名消息的hash值H=Hash(M)，将H转换成整数e。(4）计算s

dU-1(rk-e)(modn)，如果s=0,返回1。(5）输出S=(r，s)为数字签名。ECDSA算法的变形一验证算法(1）如果r,s

[1,n-1],验证失败。(2）计算待签消息的hash值H=Hash(M)，将H转换成整数e(3）计算u1

er-1(modn),u2

sr-1(modn)(4）计算R=(xR，yR)=u1G+u2QU，如果R=O,验证失败。(5）令v=

xR(modn)，如果v=r,验证成功，否则验证失败。这个改进方案中，可以预计算dU-1，将计算结果存储下来作为签名参数，在每次签名时模乘dU-1即可，于是模逆转化为模乘，运算量将减小。ECDSA算法的变形一签名算法(1）选择临时密钥对(k，R)，其中R=kG=(xR，yR)和域参数T相关；(2）令r=xR(modn)，如果r=0,返回1；(3）计算待签名消息的hash值H=Hash(M)，将H转换成整数e；(4）计算s

k(e+rdU)-1(modn)，如果s=0,返回1；(5）S=(r，s)作为数字签名。ECDSA算法的变形二验证算法(1)如果r,s

[1,n-1],验证失败；(2)计算待签名消息的hash值H=Hash(M)，将H转换成整数e；(3)计算u1

es(modn),u2

rs(modn)；(4)计算R=(xR，yR)=u1G+u2QU，如果R=O,验证失败。(5)令v=

xR(modn)，如果v=r,验证成功，否则验证失败。ECDSA算法的变形二掌握ECDSA签名过程理解阈下信道的含义理解如何在ECDSA中利用阈下信道进行信息隐藏了解ECDSA的两种变形小结第四节盲签名三、盲签名的原理及典型算法(重点)二、盲签名的产生背景----电子投票主要内容：一、盲签名的基本概念盲签名

盲签名:是一类特殊的数字签名,消息持有者希望签名者对他的消息作数字签名，但又不想让签名看到消息的真实内容。一、盲签名的基本概念1、远程匿名投票20世纪80年代，密码学家DavidChaum就建立过一个远程匿名投票模型设立一个选举委员会，其职责为：

规定选票格式。

确认选民身份。

统计选票。二、电子投票问题（盲签名产生的背景）条件：所有投票人散居各城市，无法集中，利用普通邮政系统投票。选民选委会资格审查票数统计

①②⑤③④

1、远程匿名投票

二、电子投票问题（盲签名产生的背景）用电子手段解决以下三个关键问题：（1）如何使选委会看不到选票内容？（2）选举委员会如何盖章？（3）选民如何确认收回的选票没有被做上记号？2、电子投票二、电子投票问题（盲签名产生的背景）1、盲签名的特性（1）签名人看不到所签的“文件内容”。（2）签名人无法建立文件与他的签名之间的联系。三、盲签名的原理及算法消息持有者签名者MS=S(M)M=B(M)S=B-1(S

)

2、盲签名的原理盲化盲签名解盲

消息持有者希望签名者对他的消息作数字签名，但又不想让签名者看到消息的真实内容。三、盲签名的原理及算法1.不可伪造性除了签名者本人外，任何人都不能以他的名义生成有效的盲签名。2.不可抵赖性签名者签署了某个消息后将无法否认自己对消息的签名。3.盲性签名者不可能得到消息的具体内容。4.不可跟踪性一旦消息的签名公开后，签名者不能确定自己何时签署的这条消息。一个好的盲签名算法应该具有以下的性质：

三、盲签名的原理及算法3、基于RSA密码的盲签名算法（1）参数选取（同RSA公钥密码）：选定p,q为大素数，计算n=pq。选取秘密密钥d，要求gcd(d,φ(n))=1。计算e,满足de=1modφ(n)。

e,n

公开，其它参数均保密。三、盲签名的原理及算法RSA数字签名过程AliceBobn,epublicdprivates≡md

modngcd(m,n)=1m≡se

modnsSetp1:选定M，随机数R。计算M

=ReM

modn签名者消息持有者Setp2:计算S

=M

d

modnStep3:S=R-1S

modn

=M

dmodnStep4:验证

Semodn？=M（2）签名算法三、盲签名的原理及算法（3）分析MM

(M,S)(M

，S

)

签名人对签的“文件内容”是看不见的。即使公布文件内容，签名人也不能把文件与他所作的签名联系起来。

三、盲签名的原理及算法（4）与普通RSA签名比较MS=M

dmodnRSA签名RSA盲签名M?=S

emodnS

=M

dmodnM?=S

emodnMM

S=R-1S

modn三、盲签名的原理及算法1.密钥的长度；2.盲签名的长度；3.盲签名的算法和验证算法。盲签名的可操作性和实现速度取决于：三、盲签名的原理及算法4、盲签名技术的应用现状（1）匿名电子投票系统（2）电子商务系统中的匿名支付

Microsoft公司的eWallet系统。三、盲签名的原理及算法主要内容：（1）盲签名的基本概念（2）盲签名的产生背景。（3）基于RSA密码的盲签名算法。

四、小结及相关问题第五节代理签名代理签名的含义及特点代理签名的分类M-U-O代理签名方案主要内容代理签名：签名者可以授权他人代理自己，由被指定的代理签名者代表原始签名者生成有效的签名。1996年，Mambo、Usuda和Okamoto首先提出了代理签名的概念。代理签名系统中的参与者：原始签名者获得授权执行签名的一个或多个代理签名者验证者第五节代理签名代理签名应满足三个基本条件验证者能够像验证原始签名者的签名那样来验证代理签名；能够容易区分代理签名和原始签名；原始签名者对代理签名者所作的代理签名不可否认。代理签名的特点第五节代理签名Mambo、Usuda和Okamoto把代理签名分为三类：完全代理签名、部分代理签名和具有证书的代理签名。完全代理签名(fulldelegation)：原始签名者通过可靠途径直接把自己的签名密钥分发给代理签名者，代理签名者产生的签名与原始签名者所产生的签名完全相同。代理签名的分类第五节代理签名部分代理签名(partialdelegation)，原始签名者用自己的签名密钥生成代理签名密钥s，然后将代理签名密钥通过可靠途径分发给代理签名者。要求：代理签名者不能由自己所获得的代理签名密钥推算出原始签名者的签名密钥。又可分为两种：代理非保护代理签名和代理保护代理签名。代理签名的分类第五节代理签名具有证书的代理签名(delegationbywarrant)，分两种类型：授权代理签名和持票代理签名。授权代理签名(delegateproxy)：原始签名者用他的签名密钥使用普通的签名方案签一个文件（证书），然后把产生的证书发给代理签名者。持票代理签名(bearerproxy)：证书由消息部分和原始签名者对新产生的公钥的签名组成。原始签名者把新产生的公钥所对应的私钥以安全的方式发给代理签名者。代理签名的分类第五节代理签名代理签名又可分为强代理签名和弱代理签名。强代理签名——代理签名不仅能够代表原始签名者的签名，也能代表代理签名者的签名；弱代理签名——代理签名只代表原始签名者的签名。代理签名的分类第五节代理签名2学时消息认证与Hash函数——公钥密码的应用消息认证概述认证函数消息认证码Hash函数和MAC的安全性Hash算法主要内容机密性（Confidentiality）：确保信息不暴露给未经授权的人或应用进程。完整性（Integrity）：只有得到允许的人或应用进程才能修改数据，并且能够判别出数据是否已被更改。可用性（Availability）：只有得到授权的用户在需要时才可以访问数据，即使在网络被攻击时也不能阻碍授权用户对网络的使用。三种基本安全需求认证系统由认证编码器和认证译码器组成条件：指定的接收者能检验和证实消息的合法性、真实性和完整性发送者和接收者不能抵赖除了合法的发送者，其它人不能伪造消息认证系统第一节消息认证认证函数的特点：必须是单向函数对于一个特定消息，很难找到另外一个消息与其具有相同的认证码很难找到一对具有相同认证码的消息认证函数第一节消息认证认证函数可分为三类：消息加密：将整个消息的密文作为认证符；消息认证码（MAC）：是消息和密钥的公开函数，产生定长的认证符；Hash函数：将任意长的消息映射为定长的hash值的公开函数，该hash值则作为认证符。认证函数第一节消息认证消息认证码（MessageAuthenticationCode）：利用密钥生成固定长度的短数据块（MAC），将其附加在消息之后，也称为密码校验和（cryptographicchecksum）。MAC函数与加密的区别：不要求可逆性多对一不能用于数字签名第一节消息认证用消息认证码实现认证通过MAC，可以认证以下内容：

a.接收者可以确信所收到的消息M未被篡改；

b.接收者可以确信消息来自真实的发送者；

c.如果消息中包含顺序码(如X.25,TCP)，接收者可以确认消息的正常顺序。消息认证码第一节消息认证已知M和Ck(M)时，构造满足Ck(M’)=Ck(M)的消息M’在计算上不可行；Ck(M)应是均匀分布的，即对任何随机选择的消息M和M’，Ck(M’)=Ck(M)的概率是2-n，其中n是MAC的位数；设M’是M的某个已知的变换，即M’=f(M)，例如可令f

表示对M的一位或多位取反，那么

Pr[Ck(M’)=Ck(M)]=2-n

对MAC的要求第一节消息认证十进制移位加MAC算法

1980年，Sievi提出，称为十进制移位加算法(DecimalShiftandAddAlgorithm)简记为DSA，适用于金融支付中的数值消息交换业务，消息按十位十进制数字分段处理，不足十位时在右边以0补齐基于DES的MAC算法

两种：CBC模式和CFB模式。CBC模式是使用最广泛的一种，被美国作为数据认证算法(DataAuthenticationAlgorithm)，已被FIPS(FIPSPUB113)和ANSI(X9.17)作为标准。MAC算法第一节消息认证消息按64bit分组M1,M2,…,MN，不足时以0补齐，DES加密，设密钥为K，初始向量为0，计算如下：

O1=EK(M1)

O2=EK(M2XORO1)

O3=EK(M3XORO2) …

ON=EK(MNXORON-1)取加密结果最左边的r位作为认证码。r的大小由通信双方约定。第二节消息认证码MAC算法——CBC模式散列函数（HashFunction）：也称哈希函数，对任意长度的明文进行变换，得到相对应的函数值，称为散列值，或称散列值、消息摘要（MessageDigest）、指纹（Fingerprint），变换的过程称为散列变换。散列值的长度一般是固定的。用途：（1）消息鉴别码；（2）数字签名之前的预处理第二节散列函数第二节散列函数要求：对任意长度输入进行变换，得到固定长度输出求逆不可行对给定x，很难找到x’≠x，使得h(x’)=h(x)很难找到一对不同的x,x’，使得h(x’)=h(x)第二节散列函数对hash函数的要求满足条件（1）（2）的称之为单向散列函数(One-WayHashFunction)满足条件（1）~（3）的称之为弱散列函数（WeakHashFunction）或弱无碰撞的散列函数满足条件（1）~（4）的称之为强散列函数（StrongHashFunction）或强无碰撞的散列函数。对hash函数的要求第二节散列函数1978年，Rabin的方法利用DES的密码分组链接模式设计将明文M按M=m1m2…mn进行分组，mi为64bit，按DES的CBC模式依次对每个分组进行加密，令h0=初始向量，hi=Emi[hi-1]，加密过程不使用任何密钥，G=hn为最终得到的散列值。第二节Hash函数Hash函数举例散列函数用于签名时，假设签名消息为(x,y)，y=sigk(h(x))，则攻击者可用如下方式伪造攻击者计算Z=h(x)，找到x’≠x，但h(x’)=h(x)，则（x’,y）构成有效的签名；攻击者找到任意两个不同消息x’，x，满足h(x’)=h(x)，令签名者对h(x)签名，则（x’,h(x)）也是有效签名；攻击者伪造一个签名Z，若能计算h-1(Z)=x，则(x,h(x))为有效签名。对Hash函数的攻击第二节散列函数对hash函数的攻击可以看作是寻找碰撞的过程，攻击者的主要目标不是恢复原始的明文，而是用非法消息替代合法消息进行伪造和欺骗，。攻击方法：生日攻击、中间相遇攻击、穷举攻击第二节Hash函数对Hash函数的攻击攻击者通过一对已知的明文和散列值，就可以任意伪造其它明文的散列值，步骤如下：第一步，对已知明文M产生散列值G；第二步，将非法明文Q按Q=Q1Q2…Qn-2进行分组，每个分组长度为64bit；第三步，计算hi=EQi[hi-1]，1≤i≤n-2；第二节Hash函数中间相遇攻击第四步，产生232个不同的x，对每个x计算Ex[hn-2]，再任意产生232个不同的y，对每个y计算Dy[G]，D是对应于E的解密函数；第五步，找到一对对应的x和y，使得Ex[hn-2]=Dy[G]；第六步，生成新的明文Q′=Q1Q2…Qn-2xy。第二节Hash函数中间相遇攻击Merkle在1989年提出了散列函数的通用结构：

a.将原始消息M分成固定长度的分组(Block)Mi；

b.对最后一个分组MN填充，并附上原始消息M的长度，

使其长度等于固定长度；

c.设定链接变量(chainingvalue)的初始值CV0；

d.定义压缩函数f，CVi=f(CVi-1,Mi-1)；

e.循环操作N次，最后一个CVN为散列值。第二节Hash函数Hash函数的通用结构对hash函数的密码分析主要集中在f的内部结构进行分析，并试图找到能与f的执行产生碰撞的有效方法。第二节Hash函数密码分析2004年8月17日，美国加州圣巴巴拉，Crypto’2004。来自山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告。第二节Hash函数密码分析CollisionsforHashFunctionsMD4,MD5,HAVAL-128andRIPEMDMD5SHA-1RIPEMD-160HMAC第三节Hash算法Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年,RonRivest完成MD5(RFC1321)现行美国标准SHA-1以MD5的前身MD4为基础第三节Hash算法MD5输出：128bit分组长度：512bit算法细节：填充→轮函数MD5总体特征第三节Hash算法Step1:Padding，

M→M’ |M’|448mod512 |M’|>|M|→

如果|M|448mod512,则|M’|=|M|+512

Padding内容:100…0第三节Hash算法MD5算法细节Step2:Append64-bitMessagelength，M’→M’’

若|M|>264,则仅取低64位

低字节在前(little-endian) |M’’|为512的倍数:M0,M1,…,ML-1第三节Hash算法MD5算法细节第三节Hash算法MD5paddingMessage1000…064bit(消息长度)512n+448bitStep3InitializeMDBuffer计算消息摘要时用到四个字的缓冲区(A，B，C，D)。A、B、C、D均为32-bit的寄存器。第一个分组进行第一轮运算时，用以下16进制数来初始化这四个寄存器：

A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210第三节Hash算法MD5算法Step44RoundDepression

定义四个非线性逻辑函数，每一轮用一个。这四个函数分别以3个32bit的变量为输入值，输出一个32bit的值。第1轮：F(X,Y,Z)=(XandY)or(not(X)andZ)

第2轮：G(X,Y,Z)=(XandZ)or(Yandnot(Z))

第3轮：H(X,Y,Z)=XxorYxorZ

第4轮：I(X,Y,Z)=Yxor(Xornot(Z))第三节Hash算法MD5算法第一轮的第一步开始时，将四个链接寄存器中的值复制到另外四个存储单元中：A到AA，B到BB，C到CC，D到DD。设M[k]表示消息的第k个子分组（从0到15），<<<s表示循环左移s位。每次操作对A、B、C和D中的三个作一次非线性函数运算，然后将所得结果加上第四个变量。再将所得结果向右循环移位，并加上A、B、C、D中的一个，用该结果取代A、B、C、D中的一个。第三节Hash算法MD5算法Step5output

第4轮的最后一步完成后，再作运算：

A=A+AA

B=B+BB

C=C+CC

D=D+DD

以上“+”均指mod232的加法运算。A、B、C、D的值作为下一个消息分组运算时的初始值；最后一个消息分组得到的输出A、B、C、D级联成为128bits的消息散列值。第三节Hash算法MD5算法MD5SHA-1RIPEMD-160HMAC第三节Hash算法SecureHashAlgorithm（安全hash算法）1992年NIST制定了SHA(128位)1993年SHA成为标准（FIPSPUB180）1994年修改产生SHA-1(160位)1995年SHA-1成为新的标准,作为SHA-1(FIPSPUB180-1)SHA-1要求输入消息长度<264输入分组长度为512，输出消息摘要长度为160位基础是MD4第三节Hash算法SHA-1Step1:PaddingM

M1|M1|448mod512|M1|>|M|

如果|M|448mod512,则|M1|=|M|+512Padding内容:100…0Step2:Append64-bitlengthM1

M2|M|<264高字节在前(big-endian)|M2|为512的倍数:Y0,Y1,…,YL-1第三节Hash算法SHA-1算法步骤Step3:InitializeMDbuffer(big-endian)

A=67452301(0x67452301) B=EFCDAB89(0xEFCDAB89) C=98BADCFE(0x98BADCFE) D=10325476(0x10325476) E=C3D2E1F0(0xC3D2E1F0)Step4:Compression CV0=IV

CVi=HSHA-1(CVi-1,Yi)Step5:Output MD=CVL第三节Hash算法SHA-1算法步骤SHA-1压缩函数第三节Hash算法Step4:CV0=IV, CVi=HSHA-1(CVi-1,Yi)(A0,B0,C0,D0,E0)(A,B,C,D,E),t0Round(A,B,C,D,E,K[t],W[t]) 0t<80(A,B,C,D,E)(A+A0,B+B0,C+C0,D+D0,E+E0)整个Round包含80次循环,每次处理32-bitW[t]=Yi[t] 0t<16W[t]=(W[t-16]W[t-14]W[t-8]W[t-3])<<<1 16t<80每组(16个)W[t]可由前一组W[t]直接计算第三节Hash算法SHA-1step4:overviewFourrounds: 0t<80

EE+f(t,B,C,D)+(A<<<5)+W[t]+K[t] BB<<<30 (A,B,C,D,E)(A,B,C,D,E)>>>32 f(t,B,C,D)=(B&C)|(B&D) 0t<20 K[t]=230sqrt(2) f(t,B,C,D)=BCD 20t<40 K[t]=230sqrt(3) f(t,B,C,D)=(B&C)|(B&D)|(C&D) 30t<60 K[t]=230sqrt(5) f(t,B,C,D)=BCD 60t<80 K[t]=230sqrt(10)第三节Hash算法SHA-1step4:overviewABCDABCD++++ftT[i]EES5WtKtS30第三节Hash算法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<=79 f(t,B,C,D)=步t的基本逻辑函数；

Sk =循环左移k位给定的32位字