第11章杂凑(hash)函数
第11章 杂凑（hash）函数
11.1杂凑函数的定义 ●定义111一个函数族{:y→rmn>m称为强无 碰撞压缩函数族,若下面两个条件成立。 (1)计算hn(x)是容易的,即存在一个多项式时间 算法F,若F的输入为1和x∈1,则其输出为 hn(x)。 (2)给定算法F要找两个不同的消息x≠x2(x1=x2) 使得h3(x)=h31(x2是困难的,即对每一个多项式时 间概率算法M,每一正多项式p(n)和一切充分大 的n有P(M(b Un)1")∈CnUn)<1m(n)(111) 其中Un表示{0,1}上的均匀分布随机变量
11.1 杂凑函数的定义 ⚫ 定义 11.1 一个函数族 称为强无 碰撞压缩函数族，若下面两个条件成立。 （1）计算hn (x)是容易的，即存在一个多项式时间 算法F，若F的输入为1 n和 ，则其输出为 hn (x) 。 （2）给定算法F要找两个不同的消息 ， 使得 是困难的，即对每一个多项式时 间概率算法M’，每一正多项式p(n)和一切充分大 的n有 （11.1） 其中Un表示{0,1}n上的均匀分布随机变量。 h n m n m n : 0,1 → 0,1 ; n x 0,1 ( ) 1 2 1 2 x x x = x ( ) ( ) 1 2 1 2 h x h x x x = P ( ( ),1 ) ( ) 1/ ( ) ' r M h U Cn Un p n n n n
●定理111若一个函数族{:1→:n>m为 强单向函数族,则它也是一个强无碰撞 压缩函数族。反之,若函数族{n>m为一强 无碰撞压缩函数族,且对(充分大的)每 个及x∈{0,1y,hn(X)的原象集h((x)中 至少包含两个原象,则它也是一个强单向 函数族 强无碰撞压缩函数族中的函数也称无碰撞 压缩函数或单向压缩函数
⚫定理 11.1 若一个函数族 为 一强单向函数族，则它也是一个强无碰撞 压缩函数族。反之，若函数族 为一强 无碰撞压缩函数族，且对（充分大的）每 个n及x∈{0,1}n ，hn (x)的原象集 中 至少包含两个原象，则它也是一个强单向 函数族。 ⚫强无碰撞压缩函数族中的函数也称无碰撞 压缩函数或单向压缩函数。 h n m n m n : 0,1 → 0,1 ; hn ;n m ( ( )) 1 h h x n n −
●定义112一个强无碰撞杂凑函数是一个满足下列 条件的函数h (1)h可应用于任意长的消息或文件; (2)h的值(杂凑值)是固定长的,但要足够长才能 抵抗生日攻击 (3)计算h的值h(x)是容易的,即h(x)是多项式时间可 计算的 (4)给定算法h,要找两个不同的消息x1#X2,使其杂 凑值h(x1)=h(x2)是困难的(计算不可行的),即 是由强无碰撞压缩函数族中的压缩函数所构造的 (构造方法见后)
⚫ 定义 11.2 一个强无碰撞杂凑函数是一个满足下列 条件的函数h。 (1)h可应用于任意长的消息或文件； (2)h的值（杂凑值）是固定长的，但要足够长才能 抵抗生日攻击。 (3)计算h的值h(x)是容易的，即h(x)是多项式时间可 计算的； (4)给定算法h，要找两个不同的消息x1≠x2，使其杂 凑值h(x1)=h(x2)是困难的（计算不可行的），即 是由强无碰撞压缩函数族中的压缩函数所构造的 （构造方法见后）
11.2无碰撞杂凑函数的构造方法 11.2.1用单向压缩函数构造无碰撞杂凑函数的一般方法 ●设h:801→为一单向压缩函数,其中≥m+2为选 定的正整数。首先将输入h的消息x∈{01份为长-m-1的组, 记作x=若×的长凶不能被m1整除,则在X后面添 加d个0使n=+0被-m-1整除。不妨将x0仍记作x,使 X=m-1,再附加一个分组X+1,它由d的二进数表示在其 前面添加若干个0构成,使+=m-1。杂凑函数h(x)的值 由下面的迭代算法定义 h1=h2(0m1x1) h+1=h(h1x1) A h(x)=h,1 ●定理112杂凑函数和用来构造它的单向压缩函数有几乎 同样的安全性
11.2 无碰撞杂凑函数的构造方法 11.2.1 用单向压缩函数构造无碰撞杂凑函数的一般方法 ⚫ 设 为一单向压缩函数，其中l≥m+2为一选 定的正整数。首先将输入h的消息 分为长l-m-1的组， 记作 。若x的长|x|不能被l-m-1整除，则在xr后面添 加d个0使n=|x|+d被l-m-1整除。不妨将x,0d仍记作x，使 |xr |=l-m-1，再附加一个分组xr+1，它由d的二进数表示在其 前面添加若干个0构成，使|xr+1|=l-m-1。杂凑函数h(x)的值 由下面的迭代算法定义。 ⚫ 定理 11.2 杂凑函数和用来构造它的单向压缩函数有几乎 同样的安全性。 l m hl : 0,1 → 0,1 * x 0,1 r x x x x = 1 2 (0 ) 1 1 1 h h x m l + = h h h x i r i l i i ( 1 ) 1,2, , +1 = +1 = 1 ( ) = hr+ h x
11.22用分组加密函数构造杂凑函数 ● Rabin方案 ●密码组链接方案 ●密钥链接方案 112.3用候选单向函数构造杂凑函数 ●单向函数输出值链接方案 ●单向无爪函数输出值链接方案
11.2.2 用分组加密函数构造杂凑函数 ⚫Rabin方案 ⚫密码组链接方案 ⚫密钥链接方案 11.2.3 用候选单向函数构造杂凑函数 ⚫单向函数输出值链接方案 ⚫单向无爪函数输出值链接方案
8安全杂凑算法的一般结构 Y Y L-1 n n f CVL CVI ⅣV=初始值 CV=链接值 Yi=第i个输入数据块 f=压缩算法 n=散列码的长度 b=输入块的长度
b Y0 n f b Y1 n f b YL-1 n CVL-1 f CV1 n n IV = 初始值 CV = 链接值 Yi = 第i 个输入数据块 f = 压缩算法 n = 散列码的长度 b = 输入块的长度 8 安全杂凑算法的一般结构 CVL CV0=IV= initial n-bit value CVi=f(CVi-1 , Yi-1 ) (1 i L) H(M) = CVL
9MD5算法逻辑 ●输入:任意长度的消息 ●输出:128位消息摘要 ●处理:以512位输入数据块为单位 MD5 (RFC 1321)developed by ron Rivest at mit in 90's
9 MD5 算法逻辑 ⚫输入：任意长度的消息 ⚫输出：128位消息摘要 ⚫处理：以512位输入数据块为单位 MD5 (RFC 1321) developed by Ron Rivest at MIT in 90’s
L×512bits=N×32bits 填充 (1to512 K bits bits) 报文 100..0 报文长度 (K mod 264 512 bits 512 bits 512 bits 512 bits Y q YI 512 512 512 512 128 128 128 128 MDS MDS MDS MD5 CⅤ CV CVL MD5产生报文摘要的过程 128-bit 摘要
报文 K bits L512 bits=N 32bits 报文长度 (K mod 264) 100…0 Y0 512 bits Y1 512 bits Yq 512 bits YL-1 512 bits HMD5 IV 128 HMD5 CV1 128 HMD5 CVq 128 HMD5 CVL-1 128 512 512 512 512 128-bit 摘要 MD5产生报文摘要的过程 填充 (1 to 512 bits)
11MD5算法描述 ●步骤1:添加填充位(一个1和若干个0)。在消息的最 后添加适当的填充位使得数据位的长度满足 ength≡ 448mod512。 步骤2:添加长度。原始消息长度(二进制位的个数 ),用64位表示 表示为L个512位的数据块:YY1YL1其长度为 L×512bits。令N=Lx16则长度 为N个32位的字。令M[0.N-1表示以字为单位的消息 表示
11 MD5算法描述 ⚫ 步骤1： 添加填充位(一个1 和若干个0)。在消息的最 后添加适当的填充位使得数据位的长度满足length 448 mod 512。 ⚫ 步骤2： 添加长度。原始消息长度（二进制位的个数 ），用64位表示。 表示为L个512位的数据块：Y0 ,Y1 ,…,YL-1。其长度为 L512bits。令N=L16,则长度 为N个32位的字。令M[0…N-1]表示以字为单位的消息 表示