杂凑函数 Hash functions 2021/2/21
2021/2/21 2 杂凑函数 Hash Functions
迭代型杂凑函数的一般结构 明文M被分为L个分组 Y L-1 b:明文分组长度 n:输出hash长度 b b CV:各级输出,最后 个输出值是hash值 CVL n n V=CV CV CV 无碰撞压缩函 数f是设计的 关键 2021/2/21
2021/2/21 3 迭代型杂凑函数的一般结构 f f f Y0 Y1 YL-1 b b b n n n n n IV=CV0 CV1 CVL-1 CVL 明文M被分为L个分组 Y0 ,Y1 ,…,YL-1 b:明文分组长度 n:输出hash长度 CV:各级输出,最后 一个输出值是hash值 无碰撞压缩函 数f是设计的 关键
MD5杂凑算法 MD5 Hash Algorithm 2021/2/21
2021/2/21 4 MD5杂凑算法 MD5 Hash Algorithm
法步骤(1)一分组填充 Ron rivest于1990年提出MD-4杂凑算法。输 入消息可任意长,压缩后输出为128bits 1992年改进为MD-填充图样 消息长度 消息 100..0 64bit Kbit L×512bt 2021/2/21 5
2021/2/21 5 算法步骤(1)-分组填充 ◼ Ron Rivest于1990年提出MD-4杂凑算法。输 入消息可任意长,压缩后输出为128bits。 1992年改进为MD-5。 消息 100…0 64bit 填充图样 消息长度 L×512bit Kbit
算法步骤(2)一缓冲初始化 每轮輪出为128bit,可用4个32b字表示 A,B,C,D。初始存数以十六进制表示为 A=01234567, B=89ABCDEF C=FEDCBA98 D=76543210。 2021/2/21 6
2021/2/21 6 算法步骤(2)-缓冲初始化 每轮输出为128 bit,可用4个32bits字表示: A,B,C,D。初始存数以十六进制表示为 A=01234567, B=89ABCDEF, C=FEDCBA98, D=76543210
法步骤(3)-HMDs运算 ■对512bit(16-字)组进行运算,表示輪入 的第q组512bit数据,在各轮中参加运算 71,,64]为64个元素表,分四组参与不同 轮的计算。丌为232×abs(sine()的整教部 分,侵是孤度。T[小可用32bt二元教表示,7 是32bt随机数娠。 2021/2/21
2021/2/21 7 算法步骤(3) -HMD5运算 ◼ 对512 bit(16-字)组进行运算,Yq表示输入 的第q组512bit数据,在各轮中参加运算。 ◼ T[1,…,64]为64个元素表,分四组参与不同 轮的计算。T[i]为2 32×abs(Sine(i))的整数部 分,i是弧度。T[i]可用32 bit二元数表示,T 是32 bit随机数源
MDq, 128 ABCn"厂ABCp,rqu7tt.f6」) ABCDTG(BC4, Yq,[T7.321) AB C D ABCD H(ABCD Yq, /133...48]) AB a 3 斤团决。64 mod 232 MD5的一个 2021/2/21 Mn+1128 512bi组的处理
2021/2/21 8 MDq ,128 Yq 512 A B C D 32 ABCD"fF (ABCD,Yq,T[1…16]) A B C D ABCD"fG(ABCD,Yq,T[17…32]) A B C D ABCD"fH(ABCD,Yq,T[33…48]) A B C D ABCD"fI (ABCD,Yq,T[49…64]) + + + + + :mod 2 32 MD-5的一个 MDq+1 128 512-bit组的处理
轮运算 ■MD-5是四轮运算,各轮逻辑函数不同。每轮又 要进行16步迭代运算,4轮共需64步完成。每步 完成 a←b+CLS(a+(B,c,D+Xk+丌小) 其中 ab,Gc=缓存器中的四个字,按特定次序变化。 8=基本逻辑函数F,GH,冲中之一,算法的每一轮 用其中之一。 2021/2/21
2021/2/21 9 轮运算 ◼ MD-5是四轮运算,各轮逻辑函数不同。每轮又 要进行16步迭代运算,4轮共需64步完成。每步 完成 a b+CLSS (a+g(B,C,D)+X[k]+T[i]) 其中 a,b,c,d=缓存器中的四个字,按特定次序变化。 g=基本逻辑函数F, G, H, I中之一,算法的每一轮 用其中之一
A B C D Ⅹ[k] CLSs:循环左移s位 第q512-bt组 的第k个32-b字 7:矩阵T中第个 32bit字 CLS :模232加法 A B C D 2021z/z
2021/2/21 10 A B C D A B C D + + + CLSS + + X[k] T[i] CLSs:循环左移s位。 X[k]:第q-512-bit组 的第k个32-bit字。 T[i]:矩阵T中第I个 32-bit字。 +:模2 32加法
基本逻辑函教定义 轮基本函数gg(b,c,d) f F(b,c,d) (b.c)v(b-d) f G(b,c, d)(bd)V(cd fH H(b,c, d) beco f1 I(b, c, d) cG(b·d 2021/2/21
2021/2/21 11 基本逻辑函数定义 轮 基本函数 g g(b, c, d) fF F(b,c,d) (b•c)V(b•d) fG G(b,c,d) (b•d)V(c• d¯) fH H(b,c,d) bcd fI I(b,c,d) c(b•d¯)