Adler-32
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目需要補充更多來源。 (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).