巡回冗長検査（じゅんかいじょうちょうけんさ、）は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は、入力されたデータ列をもとに一種の割り算に似た計算を行い、その余りをチェック用の値として追加した上で送信する。受信側では、受け取ったデータを元に同じ計算を行い、その結果をチェック用の値と比較してデータ破損の有無を判断する。CRCは、デジタル回路で簡単に実装でき、数学的にも分析が容易で、伝送路ノイズによる誤りの検出によく使われている。パリティや単純な加算によるチェックサムに比べ検出精度が高く、その点では高級なチェックサムと言える。単純なチェックサムと同じく、データの改竄に対する耐性はない。CRCは W. Wesley Peterson が発明し、1961年に論文として発表した。CRC-32と一般に呼ばれているIEEE 802.3のCRCは1975年に登場し、イーサネットなどの各種通信やZIPやPNGなど各所に使われている。CRC は、巡回符号の理論に基づいた誤り検出符号の一種である。その計算は筆算による多項式の除算に似ており、送受信するデータを二進数とみなして、あらかじめ決めておいた特定の数で割り、その余りをチェック用の値として使う。除算に使う特定の数を生成多項式といい、送信側と受信側で揃えておく必要がある。また、有限体の繰り下がり（繰り上がり）のない算術を使っている点が通常の除算とは異なる。余りの長さは常に除数の長さ以下であり、除数の長さによって結果の長さを決定できる。CRC には多数のバリエーションがあり、主に出力結果のビット幅や生成多項式に違いがある。チェック用の値が n ビットになる CRC は CRC-n と表記される。規格によって生成多項式が異なることが多く、CRC-n XXX というように表記される（主な標準CRC）。CRCは任意の有限体を使って構築できるが、一般に使われているCRCは有限体 GF(2) を使用している。すなわち、2つの元の体であり、それを通常1と0で表す。CRCがよく使われている重要な理由として、効率が保証されている点が挙げられる。nビットCRCは通常、nビット未満の連続する誤り（バースト誤り）を検出できる。言い換えれば、nビットの範囲内に1ビットの誤りが複数存在する場合を検出できる。また、それより長いバースト誤りも 1-2 の確率で検出する。データ通信での誤りも記憶装置での誤りも、誤りは無作為に出現するわけではなくバースト性がある。そのため、CRCの性質はそれらによく合っており、単にパリティチェックを複数行うよりも便利である。最も単純な誤り検出であるパリティビットは、最も単純なCRCと見ることもできる（除数は2ビットの 11 である）。CRCは数学的特性上消失訂正が容易であることから、CRC値が変化しないように元のデータを改竄することが容易である。このため改竄検出には使えない。メッセージとそのCRCを受信し、メッセージから計算したCRCと受信したCRCが一致したとき、「転送中に改竄されなかった」と結論するのは間違いである。なぜならCRCは暗号ではないからである。CRCはデータ完全性のチェックに使われるが、それと暗号化とは別である。送信側でCRCを計算したときメッセージはそのままのクリアテキストであり、固定長のCRCが付与される。CRCはメッセージダイジェストと同様、メッセージとの1対1の対応が不可能（メッセージより常に情報量が少ないため）という問題があるが、一方向性関数でないぶんだけCRCの方が深刻である。つまり消失訂正によって同じCRC値になるメッセージを容易に作成可能であり、元のメッセージを少しだけ改変したものでもCRC値を同じにできる。ただし、設計上元のメッセージに非常によく似た（通信エラーと同程度にしか差異の無い）メッセージはCRCが大きく異なるため、検出可能である。また、伝送途中で傍受してメッセージを偽物とすりかえるなら、同時にCRCもすり替えることができる。従って、CRCはデータ完全性は検証できるが、改竄検出はできない。またCRCは分配法則・結合法則が成り立つので、メッセージ認証符号のHMACのような「秘密の文字列」を前置したり後置したりしても改竄に対する耐性は全く上がらない。nビットの2値CRCの計算方法は単純である。入力ビット列を一行に並べ、CRCの除数を表す (n+1) ビットのパターンをその下に左端を合わせるように書く。以下に3ビットCRCの計算の最初の様子を示す。除数の左端のビットの上にある入力ビットが0なら、何もせず除数を右に1ビットずらす。除数の左端のビットの上にある入力ビットが1なら、除数と入力ビットをXOR演算する（つまり、除数のビット列のうち 1 になっている部分の上にあたる入力ビットを反転させる）。そして、除数を右に1ビットずらす。これを除数が入力ビット列の右端に到達するまで繰り返す。最終状態は以下の通りである。除数の左端ビットは毎回入力ビットを0にしていくので、最終的には除数のビット数（nビット）の範囲にだけ1のビットが残ることになる。これが除算の余りであり、同時にCRC関数の値となる（CRC仕様によっては、さらなる後処理を要求する場合がある）。このような除法のような計算方法を数学的に分析することで、よりよい誤り検出が可能な除数を選択する方法がわかる。このとき、ビット列の各桁をある変数 x の多項式の係数と見なす。この係数は有限体 GF(2) の元であり、一般的な意味での数ではない。多項式と見なすことで、ビット列は環の元と見なすことができるようになる。環は大まかに言えば、数にある意味で似た元の集合であり、それに対して加算に似た操作と乗算に似た操作を作用させることができる。これらの演算は一般的な算術と同様、交換法則、結合法則、分配法則が成り立つ。環では一般的な解析的手法が使えるため、多項式に見立てることで解析が容易になる。生成多項式の選択は、CRCアルゴリズムの実装の最重要部分である。多項式は誤り検出機能を高めつつ、CRC値の衝突が起きにくくなるよう選択する必要がある。多項式の最も重要な属性は、その長さである（最も高次なゼロでない係数）。なぜなら、それがCRC値の長さに直接影響するからである。よく採用される多項式の長さは次の通り。新たなCRC多項式を作成したり、既存のCRCを改良する場合、多項式が既約性を持つようにするのが一般的である。すなわち生成多項式の特性は、アルゴリズムの定義から、以下のように導き出せる。誤り検出符号としてのCRCの概念を実用システムでの実装に移すとき、実装者がそれを複雑化させることがある。以下では、そのような例を解説する。巡回冗長検査は唯一の標準規格があるわけではなく、例えば CRC-12 では3種類の多項式が使われている。また、CRC-16 にはよく使われているものが8種類、CRC-32 は3種類存在する。よく使われている多項式が最も効果的とは限らない。1993年から2004年にかけて、Koopman と Castagnoli らは16ビットまでと、24ビットおよび32ビットの多項式の総当り的調査を行った。そして、それまで利用されていたものよりも（そのメッセージ長でのハミング距離の観点で）性能のよい多項式を発見し、今後の標準化に役立てられるよう発表した。iSCSIはその研究成果を取り入れている。よく使われるCRC-32多項式は、IEEE勧告のものも V.42、イーサネット、FDDI、ZIP、PNG などで使われているものも、ハミング符号の生成多項式を使っている。これは、誤り検出性能がよいためである。ただし、iSCSIで使っている Castagnoli CRC-32C の方がさらに優れている。以下の表は、実際に使われている各種アルゴリズムの多項式である。プロトコルによっては、これに事前の逆転や事後の逆転、ビット順序の反転などを施すことがある。独自プロトコルでのCRCは、目くらましとして初期値を複雑化させたり最後にXORしたりすることがあるが、それによって暗号的に強くなるわけではない。"注: ここでは、最上位ビットを省略している。上の特化したCRCの節参照。"以下は、かつて使われていたが、現在はハッシュ関数などに置換されたもの。C言語での実装例。RFC 1952 (gzip) や RFC 2083 (PNG) の末尾にも実装例が載っている。zlib などにも含まれている。生成多項式を反転させない場合の実装例。

出典:wikipedia