第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