哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　免费在线 Hash函数数据的完整性是指数据从发送方产生，经过传输或存储以后，未被以未授权的方式修改的性质。密码学中的Hash函数在现代密码学中扮演着重要的角色，该函数不同于计算机应用领域中的Hash函数，本书中所讲的都是密码学中的Hash函数。Hash函数是一个将任意长度的消息序列映射为较短的、固定长度的一个值的函数。密码学上的Hash函数能够保障数据的完整性，它通常被用来构造数据的“指纹”(即函数值)，当被检验的数据发生改变的时候，对应的“指纹”信息也将发生变化。这样，即使数据存储在不安全的地方，也可以通过数据的“指纹”信息来检测数据的完整性。 设H是一个Hash函数，x是消息，不妨假设x是任意长度的二元序列，相应的“指纹” 定义为y=H(x)， Hash函数值通常也称为消息摘要(Message Digest)。一般要求消息摘要是相当短的二元序列，常用的消息摘要是160位。如果消息x被修改为x′，则可以通过计算消息摘要y′=H(x′)并且验证y′=y是否成立来确认数据x是否被修改的事实。如果y′≠y，则说明消息x被修改，从而达到了检验消息完整性的目的。对于Hash函数的安全要求，通常采用下面的三个问题来进行判断。如果一个Hash函数对这三个问题都是难解的， 则认为该Hash函数是安全的。用X表示所有消息的集合(有限集或无限集)，Y表示所有消息摘要构成的有限集合。 定义4.1.1 原像问题(Preimage Problem) 设H：X→Y是一个Hash函数，y∈Y。是否能够找到x∈X，使得H(x)=y。如果对于给定的消息摘要y，原像问题能够解决，则(x，y)是有效的。不能有效解决原像问题的Hash函数称为单向的或原像稳固的。定义4.1.2 第二原像问题(Second Preimage Problem) 设H: X→Y是一个Hash函数，x∈X。是否能够找到x′∈X，使得x′≠x，并且H(x′)=H(x)。如果第二原像问题能够解决，则(x′，H(x))是有效的二元组。不能有效解决第二原像问题的Hash函数称为第二原像稳固的。 定义4.1.3 碰撞问题(Collision Problem) 设H: X→Y是一个Hash函数。是否能够找到x，x′∈X，使得x′≠x，并且H(x′)=H(x)。对于碰撞问题的有效解决并不能直接产生有效的二元组，但是，如果(x，y)是有效的二元组，并且x′，x是碰撞问题的解，则(x′，y)也是一个有效的二元组。不能有效解决碰撞问题的Hash函数称为碰撞稳固的。 实际应用中的Hash函数可分为简单的Hash函数和带密钥的Hash函数。带密钥的Hash函数通常用来作为消息认证码(Message Authentication Code)。假定Alice和Bob有一个共享的密钥k，通过该密钥可以产生一个Hash函数Hk。对于消息x，Alice和Bob都能够计算出相应的消息摘要y=Hk(x)。Alice通过公共通信信道将二元组(x，y)发送给Bob。当Bob接收到(x，y)后，它可以通过检验y=Hk(x)是否成立来确定消息x的完整性。如果y=Hk(x)成立，说明消息x和消息摘要y都没有被篡改。 下面给出带密钥的Hash函数族的定义。定义4.1.4 一个带密钥的Hash函数族包括以下构成要素：(1) X：所有消息的集合(有限集或无限集)；(2) Y：所有消息摘要构成的有限集合；(3) K：密钥空间，是所有密钥的有限集合；(4) 对任意的k∈K，都存在一个Hash函数Hk∈H，Hk: X→Y。如果Hk(x)=y，则二元组(x，y)∈X×Y称为在密钥k下是有效的。 Hash函数的目的是为文件、报文或者其他的分组数据提供完整性检验。要实现这个目的，设计的Hash函数H必须具备以下性质：(1) H能够用于任何大小的数据分组；(2) H产生定长的输出；(3) 对任意给定的x，H(x)要易于计算，便于软件和硬件实现;(4) 对任意给定的消息摘要y，寻找x使得y=H(x)在计算上是不可行的；(5) 对任意给定的消息x，寻找x′，x′≠x，使得H(x)=H(x′)在计算上是不可行的； (6) 寻找任意的(x，x′)，使得H(x)=H(x′)在计算上是不可行的。 以上6个条件中，前3个条件是Hash函数能够用于消息认证的基本要求；第4个条件是指Hash函数具有单向性；第5个条件用于消息摘要被加密时防止攻击者的伪造；第6个条件用于防止生日攻击。 生日攻击的思想来源于概率论中一个著名的问题——生日问题。该问题是问一个班级中至少要有多少个学生才能够使得有两个学生生日相同的概率大于1/2。该问题的答案是23。即只要班级中学生的人数大于23人，则班上有两个人生日相同的概率就将大于1/2。基于生日问题的生日攻击意味着要保证消息摘要对碰撞问题是安全的，则安全消息摘要的长度就有一个下界。例如，长度为40比特的消息摘要是非常不安全的，因为仅仅在220(大约为一百万)个随机Hash函数值中就有50%的概率发现一个碰撞。所以对于安全的消息摘要，现在通常建议可接受的最小长度为128比特(此时生日攻击需要超过264个Hash函数值)。而实际使用的消息摘要一般为160比特甚至更长。 4.1.2 随机预言模型本小节介绍一种Hash函数的某种理想化模型，该模型对于每一个消息，都试图得到一个理想的Hash函数值。由Bellare和Rogaway提出的随机预言模型(Random Oracle Model)是一种 “理想化”的Hash函数数学模型。在这个模型中，随机从FX，Y中选出一个Hash函数H: X→Y，仅仅允许预言器访问函数H，这表示对于任一个消息x，随机预言模型都不会给出一个公式或者算法来计算消息摘要H(x)的值。因此，计算H(x)值的惟一方法是询问预言器，这种Hash函数模型相当于根据给出的消息x，在一本关于随机数的书中查询H(x)的值，对于每一个x，都有一个完全随机的H(x)与之对应。 定义4.1.5 令FX，Y是所有从X到Y的函数集合。假定X=N，Y=M，则FX，Y=MN。任何Hash函数族FFX，Y被称为一个(N，M)—Hash族。对于随机预言模型，以下结论是成立的。定理4.1 随机选择H∈FX，Y并取子集合X0X。假设当且仅当x∈X0时，H(x)的值由查询预言器确定，那么对于所有的x∈X＼X0和y∈Y，P(H(x)=y)=。在以上结论中，概率P(H(x)=y)实际上是对任意的x∈X，计算相应的函数H(x)的值，从而得到指定值的条件概率。通过该结论可知，M的值越大，相应地产生碰撞的概率就越小。 基于压缩函数compress构造迭代Hash函数包括以下三步：(1) 预处理。输入一个消息x，其中x≥m+t+1，基于x构造相应的位串y(y≡0 mod t)的过程如下： y=y1‖y2‖…‖yr其中，yi=t，1≤i≤r，r为消息分组的个数。 (2) 迭代压缩。设z0是一个公开的初始位串，z0=m。具体的迭代过程如下： z1←compress(z0‖y1) z2←compress(z1‖y2) zr←compress(zr-1‖yr)最终得到长度是m的位串zr。 (3) 后处理。设g: {0，1} m→{0，1} t是一个公开函数，定义H(x)=g(zr)。则有  在上述预处理过程中常采用以下方式实现： y=x‖pad(x)其中，pad(x)是填充函数，一个典型的填充函数是在消息x后填入x的值，并填充一些额外的比特，使得所得到的比特串y是t的整数倍。在预处理阶段，必须保证映射x→y是单射(如果映射x→y不是一一对应的，就可能找到x≠x′使得y=y′，则有H(x)=H(x′)，从而设计的H将不是碰撞稳固的)，同时保证x‖pad(x)是t的整数倍。 基于压缩函数compress构造迭代Hash函数的核心技术是设计一种无碰撞的压缩函数compress，而攻击者对算法的攻击重点也是compress的内部结构。由于迭代Hash函数和分组密码一样是由compress压缩函数对消息x进行若干轮压缩处理组成的，因此对compress的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找到compress的碰撞。由于compress是压缩函数，其碰撞是不可避免的，因此在设计compress 时就应保证找出其碰撞在计算上是不可行的。 下面介绍几个重要的迭代Hash函数。 4.3.1 MD4MD4算法中涉及到如下一些基本运算：(1) X∧Y：X和Y进行逻辑与运算；(2) X∨Y：X和Y进行逻辑或运算；(3) X⊕Y：X和Y进行逻辑异或运算；(4) ：X的逻辑补运算；(5) X+Y：整数模232加法运算；(6) Xs：将X循环左移s位(0≤s≤31)。MD4算法的具体过程如下。首先输入任意长度的消息x，由x构造一个数组序列 M=M［0］M［1］…M［n-1］其中，M［i］=32，0≤i≤n-1，n≡0 mod 16。 在得到M的基础上，MD4构造Hash函数H(x)的方法如下：(1) 给定4个寄存器A、B、C、D(也称为链接变量)，对其赋初值： A B=efcdab89 C=98badcfe D其中，0，1，2，3，4，5，6，7，8，9，a，b，c，d，e，f表示一个十六进制的数字或一个长度为4的二进制序列。(2) 计算 X［j］=M［16i+j］其中，0≤i≤(n/16)-1，0≤j≤15。 (3) 将已有的4个寄存器A、B、C、D中的数组分别存放到另外4个寄存器AA、BB、CC、DD中。(4) 执行第一作。具体内容包括： A=(A+F(B，C，D)+X［4k］)3  D=(D+F(A，B，C)+X［4k+1］) 7 C=(C+F(D，A，B)+X［4k+2］) 11 B=(B+F(C，D，A)+X［4k+3］) 19其中，0≤k≤3，F(X，Y，Z)=(X∧Y)∨( ∧Z)。 (5) 执行第二作。具体内容包括：A=(A+G(B，C，D)+X［k］+5a827999)3 D=(D+G(A，B，C)+X［4+k］+5a827999) 5C=(C+G(D，A，B)+X［8+k］+5a827999) 9B=(B+G(C，D，A)+X［12+k］+5a827999) 13其中，0≤k≤3，G(X，Y，Z)=(X∧Y)∨(X∧Z)∨(Y∧Z)。 (6) 执行第三作。具体内容包括： A=(A+H(B，C，D)+X［0］+6ed9eba1) 3 D=(D+H(A，B，C)+X［8］+6ed9eba1) 9 C=(C+H(D，A，B)+X［4］+6ed9eba1) 11 B=(B+H(C，D，A)+X［12］+6ed9eba1) 15 A=(A+H(B，C，D)+X［2］+6ed9eba1) 3 D=(D+H(A，B，C)+X［10］+6ed9eba1) 9 C=(C+H(D，A，B)+X［6］+6ed9eba1) 11 B=(B+H(C，D，A)+X［14］+6ed9eba1) 15 A=(A+H(B，C，D)+X［1］+6ed9eba1)3 D=(D+H(A，B，C)+X［9］+6ed9eba1) 9 C=(C+H(D，A，B)+X［5］+6ed9eba1) 11 B=(B+H(C，D，A)+X［13］+6ed9eba1) 15 A=(A+H(B，C，D)+X［3］+6ed9eba1) 3 D=(D+H(A，B，C)+X［11］+6ed9eba1) 9 C=(C+H(D，A，B)+X［7］+6ed9eba1) 11 B=(B+H(C，D，A)+X［15］+6ed9eba1) 15其中，H(X，Y，Z)=X⊕Y ⊕ Z。(7) A=A+AA，B=B+BB，C=C+CC，D=D+DD。(8) 输出H(x)=A‖B‖C‖D，得到128位的消息摘要。 4.3.2 MD5MD5算法以512位的分组长度来处理消息，每一个分组又被划分为16个32位的子分组。算法的输出由4个32位的分组组成，它们串联成一个128位的消息摘要。MD5算法的具体过程如下。首先对消息x进行预处理，使其长度恰好比512的整数倍小64。然后在其后面附上用64位表示的消息长度信息。得到的结果序列长度恰好是512的整数倍。 在此基础上，MD5构造Hash函数H(x)的方法如下：(1) 对给定的4个寄存器A、B、C、D赋初值： A B=89abcdef C=fedcba98 D其中，0，1，2，3，4，5，6，7，8，9，a，b，c，d，e，f表示一个十六进制的数字或一个长度为4的二进制序列。 (2) 将以上得到的寄存器的值赋给相应的变量AA、BB、CC、DD。然后对512位的消息分组序列应用主循环进行处理，循环的次数是消息中512位的分组数。每一次的主循环都有四轮(注：MD4只有三轮) 操作，而且这四作都很相似。每一轮进行16次操作，每次操作对AA、BB、CC、DD中的三个作一次非线性的函数运算，然后将得到的结果加上第四个变量，再加上消息的一个子分组和一个常数。再将所得结果循环右移一个不定的数(在MD5算法中给出了具体的数值)，并加上AA、BB、CC、DD其中的一个。最后用得到的结果取代AA、BB、CC、DD其中的一个。 以上过程中用到的四个非线性函数分别定义为 在此基础上，设Mj表示消息的第j个子分组，0≤j≤15。则以上过程中四种基本操作分别定义为AA=FF(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+F(BB,CC,DD)+Mj+tj)s)AA=GG(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+G(BB,CC,DD)+Mj+tj) s)AA=HH(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+H(BB,CC,DD)+Mj+tj) s)AA=II(AA,BB,CC,DD,Mj,s,tj)=BB+((AA+I(BB,CC,DD)+Mj+tj) s) 接下来详细介绍主循环中的四作的具体内容。第一作(共包含16次操作)： FF(AA，BB，CC，DD，M0，7，d76aa478) FF(DD，AA，BB，CC，M1，12，e8c7b756) FF(CC，DD，AA，BB，M2，17，242070db) FF(BB，CC，DD，AA，M3，22，c1bdceee) FF(AA，BB，CC，DD，M4，7，f57c0faf) FF(DD，AA，BB，CC，M5，12，4787c62a) FF(CC，DD，AA，BB，M6，17，a8304613) FF(BB，CC，DD，AA，M7，22，fd469501) FF(AA，BB，CC，DD，M8，7，698098d8) FF(DD，AA，BB，CC，M9，12，8b44f7af) FF(CC，DD，AA，BB，M10，17，ffff5bb1) FF(BB，CC，DD，AA，M11，22，895cd7be) FF(AA，BB，CC，DD，M12，7，6b901122) FF(DD，AA，BB，CC，M13，12，fd987193) FF(CC，DD，AA，BB，M14，17，a679438e) FF(BB，CC，DD，AA，M15，22，49b40821) 第二作(共包含16次操作)： GG(AA，BB，CC，DD，M1，5，f61e2562) GG(DD，AA，BB，CC，M6，9，c040b340) GG(CC，DD，AA，BB，M11，14，265e5a51) GG(BB，CC，DD，AA，M0，20，e9b6c7aa) GG(AA，BB，CC，DD，M5，5，d62f105d) GG(DD，AA，BB，CC，M10，9 GG(CC，DD，AA，BB，M15，14，d8a1e681) GG(BB，CC，DD，AA，M4，20，e7d3fbc8) GG(AA，BB，CC，DD，M9，5，21e1cde6) GG(DD，AA，BB，CC，M14，9，c33707d6) GG(CC，DD，AA，BB，M3，14，f4d50d87) GG(BB，CC，DD，AA，M8，20，455a14ed) GG(AA，BB，CC，DD，M13，5，a9e3e905) GG(DD，AA，BB，CC，M2，9，fcefa3f8) GG(CC，DD，AA，BB，M7，14，676f02d9) GG(BB，CC，DD，AA，M12，20，8d2a4c8a) 第三作(共包含16次操作)： HH(AA，BB，CC，DD，M5，4，fffa3942) HH(DD，AA，BB，CC，M8，11，8771f681) HH(CC，DD，AA，BB，M11，16，6d9d6122) HH(BB，CC，DD，AA，M14，23，fde5380c) HH(AA，BB，CC，DD，M1，4，a4beea44) HH(DD，AA，BB，CC，M4，11，4bdecfa9) HH(CC，DD，AA，BB，M7，16，f6bb4b60) HH(BB，CC，DD，AA，M10，23，bebfbc70) HH(AA，BB，CC，DD，M13，4，289b7ec6) HH(DD，AA，BB，CC，M0，11，eaa127fa) HH(CC，DD，AA，BB，M3，16，d4ef3085) HH(BB，CC，DD，AA，M6，23，04881d05) HH(AA，BB，CC，DD，M9，4，d9d4d039) HH(DD，AA，BB，CC，M12，11，e6db99e5) HH(CC，DD，AA，BB，M15，16，1fa27cf8) HH(BB，CC，DD，AA，M2，23，c4ac5665) 第四作(共包含16次操作)： II(AA，BB，CC，DD，M0，6，f4292244) II(DD，AA，BB，CC，M7，10，432aff97) II(CC，DD，AA，BB，M14，15，ab9423a7) II(BB，CC，DD，AA，M5，21，fc93a039) II(AA，BB，CC，DD，M12，6，655b59c3) II(DD，AA，BB，CC，M3，10，8f0ccc92) II(CC，DD，AA，BB，M10，15，ffeff47d) II(BB，CC，DD，AA，M1，21，85845dd1) II(AA，BB，CC，DD，M8，6，6fa87e4f) II(DD，AA，BB，CC，M15，10，fe2ce6e0) II(CC，DD，AA，BB，M6，15，a3014314) II(BB，CC，DD，AA，M13，21，4e0811a1) II(AA，BB，CC，DD，M4，6，f7537e82) II(DD，AA，BB，CC，M11，10，bd3af235) II(CC，DD，AA，BB，M2，15，2ad7d2dd) II(BB，CC，DD，AA，M9，21，eb86d391)(3) A=A+AA，B=B+BB，C=C+CC，D=D+DD。 (4) 输出H(x)=A‖B‖C‖D，得到128位的消息摘要。通过与MD4的过程进行比较可知，MD5相对MD4进行了以下一些改进：(1) 增加了主循环中的操作次数，由三作改进为四作；(2) 操作的每一步均有惟一的加法常数；(3) 为了减弱函数G的对称性，函数定义由(X∧Y)∨(X∧Z)∨(Y∧Z)改进为(X∧Z)∨(Y∧(Z))； (4) 改变了第二轮和第三轮中访问消息子分组的次序，使得其形式更加不相似；(5) 近似优化了每一轮中循环移位的位移量，各轮的位移量各不相同。 MD5算法有以下性质：Hash函数的每一位均是输入消息序列中每一位的函数。该性质保证了在Hash函数计算过程中产生基于消息x的混合重复，从而使得生成的Hash函数结果混合得非常理想，也就是说，随机选取两个有着相似规律性的两组消息序列，也很难产生相同的Hash函数值。目前，MD5算法被广泛应用于各种领域。从密码分析的角度上看，MD5仍然被认为是一种易受到攻击的算法，而且，近年来对MD5攻击的相关研究已取得了很大的进展。2004年，我国学者王小云给出了一种解决MD5碰撞问题的算法。因此，有必要用一个具有更长消息摘要和更能抵御已知密码分析攻击的Hash函数来代替目前被广泛使用的MD5算法。下面介绍的安全Hash算法——SHA-1就是这样一个算法。 SHA-1算法的具体操作包括以下几步：(1) 填充过程。设输入的消息序列为x，x表示消息序列的长度。因为SHA-1算法要求输入消息的最大长度不超过264位，所以x≤264-1。填充过程对输入的消息序列进行填充使得消息长度与448模512同余(即x mod 512=448)，填充的位数范围是1~512，填充位串的最高位为1，其余各位均为0。(2) 在填充的结果序列后附加序列。将一个64位的序列附加到填充的结果序列后面，填充列的值等于初始序列位串的长度值。从而得到长度是512位的分组序列。 (3) 对给定的5个寄存器A、B、C、D、E赋初值： A B=efcdab89 C=98badcfe D E=c3d2e1f0其中，0，1，2，3，4，5，6，7，8，9，a，b，c，d，e，f表示一个十六进制的数字或一个长度为4的二进制序列。 (4) 将以上得到的寄存器的值赋给相应的变量AA、BB、CC、DD、EE。然后对512位的消息分组序列y应用主循环进行处理，每一次的主循环都有四作。每一轮进行20次操作，每次操作对AA、BB、CC、DD、EE中的三个作一次非线性的函数运算，然后进行与MD5算法类似的移位运算和加运算。SHA-1算法中的非线性函数定义为 同时定义相应的常数为设y=M0‖M1‖…‖M15，其中每一个消息分组Mi都是长度为32位的序列。用以下方法将消息分组从16个32位的序列变成80个32位的序列。 主循环如下：当0≤t≤79时，  TEMP=(AA5)+Ft(BB，CC，DD)+EE+Wt+Kt EE=DD DD=CC CC=BB 30 BB=AA AA=TEMP(5) A=A+AA，B=B+BB，C=C+CC，D=D+DD，E=E+EE。(6) 输出H(x)=A‖B‖C‖D，得到160位的消息摘要。 (2) 速度。由于两个算法的主要运算都是模232加法，因此都易于在32位结构上实现。但比较起来，SHA-1的迭代步数(80步)多于MD5的迭代步数(64步)，所用的缓冲区(160位)大于MD5使用的缓冲区(128位)，因此在相同硬件上实现时，SHA-1的速度要比MD5的速度慢。(3) 简洁与紧致性。两个算法描述起来都较为简单，实现起来也较为简单，均不需要较大的程序和代换表。 构造MAC的常用方法是把密钥作为Hash函数输入消息的一部分，使得产生的消息摘要不仅与消息序列有关，而且与附加的密钥有关，从而在一个不带密钥的Hash函数中介入一个密钥。但这样做往往是不安全的，下面通过实例给予说明。设H(x)是不带密钥的迭代结构的Hash函数，k是一个密钥，其长度为m位。现在来构造一个新的带密钥的Hash函数Hk(x)。为了描述简单，假定H(x)没有预处理过程和输出变换过程。输入的消息序列记为x，则x的长度应该是t的倍数， 建立Hash函数的压缩函数，记为compress: {0，1} m+t→{0，1} m。 现在给出在已知一组有效的消息x和相应的消息认证码Hk(x)，且无需知道密钥k的情况下， 来构造一个有效的消息认证码的过程。设x′是一个长度为t的位串，现在考虑消息序列x‖x′。产生消息摘要Hk(x‖x′)的过程如下： Hk(x‖x′)=compress(Hk(x)‖x′)因为Hk(x)和x′都是已知的，所以攻击者在无需知道密钥k的情况下，也能构造出有效的消息认证码(x‖x′，Hk(x‖x′))。应用上述方法构造的带密钥的Hash函数存在安全问题。 根据以上分析可知，构造消息认证码不能够简单地将密钥参数和消息x进行拼接，然后直接计算相应的Hash函数值来处理。根据消息x和密钥k计算消息认证码需要更复杂的处理过程，下面介绍两种广泛使用的消息认证码。 4.6.1 基于分组密码的MAC目前被广泛使用的MAC算法是基于分组密码的MAC算法。下面以DES分组密码为例，来说明构造MAC算法的过程。消息分组的长度取为64位，MAC算法的密钥取为DES算法的加密密钥。 给定消息序列x和56位的密钥k，构造相应的MAC的过程如下：(1) 填充和分组。对消息序列x进行填充，将消息序列x分成t个长度为64位的分组，记为 x=x1‖x2‖x3‖…‖xt (2) 分组密码的计算。应用DES分组加密算法的计算过程如下： (3) 可选择输出。使用第二个密钥k′，k′≠k，计算相应的H(x)的过程如下：通过以上过程最终得到消息x的MAC为H(x)。在以上计算MAC的过程中，第(3)步可选择输出过程相当于对最后一个消息分组进行了三重DES加密，该操作能够有效减少MAC受到穷举式搜索攻击的威胁。由于三重DES加密过程只是在可选择输出过程进行，没有在整个分组密码计算过程采用，因此不会影响中间过程的效率。 4.6.2 基于序列密码的MAC考虑到基于异或运算的流密码的位运算会直接导致作为基础明文的可预测变化，对流密码进行数据完整性保护显得更为重要。一般的Hash函数每次处理的是消息序列的一个分组，而为流密码设计的MAC算法每次处理的是消息的一个位。给定长度为m位的消息序列x，构造相应的MAC的过程如下： (1) 建立关联多项式。建立与消息序列x=xm-1xm-2…x1x0相关联的多项式Px(t)=x0+x1t+…+xm-1tm-1。 (2) 密钥的选择。随机选择一个n次的二进制不可约多项式q(t)，同时随机选择一个n位的密钥k。MAC的密钥由q(t)和k组成。(3) 计算过程。计算h(x)=coef(Px(t)·tn mod q(t))，这里coef表示取Px(t)·tn除以q(t)所得到的次数为n-1次的余式多项式的系数，计算结果对应n位的序列。(4) MAC。消息序列x的MAC定义为H(x)←h(x) k。通过以上过程后得到消息x的MAC为H(x)。 在上面的MAC计算过程中，对于不同的消息序列，不可约多项式q(t)可以重复使用，但对于不同的消息序列，相应的随机密钥k要随时更新，以保证算法的安全性。任何一个基于Hash函数的MAC算法的安全性都在某种方式下依赖于所使用的Hash函数的安全性。MAC的安全性一般表示为伪造成功的概率，该概率等价于对使用的Hash函数进行以下攻击中的一种：(1) 即使对攻击者来说z0是随机的、秘密的和未知的，攻击者仍能够计算出压缩函数的输出。(2) 即使z0是随机的、秘密的和未知的，攻击者仍能够找到Hash函数的碰撞。 在以上两种情况下，对应的MAC算法都是不安全的。 2. 设已知整数p，p′(p=2p′+1)，q，q′(q=2q′+1)都是大素数，n=pq而且分解n是困难的。设a∈Z*n，a的阶为2p′q′(Z*n中阶数最大的元素)。现在定义压缩函数如下： h(x)=ax mod n，x∈{1，2，…，n2} 设n=603241，a=11。如果已经给定了压缩函数h(x)的3个碰撞消息为 h(1294755)=h=h试利用这些消息分解603241。 3. 设函数h1: {0，1}2m→{0，1}m是一个碰撞稳固的Hash函数。(1) 定义函数h2: {0，1}4m→{0，1}m如下：a. 将x∈{0,1}4m分组表达为x=x1‖x2，其中x1，x2∈{0,1} 2m。b. 定义h2(x)=h1(h1(x1)‖h1(x2))。试证明：h2是碰撞稳固的。 (2) 对于整数i≥2，应用hi-1递归定义Hash函数如下：a． 将分组表达为x=x1‖x2，其中x1，。b． 定义hi(x)=h1(hi-1(x1)‖hi-1(x2))。试证明：hi是碰撞稳固的。4. 试比较SHA-1与MD4的主要区别。 4.4 SHA-1 SHA-1(Security Hash Algorithm，安全Hash算法)是一个产生160位消息摘要的迭代Hash函数。该算法由美国国家标准和技术协会(NIST)提出，并作为联邦信息处理标准在1993年公布。SHA-1算法输入消息的最大长度不超过264位，输入的消息按照512位的分组进行处理。 4.5 MD5与SHA-1的比较 由于SHA-1与MD5都由MD4演化而来，所以极为相似。下面给出MD5和SHA-1之间的比较分析。 (1) 抗穷举式搜索攻击的强度。由于MD5和SHA-1的消息摘要长度分别为128和160，因此用穷举式搜索攻击寻找具有给定消息摘要的消息分别需要做O(2128)和O(2160) 次运算，而穷举式搜索攻击找到具有相同消息摘要的两个不同消息分别需要做O(264)和O(280)次运算。所以SHA-1抗击穷举式搜索攻击的强度高于MD5抗击穷举式搜索攻击的强度。 *4.6 消息认证码(MAC) 含有密钥的Hash函数通常称为消息认证码(Message Authentication Codes，MAC)。MAC具有与前面讨论的单向Hash函数相同的特性，所不同的是MAC还包含有密钥。 将单向Hash函数变成MAC的一个简单办法是应用对称加密算法对消息摘要进行加密。但这种方法需要在发送消息和消息摘要的同时还要将加密算法使用的加密密钥通过安全的信道发送，这样做降低了算法的实用性。 习 题 1. 设函数f: {0，1}m→{0，1}n是一个原像稳固的双射，对于给定的x∈{0，1}2m，记做x=x′‖x″，其中x′，x″∈{0，1}m。现在定义函数h: {0，1} 2m→{0，1} m如下： h(x)=f(x′⊕x″) 试证明：h不是第二原像稳固的。 * 第4章 Hash函数 4.1 Hash函数与随机预言模型 4.2 迭代Hash函数 4.3 MD 4.4 SHA-1 4.5 MD5与SHA-1的比较 *4.6 消息认证码(MAC) 习题 4.1 Hash函数与随机预言模型 4.2 迭代Hash函数 本节讨论一种可以将有限定义域上的Hash函数延拓到具有无限定义域上的Hash函数的方法——迭代Hash函数。目前使用的Hash函数大多数都是迭代Hash函数，例如被广泛使用的MD5、安全Hash算法(SHA-1)等。 在本节中，假设Hash函数的输入和输出都是位串。把位串的长度记为x，把位串x和y的串联记为x‖y。下面给出一种构造无限定义域上Hash函数H的方式，该方式通过将一个已知的压缩函数compress: {0，1} m+t→{0，1} m(m≥1，t≥1)扩展为可以具有无限长度输入的Hash函数H来达到目的。通过这种方法构造的Hash函数称为迭代Hash函数。 4.3 MD MD(Message Digest，消息摘要)算法由Ron Rivest在1990年10月提出， 人们通常称之为MD4。 MD4对于输入的消息产生128位的消息摘要。由于它的安全性不是基于任何其他的密码体制和已知的单向函数，因此它的安全性只能由时间来证明。MD4算法首次公布后，Bert den Boer和Antoon Bosselaers对三轮算法中的后两轮成功地进行了密码分析。在一个不相关的分析结果中，Ralph Merkle成功地攻击了三轮算法中的前两轮。Eli Biham也讨论了对MD4的前两轮进行差分攻击的可能性。尽管这些攻击算法还没有扩展到整个MD4算法，但是为了增强算法的安全性，Ron Rivest于1992年4月给出了MD4的改进算法——MD5。为了介绍MD5，下面先介绍MD4。