Накопительные хэши

Question

Я уже читал здесь о SO (EDIT: Incremental Checks), что есть некоторые алгоритмы контрольных сумм (я думаю, один из них - adler32), которые поддерживают следующее свойство:

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

Обратите внимание, что результаты являются лишь примерами, демонстрирующими то, что я хочу архивировать. Я пробовал несколько примеров с расширением хеша в PHP с модулями adler и fletcher, но значения, похоже, не складываются. Может кто-нибудь показать мне некоторые примеры реализации?

Answer 1

Если то, что вы ищете, это хеш-функция на строках, которая hash(s1+s2) = hash(s1) + hash(s2), Я уверен, что все функции хэш с этим свойством имеют вид (sum of the hash_char(c) for all the chars c in the string)для фиксированной функции hash_char,

Это не делает для очень хорошей хэш-функции. Вы не помните, что вы видели о adler32?

Answer 2

Adler32 не является хеш-функцией.
Нет хороших хеш-функций с этим свойством.

Однако существуют функции шифрования с аналогичным свойством; известный как гомоморфизм.
В принципе:

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

Где E - это функция шифрования, D - это функция шифрования, а тексты - это числа (или данные, сериализованные как число). Обратите внимание, что схемы, использующие операции, отличные от + & *, существуют.

Два примера схем: Эль-Гамаль и Пайе. Оба медленны, что является общей чертой асимметричных схем шифрования. Оба эти примера используют * & +.

Answer 3

Если я не пойму неправильно, я не понимаю, как это возможно без ненужного количества столкновений.

hash('cde') => 345 
hash('aaabcd') => 345

Answer 4

Adler32 - это алгоритм контрольной суммы, а не хеш, и у него нет свойства, которое вы описываете.

Хэши довольно часто имеют свойство, что состояние хэша может быть описано результатом хэша, так что если

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

где G - функция хеша и сцепление с хешем, а H0 - начальное значение, часто ноль. затем

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

Но функция, которая просто добавляет некоторую функцию символов во входных данных вместе (как подразумевается вашим правилом, что G ( x .concat. Y) = G(x) + G(y)) будет сталкиваться для всех перестановок этого вход.

Одна из таких функций может создать 128-битный хэш из входа ASCII:

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.

Answer 5

Ввиду описания алгоритма Alder32 я не вижу, как возможно описанное вами свойство в отношении конкатенации строк.

Редактировать: удалена некорректная демка, что такое свойство для хэша невозможно. Действительно, примером такого хеша является тот, который просто добавляет (ну, может быть, по модулю какое-то большое число, но это понятно) значение ASCII символов во входных данных. (Спасибо, Пит Киркхэм, за указание на мою ошибку).

Вместо Alder32 вы можете ссылаться на гомоморфные алгоритмы шифрования. Вы можете найти список таких схем шифрования здесь. Крейг Джентри, исследователь в IBM, также объявил о своем успехе в создании полностью гомоморфного шифрования, но я не знаю, были ли какие-либо технические подробности опубликованы в это время (это было бы большой новостью, кстати).