問題タブ [crc64]

データの整合性を確保するためにCRC64値を使用するキャッシュアプ​​リケーションがあります。さまざまなキャッシュサーバー間でデータとともに渡され、データが変更されたかどうかを比較するためのタイムスタンプである、追加のフィールドを配置することを考えています。

ただし、これにはプロトコルの変更が必要です。それは大したことではありませんが、何かが変わったことを示す指標として使用できるCRC64をすでに持っています。

同じCRC64を生成する2つのデータブロックの統計を知っている人はいますか？そうでない場合、どうすればそれを計算したり、その可能性を推定したりできますか？

ここでちょっとした難問があります: CRC-64 のようなハッシュ アルゴリズムを使用する場合、適切なハッシュを計算するには、文字列内の何バイトを読み取る必要があるでしょうか? すべての文字列の長さが少なくとも 2 KB だとすると、文字列全体を使用してキャッシュを計算するのは無駄またはリソースのように見えますが、何文字あれば十分だと思いますか? 64ビットに等しいので、8つのASCII文字で十分でしょうか? ASCII 文字を 8 文字以上使用しても意味がありませんか? これについてあなたの考えを知りたいです。

更新: 「適切なハッシュ」とは、計算にさらに多くのバイトを使用してもハッシュ衝突の可能性が低くならないポイントを意味します。

このメッセージ(ab,cd,ef)があり、ROHC (堅牢なヘッダー圧縮) CRC8 多項式があるとしe0ます。

最後のバイトから逆方向にメッセージの CRC を計算し、元のメッセージで計算している場合と同じ結果を得る方法はありますか?

CRC および同様の計算 (Fletcher や Adler など) の主な用途は、伝送エラーの検出にあるようです。そのため、私が見たほとんどの研究は、2 つのデータセット間の小規模な違いを検出する確率の問題に対処しているようです。私のニーズは少し異なります。

以下は、問題の非常に大まかな説明です。詳細はこれよりもはるかに複雑ですが、以下の説明は私が探している機能を示しています。この小さな免責事項は、「私が提案する別の方法で問題をより簡単に解決できるのに、なぜこの方法で問題を解決しているのですか?」などの回答を避けることを目的としています。- この質問や投稿に関係のない無数の理由により、この方法で問題を解決する必要があるため、そのような回答を投稿しないでください。

分散ネットワーク上でデータ セット (サイズ ~1MB) のコレクションを扱っています。これらのデータセットに対して計算が実行され、速度/パフォーマンスが重要になります。データセットの再送信を回避できるメカニズムが必要です。つまり、特定のサイズのデータ​​ セットごとに一意の識別子 (UID) を生成する何らかの方法が必要です。(次に、あるマシンから別のマシンにデータ セットのサイズと UID を送信します。受信側のマシンは、UID に基づいてデータがローカルにない場合にのみ、データの送信を要求する必要があります。)

これは、CRC を使用してファイルの変更をチェックすることと、CRC をダイジェストとして使用してファイル間の重複を検出することの違いに似ています。後者の使用についての議論は見たことがありません。

私は改ざんの問題には関心がありません。つまり、暗号強度ハッシュは必要ありません。

私は現在、シリアル化されたデータの単純な 32 ビット CRC を使用しており、これまでのところうまく機能しています。ただし、この状況で衝突の可能性を最小限に抑えるために、どの 32 ビット CRC アルゴリズム (つまり、どの多項式) が最適かを誰かが推奨できるかどうか知りたいですか?

私が持っている他の質問は、もう少し微妙です。現在の実装では、データ セットの構造を無視し、事実上、データを表すシリアル化された文字列を CRC するだけです。しかし、さまざまな理由から、CRC 方法論を次のように変更したいと考えています。最上位のデータ セットが、いくつかの生データといくつかの従属データ セットのコレクションであるとします。私の現在のスキームは、本質的に生データとすべての従属データセットを連結し、CRC の結果です。ただし、ほとんどの場合、従属データ セットの CRC を既に持っているため、生データを従属データ セットのCRCと連結してトップレベル データ セットの UID を作成し、次に CRC を作成します。この構築。質問は、

自分の考えを議論できる言語で表現するために、ちょっとした表記法を定義します。最上位データ セットTを呼び出し、生データ セットRと従属データ セットで構成されているとしますSi, i=1..n。のように書けますT = (R, S1, S2, ..., Sn)。データセットの連結を表す場合&、私の元のスキームは次のように考えることができます。

そして、私の新しいスキームは次のように考えることができます

次に、私の質問は次のとおりです。(1)TとT'が非常に異なる場合、どの CRC アルゴリズムが最小化するprob( UID_1(T)=UID_1(T') )か、およびどの CRC アルゴリズムが最小化するprob( UID_2(T)=UID_2(T') )か、これら 2 つの確率はどのように比較されますか?

この問題に関する私の（素朴で情報に通じていない）考えは次のとおりです。Tとの違いがT'1 つの下位データ セットにあるとします。WLOG はS1!=S1'. もしそれが起こればCRC(S1)=CRC(S1')、明らかに私たちは を持つでしょうUID_2(T)=UID_2(T')。一方、 の場合CRC(S1)!=CRC(S1')、 と の差は 4 バイトのみの小さな差R & CRC(S1) & CRC(S2) & ... & CRC(Sn)でR & CRC(S1') & CRC(S2) & ... & CRC(Sn)あるため、差を検出する UID_2 の能力は、伝送エラーを検出する CRC の能力と実質的に同じです。広く分離されていないいくつかのビット。これは CRC が行うように設計されているため、使用している CRC が送信エラーの検出に優れている限り、UID_2 はかなり安全だと思います。私たちの表記法で言えば、

CRC が数ビットのエラーを検出Pしない確率と、大きなサイズのデータ​​セットで大きな違いを検出しない確率を呼び出しますQ。上記はおおよそ次のように書くことができます。

ここで、次のように UID をもう少し変更します。「基本的な」データ、つまりT=(R)R が double、integer、char、bool などであるデータセットの場合は、 を定義しますUID_3(T)=(R)。次に、T下位データ セット のベクトルで構成されるデータ セットT = (S1, S2, ..., Sn)について、定義します。

T特定のデータセットに下位レベルのネストされた下位データセットがあると仮定すると、m漠然とした意味で、

いずれにせよ、これらの確率が小さいとすれば、これは次のように概算できます。

したがって、最大ネスト レベルがわかっている場合m、およびさまざまな CRC についてわかっPてQいる場合、必要なのは、 の最小値を与える CRC を選択することですQ + m*P。私がそうかもしれないと思うなら、P~Q上記はこれに単純化されます。UID_1 のエラー確率は ですP。UID_3 のエラー確率は です(m+1)P。ここmで、 は最大ネスト (再帰) レベルです。

これはすべて合理的に思えますか？

この G(x) =x^8 +x^2 +x+1 のような生成多項式を CRC-8 に使用する理由。これが最適な場合、どのように証明できますか。または、この多項式 G(x) = x^5 + x^4 + x^2 + 1 を CRC-5-ITU に使用します。

OSX 上の C から CRC64 実装で CommonCrypto を使用する C# にいくつかのコードを移植していますkCN_CRC_64_ECMA_182。たとえば、CommonCrypto を使用すると、CRC は次のように計算されます。

CNCRC(kCN_CRC_64_ECMA_182, bytes, bytesLen, &crcResult)

これにより、正しい値が出力されます。C# ライブラリ HashLib (またはその他のコード) を使用する場合、出力はまったく異なります。たとえば、上記の HashLib を使用した場合と同等の結果は次のようになります。

var checksum = HashFactory.Checksum.CreateCRC64(0x42F0E1EBA9EA3693UL); // ECMA 182 var result = checksum.ComputeBytes(bytes);

何か案は？出力に関して Apple の CommonCrypto と同等の C# の実装はありますか?

20桁以上の文字列のcrc64を保存したいです。スペースの複雑さと JOINS の観点から、大きな数字を格納することによるパフォーマンスへの影響を理解したいと考えています。

どんな助けや提案も大歓迎です。

ありがとう