巡回冗長検査

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

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

CRCは、

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

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

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

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

概要

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	$x+1$ （各種ハードウェア。パリティビット）	0x1 / 0x1 (0x1)
CRC-4-ITU	$x^{4}+x+1$ (ITU G.704, p. 12)	0x3 / 0xC (0x9)
CRC-5-ITU	$x^{5}+x^{4}+x^{2}+1$ (ITU G.704, p. 9)	0x15 / 0x15 (0x1A)
CRC-5-USB	$x^{5}+x^{2}+1$ （USBトークンパケット）	0x05 / 0x14 (0x12)
CRC-6-ITU	$x^{6}+x+1$ (ITU G.704, p. 3)	0x03 / 0x30 (0x21)
CRC-7	$x^{7}+x^{3}+1$ （通信系、MMC、SD）	0x09 / 0x48 (0x44)
CRC-8-ATM	$x^{8}+x^{2}+x+1$ (ATM Header Error Correction)	0x07 / 0xE0 (0x83)
CRC-8-CCITT	$x^{8}+x^{7}+x^{3}+x^{2}+1$ （1-Wire バス）	0x8D / 0xB1 (0xC6)
CRC-8-Dallas/Maxim	$x^{8}+x^{5}+x^{4}+1$ （1-Wire バス）	0x31 / 0x8C (0x98)
CRC-8	$x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1$	0xD5 / 0xAB (0xEA ^[6])
CRC-8-SAE J1850	$x^{8}+x^{4}+x^{3}+x^{2}+1$	0x1D / 0xB8 (0x8E)
CRC-10	$x^{10}+x^{9}+x^{5}+x^{4}+x+1$	0x233 / 0x331 (0x319)
CRC-11	$x^{11}+x^{9}+x^{8}+x^{7}+x^{2}+1$ (FlexRay)	0x385 / 0x50E (0x5C2)
CRC-12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$ （通信系、^[9]^[10] )	0x80F / 0xF01 (0xC07)
CRC-15-CAN	$x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1$	0x4599 / 0x4CD1 (0x62CC)
CRC-16-Fletcher	CRCではない。フレッチャーのチェックサム	Adler-32 A & B CRC で使用
CRC-16-CCITT	$x^{16}+x^{12}+x^{5}+1$ （X.25、V.41、CDMA、Bluetooth、XMODEM、HDLC、PPP、IrDA、BACnet; CRC-CCITTとも）	0x1021 / 0x8408 (0x8810 ^[6])
CRC-16-IBM	$x^{16}+x^{15}+x^{2}+1$ （SDLC、USB、その他; CRC-16とも）	0x8005 / 0xA001 (0xC002)
CRC-24-Radix-64	$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$ (FlexRay)	0x864CFB / 0xDF3261 (0xC3267D)
CRC-30	$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$ (CDMA)	0x2030B9C7 / 0x38E74301 (0x30185CE3)
CRC-32-Adler	CRCではない; Adler-32	Adler-32参照
CRC-32-IEEE 802.3	$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$ (V.42, MPEG-2, PNG ^[11])	0x04C11DB7 / 0xEDB88320 (0x82608EDB ^[8])
CRC-32C (Castagnoli)	$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$	0x1EDC6F41 / 0x82F63B78 (0x8F6E37A0 ^[8])
CRC-32K (Koopman)	$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$	0x741B8CD7 / 0xEB31D82E (0xBA0DC66B ^[8])
CRC-64-ISO	$x^{64}+x^{4}+x^{3}+x+1$ (HDLC — ISO 3309)	0x000000000000001B / 0xD800000000000000 (0x800000000000000D)
CRC-64-ECMA-182	$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}+$ $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$ (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つしかなく且つ、それらの間隔が両方のビット誤りを含め2^k-1ビットより短い場合、必ず検出できる。
長さkビットのCRC多項式は、入力メッセージ中の最初のビット誤りと最後のビット誤りの間隔が両方のビット誤りを含めkビットより短い場合、言い換えるとkビットより短いバースト誤りが1つしかない場合、必ず検出できる。
x + 1 を因数に持つCRC多項式は、入力メッセージ中に奇数個のビット誤りがある場合、必ず検出できる。

脚注

^ Peterson, W. W. and Brown, D. T. (1月 1961年). “Cyclic Codes for Error Detection”. Proceedings of the IRE 49: 228. doi:10.1109/JRPROC.1961.287814. ISSN 0096-8390.
^ ^a ^b Brayer, K (1975年). "Evaluation of error detection polynomial performance on the AUTOVON channel". Conference Record. National Telecommunications Conference, New Orleans, La. Vol. 1. New York: Institute of Electrical and Electronics Engineers. pp. p. 8-21 to 8-25. {{cite conference}}: |page(s)=にp.など余分の文字が入力されています。 (説明); 不明な引数|coauthors=は無視されます。（もしかして：|author=） (説明); 不明な引数|month=は無視されます。 (説明)
^ ビット幅の多寡とは別に、入力文字列の規則性（例えばASCII文字列であれば必ず8ビット目がゼロである等）に影響されてCRC値が偏る
^ “(slib) Cyclic Checksum”. 2008年4月6日閲覧。
^ Greg Cook (2008年9月9日). “Catalogue of parameterised CRC algorithms”. 2008年9月9日閲覧。
^ ^a ^b ^c Koopman, Philip; Chakravarty, Tridib (2004), Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks
^ Castagnoli, G. and Braeuer, S. and Herrman, M. (June 1993年). “Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits”. IEEE Transactions on Communications 41 (6): 883. doi:10.1109/26.231911. ISSN 0090-6778. - Castagnoli's et al. CRC多項式のアルゴリズム選択に関する研究
^ ^a ^b ^c ^d ^e ^f Koopman, P. (6月 2002年). “32-Bit Cyclic Redundancy Codes for Internet Applications”. The International Conference on Dependable Systems and Networks: 459. doi:10.1109/DSN.2002.1028931. - Castagnoli の結果を総当り探索で検証し、新たによい多項式を発見した。
^ Perez, A.; Wismer & Becker (1983年). “Byte-Wise CRC Calculations”. IEEE Micro 3 (3): 40–50. doi:10.1109/MM.1983.291120. ISSN 0272-1732.
^ Ramabadran, T.V.; Gaitonde, S.S. (1988年). “A tutorial on CRC computations”. IEEE Micro 8 (4): 62–75. doi:10.1109/40.7773. ISSN 0272-1732.
^ Thomas Boutell, Glenn Randers-Pehrson, et al. (1998年7月14日). “PNG (Portable Network Graphics) Specification, Version 1.2”. 2008年4月28日閲覧。

外部リンク

わかりやすい CRC32 の C++ によるソースコード
Free CRC Source Code from the Boost C++ Libraries
The CRC Pitstop
Williams, R. (1993-09) A Painless Guide to CRC Error Detection Algorithms
Black, R. (1994-02) Fast CRC32 in Software; Linux向けの4種類のアルゴリズムなど
Kounavis, M. and Berry, F. (2005). A Systematic Approach to Building High Performance, Software-based, CRC generators, Slicing-by-4 と slicing-by-8 アルゴリズム
CRC32: Generating a checksum for a file, C++ による実装 by Brian Friesen
CRC16 to CRC64 collision research
Reversing CRC - Theory and Practice.
'CRC-Analysis with Bitfilters'.
JFileRecovery CRCエラーの発生する媒体を読むツール（フリー）
MathPages - Cyclic Redundancy Checks
A CRC calculation utility and C source code generator written in Python. (MIT licence)
CRC Encoding - C# による実装 by Marcel de Wijs
Cyclic Redundancy Check: 主にCRC-32についての理論、ハードウェア、ソフトウェア。Henry S. Warren, Jr. の Hacker's Delight のサンプル

オンラインツール

Free CRC Verilog Circuit generator
CRC オンラインのCRC32/CRC32B計算機（多項式は不明）
文字列を入力すると、各種標準CRC(8/16/31/64)を計算するオンラインツール
オンラインCRC計算機
別のオンラインCRC計算機
CRC Tool: Generator of synthesizable CRC functions
TRANSLATOR, BINARY オンラインでASCII、16進、2進、Base64などに変換し、CRCを含めた各種ハッシュアルゴリズムによるチェックサムを計算する。

[PetersonBrown1961-1] Peterson, W. W. and Brown, D. T. (1月 1961年). “Cyclic Codes for Error Detection”. Proceedings of the IRE 49: 228. doi:10.1109/JRPROC.1961.287814. ISSN 0096-8390.

[BrayerHammond1975-2] Brayer, K (1975年). "Evaluation of error detection polynomial performance on the AUTOVON channel". Conference Record. National Telecommunications Conference, New Orleans, La. Vol. 1. New York: Institute of Electrical and Electronics Engineers. pp. p. 8-21 to 8-25. {{cite conference}}: |page(s)=にp.など余分の文字が入力されています。 (説明); 不明な引数|coauthors=は無視されます。（もしかして：|author=） (説明); 不明な引数|month=は無視されます。 (説明)

[3] ビット幅の多寡とは別に、入力文字列の規則性（例えばASCII文字列であれば必ず8ビット目がゼロである等）に影響されてCRC値が偏る

[slib-4] “(slib) Cyclic Checksum”. 2008年4月6日閲覧。

[cook-catalogue-5] Greg Cook (2008年9月9日). “Catalogue of parameterised CRC algorithms”. 2008年9月9日閲覧。

[koop04-6] Koopman, Philip; Chakravarty, Tridib (2004), Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks

[cast93-7] Castagnoli, G. and Braeuer, S. and Herrman, M. (June 1993年). “Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits”. IEEE Transactions on Communications 41 (6): 883. doi:10.1109/26.231911. ISSN 0090-6778. - Castagnoli's et al. CRC多項式のアルゴリズム選択に関する研究

[koop02-8] ^ ^a ^b ^c ^d ^e ^f Koopman, P. (6月 2002年). “32-Bit Cyclic Redundancy Codes for Internet Applications”. The International Conference on Dependable Systems and Networks: 459. doi:10.1109/DSN.2002.1028931. - Castagnoli の結果を総当り探索で検証し、新たによい多項式を発見した。

[9] Perez, A.; Wismer & Becker (1983年). “Byte-Wise CRC Calculations”. IEEE Micro 3 (3): 40–50. doi:10.1109/MM.1983.291120. ISSN 0272-1732.

[10] Ramabadran, T.V.; Gaitonde, S.S. (1988年). “A tutorial on CRC computations”. IEEE Micro 8 (4): 62–75. doi:10.1109/40.7773. ISSN 0272-1732.

[11] Thomas Boutell, Glenn Randers-Pehrson, et al. (1998年7月14日). “PNG (Portable Network Graphics) Specification, Version 1.2”. 2008年4月28日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

概要