a = "hello";
b = "world";
Вопрос про алгоритм CRC32
Пусть нам даны две строки:
Посчитаем хеши этих строк по алгоритму CRC32:
Вопрос: возможно ли найти хеш строки, полученной с помощью конкатенации двух строк a и b (т. е. c="helloworld"), зная только хеши исходных строк hash_a и hash_b?
Код:
Посчитаем хеши этих строк по алгоритму CRC32:
Код:
hash_a = CRC32(a);
hash_b = CRC32(b);
hash_b = CRC32(b);
Вопрос: возможно ли найти хеш строки, полученной с помощью конкатенации двух строк a и b (т. е. c="helloworld"), зная только хеши исходных строк hash_a и hash_b?
hello = 3d653119
world = cb7bce59
helloworld = 00456b75
Вот вам и ответ.
world = cb7bce59
helloworld = 00456b75
Вот вам и ответ.
вобще-то это не ответ. Как я понял вопрос состоит в том, существует ли функция f(x, y) такая что hash(a * b) = f( hash(a), hash(b) ) для любых a и b. С точки зрения чистой математики такая функция безусловно существует, но на практике задать ее вид довольно трудно и скорее всего вычислительная сложность такой функции не будет лучше чем у CRC32...
насколько я понимаю напишу.
crc32 не обратима (хотя вроде последние 4 байта можно восстановить) (и это даже не хэш) и чтобы получить crc32("helloworld") можно посчитать crc32("world") с вектором инициализации равному crc32("hello")
то есть, грубо говоря, нам всё равно нужна часть plaintext, в данном случае кусочек "world".
crc32 не обратима (хотя вроде последние 4 байта можно восстановить) (и это даже не хэш) и чтобы получить crc32("helloworld") можно посчитать crc32("world") с вектором инициализации равному crc32("hello")
то есть, грубо говоря, нам всё равно нужна часть plaintext, в данном случае кусочек "world".
и вообще может это вам пригодится как-то, самому стало интересно и сделал пример.
C точки зрения математики как раз такой функции в общем виде НЕ существует.
Смысл хэш-функций (точнее, контрольных сумм) в том, что даже при смене одного байта в массиве данных его хэш меняется неузнаваемо.
Если бы такие операции над хэшами были возможны, вся криптография и контроль целостности бы не существовали.
Смысл хэш-функций (точнее, контрольных сумм) в том, что даже при смене одного байта в массиве данных его хэш меняется неузнаваемо.
Если бы такие операции над хэшами были возможны, вся криптография и контроль целостности бы не существовали.
Цитата: Zorkus
C точки зрения математики как раз такой функции в общем виде НЕ существует.
не совсем понял что здесь означает в общем виде, но если быть точным, то с точки зрения математики функция -- это отображение множества чего-то на множество чего-то, так что такая функция безусловно существует. А если учесть конечность рассматриваемых множеств, то ее можно задать и аналитически. Я имею в виду принципиальную возможность, а не практическую, о трудности последней я писал в предыдущем посте
А, вот вы про что.
Тогда уточните, в вашей формуле hash() - фиксированная функция, или произвольная?
Вообще, может теоритически такая функция и существует. Но практически для любой сильной хэш функции я думаю не существует алгоритма (разумно быстрого) который бы вычислял hash (a + b) через hash(a), hash(b).
Тогда уточните, в вашей формуле hash() - фиксированная функция, или произвольная?
Вообще, может теоритически такая функция и существует. Но практически для любой сильной хэш функции я думаю не существует алгоритма (разумно быстрого) который бы вычислял hash (a + b) через hash(a), hash(b).
Спасибо всем кто откликнулся.
насколько я понимаю напишу.
чтобы получить crc32("helloworld") можно посчитать crc32("world") с вектором инициализации равному crc32("hello")
Цитата: bagie2
насколько я понимаю напишу.
чтобы получить crc32("helloworld") можно посчитать crc32("world") с вектором инициализации равному crc32("hello")
Я тоже так решил сделать, и не заморачиваться в дальнейших поисках.
Необходимо было реализовать алгоритм LZW. Для поиска по словарю я использовал хеш-таблицу. Работало за приемлемое время, но все-таки решил оптимизировать. Запросы в хеш-таблицу представляют собой find(string+character).
Слабое место было в том, что каждый раз считался хеш строки заново. Когда я кешировал хеши строк, и уже вычислял не полностью string+character, а только crc32(character), получил заметный прирост производительности.