0

SO ( EDIT: Incremental Checksums ) で、次のプロパティをサポートするいくつかのチェックサムアルゴリズム (そのうちの 1 つが adler32 だと思います) があることを以前に読んだことがあります。

adler32('abc'); // 123
adler32('def'); // 456
adler32('abcdef'); // 579 (123 + 456)

結果は、私がアーカイブしたいものを示すための単なる例であることに注意してください. adler および fletcher モジュールを使用して、PHP のハッシュ拡張でいくつかの例を試しましたが、値が加算されないようです。誰かが実装例を見せてもらえますか?

4

5 に答える 5

3

あなたが探しているのが のような文字列のハッシュ関数である場合、このプロパティを持つすべての関数ハッシュは固定関数hash(s1+s2) = hash(s1) + hash(s2)の形式であると確信しています。(sum of the hash_char(c) for all the chars c in the string)hash_char

これでは、非常に優れたハッシュ関数にはなりません。adler32 について見たことを覚えていませんか?

于 2009-09-29T19:59:56.030 に答える
2

Adler32はハッシュ関数ではありません。
このプロパティを持つ適切なハッシュ関数はありません。

ただし、同様の特性を持つ暗号化関数があります。準同型として知られています。
基本的：

E(text1)*E(text2)=cipher  
D(cipher) = text1 + text2

ここで、E は暗号化関数、D は暗号化関数、テキストは数値 (または数値としてシリアル化されたデータ) です。+ & * 以外の操作を使用するスキームが存在することに注意してください。

2 つのスキームの例: ElGamalとPaillier。どちらも遅いです。これは、非対称暗号化方式の一般的な特徴です。これらの例はどちらも * & + を使用しています。

于 2009-09-29T21:21:15.783 に答える
1

Adler32 はハッシュではなくチェックサム アルゴリズムであり、説明したプロパティはありません。

ハッシュが、ハッシュの結果によってハッシュの状態を記述できるという特性を持つことは非常に一般的です。

H (「aaa」) = G (H0、「aaa」)

ここで、G はハッシュとハッシュへの連結の関数であり、H0 は初期値で、多くの場合ゼロです。それで

H ( "aaa" ) = G ( H("aa"), "a" ) = G ( G ( H("a"), "a" ), "a" ) = G ( G ( G ( H0, "a" ), "a" ), "a" )

ただし、入力内の文字の関数を単純に追加する関数 ( G ( x .concat. y ) = G(x) + G(y) というルールで暗示されているように) は、そのすべての順列に対して衝突します。入力。

そのような関数の 1 つは、ASCII 入力から 128 ビットのハッシュを作成する場合があります。

H(x) = sum ( b => 1 << b foreach byte b in x )

それはその特性を持っているでしょう

H("abcdef") == H("abc") + H("def") 
            == H("a") + H("b") + H("c") + H("d") + H("e") + H("f") 
            == H("abcdfe")
            == H("abcfde")
            == H("abcfed")
 etc.
于 2009-09-29T20:26:01.467 に答える
1

私が誤解しない限り、不必要な数の衝突がなければこれがどのように可能かわかりません。

hash('cde') => 345 
hash('aaabcd') => 345
于 2009-09-29T19:50:15.657 に答える
0

Alder32 アルゴリズムの説明を考慮すると、文字列の連結に関して説明したプロパティがどのように可能であるかがわかりません。

編集：ハッシュのそのようなプロパティが不可能であるという欠陥のあるデモを削除しました。実際、そのようなハッシュの例は、入力内の文字の ASCII 値を単純に追加するものです (大きな数をモジュロするかもしれませんが、それは理解できます)。（私のこの誤りを指摘してくれたピート・カーカムに感謝します）。

Alder32 ではなく、準同型暗号化アルゴリズムを参照している可能性があります。このような暗号化スキームのリストは、こちら にあります。IBM の研究者である Craig Gentry も、完全な準同型暗号の作成に成功したと発表しましたが、現時点で技術的な詳細が公開されているかどうかはわかりません (これは大きなニュースになるでしょう)。

于 2009-09-29T19:57:53.317 に答える