技術記事
チェックサムの計算方法
さまざまな種類のチェックサムは、データ通信プロトコルで広く用いられており、メッセージの受信者がデータが伝送中に破損した可能性があるかどうかを素早く簡単に判断できるようにします。たとえば、メッセージのすべてのバイトを加算した合計(オーバーフローを無視して)が96になった場合、その値をメッセージに付加して送信します。受信者はメッセージの最初のN-1バイトについて同じ加算を行い、その結果を最後のバイトと比較して96であるかを確認できます。一致すれば、受信者はメッセージがおそらく(議論の余地はありますが)伝送中に改変されていないと推測できます。
一般的に使用されているチェックサム技術は多岐にわたります。最も普及しているものを3つ挙げると、従来型チェックサム、LRC(縦方向冗長検査)、CRC(巡回冗長検査)です。最後のCRCは厳密には通常の意味でのチェックサムではなく、一方向 ハッシュ の一例であり、「線形合同法ジェネレータ」ファミリーに属します。
先ほど、これらのデータ整合性検査技術は、データが「破損した可能性があるかどうか」を判定できると述べました。任意の長さのデータに対して、一般的なケースで100%確実なチェックサム技術は存在しません。ただし、技術によって明らかに優れているものもあります。
それでは、JavaScriptでLRC、チェックサム、CRCをどのように計算するかを見ていきましょう。
従来型の8ビットチェックサムはまさにその名の通り、入力中のすべてのバイト値を合計し、(キャリー演算による)オーバーフローはすべて切り捨てたものです。JavaScriptでは次のようになります:
この関数への入力は、「48656C6C6F20776F726C6421」のような16進文字列が想定されています(この場合、ASCII文字列「Hello world!」の16進表現です)。「48656C6C6F20776F726C6421」を上記の関数への入力として使用すると、出力は「5d」となり、これが最終的な8ビット合計の16進値です。
コードは非常にシンプルです。まず(3行目で)、正規表現 /../g を使って16進入力を2ニブル(=2文字)ずつのまとまりに分解します。これは「任意の文字に続く任意の文字」のパターン(ドット2つ)に一致する部分文字列をグローバルに(’g’の意味)検索することを意味します。結果は2桁の16進値の配列 sとなります。
5行目で、 forEach 反復構文を使ったループに入り、2ニブルの16進値の文字列表現を、演算可能な実際の数値に変換します。7行目で実際の加算を行います。なお、変数 sum は内部的には本質的に32ビット整数なので、最終値は255よりはるかに大きくなる可能性があります。ループ終了後、合計値を必ず8ビット値に制約する必要があります。これを9行目で、255との論理ANDで行っています。同時に、 toString() メソッドに引数16(数値の最終表現で基数16、つまり「16進」を使うことを意味します)を渡して、16進に変換しなおしています。
10行目と11行目では、最終的な16進値が2ニブル長であることを確認する必要があります。JavaScriptのtoString(16)操作は、10未満の値に対しては1桁の値を返します。その場合、結果に ‘0’ を先頭に付ける必要があります。
コードを試したい場合は、上記のコードをJSコンソール(Chromeでは Shift-Cmd-J でコンソールを表示)にコピー&ペーストし、関数の外側の一番下に CHECKSUM(“48656C6C6F20776F726C6421”) という行を追加してください。Enterキーを押すと、コンソールに戻り値として ‘5d’ が表示されるはずです。
LRCを使ったチェックサムの計算方法
縦方向冗長検査(LRC)は、8ビットチェックサムのバリエーションであり、「合計」を数値加算ではなくXORを使用して行う点だけが異なります。
6行目に、XOR代入演算子(^=)が確認できます。
XORはオーバーフローを起こさないため、最終結果をANDで8ビットに制約する必要はありません。単に2ニブル長を確認したうえで、最終値を返すだけです。
先ほど示した文字列を使ってコンソールでコードを試すと、答えは ’21’ になるはずです。
チェックサムとLRCについての考察
チェックサムもLRCも、メッセージの破損に対して堅牢とは言えません。たとえば、元のメッセージ(「48656C6C6F20776F726C6421」)を考えてみましょう。仮にメッセージの最後の2バイトを 6421 から 6520 に変更したとします。LRCもチェックサムも変わらないままです!(上流のバイトで1ビットをONにし、下流の同じ位置のビットをOFFにすることで、チェックサム計算時に互いに打ち消し合う2つの変更を行ったのです。)
同様に、メッセージを反転させた場合(つまり、バイト単位でメッセージを逆順にして、21で始まり48で終わるようにする)を考えてみましょう。この場合も、LRCとチェックサムは元のメッセージと同じままです。これは、XORと加算が交換則を満たすためです。A + B は常に B + A と等しいのです。
また、8ビットのLRCやチェックサムは256通りの値しか取り得ないため、任意のメッセージが、ランダムに選ばれた別のメッセージとまったく同じLRC(またはチェックサム)を生成する確率は256分の1であることも考慮すべきです。
一般に、チェックサムおよびLRCアルゴリズムを「だます」のは非常に簡単であり、メッセージの整合性検査としてはあまり信頼性が高くありません。
幸いなことに、整合性検査にはLRCやチェックサムよりも優れたアルゴリズムが存在しますが、それらは計算オーバーヘッドという代償を伴います。
CRCを使ったチェックサムの計算方法
整合性検査が本当に重要な場合、一般的には何らかの非可換ハッシュを使用する必要があります。これは、SHA-1やMD5のような暗号学的ハッシュを意味することが多いのですが、これらは計算負荷が高く、多くの状況では「過剰」とみなされることがあります。
計算オーバーヘッドと信頼性の良好なトレードオフは巡回冗長検査(CRC)に見出すことができます。CRCにはさまざまなバージョンがありますが、後述する16ビットCRCは、短いメッセージ(おおむね4キロバイトまで)には十分(かつ非常に普及している)ものです。
CRCは興味深いテーマですが、紙幅の都合上、ここで包括的に扱うことはできません。(詳細はGoogleでご確認ください。)実用的な観点から言えば、2バイトのCRCはデータ中のランダムなビット反転に対して非常に高い感度を持ち、複数のビット反転を含むデータに対しても誤検出を起こしにくいものです。このため、また、ハードウェアやソフトウェアでの実装が容易で、わずかなメモリで非常に高速に動作することから、ストレージディスクのドライバ(ディスクエラーの検出にCRCがよく使われます)、モデム、小型電子機器(ID TECH社のViVOpayシリーズのクレジットカードリーダーすべてを含む)など、さまざまなデータ通信環境で使用されています。
以下のJavaScriptコードは、16ビットCRC値(16進ASCIIの4ニブルとして返される)の計算方法を示しています。
CRCは、英語で次のように説明できるハッシュアルゴリズムを実装しています:
- 開始値を設定する crc の値を 0xFFFF に設定 — 10行目
- 入力データから1バイト（8ビットの数値として）を取得する — 13行目
- 既存の crc 値を右に8ビットシフトする — 14行目
- 右シフトした crc と入力バイトを XOR する — 14行目
- 結果の値 j（下位8ビットのみ）をテーブルオフセットとして使用し、次のテーブルから「置換バイト」を参照する： crcTable — 15行目
- 次の crc 値を左に8ビットシフトし、「置換バイト」と XOR する — 15行目
- 次の入力バイトを使って、13行目から上記の操作を繰り返す
- すべての入力をこのように処理した後、結果をゼロと XOR し、crc の下位16ビットを保持する — 17行目
最終的な数値を整数から16進数文字列に変換するため、簡単なユーティリティルーチンを使用します：
これら両方の関数（numToHex と CRC）をブラウザの JS コンソールにロードし、次を実行すると： CRC( "48656C6C6F20776F726C6421" )「Hello world!」という入力データに対する CRC として「BD22」が得られるはずです。
練習として、入力のビットを1つ反転させて、出力がどう変わるかを試してみるとよいでしょう。例えば、「Hello world!」の文字列を入力として使い、データの最後のバイトを 21 から 20 に変更すると、CRC は「AD03」に変わり、「BD22」とは何の関連性もありません。最後の2バイトを「6520」に変更すると、CRC は「9E32」になります。（同じ変更でも LRC やチェックサムには影響しなかったことを思い出してください。）
10個のゼロ（null）バイトを表す文字列を考えてみましょう。このような文字列の LRC 値はゼロになります。チェックサムも明らかにゼロです。しかし CRC は E139 になります。
入力を逆順にすると、元の順序の入力を使った場合とはまったく異なる CRC が得られることは、容易に納得できるでしょう。（LRC やチェックサムでは、これは当てはまりませんでした。）CRC が可換でないのは、すべてを左にシフトする前に、CRC の上位8ビットを入力バイトと XOR する仕組みのためです（これは次の仕組みに似ています： cipher block chaining（暗号ブロック連鎖） の仕組み。ただしこの場合、「暗号ブロック」のサイズは8ビットです）。
CRC は一方向ハッシュではあるものの、厳密には暗号学的ハッシュではないことに注意してください。なぜなら、データに付加することで、特定のデータ改変が望ましい最終 CRC を生むような「補正値」を計算するのは、実はかなり容易だからです。（いわゆる暗号学的ハッシュではこれは当てはまらず、改変されたデータブロックを目的のハッシュへと逆補正する「補正係数」を計算するのは困難です。）したがって CRC は、意図しないデータ破損を検出するのに適しています。
データパケットの破損を監視するために使える「整合性チェック」アルゴリズムは数多くあります。場合によっては、単純なチェックサムや LRC で十分です。しかし、かなりの量のデータを扱い、データ整合性に対する厳しい要件がある状況では、ほぼ必然的に次のような種類のハッシュに目を向けることになります： 「線形合同法ジェネレーター」 タイプのハッシュです。CRC ファミリーのアルゴリズムは、優れた整合性判別能力に加えて、実装の容易さ、高速な実行、低メモリ要件を兼ね備えるよう十分にチューニング・最適化されており、ハードドライブからクレジットカードリーダーに至るまで、多種多様なデータチェックシナリオで CRC を魅力的な選択肢にしています。