第十一讲 认证、哈希算法.pptVIP

第十一讲 认证、哈希算法 上海交通大学计算机科学系 1. Message Authentication 消息认证包括: 消息完整性 身份识别 不可否认性 2. 消息认证码 (MAC)  message authentication code (MAC) 签名的电子等价形式 与消息同时发送 通过一些算法, 依赖于消息及双方共享的秘密 消息可以是不任意长 MAC 可以是任意长,但常选固定长度 这需要hash function “压缩”消息成固定长度 3. 消息认证过程  4. 1利用对称密码进行认证 利用对称密码加密的消息可以作为认证内容 因为只有密钥的拥有者才可以生成 (要求消息有一定的冗余度) 但不能解决消息的不可否认性 （无法证明谁生成的消息） 4.2 报文鉴别码 5. Hashing Functions 把任意长的消息“压缩”成固定长的消息的算法 数字签名时，常被使用 通常，HASH 函数是公开的 输出长度应足够大，防止生日攻击 64-bits 认为太小 通常 128-512bits 6. Hash 函数设计原理 H能用于任何大小的数据分组; H产生定长输出; 对任意给定的x, H(x)要相对易于计算,使得软硬件实现都实际可行; 对任意给定的码h, 寻求x使得H(x)=h在计算上是不可行的(单向性); 任意给定分组x, 寻求不等于x的y, 使得H(y)= H(x)在计算上不可行(弱抗攻击性); 寻求对任何的(x,y)对使得H(x)=H(y)在计算上不可行(强抗攻击性); 7 Hash 函数设计原理 生日攻击(基于生日悖论) 在k个人中,找一个与某人生日相同的人的 概率超过0.5时,只需k183; 而在此人群中, 至少有两个人生日相同的概率超过0.5,只需 k23. 9 MD5 算法逻辑 输入：任意长度的消息 输出：128位消息摘要 处理：以512位输入数据块为单位 MD5 (RFC 1321) developed by Ron Rivest at MIT in 90’s. 11 MD5算法描述 步骤1： 添加填充位(一个1 和若干个0)。在消息的最后添加适当的填充位使得数据位的长度满足length ? 448 mod 512。 步骤2： 添加长度。原始消息长度（二进制位的个数），用64位表示。 表示为L个512位的数据块：Y0,Y1,…,YL-1。其长度为L?512bits。令N=L?16,则长度 为N个32位的字。令M[0…N-1]表示以字为单位的消息表示。 12 MD5算法描述(Cont.) 步骤3：初始化MD缓冲区。一个128位MD缓冲区用以保存中间和最终散列函数的结果。它可以表示为4个32位的寄存器(A,B,C,D)。 寄存器初始化为以下的16进制值。 A = B = EFCDAB89 C = 98BADCFE D = 13 Word A: 01 23 45 67 Word B: 89 AB CD EF Word C: FE DC BA 98 Word D: 76 54 32 10 14 MD5算法描述(Cont.) 步骤4：处理消息块（512位 = 16个32位字）。一个压缩函数是本算法的核心(HMD5)。它包括4轮处理。四轮处理具有相似的结构,但每次使用不同的基本逻辑函数，记为F,G,H,I。每一轮以当前的512位数据块(Yq)和128位缓冲值ABCD作为输入，并修改缓冲值的内容。每次使用64元素表T[1…64]中的四分之一 T表，由sin 函数构造而成。T的第i个元素表示为T[i]，其值等于 232?abs(sin(i)),其中i是弧度。由于abs(sin(i))是一个0到1之间的数，T的每一个元素是一个可以表示成32位的整数。T表提供了随机化的32位模板，消除了在输入数据中的任何规律性的特征 15 T 表 16 MD5算法描述(Cont.) 步骤5：输出结果。所有L个512位数据块处理完毕后，最后的结果就是128位消息摘要。 CV0 = IV CVq+1 = SUM32(CVq,RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]) MD = CVL 其中：IV = ABCD的初始值（见步骤3） Yq = 消息的第q个512位数据块 L = 消息中数据块数； CVq = 链接变量，用于第q个数据块的处理 RFx = 使用基本逻辑函数x的一轮功能函数。 MD = 最终消息摘要结果 SUM