21.DH密钥交换2022-02-2822.Paillier半同态加密：原理、高效实现方法和应用2021-10-27

收起

hash函数#

hash函数，简单点说，就是输入一个数，输出一个数，输出具有唯一性，输入和输出具有一一映射关系，该函数叫做哈希函数或杂凑函数，输出值叫做哈希值或杂凑值，常见的杂凑算法有：Md5、Sha256、SM3等。

SHA -> Secure Hash Algorithm

Hash通过Hash函数，将Key值映射为地址，Address = F[key];

无论输入是什么数字格式、文件有多大，输出都是固定长度的比特串。以比特币使用的Sh256算法为例，无论输入是什么数据文件，输出就是256bit。

每个bit就是一位0或者1，256bit就是256个0或者1二进制数字串，用16进制数字表示的话，就是多少位呢？

16等于2的4次方，所以每一位16进制数字可以代表4位bit。那么，256位bit用16进制数字表示，当然是256除以4等于64位。

于是你通常看到的哈希值，就是这样的了：
00740f40257a13bf03b40f54a9fe398c79a664bb21cfa2870ab07888b21eeba8

在学数据结构时，常见的hash函数有：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法.

碰撞(Collision Resistance)（冲突）问题#

不管选用何种散列函数，不可避免的都会产生不同Key值对应同一个Hash地址的情况，这种情况叫做哈希冲突。

当冲突发生时，我们需要想办法解决冲突，一般常用的方法有：开放定址法、单独链表法、双散列法、再散列法以及建公共溢出取等方法。

再详细的说说Hash与Hash碰撞

Hash，简单来讲，是一种将任意长度的输入变换成固定长度的输出，固定长度的输出在“实际应用场景”下可以代表该输入。Hash函数通常被翻译成散列函数。Hash通常用来校验信息的一致性。

　　Hash函数的实现多种多样，在安全领域应用最为广泛的是SHA-x系列和MDx系列。Hash函数也划分为带密钥的Hash函数和不带密钥的Hash函数，通常所说的Hash函数是不带密钥的Hash函数

　　由于Hash固定长度输出的特性，必然会存在多个不同输入产生相同输出的情况。如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞(Collision)。在理论范围内，存在一个输出串对应无穷多个输入串，所以碰撞具有其必然性。

　　如果找到碰撞，那么意味着我们可以破坏信息的一致性而不被接收方察觉，搜寻指定输入的Hash碰撞值的过程被称作“Hash破解”。这里需要说明的是，Hash函数必须是不可逆的，所以不存在从散列值到原始输入的破解（这里不包括暴力破解，使用彩虹表是暴力破解的最佳方式，但是仍然无法保证破解到的数据是原始数据）。设计不良的Hash算法，很容易让人找到碰撞值