Chapter 09

巡回符号と CRC — 多項式の割り算による誤り検出

この章の位置づけ. CRC（Cyclic Redundancy Check、巡回冗長検査）は、Ethernet、Wi-Fi、USB、ZIP、PNG、SATA、CAN バスなど、データを送ったり保存したりする多くの場面で使われている誤り検出の方式である。 中身は、データを多項式と見なし、決められた多項式で割った余りを付けて送るというものである。04 章 2 節の多項式の割り算がそのまま使われる。

この章では、(1) 巡回符号という構造、(2) CRC の手順、(3) CRC で必ず検出できる誤りとできない誤り、(4) 実装、(5) CRC を改ざん検知に使ってはいけない理由を順に扱う。(3) は実務で誤解が多いので、証明を付ける。

この章で使う既出の用語（定義は各リンク先）. 多項式とビット列の対応・「標数 2 では引き算 = 足し算」（04 章 1 節）、多項式の除算と合同式\(\equiv \pmod f\)（04 章 2 節）、 因数・既約多項式・剰余の定理（04 章 3 節）、原始多項式と\(x\)の位数（04 章 4 節）、拡張ユークリッドの互除法（04 章 5 節）、 符号化・誤りのモデル（06 章）、線形符号・生成行列・シンドローム（07 章）。 7 節では、送信者と受信者だけが知る秘密の値である鍵という言葉を使う（詳しくは12 章 1 節）。

1. 巡回符号 — 「ずらしても符号語」という構造

定義

線形符号\(C\)で、どの符号語を巡回シフト（右端のビットを左端に回して、残りを 1 つ右にずらす）しても符号語になるものを巡回符号という:

多項式表現

符号語\((c_0,\dots,c_{n-1})\)を多項式\(c(x) = c_0 + c_1x + \cdots + c_{n-1}x^{n-1}\)と同一視する。\(c_i\)が\(x^i\)の係数で、この節ではベクトルの左端\(c_0\)が定数項である。 2 節以降の CRC では送信順に合わせて逆にし、04 章と同じくビット列の左端を最高次、右端を定数項とする。どちらも係数を並べたものであり、左右どちらから読むかの約束が違うだけである。

巡回シフトは「\(x\)を掛けて\(x^n+1\)で割った余り」になる。\(\mathrm{GF}(2)\)では\(-1 = 1\)なので\(x^n - 1\)と\(x^n + 1\)は同じ多項式であり、以下ではどちらの書き方も使う。

導出: \(x \cdot c(x) = c_0x + c_1x^2 + \cdots + c_{n-2}x^{n-1} + c_{n-1}x^{n}\)である。\(x^n = 1 \cdot (x^n + 1) + 1\)なので\(x^n \equiv 1 \pmod{x^n+1}\)であり、最高次の項\(c_{n-1}x^n\)は定数項\(c_{n-1}\)に置き換わる:

係数を並べると\((c_{n-1}, c_0, \dots, c_{n-2})\)で、1 つ巡回シフトしたものになっている ∎

ビット列を回すという操作が、\(x\)を掛けるという多項式の計算に置き換わった。これにより、多項式の割り算や因数分解の性質を符号の解析に使えるようになる。

生成多項式

定理: 0 だけでない長さ\(n\)の巡回符号\(C\)には、\(x^n + 1\)を割り切る多項式\(g(x)\)で

となるものがある。この\(g\)を生成多項式という。\(m\)は\(2^{n - \deg g}\)通りあるので\(k = n - \deg g\)、つまり\(\deg g = n-k\)は検査ビット数である。

方針: 0 でない符号語のうち次数が最小のものを\(g\)とする。まず「\(g\)の倍数を\(x^n+1\)で割った余りは符号語」という補題を示し、それを使って (i) \(g\)の倍数で次数\(n\)未満のものは符号語、(ii) 符号語はすべて\(g\)の倍数、(iii) \(g\)は\(x^n+1\)を割り切る、の 3 つを示す。

補題: 任意の多項式\(a\)について、\(a g\)を\(x^n + 1\)で割った余りは符号語である。 \(g\)に\(x\)を掛けて余りを取ると 1 回巡回シフトしたものなので符号語であり、繰り返せば\(x^j g \bmod (x^n+1)\)も符号語である。\(a g\)は\(a\)の 1 の項に対応する\(x^j g\)の和で、余りを取ってから足しても同じ（04 章 2 節）なので、符号語の和として符号語である。

(i) \(\deg(m g) < n\)なら\(x^n + 1\)で割った余りは\(m g\)自身なので、補題より\(m g\)は符号語である。

(ii) 符号語\(c\)を\(g\)で割って\(c = qg + r\)（\(r = 0\)または\(\deg r < \deg g\)）とする。\(\deg(qg) \leq \deg c < n\)なので (i) より\(qg\)は符号語であり、\(r = c + qg\)は符号語の和として符号語である。 \(g\)は 0 でない符号語のうち次数が最小だったので、\(\deg r < \deg g\)の符号語\(r\)は 0 しかない。よって\(c = qg\)。

(iii) \(x^n + 1\)を\(g\)で割って\(x^n + 1 = q'g + r'\)とする。この式から\(r' = q'g + (x^n + 1)\)なので、\(r'\)は\(q'g\)を\(x^n+1\)で割った余りに等しく（\(\deg r' < \deg g < n\)）、補題より符号語である。(ii) と同じ理由で\(r' = 0\)、すなわち\(g\)は\(x^n+1\)を割り切る ∎

例: \(x^7 + 1 = (x+1)(x^3+x+1)(x^3+x^2+1)\)なので、\(g = x^3+x+1\)は長さ 7 の巡回符号\((7, 4)\)を生成する。これは08 章のハミング符号とビットの並べ方が違うだけの符号で、ハミング符号は巡回符号としても作れる。

巡回符号が実装に有利な理由: 生成行列\(G\)（\(k \times n\)個の成分）を持つ代わりに、\(n - k + 1\)ビットの生成多項式\(g\)を 1 本持てばよい。 符号化も検査も多項式の割り算なので、シフトレジスタと XOR で実装でき、ハードウェアでは少ないゲートで作れる（6 節）。

2. CRC の手順

CRC は、データの後ろに「\(g\)で割った余り」を付けて、全体を\(g\)の倍数にする方式である。符号語は\(g\)の倍数全体（ただし長さ\(n\)以下）なので 1 節の (i) (ii) と同じ形の線形符号になる。 実際の CRC は\(g\)が\(x^n + 1\)を割り切るように\(n\)を選ぶとは限らない（データ長は自由に変わる）ので、厳密には巡回符号を途中で切った短縮巡回符号である。割り算で検査するという仕組みはそのまま使える。

符号化（送信側）

データを\(k\)ビット、生成多項式\(g(x)\)の次数を\(r = n-k\)とする。この章の\(r\)は次数を表し、余りの多項式は大文字\(R(x)\)で書く。

1. データのビット列を多項式\(m(x)\)と見なす。
2. \(x^r\)を掛ける。ビット列では、データの後ろに 0 を\(r\)個並べることに当たる。
3. \(x^r m(x)\)を\(g(x)\)で割った余り\(R(x)\)を求める。\(\deg R < r\)なので、\(R\)は\(r\)ビットで書ける。
4. 送信する符号語を\(T(x) = x^r m(x) + R(x)\)とする。ビット列では、データの後ろに余りの\(r\)ビットを付けたものである。

T は必ず g で割り切れる

割り算の結果を\(x^r m(x) = q(x)g(x) + R(x)\)と書くと

\(\mathrm{GF}(2)\)では\(R + R = 0\)だからである。よって\(T(x)\)は\(g(x)\)で割り切れる ∎

整数なら割り切れる形にするには余りを引く必要があるが、\(\mathrm{GF}(2)\)では引き算と足し算が同じなので、余りをそのまま後ろに付けるだけで済む。

検査（受信側）

受信語\(T'(x)\)を\(g(x)\)で割り、余りが 0 なら誤り無し、0 でなければ誤り有りと判定する。 誤りパターン（反転した位置に 1 が立ったビット列）を\(E(x)\)として\(T'(x) = T(x) + E(x)\)と書くと、\(T\)は\(g\)で割り切れるので

である。07 章 4 節のシンドロームと同じく、余りは送ったデータによらず、誤りパターンだけで決まる。したがって

であり、どんな誤りを検出できるかは、どんな\(E(x)\)が\(g(x)\)で割り切れるかという問題になる。4 節でこれを調べる。

3. 手計算の実例

ビット列は左端が最高次の係数である。筆算は04 章 2 節と同じで、先頭が 1 の段では除数より小さく見えても XOR し、下ろす桁が無くなったら終わる。

データ: 1101、つまり\(m(x) = x^3+x^2+1\)。生成多項式: \(g(x) = x^3 + x + 1\)、ビット列1011（\(r = 3\)）。

ステップ 1: データの後ろに 0 を 3 個並べて1101000（\(x^3m(x) = x^6+x^5+x^3\)）。

ステップ 2: 1101000を1011で割る。

余りは\(R = 001\)（\(R(x) = 1\)）である。

ステップ 3: データの後ろに余りを付けて、送信符号語は1101 + 001 = 1101001。

検算: 1101001を1011で割ると余りが 0 になる。

誤りを入れてみる: 左から 3 ビット目が反転して1111001を受信したとする。

余りが110で 0 でないので、誤りが検出される。2 節のとおり、この余りは誤りパターン0010000（\(x^4\)）を1011で割った余り\(x^4 \bmod g = x^2 + x\)に等しい。

4. CRC の検出能力（実務で最も重要な節）

\(g(x)\)の次数を\(r\)とする。以下ではいずれも「\(E(x)\)が\(g(x)\)の倍数にならない」ことを示す。 まず、何度も使う補題を示しておく。

補題: \(g\)の定数項が 1 なら、\(g\)が\(x^i A(x)\)を割り切るとき、\(g\)は\(A(x)\)を割り切る。

導出: 定数項が 1 なので\(g\)は\(x\)で割り切れず（04 章 3 節）、\(x\)は既約なので\(\gcd(g, x^i) = 1\)である。拡張ユークリッドの互除法（04 章 5 節）より\(u g + v x^i = 1\)となる\(u, v\)があり、両辺に\(A\)を掛けると\(A = uAg + v\,x^iA\)。右辺の 2 項はどちらも\(g\)で割り切れるので、\(A\)も割り切れる ∎

実用の生成多項式はどれも定数項が 1 なので、以下ではそれを仮定する。

(a) すべての 1 ビット誤り

1 ビット誤りは\(E(x) = x^i\)である。\(g\)が\(x^i\)を割り切るとすると、補題（\(A = 1\)）より\(g\)は 1 を割り切ることになるが、\(\deg g = r \geq 1\)なのでありえない。

→ 1 ビット誤りは必ず検出される。

(b) すべての 2 ビット誤り

\(E(x) = x^i + x^j = x^i(1 + x^{j-i})\)（\(i<j\)）である。補題より、\(g\)が\(E\)を割り切るなら\(g\)は\(1 + x^{j-i}\)を割り切る。

\(g\)が\(1+x^L\)を割り切る最小の正整数\(L\)を\(g\)の周期という。\(g\)が\(1 + x^L\)を割り切ることは\(x^L \equiv 1 \pmod g\)と同じなので、周期は\(g\)を法とする\(x\)の位数（04 章 4 節）である。 \(x^a \equiv 1\)となる\(a\)は周期\(L\)の倍数に限る（03 章 3 節の段階 2 と同じ議論）ので、\(0 < j - i < L\)なら\(g\)は\(1 + x^{j-i}\)を割り切らない。 符号語の長さを\(n\)とすると\(j - i \leq n - 1\)なので、\(n \leq L\)ならすべての 2 ビット誤りを検出できる。

周期の値:

• \(g\)が次数\(r\)の原始多項式なら、定義より\(L = 2^r - 1\)である。CRC-32 の多項式は原始多項式で、\(L = 2^{32}-1 \approx 4.3 \times 10^9\)ビット（約 512 MB）まで 2 ビット誤りを必ず検出する。
• \(g = (x+1)p(x)\)で\(p\)が次数\(r-1\)の原始多項式なら、\(x^L \equiv 1\)を\(x+1\)と\(p\)の両方で満たす最小の\(L\)なので\(L = 2^{r-1} - 1\)である。CRC-16 の 2 種類はこの形で、\(L = 32767\)ビットまで検出する。

(c) すべての奇数個の誤り

定理: \(g(x)\)が\(x+1\)を因数に持つなら、奇数個のビット誤りを必ず検出する。

方針: 奇数個の項を持つ\(E\)は\(x+1\)で割り切れないことを、04 章 3 節の判定（項の個数が偶数 ⇔ \(x+1\)で割り切れる）で示す。\(g\)が\(x+1\)の倍数なら、\(g\)の倍数もすべて\(x+1\)の倍数である。

導出: \(E\)の項の個数が奇数なら、04 章の判定より\(E\)は\(x+1\)で割り切れない。一方\(g = (x+1)h\)なので、\(E\)が\(g\)の倍数\(E = gq\)なら\(E = (x+1)(hq)\)は\(x+1\)で割り切れる。矛盾するので\(E\)は\(g\)の倍数でない ∎

→ \(g\)が\(x+1\)を因数に持てば、奇数個の誤りはすべて検出される。

5 節の表のうち CRC-8、CRC-16 の 2 種類、CRC-32C、CRC-64 は\(x+1\)を因数に持つ。CRC-32（Ethernet などで使う 0x04C11DB7）は既約多項式なので\(x+1\)を因数に持たず、奇数個の誤りの検出は保証されない。その代わり原始多項式なので、(b) の 2 ビット誤りを非常に長い符号語まで保証する。

(d) 長さ r 以下のバースト誤り

バースト誤りとは、連続する区間の中で起きる誤りである。区間の長さ\(b\)は最初の誤りから最後の誤りまでを数えるので、両端は必ず誤りで、中は誤っていてもいなくてもよい。長さ\(b\)のバーストは

と書ける。\(x^i\)がバーストの位置を表し、\(B\)は両端が誤りなので最高次\(x^{b-1}\)と定数項の係数が 1、\(\deg B = b - 1\)である。

\(b \leq r\)のとき: 補題より、\(g\)が\(E\)を割り切るなら\(g\)は\(B\)を割り切る。ところが\(B \neq 0\)で\(\deg B = b-1 < r = \deg g\)なので、\(g\)は\(B\)を割り切れない。よって\(E\)は\(g\)の倍数でない ∎

→ 長さ\(r\)以下のバースト誤りはすべて検出される。

これが CRC の最大の強みである。実際の通信では、各ビットが独立に誤るより、電気的なノイズやディスクの傷、無線の電波の落ち込みで連続した数ビットがまとめて壊れることが多い。CRC-32 なら長さ 32 ビット以下のバーストはすべて検出される。

(e) 長さ r+1 以上のバースト

バーストの中間のビットがランダムに誤るとすると、見逃す確率は次のようになる。

• 長さ\(r+1\): \(\deg B = r = \deg g\)なので、\(g\)が\(B\)を割り切るのは\(B = g\)のときだけである。\(B\)の両端は 1 に固定で、中間の\(r - 1\)ビットは\(2^{r-1}\)通りあり、そのうち\(g\)と一致する 1 通りだけを見逃す。見逃す確率は\(2^{-(r-1)}\)。
• 長さ\(r+2\)以上: \(B\)を\(g\)で割った余りは\(r\)ビットで、中間のビットがランダムなら余りも\(2^r\)通りにほぼ均等に散らばる。見逃すのは余りが 0 のときだけなので、見逃す確率はおよそ\(2^{-r}\)。

CRC-32 なら長いバーストの見逃し確率は約\(2^{-32} \approx 2.3\times10^{-10}\)である。

まとめ表

5. 標準的な CRC の仕様

生成多項式は、最高次\(x^r\)の係数（必ず 1）を省いた下位\(r\)ビットを 16 進で書くのが慣例である。たとえば CRC-32 の 0x04C11DB7 は、04 章で最高次まで含めて書いた 0x104C11DB7 と同じ多項式である。

実装パラメータ（ここが実務のハマりどころ）

同じ「CRC-32」でも、次の 5 つのパラメータが違うと値が一致しない。

init が必要な理由: 初期値 0 の素朴な CRC では、データの先頭に 0 が何個付いても余りが変わらない。多項式として先頭の 0 は係数 0 の高次の項で、何も足していないのと同じだからである。つまり0x1234と0x00001234が同じ CRC になる。 通信では同期がずれて 0 のバイトが余分に入ったり抜けたりする事故が実際に起き、これを検出したい。init を全 1 にすると、先頭の 0 を処理するたびにレジスタの中身が変わるので、0 の個数が CRC に反映される。

xorout が必要な理由: 末尾側にも似た問題がある。余りがたまたま 0 のデータに 0 を付け足しても、\(g\)の倍数に\(x\)を掛けたものはやはり\(g\)の倍数なので、余りは 0 のままで末尾の 0 の増減が見えない。最後に全 1 を XOR しておくと、送る検査値が余りそのものではなくなり、この一致が起きなくなる。

教科書どおりの割り算だけで実装すると、既存のシステムと値が合わない。実装するときはこの 5 つのパラメータを必ず確認する。

6. 実装

ビットごと（教科書的、遅いが分かりやすい）

C 言語で書く。記号の意味: ^ は XOR、<</>> は左/右シフト、& はビットごとの AND、data[i] は\(i\)番目の入力バイト、? : は「条件 ? 真のとき : 偽のとき」。

uint32_t crc32_bitwise(const uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;              // init
    for (size_t i = 0; i < len; i++) {
        crc ^= (uint32_t)data[i] << 24;     // 上位バイトに入力
        for (int b = 0; b < 8; b++) {
            crc = (crc & 0x80000000)
                ? (crc << 1) ^ 0x04C11DB7   // 最上位が 1 なら poly を XOR
                : (crc << 1);
        }
    }
    return crc ^ 0xFFFFFFFF;                // xorout
}

これは 3 節の筆算そのものである。レジスタの最上位ビットが 1 なら生成多項式を XOR して次数を下げる、という操作を 1 ビットずつ行っている。左シフトで 32 ビットのレジスタからあふれた最上位の 1 が、筆算で消した先頭の項に当たる。 0x04C11DB7 は 5 節のとおり最高次\(x^{32}\)を省いた表記なので、あふれた 1 と合わせて\(g\)全体を XOR したことになる。

ただしこのコードはビット順を反転しない形（refin/refout = false）なので、返る値は CRC-32/BZIP2 と呼ばれる変種になる。 Ethernet・ZIP・PNG の CRC-32（refin/refout = true）は、各バイトのビット順を逆にして処理する。 ビット順を逆にすると「最上位」が「最下位」に、「左シフト」が「右シフト」に、多項式もビット順を逆にした 0xEDB88320 になり、次のように書ける:

uint32_t crc32_ethernet(const uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;              // init
    for (size_t i = 0; i < len; i++) {
        crc ^= data[i];                     // 下位バイトに入力（ビット順反転済みとみなす）
        for (int b = 0; b < 8; b++) {
            crc = (crc & 1)
                ? (crc >> 1) ^ 0xEDB88320   // 最下位が 1 なら反転 poly を XOR
                : (crc >> 1);
        }
    }
    return crc ^ 0xFFFFFFFF;                // xorout
}

2 つは同じ割り算をビットの並べ方だけ変えて行っており、"123456789" に対して前者は 0xFC891918、後者は 0xCBF43926 を返す。

テーブル駆動（実用の定番）

1 バイト分（8 回のシフト）の結果を、上位バイトの値 256 通りについて事前に計算して表にしておく:

uint32_t table[256];
void make_table(void) {
    for (int i = 0; i < 256; i++) {
        uint32_t c = (uint32_t)i << 24;
        for (int b = 0; b < 8; b++)
            c = (c & 0x80000000) ? (c << 1) ^ 0x04C11DB7 : (c << 1);
        table[i] = c;
    }
}

uint32_t crc32_table(const uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;
    for (size_t i = 0; i < len; i++)
        crc = (crc << 8) ^ table[((crc >> 24) ^ data[i]) & 0xFF];
    return crc ^ 0xFFFFFFFF;
}

なぜ表にできるのか: init と xorout を 0 にした素の CRC は線形で、同じ長さのデータ\(a, b\)について\(\mathrm{CRC}(a \oplus b) = \mathrm{CRC}(a)\oplus\mathrm{CRC}(b)\)を満たす。余りを取る操作が\((a + b) \bmod g = (a \bmod g) + (b \bmod g)\)を満たすからである。 1 バイト処理するとき、8 回のシフトの間に XOR されるものは「レジスタの上位バイトと入力バイトの XOR」の 8 ビットだけで決まる。線形なので、その 8 ビットの 256 通りについて結果を表にしておけば、ビットごとのループ 8 回の代わりに表引き 1 回で済む。

ハードウェア命令

• CRC-32C: Intel/AMD の CRC32 命令、ARM の CRC32C 系命令で計算できる
• 任意の poly: キャリーレス乗算の命令 PCLMULQDQ（04 章 1 節）を使うと、毎秒数 GB の速度で計算できる

7. CRC の限界 — 「改ざん検知」には使えない

CRC は偶然に起きた誤りを検出するためのもので、悪意のある改ざんは防げない。理由は 2 つある。

(1) 線形性: 6 節のとおり、同じ長さのデータ\(a, b\)について、init と xorout を 0 にした素の CRC は\(\mathrm{CRC}(a \oplus b) = \mathrm{CRC}(a)\oplus\mathrm{CRC}(b)\)を満たす。init と xorout があっても、変化分だけを見れば

となり、右辺は\(m\)を含まない。攻撃者が元のデータ\(m\)の一部を\(\Delta\)の位置だけ反転して\(m \oplus \Delta\)に書き換えるとき、\(m\)の中身を知らなくても、自分が加えた変更\(\Delta\)だけから CRC の変化分を計算し、元の CRC に XOR して辻褄を合わせられる。

(2) 鍵が無い: 生成多項式は公開された仕様なので、誰でも正しい CRC を計算できる。攻撃者の知らない秘密の値（鍵）が計算に入っていない。

改ざんを検知するには、18 章の暗号学的ハッシュ関数（SHA-256 など）や、鍵を使う MAC（HMAC など）を使う。「チェックサムが合っているから改ざんされていない」とは言えない。

歴史的な事故: 無線 LAN の旧規格 WEP は、データに CRC-32 を付けてから、RC4 というストリーム暗号で暗号化していた。RC4 は鍵から作ったビット列を平文に XOR するだけの方式である（13 章）。 暗号化が XOR なので、暗号文のビットを反転すると、復号した平文の同じビットが反転する。CRC も (1) のとおり XOR について線形なので、反転に応じた CRC の変化分も暗号文に XOR で足し込める。 この 2 つが組み合わさって、暗号文のまま任意のビットを改ざんし、CRC まで合わせることができた。これが WEP が破られた原因の 1 つである。

8. まとめ

CRC は検出に特化していた。同じ巡回符号の枠組みで訂正までできるように設計したのが、次章の BCH 符号である。 鍵になるのは、生成多項式の根を有限体\(\mathrm{GF}(2^m)\)の中で指定するという考え方で、05 章で作った拡大体がここで使われる。