MD5算法(消息摘要)

客户端在向服务端发送请求时,服务端会要求添加数字签名,其中就涉及到MD5算法,OC中实现MD5很简单,短短几行一搜就有,但MD5究竟是什么,为什么能用于数字签名呢?

概括

MD5 Message-Digest Algorithm,一种被广泛使用的消息摘要算法,可以产生出一个128位元(16位元组)的散列值(hash value),用于确保信息传输完整一致。

特点

  • 压缩性:任意长度的数据,算出的MD5值长度都是固定的。
  • 容易计算:从原数据计算出MD5值很容易。
  • 抗修改性:对原数据进行任何改动,哪怕只修改1个字节,所得到的MD5值都有很大区别。
  • 强抗碰撞:想找到两个不同的数据,使它们具有相同的MD5值,是非常困难的。

用途

  • 文件校验:如,客户端向服务端发送的数据,附加上原数据MD5的值,服务端就可验证是否是未篡改数据。
  • 密码加密:如,客户端存储用户密码,只存储用户密码的MD5值在数据库,用户再次登录只需将密码MD5值和数据库内的做比较即可。
  • 数字签名:如,客户端向服务器发送数据,并将原始数据按约定的算法进行运算,并将结果的MD5值一同发送给服务端,服务端在接受到数据后,只需要对原始数据做一样的操作,对比两个MD5值是否相同就能确保数据未篡改。
  • 鉴权协议:有个称为挑战-认证模式的鉴权协议:需要鉴权的一方,向将被鉴权的一方发送随机串(挑战),被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后,返还鉴权方,鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较(认证),如相同,则可在统计上认为对方拥有该口令字,即通过鉴权。

安全性

普遍认为MD5是很安全,因为暴力破解的时间是一般人无法接受的。实际上如果把用户的密码MD5处理后再存储到数据库,其实是很不安全的。因为用户的密码是比较短的,而且很多用户的密码都使用生日,手机号码,身份证号码,电话号码等等。或者使用常用的一些吉利的数字,或者某个英文单词。如果我把常用的密码先MD5处理,把数据存储起来,然后再跟你的MD5结果匹配,这时我就有可能得到明文。比如某个MD5破解网站,所以现在大多数网站密码的策略是强制要求用户使用数字大小写字母的组合的方式提高用户密码的安全度。

唯一性?

首先MD5是数据摘要,得到的是128位数据,大致一想,显然比原数据少了很多很多,必然会出现多个原数据对应一个MD5的情况。只不过概率很低,而且如果还想把特定数据加入原数据就更难了。
网上的专业回答:

md5是用来做消息摘要的,不是加密算法,当然它可以作为普通的密码验证字串作为保存来屏蔽密码泄露。任何散列算法都是会碰撞的,毕竟将任意数据散列为一个固定长度的整数不出现重复是不可能的,但是为了验证数据有效性的消息摘要算法,需要保证散列的雪崩性——即是越是相近的数据散列出来的结果差异越大,由此特性来明确数据的差异能做到覆盖任何情况,毕竟两个差异过于明显的数据是不需要用散列来认证的。
举个例子来说,一般现在网上实现了很多网盘的功能的急速秒传就是通过散列来认证服务器是否存在相同文件,而且算法很多是sha1(和md5相同功能但是更加高级精确的散列算法),但是就芸芸众多文件而已,不发生碰撞是不可能的,但是为什么还是可以用这个算法来认真,就是因为算法本身的雪崩性,两个发生碰撞的数据,其差异很有可能异常巨大,如果发生碰撞,只要稍微判断一下其它项即可解决,例如数据长度,数据首N个数据段或者尾N数据段进行匹配即可。

攻击MD5手段

  • 预计算的哈希链集(Precomputed hash chains
  • 彩虹表(rainbow table

防止MD5攻击手段

在密码保护上,客户端一般只能做下对密码明文的加密,将加密的密码传给服务端或者存在本地数据库。
而在服务端的防护看链接知乎链接

MD5的计算逻辑

大致逻辑

MD5将输入的信息以512位分组来处理,且每一分组又被划分为16个32位子分组,​经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位分组级联后将生成一个128位散列值。

具体步骤

第一步:填充

如果输入信息的长度(bit)对512求余的结果不等于448,就需要填充使得对512求余的结果等于448
​填充的方法是填充11n0。填充完后,信息的长度就为N*512+448(bit);

​第二步:记录信息长度

64位来存储填充前信息长度。这64位加在第一步结果的后面,这样信息长度就变为N*512+448+64=(N+1)*512位。

第三步:装入标准的幻数(四个整数参数)

标准的幻数(物理顺序)是(A=(01234567)16B=(89ABCDEF)16C=(FEDCBA98)16D=(76543210)16)。如果在程序中定义应该是(A=0x67452301B=0xEFCDAB89C=0x98BADCFED=0x10325476)。

第四步:四轮循环运算

循环的次数是分组的个数(N+1
(1)将每一512字节细分成16个小组,每个小组64位(8个字节)
(2)先认识四个线性函数(&是与,|是或,~是非,^是异或)

1
2
3
4
F(X,Y,Z)=(X&Y)|((~X)&Z)  
G(X,Y,Z)=(X&Z)|(Y&(~Z))
H(X,Y,Z)=X^Y^Z
I(X,Y,Z)=Y^(X|(~Z))

(3)设Mj表示消息的第j个子分组(从0到15),<<<s表示循环左移s位,则四种操作为:

1
2
3
4
FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<<<s)  
GG(a,b,c,d,Mj,s,ti)表示a=b+((a+G(b,c,d)+Mj+ti)<<<s)
HH(a,b,c,d,Mj,s,ti)表示a=b+((a+H(b,c,d)+Mj+ti)<<<s)
II(a,b,c,d,Mj,s,ti)表示a=b+((a+I(b,c,d)+Mj+ti)<<<s)

(4)四轮运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
第一轮  
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)

第二轮
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三轮
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)

第四轮
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)

(5)每轮循环后,将ABCD分别加上abcd,然后进入下一循环
所有这些完成之后,将abcd分别在原来基础上再加上ABCD
a = a + Ab = b + Bc = c + Cd = d + D
然后用下一分组数据继续运行以上算法。

第五步:输出

最后的输出是abcd的级联。

OC实现MD5

1
2
3
4
5
6
7
8
9
10
11
12
13
-(NSString *) md5
{
const char *cStr = [self UTF8String];
unsigned char digest[CC_MD5_DIGEST_LENGTH];
CC_MD5( cStr, strlen(cStr), digest );

NSMutableString *output = [NSMutableString stringWithCapacity:CC_MD5_DIGEST_LENGTH * 2];

for(int i = 0; i < CC_MD5_DIGEST_LENGTH; i++)
[output appendFormat:@"%02x", digest[i]];

return output;
}