中国科学技术大学：《现代密码学理论与实践》课程教学资源（PPT课件讲稿）第12章 消息认证和散列函数

车衣 本章要点 15 。所有安全散列函数都有图11.9所示的一般结构 。安全散列函数里用到的压缩函数可以分为两类： 专为散列函数设计的函数或对称分组密码。安全 散列算法(SHA)和Whirlpool分别是这两种方法的 例子。 ·消息认证码也可分为两类：使用安全散列算法和 使用对称分组密码。HMAC和CMAC分别是这两 种方法的例子。 2022/10/9 现代密码学理论与实践-12 2/45

2022/10/9 现代密码学理论与实践-12 2/45 本章要点 ⚫ 所有安全散列函数都有图11.9所示的一般结构 ⚫ 安全散列函数里用到的压缩函数可以分为两类： 专为散列函数设计的函数或对称分组密码。安全 散列算法(SHA)和Whirlpool分别是这两种方法的 例子。 ⚫ 消息认证码也可分为两类：使用安全散列算法和 使用对称分组密码。HMAC和CMAC分别是这两 种方法的例子

12.1安全散列算法 安全散列算法SHA是由美国标准与技术协会NIST设讦， 并于1993作为联邦标准FIPS180发布，1995年修订为 FIPS180-1,即SHA-1,算法是SHA,标准是SHS SHA算法建立在MD4算法之上，基本框架与MD4类似 ● SHA-1产生160位散列值，以后的修订版分别为SHA 256,SHA-384,SHA-512,与SHA-1有相同的基础结构 0 2005年王晓云在Crypto05会议上发表Finding Collisions in the Full SHA-1,宣布了一种攻击方法，用 269次操作找到两个独立的消息具有相同散列值 NIST随即宣布废弃SHA-1的意图，到2010年转用其他 版本的SHA 2022/10/9 现代密码学理论与实践-12 3/45

2022/10/9 现代密码学理论与实践-12 3/45 12.1 安全散列算法 ⚫ 安全散列算法SHA是由美国标准与技术协会 NIST设计， 并于1993作为联邦标准FIPS180发布, 1995年修订为 FIPS180-1, 即SHA-1, 算法是SHA, 标准是SHS ⚫ SHA算法建立在MD4算法之上，基本框架与MD4类似 ⚫ SHA-1产生160位散列值，以后的修订版分别为SHA- 256, SHA-384, SHA-512, 与SHA-1有相同的基础结构 ⚫ 2005年王晓云在Crypto05会议上发表Finding Collisions in the Full SHA-1, 宣布了一种攻击方法，用 2 69次操作找到两个独立的消息具有相同散列值 ⚫ NIST随即宣布废弃SHA-1的意图，到2010年转用其他 版本的SHA

少因海冷长大 SHA参数比较 105 Table 12.1 Comparison of SHA Parameters SHA-1 SHA-256 SHA-384 SHA-512 Message digest size 160 256 384 512 Message size <264 <264 <2128 <2128 Block size 512 512 1024 1024 Word size 32 32 64 64 Number of steps 80 64 80 80 Security 80 128 192 256 Notes:1.All sizes are measured in bits. 2.Security refers to the fact that a birthday attack on a message digest of size n produces a collision with a workfactor of approximately 22. 2022/10/9 现代密码学理论与实践-12 4/45

2022/10/9 现代密码学理论与实践-12 4/45 SHA参数比较

安全散列标准SHS之SHA-1 15 概述 由美国NIST提出，SHS(Secure Hash Standard),算法为SHA。 ● 要求输入小于264位，输出为160位(5个寄存器，A,B,C,D,E)。 将明文分成若干512位的定长块，每一块与当前的信息摘要值 结合，产生信息摘要的下一个中间结果，直到处理完毕。共扫 描5遍，效率略低于MD5,强度略高。 ● 基本算法 ●初值：A=67452301;B=EFCDAB89;C=98 BADCFE; D=10325476;E=C3D2E1F0 A、B、C、D、E分别被复制到AA、BB、CC、DD、EE,进行 四回合迭代，每回合20步运算，每一步运算对A、B、C、D、 E中的三个寄存器进行非线性操作，然后移位。每回合有一个 常数k。 2022/10/9 现代密码学理论与实践-12 5/45

2022/10/9 现代密码学理论与实践-12 5/45 ⚫ 概述 ⚫ 由美国NIST提出, SHS(Secure Hash Standard), 算法为SHA。 ⚫ 要求输入小于2 64位，输出为160位(5个寄存器，A, B, C, D, E)。 将明文分成若干512位的定长块，每一块与当前的信息摘要值 结合，产生信息摘要的下一个中间结果，直到处理完毕。共扫 描5遍，效率略低于MD5，强度略高。 ⚫ 基本算法 ⚫ 初值：A = 67452301; B = EFCDAB89; C = 98BADCFE; D = 10325476; E = C3D2E1F0 ⚫ A、B、C、D、E分别被复制到AA、BB、CC、DD、EE，进行 四回合迭代，每回合20步运算，每一步运算对A、B、C、D、 E中的三个寄存器进行非线性操作，然后移位。每回合有一个 常数k。 安全散列标准SHS之SHA-1

SHA-1的逻辑运算 少国海车线K才 回合 Kt Ft(B,C,D) 0<=t<=19 5A827999 (B.C)V(B-iD) 20<=t<=39 6ED9EBA1 B⊕C⊕D 40<=t<=59 8F1BBCDC (B●C)v(BD)v(CD) 60<=t<=79 CA62C1D6 B⊕C⊕D 2022/10/9 现代密码学理论与实践-12 6145

2022/10/9 现代密码学理论与实践-12 6/45 SHA-1的逻辑运算 回合 Kt Ft(B, C, D) 0 <= t <= 19 5A827999 (B•C)  (B-1•D) 20 <= t <= 39 6ED9EBA1 BCD 40 <= t <= 59 8F1BBCDC (B•C)  (B•D)  (C•D) 60 <= t <= 79 CA62C1D6 BCD

SHA-1逻辑函数真值表 光@海秦我长大 1950 Table 12.2 Truth Table of Logical Functions for SHA-1 B C D f0.19 f20.39 f40.59 f60.79 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 2022/10/9 现代密码学理论与实践-12 7/45

2022/10/9 现代密码学理论与实践-12 7/45 SHA-1逻辑函数真值表

160 512 园海车不才 32 A B C D E 1,K,W0.19J 20 steps A B C D E f,K,W[2039 20 steps A B IC D f6,K,W40.59 20 steps A B C D E f,K,WL60.79] 20 steps + + /160 Note:addition (+is mod 22 CVg+l 2022/10/9 Figure 12.5 SHA-1 Processing of a Single 512-bit Block 8/45 (SHA-1 Compression Function)

2022/10/9 现代密码学理论与实践-12 8/45

SHA-1的基本操作（单步） ◆奉本 1950 A B C D E Ss Wt 30 K A B D E Figure 12.6 Elementary SHA Operation(single step) 题配三 2022/10/9 现代密码学理论与实践-12 9/45

2022/10/9 现代密码学理论与实践-12 9/45 SHA-1的基本操作(单步)

海拳术为 SHA-1的基本操作（单步） 15 每一步基本运算 A,B,C,D,E<(CLS5(A)+f(B,C,D)+E+w+k )A,CLS30(B),C,D 其中，A,B,C,D,E为寄存器 t:步数 f:基本逻辑函数 CLSx:左循环移位x位 W:由输入导出的一个32位字 k:常数 +: 模232的加运算 ● W=M4(输入的相应消息字)，0<=t<=15 W4=W4-3⊕W4-8⊕W-14⊕W4-16,16<=t<=79 SHA的安全性 ●类似MD5,增加扩展变换，160位输出，能对抗穷举攻击。 2022/10/9 现代密码学理论与实践-12 10/45

2022/10/9 现代密码学理论与实践-12 10/45 ⚫ 每一步基本运算 A, B, C, D, E  (CLS5 (A)+ft (B, C, D)+E+wt+kt ), A, CLS30(B), C, D 其中，A, B, C, D, E为寄存器 ⚫ t：步数 ⚫ ft：基本逻辑函数 ⚫ CLSx：左循环移位x位 ⚫ wt：由输入导出的一个32位字 ⚫ kt：常数 ⚫ +：模2 32的加运算 ⚫ wt = Mt (输入的相应消息字), 0 <= t <= 15 ⚫ wt = wt -3  wt -8  wt -14  wt -16, 16 <= t <= 79 ⚫ SHA的安全性 ⚫ 类似MD5，增加扩展变换，160位输出，能对抗穷举攻击。 SHA-1的基本操作(单步)

为SHA-1处理一个分组而产生的80字输入序列 195 512 bits. Wo W:Ws W13 W16W14W.8W3 W63W65W71W76 Ya XOR XOR XOR S1 S1 Wo W W15 W16 W W79 Figure 12.7 Creation of 80-word Input Sequence for SHA-1 Processing of Single Block 2022/10/9 现代密码学理论与实践-12 11/45

2022/10/9 现代密码学理论与实践-12 11/45 为SHA-1处理一个分组而产生的80字输入序列