北京大学网络信息安全课件-身份认证

《北京大学网络信息安全课件-身份认证》由会员分享，可在线阅读，更多相关《北京大学网络信息安全课件-身份认证（127页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,,,,,,,网络与信息平安第五讲,,密码学根底(四),,,王 昭,,北京大学信息科学技术学院,,软件研究所--信息平安研究室wangzhao@infosec.pku.edu,2003年春季北京大学硕士研究生课程,,回忆与总结,,对称密码算法,,运算速度快、密钥短、多种用途〔随机数产生、Hash函数〕、历史悠久,,密钥管理困难〔分发、更换〕,,非对称密码算法,,只需保管私钥、可以相当长的时间保持不变、需要的数目较小,,运算速度慢、密钥尺寸大、历史短,,,信息平安的需求,,保密性〔 Conf

2、identiality〕,,完整性 〔Integrity〕,,数据完整性，未被未授权篡改或者损坏,,系统完整性，系统未被非授权操纵，按既定的功能运行,,可用性 〔Availability〕,,鉴别 〔Authenticity〕,,实体身份的鉴别，适用于用户、进程、系统、信息等,,不可否认性 〔 Non-repudiation〕,,防止源点或终点的抵赖,,,,讨论议题,,消息鉴别〔Message Authentication),,,,散列函数〔 Hash Functions),,,,数字签名〔Digital Signature〕,,,,定义,,消息鉴别〔Message Authenticat

3、ion)：,,是一个证实收到的消息来自可信的源点且未被篡改的过程。,,散列函数〔 Hash Functions)：,,一个散列函数以一个变长的报文作为输入，并产生一个定长的散列码，有时也称报文摘要，作为输出。,,数字签名〔Digital Signature〕,,是一种防止源点或终点抵赖的鉴别技术。,,,,,通信系统典型攻击,,1),窃听,,2)业务流分析,,3)消息篡改,,内容修改：消息内容被插入、删除、修改。,,顺序修改：插入、删除或重组消息序列。,,时间修改：消息延迟或重放。,,4)冒充：从一个假冒信息源向网络中插入消息,,5)抵赖：接受者否认收到消息；发送者否认发送过消息。,,,两个概念

4、,,鉴别(Authentication):,,真伪性,,认证(Certification),,资格审查,,,,,消息鉴别,鉴别的目的,,鉴别模型,,鉴别函数,,,鉴别的目的,,鉴别的主要,目的,有二：,,第一，验证信息的发送者是真正的，而不是冒充的，此为信源识别；,,第二，验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等。,,,鉴别模型,,一个单纯,鉴别系统,的模型,窜扰者,,信宿,,,信源,,鉴别编码器,鉴别译码器,信道,平安信道,密钥源,,鉴别系统的组成,,鉴别编码器和鉴别译码器可抽象为鉴别函数。,,一个平安的鉴别系统，需满足,,〔1〕意定的接收者能够检验和证实消息的合法性、真实

5、性和完整性,,〔2〕消息的发送者和接收者不能抵赖,,〔3〕除了合法的消息发送者，其它人不能伪造合法的消息,,,首先要选好恰当的鉴别函数，该函数产生一个鉴别标识，然后在此根底上，给出合理的鉴别协议(Authentication Protocol)，使接收者完成消息的鉴别。,,鉴别函数,,可用来做鉴别的函数分为三类：,,(1),消息加密函数,(Message encryption),,,用完整信息的密文作为对信息的鉴别。,,(2),消息鉴别码MAC,(Message Authentication Code),,公开函数+密钥产生一个固定长度的值作为鉴别标识,,(3),散列函数,(Hash Func

6、tion),,是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。,,,消息加密,,消息的自身加密可以作为一个鉴别的度量。,,对称密钥模式和公开密钥模式有所不同。,,,(a) 对称加密：保密性与鉴别,,提供保密,,提供鉴别,,仅来自,A,,传输中没有被更改,,需要某种结构或冗余,,不提供签名,,,,如何自动确定是否收到的明文可解密为可懂的明文?,,,一种解决方法是强制明文有某种结构.,,,过失控制：Error Control,,(b) 公钥加密：保密性,,提供保密,,不提供鉴别,,(c) 公钥加密：鉴别与签名,,提供鉴别和签名,,仅,A,有,Kra,可以进行加密,,传输中没有被更改,,

7、需要某种结构或冗余,,任何一方均可以使用,Kua,验证签名,,(d)公钥加密：保密、鉴别与签名,,KUb,提供保密性,,Kra,提供鉴别和签名,,消息,鉴别,码MAC,使用一个密钥生成一个固定大小的小数据块，并参加到消息中，称MAC， 或密码校验和〔cryptographic checksum〕,1、接收者可以确信消息M未被改变。,2、接收者可以确信消息来自所声称的发送者；,3、如果消息中包含顺序码〔如HDLC,X.25,TCP〕，那么接收者可以保证消息的正常顺序；,MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少。,,MAC的根本用法(a),,消息鉴别,Pr

8、ovides authentication ---- only A and B share K,,MAC的根本用法(b),,消息鉴别与保密，鉴别与明文连接,Provides authentication -- only A and B share K1,,Provides confidentiality -- only A and B share K2,,MAC的根本用法(c),,消息鉴别与保密，鉴别与密文连接,,Provides authentication -- Using K1,,Provides confidentiality -- Using K2,,通过加密得到信息真实性

9、: 问题,保密性与真实性是两个不同的概念,,根本上,信息加密提供的是保密性而非真实性,,加密代价大(公钥算法代价更大),,鉴别函数与保密函数的别离能提供功能上的灵活性,,某些信息只需要真实性,不需要保密性,,播送的信息难以使用加密(信息量大),,网络管理信息等只需要真实性,,政府/权威部门的公告,,散列函数,Hash Function,,H(M): 输入为任意长度的消息M; 输出为一个固定长度的散列值，称为消息摘要Message Digest〕。,,这个散列值是消息M的所有位的函数并提供错误检测能力：消息中的任何一位或多位的变化都将导致该散列值的变化。,,又称为：哈希函数、数字指纹〔Digit

10、al finger print)、压缩〔Compression)函数、紧缩〔Contraction 〕函数、数据鉴别码DAC〔Data authentication code〕、篡改检验码MDC(Manipulation detection code),,散列函数的根本用法〔a、b),,Provides confidentiality -- only A and B share K,,Provides authentication -- H(M) is cryptographically protected,Provides authentication -- H(M) is crypto

11、graphically protected,,散列函数的根本用法〔c),,Provides authentication and digital signature,,-- H(M) is cryptographically protected,,-- only A could create E,KRa,[H(M)],,散列函数的根本用法(d),,,(d) A,,B: E,K,[M||E,KRa,[H(M)]],Provides authentication and digital signature,,Provides confidentiality,,散列函数的根本用法(e、f),,Pr

12、ovides authentication -- only A and B share S,Provides authentication -- only A and B share S,,Provides confidentiality -- only A and B share K,,方法e的优点,,加密软件很慢,,加密硬件的开销很大,,加密是对大长度数据进行优化的,,加密算法可能受专利保护,,加密算法可能受出口的限制.,,,MAC函数的特性与实现,,MAC函数为多对一映射,,包含所有可能的MAC和所有可能的密钥,,n-bit MAC： 有2,n,个可能的MAC；,,k-bit 密钥：

13、有2,k,个可能的密钥；,,N个可能的消息：有 N>>2,n,,,攻击者如何用强力攻击方法攻击MAC？,,假设：用户A和B通信时没有增加保密性实现，攻击者可以看到明文， k > n (k为密钥长度位数，n为MAC长度位数,),,给定：M,1,和MAC,1,， MAC,1,= C,K1,(M,1,),,密码分析员可以计算MAC,i,= C,Ki,(M,1,) 对所有可能的Ki，至少有一个Ki保证产生 MAC,i,= MAC,1,注意：总共会产生2k个MAC结果，但只有2n< 2k个不同的MAC值，因此，有假设干个key将产生相同的MAC，而攻击者无法确定哪一个是正确的key。,平均来说， 2k

14、/2n= 2(k-n)个key将产生匹配的MAC，所以，攻击者需要循环屡次攻击，以确定K:,,第一轮：给定 M1和MAC1= CK(M1)，对所有2k个key，计算,,MACi = CKi(M1) ，匹配的数量 2(k-n),,第二轮：给定 M2和MAC2= CK(M2)，对所有2(k-n)个key，计算,,MACi = CKi(M2) ，匹配的数量 2(k-2n),,平均来说，如果k=an，那么需要a轮。,例：k=80, MAC 32-bit,那么：,,第一轮：248可能的key；,,第二轮：216个；,,第三轮：1 个；,由此可见，强力攻击企图发现authentication k

15、ey不小于甚至大于对同样长度的解密key的攻击。,如果 k≤n，那么第一轮就可以产生一个唯一对应。仍然可以有多于一个key产生这一配对，这时攻击者只需对一个新的(message, MAC)进行相同的测试。,,考虑以下的MAC算法,M = (X,1,|| X,2,|| … || Xm) 是一个由64位Xi数据块连接而成，,,定义,,,(M) = X,1,X,2,...Xm,,C,K,(M) = E,K,[(M)],,其中,, 为异或操作；E为 ECB工作模式的DES算法。,,,Key length = 56 bit,,MAC length = 64 bit,,强力攻击需要至少2,5

16、6,次加密来决定K。,但攻击者可以不用找到 K就可以实施攻击。,,设 M,,= ( Y,1,|| Y,2,|| … || Ym-,1,|| Ym),,其中 Y,1,, Y,2,, …, Ym-,1,是替换 X,1,, X,2,,…,Xm-,1,的任意值，而,,Ym = Y,1,,Y,2,,, …,,,Ym-,1,,,(M),,这时,,消息M’ 和 MAC= C,K,(M) = E,K,[(M)],是一对可被接收者认证,,的消息。,C,K,(M ) = E,K,[(M )],,= E,K,[,Y,1,,Y,2,,, …,,,Ym-,1,,,Ym ],,= E,K,

17、[,Y,1,,Y,2,,, …,,,Ym-,1,,(Y,1,,Y,2,,, …,,,Ym-,1,,,(M)) ],,= E,K,[(M)],用此方法，任何长度为64,(m-1),位的消息可以作为欺骗性,,信息被插入！,,为了防止以上可能的攻击，MAC函数应具有以下性质：,如果一个攻击者得到M和CK(M)，那么攻击者构造一个消息M 使得CK(M )=CK(M)应在计算上不可行。,,CK(M)应均匀分布，即：随机选择消息M和M  ， CK(M)= CK(M )的概率是2-n，其中n是MAC的位数。,,令M 为M的某些变换，即：M  =f(M)，〔例如：f可以涉及

18、M中一个或多个给定位的反转〕，在这种情况下，Pr[CK(M)= CK(M )] = 2-n。,,基于DES的MAC,,Data Authentication Algorithm,,FIPS publication (FIPS PUB 113),,ANSI standard (X9.17),,,使用CBC(Cipher Block Chaining)方式，初始向量为0。,,,最广泛的用法,,将数据按64位分组，D,1,, D,2,, … , D,N,，必要时最后一个数据块用0向右填充。运用DES算法E，密钥K,,,数据鉴别码(DAC)的计算如下：,,O,1,= E,K,(D,1,),,O,2,

19、= E,K,(D,2,,O,1,),,O,3,= E,K,(D,3,,O,2,),,…,,O,N,= E,K,(D,N,,O,N-1,),,,M的大小可由通信双方约定。美国联邦电信建议采用,,24bit[见FTSC-1026],而美国金融系统采用32bit [ABA,1986],,,,D,1,,(64bits),Time = 1,DES,,encrypt,K,,(56bits),O,1,,(64bits),D,2,,(64bits),Time = 2,DES,,encrypt,K,O,2,,(64bits),+,D,N,,(64bits),Time = N,DES,,encrypt,K,

20、O,N,,+,DAC M-bits,,(16 to 64 bits),,},...,(16<=M<=64),,工作于CFB模式下DES,,,64bit存放器,DES,选左边k位,选左边M位,+,y,i,x,i,k,,问题,,假设对相当长的文件通过签名认证怎么办？如一个合法文件有数兆字节长。自然按64比特分划成一块一块，用相同的密钥独立地签每一个块。然而，这样太慢。,,解决方法,,解决方法：引入可公开的密码散列函数(Hash function)。它将取任意长度的消息做自变量，结果产生规定长度的消息摘要。[如，使用数字签名标准DSS，消息摘要为160比特]，然后签名消息摘要。对数字签名来说，散列

21、函数h是这样使用的：,,消息： x 任意长,,消息摘要： Z=h(x) 160bits,,签名： y=sigk(Z) 320 bits (签名一个消息摘要),,,验证签名:(x,y),其中y= sigk(h(x))，使用公开的散列函数h，重构作Z  =h(x)。然后Verk(y)=Z,来看Z=Z',,新的问题,,用以鉴别的散列函数，能否减弱认证方案的平安性？这个问题是要分析的。签名的对象由完整消息变成消息摘要，这就有可能出现伪造。,,平安威胁一,,(a)伪造方式一：Oscar以一个有效签名(x,y)开始，此处y= sigk(h

22、(x))。首先他计算Z=h(x)，并企图找到一个x'满足h(x')=h(x)。假设他做到这一点，那么(x',y)也将为有效签名。为防止这一点，要求函数h具有无碰撞特性。,,定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x ∈ X，在计算上几乎找不到异与x的x' ∈ X使h(x)=h(x')。,,平安威胁二,,(b)伪造方式二：Oscar首先找到两个消息x=x',满足h(x)=h(x'),然后Oscar把x 给Bob且使他对x的摘要h(x)签名，从而得到y,那么(x',y)是一个有效的伪造,。,,,定义2(强无碰撞),散列函数h被称为是强无碰撞的,是指在计算上几乎不可能找到相异的

23、x，x'使得h(x)=h(x')。,,,注：强无碰撞自然含弱无碰撞！,,,平安威胁三,,(c)伪造方式三：在散列函数的用法(e)中, 秘密值S本身并不发送, 如果散列函数不是单向的,攻击者截获到M和H(M||S). 然后通过某种逆变换获得M||S, 因而攻击者就可以得到S.,,,定义3(单向的),称散列函数h为单向的，是指计算h的逆函数h,-1,在计算上不可行。,,,HASH 函数 h = H(M),,满足：,,1、H可以作用于一个任意长度的数据块；,,2、H产生一个固定长度的输出；,,3、对任意给定的x ,H(x) 计算相对容易，无论是软件还是硬件实现。,,4、对任意给定码h，找到x满足

24、H(x)=h具有计算不可行性；〔单向性〕,,5、对任意给定的数据块x，找到满足H(y)=H(x)的yx具有计算不可行,,性。,,6、找到任意数据对(x,y)，满足H(x) = H(y)是计算不可行的。,前三条要求具有实用性，第4条是单向性质，即给定消息可以产生一个,,散列码，而给定散列码不可能产生对应的消息。第5条性质是保证一个,,给定的消息的散列码不能找到与之相同的另外的消息。即防止伪造。,,第6条是对的生日攻击方法的防御能力。,目的：“fingerprint〞 of messgae,,Hash函数的分类,,根据平安水平：,,定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x

25、 ∈ X，在计算上几乎找不到异于x的x' ∈ X使h(x)=h(x')。,,定义2(强无碰撞)，散列函数h被称为是强无碰撞的,是指在计算上几乎不可能找到相异的x，x'使得h(x)=h(x')。,,注：强无碰撞自然含弱无碰撞！,,Hash函数的分类,,根据是否使用密钥,,带秘密密钥的Hash函数:,消息的散列值由只有通信双方知道的秘密密钥K来控制。此时，散列值称作MAC。,,不带秘密密钥的Hash函数：,消息的散列值的产生无需使用密钥。此时，散列值称作MDC。,,,Hash与MAC的区别,,MAC,需要对全部数据进行加密,,MAC,速度慢,,Hash,是一种直接产生鉴别码的方法,,,生日攻击,,

26、假定使用64位的散列码,是否平安?,,如果采用传输加密的散列码和不加密的报文M,对手需要找到M ,使得H(M)=H(M),以便使用替代报文来欺骗接收者.,,一种基于生日悖论的攻击可能做到这一点.,,,生日悖论,,生日问题：一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？,,概率结果与人的直觉是相违背的.,,实际上只需23人,即任找23人，从中总能选出两人具有相同生日的概率至少为1/2。,,,,,,相关问题,,给定一个散列函数,有n个可能的输出,输出值为H(x),如果H有k个随机输入, k必须为多大才能使至少存在一个输入y,使得H(y)=H(x)的概率大于0.5.

27、,,对单个y, H(y)=H(x)的概率为1/n,反过来H(y)H(x)的概率为1-(1/n).,,如果产生k个随机值y,他们之间两两不等的概率等于每个个体不匹配概率的乘积,即[1-(1/n)]k,这样,至少有一个匹配的概率为1-[1-(1/n)]k1-[1-(k/n)]=k/n.要概率等于0.5,只需k=n/2.,,对长度为m位的散列码，共有2m个可能的散列码，假设要使任意的x,y 有H(x)=H(y)的概率为0.5,只需,,k=2m/2,,,,,,Birthday Attacks: example,A,准备两份合同,M,和,M,,，,一份,B,会同意，一份会取走他的财产而被拒绝,,A

28、,对,M,和,M,,各做32处微小变化(保持原意),分别产生2,32,个64位,hash,值,,根据前面的结论,超过0.5的概率能找到一个,M,和一个,M,,,它们的,hash,值相同,,A,提交,M,,经,B,审阅后产生64位,hash,值并对该值签名,返回给,A,,A,用,M,,替换,M,,Hash,必须足够长(64,,128,,160),,散列函数的平安性,,强行攻击：生日攻击,,,,,,MD5 128位， 24小时找到一个冲突,,,单向,2,n,弱无碰撞,2,n,强无碰撞,2,n/2,,Hash函数的构造,,基于数学难题的构造方法：,,计算速度慢，不实用,,利用对称密码体

29、制来设计Hash,,直接设计,,,,,分组链接 Block Chaining,用对称加密算法构造hash函数,,M=(M1,M2,…,Mt), H0=Initial value,,Hi=f(Mi,Hi-1), 例如Hi=EMi(Hi-1),,hash: Ht,,速度慢,且许多这样的hash函数被证明不平安(与E的平安性无关),,下面的四种可能是平安的:,,Hi=EHi-1(Mi)Mi,,Hi=EHi-1(Mi)MiHi-1,,Hi=EHi-1(MiHi-1)Mi,,Hi=EHi-1(MiHi-1)MiHi-1,,现在很少使用,,,hash函数通用结构,由,Merkle

30、,于1989年提出,,Ron,Rivest,于1990年提出,MD4,,几乎被所有,hash,函数使用,,具体做法:,,把原始消息,M,分成一些固定长度的块,Y,i,,最后一块,padding,并使其包含消息,M,长度,,设定初始值,CV,0,,压缩函数,f, CV,i,=f(CV,i-1,,Y,i-1,),,最后一个,CV,i,为,hash,值,,,,,b,Y,0,n,IV=,,CV,0,f,,b,Y,1,n,f,,b,Y,L-1,n,CV,L-1,f,CV,1,n,n,IV = initial value 初始值,,CV = chaining value 链接值,,Yi = it

31、h input block (第i 个输入数据块),,f = compression algorithm (压缩算法〕,,n = length of hash code (散列码的长度),,b = length of input block(输入块的长度),General,Structure of Secure Hash Code,CV,L,,CV,0,=IV=,initial n-bit value,,CV,i,=f(CV,i-1,, Y,i-1,),(1,,i,,L),,H(M) = CV,L,,讨论几种常用的HASH算法,,MD5,,,SHA-1,,,RIP

32、EMD-160,,,HMAC,,,,,,MD5简介,Merkle于1989年提出hash function模型,,Ron Rivest于1990年提出MD4,,1992年, MD5 (RFC 1321) developed by Ron Rivest at MIT,,MD5把数据分成512-bit块,,MD5的hash值是128-bit,,在最近数年之前,MD5是最主要的hash算法,,现行美国标准SHA-1以MD5的前身MD4为根底,,,,,MD5: padding,Step 1: Padding M  M1,,|M1|  448 mod 512,,|M1| > |M| ,,如果|M|

33、  448 mod 512,那么|M1| = |M|+512,,Padding内容: 100…0,,Step 2: Append 64-bit length M1  M2,,假设|M| > 264,那么仅取低64位,,低字节在前 (little-endian),,|M2|为512的倍数: Y0,Y1,…,YL-1,,,,,MD5: 示意图,,,,,MD5: compression,Step 3: Initialize MD buffer (little-endian),,A = 01 23 45 67 (0x67452301),,B = 89 AB CD EF (0xEFCDAB89),

34、,C = FE DC BA 98 (0x98BADCFE),,D = 76 54 32 10 (0x10325476),,Step 4: Compression,,CV,0,=IV,,,CV,i,=H,MD5,(CV,i-1,,Y,i,),,Step 5: Output,,MD = CV,L,,,,,MD5 Step 4: 示意图,,,,,MD5 Step 4: overview,Step 4: CV0=IV, CVi=HMD5(CVi-1,Yi),,(A0,B0,C0,D0)(A,B,C,D),,RoundOne(A,B,C,D,T[1…16],X[0…15]),,RoundTwo(A,

35、B,C,D,T[17…32],X[0…15]),,RoundThree(A,B,C,D,T[33…48],X[0…15]),,RoundFour(A,B,C,D,T[49…64],X[0…15]),,(A,B,C,D)(A+A0,B+B0,C+C0,D+D0),,512-bit块(X[…]为32-bit表示)在四个Round使用,,每个Round包含16次循环,每次处理一个32-bit,,T[j]= [sin(j)*232]的整数局部, 1  j  64,,MD5 Compression Function,每一轮包含对缓冲区ABCD的16步操作所组成的一个序列。,,,ab + (( a

36、 + g(b,c,d) + X[k] +T[i])<<

37、b,c)(bd),,2 G(b,c,d) (bd)(cd),,3 H(b,c,d) bcd,,4 I(b,c,d) c(bd),,2,i = (1+5i) mod 16,,,3,i = (5+3i) mod 16,,,2,i = 7i mod 16,,MD5 Step 4: RoundOne,For(k = 0; k < 16; ++k) {,,AB + ((A+g,1,(B,C,D)+X[,1,(k)]+T[160+k+1]) <<< s,1,[k mod 4]),,(A,B,C,D),,(A,B,C,D),>>>32,,},,g,1,(

38、B,C,D) = (B & C) | (B & D),,,1,(k) = k, 0  k < 16,,s,1,[0…3] = [7,12,17,22],,MD5 Step 4: RoundTwo,For(k = 0; k < 16; ++k) {,,AB + ((A+g,2,(B,C,D)+X[,2,(k)]+T[161+k+1]) <<< s,2,[k mod 4]),,(A,B,C,D),,(A,B,C,D),>>>32,,},,g,2,(B,C,D) = (B & D) | (C & D),,,2,(k) = (1+5k) mod 16, 0  k < 16,,s,2,

39、[0…3] = [5,9,14,20],,MD5 Step 4: RoundThree,For(k = 0; k < 16; ++k) {,,AB + ((A+g,3,(B,C,D)+X[,3,(k)]+T[162+k+1]) <<< s,3,[k mod 4]),,(A,B,C,D),,(A,B,C,D),>>>32,,},,g,3,(B,C,D) = B  C  D,,,3,(k) = (5+3k) mod 16, 0  k < 16,,s,3,[0…3] = [4,11,16,23],,MD5 Step 4: RoundFour,For(k = 0; k < 16; ++

40、k) {,,AB + ((A+g,4,(B,C,D)+X[,4,(k)]+T[163+k+1]) <<< s,4,[k mod 4]),,(A,B,C,D),,(A,B,C,D),>>>32,,},,g,4,(B,C,D) = C  (B | D),,,4,(k) = 7k mod 16, 0  k < 16,,s,4,[0…3] = [6,10,15,21],,CV0 = IV,,CVq+1 = SUM32(CVq,RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]),,MD = CVL,,,其中：IV = ABCD的初始值〔见步骤3〕,,Yq

41、 = 消息的第q个512位数据块,,L = 消息中数据块数；,,CVq = 链接变量，用于第q个数据块的处理,,RFx = 使用根本逻辑函数x的一轮功能函数。,,MD = 最终消息摘要结果,,SUM32=分别按32位字计算的模232加法结果。,,,,,MD5: 总结,MD5使用小数在前,,生日攻击+64位可计算  128位hash值太短,,Dobbertin在1996年找到了两个不同的512-bit块,它们在MD5计算下产生相同的hash,,至今还没有真正找到两个不同的消息,它们的MD5的hash相等,,MD5不是足够平安的,,Secure Hash Algorith

42、m简介,1992年NIST制定了SHA(128位),,1993年SHA成为标准〔FIPS PUB 180〕,,1994年修改产生SHA-1(160位),,1995年SHA-1成为新的标准,作为SHA-1(FIPS PUB 180-1),,SHA-1要求输入消息长度<264,,输入按512位的分组进行处理的,,SHA-1的摘要长度为160位,,根底是MD4,,SHA-1: padding,与MD5相同,,Step 1: Padding M  M1,,|M1|  448 mod 512,,|M1| > |M| ,,如果|M|  448 mod 512,那么|M1| = |M|+512,,P

43、adding内容: 100…0,,Step 2: Append 64-bit length M1  M2,,|M| < 264,,高字节在前 (big-endian),,|M2|为512的倍数: Y0,Y1,…,YL-1,,SHA-1: compress,Step 3: Initialize MD buffer (big-endian),,A = 67 45 23 01 (0x67452301),,B = EF CD AB 89 (0xEFCDAB89),,C = 98 BA DC FE (0x98BADCFE),,D = 10 32 54 76 (0x10325476),,E = C3

44、D2 E1 F0 (0xC3D2E1F0),,Step 4: Compression,,CV,0,=IV,,,CV,i,=H,SHA-1,(CV,i-1,,Y,i,),,Step 5: Output,,MD = CV,L,,SHA-1 step 4: 示意图,,SHA-1 step 4: overview,Step 4: CV,0,=IV,,CV,i,=H,SHA-1,(CV,i-1,,Y,i,),,(A0,B0,C0,D0,E0)(A,B,C,D,E), t  0,,Round(A,B,C,D,E,K[t],W[t]) 0  t < 80,,(A,B,C,D,E)(A+A0,B+B

45、0,C+C0,D+D0,E+E0),,整个,Round,包含,80,次循环,每次处理一个32-,bit,,W[t] = Y,i,[t] 0  t < 16,,W[t] =(W[t-16]W[t-14]W[t-8]W[t-3])<<<1,,16  t < 80,,每组(16个),W[t],可由前一组,W[t],直接计算,,SHA-1: compression function,Four rounds: 0  t < 80,,E  E+f(t,B,C,D)+(A<<<5)+W[t]+K[t],,B  B<<<30,,(A,B,C,D,E)(A,B,C,D,E)>>>32,,f

46、(t,B,C,D) = (B&C)|(B&D) 0  t < 20,,K[t] = 2,30, sqrt(2),,f(t,B,C,D) = B  C  D 20  t < 40,,K[t] = 2,30, sqrt(3),,f(t,B,C,D) = (B&C)|(B&D)|(C&D) 30  t < 60,,K[t] = 2,30, sqrt(5),,f(t,B,C,D) = B  C  D 60  t < 80,,K[t] = 2,30, sqrt(10),,SHA-1,压缩函数,,,A,B,C,D,E, (E + f(t,B,C,D)+S,5,(A)

47、 +Wt + Kt),A,S,30,(B),C,D,其中，,,A,B,C,D,E = 缓冲区的5个字；,,t = 步数，0<= t <= 79；,,f(t,B,C,D) = 步t的根本逻辑函数；,,Sk = 循环左移k位给定的32位字；,,Wt = 一个从当前512数据块导出的32位字；,,Kt = 一个用于加法的常量，四个不同的值，如前所述,,+ = 加模232。,,A,B,C,D,A,B,C,D,+,+,+,+,f,t,T[i],E,E,S,5

48、,W,t,K,t,S,30,,SHA-1总结,SHA-1使用big-endian,,抵抗生日攻击: 160位hash值,,没有发现两个不同的512-bit块,它们在SHA-1计算下产生相同的“hash〞,,速度慢于MD5,,平安性优于MD5,,RIPEMD-160简介,欧洲RIPE工程的结果,,RIPEMD为128位,,更新后成为RIPEMD-160,,根底是MD5,,RIPEMD-160: padding,Step 1: Padding M  M1,,|M1|  448 mod 512,,|M1| > |M| ,,如果|M|  448 mod 512,那么|M1| = |M|+512

49、,,Padding内容: 100…0,,Step 2: Append 64-bit length M1  M2,,|M| < 264,,低字节在前 (little-endian),,|M2|为512的倍数: Y0,Y1,…,YL-1,,RIPEMD-160: compression,Step 3: Initialize MD buffer (little-endian),,A = 01 23 45 67 (0x67452301),,B = 89 AB CD EF (0xEFCDAB89),,C = FE DC BA 98 (0x98BADCFE),,D = 76 54 32 10 (0x1

50、0325476),,E = F0 E1 D2 C3 (0xC3D2E1F0),,Step 4: Compression,,CV,0,=IV,,,CV,i,=H,RIPE,(CV,i-1,,Y,i,),,Step 5: Output,,MD = CV,L,,RIPEMD-160 step 4: 示意图,,RIPEMD-160: compression function,,(A0,B0,C0,D0,E0)(A,B,C,D,E),,Five rounds: 0  t < 16,,,A  ((A+,f,(B,C,D)+X[,p,[t]]+,K,)<<<,s,)+E,,C  C<<<10,,(A

51、,B,C,D,E)(A,B,C,D,E)>>>32,,A((A+,f,(B,C,D)+X[,p,[t]]+,K,)<<<,s,)+E,,CC<<<10,,(A,B,C,D,E)(A,B,C,D,E)>>>32,,(A,B,C,D,E)  (B0+C+D, C0+D+E, D0+E+A, E0+A+B, A0+B+C),,RIPEMD-160 step 4: f,i,,,,, ,Function f,1,,f,2,,f,3,,f,4,,f,5,:,,f,1,(B,C,D) = B  C  D,,f,2,(B,C,D) = (

52、B&C)|(!B&D),,f,3,(B,C,D) = (B|!C)  D,,f,4,(B,C,D) = (B&C)|(C&!D),,f,5,(B,C,D) = B  (C|!D),,: 7,4,13,1,10,6,15,3,12,0,9,5,2,14,11,8,,: 5,14,7,0,9,2,11,4,13,6,15,8,1,10,3,12,,RIPEMD-160总结,RIPEMD-160使用little-endian,,抵抗生日攻击: 160位hash值,,没有发现两个不同的512-bit块,它们在RIPEMD-160计算下产生相同的“hash〞,,速度略慢于SHA-1,,平安性优于

53、MD5,,对密码分析的抵抗力好于SHA-1,,比较：,,,MD5 SHA-1 RIPEMD-160,,摘要长度 128位 160位 160位,,根本处理单位 512位 512位 512位,,步数 64(4 of 16) 80(4 of 20) 160(5 paired of 16),,最大消息长度 无限 264-1位 264-1位,,根本逻辑函数 4 4 5,,加法常数 64 4 9,,Endianness Little-endian Big-endian Little-endian,性能 32.4 Mb

54、ps 14.4Mbps 13.6Mbps,,Http:// eskimo /~weidai/benchmarks.txt, C++ on Pentium 266Mhz,,hash函数小结,hash,函数把变长信息映射到定长信息,,hash,函数不具备可逆性,,hash,函数速度较快,,hash,函数与对称密钥加密算法有某种相似性,,对,hash,函数的密码分析比对称密钥密码更困难,,hash,函数可用于消息摘要,,hash,函数可用于数字签名,,HMAC简介,MAC,可用分组加密算法产生,,ANSI,标准(,X9.17): M=(X,1,,X,2,,…,X,t,),,,M,1,

55、=E,K,(X,1,),,,M,j+1,=E,K,(X,j+1,,M,j,), 1,j

56、pad(00110110)作XOR以产生S,i,,,对(S,i,||M)进行hash,,,K,+,每个字节与opad(01011010)作XOR以产生S,o,,,HMAC=f[IV,S,o,||f(IV,S,i,||M)],,,数字签名,,Message authentication用以保护双方之间的数据交换不被第三方侵犯；但它并不保证双方自身的相互欺骗。假定A发送一个认证的信息给B，双方之间的争议可能有多种形式：,,B伪造一个不同的消息，但声称是从A,收到的。,,A可以否认发过该消息，B无法证明A确实发了该消息。,,例如：EFT中改大金额；股票交易指令亏损后抵赖。,,,,数字签名,传统

57、签名的根本特点:,,能与被签的文件在物理上不可分割,,签名者不能否认自己的签名,,签名不能被伪造,,容易被验证,,数字签名是传统签名的数字化,根本要求:,,能与所签文件“绑定〞,,签名者不能否认自己的签名,,签名不能被伪造,,容易被自动验证,,数字签名应具有的性质,,必须能够验证作者及其签名的日期时间；,,必须能够认证签名时刻的内容；,,签名必须能够由第三方验证，以解决争议；,,因此，数字签名功能包含了鉴别的功能,,数字签名的设计要求,,签名必须是依赖于被签名信息的一个位串模式；,,签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与否认；,,必须相对容易生成该数字签名；,

58、,必须相对容易识别和验证该数字签名；,,伪造该数字签名在计算复杂性意义上具有不可行性，既包括对一个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个数字签名；,,在存储器中保存一个数字签名副本是现实可行的。,,数字签名分类,以方式分,,直接数字签名direct digital signature,,仲裁数字签名arbitrated digital signature,,以平安性分,,无条件平安的数字签名,,计算上平安的数字签名,,以可签名次数分,,一次性的数字签名,,屡次性的数字签名,,直接数字签名〔DDS〕,,(1) A,,B: E,KRa,[M],,,提供了鉴别与签名：

59、,,只有,A,具有,KRa,进行加密;,,传输中没有被篡改；,,需要某些格式信息/冗余度；,,任何第三方可以用,KUa,验证签名,(1’) A,,B: E,KUb,[E,KRa,(M)],,,提供了保密(KUb)、鉴别与签名(KRa)：,,直接数字签名,,(2) A,,B: M||E,KRa,[H(M)],提供鉴别及数字签名,,-- H(M) 受到密码算法的保护；,,-- 只有 A 能够生成 E,KRa,[H(M)],(2’) A,,B: E,K,[M||E,KRa,[H(M)]],提供保密性、鉴别和数字签名。,,直接数字签名的缺点,,验证模式依赖于发送方的保密密钥；,,发送方要抵赖发送

60、某一消息时，可能会声称其私有密钥丧失或被窃，从而他人伪造了他的签名。,,通常需要采用与私有密钥平安性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在。,,改进的方式例如可以要求被签名的信息包含一个时间戳〔日期与时间〕，并要求将已暴露的密钥报告给一个授权中心。,,X的某些私有密钥确实在时间T被窃取，敌方可以伪造X的签名及早于或等于时间T的时间戳。,,仲裁数字签名,,引入仲裁者。,,通常的做法是所有从发送方X到接收方Y的签名消息首先送到仲裁者A，A将消息及其签名进行一系列测试，以检查其来源和内容，然后将消息加上日期并与已被仲裁者验证通过的指示一起发给Y。,,仲裁者在这一

61、类签名模式中扮演敏感和关键的角色。,,所有的参与者必须极大地相信这一仲裁机制工作正常。〔trusted system〕,,仲裁数字签名技术,(a) 单密钥加密方式，仲裁者可以看见消息,,(1) X,A：M||E,K,xa,[ID,x,|| H(M)],,(2),A,Y：E,K,ay,[ID,x,|| M || E,K,xa,[ID,x,|| H(M)] || T],X与A之间共享密钥K,xa,，Y,与A之间共享密钥K,ay,；,,X：,准备消息M，计算其散列码H(M)，用X的标识符,ID,x,和散列值构成,,签名，并将消息及签名经K,xa,加密后发送给A；,,A：解密签名，用H(M)验证消

62、息M，然后将ID,x,，M，签名，和时间戳,,一起经K,ay,加密后发送给Y；,,Y：解密A发来的信息，并可将M和签名保存起来。,解决纠纷：,,Y：向A发送 EKay[IDx|| M || EKxa[IDx|| H(M)]],,A：用Kay恢复IDx，M，和签名〔 EKxa[IDx|| H(M)]〕，然后用Kxa解密签,,名并验证散列码,,注意：,,在这种模式下Y不能直接验证X的签名，Y认为A的消息正确，只,,因为它来自A。因此，双方都需要高度相信A:,,X必须信任A没有暴露Kxa，并且没有生成错误的签名,,EKxa[IDx|| H(M)],,Y必须信任A仅当散列值正确并且签名确实是X产生的情

63、况下才,,发送的 EKay[IDx|| M || EKxa[IDx|| H(M)] || T],,双方都必须信任A处理争议是公正的。,,只要A遵循上述要求，那么X相信没有人可以伪造其签名；Y相信X不,,能否认其签名。,,上述情况还隐含着A可以看到X给Y的所有信息，因而所有的窃听者,,也能看到。,,(b) 单密钥加密方式，仲裁者不可以看见消息,,(1) X,A： ID,x,|| E,K,xy,[M]||E,K,xa,[ID,x,|| H(E,K,xy,[M])],,(2),A,Y：E,K,ay,[ID,x,||E,K,xy,[M] || E,K,xa,[ID,x,|| H(E,K,xy,[M

64、])] || T],在这种情况下，X与Y之间共享密钥K,xy,，,,X：将标识符,ID,x,,,密文 E,K,xy,[M]，以及对ID,x,和密文消息的散列码用,,K,xa,加密后形成签名,发送给A。,,A：解密签名，用散列码验证消息，这时A只能验证消息的密文而不,,能读取其内容。然后A将来自X的所有信息加上时间戳并用K,ay,加,,密后发送给Y。,(a),和(b)共同存在一个共性问题：,,A和发送方联手可以否认签名的信息；,,A和接收方联手可以伪造发送方的签名；,,(c) 双密钥加密方式，仲裁者不可以看见消息,,(1) X,A： ID,x,|| E,KR,x,[ID,x,|| E,KU,

65、y,(E,KR,x,[M])],,(2),A,Y： E,KR,a,[ID,x,|| E,KU,y,[E,KR,x,[M]] || T],X：对消息M双重加密：首先用X的私有密钥KRx，然后用Y的公开,,密钥KUy。形成一个签名的、保密的消息。然后将该信息以及,,X的标识符一起用KRx签名后与IDx 一起发送给A。这种内部、,,双重加密的消息对A以及对除Y以外的其它人都是平安的。,,A：检查X的公开/私有密钥对是否仍然有效，是，那么确认消息。并,,将包含IDx、双重加密的消息和时间戳构成的 消息用KRa签名后,,发送给Y。,本模式比上述两个模式具有以下好处：,,1、在通信之前各方之间无须共享任

66、何信息，从而防止了联手作弊；,,2、即使KRx 暴露，只要KRa 未暴露，不会有错误标定日期的消息,,被发送；,,3、从X发送给Y的消息的内容对A和任何其他人是保密的。,,数字签名算法,,普通数字签名算法,,RSA,,EIGamal,,DSS/DSA,,不可否认的数字签名算法,,群签名算法,,盲签名算法,,RSA签名方案,,,RSA签名,A,的公钥私钥对{,KU,a,||,KR,a,},,A,对消息,M,签名:,S,A,=,E,KRa,(M),,问题:,,速度慢,,信息量大,,第三方仲裁时必须暴露明文信息,,漏洞:,E,KRa,(x,,y),,E,KRa,(x),,E,KRa,(y) mod n,,先做摘要:,H,M,= hash(M),,再对,H,M,签名,S,A,=,E,KRa,(H,M,),,hash,函数的无碰撞性保证了签名的有效性,,签名与加密,签名提供真实性(authentication),,加密提供保密性(confidentiality),,“签名+加密〞提供“真实性+保密性〞,,两种实现方式: (AB),,先签名,后加密: EKUb{M||SigA(M)},,