CRC(巡回冗長検査) - CTFと共に生きる

どうも。duckです。
巡回冗長検査書くよ。
理論は難しくないですが、実装に癖がありまする。

理論編

概要
巡回冗長検査（巡回冗長検査 - Wikipedia）とは、誤り検出の手法の一つ。
データ送信の際にデータの破損（ビット欠落など）が起こっていないかの判定に用いる。割り算をする際の多項式（生成多項式という）の次数によってcrc-32,crc-64などと呼ばれる。生成多項式は誤り検出しやすいものを使う。(wikipedia参照、標準と反転があるが後述)
もっとも単純な誤り検出の方法としては、同じbit列を二回送信するなどがある。今回の巡回冗長検査はそれよりかは高度。

理論
一言で言うならば、二進数係数多項式（生成多項式）の割り算のあまりが巡回冗長検査。

・定義（例）
bitと二進数多項式の対応
bitを $b$ としたとき多項式は $f_b$ としてあらわす。例を見ると早い。
m=1011000なら
$f_m=1*x^6 + 0 * x^5 + 1 * x^4 + 1 * x^3 + 0* x^2+ 0*x + 0=x^6+x^4+x^3$
c=11なら
$f_c=1*x+1=x+1$

・crc計算手順
送信するメッセージをm、生成多項式をgとおく。このとき以下の手順でcrcの計算をする。
１． $g$ の(bit数-1)だけ、mの後ろに0を詰め込む。これをm'とおく。
２． $f_m'$ を求める。
３． $f_m'$ を $f_g$ で割ったあまりのbit表現がcrc。

例
m=1011010,g=10011とする。
１．m'=10110100000
２． $f_m'=x^{10}+x^8+x^7+x^5$
３． $f_g=x^4+x+1$ であり、 $f_m'$ を $f_g$ で割ったあまりを計算すると
$f_{crc}=x^3+x^2+x+1$ 。よってcrc=1111

・巡回冗長検査手順
１．[送信側]m'+crcを送信する
２．[受信側]m'+crcをgで割り算し、0になればビット誤りがないと判断する

理由
$f_m'=P*f_g+f_{crc}$
$f_m'-f_{crc}=P*f_g$
$f_m'+f_{crc}=P*f_g$ (係数がGF(2)のため $1=-1$ )より、 $f_{m'+crc}$ は必ず $f_g$ で割り切れる。

もし送られてきた $m'$ に誤りがあれば、割り算の結果が0にならず、受信側は誤りに気が付ける。

実装編

・素朴な実装
これ素朴にpythonで実装したの私が初めて説まである。多倍長整数と絶望的に相性が悪い。
わかりやすさのため（？）冗長に書いてある。一般的に使われてる実装は後述。

#input int
def crc4(m,receive = False):
    keta = len(bin(m)) + 2
    g = 0b10011 << (keta - 5)
    if not receive:
        crc = m << 4
    else:
        crc = m
    mask = 1
    for i in range(keta - 1):
        mask |= (mask << 1)
    for i in range(keta - 4):
        if crc & 2 ** (keta - 1):
            crc = crc ^ g
            crc = crc << 1
            crc &= mask
        else:
            crc = crc << 1
            crc &= mask
    return crc >> (keta - 4)

receive=Trueとすると、受信時の設定でかいた。
実行例

#送信
print(bin(crc4(0b1011011)))
0b1100
#受信
print(bin(crc4(0b10110111100,True)))
0b0

うまくいってる。

しかしコードの説明がうまくできないので図を載せておく。（わかるとはいっていない）
コードと図の対応を説明する。
コードのketaは図の赤い四角=crcと書いてある部分のbit数に対応。
コードのgは図のgに対応。
コードのmaskはketaのbit数分1を並べた数字で、crcのサイズを固定するのに使用。
2**(keta - 1)は先頭が1で他は0でketa数分のbitをもつ数。

f:id:falconctf:20191025080006j:plain — 説明的な何か

こんなん自分で割り算やってみないとわからんて。（丸投げ）

・反転実装
pythonではこっちが主流なはず。実装の難易度が違いすぎるから。
多項式の読み方を逆にする。（次数が大きい項が右端になる。）
gは適した固定の多項式を使いたい事情がある。(Wikipediaみて)
例
m=1011010,g=11001(上の例の多項式と同じ)とする。
１．m'=00001011010
２． $f_m'=x^9+x^7+x^6+x^4$
３． $f_g=x^4+x+1$ であり、 $f_m'$ を $f_g$ で割ったあまりを計算すると
$f_{crc}=x^3+x^2+x$ 。よってcrc=0111

これをコードに落とす。~~三項演算子使えとか言わない。上の例でもやめといたし。~~

def crc4_reverse(m):
    keta = len(bin(m)) + 2
    g = 0b11001
    crc = m
    for i in range(keta - 4):
        if crc & 1:
            crc = crc ^ g
            crc = crc >> 1
        else:
            crc = crc >> 1
    return crc

receiveの設定しなくてもいいしサイコーですね。

f:id:falconctf:20191026074113j:plain — 適当な画像

実行例

#送信
print(bin(crc4_reverse(0b1011010)))
0b111
#受信 crcのつける場所が前になることに注意
print(bin(crc4_reverse(0b01111011010)))
0b0

Wikipediaに標準と反転の生成多項式のbit表現がわざわざかいてあるけど、つまるところ同じ多項式。

高速化

・gの先頭の1は実はいらない
割られる数に1が立っているかの判定だけでよいため。

crc & 2 ** (keta - 1)
や
crc & 1

で事足りる。どうせxorした結果の先頭は0になってるからね。
wikipediaは最初から先頭の１をはしょった形で書かれてる。

・8bit分の割り算を先にしてテーブル化しておく
前回の記事で思いついたけど実装しなかったって言ってたやつ。
いやあ標準的に使われてるのねさすがです。
これも反転のほうが有利だね。標準だと固定長がmによって変わるから、mの長さがわかってからじゃないとテーブル計算ができない。

wikipediaにあわせてcrc32_reverseの例だけ図に起こした。
今まで例で使ってたcrc4_reverseでも同じ作業できる。

f:id:falconctf:20191026080943j:plain — テーブル利用crc32_reverse

・謎
wikipedia見ればわかるがなぜかcrc32のときは
初期値をcrc=0xffffffffとしcrc^0xffffffffをreturnする風潮がある。
考えたけど意味は不明だった。

ちなみに私の実装例はすべてcrc=0を初期値としている実装である。
まあそういこともあるんだと思っておく。

2019/10/27　追記

ググったらそれらしい理由があった
0固定故障への対策らしいhttps://t.co/Hzel27DQhx
— 道路 (@Nperair) October 25, 2019

有力情報を頂いた。リンク先を見ると、全部0になるバグ？の判定ができるためだそう。

参考：Cyclic Redundancy Check(CRC)を理解する - Qiita
　　　巡回冗長検査 - Wikipedia

正直後半書くの飽きてた。4日くらいかいてるからなこれ。