Вопрос про алгоритм CRC32

[zhekka3]

Пусть нам даны две строки:

a = "hello";
b = "world";

Посчитаем хеши этих строк по алгоритму CRC32:

hash_a = CRC32(a);
hash_b = CRC32(b);

Вопрос: возможно ли найти хеш строки, полученной с помощью конкатенации двух строк a и b (т. е. c="helloworld"),
зная только хеши исходных строк hash_a и hash_b?

[Xaositect]

Нет:

Prelude Data.Digest.CRC32 Data.Word Data.ByteString.UTF8> crc32 $ fromString "Maria has nine red beds."
248210933
Prelude Data.Digest.CRC32 Data.Word Data.ByteString.UTF8> crc32 $ fromString "Joe has fourteen magenta things."
93832682
Prelude Data.Digest.CRC32 Data.Word Data.ByteString.UTF8> crc32 $ fromString "Lars has thirteen black balls."
93832682
Prelude Data.Digest.CRC32 Data.Word Data.ByteString.UTF8> crc32 $ fromString "Maria has nine red beds.Joe has fourteen magenta things."
1783037554
Prelude Data.Digest.CRC32 Data.Word Data.ByteString.UTF8> crc32 $ fromString "Maria has nine red beds.Lars has thirteen black balls."
571588660

[venco]

Надо ещё знать длину первой строки.

[zhekka3]

venco в сообщении #396343 писал(а):

Надо ещё знать длину первой строки.

Да, забыл сказать длины сторок известны.
Подскажите как это сделать?

[zhekka3]

up

[Circiter]

Прошу прощения за поднятие старой темы, просто появилась парочка глупых мыслишек. А нельзя ли попробовать ответить на ворос топикстартера используя определение CRC как остатка от деления одного полинома-сообщения на другой полином? Нет, я не предлагаю привлекать китайскую теорему об остатках или ещё что-нибудь в том же духе. Моя идея гораздо проще.

Если я не ошибаюсь, CRC32 для некоторого сообщения $m$ можно посчитать как $\mathrm{CRC}(m)=m(x)\cdot x^{32}\bmod n(x)$, $\deg n=32$. Тогда для конкатенации двух строк $a$ и $b$, CRC32 будет вычисляться как-то так: $\mathrm{CRC}(a\circ b)=\big(a(x)\cdot x^{\deg b}+b(x)\big)\bmod n(x)$, то есть мы предварительно сдвигаем коэффициенты первого полинома, чтобы после сложения там поместилась вторая строка ($\deg b$ есть длина второй строки).

Вот я тут наткнулся на одну крайне разжеванную тему Арифметика остатков и взял оттуда две формулки, которые решил применить к выражению для CRC конкатенации так, чтобы оно вычислялось из известных $\mathrm{CRC}(a)$ и $\mathrm{CRC}(b)$. Неуверен в безошибочности выкладок (другие участники форума подобные вещи, наверное, в уме просто так проделывают), но конечный результат у меня получился таким:

$$\begin{align}\mathrm{CRC}(a\circ b)=\bigg(\Big(\big(a(x)&\cdot x^{32}\bmod n(x)\big)\big(x^{\deg b}\bmod n(x)\big)\Big)\bmod n(x)+\\&+b(x)\cdot x^{32}\bmod n(x)\bigg)\bmod n(x)=\\&=\bigg(\Big(\mathrm{CRC}(a)\big(x^{\deg b}\bmod n(x)\big)\Big)\bmod n(x)+\mathrm{CRC}(b)\bigg)\bmod n(x).\end{align}$$

Экспериментально не проверял (отчасти потому, что не совсем представляю себе как это реализовать), скорее всего не работает. :) Но тут важна сама идея, ведь CRC это же не какой-нибудь там криптографический хэш и такие вещи вполне возможны...

P.S.: Исходная задача точно решаема если одна из строк известна (лучше первая).

[maxal]

Circiter
Верно. Задача вполне решаема, если известна длина строки $b$.

Для простосты можно считать, что строка $b$ состоит из нулей, а ее значение CRC32 получается с помощью "подходящей" xor-константы, накладываемой в конце вычислений. Сначала вычисляем эту константу. Затем берем CRC32 от строки $a$ и преобразуем ее в соответствии с нулевыми символами строки $b$ (в известном количестве, равном длине $b$), ну и ксорим с вычисленной ранее константой.