CRC（巡回冗長検査）とは？

python セキュリティ

CRC（Cyclic Redundancy Check）は、データの誤り検出に用いられるアルゴリズムです。主に通信やストレージデータの整合性を確認する目的で広く使用されています。CRCは、送信データに対して計算される固定長の符号（CRCコード）を用いて、受信側でデータの破損を検出します。

CRCの基本的な仕組み

CRCは次のステップで動作します：

  1. 多項式の定義
    CRCでは、特定の生成多項式（generator polynomial）が使用されます。例えば、CRC-8では多項式 x8+x2+x+1x^8 + x^2 + x + 1 がよく使われます。

  2. データをビット列として扱う
    入力データは、1と0のビット列に変換されます。これを「メッセージ」と呼びます。

  3. 生成多項式で割り算
    メッセージに仮想的な余分なビット（生成多項式の次数分）を追加し、生成多項式でビット単位の割り算を行います。

  4. 余りを計算
    割り算の余りがCRCコードです。この余りが送信データに付加されます。

  5. 受信側で検証
    受信側では、データとCRCコードを使って再度割り算を行い、余りが0であればデータが正しいと判断します。

CRCの利点

  1. 計算が軽量
    ハードウェアやソフトウェアで容易に実装可能です。

  2. 誤り検出能力が高い
    単一ビットエラーや連続するエラーの多くを検出できます。

  3. 汎用性
    ネットワーク通信（イーサネット、CANバスなど）やストレージデバイス（ハードディスク、SSD）で幅広く利用されています。

CRCの種類

CRCにはさまざまなバリエーションがあります。主な例は以下の通りです：

  • CRC-8
    軽量データ通信に適しており、8ビットのCRCコードを生成します。

  • CRC-16
    USBやModbusなどで使用される一般的な形式です。

  • CRC-32
    EthernetやZIPファイルの整合性チェックに使われる形式です。

  • CRC-64
    高い精度を求められる用途で使用されます。

CRCの実際の用途

  1. ネットワーク通信
    データパケットが正しく送信されたかを確認するため、イーサネットやWi-Fiで使用されています。

  2. ストレージのデータ整合性
    ハードディスクやSSDでは、データの破損を検出するために使用されています。

  3. 組み込みシステム
    CANバスやLINバスなどの車載ネットワークプロトコルでエラー検出に使用されています。

CRCの限界

  • エラー訂正はできない
    CRCは誤り検出が目的であり、データの修復や訂正は行いません。

  • 特定のエラーに弱い
    例えば、生成多項式の倍数であるエラーは検出できない可能性があります。

実装例（Python）

以下は、CRC-8をPythonで実装する例です。

python
def crc8(data: bytes, poly: int = 0x07) -> int:
  crc = 0
 　for byte in data:
 　　crc ^= byte
　　for _ in range(8):
　　　if crc & 0x80:
　　　　crc = (crc << 1) ^ poly
　　　else:
　　　　crc <<= 1 crc &= 0xFF # 8ビットに制限
　　return crc
# 使用例 data = b"Hello, CRC!"
crc_code = crc8(data)
print(f"CRC-8コード: {crc_code:#04x}")

まとめ

CRCは、軽量で効率的な誤り検出アルゴリズムとして、さまざまな分野で利用されています。正確な生成多項式の選択や用途に応じた設定が必要ですが、その柔軟性と効果的なエラー検出能力により、広範囲で使用されています。