Михаил Масленников - Криптография и свобода

– Вот шифртелеграмма, которую я получил накануне!

Это уже 1989 год, съезд народных депутатов. Генерал, стоя на трибуне, показывает прямо в телекамеру содержание шифртелеграммы, тот самый открытый текст, по которому легко вычисляется гамма наложения. И не в какой-нибудь ближневосточной стране, а в СССР. Мораль отсюда следует простая: советский военный шифр должен быть еще и стойким к проявлениям военного идиотизма.

На лекциях по основам криптографии нас последовательно подводили к мысли, что только строгий математический подход, основанный на результатах Шеннона, способен обеспечить гарантированную стойкость шифра. Всякие простые или чуть усложненные замены, коды, не обеспечивающие равновероятности шифртекста, перестановки знаков открытого текста без последующей перешифровки – это все ненадежно, нестойко, рассчитано на слабого противника. Хочешь быть спокойным за свои шифры – используй в них только то, что дает надежную гарантию стойкости при любом уровне подготовки криптоаналитиков-оппонентов. А уровень подготовки криптографов в США, по определению, не ниже, а даже может быть и выше, чем в СССР. Американцы давно следят за нашими линиями связи, знают общий характер переписки, умеют выделять служебные символы, используют протяжку вероятного слова, знают статистику языка и может быть еще многое другое. Хочешь иметь стойкий шифр — доверяй только строгим математическим оценкам!

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

Дисковые шифраторы были изобретены очень давно, еще до второй мировой войны. Они предназначены для шифрования телеграфных сообщений, состоящих из обычных букв латинского алфавита. Идея их построения очень простая. Каждой из 26 латинских букв ставится в соответствие один контакт на входе. При нажатии на клавишу, соответствующую этой букве, на данный контакт поступает электрический импульс, который начинает свое движение по цепочке дисков. Каждый диск представляет из себя колесо, на котором есть входные и выходные контакты, связанные между собой проводами-перепайками так, что одному контакту на входе соответствует строго один контакт на выходе. В математике такую конструкцию принято еще называть подстановкой. В результате после прохождения всей цепочки дисков на выходе появляется электрический импульс только на одном контакте. Буква, соответствующая этому контакту, является буквой шифртекста.

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

Историю возникновения дисковых шифраторов, а также их подробное описание и характеристики нам рассказывали на СД–7Б. Сейчас все это можно прочитать в упоминавшейся уже ранее книге Дэвида Кана «Взломщики кодов». Здесь же мне хотелось бы упомянуть об одном весьма интересном эпизоде из лекций по СД–7Б, который я потом неоднократно вспоминал в своей дальнейшей работе.

У дискового шифратора есть два типа ключей. Одни ключи – долговременные, это перепайки между контактами дисков, т.е. те подстановки, которые соответствуют каждому диску. Их смена означает смену самого диска, и производится довольно редко, например, раз в месяц или даже в год. Другие ключи – начальное расположение дисков друг относительно друга. Их можно менять гораздо чаще, делать различными для каждой телеграммы в зависимости от ее номера. Такие ключи называются сеансовыми или разовыми. Количество долговременных ключей – всевозможных подстановок — огромно. Для каждого диска может быть всего 26! (26 факториал – произведение всех чисел от 1 до 26) различных вариантов его перепаек, а дисков несколько, иногда по 6, поэтому общее количество долговременных ключей получается совершенно фантастическим, (26!) 6, нечего даже и думать о возможности опробования такого числа вариантов. Разовых же ключей намного меньше, всего (26) 6различных вариантов, даже во времена «Руты–110» было ясно, что такая работа по силам ЭВМ. Сюда еще добавляются разные заморочки, связанные с законом движения дисков друг относительно друга, но общий вывод можно сделать один: без знания подстановок надеяться дешифровать дисковый шифратор бесполезно. И вот тут лектор произнес одну замечательную фразу:

– Вы спросите, как вычисляются долговременные ключи? А никак, они покупаются.

Заходишь в магазин и покупаешь. На самом деле сейчас широко известно несколько детективных историй о том, как именно добывались долговременные ключи. Одна из таких историй – о немецкой подводной лодке U–571 времен второй мировой войны и находящемся на ней дисковом шифраторе «Энигма», захваченном американцами только для того, чтобы «купить» неизвестные подстановки.

Невозможность перебора долговременных ключей в дисковых шифраторах была равносильна признанию аксиомы в криптографии, аналогично той, что в геометрии прямая короче всякой другой линии, соединяющей ее концы, что в мат. анализе последовательность натуральных чисел бесконечна, что в физике справедливы законы Ньютона. Иметь дело с неизвестными факториальными ключами-подстановками, пытаться их определить, как-то вычислить – занятие малоприятное, в большинстве случаев просто бесполезное, их можно только «купить».

И вот тут начались вопросы и ответы.

– А почему нельзя сделать подстановку разовым ключом?

– Менять каждый раз диск в дисковом шифраторе долго, сложно и дорого.

– А не в дисковом? А, например, в шифре на новой элементной базе, работающем с байтами?

И уже много позже:

– А если мы реализуем шифр программно, то почему там нельзя использовать разовые факториальные ключи?

Можно, и еще как! Наличие факториальных ключей в криптосхеме, работающей с байтами по типу традиционного регистра сдвига, подрубает на корню все усилия криптоаналитика выписать и проанализировать уравнения шифрования, найти в них какие-то зависимости. Подстановка неизвестна – все, суши весла. Но если в дисковом шифраторе подстановки были долговременными ключами по объективным причинам, то в программном шифре все эти причины исчезли, запросто можно сделать факториальные ключи разовыми! Первый этап – схема работает вхолостую, выработанная генератором гамма идет на внутренние цели, выработку факториальных ключей-подстановок. А на втором этапе традиционный регистр сдвига, работающий с байтами и дополненный ключами-подстановками, начинает вырабатывать гамму наложения для шифрования открытого текста. За счет факториальных ключей схема может быть сильно упрощена и работать в дальнейшем с огромной скоростью, намного перекрывающей все небольшие издержки начальной холостой работы. Для такой схемы пусть хоть весь Генштаб каждый день трясет перед телекамерами CNN своими шифрованными телеграммами, дразнит ими АНБ вволю, до факториальных ключей им все равно не добраться!