Adler-32

Adler-32 は、マーク・アドラー(Mark Adler)が考案したチェックサムアルゴリズム。同じ長さの巡回冗長検査と比較すると、信頼性と引き換えに高速性を追求している。その元となった Fletcher-16 に比較すると信頼性が高いが、Fletcher-32 に比較すると若干信頼性が劣る^[1]。

歴史

Adler-32 はフレッチャーのチェックサムを修正したものである。

同じくマーク・アドラーが開発したzlib圧縮ライブラリの一部として使われている。Adler-32 に基づくローリングチェックサムが rsync で使われている。

アルゴリズム

Adler-32 チェックサムは、まず2つの16ビットのチェックサム A と B を計算し、それらを連結して32ビットの整数にする。Aは全てのバイトの総和に1を加えた値、B は A を計算している各ステップの値を累積した総和である。

初期状態では、A は 1 に初期化され、B は 0 に初期化される。これらの総和は modulo 65521 で保持される（65521 は 2¹⁶ 未満の最大の素数）。これらのバイトはネットワークオーダー（ビッグエンディアン）で格納され、B が最上位バイト側に位置する。

式で表すと、以下のようになる。

 A = 1 + D₁ + D₂ + ... + D_n (mod 65521)
 B = (1 + D₁) + (1 + D₁ + D₂) + ... + (1 + D₁ + D₂ + ... + D_n) (mod 65521)
   = n×D₁ + (n-1)×D₂ + (n-2)×D₃ + ... + D_n + n (mod 65521)

 Adler-32(D) = B × 65536 + A

ここで D はチェックサム計算対象のバイト列の各バイトを意味し、n はバイト数を意味する。

例

ASCII文字列 "Wikipedia" のAdler-32チェックサムは以下のように計算される。

   ASCIIコード         A                   B
   （基数10で示す）
   W: 87           1 +  87 =  88        0 +  88 =   88
   i: 105         88 + 105 = 193       88 + 193 =  281
   k: 107        193 + 107 = 300      281 + 300 =  581
   i: 105        300 + 105 = 405      581 + 405 =  986
   p: 112        405 + 112 = 517      986 + 517 = 1503
   e: 101        517 + 101 = 618     1503 + 618 = 2121
   d: 100        618 + 100 = 718     2121 + 718 = 2839
   i: 105        718 + 105 = 823     2839 + 823 = 3662
   a: 97         823 +  97 = 920     3662 + 920 = 4582

   A = 920  =  398 hex (base 16)
   B = 4582 = 11E6 hex

   Output = 300286872 = 11E60398 hex

この例では、総和が65521を超えることがないため、modulo演算は特に意味がない。

フレッチャーのチェックサムとの比較

1つめの違いは、Adler-32では素数の modulo を使って計算している点で、フレッチャーの場合は使うビット数に応じて modulo 2⁴-1, 2⁸-1, 2¹⁶-1 を採用している（これらは合成数である）。素数を使うことで、フレッチャーのチェックサムでは捉えられないバイト列の違いを捉えられることがある。

2つめの違いはアルゴリズムの高速性に関連するもので、Adler-32 では16ビットワード単位ではなく8ビットバイト単位で計算するため、ループ回数が2倍になる。このため16ビット境界に整列されたデータでは、フレッチャーのチェックサムの1.5倍から2倍の時間がかかる。ただし、16ビット境界に整列されていないデータでは、Adler-32 は普通に実装されたフレッチャーのチェックサムよりも高速である。

実装例

最適化されていない、C言語でのシンプルな実装は RFC 1950 の末尾に記載されていて、以下の通り。

/* data: 対象データへのポインタ; len: バイト数 */
uint32_t adler32(uint8_t *data, size_t len) {
    uint32_t a = 1, b = 0;

    for (size_t n = 0; n < len; n++) {
        a = (a + data[n]) % 65521;
        b = (b + a)       % 65521;
    }

    return (b << 16) + a;
}

これの、最適化実装例を以下に示す。

#define MOD_ADLER 65521

uint32_t adler32(uint8_t *data, size_t len) { 
    uint32_t a = 1, b = 0;
 
    while (len > 0) {
        size_t tlen = len > 5552 ? 5552 : len;
        len -= tlen;
        do {
            a += *data++;
            b += a;
        } while (--tlen);

        a %= MOD_ADLER;
        b %= MOD_ADLER;
    }

    return (b << 16) | a;
}

効率化のためにいくつかトリックが用いられている。

最も重要な点は、総和の一時格納変数として32ビット整数が使われている点で、これによって modulo 65521 を行う回数を減らしている。modulo 65521 は総和がオーバーフローする前に行う必要がある。
マジックナンバー 5552 は b がオーバフローしない最大の反復（加算）回数である。

ローリングチェックサム

ローリングチェックサム化は以下のようにして行える。

/* adler: 前の Adler-32、len: データ長（23ビット以下でないとオーバーフロー）、delValue: 消える値、addValue: 追加する値 */
uint32_t rollingAdler32(uint32_t adler, uint32_t len, uint8_t delValue, uint8_t addValue) {
    uint32_t a = adler & 0xFFFF;
    uint32_t b = (adler >> 16) & 0xFFFF;
    b = (b + addValue - delValue * (len + 1) + a - 1 + 65521) % 65521;
    a = (a + addValue - delValue                     + 65521) % 65521;
    return (b << 16) | a;
}

長所と短所

CRC-32と同様、Adler-32チェックサムも容易に偽造できるため、改ざんに対するプロテクトとして用いるのは安全ではない。
CRC に比較してソフトウェアで実装したとき高速である。
数百バイト程度の短いメッセージでは、チェックサムの32ビット全体を使うことがないため、Adler-32 は脆弱とされている。2001年に Jonathan Stone が指摘した。128バイトのメッセージでは A の最大値は 32640 であり、65521 を超えない。このため RFC 3309 ではSCTPでAdler-32の代わりにCRC-32を使うことを指示している。

脚注

^ Revisiting Fletcher and Adler Checksums

外部リンク

RFC 1950 - C言語コード例がある。
ZLib - Adler-32 を実装している。
Adler-32 - Adler-32チェックサムをオンラインで計算
RFC 3309 - 短いメッセージの脆弱性に関する情報と関連するSCTPへの変更

[1] Revisiting Fletcher and Adler Checksums

[1]