YuMo's Blog

数据摘要算法总结

概述

数据摘要算法具有不可逆性, 其主要功能有数据签名, 数据完整性校验等. 下面介绍常见的数据摘要算法:

CRC

CRC(Cyclic Redundancy Check,循环冗余校验)算法出现时间较长,应用也十分广泛,尤其是通讯领域,现在应用最多的就是 CRC32 算法,它产生一个4字节(32位)的校验值,一般是以8位十六进制数,如FA 12 CD 45等。CRC算法的优点在于简便、速度快,严格的来说,CRC更应该被称为数据校验算法,但其功能与数据摘要算法类似,因此也作为测试的可选算法。

MD5

Message-Digest Algorithm 5,消息摘要算法版本5。由Ron Rivest(RSA公司)在1992年提出,目前被广泛应用于数据完整性校验、数据(消息)摘要、数据加密等。MD2、MD4、MD5 都产生16字节(128位)的校验值,一般用32位十六进制数表示。MD2的算法较慢但相对安全,MD4速度很快,但安全性下降,MD5比MD4更安全、速度更快。

SHA

SHA(Secure Hash Algorithm)是由美国专门制定密码算法的标准机构——美国国家标准技术研究院(NIST)制定的,SHA系列算法的摘要长度分别为:SHA为20字节(160位)、SHA256为32字节(256位)、 SHA384为48字节(384位)、SHA512为64字节(512位),由于它产生的数据摘要的长度更长,因此更难以发生碰撞,因此也更为安全,它是未来数据摘要算法的发展方向。由于SHA系列算法的数据摘要长度较长,因此其运算速度与MD5相比,也相对较慢。
目前SHA1的应用较为广泛,主要应用于CA和数字证书中,另外在目前互联网中流行的BT软件中,也是使用SHA1来进行文件校验的。

Crc32

CRC32 Cyclical Redundancy Check 循环冗余检查, 是一种数据传输检错功能。常用在在数据存储和数据通讯领域, CRC32 Cyclical Redundancy Check 循环冗余检查, 是一种数据传输检错功能。常用在 在数据存储和数据通讯领域。

常见应用

  • 著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT
  • ARJ、LHA等压缩工具软件采用的是CRC32
  • 磁盘驱动器的读写采用了CRC16
  • 通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段

本质

是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式如表1所示。
CRC-32: x^32 + x^26 + x^23 + x^22 + x^16 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

Adler32

Adler-32是Mark Adler发明的校验和算法,和32位CRC校验算法一样,都是保护数据防止意外更改的算法,但是这个算法较容易被伪造,所以是不安全的保护措施。但是比CRC好点的是,它计算的很快。这个算法那是从Fletcher校验和算法中修改过来的,原始的算法形式略快,但是可依赖性并不高。

Adler-32的一种滚动哈希版本被用在了rsync工具 Adler-32通过求解两个16位的数值A、B实现,并将结果连结成一个32位整数。A就是字符串中每个字节的和,而B是A在相加时每一步的阶段值之和。在Adler-32开始运行时,A初始化为1,B初始化为0,最后的校验和要模上65521(继216之后的最小素数)。

1
2
3
4
A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
= n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)
Adler-32(D) = B × 65536 + A

其中D为字符串的字节,n是D的字节长度。

综合应用

对用户手机设备唯一码加密:
Python版:

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python
import zlib,base64
def diu2pid(diu, cpcode):
row = '%s.%s' % (base64.b64encode(diu), cpcode.upper())
a = zlib.crc32(row)
b = zlib.adler32(row, 0) & 0xffffffff
return a << 32 | b & 0x7fffffffffffffff
if __name__ == '__main__':
diu = '866100020117496'
cpcode = 'AN_Amap_ADR_FC'
print diu2pid(diu, cpcode)

Java版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public BigInteger toPid() {
String base64Uuid = new String(Base64.encodeBase64(uuid.getBytes()));
String key = String.format("%s.%s", base64Uuid, this.cpcode.toUpperCase());
CRC32 crcChecksum = new CRC32();
crcChecksum.update(key.getBytes());
BigInteger crcValue = new BigInteger(String.format("%d", crcChecksum.getValue()));
Adler32 adlerChecksum = createAdler32Checksum(0);
adlerChecksum.update(key.getBytes());
BigInteger adlerValue = new BigInteger(String.format("%d", adlerChecksum.getValue()));
BigInteger pid = crcValue.shiftLeft(32).or(adlerValue).and(new BigInteger("7FFFFFFFFFFFFFFF", 16));
return pid;
}