巡回冗長検査
ファイルの完全性検査などにはSHA256やMD5が使われますが、短いテキストのようなデータの場合、SHA256やMD5は結果が長すぎて使いにくいことがあります。
その点、CRC32は結果が32bitで、16進数表記でも8文字で済むため、元のテキストの代替として使うのに簡便です。
しかし、CRC32と一口に言っても実はいくつかの方式があり、異なる値を算出します。
CRC32の種類
前掲のWikipediaのページを見ても、32bitのCRCには(厳密にはCRCでないAdler32も含めて)
- CRC-32Adler (厳密にはCRCではないがよく混同される)
- CRC-32
- CRC-32C
- CRC-32K
の4種類が掲載されています。CRC-32Adlerは計算方法が全く異なりますが、それ以外の3つは、Wikipedia記事中では生成多項式と呼んでいる定数が異なるのみです。
手軽なツールの利用(とその罠)
MD5やSHA256などの値は、元の値から完全に決定されるので、オンラインツールが多く存在しており、元の値に機密性がないならこういったツールを利用できます。
そうしてたまたま以下のようなサイト
で生成した crc32 の値を持ってくると、例えば hoge はこのようになります
- bfotool.com:
Crc32: 4b775151 Crc32b: 8b39e45a -
www.paulschou.com:
crc32: 4b775151 crc32b: 8b39e45a
crc32 と crc32b があることを気にせずに crc32 を使うこともあると思います。
ただ、同じ計算をほかのサイトでしてみるとちょっとおかしいことに気づきます。
「おかしい」というのは、「(このサイトを使う以外の)ほかの方法で再現方法がわからない」という意味で言っています。後述するようにこの結果は標準化された方法に基づいて算出されており、巡回冗長検査を目的とした結果としては変な結果ではありません。また、このような値を算出するのは(筆者が調べた限り)珍しいかもしれませんが、PHPをバックエンドの言語・ランタイムとして利用していれば自然だといえます。
例えば以下のサイトで計算すると計算結果は crc32b の結果(8b39e45a)になります。
また、例えばJavaの CRC32 や Goの hash/crc32 パッケージを使って計算しても同じ結果になります。
ちなみにGoの場合は、Wikipediaにあった CRC-32Adler (hash/adler32パッケージを利用))、CRC-32C、CRC-32K のすべてが実装されていますがいずれで計算しても上記 crc32 の結果とは一致しません)
では先ほどの crc32 の結果は何だったのでしょうか？
深まる謎
crc32 や crc32b で調べると、どうもPHPに hash という関数があり、その引数としてハッシュアルゴリズムを指定するときの引数で crc32/crc32b という指定があるようです。
気づくのが遅かったのは筆者がPHP経験ゼロのためです
そしてこれらの違いは利用者にとっても不思議なもののようで、StackOverflowにも質問されていました。
ただ、回答は「それぞれ別のアルゴリズムだよ。詳細はそれぞれの標準を見に行ってね。」(意訳)といったもので、実用上はそれで困らないものの、何がどう違うのか(例えば生成多項式がどう違うのか)といったことは分かりませんでした。
この時点でPHPを使えば結果を再現できることは分かったものの、PHP経験ゼロの筆者としては「自分の使える道具立てで再現したい」と考え、調査を続行しました。
ヒント
ヒントになったのは以下のサイトの計算結果でした。
CRC-32 という結果のほかに CRC-32/BZIP2 という行があり、入力 hoge に対して 0x5151774B という結果が出ています。バイト順序こそ逆ですが 4b775151 が出力されていたのです。
このサイトはアルゴリズムの違ういろいろなCRC32を計算してくれており、その詳細についても表形式でまとまっています。
CRC-32と CRC-32/BZIP2を取り出してみると(resultなどの列は入力 hoge に対するもの)
| Algorithm | Result | Check | Poly | Init | RefIn | RefOut | XorOut |
|---|---|---|---|---|---|---|---|
| CRC-32 | 0x8B39E45A | 0xCBF43926 | 0x04C11DB7 | 0xFFFFFFFF | true | true | 0xFFFFFFFF |
| CRC-32/BZIP2 | 0x5151774B | 0xFC891918 | 0x04C11DB7 | 0xFFFFFFFF | false | false | 0xFFFFFFFF |
となっていて、RefIn/RefOut が異なるのみのようです。
解決編
眠い目をこすりながら crc refin で検索して次のページにたどり着きました。
Google翻訳を使いながら読んでいくと、どうもGitHubに具体的なコードがあるようです。
crc32 と crc32_mpeg_2 という関数が上記コードの最下部にあり、これらがそれぞれPHPの crc32 と crc32b (のバイト順序が逆のもの)に相当するようです。
当該Webサイトがアクセスできなくなったあとも結果を再現できれば良い(←今決めた)のでGoでコードを書き直しておきます。
func crc32(b []byte) uint32 {
var crc uint32 = 0xffffffff
for _, c := range in {
crc = crc ^ ((uint32)(c) << 24)
for i := 0; i < 8; i++ {
if crc & 0x80000000 != 0 {
crc = (crc << 1) ^ 0x04C11DB7
} else {
crc = (crc << 1)
}
}
}
return 0xffffffff ^ crc
}
func crc32b(in []byte) uint32 {
var crc uint32 = 0xffffffff
for _, c := range in {
crc = crc ^ (uint32)(c)
for i := 0; i < 8; i++ {
if crc & 0x1 != 0 {
crc = (crc >> 1) ^ 0xEDB88320
} else {
crc = (crc >> 1)
}
}
}
return 0xffffffff ^ crc
}
基本はこれで crc32(...) を使えばPHPの hash("crc32", ...) 相当、 crc32b(...) を使えば hash("crc32b", ...) 相当の結果が得られます。
なお、前述の通りPHPの crc32 の結果はバイト順序が逆になっているので、これを逆にするには encoding/binary パッケージのバイト順序関数を使って
import (
"encoding/binary"
"fmt"
)
func main() {
var b []byte = ([]byte)("hoge") // 入力
// PHPのhash("crc32", ...) 関数に合わせるためにLittleEndianを使ってバイト順序を逆にしている
fmt.Printf("crc32: %08X\n", binary.LittleEndian.AppendUvarint([]byte{}, crc32(b))
}
のようにすればよい。もしバイト配列ではなく uint32 が欲しければ binary.BigEndian.Uint32([]byte) uint32 で戻せばよい(この時はBigEndianにしておかないと順序が戻ってしまう)。
最後に
巡回冗長検査というのは抽象的な方式に名前が付けられているだけで、具体的なアルゴリズムではないことが分かった。
また、PHPのhash関数のような変種についてWikipediaにも
誤り検出符号としてのCRCの概念を実用システムでの実装に移すとき、実装者がそれを複雑化させることがある。以下では、そのような例を解説する。
(中略)
- ビット順序: ある種の方式では各バイトの最下位ビットを先頭とする。すると多項式除算での「左端」は通常の意味での最下位ビットになる。これはシリアルポートでの転送でハードウェアによるCRCチェックを行う場合に良く見られる。というのも、シリアルポートでは最下位ビットを先に転送するものが多いためである。
- バイト順序: 多バイトCRCでは、バイトの転送順序に混乱が見られる。一部の16ビットCRCではCRCを構成する2バイトを入れ替えている。
という形で記載があった。