第六章 hash函数.ppt

①四个轮运算的结构相同，但各轮使用不同的基本逻辑函数，我们分别称之为F、G、H和I。 ②每轮的输入是当前要处理的512位的分组Yq和128位缓冲区的当前值A、B、C、D的内容，输出仍然放在缓冲区中以产生新的A、B、C、D。 ③每轮的处理过程还需要使用常数表T中元素的1/4。第4轮的输出再与第1轮的输入CVq相加，相加时将CVq看作4个32比特的字，每个字与第4轮输出的对应的字按模232相加,相加的结果就是本轮压缩函数HMD5的输出。 HMD5压缩函数要用到常数表T，表T有64个元素，如表6.1 所示,该表通过正弦函数构建。表中第i个元素T[i]为232×abs (sin(i))的整数部分，其中sin为正弦函数，i的单位为弧度。由于abs(in(i))大于0小于1，所以T[i]可由32比特的字来表示。 表6.1 常数表T （5）输出：消息的所有L个分组被处理完以后，最后一个HMD5的输出即为产生的消息摘要（Hash值）。图6.4为MD5的消息处理框图。 图6.4 MD5的消息处理框图 压缩函数HMD5中有4轮处理过程，每轮又对缓冲区A、B、C、D进行16步迭代运算，每一步的运算形式为，如图6.5所示。 a ---b + ( a + g(b, c, d) + X[k] + T[i]) s 图 6.5 压缩函数中的一步迭代 其中符号为： a, b, c, d 缓存中四个字； g 函数F, G, H, I中的一个； s 32bit的参数循环左移s个比特； X [k] 在第q个长度为512比特的分组 中的第k个32比特的字； T [i] 常数表T中的第i个32比特的字； + 模232的加法； MD5压缩函数要经过4轮处理过程中，每轮又包括16步，且每轮以不同的次序使用16个字。其中在第一轮以字的初始次序使用，第二轮到第四轮，分别对字的次序i做置换后得到一个新次序，然后以新次序使用16个字。 三个置换分别为： P2(i)＝(1＋5 i) mod 16 P3(i)＝(5＋3 i) mod 16 P4(i)＝7 i mod 16 4轮处理过程中分别使用基本的逻辑函数F、G、H、I。每个逻辑函数的输入为3个32比特的字，输出是一个32比特的字，其中的运算为逐比特的逻辑运算，四个逻辑函数的定义如下： F(X, Y, Z)＝(X∧Y) ∨( (﹁X )∧Z) G(X, Y, Z)＝(X∧Y ) ∧(Y∧(﹁Z)) H(X, Y, Z)＝X ? Y ? Z I(X, Y, Z)＝Y ? (X∨(﹁Z)) 其中：∧是与，∨是或，?是异或，﹁是反。 4轮处理过程中，每一轮的16步都一个循环左移，移动的位数用s表示，如表6.2所示。 表6.2 压缩函数每步左循环移位的位数 如果设Mj表示消息的512比特的分组中的第j个32比特的字（0≤j≤15），s表示循环左移位s位，则对应于4轮中的4种操作： FF(a, b, c, d, Mj, s, T[i])： a＝b＋((a＋(F(b, c, d)＋Mj＋T[i])s) GG(a, b, c, d, Mj, s, T[i])： a＝b＋((a＋(G(b, c, d)＋Mj＋T[i])s) HH(a, b, c, d, Mj, s, T[i])： a＝b＋((a＋(H(b, c, d)＋Mj＋T[i])s) I I(a, b, c, d, Mj, s, T[i])： a＝b＋((a＋(I(b, c, d)＋Mj＋T[i])s) 则MD5压缩函数HMD5的四轮可表示为: 第一轮的16步： 第二轮的16步： 第三轮的16步： 第四轮的16步： * 第六章 Hash函数 曹天杰 中国矿业大学计算机学院 6.1 HASH函数的性质 6.2 HASH函数实例 6.3 HASH的应用举例 Hash函数的目的是为指定的消息产生一个消息“指纹”， Hash函数通常具有以下这些性质： （1）压缩性：Hash函数将一个任意比特长度的输入x，映射为固定长度为n的输出H ( x )。 （2）正向计算简单性：给定Hash函数H和任意的消息输入x，计算H ( x )是简单的。 6.1 Hash函数的性质 （3）逆向计算困难性：对给定的任意值y，求使得H ( x )＝y的x在