5

SMB共有間でファイルをコピーする、サポートされていない非常に古いプログラムがあります。コピー前にファイルの内容が変更されたかどうかを判断するためのチェックサム アルゴリズムがあります。アルゴリズムは簡単にだまされているようです。2 つのファイルが 1 つの '1' が '2' に変わることを除いて同一であり、同じチェックサムを返す例を見つけました。アルゴリズムは次のとおりです。

unsigned long GetFileCheckSum(CString PathFilename)
{
        FILE* File;
        unsigned long CheckSum = 0;
        unsigned long Data = 0;
        unsigned long Count = 0;

        if ((File = fopen(PathFilename, "rb")) != NULL)
        {
                while (fread(&Data, 1, sizeof(unsigned long), File) != FALSE)
                {
                        CheckSum ^= Data + ++Count;
                        Data = 0;
                }
                fclose(File);
        }
        return CheckSum;
}

私はあまりプログラマーではありません (私はシステム管理者です) が、XOR ベースのチェックサムがかなり雑になることは知っています。このアルゴリズムが、同じサイズで内容が異なる 2 つのファイルに対して同じチェックサムを返す可能性はどれくらいですか? （正確な答えは期待していません。「リモート」または「かなり可能性が高い」で問題ありません。）

パフォーマンスに大きな影響を与えることなく、どうすれば改善できるでしょうか?

最後に、 ? はどうなっていfread()ますか? ドキュメントを簡単にスキャンしましたが、理解できませんでした。Dataファイルの各バイトに順番に設定されていますか? 編集：わかりました。ファイルをチャンクに読み込みますunsigned long（ここでは32ビットOSを想定しましょう）。各チャンクには何が含まれていますか? ファイルの内容が の場合、最初のパスabcdの値は? Dataそれですか（Perlで）：

(ord('a') << 24) & (ord('b') << 16) & (ord('c') << 8) & ord('d')
4

8 に答える 8

7

MD5は通常、転送ファイルの整合性を検証するために使用されます。ソースコードは c++ で簡単に入手できます。これは、高速で正確なアルゴリズムであると広く考えられています。

堅牢で高速なチェックサム アルゴリズムも参照してください。

于 2009-06-25T17:43:31.677 に答える
5

Fletcher の checksum、特に fletcher-32 を調べて、現在の XOR チェーンでは検出できないさまざまなことを検出することをお勧めします。

于 2009-06-25T17:58:49.830 に答える
3

次のような式を使用して、アルゴリズムを簡単に改善できます。

Checksum = (Checksum * a + Data * b) + c;

a、b、および c が大きな素数の場合、これは適切な結果を返すはずです。この後、チェックサムのビットをローテーション (シフトではなく!) すると、さらに少し改善されます。

素数を使用すると、これは線形合同ジェネレーターに使用されるものと同様のアルゴリズムになります。これにより、長い期間と適切な分布が保証されます。

于 2009-06-25T17:36:56.160 に答える
0

あなたのアルゴリズムは、サイズが正確に 4 バイトの倍数ではないファイルを処理しようとはしていないようです。fread の戻り値はブール値ではなく、実際に読み取られたバイト数であり、EOF の場合やエラーが発生した場合は 4 とは異なります。どちらもチェックされませんが、0 が返されなかった場合は、ハッシュを計算する「データ」に 4 つの有効なバイトがあると単純に仮定します。

本当にハッシュを使用したい場合は、いくつかのことをお勧めします。まず、CRC32 ではなく、MD5 のような単純な暗号化ハッシュを使用します。CRC32 は、データの有効性をチェックするのには適していますが、ファイル システム全体にまたがって衝突が発生しないようにするためには、他の場所のコメントで言及されている誕生日のパラドックスのため、それほど優れたツールではありません。次に、関数を自分で作成しないでください。既存の実装を見つけます。最後に、独自のソリューションを展開する代わりに、単純に rsync を使用してファイルをレプリケートすることを検討してください。

于 2009-06-25T17:39:23.350 に答える
0

SHA-1 と (最近では SHA-2) は優れたハッシュ関数を提供し、より優れたハッシュ特性により MD5 にゆっくりと取って代わりつつあると私は信じています。それらのすべて (md2、sha など...) は効率的な実装を備えており、数文字の長さのバッファーのハッシュを返します (常に固定長ですが)。ハッシュを整数に縮小するよりも信頼性が高いことが証明されています。ドラザーがいる場合は、SHA-2 を使用します。SHA チェックサムを実装するライブラリについては、このリンクをたどってください。

これらのライブラリでコンパイルしたくない場合、Linux (およびおそらく cygwin) には次の実行可能ファイルがあります。にファイルを提供すると、チェックサムが 16 進文字列として出力されます。popen を使用してこれらのプログラムを実行できます -- 次のようにします:

const int maxBuf=1024;
char buf[maxBuf];
FILE* f = popen( "sha224sum myfile", "w" );
int bytesRead = f.read( buf, maxBuf );
fclose( f );

明らかに、これは非常に遅く実行されますが、有用な最初のパスになります。このようなファイル ハッシュ操作と I/O バウンド (メモリとディスク アクセスがボトルネックになる) を考えると、速度が問題になる場合、このアルゴリズムはすべて unsigned int を生成するアルゴリズムとほぼ同じ速度で実行されると予想されます。Perl と Python にも MD5 SHA1 と SHA2 の実装が付属しており、おそらく C/C++ と同じくらい高速に実行されます。

于 2009-06-25T22:00:20.347 に答える
0

freadビットは一度に 1 つのチャンクでファイルを読み込んでいます。各チャンクは long のサイズです (c では​​、これは適切に定義されたサイズではありませんが、32 ビットまたは 64 ビットと想定できます)。バッファリングの方法によっては、これは悪くないかもしれません。OTOH、より大きなチャンクを配列に読み込んでループする方がはるかに高速かもしれません。

于 2009-06-25T17:41:28.573 に答える
0

「高価な」暗号化ハッシュ関数でさえ、通常、かなりの時間がかかるように複数回の反復が必要です。ユーザーが故意に衝突を起こそうとする暗号化目的には推奨されなくなりましたが、SHA1 や MD5 などの機能は広く利用可能であり、この目的に適しています。

より小さなハッシュ値が必要な場合、CRC は問題ありませんが、優れたものではありません。nビットのCRC は、 nビットより長い変更のごく一部を検出できません。たとえば、ファイル内の 1 ドルの金額が $12,345 から $34,567 に変更されたとします。32 ビット CRC は、その変更を見逃す可能性があります。

より長い暗号化ハッシュの結果を切り捨てると、CRC よりも確実に変更を検出できます。

于 2009-06-25T17:44:27.433 に答える
0 
{
   CheckSum ^= Data + ++Count;
   Data = 0;
}

「++Count」はあまり機能しないと思います。コードは次と同等です

{
  CheckSum ^= Data;
}

一連のバイトを XOR するだけでは不十分です。特にテキストファイルの場合。ハッシュ関数

を使用することをお勧めします。

于 2009-06-25T17:50:44.803 に答える