单向散列函数

单向散列函数

• 什么是单向散列函数
  假设Alice在将今日完成的项目进度进行保存后离开，当第二天到工作岗位重新打开时，怎么确定保存的项目和离开时是一样的。离开的时间内是否有攻击者对项目嵌入病毒或使用她的电脑更改项目代码。确认离开时和新打开的文件是否一致的性质称为完整性。如果去一一查看代码，过程是漫长且痛苦的。
  为解决这个问题，可以采取单项散列函数。将保存的文件通过单项散列函数生成散列值，再将第二天的文件生成散列值进行对比两者一致即代表文件未被修改，反之则被修改。
  
  单向散列函数有一个输入和输出，其中输入称为消息，输出称为散列值。单向散列函数可以根据消息的内容计算出散列值就可以被用来检查消息的完整性。
  其中消息不局限于文字，无论任何形式的消息，单向散列函数都会将它作为单纯的比特序列来处理，即根据比特序列计算出散列值。同时，无论输入的信息大小，单向散列函数都会计算出固定长度的散列值。以SHA-256单向散列函数为例，计算出的散列值长度永远是256比特(32字节)
• 单向散列函数的性质
  1. 根据任意长度的消息计算出固定长度的散列值
  保证输入的任意长度，且输出是短且固定的。这样能保证使用方便
  2. 能够快速计算出散列值
  如果因为输入过长而导致计算时间过长，会影响使用体验。
  3. 消息不同散列值也不同
  如果单向散列函数计算出的散列值没有发生变化，那么消息很容易会被篡改，这个单向散列函数也就无法被用于完整性的检查。两个不同的消息产生同一个散列值的情况称为碰撞。难以发现碰撞的性质称为抗碰撞性，密码技术中所使用的单项散列函数都需要具备抗碰撞性。这里提到的抗碰撞性指的是难以找到另外一条具备特定散列值的消息。
  当给定某条消息的散列值时，单向散列函数必须确保要找到和该条消息具备相同散列值的另外一条消息是非常困难的。这一性质称为弱抗碰撞性。相对的，要找到散列值相同的两条不同的消息是非常困难的称为强抗碰撞性。单向散列函数都必须同时具备弱抗碰撞性和强抗碰撞性。
  4.具备单向性
  单项散列函数必须具备单向性是指无法通过散列值反算出消息的性质。单项散列函数不等同于加密，因此无法解密
  5. 个别术语
  单项散列函数也称为消息摘要函数、哈希函数、杂凑函数
  输入单项散列函数的消息也称为原像
  单项散列函数输出的散列值也称为消息摘要或指纹，完整性也称为一致性
• 单项散列函数的实际应用

1. 检测软件是否被篡改
2. 基于口令的加密
3. 消息认证码
4. 数字签名
5. 为随机数生成器
6. 一次性口令

• 具体的单项散列函数

1. MD4、MD5
   MD4、MD5均是由Rivest设计的单项散列函数，能够产生128比特的散列值。
2. SHA-1、SHA-256、SHA-384、SHA-512
   SHA-1是由美国设计的一种能够产生160比特的散列值的单项散列函数；SHA-256、SHA-384、SHA-512统称为SHA-2，SHA-256的散列值长度上限接近于2⁶⁴，SHA-384、SHA-512上限接近于2¹²⁸。
3. RIPEMD-160
   RIPEMD-160能够产生160比特的散列值的单向散列函数。
4. SHA-3
   由于SHA-1在2005年被中国团队破解，在经过选拔后名叫Keccak的算法胜出。

• Keccak
  Keccak采用了与SHA-1、SHA-2完全不同的海绵结构
  
  Keccak的海绵结构中，输入的数据在进行填充之后，要进过吸收阶段和挤出阶段，最终生成输出的散列值。
  吸收阶段流程：

  1. 将经过填充的输入消息按照每r个比特为一组分割成若干个输入分组
  2. 首先，将”内部状态的r个比特”与”输入分组1″进行XOR，将其结果作为”函数f的输入值”
  3. 然后，将”函数f的输出值r个比特”与”输入分组2″进行XOR，将其结果再次作为”函数f的输入值”
  4. 反复执行上述操作，直到最后一个输入分组
  5. 带所有输入分组处理完成后，结束吸收阶段，进入挤出阶段

  其中函数f的作用是将输入的数据进行复杂的搅拌操作并输出结果（输入和输出的长度均为b=r+c哥比特），其操作对象是长度为b=r+c哥比特的内部状态，内部状态的初始值为0。每次被吸收的输入分组长度为r个比特，因此r被称为比特率。其中函数f的输入长度不是r个比特，而是r+c个比特，即内部状态中有c个比特是不受输入分组内容的直接影响的(但会通过函数f受到间接影响)。c则被称为容量。

  挤出阶段流程：

  1. 首先，将”函数f的输出值中的r个比特”保存为”输出分组1″，并将整个输出值(r+c个比特)再次输入到函数f中
  2. 然后，将”函数f的输出值中的r个比特”保存为”输出分组2″，并将整个输出值(r+c个比特)再次输入到函数f中
  3. 反复执行上述步骤，直到获得所需长度的输出数据

  在挤出阶段中，内部状态r+c个比特中的容量（c个比特）部分是不会直接进入输出分组的，这部分数据只会通过函数f间接影响输出的内容。因此，容量c的意义在于防止将输入消息中的一些特征泄漏（作用相当于加盐）。

• 双工结构
  即海绵结构的输入和输出是以相同的速率进行的。双工结构被用在伪随机数生成器、流密码、认证加密、消息认证码等。

• Keccak的内部状态、函数Keccak-f[b]
  该部分建议前往Keccak官方网站查看，该部分作者并未能理解，也希望有读者能将分享相关学习资料。

• 对单项散列函数的攻击

1. 暴力破解
   在不更改文档意思的前提下能够对文件的内容进行修改，且这个修改程度称为冗余性。利用文件的冗余性生成具有相同散列值的另一个文件，这就是一种针对单项散列函数的攻击。当寻找的是一条具备特定散列值的消息，就相当于是一种试图破解单项散列函数的”弱抗碰撞性”的攻击。
   找出具有制定散列值的消息的攻击分为”原相攻击”和”第二原相攻击两种”。前者是指给定一个散列值，找出具有该散列值的任意消息。后者则是指给定一条消息1，找出另外一条消息2，消息2的散列值和消息1相同。
2. 生日攻击
   生日攻击不是寻找生成特定散列值的消息，而是找到散列值相同的两条消息，而散列值为任意值。这等同于试图破解单项散列函数的”强抗碰撞性”的攻击。生日悖论：当23个人组成一个集合时，就能保证至少有两个人生日一样的概率大于二分之一

• 单项散列函数不无法解决的问题
  单项散列函数只能辨别出信息是否被篡改而无法辨别出伪装。

原文地址：http://www.cnblogs.com/addc/p/16851892.html