Adler-32
此条目需要补充更多来源。 (2020年6月12日) |
Adler-32是一种校验算法,由马克·阿德勒在1995年发明[1],是对Fletcher校验的一种改进。与相同长度的循环冗余校验相比,它以可靠性换取速度(更倾向于后者)。Adler-32比Fletcher-16更加可靠,比Fletcher-32可靠性稍差。[2]
历史
Adler-32校验和是广泛使用的zlib压缩库的一部分,因为两者都是由马克·阿德勒开发的。在rsync工具中使用了Adler-32的“旋转哈希”版本。
算法
Adler-32校验和是通过计算两个16位的校验和A和B,并将它们的位连为一个32位整数来获得的。A是流中所有字节的总和加1,而B是每个步骤中A的各个值的总和。 在Adler-32运行开始时,A被初始化为1,B为0。以模65521(小于216的最大质数)进行求和。字节以网络顺序存储(字节序),B占据最高的两个字节。
该函数可以表示为
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的长度。
示例
ASCII字符串“ Wikipedia
”的Adler-32校验和计算如下:
字符 | ASCII码 | A | B | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
(显示为10进制) | |||||||||||
W | 87 | 88 | 88 | ||||||||
i | 105 | 193 | 281 | ||||||||
k | 107 | 300 | 581 | ||||||||
i | 105 | 405 | 986 | ||||||||
p | 112 | 517 | 1503 | ||||||||
e | 101 | 618 | 2121 | ||||||||
d | 100 | 718 | 2839 | ||||||||
i | 105 | 823 | 3662 | ||||||||
a | 97 | 920 | 4582 |
A = 920 = 0x398 (16进制) B = 4582 = 0x11E6 输出 = 0x11E6 << 16 + 0x398 = 0x11E60398
在这个例子中,取模运算没有效果,因为没有一个值达到65521。
与Fletcher校验和的比较
两种算法之间的第一个区别,是Adler-32和是以一个质数为模数计算的,而Fletcher和是以24-1、28-1或216-1为模(取决于所使用的位数)为模数计算的,它们都是复合数。使用质数使得Adler-32可以捕获到Fletcher无法检测到的某些字节组合中的差异。
第二个区别,也是对算法的速度影响最大的区别,是Adler和是在8位的字节上计算的,而不是16位的字上,导致循环迭代次数增加了一倍。 这使得对于16位字对齐数据,Adler-32校验和花的时间是Fletcher校验和的1.5到2倍。对于字节对齐的数据,Adler-32比正确实现的Fletcher的校验和(例如,HDF中的实现)要快。
实现示例
在C语言中,一个低效但直接的实现方式是:
const uint32_t MOD_ADLER = 65521;
uint32_t adler32(unsigned char *data, size_t len)
/*
where data is the location of the data in physical memory and
len is the length of the data in bytes
*/
{
uint32_t a = 1, b = 0;
size_t index;
// Process each byte of the data in order
for (index = 0; index < len; ++index)
{
a = (a + data[index]) % MOD_ADLER;
b = (b + a) % MOD_ADLER;
}
return (b << 16) | a;
}
请参阅zlib源代码,了解更有效的实现,它需要对每个字节进行一次取数和两次加法,模数运算延后,并每隔几千个字节计算两次余数,这种技术最早是在1988年被发现用于Fletcher校验。js-adler32
也提供了类似的优化,增加了一个技巧,即推迟计算65536-65521中的“15”,这样模数运算就会变得更快:可以证明((a >> 16) * 15 + (a & 65535)) % 65521
相当于简单的积累。[3]
优点和缺点
- 与标准CRC-32一样,Adler-32校验和很容易伪造,因此在防止故意修改方面是不安全的。
- 在许多平台上,它都比CRC-32更快。[4]
- Adler-32对于只有几百个字节的短消息方面有一个弱点,因为这类消息的校验和对32个可用位的覆盖率很低。
弱点
对于短消息来说,Adler-32是很弱的,因为总和A不会回绕(英语:Wrap,即整数溢出后的处理)。128字节消息的最大和是32640,低于取模操作所使用的值65521,这意味着大约有一半的输出空间未使用,并且使用部分内的分布也是不均匀的。延伸的解释可以在RFC 3309中找到,它规定流控制传输协议SCTP使用CRC32C而不是Adler-32。[5]对于较小的增量更改,Adler-32也被证明变化很弱[6],并且对于从一个共同的前缀和连续的数字生成的字符串也很弱(例如由典型代码生成器自动生成的标签名)。[7]
参见
脚注
- ^ First appearance of Adler-32 (see ChangeLog and adler32.c). [2020-06-12]. (原始内容存档于2020-09-17).
- ^ Revisiting Fletcher and Adler Checksums (PDF). [2020-06-12]. (原始内容存档 (PDF)于2020-09-17).
- ^ adler32.js. Sheet JS. 3 July 2019.
- ^ Theresa C. Maxino, Philip J. Koopman. The Effectiveness of Checksums for Embedded Control Networks (PDF). IEEE Transactions on Dependable and Secure Computing. January 2009 [2020-06-12]. (原始内容存档 (PDF)于2013-10-21).
- ^ RFC 3309
- ^ 存档副本. [2020-06-12]. (原始内容存档于2012-11-29).
- ^ 存档副本. [2020-06-12]. (原始内容存档于2020-06-12).