图解密码技术 - 单向散列函数

单向散列函数的性质

单向散列函数(one-way hash function)有一个输入和一个输出，输入称为消息(message)，输出称为散列值(hash value)。

单向散列函数主要的功能是防止文件被篡改，它用于验证文件的完整性。

单向散列函数主要有以下性质：

• 能够根据任意长度的消息计算出固定长度的散列值
• 能够快速计算出散列值
• 消息不同散列值也不同
• 具备单向性：无法通过散列值反推出消息。

单向散列函数的应用

单向散列函数的主要应用有：

• 检测文件是否被篡改
• 基于口令的加密：MD5(key + salt)
• 消息认证码：将"加密的密钥"和"消息"一起计算散列值后发送，防止通信过程中的错误、篡改以及伪装。
• 数字签名
• 伪随机数生成器
• 一次性口令

单向散列函数算法

生日攻击

生日问题是指，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。

$$P(N) = 1 - \frac{365364363*{\cdots}*(365-N+1)}{365^N}$$

当P(N)>0.5时，N大于23。

生日悖论指的就是任意生日相同的概率比我们想象的要大这么一个现象。

生日攻击就是利用了生日悖论这一现象。

• (1) Eve生成N个100万元的合同
• (2) Eve生成N个1亿元的合同
• (3) Eve将(1)中的N个散列值和(2)中的N个散列值进行对比，寻找其中是否有一致的情况
• (4) 如果有相同，则用这一组合同进行欺骗

假设使用的单向散列函数的散列值长度为M比特，则M比特所能产生的全部散列值的个数为$$2^M$$个，也就相当于一年中的天数Y。

那么当$$N=2^{M/2}$$时，就有50%的可能出现相同散列值的情况。

假设单向散列函数的散列值长度为128位，则需要进行尝试的次数即为$$2^{64}$$次。比起暴力破解，少了很多！