アドラー32

アドラー32は、マーク・アドラーが1995年に書いたチェックサム アルゴリズムで、^[1]フレッチャーのチェックサムを修正したものです。同じ長さの巡回冗長検査と比較すると、信頼性と速度がトレードオフになっています。アドラー32はフレッチャー16よりも信頼性が高く、フレッチャー32よりもわずかに信頼性が低いです。^[2]

Adler-32 チェックサムは、広く使用されているzlib圧縮ライブラリの一部です。どちらもMark Adlerによって開発されました。rsyncユーティリティでは、Adler-32 の「ローリング チェックサム」バージョンが使用されています。

Adler-32 チェックサムは、2 つの16 ビットチェックサムAとB を計算し、それらのビットを 32 ビットの整数に連結することによって得られます。Aはストリーム内のすべてのバイトの合計に 1 を加えた値であり、B は各ステップの Aの個々の値の合計です。

Adler-32 の実行開始時に、A は1 に初期化され、B は0 に初期化されます。合計は65521 ( 2 ¹⁶より小さい最大の素数)を法として行われます。バイトはネットワーク順 (ビッグ エンディアン)で格納され、B が最上位 2 バイトを占めます。

この関数は次のように表現される。

A = 1 + D 1 + D 2 + ... + D n (65521 を法として)

B = (1 + D 1 ) + (1 + D 1 + D 2 ) + ... + (1 + D 1 + D 2 + ... + D n ) (65521 を法として)
  = n × D 1 + ( n −1)× D 2 + ( n −2)× D 3 + ... + D n + n (65521 を法として)

アドラー32 ( D ) = B × 65536 + A

ここで、D はチェックサムを計算するバイト文字列であり、n はDの長さです。

ASCII文字列 " "の Adler-32 合計はWikipedia次のように計算されます。

A = 920 = 0x398 (基数16)
B = 4582 = 0x11E6
出力 = (0x11E6 << 16) + 0x398 = 0x11E60398 = 300286872

この例では、いずれの値も 65521 に達しなかったため、モジュロ演算は効果がありません。

2 つのアルゴリズムの最初の違いは、Adler-32 の合計が素数を法として計算されるのに対し、Fletcher の合計は 2 ⁴ −1、2 8 ⁻¹、または 2 ¹⁶ −1 (使用されるビット数によって異なります) を法として計算され、これらはすべて合成数であることです。素数を使用すると、Adler-32 は Fletcher が検出できない特定のバイトの組み合わせの違いを検出できます。

アルゴリズムの速度に最も大きな影響を与える 2 番目の違いは、Adler の合計が16 ビットワードではなく 8 ビットバイトで計算されるため、ループの反復回数が 2 倍になることです。このため、16 ビット ワードに揃えられたデータの場合、Adler-32 チェックサムは Fletcher のチェックサムの 1.5 ～ 2 倍の時間がかかります。バイトに揃えられたデータの場合、Adler-32 は適切に実装された Fletcher のチェックサム (たとえば、階層データ形式にあるもの) よりも高速です。

Cでは、非効率的ですが簡単な実装は次のようになります。

定数uint32_t MOD_ADLER = 65521 ;    

uint32_t adler32 ( unsigned char * data , size_t len ) /*    ここで、data は物理メモリ内のデータの位置、    len はバイト単位のデータの長さです*/ { uint32_t a = 1 , b = 0 ; size_t index ; // データの各バイトを順番に処理しますfor ( index = 0 ; index < len ; ++ index ) { a = ( a + data [ index ]) % MOD_ADLER ; b = ( b + a ) % MOD_ADLER ; } return ( b << 16 ) | a ; }      





          
     
    
    
           
    
              
              
    
    
         

1 バイトあたり 1 回のフェッチと 2 回の加算を必要とするより効率的な実装については、zlibソース コードを参照してください。js-adler32この実装では、モジュロ演算は延期され、数千バイトごとに 2 つの剰余が計算されます。この手法は、1988 年に Fletcher チェックサム用に初めて発見されました。 は、モジュロが高速になるように 65536 - 65521 の "15" の計算を遅らせるトリックを追加した同様の最適化を提供します。これは、((a >> 16) * 15 + (a & 65535)) % 65521単純な累積と同等であることが示されています。^[3]

• 標準のCRC-32と同様に、Adler-32 チェックサムは簡単に偽造できるため、意図的な変更から保護するには安全ではありません。
• 多くのプラットフォームではCRC-32よりも高速です。^[4]
• Adler-32 は、数百バイトの短いメッセージに対しては弱点があります。これは、これらのメッセージのチェックサムが、利用可能な 32 ビットを十分にカバーしていないためです。

Adler-32 は、合計Aが折り返されないため、短いメッセージには弱い。128 バイトのメッセージの最大合計は 32640 で、これはモジュロ演算で使用される値 65521 を下回っているため、出力スペースの約半分が未使用であり、使用済み部分内の分布は不均一である。詳細な説明はRFC 3309 で確認でき、 SCTP ( Stream Control Transmission Protocol)には Adler-32 ではなくCRC32C の使用が義務付けられている 。 ^[5] Adler-32 は、小さな増分変更にも弱いことが示されている。^[6]また、一般的なプレフィックスと連続する数字から生成された文字列 (一般的なコード ジェネレータによって自動生成されるラベル名など) にも弱い。^[7]

• ハッシュ関数のリスト

• RFC  1950 – 仕様、Cコード例を含む
• ZLib – adler32.c で Adler-32 チェックサムを実装します
• Chrome – Adler-32 のSIMD実装を使用します adler32_simd.c
• RFC  3309 – ショートメッセージの脆弱性とSCTPに関連する変更に関する情報