巡回冗長検査

巡回冗長検査（じゅんかいじょうちょうけんさ、英: Cyclic Redundancy Check, CRC）は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出する。
デジタル回路で簡単に実装でき、数学的にも分析が容易であり、また、ビットのランダム誤りやバースト誤りを検出できるので、HDLC手順やCSMA/CD方式などにおいて誤りチェック・伝送路ノイズチェックによく使われている。パリティや単純な加算による検査合計に比べ検出精度が高く、その点では高級な検査合計と言える。単純な検査合計と同じく、データの改竄に対する耐性はない。
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は位数2のGF(2)を使用している。
CRCがよく使われている重要な理由として、効率が保証されている点が挙げられる。nビットCRCは通常、nビット未満の連続する誤り（バースト誤り）を検出できる。言い換えれば、nビットの範囲内に1ビットの誤りが複数存在する場合を検出できる。また、それより長いバースト誤りも 1-2⁻ⁿ の確率で検出する。データ通信での誤りも記憶装置での誤りも、誤りは無作為に出現するわけではなくバースト性がある。そのため、CRCの性質はそれらによく合っており、単にパリティチェックを複数行うよりも便利である。
最も単純な誤り検出であるパリティビットは、最も単純なCRCと見ることもできる（除数は2ビットの 11 である）。

CRCとセキュリティ

CRC値は、メッセージとの1対1の対応が不可能（メッセージより常に情報量が少ないため）という点は、暗号学的ハッシュ関数によるハッシュ値（以下、単に「ハッシュ値」とする）と同じだが、ハッシュ値はそれでも100ビット程度以上の大きさがあるのが普通であり、また、内容が異なるのに同じハッシュ値となるようなメッセージを偽造したりするのは容易でない（という特性が一般に暗号学的ハッシュ関数には必須である）。それに対し、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-32

C言語での実装例。RFC 1952 (gzip) や RFC 2083 (PNG) の末尾にも実装例が載っている。zlib などにも含まれている。
uint32_t crc_table[256];void make_crc_table(void) {
    for (uint32_t i = 0; i < 256; i++) {
        uint32_t c = i;
        for (int j = 0; j < 8; j++) {
            c = (c & 1) ? (0xEDB88320 ^ (c >> 1)) : (c >> 1);
        }
        crc_table[i] = c;
    }}uint32_t crc32(uint8_t *buf, size_t len) {
    uint32_t c = 0xFFFFFFFF;
    for (size_t i = 0; i < len; i++) {
        c = crc_table[(c ^ buf[i]) & 0xFF] ^ (c >> 8);
    }
    return c ^ 0xFFFFFFFF;}int main(void){
    make_crc_table();
    uint32_t crc = crc32();
    
    return 0;}
生成多項式を反転させない場合の実装例。
uint32_t crc_table[256];/* 事前にこの関数を実行しておくこと */void make_crc_table(void){
    for(uint32_t i=0; i<256; i++){
        uint32_t c = i << 24;
        for( int j=0; j<8; j++){
            c = ( c << 1) ^ ( ( c & 0x80000000) ? 0x04C11DB7 : 0);
        }
        crc_table[i] = c;
    }}uint32_t crc32(uint8_t *buf, int len){
    uint32_t c = 0xffffffff;
    for (int i = 0; i < len; i++)    {
        c = (c << 8) ^ crc_table[((c >> 24) ^ buf[i]) & 0xff];
    }
    return c;}