Функция CRC без зависимости порядка

Question

Мне нужен механизм CRC для вычисления CRC числа строк, чтобы при заданных двух строках A и B сумма crc (A) + crc (B) == crc (A + B) .

P.S. XOR слишком слабый - алгоритм не должен быть тривиальным для обратного инжиниринга.

Answer 1

Принимая ваше обязательное условие, с + означает конкатенацию строк в RHS и добавление целых чисел в LHS, контрольная сумма любой строки будет суммой контрольных сумм ее отдельных символов. Все такие контрольные суммы изоморфны [*], единственными настраиваемыми параметрами являются значения, которые вы присваиваете каждому отдельному символу.

Если XOR слишком слаб, то я сомневаюсь, что любая такая линейная контрольная сумма будет достаточно сильной.

Если + означает что-либо еще в вашем необходимом состоянии, возможно, вы могли бы указать, что ...

[*] Ну, что-то морфическое.

Answer 2

Гомоморфное хеширование приближается к тому, что вы просите, но я не знаю ни одного, которое работает для контактирования строк, в отличие от математических операций.Все известные гомоморфные хеш-функции тоже абсурдно медленны.

Я бы предположил, что, возможно, даже невозможно создать безопасную хеш-функцию с таким свойством.

Answer 3

Я не думаю, что какие-либо контрольные суммы могли бы заполнить это условие.

Обычно размер (CRC (A)) == const (кодовый домен CRC является ограниченным набором, const == size (max_checksum)).

Так что, если у вас есть сообщение B, для которого CRC (B) == max_checksum, то для любого другого размера сообщения (CRC (B)) + размер (CRC (C))> const, (из CRC (B) + CRC (C)> max_checksum).

Или, иначе говоря, нет функции CRC, которая удовлетворяет требованию.

EDIT:

Однако, если вы имели в виду, что хотите иметь возможность определять CRC двух сообщений вместе, зная CRC обоих отдельных сообщений, да, возможно, это используется, например, rsync и называется переходящий хэш .