Блюм, Микали и Яо: подделка, которую не отличить

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

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

Чем плохи обычные генераторы

Стандартный датчик случайных чисел устроен так:

$$x_{n+1} \;=\; a\,x_n + c \pmod m .$$

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

Он проходит уйму статистических проверок: цифры распределены ровно, пары не коррелируют, серии правильной длины. И при этом он предсказуем полностью: получив три подряд идущих числа, параметры $a$ и $c$ восстанавливают за пару строк арифметики, а дальше выписывают всю последовательность вперёд и назад.

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

Смена вопроса

Мануэль Блюм на лекции, 2018Joofjoof · CC BY 4.0

Блюм и Микали (Беркли, 1982) перестали спрашивать «похоже ли на случайное» и спросили: может ли кто-нибудь предсказать следующий бит?

Генератор называется криптографически стойким, если никакая быстрая программа, увидев первые $k$ битов, не угадывает $(k+1)$-й с вероятностью, заметно большей $1/2$.

Определение выглядит слабее прежних — говорится всего про один бит. И тут же теорема Яо (того же 1982 года) показывает, что оно сильнее всех:

Непредсказуемость следующего бита равносильна неотличимости от честной монеты никакой быстрой проверкой.

То есть одно скромное требование покрывает разом все статистические критерии — и те, что придуманы, и те, что придумают. Ход в точности тот же, что у Мартин-Лёфа с универсальной проверкой, с одной подменой: там слово «эффективный» означало «выполнимый машиной вообще», здесь — «выполнимый быстро».

Как такое построить

Сильвио Микали — соавтор определения и будущий лауреат премии Тьюринга за доказательства с нулевым разглашениемRguillou228 · CC BY-SA 4.0

Нужно, чтобы бит было трудно предсказать. Значит, нужна задача, которую легко поставить и трудно решить.

Построение Блюма — Микали берёт дискретный логарифм. Выбирается большое простое $p$ и первообразный корень $g$; из случайного зерна $x_0$ строится

$$x_{i+1} \;=\; g^{\,x_i} \bmod p ,$$

а на выход идёт один бит: меньше ли $x_i$, чем $p/2$. Возведение в степень быстрое, обратная задача — логарифм — считается трудной, и доказано: кто умеет предсказывать этот бит, тот умеет брать дискретный логарифм.

Через четыре года Блюм, Блюм и Шуб предложили вариант ещё проще: $x_{i+1} = x_i^2 \bmod n$, на выход — чётность, а стойкость опирается на трудность разложения на множители.

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

Третье определение случайности

Соберём вместе то, что получилось за эту нить.

Колмогоров: случайно то, что нельзя описать короче, чем выписать. Свойство объекта.
Мартин-Лёф: случайно то, что нельзя уличить никакой эффективной проверкой. Свойство объекта, добытое через свойства проверок.
Блюм и Микали: случайно то, что нельзя отличить от случайного за разумное время. Свойство наблюдателя.

Третье определение — единственное из трёх, которое умеет удовлетворить инженер, и единственное, которое зависит от того, кто смотрит. Одна и та же последовательность случайна для того, у кого час, и не случайна для того, у кого вечность. Случайность стала относительной — как скорость.

Честная оговорка: всё это стоит на предположении. Никто не доказал, что односторонние функции существуют; из $\mathrm{P} = \mathrm{NP}$ следовало бы, что ни одна из этих конструкций не работает. Криптография вся целиком — надстройка над недоказанной гипотезой, и об этом честнее говорить вслух.

Для класса

Сломайте линейный конгруэнтный генератор.

Известно, что числа получаются по правилу $x_{n+1} = a x_n + c \bmod 101$, и подряд вышли три числа: $x_1 = 5$, $x_2 = 48$, $x_3 = 46$.

Из двух уравнений $x_2 = ax_1 + c$ и $x_3 = ax_2 + c$ выведите, что $a = (x_3 - x_2)(x_2 - x_1)^{-1} \bmod 101$.
Найдите обратный элемент к $43$ по модулю $101$ (алгоритмом Евклида) и вычислите $a$.
Найдите $c$ и предскажите $x_4$ и $x_5$.
Сколько чисел подряд нужно увидеть, чтобы восстановить генератор, если модуль $m$ тоже неизвестен?
Обсудите: этот генератор прошёл бы проверку на равномерность распределения. Что это говорит о ценности статистических проверок для защиты тайны?

О людях

Мануэль Блюм (род. 1938, Каракас) — премия Тьюринга 2005 года. Отдельного упоминания стоит его школа: у него учились Сильвио Микали, Шафи Голдвассер, Расселл Импальяццо и ещё десяток людей, определивших нынешнюю криптографию. Он же придумал и то, что миллиард человек видит ежедневно, — проверку «докажите, что вы человек».

Сильвио Микали (род. 1954, Палермо) — премия Тьюринга 2012 года вместе с Голдвассер, за доказательства с нулевым разглашением: способ убедить собеседника, что вы знаете ответ, не сообщив о нём ничего.

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

Трое из одной лаборатории, три премии Тьюринга, и всё — вокруг вопроса, что значит «случайно».