crc - トリッキーな CRC アルゴリズム

Question

次の結果で機能するcrcを見つけようとしています。バイト文字列は 2 バイト (つまり 0xCE1E) で構成され、crc は 1 バイト (つまり 0x03) です。

バイトcrc
CE1E 03
CE20 45
CE22 6F
0000 C0
0001 D4
FFFF95

誰でも助けることができますか？

Answer 1

まず、16 進数の 4 桁は 4 バイトではありません。あなたのすべての例は4桁の16進数（2バイト）を示しているので、2バイトを意味すると仮定します。

ハッシュ値は 65,536 個しかないので、次のようにします。

0000 から FFFF までの 65,536 個の値すべてに対してハッシュ関数を実行します。結果を表にします。そのテーブルが関数です。入力値を出力値にマッピングします。

不器用ですが、常に正しく、それほど大きくなく (65K バイト)、計算後は非常に高速です。

ハッシュ関数を簡単にリバース エンジニアリングすることはできません。優れたものは、すべての入力ビットを何らかの「公平な」方法で使用する洗練されたステート マシンであり、数ビットだけ異なる入力値に対して出力値が劇的に異なるものです。

0000 を 0001、0002、0004、0008、0010、0020、0040、0080、0100、0200、0400、0800、1000、2000、4000、8000 と比較すると、各ビットがハッシュ。しかし、私はそれを疑います。

Answer 2

それらが 2 バイト (16 ビット) の値であると仮定して、いくつかのオンライン CRC ジェネレーターでいくつか試してみましたが、結果は得られませんでした。そのため、一般的に使用されている CRC アルゴリズムではないようです。

可能性の高いアルゴリズムについての手がかりはありますか? または、これは宿題で、CRC アルゴリズム/パラメーターをリバース エンジニアリングすることになっていますか?

要約: より多くの情報が必要です。

Answer 3

加算と減算が XOR に置き換えられることを除いて、小学校で手書きの除算を学ぶのと同じように、CRC は単純な除算です。したがって、次の方程式を GF(2) で解く必要があります。

CE1E % p = 03
CE20 % p = 45
CE22 % p = 6F
0000 % p = C0
0001 % p = D4
FFFF % p = 95

0000%p = c0 となる多項式 p はありません。(0 modulo p は、p のすべての値に対して 0 です。) したがって、おそらく (x+input) % p = crc です。あなたの場合、x は c0 でなければなりません。そうであれば、(x+0001)%p は c1 に違いありません。CRCではないようです。あなたが決心していて、答えが線形であると信じている場合は、可逆な0と1の行列を作成し、行列時間入力=出力から生じる一連の方程式を解きます。ただし、より多くの入力が必要になります。

Answer 4

http://www.geocities.com/SiliconValley/Pines/8659/crc.htm#r2

経験の浅い私の目には、一般的な crc アルゴリズムを実装し、いくつかのポリゴンで試してみる必要があるように見えます (その記事で言及されている「人気のある」ものを最初に試してください)。

編集：さらに読んだ後、逆ポリゴンも考慮する必要があるようです。