前のページ 1/3 次のページ

巡回冗長検査(じゅんかいじょうちょうけんさ、英: Cyclic Redundancy Check、CRC)とは、任意長のデータストリームを入力とし、例えば32ビット整数などの固定サイズの値を出力する関数の一種であり、連続する誤りを検出するための誤り検出符号の一種。CRC という用語は、その関数自体を指す場合とその出力値を指す場合がある。CRCは、データの転送や格納時にその一部が偶然変化したことを検出するチェックサムとして使うことができる。デジタル回路で簡単に実装でき、数学的にも分析が容易で、伝送路ノイズによる誤りの検出によく使われている。CRCは W. Wesley Peterson が発明し、1961年に論文として発表した。IEEE勧告の32ビットCRCは1975年に登場し、イーサネットなどの各種通信に使われている。

この符号自体はデータが誤りであることを検出できるにすぎず、値から元のデータを復元できるわけではない。

CRCは、

・パリティ・チェックサム方式に比べ検出精度が高い。

・高速である。

・1ビットずつの走査により計算ができ、実現するためのハードウェア回路が簡単。

などの特徴を持つことから、ネットワークからハードウェア回路における転送に幅広く使われているだけにとどまらず、ソフトウェアにおいてデータの検索のハッシュキーなどに使われることもある。

CRCのソースコードについては、RFC1952に規定されているGZIPフォーマットに含まれるcrc32.cにある。

ただ、CRCはビット幅(通常、16bit若しくは32bit)、生成多項式(CCITTで推奨値が2つ例示されている)等が一意に定まっていないため、同じビット列を処理してもプログラムにより全く違う値を返すことがある。一般的ではないが、ビット幅に関しては、12bitのものも存在する。また、ハッシュとして用いるには同値が頻出するため適当と言えず、現在では誤りの検出以外の目的で使用されることはまれである。

◆ 概要

CRCは誤り検出符号の一種である。その計算は長除法に似ているが、商は捨てて余りを結果とする。また、有限体の繰り下がり(繰り上がり)のない算術を使っている点が通常の除算とは異なる。余りの長さは常に除数の長さ以下であり、除数の長さによって結果の長さを決定できる。個別のCRCではこの除数が必ず定義されている。

CRCは任意の有限体を使って構築できるが、一般に使われているCRCは有限体 GF(2) を使用している。すなわち、2つの元の体であり、それを通常1と0で表す。以下、本項目では2値CRCのみを扱う。

CRCがよく使われている重要な理由として、効率が保証されている点が挙げられる。nビットCRCは通常、nビット未満の連続する誤り(バースト誤り)を検出できる。言い換えれば、nビットの範囲内に1ビットの誤りが複数存在する場合を検出できる。また、それより長いバースト誤りも 1-2^-n の確率で検出する。データ通信での誤りも記憶装置での誤りも、誤りは無作為に出現するわけではなくバースト性がある。そのため、CRCの性質はそれらによく合っており、単にパリティチェックを複数行うよりも便利である。

最も単純な誤り検出であるパリティビットは、最も単純なCRCと見ることもできる(除数は2ビットの 11 である)。

◆ CRCとセキュリティ

CRC の数学的特性上、CRC値が変化しないように元のデータを改ざんすることが容易であり、CRC単独では意図的なデータ改ざんを検出するのには向いていない。メッセージとそのCRCを受信し、メッセージから計算したCRCと受信したCRCが一致したとき、「転送中に改ざんされなかった」と結論するのは間違いである。なぜならCRCは暗号ではないからである。CRCはデータ完全性のチェックに使われるが、それと暗号化とは別である。送信側でCRCを計算したときメッセージはそのままのクリアテキストであり、固定長のCRCがその末尾に付与される。

CRCはメッセージダイジェストと同様、メッセージとの1対1の対応が不可能(メッセージより常に情報量が少ないため)という問題があるが、一方向性関数でないぶんだけCRCの方が深刻である。つまり、同じCRC値になるメッセージを容易に作成可能であり、元のメッセージを少しだけ改変したものでもCRC値を同じにできる。ただし、設計上もとのメッセージに非常によく似たメッセージはCRCが大きく異なるため、検出可能である。

また、伝送途中で傍受してメッセージを偽物とすりかえるなら、同時にCRCもすり替えることができる。従って、CRCはデータ完全性は検証できるが、データの正しさは保証できない。

対照的に、意図的な改ざんからメッセージを守る方法としては、HMACのようなメッセージ認証符号を用いるのが有効である。

◆ CRCの計算

nビットの2値CRCの計算方法は単純である。入力ビット列を一行に並べ、CRCの除数を表す (n+1) ビットのパターンをその下に左端を合わせるように書く。以下に3ビットCRCの計算の最初の様子を示す。

11010011101100 <--- 入力

1011 <--- 除数 (4 Bits)

--------------

01100011101100 <--- 結果

除数の左端のビットの上にある入力ビットが0なら、何もせず除数を右に1ビットずらす。除数の左端のビットの上にある入力ビットが1なら、除数と入力ビットをXOR演算する(つまり、除数のビット列のうち 1 になっている部分の上にあたる入力ビットを反転させる)。そして、除数を右に1ビットずらす。これを除数が入力ビット列の右端に到達するまで繰り返す。最終状態は以下の通りである。

00000000001110 <--- それまでの計算結果

1011 <--- 除数

--------------

00000000000101 <--- 余り (3 bits)

除数の左端ビットは毎回入力ビットを0にしていくので、最終的には除数のビット数(nビット)の範囲にだけ1のビットが残ることになる。これが除算の余りであり、同時にCRC関数の値となる(CRC仕様によっては、さらなる後処理を要求する場合がある)。

◆ CRCの数学

このような除法のような計算方法を数学的に分析することで、よりよい誤り検出が可能な除数を選択する方法がわかる。このとき、ビット列の各桁をある変数 x の多項式の係数と見なす。この係数は有限体 GF(2) の元であり、一般的な意味での数ではない。多項式と見なすことで、ビット列は環の元と見なすことができるようになる。環は大まかに言えば、数にある意味で似た元の集合であり、それに対して加算に似た操作と乗算に似た操作を作用させることができる。これらの演算は一般的な算術と同様、交換法則、結合法則、分配法則が成り立つ。環では一般的な解析的手法が使えるため、多項式に見立てることで解析が容易になる。

◆ 特化したCRC

誤り検出符号としてのCRCの概念を実用システムでの実装に移すとき、実装者がそれを複雑化させることがある。以下では、そのような例を解説する。

・ 検査対象のビットストリームに固定ビットパターンを常に前置する実装。これは同期がずれた際にCRCの対象となる部分を明らかにするための実装である。つまり、ある時点でメッセージが受信されるはずだという場合、同期がずれると先頭に0がずっと並んだメッセージを受信したようになる。固定パターンがメッセージの先頭に必ず存在するなら、同期がずれてもメッセージの範囲がすぐにわかる。

・ 検査対象のビットストリームに多項式除算を行う前にnビットの0を常に後置する実装(n はCRCのサイズ)。この場合、CRCをビットストリームに加算する形で送出する。するとnビットの0を後置した部分がCRCに置き換わり、それを含めたビットストリームに対して検査を行うと必ず余りが0になる。

・ ビットストリームの多項式除算の余りに固定ビットパターンをXORする実装。

・ ビット順序: ある種の方式では各バイトの最下位ビットを先頭とする。すると多項式除算での「左端」は通常の意味での最下位ビットになる。これはシリアルポートでの転送でハードウェアによるCRCチェックを行う場合に良く見られる。というのも、シリアルポートでは最下位ビットを先に転送するものが多いためである。

前のページ 1/3 次のページ

・巡回冗長検査 page1

・巡回冗長検査 page2

・巡回冗長検査 page3