第四章 散列函数与报文鉴别

1、第四章 散列函数与报文鉴别南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 4.1 鉴别概念 4.2 鉴别函数 4.3 散列函数 4.4 MD5报文摘要算法 4.5 安全散列算法SHA 4.6 报文鉴别码 南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 报文鉴别（Message Authentication）是防御网络主动攻击的重要技术。 网络攻击一般具有以下形式：n泄漏（或消息析取）泄漏（或消息析取）n截获和分析出报文的内容，即报文的内容泄漏给没有拥截获和分析出报文的内容，即报文的内容泄漏给没有拥有合法密钥的人或过程。有合法密钥的人或过程。n通信量分析通信量

2、分析n发现通信双方的通信方式。在面向连接的应用中，可以发现通信双方的通信方式。在面向连接的应用中，可以确定连接的频率和连接持续时间。在面向连接或无连接确定连接的频率和连接持续时间。在面向连接或无连接的环境中，可以确定通信双方的报文数量和长度。的环境中，可以确定通信双方的报文数量和长度。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n伪装伪装n以假的源点身份将报文插入网络中。以假的源点身份将报文插入网络中。n包括由敌手伪造一条报文却声称它来自已授权的某个实包括由敌手伪造一条报文却声称它来自已授权的某个实体。另外，还包括由假的报文接收者对收到报文发回假体。另外，还包括由假的报文接

3、收者对收到报文发回假确认，或者不予接受。确认，或者不予接受。n内容篡改内容篡改n篡改报文的内容，包括插入、删除、调换及修改。篡改报文的内容，包括插入、删除、调换及修改。n序号篡改序号篡改n对通信双方报文序号的任何修改，包括插入、删除和重对通信双方报文序号的任何修改，包括插入、删除和重排序。排序。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n计时篡改计时篡改n报文延迟或回放。报文延迟或回放。n对面向连接应用，一个完整的会话或报文序列可以是在对面向连接应用，一个完整的会话或报文序列可以是在之前某些有效会话的回放，或者序列中的单个报文能被之前某些有效会话的回放，或者序列中的单个报

4、文能被延迟或回放。对无连接应用，单个报文能被延迟或回放。延迟或回放。对无连接应用，单个报文能被延迟或回放。n抵赖抵赖n终点否认收到某报文或源点否认发过某报文。终点否认收到某报文或源点否认发过某报文。 报文鉴别n是证实收到的报文来自可信的源点且未被篡改的过程。是证实收到的报文来自可信的源点且未被篡改的过程。n对付第对付第3、4、5、6类攻击类攻击 数字签名n是一种防止源点或终点抵赖的鉴别技术。是一种防止源点或终点抵赖的鉴别技术。n对付第对付第3、4、5、6、7类攻击类攻击南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 任何报文鉴别机制均由两个基本层次构成：n较低层次的鉴别函数较

5、低层次的鉴别函数n能够产生鉴别符，用于鉴别一个报文的值。能够产生鉴别符，用于鉴别一个报文的值。n高层鉴别协议高层鉴别协议n通过调用鉴别函数，鉴别协议能使接收者完成报文的鉴通过调用鉴别函数，鉴别协议能使接收者完成报文的鉴别。别。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 产生鉴别符的函数分为以下几类：n报文加密报文加密n以整个报文的密文作为鉴别符；以整个报文的密文作为鉴别符；n报文鉴别码（报文鉴别码（MAC）n以一个公共函数和密钥产生一个定长值作为鉴别符；以一个公共函数和密钥产生一个定长值作为鉴别符；n散列函数散列函数n一个将任意长度的报文映射为定长的散列值的公共函数，一个

6、将任意长度的报文映射为定长的散列值的公共函数，以散列值作为鉴别符。以散列值作为鉴别符。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 4.2.1 报文加密 4.2.2 报文鉴别码 4.2.3 散列函数南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 报文加密能提供一种鉴别机制。 报文加密包括n常规加密常规加密n公开密钥加密公开密钥加密南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 常规加密n考虑直接使用常规加密方法考虑直接使用常规加密方法n用用A和和B共享的秘密密钥共享的秘密密钥K对整个报文进行加密，实现了：对整个报文进行加密，实现了：n提供

7、保密，仅源点提供保密，仅源点A和终点和终点B共享共享K；n提供一定程度的鉴别，采用密钥提供一定程度的鉴别，采用密钥K加密的报文仅能够来加密的报文仅能够来自源点自源点A；n不提供签名，接收方可以伪造报文，发送方可以否认报不提供签名，接收方可以伪造报文，发送方可以否认报文。文。MEKDKMEKM源点源点终点终点南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n直接使用常规加密进行报文鉴别的问题直接使用常规加密进行报文鉴别的问题n若明文若明文M是二进制文件或数字化的是二进制文件或数字化的X光片等，要正确判光片等，要正确判断其文件形式以及真实的明文是困难的。断其文件形式以及真实的明文是

8、困难的。n攻击方可以声称自己是合法用户并发送报文攻击方可以声称自己是合法用户并发送报文Z，此时，此时，接收方很难判断明文的正确性。接收方很难判断明文的正确性。MEKDKMY = EKMDKNZ EKM南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 公开密钥加密n公开密钥加密可以提供公开密钥加密可以提供n保密性保密性n鉴别与签名鉴别与签名n保密、鉴别与签名保密、鉴别与签名南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 公开密钥加密：保密性n提供保密：仅用户提供保密：仅用户B拥有私有密钥拥有私有密钥KRb能解密；能解密；n不提供鉴别：任何一方均可使用不提供鉴别：

9、任何一方均可使用KUb加密报文，而假称该加密报文，而假称该报文是发自用户报文是发自用户A的。的。MEKUbDKRbMEKUbM源点源点A终点终点B南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 公开密钥加密：鉴别和签名n不提供机密性：任何人均可以使用不提供机密性：任何人均可以使用A的公开密钥解密并阅的公开密钥解密并阅读报文。读报文。n提供鉴别和签名：提供鉴别和签名：n仅用户仅用户A拥有私有密钥拥有私有密钥KRa可进行加密；可进行加密；n传输过程中报文不会被更改；传输过程中报文不会被更改；n任何一方均能使用用户任何一方均能使用用户A的公开密钥的公开密钥KUa验证用户验证用户A签

10、签名。名。MEKRaDKUaMEKRaM源点源点A终点终点B南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 公开密钥加密：保密、鉴别和签名n使用使用B的公开密钥加密可以提供保密性；的公开密钥加密可以提供保密性；n使用使用A的私有密钥加密可以提供鉴别和签名。的私有密钥加密可以提供鉴别和签名。MEKRaDMEKRaM源点源点AEEKUbEKRaMKUbEKRaM终点终点BKRbKUaD南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 直接使用公开密钥加密进行报文鉴别存在的问题n与常规加密相同，难以对报文的合法性进行鉴别。与常规加密相同，难以对报文的合法性进行鉴别。

11、 解决方法n一种方法是强制明文具有某种结构，这种结构易于识别、一种方法是强制明文具有某种结构，这种结构易于识别、不能复制且无需使用加密。不能复制且无需使用加密。n如使用帧校验序列如使用帧校验序列FCS进行差错控制。进行差错控制。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 差错控制的示意图n内部差错控制内部差错控制n外部差错控制外部差错控制MEKEKM|F(M)源点源点终点终点F|MF(M)DKFMF(M)比较比较MF(EKM)F|DKFM比较比较EKEKMEKM南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院nFCS和加密函数执行的顺序至关重要和加密函数执

12、行的顺序至关重要n使用内部差错控制能够提供有效的鉴别，因为敌手难以使用内部差错控制能够提供有效的鉴别，因为敌手难以产生在解密之后差错控制码产生在解密之后差错控制码F(M)仍然有效的密文。仍然有效的密文。n而对于外部差错控制，敌手可以使用有效的差错控制码而对于外部差错控制，敌手可以使用有效的差错控制码来伪造报文，此时敌手尽管不知道明文的内容，但仍可来伪造报文，此时敌手尽管不知道明文的内容，但仍可以制造混乱，破坏正常的工作。以制造混乱，破坏正常的工作。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 基本原理n发送方使用一个密钥和特定算法对明文进行计算，产生一发送方使用一个密钥和特

13、定算法对明文进行计算，产生一个短小的定长数据分组，即报文鉴别码（个短小的定长数据分组，即报文鉴别码（MAC），并将其），并将其附加在报文中。附加在报文中。n在接收方，使用相同的密钥和算法对明文计算在接收方，使用相同的密钥和算法对明文计算MAC，如果，如果生成的生成的MAC与报文中的与报文中的MAC匹配，则匹配，则n接收者确信报文未被更改过。接收者确信报文未被更改过。n接收者确信报文来自所期望的发送方。接收者确信报文来自所期望的发送方。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 报文鉴别码应具有以下特性n要改变报文而使鉴别码不发生改变是不可能的。要改变报文而使鉴别码不发生改

14、变是不可能的。 MAC函数nMAC=CK(M)nMAC函数类似于加密过程，区别主要在于函数类似于加密过程，区别主要在于MAC函数无需函数无需可逆。可逆。n由于鉴别函数的这个特性，使得它比加密函数更不易破解。由于鉴别函数的这个特性，使得它比加密函数更不易破解。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 报文鉴别码的基本用法n报文鉴别，不加密；报文鉴别，不加密；n报文鉴别与加密，报文鉴别码与明文相连，然后作为完整报文鉴别与加密，报文鉴别码与明文相连，然后作为完整的分组加密；的分组加密；n报文鉴别与加密，报文鉴别码与密文相连，然后作为完整报文鉴别与加密，报文鉴别码与密文相连，然

15、后作为完整的分组传输。的分组传输。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n报文鉴别，不加密报文鉴别，不加密nMAC直接与明文连接后传输直接与明文连接后传输nAB: M | CKMn提供鉴别：仅提供鉴别：仅A和和B共享共享KMC|MCKK比较比较CKM南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n报文鉴别与加密，报文鉴别码与明文连接报文鉴别与加密，报文鉴别码与明文连接nAB: EK2M | CK1Mn提供鉴别：仅提供鉴别：仅A和和B共享共享K1n提供保密：仅提供保密：仅A和和B共享共享K2MC|CK1K1比较比较CK1MEK2DMEK2M|CK1MK

16、2南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n报文鉴别与加密，报文鉴别码与密文连接报文鉴别与加密，报文鉴别码与密文连接nAB: EK2M | CK1EK2Mn提供鉴别：使用提供鉴别：使用K1n提供保密：使用提供保密：使用K2n显然，将报文鉴别码与明文连接之后作为一个完整的分组显然，将报文鉴别码与明文连接之后作为一个完整的分组加密更可取。加密更可取。MC|CK1K1比较比较CK1EK2MEK2DMEK2MK2南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 一个散列函数以一个变长的报文M作为输入，产生一个定长的散列码H(M)作为输出，H(M)又称为报文摘要M

17、D（Message Digest）。 散列码是报文所有比特的函数值，具有差错检测能力：n报文中任一比特或若干比特发生变化都将导致散列码发生报文中任一比特或若干比特发生变化都将导致散列码发生变化。变化。 报文摘要MD与报文鉴别码MAC的区别在于：nMAC需要生成密钥，而需要生成密钥，而MD不需要密钥。不需要密钥。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 散列函数H的基本用法n使用常规加密方法对附加散列码的报文进行加密；使用常规加密方法对附加散列码的报文进行加密；n使用常规加密方法仅对散列码进行加密；使用常规加密方法仅对散列码进行加密；n使用公开密钥加密方法及发送方的私有密

18、钥仅对散列码进使用公开密钥加密方法及发送方的私有密钥仅对散列码进行加密；行加密；n使用常规密钥对报文和已使用公开密钥加密的散列码一起使用常规密钥对报文和已使用公开密钥加密的散列码一起进行加密；进行加密；n使用散列码、公共秘密值的明文方案；使用散列码、公共秘密值的明文方案；n使用散列码、公共秘密值的保密方案。使用散列码、公共秘密值的保密方案。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 使用常规加密方法对附加散列码的报文进行加密nAB: EKM | H(M)n提供保密：对报文和散列码整体进行加密提供保密：对报文和散列码整体进行加密n提供鉴别：只有提供鉴别：只有A和和B共享密钥

19、共享密钥K，可以确定该报文必定来，可以确定该报文必定来自自A且未被篡改，而散列码提供鉴别所需要的结构。且未被篡改，而散列码提供鉴别所需要的结构。MH|H比较比较H(M)EKDMEKM|H(M)K南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 使用常规加密方法仅对散列码进行加密nAB: M | EKH(M)n提供鉴别，不提供加密提供鉴别，不提供加密ME|MHKK比较比较EKH(M)HD南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 使用公开密钥加密方法及发送方的私有密钥仅对散列码进行加密nAB: M | EKRaH(M)n提供鉴别和数字签名，不提供加密提供鉴别

20、和数字签名，不提供加密n仅用户仅用户A能生成能生成EKRaH(M)，提供了数字签名，而，提供了数字签名，而H(M)保保护报文的完整性。护报文的完整性。ME|MHKUaKRa比较比较EKRaH(M)HD南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 使用常规密钥对报文和已使用私有密钥加密的散列码一起进行加密nAB: EKM | EKRaH(M)n提供鉴别和数字签名提供鉴别和数字签名n提供保密提供保密ME|H比较比较EKRaH(M)EKDMEKM|EKRaH(M)KHKRaDKUa南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 使用散列码、公共秘密值的明文方案n

21、AB: M | H(M | S)n通信双方共享一个公共的秘密值通信双方共享一个公共的秘密值S，用户，用户A对报文对报文M和公共和公共秘密值秘密值S的连接计算散列值的连接计算散列值H(M|S)，并将得到的散列值附，并将得到的散列值附加在报文加在报文M之后。因为秘密值本身并不被发送，所以攻击之后。因为秘密值本身并不被发送，所以攻击者无法更改中途截获的报文，也就无法产生假报文。者无法更改中途截获的报文，也就无法产生假报文。n提供鉴别，不提供保密：仅提供鉴别，不提供保密：仅A和和B共享秘密值共享秘密值S。MH|M|比较比较H(M|S)|HSS南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术

22、学院 使用散列码、公共秘密值的保密方案nAB: EKM | H(M|S)n提供鉴别和保密提供鉴别和保密MH|比较比较H(M|S)EKDMEKM|H(M|S)K|HSS南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 散列函数以变长的报文M作为输入，产生定长的报文摘要或散列值H(M)。 报文摘要主要用于报文的完整性鉴别，另外，还可以用于存储文件的完整性鉴别。 散列函数将任意长度的报文当作自变量，结果产生规定长度的报文摘要，可用如下函数形式表示：h = H(M)其中M为变长报文，H(M)为定长的报文摘要MD。 当确信或已知报文值正确时，报文摘要MD在源点被加到该报文上。接收端通过计

23、算该报文的MD并将其与收到的MD进行比较来鉴别该报文。 由于散列函数是公开的，所以需要对其进行保护。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 4.3.1 对散列函数的要求 4.3.2 迭代型散列函数的一般结构南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 要用于报文鉴别，散列函数H必须具有如下性质：nH能用于任何大小的数据分组；能用于任何大小的数据分组；nH产生定长输出；产生定长输出；n对任何给定的对任何给定的x，H(x)要相对易于计算，使得硬件和软件实要相对易于计算，使得硬件和软件实现成为可能；现成为可能；n对任何给定的代码对任何给定的代码h，寻找，

24、寻找x使得使得H(x) = h在计算上是不可在计算上是不可行的，又称为行的，又称为单向性质单向性质；n对任何给定的分组对任何给定的分组x，寻找不等于，寻找不等于x的的y，使得，使得H(y) = H(x)在在计算上是不可行的，又称为计算上是不可行的，又称为弱抗冲突弱抗冲突（weak collision resistance）；）；n寻找对任何的寻找对任何的(x, y)对使得对使得H(x) = H(y)在计算上是不可行的，在计算上是不可行的，又称为又称为强抗冲突强抗冲突（strong collision resistance）。）。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院

25、满足性质4和5的函数也称为单向散列函数或弱单向散列函数。 满足性质4、5和6的函数也称为抗冲突散列函数或强单向散列函数。 具有强抗冲突的散列函数对“生日攻击”具有抵抗能力。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 散列函数的一般结构n函数的输入函数的输入M被分成被分成L个分组个分组Y0, Y1, , YL-1，每个分组长，每个分组长度为度为b比特，通常比特，通常b n，若最后一个分组长度不满，则进，若最后一个分组长度不满，则进行填充，在最后一个分组中包括整个函数输入的长度值。行填充，在最后一个分组中包括整个函数输入的长度值。fffbYL-1bY1bY0nnnnnIV =

26、 CV0CV1CVL-1南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n算法中重复使用压缩函数算法中重复使用压缩函数f，f的输入包括两个部分：的输入包括两个部分：n第第i-1轮输出的轮输出的n比特值比特值CVi-1，称为链接变量，称为链接变量n第第i轮的轮的b比特输入分组比特输入分组Yi-1nf的输出为的输出为n比特值比特值CVi，并作为下一轮的输入。，并作为下一轮的输入。n算法开始时为链接变量指定初值：算法开始时为链接变量指定初值：CV0 = IV。n最后一轮输出的链接变量最后一轮输出的链接变量CVL即为最终产生的散列值。即为最终产生的散列值。南京理工大学计算机科学与技术学

27、院南京理工大学计算机科学与技术学院n算法可表达如下：算法可表达如下：nCV0 = IV = n比特的初值；比特的初值；nCVi = f(CVi-1, Yi-1), 1iL；nH(M) = CVLn算法的核心是设计无碰撞的压缩函数算法的核心是设计无碰撞的压缩函数f，而攻击者对算法的，而攻击者对算法的攻击重点是攻击重点是f的内部结构，分析的过程需要先找出的内部结构，分析的过程需要先找出f的碰撞。的碰撞。n设计设计f时应保证找出其碰撞在计算上是不可行的。时应保证找出其碰撞在计算上是不可行的。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 一个简单的散列函数n散列函数操作的一般性原则

28、散列函数操作的一般性原则n输入被视作长度为输入被视作长度为n-bit的分组序列，散列函数以迭代的的分组序列，散列函数以迭代的方式每次处理一个分组，以产生一个方式每次处理一个分组，以产生一个n-bit的散列值。的散列值。n最简单的散列函数是每个分组按比特异或（最简单的散列函数是每个分组按比特异或（XOR），其表），其表达形式如下：达形式如下：Ci = bi1 bi2 bim其中，其中，nCi表示第表示第i比特的散列码，比特的散列码，1 i n；nm表示输入中的表示输入中的n-bit分组数；分组数；nbij表示第表示第j个分组中的第个分组中的第i个比特；个比特；n 表示表示XOR运算符。运算符。南

29、京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 MD5报文摘要算法是由Ron Rivest提出的，是对MD4算法的改进。 MD5算法曾经是使用最普遍的安全散列算法，但近年来出现了针对该算法的可能攻击手段。 MD5算法以任意长度的报文作为输入，产生一个128bits的报文摘要作为输出。其作用是将大容量信息在数字签名前被“压缩”成一种保密的格式。 算法的输入是按512bits的分组进行处理的。 4.4.1 MD5算法逻辑 4.4.2 MD5压缩函数 4.4.3 MD5的安全性南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 MD5算法的处理过程 报文1000512

30、bits512 bits512 bits512 bitsHMD5512HMD5512128IV128HMD5512128HMD5512128K bitsL512 bits = N32 bits填充(1到到512bits)报文长度(K mod 264)128-bit摘要南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 MD5算法的操作步骤n对报文进行填充对报文进行填充n附加报文的长度附加报文的长度n初始化初始化MD缓存缓存n处理处理512bits报文分组序列报文分组序列n输出报文摘要输出报文摘要南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 对报文进行填充n对报

31、文进行填充，使报文的长度（比特数）与对报文进行填充，使报文的长度（比特数）与448模模512同同余（长度余（长度 448 mod 512），即填充长度为），即填充长度为512的整数倍减的整数倍减去去64。n必须填充，且填充比特串的最高位为必须填充，且填充比特串的最高位为1，其余各位为，其余各位为0。 附加报文的长度n将留出的将留出的64bits以小端对齐方式来表示初始报文（填充前）以小端对齐方式来表示初始报文（填充前）的长度，若初始报文长度大于的长度，若初始报文长度大于264，则以，则以264为模数取模，即为模数取模，即仅使用报文长度的低仅使用报文长度的低64位。位。n此时，报文长度为此时，报

32、文长度为512的倍数（设为的倍数（设为L倍），则可将报文表倍），则可将报文表示为示为512bits的分组序列的分组序列Y0, Y1, , YL-1，而每个分组可以表，而每个分组可以表示为示为16个个32bit字，则报文中的字，则报文中的32bit字的总数为字的总数为N = L16，报文可以按报文可以按32bit字表示为字表示为M0, 1, 2, , N-1。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 初始化MD缓存n算法使用一个算法使用一个128bits的缓存来存放中间结果和最终散列值。的缓存来存放中间结果和最终散列值。n该缓存可以表示为该缓存可以表示为4个个32bits

33、的寄存器（的寄存器（A, B, C, D），每个），每个寄存器以小端对齐方式存储数据，其取值分别为：寄存器以小端对齐方式存储数据，其取值分别为：nA = 67452301nB = EFCDAB89nC = 98BADCFEnD = 10325476南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 处理512bits报文分组序列n算法的核心是压缩函数算法的核心是压缩函数HMD5，HMD5对每个分组对每个分组Yq进行处理。进行处理。nHMD5函数包含函数包含4个循环，个循环，4个循环具有相似的结构，但每次个循环具有相似的结构，但每次循环使用不同的基本逻辑函数循环使用不同的基本逻辑函

34、数F、G、H和和I，每个循环包，每个循环包含含16个步骤。个步骤。n每个循环使用一个每个循环使用一个64元素表元素表T164的四分之一，表中的的四分之一，表中的元素通过正弦函数构建，第元素通过正弦函数构建，第i个元素个元素Ti为为232abs(sin(i)的的整数部分。因为整数部分。因为0abs(sin(i)1，Ti可以用可以用32bit字表示。字表示。nXi是是512bits报文分组中的第报文分组中的第i个个32bit字。字。n第第4次循环的输出加到第次循环的输出加到第1次循环的输入次循环的输入CVq上产生上产生CVq+1，相加时缓存中的相加时缓存中的4个个32bit字分别与字分别与CVq中

35、对应的中对应的4个字以模个字以模232相加。相加。n单个单个512bits的的MD5处理过程处理过程F, T116, Xi16个步骤个步骤G, T1732, X2(i)16个步骤个步骤H, T3348, X3(i)16个步骤个步骤I, T4964, X4(i)16个步骤个步骤ACVq128128CVq+1512YqAAABBBBCCCCDDDD南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 输出报文摘要n报文的报文的L个分组处理完成后，最后一个个分组处理完成后，最后一个HMD5压缩函数的输压缩函数的输出即为生成的出即为生成的128bits报文摘要。报文摘要。南京理工大学计算机

36、科学与技术学院南京理工大学计算机科学与技术学院 MD5的处理过程可以总结如下：CV0 = IV；CVq+1 = CVq + RFIYq, RFHYq, RFGYq, RFFYq, CVq；MD = CVL其中：其中：nIV为缓存为缓存ABCD的初值；的初值；nYq为第为第q个长度为个长度为512bits的报文分组；的报文分组；nL为报文的分组数；为报文的分组数；nCVq为处理第为处理第q个报文分组时的链接变量；个报文分组时的链接变量；nRFx为使用基本逻辑函数为使用基本逻辑函数x的轮函数；（的轮函数；（x为为F、G、H、I）n+为对应为对应32bits字的模字的模232加法；加法；nMD为最终

37、的报文摘要。为最终的报文摘要。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 压缩函数HMD5中有4个循环处理过程，每次循环又对缓存ABCD进行了16步迭代运算。 压缩函数中的一步迭代示意图ABCDCLSsABCDgXkTi南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 每一步运算的形式为a b + CLSs(a + g(b, c, d) + Xk + Ti)其中：其中：na,b,c,d为缓存的为缓存的4个个32bit字，运算完成后向右循环一个字，字，运算完成后向右循环一个字，即得到该步迭代的输出。即得到该步迭代的输出。ng是基本逻辑函数是基本逻辑函数F,

38、G, H, I之一。之一。nCLSs表示循环左移表示循环左移s位。位。nXk = Mq16+k，即报文第，即报文第q个分组中的第个分组中的第k个个32bit字字（k = 1, 2, , 16）。）。nTi为表为表T中的第中的第i个字。个字。n+为对应为对应32bits字的模字的模232加法。加法。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 压缩函数每步左循环移位的位数s南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 在算法的4次循环处理过程中，每次以不同的次序使用16个字Xkn在第在第1次循环中以字的初始次序使用；次循环中以字的初始次序使用；n第第2次循

39、环到第次循环到第4次循环分别对字的次序次循环分别对字的次序k进行置换后得到一进行置换后得到一个新的次序，然后以新次序使用个新的次序，然后以新次序使用16个字，这个字，这3个置换分别为：个置换分别为：n2(k) = (1 + 5k) mod 16n3(k) = (5 + 3k) mod 16n4(k) = 7k mod 16南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 算法在每次循环中，使用不同的基本逻辑函数F, G, H, I，每个逻辑函数的输入为3个32bits字，输出是1个32bits字，其中的运算为按位的逻辑运算。 基本逻辑函数定义表南京理工大学计算机科学与技术学院南

40、京理工大学计算机科学与技术学院 MD5算法的性质n散列码中的每一比特均是输入中每一比特的函数。散列码中的每一比特均是输入中每一比特的函数。 Rivest猜想MD5作为128bits长的散列码是足够强的n给定给定x，求，求y使得使得H(y) = H(x)，需要，需要2128数量级的操作；数量级的操作；n求求(x, y)，使得，使得H(y) = H(x)，需要，需要264数量级的操作。数量级的操作。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 安全的散列算法SHA由美国国家标准和技术协会NIST提出，并作为联邦信息处理标准在1993年公布。 1995年发布了修订版，称为SHA-

41、1。 SHA基于MD4算法，其结构与MD4类似。 SHA-1算法的输入为最大长度不超过264比特的任意报文，按512比特的分组进行处理，输出一个160比特的报文摘要。 4.5.1 SHA-1算法描述 4.5.2 SHA-1压缩函数 4.5.3 SHA与MD5的比较南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 SHA-1算法的处理过程报文1000512 bits512 bits512 bits512 bitsHSHA512HSHA512160IV160HSHA512160HSHA512160K bitsL512 bits = N32 bits填充(1到到512bits)报文长

42、度(K mod 264)160-bit摘要南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 SHA-1算法的操作步骤n对报文进行填充对报文进行填充n附加报文的长度附加报文的长度n初始化初始化MD缓存缓存n处理处理512比特报文分组序列比特报文分组序列n输出输出南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 对报文进行填充n对报文进行填充，使报文的长度（比特数）与对报文进行填充，使报文的长度（比特数）与448模模512同同余（长度余（长度 448 mod 512），即填充长度为），即填充长度为512的整数倍减的整数倍减去去64。n必须填充，且填充比特串的最高位为

43、必须填充，且填充比特串的最高位为1，其余各位为，其余各位为0。 附加报文的长度n将留出的将留出的64比特以大端对齐方式来表示初始报文（填充前）比特以大端对齐方式来表示初始报文（填充前）的长度。的长度。n此时，报文长度为此时，报文长度为512的倍数（设为的倍数（设为L倍），则可将报文表倍），则可将报文表示为示为512bits的分组序列的分组序列Y0, Y1, , YL-1，而每个分组可以，而每个分组可以表示为表示为16个个32bit字，则报文中的字，则报文中的32bit字的总数为字的总数为N = L16，报文可以按，报文可以按32bit字表示为字表示为M0, 1, 2, , N-1。南京理工大学

44、计算机科学与技术学院南京理工大学计算机科学与技术学院 初始化MD缓存n算法使用一个算法使用一个160比特的缓存来存放中间结果和最终散列值。比特的缓存来存放中间结果和最终散列值。n该缓存可以表示为该缓存可以表示为5个个32比特的寄存器（比特的寄存器（A, B, C, D, E），），每个寄存器以大端对齐方式存储数据，其取值分别为：每个寄存器以大端对齐方式存储数据，其取值分别为：nA = 67452301nB = EFCDAB89nC = 98BADCFEnD = 10325476nE = C3D2E1F0南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 处理512比特报文分组序列

45、n压缩函数对每个分组压缩函数对每个分组Yq进行处理。进行处理。n压缩函数包含压缩函数包含4个循环，每个循环由个循环，每个循环由20个处理步骤组成。个处理步骤组成。4个循环具有相似的结构，但每次循环使用不同的基本逻辑个循环具有相似的结构，但每次循环使用不同的基本逻辑函数函数f1, f2, f3, f4。n每个循环的输入为当前处理分组每个循环的输入为当前处理分组Yq和和160比特缓冲区的当比特缓冲区的当前值前值A, B, C, D, E，然后更新缓存的内容。，然后更新缓存的内容。n每个循环使用一个额外的加法常量每个循环使用一个额外的加法常量Kt，其中，其中0 t 79表示表示迭代的步数（迭代的步数

46、（4个循环共个循环共80步），步），80个加法常量只有个加法常量只有4个不个不同取值。同取值。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院n加法常量值的十六进制与十进制表示加法常量值的十六进制与十进制表示n第第4个循环（即第个循环（即第80步迭代）的输出与第步迭代）的输出与第1个循环的输入个循环的输入CVq相加，产生相加，产生CVq+1，其中加法是缓存中，其中加法是缓存中5个个32比特字分比特字分别与别与CVq中相应的字模中相应的字模232相加。相加。n单个单个512bits的的SHA-1处理过程处理过程f1, K, W01920个步骤个步骤f2, K, W203920个步

47、骤个步骤f3, K, W405920个步骤个步骤f4, K, W607920个步骤个步骤ACVq160160CVq+1512YqAAABBBBCCCCDDDDE 32EEE南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 输出n所有所有L个个512比特的分组处理完成后，第比特的分组处理完成后，第L阶段产生的输出阶段产生的输出即为即为160比特的报文摘要。比特的报文摘要。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 SHA-1的处理过程可以总结如下：CV0 = IV；CVq+1 = CVq + ABCDEq；MD = CVL。其中：其中：nIV是缓存是缓存AB

48、CDE的初值；的初值；nABCDEq是第是第q个报文分组经最后一轮处理后产生的输出；个报文分组经最后一轮处理后产生的输出；nCVq为处理第为处理第q个报文分组时的链接变量；个报文分组时的链接变量；nL为报文的分组数；为报文的分组数；n+为对应为对应32bits字的模字的模232加法；加法；nMD为最终的报文摘要。为最终的报文摘要。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 SHA-1压缩函数由4次循环处理过程组成，每次循环由对缓存ABCDE的20步迭代运算组成。 SHA-1压缩函数中一步迭代示意图ABCDEABCDEWtKtftCLS5CLS30南京理工大学计算机科学与技

49、术学院南京理工大学计算机科学与技术学院 每一步迭代运算的形式为A, B, C, D, E (E + ft(B, C, D) + CLS5(A) + Wt + Kt), A, CLS30(B), C, D其中：其中：nA, B, C, D, E表示缓存中的表示缓存中的5个个32bits字；字；nt是迭代的步数，是迭代的步数，0t79；nft(B, C, D)是第是第t步迭代使用的基本逻辑函数；步迭代使用的基本逻辑函数；nCLSs为循环左移为循环左移s位；位；nWt是由当前是由当前512bits的分组导出的一个的分组导出的一个32bits字；字；nKt是加法常量；是加法常量；n+为对应为对应32b

50、its字的模字的模232加法。加法。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 基本逻辑函数f的输入为3个32bits字，输出是1个32bits字，其中的运算为按位的逻辑运算，即输入的第n位是3个输入的相应位的函数。 基本逻辑函数定义表南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 由当前的输入分组（512bits）导出Wt（32bits）的过程（0t79）n前前16个值个值(W0, W1, , W15)直接取自当前分组的直接取自当前分组的16个字；个字；n其余值其余值(W16, W17, , W79)取值为取值为Wt = CLS1(Wt-16 Wt-1

51、4 Wt-8 Wt-3)。n注：注：CLS1表示循环左移表示循环左移1位。位。XORYqW2W8W0W13XORWt-14Wt-8Wt-16Wt-3XORW65W71W63W76W0W1W15CLS1CLS1CLS1WtW79W16南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 SHA与MD5均由MD4算法演化而来，彼此极为相似。 对强行攻击的安全性nSHA报文摘要长度为报文摘要长度为160bits，MD5报文摘要长度为报文摘要长度为128bits，使用强行攻击寻找具有给定报文摘要的报文分别需要做使用强行攻击寻找具有给定报文摘要的报文分别需要做O(2160)和和O(2128)

52、次运算；次运算；n使用强行攻击寻找具有相同报文摘要的两个不同报文分别使用强行攻击寻找具有相同报文摘要的两个不同报文分别需要做需要做O(280)和和O(264)次运算；次运算；n因此，因此，SHA算法抗强行攻击的强度高于算法抗强行攻击的强度高于MD5算法。算法。 对密码分析的安全性n由于由于SHA的设计准则未被公开，其抗密码分析攻击的强度的设计准则未被公开，其抗密码分析攻击的强度较难判断，似乎高于较难判断，似乎高于MD5的强度。的强度。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 速度nSHA和和MD5的主要运算都是模的主要运算都是模232加法，因此易于在加法，因此易于在32

53、位结位结构的机器上实现；构的机器上实现；nSHA的迭代步数（的迭代步数（80步）多于步）多于MD5的迭代步数（的迭代步数（64步），步），而且而且SHA所用的缓存（所用的缓存（160bits）大于）大于MD5的缓存的缓存（128bits），因此，在相同的硬件上实现时，），因此，在相同的硬件上实现时，SHA的速度的速度比比MD5慢。慢。 简洁与紧凑性nSHA与与MD5均较为简单，易于实现，且无需冗长的程序和均较为简单，易于实现，且无需冗长的程序和很大的替换表。很大的替换表。 小端模式与大端模式nMD5使用小端模式；使用小端模式；SHA使用大端模式。使用大端模式。南京理工大学计算机科学与技术学院南

54、京理工大学计算机科学与技术学院 报文鉴别是使预定的报文接受者能够检验收到的报文是否真实的方法。 报文鉴别码MAC也称为密码检验和，由如下形式的函数C生成nMAC = CK(M)其中，其中，M是变长的报文，是变长的报文，K是仅由发送方与接收方共享的是仅由发送方与接收方共享的密钥，密钥，CK(M)是定长的鉴别符。是定长的鉴别符。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 MAC函数应满足的要求n假定敌手知道假定敌手知道MAC函数函数C但不知道密钥但不知道密钥K，则，则MAC函数应函数应满足以下要求：满足以下要求：n若敌手得到若敌手得到M和和CK(M)，则试图生成一个报文，则试

55、图生成一个报文M，使得，使得CK(M) = CK(M)在计算上是不可行的。在计算上是不可行的。nCK(M)应该是均匀分布的，即对于随机选择的报文应该是均匀分布的，即对于随机选择的报文M和和M，PrCK(M) = CK(M) = 2-n，其中，其中n为为MAC的比特长的比特长度。度。n若若M是是M的某个变换，即的某个变换，即M = f(M)，则，则PrCK(M) = CK(M) = 2-n。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 4.6.1 基于DES的报文鉴别码 4.6.2 HMAC算法 4.6.3 HMAC的安全性南京理工大学计算机科学与技术学院南京理工大学计算机科

56、学与技术学院 基于DES的MAC中应用最广泛的是数据鉴别算法，该算法已作为FIPS Publication （FIPS PUB 113）并被ANSI作为X9.17标准。 该算法定义为以密码分组连接（CBC）为操作模式的使用0作为初始向量的DES。 需要鉴别的数据被划分为64比特长的分组D1, D2, , DN，若有必要，最后一个分组使用0填充。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 使用DES算法和秘密密钥K，数据鉴别码DAC可以计算如下：nO1 = EK(D1)nO2 = EK(D2 O1)nO3 = EK(D3 O2)nON = EK(DN ON-1) DAC由整

57、个分组ON或该分组最左边的M比特构成，其中16M64。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 数据鉴别算法的示意图D1(64 bits)D2DES加密KO2DES加密K(56bits)DNDES加密KONON-1DES加密KDN-1O1(64 bits)DAC(16 to 64 bits)时刻时刻 = 1时刻时刻 = 2时刻时刻 = N-1时刻时刻 = N南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 数据鉴别算法DAC是常规构建MAC最常用的方法。 近年来，研究热点转向由密码散列码导出MAC，其目的在于：n密码散列函数的软件执行速度比对称分组密码快

58、；密码散列函数的软件执行速度比对称分组密码快；n可以很容易获得密码散列函数的库代码；可以很容易获得密码散列函数的库代码；n美国或其他国家对密码散列函数没有出口限制，而对称分美国或其他国家对密码散列函数没有出口限制，而对称分组密码，即便作为组密码，即便作为MAC也是有限制的。也是有限制的。 现在已经有许多将一个密钥与一个现有的散列函数结合起来的提议，获得众多支持的是HMAC。南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院 HMAC的设计目标n无需修改地使用现有散列函数。特别地，散列函数的软件无需修改地使用现有散列函数。特别地，散列函数的软件实现执行速度很快，且程序代码是公开的和

59、容易获得的。实现执行速度很快，且程序代码是公开的和容易获得的。n当出现更快或更安全的散列函数时，对算法中嵌入的散列当出现更快或更安全的散列函数时，对算法中嵌入的散列函数要能容易地进行替换。函数要能容易地进行替换。n保持散列函数的原有性能不会导致算法性能的降低。保持散列函数的原有性能不会导致算法性能的降低。n使用和处理密钥的方式简单。使用和处理密钥的方式简单。n基于对嵌入散列函数合理的假设，对鉴别机制的强度有一基于对嵌入散列函数合理的假设，对鉴别机制的强度有一个易懂的密码编码分析。个易懂的密码编码分析。 HMAC算法的结构SiY0Y1YL-1b bits b bitsb bits散列函数n bitsH(Si | M)n bitsIVK+ipadK+opadSo散列函数n bit