哈希（Hash）与加密（Encrypt）的数学基础

从数学角度讲，哈希和加密都是一个映射。下面正式定义两者：

      一个哈希算法是一个多对一映射，给定目标文本S，H可以将其唯一映射为R，并且对于所有S，R具有相同的长度。由于是多对一映射，所以H不存在逆映射

使得R转换为唯一的S。

      一个加密算法是一个一一映射，其中第二个参数叫做加密密钥，E可以将给定的明文S结合加密密钥Ke唯一映射为密文R，并且存在另一个一一映射，可以结合Kd将密文R唯一映射为对应明文S，其中Kd叫做解密密钥。

      下图是哈希和加密过程的图示：

      有了以上定义，就很清楚为什么会存在上文提到的两个区别了。由于哈希算法的定义域是一个无限集合，而值域是一个有限集合，将无限集合映射到有限集合，根据“鸽笼原理(Pigeonhole principle)”，每个哈希结果都存在无数个可能的目标文本，因此哈希不是一一映射，是不可逆的。

      而加密算法是一一映射，因此理论上来说是可逆的。

      但是，符合上面两个定义的映射仅仅可以被叫做哈希算法和加密算法，但未必是好的哈希和加密，好的哈希和加密往往需要一些附加条件，下面介绍这些内容。

      一个设计良好的哈希算法应该很难从哈希结果找到哈希目标文本的碰撞（Collision）。那么什么是碰撞呢？对于一个哈希算法H，如果，则S1和S2互为碰撞。关于为什么好的哈希需要难以寻找碰撞，在下面讲应用的时候会详解。另外，好的哈希算法应该对于输入的改变极其敏感，即使输入有很小的改动，如一亿个字符变了一个字符，那么结果应该截然不同。这就是为什么哈希可以用来检测软件的完整性。

      一个设计良好的加密算法应该是一个“单向陷门函数(Trapdoor one-way function)”，单向陷门函数的特点是一般情况下即使知道函数本身也很难将函数的值转换回函数的自变量，具体到加密也就是说很难从密文得到明文，虽然从理论上这是可行的，而“陷门”是一个特殊的元素，一旦知道了陷门，则这种逆转换则非常容易进行，具体到加密算法，陷门就是密钥。

      顺便提一句，在加密中，应该保密的仅仅是明文和密钥。也就是说我们通常假设攻击者对加密算法和密文了如指掌，因此加密的安全性应该仅仅依赖于密钥而不是依赖于假设攻击者不知道加密算法。

哈希（Hash）与加密（Encrypt）的数学基础

从数学角度讲，哈希和加密都是一个映射。下面正式定义两者：

      一个哈希算法是一个多对一映射，给定目标文本S，H可以将其唯一映射为R，并且对于所有S，R具有相同的长度。由于是多对一映射，所以H不存在逆映射

使得R转换为唯一的S。

      一个加密算法是一个一一映射，其中第二个参数叫做加密密钥，E可以将给定的明文S结合加密密钥Ke唯一映射为密文R，并且存在另一个一一映射，可以结合Kd将密文R唯一映射为对应明文S，其中Kd叫做解密密钥。

      下图是哈希和加密过程的图示：

      有了以上定义，就很清楚为什么会存在上文提到的两个区别了。由于哈希算法的定义域是一个无限集合，而值域是一个有限集合，将无限集合映射到有限集合，根据“鸽笼原理(Pigeonhole principle)”，每个哈希结果都存在无数个可能的目标文本，因此哈希不是一一映射，是不可逆的。

      而加密算法是一一映射，因此理论上来说是可逆的。

      但是，符合上面两个定义的映射仅仅可以被叫做哈希算法和加密算法，但未必是好的哈希和加密，好的哈希和加密往往需要一些附加条件，下面介绍这些内容。

      一个设计良好的哈希算法应该很难从哈希结果找到哈希目标文本的碰撞（Collision）。那么什么是碰撞呢？对于一个哈希算法H，如果，则S1和S2互为碰撞。关于为什么好的哈希需要难以寻找碰撞，在下面讲应用的时候会详解。另外，好的哈希算法应该对于输入的改变极其敏感，即使输入有很小的改动，如一亿个字符变了一个字符，那么结果应该截然不同。这就是为什么哈希可以用来检测软件的完整性。

      一个设计良好的加密算法应该是一个“单向陷门函数(Trapdoor one-way function)”，单向陷门函数的特点是一般情况下即使知道函数本身也很难将函数的值转换回函数的自变量，具体到加密也就是说很难从密文得到明文，虽然从理论上这是可行的，而“陷门”是一个特殊的元素，一旦知道了陷门，则这种逆转换则非常容易进行，具体到加密算法，陷门就是密钥。

      顺便提一句，在加密中，应该保密的仅仅是明文和密钥。也就是说我们通常假设攻击者对加密算法和密文了如指掌，因此加密的安全性应该仅仅依赖于密钥而不是依赖于假设攻击者不知道加密算法。