巡回冗長検査

巡回冗長検査（CRC）とは

巡回冗長検査（Cyclic Redundancy Check、CRC）は、データ伝送や記憶媒体におけるデータの破損や誤りを検出するための誤り検出符号の一種です。送信側でデータに付加された検査値を、受信側で再度計算し比較することで、データの正確性を検証します。特に、デジタル回路での実装が容易で、数学的な分析も行いやすいことから、広く利用されています。

CRCの基本原理

CRCは、巡回符号の理論に基づいています。その計算は、多項式の除算に似ており、送信するデータを特定の数（生成多項式）で割り、その余りを検査データとして利用します。通常の算術計算とは異なり、有限体（GF(2)）の演算を使用します。この演算では、繰り上がりや繰り下がりが発生しません。余りの長さは常に除数（生成多項式）の長さ以下であり、これにより検査データの長さを制御できます。

CRCの多様なバリエーション

CRCには、出力結果のビット幅や生成多項式の違いにより、多くのバリエーションが存在します。CRC-nは、nビットの検査値を出力するCRCを表し、具体的な生成多項式によってさらに細かく分類されます（例：CRC-32 IEEE 802.3）。

CRCが広く使われる理由

CRCが広く利用される主な理由として、その効率性と誤り検出能力の高さが挙げられます。nビットCRCは、通常nビット以下の連続した誤り（バースト誤り）を検出でき、それ以上の長さのバースト誤りも高い確率で検出可能です。データ伝送や記憶装置では、誤りがランダムではなく連続して発生しやすい傾向があり、この特性がCRCの適用を促しています。単純なパリティチェックに比べて高い検出精度を持つため、広く利用されています。

CRCとセキュリティ

CRCは誤り検出には有効ですが、セキュリティ対策としては不十分です。CRC値はメッセージよりも情報量が少ないため、同じCRC値を持つ異なるメッセージを生成することが可能です。特に、消失訂正技術を用いることで、CRC値を維持したままメッセージを改ざんすることが容易です。また、CRCは分配法則・結合法則が成り立つため、秘密の文字列を付加しても改ざん耐性は向上しません。したがって、データの改ざんを検出するためには、暗号学的ハッシュ関数などの利用が推奨されます。

CRCの計算方法

CRCの計算は、入力ビット列と生成多項式を用いた排他的論理和（XOR）演算により行われます。具体的には、入力ビット列の下に生成多項式を左端を合わせて配置し、入力ビットが1の場合はXOR演算を行い、0の場合は何もしません。この処理を繰り返すことで、最終的に余りが得られます。この余りがCRCの値として利用されます。

CRCの数学的基礎

CRCの計算は、ビット列を多項式の係数と見なすことで数学的に解析できます。この多項式は有限体GF(2)の元であり、環の元として扱うことができます。環の性質を利用することで、CRCの誤り検出能力を評価し、より適切な生成多項式を選択することが可能です。

CRC多項式の設計

生成多項式の選択は、CRCの実装において非常に重要です。生成多項式は、衝突の確率を最小化しつつ、誤り検出能力を最大化するように選択されます。一般的に、生成多項式の長さは、検査値の長さに直接影響します。よく利用される長さとしては、9ビット（CRC-8）、17ビット（CRC-16）、33ビット（CRC-32）、65ビット（CRC-64）があります。また、生成多項式を選ぶ際には、処理速度、保護したいデータ長、希望する誤り保護特性などを考慮する必要があります。

特殊なCRCの実装

実用システムでは、CRCを複雑化させる場合があります。例えば、同期ずれを防ぐために固定ビットパターンを先頭に付加したり、CRC値をデータに付加する際に0を後置するなどの工夫がされます。また、ビット順序やバイト順序、生成多項式の最上位ビットを省略するなどの実装上の注意点があります。

主な標準CRC

CRCには多くの標準規格が存在し、CRC-12では3種類、CRC-16では8種類、CRC-32では3種類の多項式が使われています。KoopmanとCastagnoliらの研究により、従来よりも優れた誤り検出能力を持つ多項式が発見されており、iSCSIなどのプロトコルで採用されています。CRC-32では、IEEE勧告のものやV.42、イーサネット、ZIP、PNGなどで使われているものがありますが、Castagnoli CRC-32Cが最も優れているとされています。

過去に使われていたCRC

CRC-128やCRC-256などのより長いCRCも存在しますが、現在では暗号学的ハッシュ関数に置き換えられる傾向にあります。

CRCの実装例

CRC-32の実装例として、C言語での実装がよく知られています。RFC 1952 (gzip) や RFC 2083 (PNG) の末尾にも実装例が記載されており、zlibライブラリなどにも含まれています。

関連技術

CRCは、MD2、MD4、MD5、Adler-32、チェックサム、パリティビットなどの誤り検出技術と関連があります。

まとめ

巡回冗長検査（CRC）は、データ伝送や記憶媒体における誤り検出に欠かせない技術です。多項式を用いた計算により、効率的かつ効果的な誤り検出を可能にします。ただし、セキュリティ対策としては不十分であるため、適切な用途に応じて他の技術と組み合わせて利用する必要があります。

もう一度検索