巡回冗長検査

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

巡回冗長検査（じゅんかいじょうちょうけんさ、テンプレート:Lang-en-short）は、任意長のデータストリームを入力とし、例えば32ビット整数などの固定サイズの値を出力する誤り検出関数による誤り検出。関数や出力値を指しても言う。CRC値は、データの転送や格納時にその一部が偶然変化したことを検出するチェックサムとして使うことができる。デジタル回路で簡単に実装でき、数学的にも分析が容易で、伝送路ノイズによる誤りの検出によく使われている。CRCは W. Wesley Peterson が発明し、1961年に論文として発表した[1]。CRC-32と一般に呼ばれているIEEE 802.3のCRCは1975年に登場し、イーサネットなどの各種通信やZIPやPNGなど各所に使われている[2]。

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

CRCは、

  • パリティや単純な加算によるチェックサムに比べ検出精度が高い。
  • 高速である。
  • 1ビットずつの走査により計算ができ、実現するためのハードウェア回路が簡単。

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

CRC-32のソースコードについては、RFC 1952 (gzip) や RFC 2083 (PNG) などの末尾に記載されている。

CRCは生成法が一意に定まっていないため、同じビット列を処理してもプログラムにより全く違う値を返すことがある。主な違いに、ビット幅（通常、16bit若しくは32bit）、生成多項式（CCITTでは推奨値が2つ例示されている）、初期値、MSBとLSBのどちらを先にするか、結果を逆転・反転するかしないか、がある。一般的ではないが、ビット幅に関しては、12bitのものも存在する。また、同値が頻出する[3]など、ハッシュに最適とは言い難く、現在の主な用途は誤りの検出であるが、例えばBtrfsではファイル名のハッシュ（と様々なデータブロックの正当性の検査）に使われている。

概要

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チェックを行う場合に良く見られる。というのも、シリアルポートでは最下位ビットを先に転送するものが多いためである。
  • バイト順序: 多バイトCRCでは、バイトの転送順序に混乱が見られる。一部の16ビットCRCではCRCを構成する2バイトを入れ替えている。
  • 除数多項式の最上位ビットの省略: nビットCRCは (n+1) ビットの除数で定義されるもので、最上位ビットは常に1である。すると、nビットのレジスタではオーバフローするため、除数の最上位ビットを省略して示すことがある。

主な標準CRC

巡回冗長検査は唯一の標準規格があるわけではなく、例えば CRC-12 では3種類の多項式が使われている[4]。また、CRC-16 にはよく使われているものが8種類、CRC-32 は3種類存在する[5]。よく使われている多項式が最も効果的とは限らない。1993年から2004年にかけて、Koopman と Castagnoli らは16ビットまでと[6]、24ビットおよび32ビット[7][8]の多項式の総当り的調査を行った。そして、それまで利用されていたものよりも（そのメッセージ長でのハミング距離の観点で）性能のよい多項式を発見し、今後の標準化に役立てられるよう発表した[8]。iSCSIはその研究成果を取り入れている。

よく使われるCRC-32多項式は、IEEE勧告のものも V.42、イーサネット、FDDI、ZIP、PNG などで使われているものも、ハミング符号の生成多項式を使っている。これは、誤り検出性能がよいためである[2]。ただし、iSCSIで使っている Castagnoli CRC-32C の方がさらに優れている[8]。

以下の表は、実際に使われている各種アルゴリズムの多項式である。プロトコルによっては、これに事前の逆転や事後の逆転、ビット順序の反転などを施すことがある。独自プロトコルでのCRCは、目くらましとして初期値を複雑化させたり最後にXORしたりすることがあるが、それによって暗号的に強くなるわけではない。

注: ここでは、最上位ビットを省略している。上の特化したCRCの節参照。

名称 多項式 （用途） 標準 / 反転 （相反多項式の反転）
CRC-1 <math>x + 1</math> （各種ハードウェア。パリティビット） 0x1 / 0x1 (0x1)
CRC-4-ITU <math>x^4 + x + 1</math> (ITU G.704, p. 12) 0x3 / 0xC (0x9)
CRC-5-ITU <math>x^5 + x^4 + x^2 + 1</math> (ITU G.704, p. 9) 0x15 / 0x15 (0x1A)
CRC-5-USB <math>x^5 + x^2 + 1</math> （USBトークンパケット） 0x05 / 0x14 (0x12)
CRC-6-ITU <math>x^6 + x + 1</math> (ITU G.704, p. 3) 0x03 / 0x30 (0x21)
CRC-7 <math>x^7 + x^3 + 1</math> （通信系、MMC、SD） 0x09 / 0x48 (0x44)
CRC-8-ATM <math>x^8 + x^2 + x + 1</math> (ATM Header Error Correction) 0x07 / 0xE0 (0x83)
CRC-8-CCITT <math>x^8 + x^7 + x^3 + x^2 + 1</math> （1-Wire バス） 0x8D / 0xB1 (0xC6)
CRC-8-Dallas/Maxim <math>x^8 + x^5 + x^4 + 1</math> （1-Wire バス） 0x31 / 0x8C (0x98)
CRC-8 <math>x^8 + x^7 + x^6 + x^4 + x^2 + 1</math> 0xD5 / 0xAB (0xEA [6])
CRC-8-SAE J1850 <math>x^8 + x^4 + x^3 + x^2 + 1</math> 0x1D / 0xB8 (0x8E)
CRC-10 <math>x^{10} + x^9 + x^5 + x^4 + x + 1</math> 0x233 / 0x331 (0x319)
CRC-11 <math>x^{11} + x^9 + x^8 + x^7 + x^2 + 1</math> (FlexRay) 0x385 / 0x50E (0x5C2)
CRC-12 <math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math> （通信系、[9][10] ) 0x80F / 0xF01 (0xC07)
CRC-15-CAN <math>x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1 </math> 0x4599 / 0x4CD1 (0x62CC)
CRC-16-Fletcher CRCではない。フレッチャーのチェックサム Adler-32 A & B CRC で使用
CRC-16-CCITT <math>x^{16} + x^{12} + x^5 + 1</math> （X.25、V.41、CDMA、Bluetooth、XMODEM、HDLC、PPP、IrDA、BACnet; CRC-CCITTとも） 0x1021 / 0x8408 (0x8810 [6])
CRC-16-IBM <math>x^{16} + x^{15} + x^2 + 1</math> （SDLC、USB、その他; CRC-16とも） 0x8005 / 0xA001 (0xC002)
CRC-24-Radix-64 <math> x^{24} + x^{23} + x^{18} + x^{17} + x^{14} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1 </math> (FlexRay) 0x864CFB / 0xDF3261 (0xC3267D)
CRC-30 <math>x^{30} + x^{29} + x^{21} + x^{20} + x^{15} + x^{13} + x^{12} + x^{11} + x^{8} + x^{7} + x^{6} + x^{2} + x + 1 </math> (CDMA) 0x2030B9C7 / 0x38E74301 (0x30185CE3)
CRC-32-Adler CRCではない; Adler-32 Adler-32参照
CRC-32 <math>x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math>
(V.42, MPEG-2, zlib, PNG [11]) 		0x04C11DB7 / 0xEDB88320 (0x82608EDB [8])
CRC-32C (Castagnoli) <math>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1</math> (iSCSI, Btrfs) 0x1EDC6F41 / 0x82F63B78 (0x8F6E37A0 [8])
CRC-32K (Koopman) <math>x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} + x^{11} + x^{10} + x^{7} + x^{6} + x^{4} + x^{2} + x + 1</math> 0x741B8CD7 / 0xEB31D82E (0xBA0DC66B [8])
CRC-64-ISO <math>x^{64} + x^4 + x^3 + x + 1</math> (HDLC — ISO 3309) 0x000000000000001B / 0xD800000000000000 (0x800000000000000D)
CRC-64-ECMA-182 <math>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} +</math> <math>x^{32} + x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1</math> (ECMA-182 p.63) 0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 (0xA17870F5D4F51B49)

以下は、かつて使われていたが、現在はハッシュ関数などに置換されたもの。

  • CRC-128 (IEEE)
  • CRC-256 (IEEE)

CRC多項式の設計

生成多項式の選択は、CRCアルゴリズムの実装の最重要部分である。多項式は誤り検出機能を高めつつ、CRC値の衝突が起きにくくなるよう選択する必要がある。

多項式の最も重要な属性は、その長さである（最も高次なゼロでない係数）。なぜなら、それがCRC値の長さに直接影響するからである。

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

  • 9 ビット (CRC-8)
  • 17 ビット (CRC-16)
  • 33 ビット (CRC-32)
  • 65 ビット (CRC-64)

新たなCRC多項式を作成したり、既存のCRCを改良する場合、多項式が既約性を持つようにするのが一般的である。すなわち

  • この場合の既約性とは、多項式が自分自身か1でしか割り切れないことを意味する。
  • 既約でない多項式も使えるが、誤り検出力が劣る。しかし、用途によっては既約でない多項式を使っている場合もある。

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

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

実装例

CRC-32

C言語での実装例。RFC 1952 や RFC 2083 の末尾にも実装例が載っている。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;
}

関連項目

脚注

テンプレート:Reflist

外部リンク

オンラインツール

  • ↑ テンプレート:Cite journal
  • ↑ 2.0 2.1 テンプレート:Cite conference
  • ↑ ビット幅の多寡とは別に、入力文字列の規則性（例えばASCII文字列であれば必ず8ビット目がゼロである等）に影響されてCRC値が偏る
  • ↑ テンプレート:Cite web
  • ↑ テンプレート:Cite web
  • ↑ 6.0 6.1 6.2 テンプレート:Citation
  • ↑ テンプレート:Cite journal - Castagnoli's et al. CRC多項式のアルゴリズム選択に関する研究
  • ↑ 8.0 8.1 8.2 8.3 8.4 8.5 テンプレート:Cite journal - Castagnoli の結果を総当り探索で検証し、新たによい多項式を発見した。
  • ↑ テンプレート:Cite journal
  • ↑ テンプレート:Cite journal
  • ↑ テンプレート:Cite web
    • 「http://wikippe.e-do-match.com/index.php?title=巡回冗長検査&oldid=64793」から取得