Как ломают хеши

Хеш даёт вероятностную гарантию, и гарантия эта держится на предположении, что входные данные не подобраны против вашей хеш-функции. Иногда предположение неверно.

Модуль 2^64

Соблазнительная идея: считать хеш в unsigned long long и не брать модуль вовсе — переполнение само даёт остаток по $2^{64}$.

Быстро, коротко, модуль огромный. И ломается элементарно.

Существуют строки Туэ — Морса, определённые так:

$$t_0 = \texttt{a}, \quad u_0 = \texttt{b}, \quad t_{k+1} = t_k u_k, \quad u_{k+1} = u_k t_k$$

То есть каждая следующая пара получается склейкой предыдущих в двух порядках.

Для любого основания $p$ у этих строк совпадают хеши по модулю $2^{64}$, начиная с некоторого шага. Проверено:

основание	длина строк, где хеши совпали
257	128
31	256
131	1024
667	1024
1000003	1024

Строки при этом различны — начинаются они так:

abbabaabbaababbabaababbaabbabaab...
baababbaabbabaababbabaabbaababba...

А по простому модулю $10^9+7$ те же строки дают разные хеши. Дело именно в модуле, равном степени двойки.

Причина в том, что $2^{64}$ — не простое число, и разность хешей этих строк оказывается кратна большой степени двойки. Подобрать такое для простого модуля куда сложнее.

Практический вывод: не используйте переполнение как модуль, если на площадке есть взломы. Восемнадцать строк на Python строят контрпример.

Взлом при известных параметрах

Даже с простым модулем: если противник знает $p$ и $m$, он может перебором найти две строки с одинаковым хешем. По парадоксу дней рождения для этого достаточно перебрать около $\sqrt{m} \approx 3 \cdot 10^4$ строк — секунды работы.

На Codeforces такие тесты подбирают регулярно, и решения с фиксированными p = 31, MOD = 1e9+7 взламывают в первую очередь.

Три защиты

1. Случайное основание. Выбирайте $p$ во время выполнения:

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long P = 300 + rng() % 100;   // случайное основание в разумном диапазоне

Теперь подобрать тест заранее нельзя: параметр неизвестен до запуска. Это самая дешёвая и самая действенная мера.

Важно, чтобы $p$ оставалось больше максимального кода символа и не было кратно модулю.

2. Два хеша. С разными $p$ и разными $m$. Подобрать коллизию сразу по обоим — задача другого порядка сложности.

3. Проверять честно. Если после совпадения хешей сравнить объекты напрямую, решение становится детерминированным. Иногда это бесплатно: например, в задаче о поиске подстроки совпадения редки, и честная проверка почти не срабатывает.

Что не помогает

Просто увеличить модуль. Против случайных данных помогает, против подобранных — нет: перебор всё равно найдёт коллизию, просто дольше.

Взять «необычное» основание. Секрета в конкретном числе нет: противник посмотрит на ваш код после контеста. Секрет — только в случайности во время выполнения.

Смешать переполнение с простым модулем. Приём встречается («один хеш по модулю, второй через переполнение»), и он действительно лучше чистого переполнения. Но первый хеш при этом всё ещё уязвим к перебору, если параметры фиксированы.

Когда не стоит волноваться

На школьных олимпиадах взломов нет: тесты составлены заранее и против вашего решения лично не подбирались. Там хватит фиксированных параметров и одного хеша, если размер модуля соответствует числу сравнений.

Случайное основание всё равно стоит завести — оно бесплатно и снимает вопрос целиком.