Встреча посередине

Сорок крупнейших городов мира по данным GeoNames — от Шанхая до Тайбэя — вместе насчитывают 494 439 236 жителей. Можно ли разделить их на две команды так, чтобы населения сравнялись до человека? Способов разделить — 2⁴⁰, больше триллиона: даже по наносекунде на разбиение их перебор займёт около двадцати минут. Ниже ответ находится за доли секунды прямо в вашем браузере, а под картой — оценка перебора с той скоростью, с какой ваш браузер складывает суммы. Двигайте число городов и переключайтесь на города вокруг Алматы.

Ответ — да, и не одним способом: ровно поровну, по 247 219 618 человек, сорок городов делятся 5294 способами. Сцена показывает первый из них по порядку перебора: восемнадцать городов в одной команде, двадцать два в другой. Справа — все пары «сумма какой-то части первых двадцати городов + сумма какой-то части вторых двадцати». Таких пар 2²⁰ × 2²⁰ — те же 2⁴⁰ разбиений, ведь каждое разбиение складывается из выбора в первой половине и выбора во второй. Синие пары не дотягивают до половины всех людей, оранжевые перебирают, а ответы лежат ровно на границе цветов. Алгоритму не нужно смотреть на весь квадрат. Он идёт по строкам и в каждой двоичным поиском находит, где цвет меняется.

Идея

Если задачу можно разрезать на две независимые половины так, что ответ складывается из ответа для левой и ответа для правой, переберите каждую половину отдельно — по 2^n/2 вариантов — и запомните результаты одной из них в отсортированной таблице или хеш-таблице. Тогда для каждого варианта второй половины подходящий партнёр находится поиском, а не перебором. Вместо 2ⁿ шагов — около 2 · 2^n/2, то есть корень из прежнего числа.

Корень из триллиона — миллион. В этом вся сила приёма и вся его граница: он превращает невозможное в возможное, но не в лёгкое. Перебор 2⁸⁰ встреча посередине превратит в 2⁴¹ — и на это нужны уже терабайты памяти. Поэтому приём живёт там, где n — от 30 до 50, а числа слишком велики для динамического программирования.

Как это работает

Возьмём задачу о двух командах. Пусть s — общее население, и мы ищем подмножество городов с суммой как можно ближе к s/2.

1. Разрезать. Города делим на две половины — первые n/2 и остальные.
2. Перебрать половины. Для каждой половины выписываем суммы всех её подмножеств. Удобно делать это удвоением: начать со списка [0] и для каждого города приписать к списку его же копию, увеличенную на население города. Тогда номер суммы в списке — это маска: бит i номера означает, что i-й город половины взят.
3. Отсортировать одну половину. Суммы левой половины сортируем — 2^n/2 чисел.
4. Встретиться. Для каждой суммы b правой половины нужна левая сумма, ближайшая к s/2 − b. Двоичный поиск находит место, куда это число встало бы в отсортированный список, и ближайшая сумма — либо на этом месте, либо прямо перед ним.

Чтобы увидеть шаги на маленьком примере, сдвиньте ползунок в первой сцене до шести городов: квадрат станет таблицей 8 × 8, где каждая клетка — одно из 64 разбиений, и граница цветов пройдёт между клетками. Вместо двоичного поиска можно отсортировать обе половины и идти двумя указателями: по левым суммам — вверх, по правым — вниз. Это та же граница цветов, пройденная лесенкой, за линейное время после сортировки. А если нужна не ближайшая сумма, а точная, левую половину можно положить в хеш-таблицу и обойтись без сортировки.

Почему ответ верный

Доказательство держится на одном: ответ складывается из ответов половин, и половины независимы — выбор в левой не меняет того, что можно выбрать в правой. Если это не так — скажем, команды должны быть одного размера, — условие перестаёт быть независимым, но его можно вернуть, разложив суммы половин по числу взятых городов и встречая только подходящие группы. Так устроена первая задача в конце статьи.

Код

Программа делит 40 крупнейших городов. На Python суммы удобно держать в массивах numpy: удвоение списка — это np.concatenate, сортировка — np.argsort, а двоичный поиск для всех миллиона правых сумм разом — один вызов np.searchsorted. На Go всё делается обычными срезами, sort и slices.BinarySearch. При равных суммах обе программы выбирают одно и то же разбиение: наименьшую маску справа, при ней — наименьшую слева.

the 40 largest towns of GeoNames, 494439236 people in all
two halves of 20: 1048576 sums each instead of 1099511627776 subsets
the smallest difference between the teams: 0 people
exact splits: 5294 (each split is counted once, not as A|B and B|A)

Населения в GeoNames часто круглые — у Чунцина ровно 22 миллиона, у Киншасы 16, — и это помогает точным разбиениям найтись. Но точных разбиений было бы много и так: подмножеств больше триллиона, а возможных сумм — меньше полумиллиарда, и на каждую сумму в среднем приходятся тысячи подмножеств.

Двойной замок

Самое известное применение приёма — в криптографии. Пусть у шифра ключ длиной k бит, и перебор всех ключей кажется слишком быстрым. Напрашивается зашифровать сообщение дважды, двумя независимыми ключами: C = E_k2(E_k1(P)). Неизвестных бит теперь 2k, и перебор пар ключей стоит 2^2k. Но у атакующего, который знает хотя бы кусок открытого текста P и его шифр C, есть путь короче. Промежуточный текст M = E_k1(P) можно получить с двух сторон: зашифровав P всеми ключами k1 и расшифровав C всеми ключами k2. Где два списка совпали — там кандидат в пару ключей. Работы — 2 · 2^k вызовов шифра вместо 2^2k: второй ключ добавил к стойкости один бит, а не k.

Ниже — настоящий шифр Speck32/64 с блоком в 32 бита, у которого ключи укорочены, чтобы атака шла секунды. Им дважды зашифрована первая фраза «Войны и мира» в переводе Луизы и Эйлмера Мод. Атакующий знает только её начало, Well, Pr, — восемь байт, два блока.

Сцена открывается с ключами по 14 бит — как в листинге ниже — и находит единственную пару. Сдвиньте ползунок до 20 бит и нажмите «Атаковать» ещё раз. Теперь посередине встречаются почти три сотни пар ключей — при ключах по умолчанию 287, — и все, кроме одной, — случайные совпадения. Причина в размерах. Пар ключей 2⁴⁰, а возможных значений блока — 2³², поэтому на каждое значение середины приходится в среднем 2⁴⁰/2³² = 256 пар, которые дают его по чистой случайности. Второй известный блок отсеивает их: вероятность, что ложная пара угадает и его, — 2⁻³². Когда ключи вдвое длиннее блока, известных блоков нужно больше, и атакующие их добывают.

Speck32/64 test vector: a86842f2 (the paper says a86842f2)
keys of 14 bits, 20 blocks intercepted: 6129cdf4 a1e61005 80c3e04a 02fee7c1 ...
cipher calls: 32768 instead of 268435456 pairs of keys
candidates after the first block: 1
after the second block: 1
k1 = 2b7e, k2 = 1a5f: Well, Prince, so Genoa and Lucca are now just family estates of the Buonapartes.

Первая строка — проверка самого шифра: контрольный пример из статьи авторов Speck, ключ 1918 1110 0908 0100 и блок 6574 694c, должен дать a868 42f2. Совпало — значит, атака ломает настоящий Speck, а не похожую на него самоделку.

Сколько это стоит

Время — 2 · 2^n/2 переборов половин, сортировка одной половины, O(2^n/2 · n), и 2^n/2 двоичных поисков, ещё столько же. Для атаки на шифр n — это число бит в обоих ключах вместе. Ниже — замер атаки на двойной Speck при разной длине ключей. Ось времени логарифмическая: экспонента выглядит прямой, и её наклон — основание.

Каждый лишний бит ключа удваивает время встречи посередине и учетверяет время перебора. На Go перебор пар двенадцатибитных ключей шёл около четверти секунды — и, продолжив прямую до двадцати бит, получаем около пяти часов. Встреча посередине для двадцати бит заняла меньше секунды, разница — двадцать пять тысяч раз.

Память — настоящая цена

Время ушло под корень, а память выросла: таблица одной половины — 2^n/2 записей. Для 40 городов это миллион чисел, восемь мегабайт. Для 60 — миллиард, и таблица уже не помещается в память обычного компьютера, хотя миллиард шагов время позволяет. Для двойного DES с ключами по 56 бит таблица — 2⁵⁶ блоков: атака стоит 2⁵⁷ шифрований, что не так уж много, но хранить таблицу негде, и поэтому на практике для атак придумывают обмены времени на память.

Один такой обмен для суммы подмножества нашли Ричард Шрёппель и Ади Шамир в 1981 году. Предметы делятся не на две, а на четыре четверти. Суммы каждой четверти — 2^n/4 чисел. Суммы левой половины — это все суммы «первая четверть + вторая», и их не нужно выписывать все сразу: достаточно уметь выдавать их по возрастанию, а это делает куча на 2^n/4 элементов. Правую половину так же выдают по убыванию — и идут двумя указателями, как раньше. Время прежнее, около 2^n/2, а памяти — 2^n/4: для n = 60 это тридцать тысяч чисел вместо миллиарда.

Когда приём не помогает

Числа маленькие. Если население считать в тысячах, сумм станет немного — сотни тысяч, — и динамика по суммам ответит за n · s шагов, где s — сама сумма. Это псевдополиномиальное время: для небольших чисел оно лучше любой экспоненты, а встреча посередине нужна, когда числа велики — население до человека, суммы в тиынах, 64-битные ключи.

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

Три ключа вместо двух. Тройное шифрование E_k3(E_k2(E_k1(P))) тоже атакуют посередине: с одной стороны перебирают k1, с другой — пары (k2, k3). Это 2^2k, а не 2^3k. Поэтому тройной DES с тремя ключами по 56 бит считается стойким на 112 бит, а не на 168. Зато 112 бит перебором не взять, и именно тройной, а не двойной DES стал заменой простому.

Где работает

• Криптоанализ. Кроме атаки на многократное шифрование, приём встречается в разборе укороченных версий шифров и хеш-функций: если первые раунды зависят от одной части ключа, а последние — от другой, середину считают с двух сторон.
• Дискретный логарифм. Найти x, при котором g^x ≡ h по модулю p. Запишем x = i · m + j, где m ≈ √p. Таблица «малых шагов» — значения g^j для всех j < m; «большие шаги» — h · g^−im для i = 0, 1, …, и первое совпадение с таблицей даёт ответ. Около 2√p умножений вместо p. Метод опубликовал Дэниел Шэнкс в 1971 году под названием «шаг младенца, шаг великана».
• Поиск пути и головоломки. Две волны — от начала и от конца — встречаются посередине, и каждой нужна глубина вдвое меньше. Это двунаправленный поиск: тот же приём на графе, где половины — первые и последние ходы.
• Олимпиады. Ограничение n ≤ 40 при числах до 10¹⁸ почти всегда подсказывает встречу посередине, а n ≤ 20 — перебор масок или динамику по маскам.

История

Первым под этот приём подвели общую задачу Эллис Горовиц и Сартадж Сахни. В 1974 году они описали алгоритм для разбиения чисел и рюкзака: разделить предметы на две половины, перечислить суммы каждой, отсортировать и слить. Время — 2^n/2 с точностью до множителя, и для суммы подмножества в худшем случае ничего заметно быстрее с тех пор не придумали. Тремя годами раньше Дэниел Шэнкс опубликовал метод «шаг младенца, шаг великана» для теории чисел — та же встреча, только в показателе степени.

В 1977 году Уитфилд Диффи и Мартин Хеллман, разбирая, сколько стоил бы перебор ключей только что принятого шифра DES, заметили, что двойное шифрование с двумя ключами ломается вдвое дольше одинарного, а не в 2⁵⁶ раз. Отсюда и название атаки, которое потом перешло на весь приём. Последствие известно: когда ключа в 56 бит перестало хватать, DES стали применять трижды. В 1981 году Ричард Шрёппель и Ади Шамир показали, как обойтись памятью 2^n/4 вместо 2^n/2.

Задачи

В первой задаче команды должны быть одного размера, и встречаться придётся только суммам с подходящим числом городов. Во второй — замок с двумя ключами и два перехваченных блока; тесты подобраны так, что первая встреча посередине не всегда настоящая.