誤り検出コードの仕組みと実践的な使い分け — CRC・チェックサム・パリティから暗号ハッシュまで

2025年12月11日 最終更新日時 : 2025年12月11日 エバープレイ編集部

はじめに：誤り検出コードとは何か

誤り検出コード（error-detecting code）は、通信や記憶装置における偶発的なビット反転や破損を検出するために付加される付加情報（冗長ビット）です。検出だけを目的とするものもあれば、誤り訂正（error-correcting）を組み合わせるものもあります。設計上のトレードオフは検出能力（どの程度の誤りを検出できるか）、オーバーヘッド（追加のビット数）、計算コスト（速度や実装の容易さ）、および攻撃耐性（故意の改竄に対する強度）です。

基本的な種類と原理

代表的な誤り検出方式には次のようなものがあります。

  • パリティビット: データ全体のビット数の偶奇を示す単純な1ビットの冗長。1ビット誤りは確実に検出できるが、2ビットや偶数個のビット誤りは見逃す。
  • チェックサム（和）: データをワード単位に分けて加算した結果の下位ビットを付加する方式（例：IP/TCPのインターネット・チェックサムは1の補数和の下位16ビット）。実装が簡単で高速だが、ワードの入れ替えや特定の誤りパターンを見逃す可能性がある。
  • Fletcher / Adler: 単純な和より衝突を減らすために累積和を2つ用いる方式（Fletcher）や素数モジュロを用いる方式（Adler-32）。高速で実装が容易だが、衝突特性や初期値の影響がある。
  • 巡回冗長検査（CRC）: ポリノミアル除算に基づく非常に広く使われる方式。リンク層（イーサネット）、ストレージ、ファイル転送などで標準的。程度 r のCRCは長さ r 以下のバースト誤りを完全に検出し、より長いランダムな誤りは高確率で検出する。
  • 符号化理論由来の検出器（例：Reed–Solomon, BCH）: ストレージやCD、QRコードなどで使われる。誤り訂正能力を持ちつつ検出も行うため、誤りが多いチャネル向け。
  • 暗号学的ハッシュ / MAC: SHA-256やHMACなど。偶発的な誤りはほぼ確実に検出でき、さらに認証（改竄検知）も可能。計算コストは高いが、悪意ある改竄に対して強力。

CRCの詳細と性質

CRCはビット列を多項式とみなし（データ D(x) と生成多項式 G(x)）、G(x) で割った余りを付加する方式です。主な性質は次のとおりです。

  • 次数 r のCRCは長さ r 以下のバースト誤りを必ず検出します。つまり、連続したビットの誤りが r ビット以下なら検出率は100%です。
  • ランダムな誤りに対する検出確率は 1 - 2^{-r} に近く、r が大きいほど有利です。
  • 生成多項式が (x+1) を因子に持つ場合、奇数個のビット誤りを必ず検出します。多くの標準的な CRC 多項式はこの性質を満たすよう選ばれています。
  • 単一ビット誤りの検出は、生成多項式が単項式（x^k）の形でない限り保証されます。

よく使われる例としては CRC-32（イーサネットやZIPなど）や CRC-16-CCITT（通信規格）があります。実装は簡単なシフト演算ベースのアルゴリズムか、テーブルルックアップ（テーブル駆動法）、さらに高速化するためにスライシング技術（Slicing-by-8 など）が用いられます。

チェックサムとその限界

インターネットで古くから使われる IP/TCP のチェックサムは 16 ビットの 1 の補数和で、実装が高速である一方で下記のような弱点があります。

  • 16 ビット幅のため衝突（異なるデータが同じチェックサムになる）は相対的に高い。
  • 16 ビットワード単位での操作のため、ワードの入れ替えや等価な誤りパターンを見逃しやすい。

Adler-32（zlib）や Fletcher 系は単純チェックサムより衝突耐性が良好ですが、短いデータや特定パターンでは弱点があります。したがって、単純なチェックサムは軽量検出には有効だが、強い整合性保証を必要とする用途には不十分です。

誤り検出と誤り訂正の違い

誤り検出コードは「誤りがあるかどうかを知らせる」ことを目的とし、誤り訂正コード（ECC）は実際に誤りを訂正する力を持ちます。メモリ用のECC（例：Hamming コードに SECDED: single-error-correcting, double-error-detecting を加えたもの）は単一ビット誤りを訂正し、二重ビット誤りを検出します。ディスクや光メディアでは Reed–Solomon などが多く用いられます。選択はアプリケーションの要件（リアルタイム性、再送可否、コスト）に依存します。

実装上の注意点

実際のシステム設計においては次の点に注意してください。

  • データのエンディアンやビット順（MSB/LSB）をプロトコルで明確に定める。CRC 実装の差分は相互運用性を崩す典型例です。
  • 初期値（初期レジスタ）や最終XOR値などのパラメータも同じにする必要があります。標準規格（IEEE、ITU、IETF）の指定に従うこと。
  • ハードウェア実装ではパイプライン化や専用回路で非常に高速に計算できる。一方、ソフトウェアではテーブル法やSIMD最適化が実用的です。
  • チェック方式は単独で用いるだけでなく、暗号的な認証（HMAC など）と組み合わせれば改竄耐性が向上します。誤り検出と認証は目的が異なる点に留意する。

用途別の選び方ガイド

一般的な推奨：

  • リンク層（イーサネット・シリアル通信）：CRC（例：CRC-32, CRC-16）を標準で使用。
  • リアルタイム再送（低遅延が重要）：軽量チェックサムや短いCRCを検討。
  • ストレージ（RAID、ディスク）：誤り訂正を含む強力な符号（Reed–Solomon、BCH）を検討。
  • メモリ（DRAM）：ECC（Hamming, SECDED）を使用して自動訂正を行う。
  • ファイル整合性やセキュリティ重視：暗号学的ハッシュ（SHA-256）や MAC（HMAC）を用いる。

テストと評価方法

誤り検出機構を導入する際は次の評価を行ってください。

  • 標本誤り注入テスト（ランダム誤りとバースト誤りの混合）で検出率を計測。
  • 境界条件テスト（極端に短い/長いデータ、全ビット 0／1、特定パターン）を確認。
  • 相互運用テスト（異実装間で同じパラメータを用いたときの一致）を行う。

攻撃や改竄に対する考慮

誤り検出コードは故障や確率的誤りに対しては有効ですが、悪意ある攻撃者が存在する場合は脆弱です。攻撃者は計算可能な冗長ビットを改竄に合わせて再計算できるため、単純なCRCやチェックサムだけでは整合性保証や認証には不十分です。改竄耐性が必要な場合はデジタル署名や HMAC、その他暗号的メカニズムを併用してください。

まとめ：最適化の観点

誤り検出コードは目的に応じて最適なものが変わります。軽量で高速な検出が要るならパリティや簡易チェックサム、通信リンクやファイル転送では CRC、強い訂正や長いバースト耐性が要るなら Reed–Solomon や BCH、セキュリティを含めるなら暗号ハッシュや MAC を選ぶのが基本です。実装にあたってはパラメータの一致、初期値、エンディアンなどの運用上の仕様を厳密に合わせることが相互運用性と信頼性を確保する鍵です。

参考文献

CRC — Wikipedia
RFC 1071: Computing the Internet Checksum
zlib (Adler-32)
Fletcher's checksum — Wikipedia
Hamming code — Wikipedia
Reed–Solomon error correction — Wikipedia
FIPS PUB 180-4 (SHA Family)
Koopman: CRC Polynomial Selection (実装と解析リソース)

カテゴリー
IT
前の記事
T-1000徹底解説：液体金属の脅威と制作秘話、文化的影響を深掘り
2025年12月11日
次の記事
ターミネーターシリーズ徹底解説：歴史・テーマ・製作・評価まで総まとめ
2025年12月11日