0

問題

行ごとに 1 つの文字列を含むテキスト ファイルがあります (改行 \r\n)。このファイルは、2 つの異なる方法で CRC16 を使用して保護されています。

  1. 4096 バイトのブロックの CRC16
  2. 32768 バイトのブロックの CRC16

ここで、これらの 4096 バイト ブロックのいずれかを変更する必要があるため、(ブロック)

  • 特定の文字列を含む
  • テキストファイルのサイズを変更しません
  • 元のブロックと同じ CRC 値を持つ (この 4k ブロックを含む 32k ブロックも同じ)

その制限を除いて、ファイル自体がそのフォーマットを壊さない限り、ブロックを満たすために必要な変更をブロックに加えることができます。最後のブロックではなく、完全に満たされた 4k ブロックのいずれかを使用するのが最善だと思います。

質問

その問題を解決するにはどうすればよいですか？私が思いつく最初のことは、ある種のブルートフォースですが、両方のCRC値が同じままになる変更を見つけるのに非常に時間がかかりませんか? おそらくそれを解決する数学的な方法はありますか？

数秒または最大で実行する必要があります。数分。

4

2 に答える 2

1

これを解決する数学的な方法がありますが、私はそれらを知りません。私はブルートフォースソリューションを提案しています：

ブロックは次のようになります。

SSSSSSSMMMMEEEEEEE

各文字はバイトを表します。S = 開始バイト、M = 変更可能なバイト、E = 終了バイト。

各バイトが CRC に追加されると、新しい内部状態になります。変更した位置までのチェックサム状態を再利用できます。変更されたバイトとそれに続くすべてのバイトのチェックサムを再計算するだけで済みます。Sそのため、 -partの CRC を 1 回だけ計算します。

次のバイトも再計算する必要はありません。変更後にCRCの状態が同じか異なるかを確認するだけです。同じであれば、ブロック全体も同じになります。異なる場合は、ブロック全体が異なる可能性があります (保証されていませんが、試行を中止する必要があります)。S+M'そのため、その部分だけの CRC を計算します(M'変更されたバイトです)。CRC(S+M)それがあなたの勝利の状態に等しい場合。

そうすれば、通過するデータがはるかに少なくなり、最近のデスクトップまたはサーバー2^32で必要な試行を数分で実行できます. 並列処理を使用します。

于 2013-09-02T10:03:02.023 に答える
0

spoof.cを見てください。これにより、4K ブロックの CRC の問題が直接解決されます。ただし、4K ブロックの CRC とそれを囲む 32K ブロックの CRC の両方の問題を同時に解決するには、コードを変更する必要があります。解くには方程式を追加するだけです。コードは非常に高速で、O(log( n )) 時間で実行されます。nはメッセージの長さです。

基本的な考え方は、32 個以上の未知数で GF(2) 上の 32 個の線形方程式を解く必要があるということです。ここで、各未知数は、変更を許可するビット位置です。問題を解決するには、32 を超える未知数を指定することが重要です。正確に 32 を選択した場合、特異な行列が得られて解が得られない可能性はまったくないためです。スプーフィング コードは、指定した 32 を超えるビット位置から 32 の未知のビット位置の特異でない選択肢を自動的に見つけます。

于 2013-09-02T15:43:34.290 に答える