有关hash的胡言乱语

连续两天看了Hash相关的内容。包括hashcode,md5,sha-1,crc32,hmac,hmac-sha,以及java的hashmap实现过程。并尝试自己实现MD5,最终发现如果不参考已有的代码,还是很困难。

MD5: 无论原文多长,或者文件多大,生成的摘要信息永远都是128-bit。通过对实现过程的观察和研究,简单描述md5的实现过程:

  • 将原文或源文件转换为bit数组,先进行补位.补位的目的是为了让整个bit数组的长度对512取莫,余448.(The message is “padded” (extended) so that its length (in bits) is congruent to 448, modulo 512. ),具体补位的规则则是按1 0 …0的方式来补。这是第一步补位。
  • 依然补位,讲原数据的bit数组的长度补位到bit数组中。当然数组的长度本身就是个变量,具体padding的规则:
    A 64-bit representation of b (the length of the message before the
       padding bits were added) is appended to the result of the previous
       step. In the unlikely event that b is greater than 2^64, then only
       the low-order 64 bits of b are used. (These bits are appended as two
       32-bit words and appended low-order word first in accordance with the
       previous conventions.)
  • 总的来说就是把整个bit array 分成若干部分(原文大小决定),然后把每一个部分进行固定的位运算,得出几个(4个,这个4个初始值最初是给出的固定值),用这几个值再和下一部分原文进行运算,直到整个array计算完毕。
  • 通过上一步最终得出的几个值(就是最初给的几个,反复运算后,这几个的值相当于来自源数据),将这几个值合并并转换为16进制即为结果。

过程如上描述,其中位运算部分相对比较复杂,这可能和自己对位运算不了解,或者了解比较少有关,了解之后发现这真是个神奇的玩意,不过实际开发中,如果使用位运算来实现某些功能,估计其他同事看到这种代码会抓狂。这是一篇入门文章:http://www.codechef.com/wiki/tutorial-bitwise-operations。简单说位运算速度应该是非常快,比+-*/这些快了很多,但看起来却很难理解。使用位运算比较适合在基础代码库或者框架代码库以及嵌入式的地方使用,因为对效率的要求最高。

说到MD5了,就不得不说MD5是否安全这个问题了,比如之前做过的两个账号系统,密码都是基于MD5做的存储,而cookie的校验位则一个的一部分使用的md5,一个是hmac-sha1,cookie的校验位相对还算安全. 如果库哪天不幸被人拖了,带来的后果可就是灾难性的。…. 2004年随着中国的科学家 王小云的论文 http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf 发表,即代表着MD5的崩溃,只是这么几年下来基于这套破解论文的破解程序还比较少,所以大家某种程度还在心安理得的用着。据说据说按照这个杂凑碰撞破解的方式,最多只需要2的63方的次数就可以碰撞出一个结果,一台普通的pc1、2个小时就可以完成一次逆运算。 之后,这位中国女侠又破解了SHA hash算法,这可是美国国家认证的安全hash算法..

好吧,说到这里了,那以后该用什么hash算法做签名才安全呢?或许hmac-sha 这种复合型的hash算法好些,再或者对原数据进行两次不同算法的hash,并在第一次的结果中加入一些特征数据后,进行第二次hash。验证的过程,需要对中间值进行校验。这样可以防范通过碰撞产生的hash值。

 

md5: http://www.ietf.org/rfc/rfc1321.txt 

crack md5:http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf