Практикум MCMC: шифр Диакониса

Шифр простой подстановки меняет названия букв, но почти не трогает привычки языка. Если «ст» часто соседствуют в русском тексте, то их зашифрованные образы тоже будут встречаться рядом. MCMC превращает этот статистический след в маршрут по пространству ключей — и заодно показывает, где заканчивается информация, а где начинается фантазия исследователя.

Ключ как перестановка

Пусть алфавит содержит $m$ символов. Ключ $k$ — перестановка: каждую букву открытого текста он заменяет ровно одной буквой шифротекста. Число возможных ключей равно $m!$. Для 33 русских букв

$$33!\approx8{,}68\cdot10^{36},$$

а в информационных единицах

$$\log_2 33!\approx122{,}7\ \text{бит}.$$

Расшифровка — применение обратной перестановки:

$$k^{-1}\bigl(k(x_t)\bigr)=x_t\qquad\text{для всех }t.$$

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

Для учебного опыта удобно привести текст к фиксированному алфавиту: строчные русские буквы плюс пробел, удалить редкие знаки, а ё либо сохранить отдельно, либо заранее заменить на е. Правило должно быть одинаковым для обучающего корпуса и шифротекста. Это не мелкая чистка: она определяет модель языка.

Что шифр не прячет

Гистограмма частот при подстановке не меняет формы — меняются только подписи столбцов. Возьмём реальный корпус: тексты уроков 01–40 этого учебника, приведённые к 33 буквам и пробелу, — 921 345 знаков. Самая частая буква — о (10,4 % всех букв), затем е (8,7 %). Пробел занимает 14,6 % всех символов. После шифрования те же доли достанутся образам этих букв.

$$\#\{t\:y_t=k(c)\}=\#\{t\:x_t=c\}\quad\text{для любой буквы }c.$$

Иначе говоря, вектор частот шифротекста — это вектор частот открытого текста, переставленный тем же ключом:

$$f_{\text{шифр}}\bigl(k(c)\bigr)=f_{\text{текст}}(c),\qquad \sum_{c}f_{\text{текст}}(c)=1.$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Наивный частотный анализ говорит: самый частый символ шифра — это о. Иногда угадывает. Но между а (8,0 %) и и (7,6 %) разницы почти нет, и на коротком тексте порядок частот перемешивается случайно. Нужна статистика более высокого порядка — соседство.

Язык как вероятностная цепь

Возьмём тот же корпус и посчитаем частоты биграмм и триграмм. Сглаженная вероятность символа $c_t$ после контекста:

$$p(c_t\mid c_{t-2},c_{t-1}) =\frac{N(c_{t-2},c_{t-1},c_t)+\lambda} {N(c_{t-2},c_{t-1})+\lambda|\mathcal A|}.$$

Это ровно сглаживание Лапласа из урока 48: добавка $\lambda$ не даёт нулю превратиться в «невозможно». Логарифмический балл расшифровки $x_1\ldots x_n$:

$$L(x)=\sum_{t=3}^{n}\log p(x_t\mid x_{t-2},x_{t-1}).$$

За этой суммой стоит цепное разложение вероятности всей строки:

$$p(x_1\ldots x_n)=p(x_1)\,p(x_2\mid x_1)\prod_{t=3}^{n}p(x_t\mid x_{t-2},x_{t-1}).$$

Логарифм превращает произведение малых вероятностей в сумму и защищает от численного обнуления. Сглаживание $\lambda>0$ не даёт одной невиданной триграмме уничтожить весь балл.

Это маленькая языковая модель: она знает только короткий контекст, зато её балл прозрачен и считается за микросекунды. Высокий $L$ не доказывает осмысленность текста, но обычно предпочитает русские сочетания случайным.

В обозначениях статистической физики это распределение Больцмана:

$$\pi(k)=\frac{e^{-\beta E(k)}}{Z},\qquad Z=\sum_{k'\in\mathcal K}e^{-\beta E(k')},\qquad |\mathcal K|=m!.$$

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

Сколько информации в одном знаке

Измерим язык в битах. Если бы все 34 символа были равновероятны и независимы, каждый нёс бы

$$H_0=\log_2 34\approx5{,}09\ \text{бита}.$$

Посчитаем кросс-энтропию наших моделей на отложенном тексте (уроки 41–50, 128 344 знака, при обучении не использованы):

$$\widehat H=-\frac1n\sum_{t}\log_2 p(x_t\mid\text{контекст}).$$

Получаем 4,42 бита для униграмм, 3,59 для биграмм и 2,88 для триграмм. Каждый следующий порядок контекста отнимает у текста примерно по три четверти бита неопределённости.

Разность между максимальной и фактической энтропией — избыточность:

$$D=H_0-\widehat H_3\approx5{,}09-2{,}88=2{,}20\ \text{бита на знак}.$$

Каждый знак шифротекста приносит примерно 2,20 бита сведений о ключе. Ключ «весит» 122,7 бита. Значит, ждать однозначного ответа раньше, чем

$$U=\frac{\log_2 m!}{D}\approx\frac{122{,}7}{2{,}20}\approx56$$

знаков, бессмысленно — это расстояние единственности Шеннона.

Локальные ходы в огромном пространстве

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

$$q(k'\mid k)=q(k\mid k')=\binom{m}{2}^{-1}.$$

Число соседей у каждого состояния одинаково:

$$\binom{33}{2}=\frac{33\cdot32}{2}=528.$$

Граф состояний связен: любую перестановку раскладывают в произведение транспозиций, а значит, от любого ключа можно добраться до любого другого не более чем за $m-1$ обменов. Локальность хода и связность графа — два условия, без которых цепь либо не сдвинется, либо не дойдёт.

Целевая плотность на ключах:

$$\pi(k)\propto \exp\{\beta L(k^{-1}y)\}.$$

Коэффициент $\beta$ задаёт обратную температуру. Переход $k\to k'$ принимается с вероятностью

$$a(k,k')=\min\left(1, \exp\{\beta[L(k'^{-1}y)-L(k^{-1}y)]\}\right).$$

Правило выбрано так, чтобы выполнялось детальное равновесие:

$$\pi(k)\,P(k,k')=\pi(k')\,P(k',k) \quad\Longrightarrow\quad \pi P=\pi .$$

Нормировочная сумма по $m!$ ключам не нужна: она сокращается, как в общем алгоритме Метрополиса–Хастингса. Именно поэтому метод вообще применим: посчитать $Z=\sum_k\exp\{\beta L(k^{-1}y)\}$ нельзя ни при каких вычислительных ресурсах, а отношение $\pi(k')/\pi(k)$ считается за микросекунду.

Почему жадный подъём проигрывает

Проверим утверждение экспериментом на реальных данных. Берём 20 фрагментов по 400 знаков из отложенных уроков, шифруем каждый случайной перестановкой и даём двум алгоритмам одинаковый бюджет — 20 000 предложений. Жадный подъём принимает только улучшения. Цепь с температурой иногда идёт вниз.

Медианная доля верно расшифрованных знаков: 0,15 у жадного подъёма и 1,00 у цепи. В 18 случаях из 20 цепь нашла ключ с более высоким баллом; медианный отрыв по баллу — 880 нат. Доля принятых предложений: 11,9 % у цепи против 0,27 % у жадного подъёма — тот почти сразу перестаёт двигаться.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Пересчитывать весь балл заново не обязательно: обмен пары $(a,b)$ меняет лишь те слагаемые, где встречается хотя бы одна из двух букв,

$$\Delta L=\sum_{t\in T(a,b)} \bigl[\log p(x'_t\mid x'_{t-2},x'_{t-1})-\log p(x_t\mid x_{t-2},x_{t-1})\bigr].$$

Картина типична для комбинаторной оптимизации: локальных максимумов много, и почти все они плохи. Та же логика, что в уроке 21 про овраги и локальные минимумы, но пространство здесь дискретное, и «шаг вниз» — не малое смещение, а обмен двух букв.

Температура должна знать длину текста

Тонкость, о которой молчат учебники: масштаб $\Delta L$ растёт вместе с длиной текста. Обмен двух частых букв в тексте из 400 знаков меняет балл на сотни нат, а в тексте из 40 — на десятки. Поэтому фиксированная температура ведёт себя по-разному на разных задачах: на длинном тексте цепь замерзает и превращается в жадный подъём.

Разумная нормировка — температура, пропорциональная длине:

$$T(t)=\tau\,n\cdot\gamma^{\,t/N},\qquad a=\min\left(1,\exp\frac{\Delta L}{T(t)}\right).$$

В наших опытах $\tau=0{,}03$, $\gamma=0{,}03$, $N=20\,000$: цепь начинает горячей и заканчивает почти жадной. Это уже не выборка из фиксированного $\pi$, а имитация отжига — оптимизационная эвристика. Разницу надо называть вслух: у отжига нет стационарного распределения, и все гарантии сходимости MCMC к нему не относятся.

Как быстро цепь забывает старт: Добрушин

У цепи Маркова есть скорость перемешивания. Насколько быстро распределение $\mu_t$ после $t$ шагов приближается к целевому $\pi$ — вопрос не философский, а измеримый. Ответ на него дал Роланд Львович Добрушин, введя в 1956 году коэффициент эргодичности переходного ядра $P$:

$$\delta(P)=\tfrac12\max_{s,s'}\sum_{u}|P(s,u)-P(s',u)|.$$

Это максимальное расстояние по вариации между строками матрицы переходов. Основное неравенство Добрушина утверждает: применение ядра сжимает расстояние между любыми двумя распределениями,

$$\|\mu P-\nu P\|_{\mathrm{TV}}\le\delta(P)\,\|\mu-\nu\|_{\mathrm{TV}},$$

откуда сразу следует геометрическая сходимость

$$\|\mu_t-\pi\|_{\mathrm{TV}}\le\delta(P)^{\,t}\,\|\mu_0-\pi\|_{\mathrm{TV}}.$$

Позже Добрушин перенёс ту же идею на случайные поля: его условие единственности гиббсовского состояния (1968) ограничивает влияние соседей суммой, меньшей единицы. Наша $\pi(k)\propto\exp\{\beta L\}$ — в точности гиббсовская мера на конечном пространстве конфигураций, а обмен пары букв — локальное обновление; поэтому язык Добрушина здесь родной.

Лаборатория: расшифровка вживую

Модель языка в лаборатории настоящая: биграммы считаются прямо в браузере по фрагменту этого учебника, а шифротекст — кусок урока 45, замкнутый случайной перестановкой. Нажмите «запустить» и смотрите на нижнюю кривую $L_t$: она растёт ступенями, потому что каждая пойманная частая буква чинит десятки позиций сразу.

Три опыта, ради которых лаборатория и сделана. Первый: переключите режим на «жадный» и убедитесь, что балл упирается в плато, а текст остаётся кашей. Второй: верните «цепь», поднимите температуру до 0,1 — доля принятых предложений вырастет, но балл перестанет расти: слишком горячая цепь бродит и не оптимизирует. Третий: сократите текст до 60 знаков. Балл будет расти бодро, а осмысленный текст так и не появится — 60 знаков едва дотягивают до расстояния единственности.

Текст проявляется скачками

Один запуск на фрагменте в 600 знаков: доля верных позиций держится около 18 % первые две тысячи шагов, потом за полторы тысячи итераций поднимается до 58 %, ещё через шестьсот шагов до 75 %, а к концу достигает 100 % и больше не меняется.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Ступенчатость — не случайность реализации, а свойство задачи. Пока пара о↔е перепутана, каждая пятая буква текста неверна, и правильный обмен разом поднимает точность на десятки процентов. Промежуточных состояний между «почти всё неверно» и «почти всё верно» мало.

Чего нельзя узнать в принципе

Возьмём фрагмент в 200 знаков. В нём встречается лишь 25 различных букв из 33 — строки ключа для остальных восьми текст не проверяет никак. Отсюда честный потолок: точность ключа не может превысить 25/33, даже когда точность текста равна 100 %. Медианное покрытие растёт медленно: 19 букв при 50 знаках, 27 при 200, 32 при 1000.

Двадцать независимых поисков на этом фрагменте дали 20 различных ключей — и при этом медианную позиционную точность 0,99. Из 25 встретившихся букв 23 совпали в 90 % и более поисков, а две (й и х, по одному вхождению) кочуют между почти равными по баллу расшифровками.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Полезно записать обе метрики явно:

$$\mathrm{acc}_{\text{ключ}}=\frac1m\sum_{c=1}^{m}[\widehat k(c)=k(c)],\qquad \mathrm{acc}_{\text{текст}}=\frac1n\sum_{t=1}^{n}[\widehat x_t=x_t].$$

Первая усредняет по буквам алфавита, вторая — по позициям текста, где частые буквы имеют больший вес. Отсюда практическое правило отчёта: публиковать не «найденный ключ», а карту уверенности — какие строки подтверждены многими запусками, какие спорны. Ровно так же в уроке 46 мы отказывались от точечной оценки в пользу интервала.

Максимум балла — не истина

Ещё одна честная оговорка. В 2 опытах из 20 найденный ключ получил балл выше, чем истинный: на 200-знаковом фрагменте превышение составило 0,6 нат. Ничего удивительного: $L$ — балл модели, а не мера правды. Модель, обученная на конечном корпусе, вполне может считать чуть более вероятной строку, немного отличающуюся от оригинала.

$$\arg\max_k L(k^{-1}y)\ne k_{\text{ист}}\quad\text{в общем случае}.$$

Формально мы максимизируем не истинную вероятность, а сглаженную оценку по конечному корпусу:

$$\widehat k=\arg\max_{k}\sum_{t} \log\widehat p_\lambda\bigl(x_t\mid x_{t-2},x_{t-1}\bigr), \qquad x=k^{-1}(y).$$

Это тот же зазор между правдоподобием и истиной, который мы обсуждали в уроке 45: максимум правдоподобия — оценка, а не гарантия. Чем короче текст, тем шире зона, где балл почти не различает конкурентов.

Диагностика без известного ответа

В настоящем шифре эталонного открытого текста нет. Значит, качество приходится оценивать косвенно:

1. сравнивать лучшие баллы независимых запусков;
2. смотреть, совпадают ли наиболее частые пары ключа;
3. проверять правдоподобие на отложенной языковой модели;
4. измерять стабильность результата при изменении корпуса и сглаживания;
5. публиковать несколько конкурирующих расшифровок, если разрыв мал.

Можно зашифровать известные тексты и оценить долю правильно восстановленных букв — так мы и делали в этом уроке. Это synthetic benchmark: он проверяет алгоритм, но может быть легче исторических шифров с опечатками, именами и необычной орфографией.

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

Корпус решает, какой язык «нормален»

Если обучить модель на статьях XXI века, она может плохо оценивать дореволюционное письмо, диалект или программный код. Наш корпус — учебник по информатике: в нём подозрительно часто встречаются слова «модель», «выборка», «вероятность». Для шифровки школьного сочинения это приемлемо, для перехвата разговорной переписки — уже нет.

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

Модель должна обучаться только на открытом корпусе, не содержащем самого исходного текста. Мы для этого разделили уроки: 01–40 в обучение, 41–50 в проверку. Иначе длинные совпадения превращают расшифровку в поиск утечки, а не в статистический вывод — та же утечка между обучением и проверкой, что и в уроке 32; а если корпус подбирать, глядя на результат взлома, добавится и переплата за просмотр кандидатов из урока 63.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Информация, модель и поиск — три разные причины неудачи

Успех расшифровки определяется тремя отдельными вещами, и путать их нельзя.

$$\text{неудача}= \underbrace{\text{мало знаков}}_{\text{информация}} \;\cup\; \underbrace{\text{чужой язык}}_{\text{модель}} \;\cup\; \underbrace{\text{застрял в максимуме}}_{\text{поиск}}.$$

Формально причины входят в разные места. Информация решает, насколько остр максимум; модель задаёт саму функцию $L$; поиск определяет, какое значение

$$L_{\text{найдено}}=\max_{t\le N}L(k_t)\le\max_{k}L(k)$$

мы вообще увидим за бюджет $N$ шагов. Различить их можно экспериментом. Дайте алгоритму заведомо хорошую модель и огромный бюджет: если при 50 знаках разные запуски всё равно дают разные ключи, ограничение информационное — лечится только длиной перехвата. Уменьшите число итераций, не трогая текст: если результат испортился, мешал поиск — лечится температурой и рестартами. Смените корпус на другой жанр: если ответ изменился, виновата модель.

От частотного анализа к современным моделям

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

Современная нейросетевая модель оценивала бы длинный контекст лучше и опустила бы расстояние единственности почти вдвое — ещё в 1951 году Шеннон экспериментально оценил энтропию английского текста для человека примерно в один бит на знак — втрое меньше, чем даёт наша триграммная модель. Но её score дороже вычислять, труднее калибровать и проще переоптимизировать: поиск найдёт странные строки, которым сеть случайно назначает высокий балл. Переход от триграмм к трансформеру не отменяет диагностику, а делает её обязательной.

Что мы взяли из этого урока

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

Главный урок аккуратности: цепь оптимизирует балл, а не смысл. Максимум $L$ может стоять не там, где истина, и в наших опытах стоял не там дважды из двадцати. Отчёт, который сообщает один ключ без карты уверенности и без числа запусков, скрывает главное.

Следующий шаг курса переносит марковскую структуру из пассивного наблюдения в управление: у переходов появятся действия и награды, а вместо «где живёт цепь» мы будем спрашивать «как ей управлять».

Задачи