巡回冗長検査

巡回冗長検査は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出する。

デジタル回路で簡単に実装でき、数学的にも分析が容易であり、また、ビットのランダム誤りやバースト誤りを検出できるので、HDLC手順やCSMA/CD方式などにおいて誤りチェック・伝送路ノイズチェックによく使われている。パリティや単純な加算によるチェックサムに比べ検出精度が高く、その点では高級なチェックサムと言える。単純なチェックサムと同じく、データの改竄に対する耐性はない。

W・ウェスレイ・ピーターソンが発明し、1961年に論文として発表した。CRC-32と一般に呼ばれているIEEE 802.3のCRCは1975年に定められ、イーサネットなどの各種通信やZIPやPNGなど各所に使われている。

1. 概要
-----

CRC は、巡回符号の理論に基づいた誤り検出符号の一種である。その計算は筆算による多項式の除算に似ており、送受信するデータを、あらかじめ決めておいた特定の数で割り、その余りをチェック用の値として使う。ただし、通常の算術による計算ではなく、有限体の計算を行う。除算に使う特定の数を生成多項式という。余りの長さは常に除数の長さ以下であり、除数の長さによって結果の長さを決定できる。

CRCには多数のバリエーションがあり、主に出力結果のビット幅や生成多項式に違いがある。チェック用の値が n ビットになる CRC は CRC-n と表記される。規格によって生成多項式が異なることが多く、CRC-n XXX というように表記される。

CRCは任意の有限体を使って構築できるが、一般に使われているCRCは位数2のGFを使用している。

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

最も単純な誤り検出であるパリティビットは、最も単純なCRCと見ることもできる。

2. CRCとセキュリティ
-------------

CRC値は、メッセージとの1対1の対応が不可能という点は、暗号学的ハッシュ関数によるハッシュ値と同じだが、ハッシュ値はそれでも100ビット程度以上の大きさがあるのが普通であり、また、内容が異なるのに同じハッシュ値となるようなメッセージを偽造したりするのは容易でない。それに対し、CRC値は一般に小さく、さらには消失訂正という技法によって同じCRC値になるメッセージを容易に作成可能であり、元のメッセージを少しだけ改変したものでもCRC値を同じにできる。なお、元のメッセージに非常によく似たメッセージであれば、CRCの設計上、大きく異なるものにはなる。

また、通信システム全体の保安として考えた場合、伝送途中で傍受してメッセージを偽物とすりかえるなら、同時にCRCもすり替えることができると考えなければならないだろう。従ってこれらは直接には、第三者による意図的な改竄などを防ぐ手段にはならない。さらにCRCは分配法則・結合法則が成り立つので、メッセージ認証符号のHMACのような「秘密の文字列」を前置したり後置したりしても改竄に対する耐性は全く上がらない。

3. CRCの計算
---------

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

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

除数の左端ビットは毎回入力ビットを0にしていくので、最終的には除数のビット数の範囲にだけ1のビットが残ることになる。これが除算の余りであり、同時にCRC関数の値となる。

4. CRCの数学
---------

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

4.1. CRC多項式の設計
--------------

CRCアルゴリズムの実装で最も重要なのは、生成多項式の選択である。生成多項式は、衝突が起きる確率を最小にしつつ、誤り検出性能を最大にするように選ぶ必要がある。

生成多項式の長さは算出される検査値の長さに直接影響するため、最も重要な性質となる。

よく採用される多項式の長さは次の通り。

9 ビット 
17 ビット 
33 ビット 
65 ビット 検査値の長さが//n// ビットになるCRCは「//n// ビット CRC」と呼ばれる。長さ//n// が与えられたとき、生成多項式が互いに異なる複数のCRCを作ることが可能である。//n// ビットCRCの生成多項式は最大次数が//n// であり、したがって//n// + 1}}個の項を含む。剰余の長さは//n// となる。そのような特定のCRCを指す場合、 CRC-//n//-XXX という形式の呼び名が用いられる。

CRC多項式の設計には、処理速度だけでなく、保護したいブロックの最大長、希望する誤り保護特性、またCRCを実装するのためのリソースの種類も影響する。よくある誤解として、「最良の」CRC多項式は、既約多項式かあるいは既約多項式に因子1 + mvarを乗じたものだ、というものがある。因子1 + mvarは任意の奇数個のビット誤りを検出可能にするために用いられる。実際には、その前に述べた全ての事項を考慮して多項式を選択すべきであり、その結果として既約でない多項式が選ばれることもあり得る。しかしながら、既約でない多項式がつくる剰余環は零因子を含むため、一定の割合で誤りの検出漏れが発生する。

生成多項式の特性は、アルゴリズムの定義から、以下のように導き出せる。

ゼロでない係数が複数あるCRC多項式は、入力メッセージ中のビット誤りが1つしかない場合、必ず検出できる。
多項式の最長の既約部分の長さがkビットであるCRC多項式は、入力メッセージ中のビット誤りが2つしかなく且つ、それらの間隔が両方のビット誤りを含め2k-1ビットより短い場合、必ず検出できる。
長さkビットのCRC多項式は、入力メッセージ中の最初のビット誤りと最後のビット誤りの間隔が両方のビット誤りを含めkビットより長くない