第11章 消息认证和散列函数 11章
(2) 初始化： A: 01 B: 89 C: fe D: 76 23 ab dc 54 45 cd ba 32 67 ef 98 10
(3) 主循环：经过4轮，每轮16次的处理。 (4) 输出： 消息摘要=
90015098 3cd24fb0 d6963f7d 28e17f72
第11章 消息认证和散列函数 11章
MD5算法 MD5对输入的任意长度消息产生128位散列值：
填填填 消消消消(K mod64) 2
L×512 bit＝N×32 bit K bit
消消
100…0
MD5算法五个步骤： 算法五个步骤： 算法五个步骤
512 bit Y0 512 IV 128 HMD5 CV 1 128
MD5 算 法
MD表示消息摘要(Message Digest),单向散列函数输入： 给定一任意长度的消息 输出： 长为m的散列值。 压缩函数的输入： 消息分组和前一分组的输出(对第一个函数需初始化向量IV)； 输出： 到该点的所有分组的散列，即分组Mi的散列为 hi=f (Mi, hi−1) 循环： 该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入，最 后一分组的散列就是整个消息的散列。
M[0]=61626380 M[1]=00000000 M[2]=00000000 M[3]=00000000 M[4]=00000000 M[5]=00000000 M[6]=00000000 M[7]=00000000 M[8]=00000000 M[9]=00000000 M[10]=00000000 M[11]=00000000 M[12]=00000000 M[13]=00000000 M[14]=00000000 M[15]=00000018
为什么？
对称加密既可提供认证，又可以提供保密性， 但是这不是绝对的。 从认证的角度看，如果消息M可以是任意的 位模式，那么接收方无法确定接收到的消息 是合法的明文。 对接收到的密文解密所得明文得可读性进行 自动判别，是一件困难的事情。
第11章 消息认证和散列函数 11章
11.2.2 消息认证码 消息认证码(MAC)
四轮操作的不同之处在于每轮使用的非线性函数不同，分别 为(其输入/输出均为32位字)： F(X,Y,Z) = (X^Y) ˇ((～X) ^Z) G(X,Y,Z) = (X^Z)ˇ(Y^ (～Z)) H(X,Y,Z) = X＋Y＋Z I(X,Y,Z) = Y＋(Xˇ (～Z)) 其中，^表示按位与； ˇ表示按位或； ～表示按位反； ＋表示按位异或。
100…0
512 bit Y 0 512 IV 160 H SHA CV 1 160
512 bit Y 1 512 HSHA … CV －1 L 160 …
512 bit Y －1 L 512 H SHA 160填消消位位
图3-5 SHA–1算法
第11章 消息认证和散列函数 11章
1) 填充消息
将消息填充为512位的整数倍，填充方法和MD5完全相同。
第11章 消息认证和散列函数 11章
还要求：
能用于任何大小的消息； 能产生定长输出； 寻找任意 任意的M和M’，会满足H(M)=H(M’)很难。 任意
实现：
单向散列函数是建立在压缩函数之上的：
消消消消1
消消消消2
…

消消消消n
填填填
IV
压压 非非
压压 非非
…
压压 非非
非非函
第11章 消息认证和散列函数 11章
还用到常数字序列K0、K1、…、K79： Kt = 0x5A827999 Kt = 0x6ED9EBA1 Kt = 0x8F1BBCDC Kt = 0xCA62C1D6 (0≤t≤19) (20≤t≤39) (40≤t≤59) (60≤t≤79)
第11章 消息认证和散列函数 11章
SHA算法按如下步骤处理每个字块Mi：
– – – 用3轮每轮16步，用了三个非线性函数， 没有T[i]常量加 每轮没有叠加上轮的结果；
RSA 实验室将 MD5 描述为“系有安全带的 MD4”，虽然比 MD4 慢， 但却被认为是安全的，对大数在前的系统性能较好。 SHA也是以MD4以基础设计的。
第11章 消息认证和散列函数 11章
安全散列函数(SHA) 安全散列函数
第11章 消息认证和散列函数 11章
第11章 消息认证和散列函数 章
第11章 消息认证和散列函数 11章
在网络环境中，存在下述的攻击： 1. 泄密 2. 传输分析 3. 伪装 4. 内容修改 5. 顺序修改 6. 计时修改 7. 发送方否认 8. 接收方否认 消息认证 数字签名
第11章 消息认证和散列函数 11章
A B C D CV q＋1
第11章 消息认证和散列函数 11章
四轮的操作类似，每轮16次：
用 到 一 个 有 64 个 元 素 的 表 T[1..64] ， T[i]=232×abs(sin(i))，i的单位为弧度。
16次
a b c d
a M j T[i] b
非非非非非
＋
＋
＋
<<<s
＋
c d
第11章 消息认证和散列函数 11章
第11章 消息认证和散列函数 11章
源源A M K Ⅱ
目目源B M C 比比 K CK(M)
C
图11.4 MAC应用于消息认证
第11章 消息认证和散列函数 11章
第11章 消息认证和散列函数 11章
单向散列函数
单向散列函数： Hash Function，哈希函数、杂凑函数 将任意长度的消息M映射成一个固定长度散列值h的函数： h=H(M) 其中，h的长度为m。 用途： 消息认证、数字签名。 MESSAGE πασσωορδ 哈希算法
2) 初始化缓冲区
SHA要用到两个缓冲区，均有五个32位的寄存器。 第一个缓冲区：A、B、C、D、E； 第二个缓冲区：H0、H1、H2、H3、H4。 运算过程中还用到一个标记为W0、W1、…、W79的80个32位字序 列和一个单字的缓冲区TEMP。 在运算之前，初始化{Hj}： H0 = 0x67452301 H1 = 0xEFCDAB89 H2 = 0x98BADCFE H3 = 0x10325476 H4 = 0xC3D2E1F0
与密钥相关的单向散列函数通常称为MAC（消息认证码）： MAC=CK(M) 其中：
M为可变长的消息；K为通信双方共享的密钥；C为单向函数。
用途： 为拥有共享密钥的双方在通信中验证消息的完整性； 被单个用户用来验证他的文件是否被改动。
第11章 消息认证和散列函数 11章
MAC函数与加密类似，其区别之一是： MAC算法不要求可逆性而加密算法必 须是可逆的。
512 bit Y1 512 HMD5 … CV －1 L 128 …
512 bit YL－1 512 HMD5
1) 附加填充位 2) 附加长度 3) 初始化MD缓冲区 4) 按512位的分组处理 5) 输出
128填消消位位
第11章 消息认证和散列函数 11章 1) 附加填充位 填充消息，使其长度为一个比512的倍数小64位的数。 填充方法：在消息后面填充一位1，然后填充所需数量的0。填 充位的位数从1～512。
第11章 消息认证和散列函数 11章
Ron Rivest的贡献 的贡献
MD2、MD4 和 MD5 都是由 Ron Rivest开发的： MD2 是为 8 位计算机系统设计的； MD4 开始是为 32 位计算机系统开发的，适合小数在前的系统（80x86 和pentium），1990 开发，简单易于编程，现在被认为是不安全的：
(1) 把Mi分为16个字W0、W1、…、W15，其中，W0为最左边的字。 (2) for t =16 to 79 do let Wt =(Wt−3 Wt−8 Wt−14 ⊕ Wt−16)<<<1 ⊕ ⊕ (3) Let A =H0，B =H1，C =H2，D =H3，E =H4 (4) for t =0 to 79 do TEMP = (A<<<5)+ft (B, C, D)+E +Wt +Kt ; E =D; D =C; C =(B<<<30); B = A; A = TEMP; (5) Let H0 =H0 +A, H1 =H1 +B, H2 =H2 +C, H3 =H3 +D, H4 =H4 +E
第11章 消息认证和散列函数 11章
单向散列函数Hash 单向散列函数
（1）单向散列函数是消息认证的一种变形。 （2）与MAC不同的是，散列码并不使用密钥， 它仅是输入消息的函数。 （3）散列码是所有消息位的函数，它具有错 误检测能力，即改变消息的任何一位或者多位， 都会导致散列码的改变。
第11章 消息认证和散列函数 11章
第11章 消息认证和散列函数 11章
第11章 消息认证和散列函数 11章
一个简单的散列函数
每个分组按比特异或(简单奇偶校验)：
Ci = bi1 ⊕ bi2 ⊕ ... ⊕ bim
改进： 针对可预测数据，每次循环左移一位将数据和散列值 再异或。 结果： 随机化、去格式化
第11章 消息认证和散列函数 11章
第11章 消息认证和散列函数 11章 3) 按512位的分组处理输入消息 SHA运算主循环包括四轮，每轮20次操作。 逻辑函数序列f0 、f1 、…、f79 ，每个逻辑函数的输入为三个 32位字，输出为一个32位字：
ft (B,C,D) = (B^C) ˇ(~B^D) ft (B,C,D) = B＋C＋D ft (B,C,D) = (B^C) ˇ(B^D) ˇ(C^D) ft (B,C,D) = B＋C＋D (0≤t≤19) (20≤t≤39) (40≤t≤59) (60≤t≤79)