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

　　第8章 Hash 函数 Hash函数定义 数据安全 机密性 完整性 认证性 密码技术主要保证数据的机密性 Hash函数能保证数据的完整性和认证性 Hash函数定义 Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与消息一起传输给接收者。 即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。??? Hash函数定义 Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。 Hash函数是一个函数，它以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。 Hash函数（hash function），或称为哈希函数、散列函数。对于任何消息x ，将h(x)称为x的Hash值、散列值、消息摘要（message digest）。 Hash函数作用 Hash函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。鉴别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。 8.1Hash 函数的性质 Hash函数的碰撞（collision） 设x、x’是两个不同的消息，如果 h(x)=h(x’) 则称x和x’是Hash函数h的一个（对）碰撞. 8. 1 Hash 函数的性质 Hash函数的分类 单向Hash函数（one?way） 给定一个Hash值y，如果寻找一个消息x，使得y=h (x)是计算上不可行的，则称h是单向Hash函数. 弱抗碰撞Hash函数（weakly collision?free） 任给一个消息x，如果寻找另一个不同的消息x’，使得h(x) =h(x’)是计算上不可行的，则称h是弱抗碰撞Hash函数. 强抗碰撞Hash函数 （strongly collision?free） 如果寻找两个不同的消息x和x’，使得h(x)=h(x’)是计算上不可行的，则称h是强抗碰撞Hash函数. 8. 1 Hash 函数的性质 hash函数在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证 压缩性：任意长度的数据，算出的摘要长度都固定。 容易计算：从原数据容易算出摘要。 抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的摘要都有很大区别。 弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），在计算上是困难的。 强抗碰撞：想找到两个不同的数据，使它们具有相同的摘要，在计算上是困难的。 Hash函数的安全性 对Hash函数的攻击是指寻找一对碰撞消息的过程 与传统密码体制的攻击方式相比，对散列函数的攻击方法主要有两种： 穷举攻击：它可以用于任何类型的散列函数的攻击，最典型的方式就是所谓的“生日攻击”。采用生日攻击的攻击者将产生许多明文消息，然后计算这些明文消息的指纹（摘要），进行比较。 利用散列函数的代数结构：攻击其函数的弱性质。通常的有中间相遇攻击、修正分组攻击和差分分析攻击等。 生日悖论（birthday paradox） 生日问题：假设每个人的生日是等概率的，每年有365天，在k个人中至少有两个人的生日相同的概率大于1/2，问k最小应是多少？ k人生日都不同的概率是： 有P(365,23)=0.5073。即在23个人中，至少有两个人生日相同的概率大于0.5，这个数字比人们直观猜测的结果小得多，因而称为生日悖论。 Hash函数的安全性 生日攻击法 生日悖论原理可以用于构造对Hash函数的攻击 设Hash函数值有n个比特，m是真消息，M是伪造的假消息，分别把消息m和M表示成r和R个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。 Hash函数的安全性 生日攻击法 分别把消息m和M表示成r和R个变形的消息 Hash函数的安全性 生日攻击法 计算真消息m的变形与假消息M的变形发生碰撞的概率 由于n比特长的散列值共有2n个，所以对于给定m的变形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由于M共有R个变形，所以M的全部变形都不与mi碰撞的概率是： 因为消息m共有r个变形，因此m的变形与M的变形都不碰撞的概率是： Hash函数的安全性 生日攻击法 8. 2 基于分组密码的Hash 函数 8.3 hash函数MD4 MD4是麻省理工学院教授Ronald Rivest于1990年设计的一种信息摘要算法。它是一种用来测试信息完整性的密码散列函数的实行。其摘要长度为128位。这个算法影响了后来的算法如MD5、SHA 家族和RIPEMD等。 MD5算法是1991年发布的一项数字签名加密算法，它当时解决了MD4算法的安全性缺陷，成为应用非常广泛的一种算法。 8.3 hash函数MD4 MD4算法的输入可以是任意长度的消息x，对输入消息按512位的分组为单位进行处理，输出128位的散列值MD(x)。整个算法分为五个步骤。 步骤1: 增加填充位 步骤2: 附加消息长度值 步骤3: 初始化MD缓冲区 步骤4: 以512位的分组(16个字)为单位处理消息 步骤5: 输出 消息的预处理步骤： 步骤1: 增加填充位 在消息x右边增加若干比特，使其长度与448模512同余。也就是说，填充后的消息长度比512的某个倍数少64位。 即使消息本身已经满足上述长度要求，仍然需要进行填充。 例如，若消息长为448，则仍需要填充512位使其长度为960位。填充位数在1到512之间。填充比特的第一位是1，其它均为0。 步骤2: 附加消息长度值 用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。若填充前消息长度大于等于264，则使用其64位。填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充。 步骤1与步骤2一起称为消息的预处理 经预处理后，原消息长度变为512的倍数 设原消息x经预处理后变为消息 Y=Y0 Y1… YN?1， 其中Yi（i =0,1,…,N?1）是32比特 在后面的步骤中，将对512比特的分组Yi进行处理 例8.1 假设消息为: x=“abcde”0 (61 62 63 64 65)16, x=40=(28)16. 步骤1在x的右边填充1个“1”和407个“0”，将x变成448比特的x1: x1= x 1 0 (407个) = x 800000 0 0 00000000. 658000000 00000000 0 00000000. 例8.1 假设消息为: x=“abcde”0 (61 62 63 64 65)16, x=40=(28)16. 经步骤2处理后的比特串为（16进制表示）： x2=x128(64位) 00 000000000. 步骤3: 初始化MD缓冲区 MD4算法的中间结果和最终结果都保存在128位的缓冲区里，缓冲区用4个32位的寄存器表示。 4个缓冲区记为A、B、C、D，其初始值为下列32位整数（16进制表示）： A=67 45 23 01, B=EF CD AB 89, C=98 BA DC FE, D=10 32 54 76. 上述初始值以小端格式存储(字的最低有效字节存储在低地址位置 )为： 字A=01 23 45 67, 字B=89 AB CD EF, 字C=FE DC BA 98, 字D=76 54 32 10. 步骤4: 以512位的分组(16个字)为单位处理消息 MD4是迭代Hash函数, 其压缩函数为: 步骤5: 输出 依次对消息的L个512比特的分组进行处理，第L个分组处理后的输出值即是消息x的散列值MD(x)。 8. 3 Hash函数MD4 8.4安全Hash算法SHA 安全Hash算法SHA（secure hash algorithm）由美国标准与技术研究所（NIST）设计并于1993年作为联邦信息处理标准（FIPS 180）发布 修改版于1995年发布（FIPS 180?1），通常称之为SHA?1。该标准称为安全Hash函数。 RFC 3174也给出了SHA?1，它基本上是复制FIPS 180?1的内容，但增加了C代码实现。 SHA?1算法的输入是长度小于264的任意消息x，输出160位的散列值。 8.4安全Hash算法SHA SHA?1处理消息的过程与MD4类似，对输入消息按512位的分组为单位进行处理，整个算法分为五个步骤 步骤1: 增加填充位 在消息右边增加若干比特，使其长度与448模512同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在1到512之间。填充比特的第一位是“1”，其它均为“0”。 8.4安全Hash算法SHA 步骤2: 附加消息长度值 用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。 步骤1与步骤2一起称为消息的预处理 经预处理后，原消息长度变为512的倍数。设原消息x经预处理后变为消息M=M0 M1… MN?1，其中Mi（i =0,1,…,N?1）是32比特。在后面的步骤中，将对512比特的分组进行处理。 8.4安全Hash算法SHA 步骤3: 初始化缓冲区 SHA?1算法的中间结果和最终结果保存在160位的缓冲区里，缓冲区用5个32位的寄存器表示。5个缓冲区记为A、B、C、D、E，其初始值为下列32位整数（16进制表示）： A=67 45 23 01, B=EF CD AB 89, C=98 BA DC FE , D=10 32 54 76, E=C3 D2 E1 F0. 其中，前4个初始值与MD5的初始值相同。SHA?1以大端格式存储缓冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述初始值存储为（十六进制）： 字A=67 45 23 01, 字B=EF CD AB 89, 字C=98 BA DC FE, 字D=10 32 54 76, 字E=C3 D2 E1 F0. 8.4安全Hash算法SHA 步骤4: 以512位的分组（16个字）为单位处理消息 SHA?1是迭代Hash函数，其压缩函数为： SHA?1的压缩函数HSHA 由四轮处理组成 加法是模232相加 SHA?1的压缩函数HSHA 压缩函数HSHA的四轮处理过程的算法结构相同，每一轮要对缓冲区ABCDE进行20次迭代，每次迭代的运算形式为 SHA?1的压缩函数HSHA 基本逻辑函数f 每一轮使用一个基本逻辑函数f，每个基本逻辑函数的输入是三个32位的字，输出是一个32位的字，它执行位逻辑运算，即输出的第n位是其三个输入第n位的函数。 SHA?1的压缩函数HSHA 字组Xt t（0≤t≤79）代表迭代步数，依次表示第一、二、三、四轮处理过程进行的迭代次序 Xt(0≤t≤79)是32比特的字，它的前面16个字X0,X1,…,X15依次取自当前输入分组Mi，其余字为 8.4安全Hash算法SHA 步骤5: 输出 第N/16个分组处理后的输出值即是消息x的散列值MD(x) 8. 4 安全Hash算法SHA SHA?1和MD5的比较 SHA?1与MD5的算法类似，所以它们的性质极为相似 抗穷举攻击的能力 SHA?1抗穷举攻击的能力比MD5强 用穷举攻击方法产生具有给定散列值的消息 MD5需要的代价为2128数量级 SHA?1需要的代价为2160数量级 用穷举攻击方法产生两个具有相同散列值的消息 MD5需要的代价为264数量级 SHA?1需要的代价为280数量级 抗密码分析的能力 MD5算法抗密码分析的能力较弱 SHA?1算法抗密码分析的能力似乎并不弱 SHA?1和MD5的比较 速度 SHA?1执行的速度比MD5的速度慢得多 简洁性 SHA?1和MD5两种算法都易于描述和实现，不需要使用大的程序和置换表 数据的存储方式 MD5使用little?endian方式，SHA?1使用big?endian方式。这两种方式没有本质的差异 步骤4是SHA?1算法的主循环，它以512比特作为分组，重复应用压缩函数HSHA，从消息的第一个分组开始，依次对每个分组进行压缩，直至最后分组，然后输出消息x的Hash值。 SHA?1循环次数等于消息中512比特分组的数目L。 CVi (160) Yi (512) B C D A E f4, K, W[60,61,…,79], 20步 B C D A E f2, K, W[20,21,…,39], 20步 B C D A E f3, K, W[40,41,…,59], 20步 B C D A E f1, K, W[0,1,…,19], 20步 + + + + + CVi+1 (160) TEMP=(A5)+ft(B,C,D)+E+X[k]+Kt E=D D=C C=B30 B=A A=TEMP f1(B, C, D) f2(B, C, D) f3(B, C, D) f4(B, C, D) 1 2 3 4 f(B, C, D) 基本逻辑函数f 轮数 加法常数表Kt 5A827999 6ED9EBA1 8F1BBCDC CA62C1D6 0?t?19 20?t?39 40?t?59 60?t?79 十进制 十六进制 迭代步数 SHA-1 算法如下 ①设A、B、C、D 、E是5个32 位的寄存器, 其初值(用十六进制表示) 分别为 AB =efcdab89、C =98badcfe、DE =c3d2e1f0 ②对i = 0 至N/16 - 1 执行第3 步至第10 步 ③对j = 0 至15 执行X[j] = M[16i + j ] ⑤将寄存器A、B、C、D、E 中的值存储到另外四个寄存器AA、BB、CC、DD 中, AA = A， BB = B， CC = C，DD = D，EE=E ⑥ 执行Round1 ⑦ 执行Round2 ⑧ 执行Round3 ⑩A = A + AA，B = B + BB，C = C + CC， D = D + DD，E=E+EE 点此查看Round1 点此查看Round2 点此查看Round3 ④ 对j = 16 至79 执行 X[j] = (X[j - 3] ⊕ X[j - 8] ⊕ X[j -14] ⊕ X[j -16]) ≤ 1 ⑨ 执行Round4 点此查看Round3 点击此处返回 点击此处返回 * m的变形与M的变形发生碰撞的概率是： 当r=R=2n/2时，P(n)=1?e?1?0.63。对于Hash值长度为64比特的Hash函数，生日攻击的时间复杂度约为232，所以是不安全的。 为了抵抗生日攻击，建议Hash值长度至少为128 比特. 基于分组密码的CBC 工作模式的Hash 函数H 首先选取一个初始向量 令 然后计算 基于分组密码的CFB 工作模式的Hash 函数H 令 然后计算 首先选取一个初始向量 设x 是一个消息, 用二进制表示。首先由x 生成一个数组 是长度为32 比特(bit)的(0,1) 序列, M 由x 生成： ①d = (447 -x)mod 512 ②令l 为 的二进制表示。 l 的长度为64 比特(bit)。 如果l 的长度不足64 比特(bit), 则在l 的左端添0 补足 ③M = 这里x表示x 的长度, 表示序列的联接, 譬如xy 表示将序列y 排在序列x 的右端。 步骤4是MD4算法的主循环，它以512比特作为分组，重复应用压缩函数HMD4，从消息Y的第一个分组Y0开始，依次对每16个分组Yi进行压缩，直至最后分组N/16-1，然后输出消息x的Hash值。可见，MD4的循环次数等于消息Y中512比特分组的数目L。 MD4 算法如下 ①设A、B、C、D 是四个32 位的寄存器, 其初值(用十六进制表示) 分别为 AB =efcdab89、C =98badcfe、D ②对i = 0 至N/16 - 1 执行第3 步至第8 步 ③对j = 0 至15 执行X[j] = M[16i + j ] ④将寄存器A、B、C、D 中的值存储到另外四个寄存器AA、BB、CC、DD 中, AA = A， BB = B， CC = C，DD = D ⑤ 执行Round1 ⑥ 执行Round2 ⑦ 执行Round3 ⑧A = A + AA，B = B + BB，C = C + CC， D = D + DD 点此查看Round1 点此查看Round2 点此查看Round3 *