巡回冗長検査

巡回冗長検査( CRC ) は、デジタルネットワークやストレージデバイスで一般的に使用されるエラー検出コードで、デジタルデータの偶発的な変更を検出します。これらのシステムに入力されるデータブロックには、その内容の多項式除算の余りに基づく短いチェック値が付加されます。データ取得時には、この計算が繰り返され、チェック値が一致しない場合は、データ破損に対する修正措置が講じられます。CRC はエラー訂正に使用できます(ビットフィルタを参照)。^{[ 1 ]}

CRCは、チェック（データ検証）値が冗長性（情報を追加せずにメッセージを拡張する）であり、アルゴリズムが巡回符号に基づいていることから、このように呼ばれています。CRCは、バイナリハードウェアでの実装が容易で、数学的に解析しやすく、特に伝送チャネルのノイズによって引き起こされる一般的なエラーの検出に優れているため、広く利用されています。チェック値の長さが固定されているため、それを生成する関数はハッシュ関数として使用されることがあります。

CRCは巡回誤り訂正符号の理論に基づいています。固定長のチェック値を追加してメッセージを符号化する体系的な巡回符号を通信ネットワークのエラー検出に用いることは、 1961年にW.ウェズリー・ピーターソンによって初めて提案されました。 ^{[ 2 ]}巡回符号は実装が簡単なだけでなく、バ​​ーストエラー（メッセージ内の誤ったデータシンボルの連続シーケンス） の検出に特に適しているという利点があります。これは、バーストエラーが磁気ストレージデバイスや光ストレージデバイスを含む多くの通信チャネルで一般的な伝送エラーであるため重要です。通常、任意の長さのデータブロックに適用されるnビットCRCは、 nビットより長くない単一のエラーバーストを検出し、それより長いエラーバーストのうち検出される割合は約(1 − 2 ^{− n} )です。

CRCコードの仕様には、いわゆる生成多項式の定義が必要です。この多項式は、メッセージを被除数とし、商を切り捨てて余りを結果とする多項式除算における除数となります。重要な注意点は、多項式の係数は有限体の算術に基づいて計算されるため、加算演算は常にビット単位で並列に実行できる（桁間の繰り上がりがない）ということです。

実際には、一般的に使用されているCRCはすべて、2つの要素を持つ有限体GF(2)を使用しています。この2つの要素は通常0と1と呼ばれ、コンピュータのアーキテクチャと容易に一致します。

CRCのチェック値がnビット長である場合、その CRC はnビット CRC と呼ばれます。与えられたnに対して、複数の CRC が存在し、それぞれ異なる多項式を持ちます。このような多項式の最高次数はnであり、これはn + 1個の項を持つことを意味します。言い換えれば、多項式の長さはn + 1であり、その符号化にはn + 1ビットが必要です。ほとんどの多項式仕様では、常に 1 であるため、最上位ビット(MSb)または最下位ビット(LSb)は省略されることに注意してください。CRC および関連する多項式には、通常、以下の表のように CRC- n -XXXの形式の名前が付けられます。

最も単純なエラー検出システムであるパリティビットは、実際には1ビットCRCです。生成多項式x + 1（2項）を使用し、^{[ 3 ]} CRC-1という名前が付けられています。 

CRC対応デバイスは、送信または保存される各データブロックに対して、チェック値またはCRCと呼ばれる短い固定長のバイナリシーケンスを計算し、それをデータに追加してコードワードを形成します。

符号語が受信または読み取られると、デバイスは、そのチェック値をデータブロックから新たに計算された値と比較するか、あるいは同等に、符号語全体に対してCRCを実行し、結果として得られたチェック値を期待される剰余定数と比較します。

CRC値が一致しない場合、そのブロックにはデータエラーが含まれています。

デバイスは、ブロックを再読み込みしたり、再送信を要求したりするなど、修正措置を講じる場合があります。それ以外の場合は、データはエラーがないものとみなされます（ただし、ごくわずかな確率で検出されないエラーが含まれている可能性があります。これはエラーチェックの性質上避けられないものです）。^{[ 4 ]}

CRC（証明書誤り訂正）は、通信チャネルにおける一般的なエラーから保護するために特別に設計されており、配信されたメッセージの完全性を迅速かつ合理的に保証することができます。しかし、意図的なデータ改ざんから保護するには適していません。

まず、認証がないため、攻撃者はメッセージを編集してCRCを再計算しても、改ざんが検出されません。CRCと暗号学的ハッシュ関数は、データとともに保存される場合、それ自体では意図的なデータ改ざんから保護されません。このような攻撃から保護する必要のあるアプリケーションは、メッセージ認証コードやデジタル署名（これらは一般的に暗号学的ハッシュ関数に基づいています）などの暗号学的認証メカニズムを使用する必要があります。

第二に、暗号学的ハッシュ関数とは異なり、CRCは容易に可逆な関数であるため、デジタル署名での使用には適していません。^{[ 5 ]}

第三に、CRCは線形関数（より正確にはアフィン関数）と同様の関係を満たします。 ^{[ 6 ]}

${\displaystyle \operatorname {CRC} (x\oplus y)=\operatorname {CRC} (x)\oplus \operatorname {CRC} (y)\oplus c}$

どこ${\displaystyle c}$長さによって${\displaystyle x}$そして${\displaystyle y}$これは次のようにも表現できます。${\displaystyle x}$、${\displaystyle y}$そして${\displaystyle z}$同じ長さである

${\displaystyle \operatorname {CRC} (x\oplus y\oplus z)=\operatorname {CRC} (x)\oplus \operatorname {CRC} (y)\oplus \operatorname {CRC} (z);}$

その結果、CRCがXORを結合演算として使用するストリーム暗号（またはOFBやCFBなど、実質的にストリーム暗号に変換するブロック暗号のモード）で暗号化されていても、暗号化キーを知らなくてもメッセージと関連するCRCの両方を操作できてしまう。これは、Wired Equivalent Privacy （WEP）プロトコルのよく知られた設計上の欠陥の1つだった。^{[ 7 ]}

nビットのバイナリCRCを計算するには、入力を表すビットを1行に並べ、CRCの除数（「多項式」と呼ばれる）を表す( n +1 )ビットのパターンを行の左端の下に配置します。

^{この例では、14 ビットのメッセージを、多項式}x³ + x + 1を用いた 3 ビット CRC でエンコードします。多項式は係数としてバイナリで表されます。3 次多項式には 4 つの係数 ( 1 x³ + 0 ^x² + 1 x + 1 ) があります。この場合、係数は 1、0、1、1 です^。計算結果は 3 ビット長なので、3 ビット CRC と呼ばれます。ただし、多項式を明示的に示すには 4 ビットが必要です。

まず、エンコードするメッセージを用意します。

11010011101100 

まず、CRCのビット長nに対応するゼロで埋めます。これは、結果として得られるコードワードが体系的な形式になるようにするためです。3ビットCRCを計算するための最初の計算式は次のとおりです。

11010011101100 000 <--- 入力は右から3ビットでパディングされています 1011 <--- 除数 (4 ビット) = x^3 + x + 1 ------------------ 01100011101100 000 <--- 結果

このアルゴリズムは、各ステップで除数の直上のビットに対して作用します。その反復の結果は、多項式の除数とそれより上のビットとのビットごとのXOR演算です。除数より上ではないビットは、そのステップでは単純に直下にコピーされます。次に、除数は入力の残りの最上位の1ビットに揃えるように右にシフトされ、除数が入力行の右端に達するまでこのプロセスが繰り返されます。計算全体は次のとおりです。

11010011101100 000 <--- 入力は右から3ビットでパディングされています 1011 <--- 除数 01100011101100 000 <--- 結果（最初の4ビットは下の除数とのXOR演算結果で、残りのビットは変更されません） 1011 <--- 除数 ... 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 <--- 除数は、被除数の次の 1 に揃えるように移動します (そのステップの商はゼロだったため) 1011（つまり、必ずしも1回の反復で1ビットずつ移動するとは限らない） 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1 ----------------- 00000000000000 100 <--- 余り (3 ビット)。被除数がゼロなので、除算アルゴリズムはここで停止します。 

左端の除数ビットが触れた入力ビットをすべてゼロにするため、この処理が終了すると、入力行でゼロ以外の値を取り得るビットは、行の右端にあるnビットのみとなります。これらのnビットは除算ステップの剰余であり、CRC関数の値にもなります（ただし、選択したCRC仕様で後処理が要求されている場合は除きます）。

受信メッセージの有効性は、上記の計算を再度実行し、今度はゼロの代わりにチェック値を加えることで簡単に検証できます。検出可能なエラーがなければ、余りはゼロになるはずです。

11010011101100 100 <--- チェック値付き入力 1011 <--- 除数 01100011101100 100 <--- 結果 1011 <--- 除数 ... 00111011101100 100 …… 00000000001110 100 1011 00000000000101 100 101 1 ------------------ 000000000000000 000 <--- 余り 

以下のPythonコードは、指定された入力と多項式に対して、初期パディングとして1または0を用いた初期CRC剰余を返す関数を示しています。このコードは、生の数値ではなく文字列入力に対応しています。

def crc_remainder ( input_bitstring , polynomial_bitstring , initial_filler ): """選択した多項式を使用してビット列のCRC剰余を計算します。initial_filler は'1'または'0'である必要があります。 """ polynomial_bitstring = polynomial_bitstring . lstrip ( "0" ) len_input = len ( input_bitstring ) initial_padding = ( len ( polynomial_bitstring ) - 1 ) * initial_filler input_padded_array = list ( input_bitstring + initial_padding ) while "1" in input_padded_array [: len_input ]: cur_shift = input_padded_array . index ( "1" ) for i in range ( len ( polynomial_bitstring )): input_padded_array [ cur_shift + i ] \ = str ( int ( polynomial_bitstring [ i ] != input_padded_array [ cur_shift + i ])) return "" . join ( input_padded_array )[ len_input :]def crc_check ( input_bitstring , polynomial_bitstring , check_value ): """選択した多項式を使用してビット列のCRCチェックを計算します。""" polynomial_bitstring = polynomial_bitstring . lstrip ( "0" ) len_input = len ( input_bitstring ) initial_padding = check_value input_padded_array = list ( input_bitstring + initial_padding ) while "1" in input_padded_array [: len_input ]: cur_shift = input_padded_array . index ( "1" ) for i in range ( len ( polynomial_bitstring )): input_padded_array [ cur_shift + i ] \ = str ( int ( polynomial_bitstring [ i ] != input_padded_array [ cur_shift + i ])) return ( "1" not in "" . join ( input_padded_array )[ len_input :])

>>> crc_remainder ( '11010011101100' , '1011' , '0' ) '100' >>> crc_check ( '11010011101100' , '1011' , '100' ) True

この除算のようなプロセスを数学的に解析すると、優れたエラー検出特性を保証する除数を選択する方法が明らかになります。この解析では、ビット列の桁は、より馴染みのある数値ではなく、ある変数xの多項式の係数（有限体GF(2)の要素（ 2 を法とする整数、つまり 0 または 1））として扱われます。バイナリ多項式の集合は数学的な環です。

CRCをエラー検出コードとして捉える概念は、実装者や標準化委員会が実用的なシステムを設計する際に複雑化します。以下にその複雑さの一部を示します。

• 実装によっては、チェック対象のビットストリームに固定のビットパターンを付加することがあります。これは、クロックエラーによってメッセージの先頭に0ビットが挿入され、そうでなければチェック値が変更されないような場合に有効です。
• 通常、実装では、多項式除算が行われる前に、チェック対象のビットストリームにn 個の 0 ビット( nは CRC のサイズ)を追加しますが、常にそうとは限りません。このような追加は、CRC の計算に関する記事で明示的に示されています。この方法の利点は、チェック値が追加された元のビットストリームの余りが正確にゼロになるため、受信したビットストリームに対して多項式除算を実行し、余りをゼロと比較するだけで CRC をチェックできることです。排他的論理和演算の結合法則と交換法則により、実用的なテーブル駆動の実装では、メッセージ ビットストリームと CRC レジスタからシフトアウトされるストリームを組み合わせる同等のより高速なアルゴリズム^{[ 8 ]}を使用することで、ゼロを明示的に追加することなく、ゼロ追加と数値的に同等の結果を得ることができます。
• 実装によっては、固定ビットパターンを多項式除算の剰余に排他的論理和演算することがある。
• ビット順序：一部の方式では、各バイトの最下位ビットを「最初」とみなしますが、多項式除算では「最左端」となり、これは私たちが通常理解する「最下位」とは異なります。この慣習は、シリアルポート伝送がハードウェアでCRCチェックされる場合に理にかなっています。なぜなら、広く普及しているシリアルポート伝送方式の中には、バイトを最下位ビットから送信するものがあるためです。
• バイト順序：マルチバイトCRCでは、最初に送信されるバイト（またはメモリのアドレスが最も低いバイトに格納されるバイト）が最下位バイト（LSB）なのか最上位バイト（MSB）なのかが混乱することがあります。例えば、16ビットCRC方式の中には、チェック値のバイトを入れ替えるものがあります。
• 除数多項式の上位ビットの省略: 上位ビットは常に 1 であり、nビット CRC は n ビット レジスタをオーバーフローする (n + 1) ビット除数によって定義されなければならないため、除数の上位ビットについて言及する必要はないと考える著者もいます。
• 除数多項式の下位ビットの省略: 下位ビットは常に 1 なので、Philip Koopman などの著者は上位ビットはそのままにして下位ビット (${\displaystyle x^{0}}$または 1 項）。この規則では、次数を含めた多項式を 1 つの整数で符号化します。

これらの複雑さから、多項式を整数として表現する一般的な方法は 3 つあります。最初の 2 つはバイナリで鏡像関係にあり、コードに見られる定数です。3 つ目はクープマンの論文に見られる数値です。 いずれの場合も、1 つの項が省略されます。したがって、多項式は${\displaystyle x^{4}+x+1}$次のように転写される可能性があります。

• 0x3 = 0b0011 は、${\displaystyle x^{4}+(0x^{3}+0x^{2}+1x^{1}+1x^{0})}$（最上位ビット優先コード）
• 0xC = 0b1100、${\displaystyle (1x^{0}+1x^{1}+0x^{2}+0x^{3})+x^{4}}$（LSB-firstコード）
• 0x9 = 0b1001 は、${\displaystyle (1x^{4}+0x^{3}+0x^{2}+1x^{1})+x^{0}}$（クープマン記法）

以下の表では、それらは次のように示されています。

独自のプロトコルにおける CRC は、非自明な初期値と最終的な XOR を使用することで難読化される可能性があるが、これらの技術はアルゴリズムに暗号学的強度を導入するものではなく、単純な方法でリバースエンジニアリングされる可能性がある。 ^{[ 10 ]}

巡回冗長検査のさまざまな種類が技術標準に組み込まれています。 1 つのアルゴリズム、または各次数につき 1 つのアルゴリズムがすべての目的に適しているわけではありません。 Koopman と Chakravarty は、アプリケーションの要件とメッセージ長の予想される分布に応じて多項式を選択することを推奨しています。^{[ 11 ]}使用されている CRC の種類の多さが開発者を混乱させており、著者らはこの状況に対処しようとしてきました。^{[ 8 ]} CRC-12 には 3 つの多項式が報告されており、^{[ 11 ]} CRC-16 には 22 の矛盾する定義があり、CRC-32 には 7 つの定義があります。^{[ 12 ]}

一般的に使用されている多項式は、最も効率的なものではありません。1993 年以来、Koopman、Castagnoli らは、3 ビットから 64 ビットのサイズの多項式の空間を調査し、^{[ 11 ] [ 13 ] [ 14 ] [ 15 ]}以前のプロトコルの多項式よりもはるかに優れたパフォーマンス (特定のメッセージ サイズに対するハミング距離の観点から) を持つ例を見つけ、将来の標準のエラー検出能力を向上させる目的で、これらの最良のものを公表しました。^{[ 14 ]}特に、iSCSIとSCTP は、この研究の発見の 1 つです。CRC-32C (Castagnoli) 多項式です。

標準化団体で最も一般的に使用されている 32 ビット多項式 CRC-32-IEEE の設計は、ローマ研究所と空軍電子システム部門のために、ジョージア工科大学の Joseph Hammond、James Brown、Shyan-Shiang Liu、およびMitre Corporationの Kenneth Brayerが共同で取り組んだ結果である。32 ビット多項式が最初に登場したことが知られているのは、1975 年の出版物である。Mitre の Brayer による技術レポート 2956 は 1 月に発行され、8 月にDTICを通じて一般に公開された^{[ 16 ]} 、および Hammond、Brown、Liu によるローマ研究所のレポートは 5 月に発行された^{[ 17 ]}である。どちらのレポートにも、もう一方のチームからの貢献が含まれている。 1975 年 12 月、Brayer と Hammond は IEEE National Telecommunications Conference で論文を発表し、IEEE CRC-32 多項式はハミング符号の生成多項式であり、エラー検出性能に基づいて選択されたことを明らかにしました。^{[ 18 ]} それでも、iSCSI や SCTP で使用される Castagnoli CRC-32C 多項式は、58 ビットから 131 kbit までのメッセージでその性能に匹敵し、インターネット パケットの最も一般的な 2 つのサイズを含むいくつかのサイズ範囲でそれを上回ります。^{[ 14 ]} ITU -T G.hn標準もペイロードのエラー検出に CRC-32C を使用しています (ただし、PHY ヘッダーには CRC-16-CCITT を使用しています)。

CRC-32C 演算は、 SSE4.2命令セットの演算 ( CRC32)としてハードウェアで実装されており、これはIntelプロセッサのNehalemマイクロアーキテクチャで初めて導入されました。ARM AArch64アーキテクチャは、CRC-32 および CRC-32C 演算の両方に対してハードウェア アクセラレーションを提供します。

以下の表には、使用されているさまざまなアルゴリズムの多項式のみが記載されています。特定のプロトコルのバリエーションでは、上記のように、前倒し、後倒し、およびビット順序の反転を課すことができます。たとえば、GzipとBzip2で使用されるCRC-32は同じ多項式を使用しますが、Gzipはビット順序を反転させ、Bzip2は反転させません。^{[ 12 ]}次数が1より大きいGF(2) の偶数パリティ多項式は決して原始的ではないことに注意してください。この表で原始的とマークされている偶数パリティ多項式は、原始多項式にを乗じたものを表します。${\displaystyle \left(x+1\right)}$多項式の最上位ビットは常に1であり、16進数表現には表示されません。

• チェックサム
• 巡回冗長検査の計算
• 情報セキュリティ
• チェックサムアルゴリズムの一覧
• ハッシュ関数のリスト
• LRC
• 巡回冗長検査の数学
• 簡単なファイル検証

• ISO/IEC 13239:2002：情報技術－電気通信およびシステム間の情報交換－高レベルデータリンク制御（HDLC）手順
• CRC32-Castagnoli Linux ライブラリ