Моноалфавитные шифры существуют в различных формах уже многие сотни, если не тысячи, лет. В этих шифрах каждая буква исходного текста заменяется другой буквой соответствующего шифровочного алфавита. «А» может записываться как «Р», а «b», например, как «S». Каждой букве алфавита всегда будет соответствовать какая-то одна определенная буква в шифре. Такой шифр называется моноалфавитным, так как используется только один шифровочный алфавит. Я помню, как в детстве мне это объяснили и намекнули, что подобрать ключ к любой разновидности такого шифра — «легкотня легкотней». Например, «Цезарь»: да, это и вправду легкотня. Нужно только выяснить, на сколько шагов «сдвинут» алфавит, и дело в шляпе. Но если шифровочный алфавит был достаточно сильно рандомизирован, задача становится покаверзней. Фактически, если считать шифровочный алфавит «ключом», тогда у «Цезаря» — двадцать пять потенциально возможных ключей (так как существует лишь двадцать пять способов «сдвинуть» алфавит, не меняя порядок букв). Но если шифровочный алфавит (стандартный английский алфавит из двадцати шести букв) был перегруппирован случайным образом, то у него, как однажды продемонстрировал мне дедушка, оказывается 403 291 461 126 605 635 584 000 000 потенциально возможных ключей; это число является факториалом двадцати шести (что математики довольно остроумно обозначают как 26! и тем доказывают, что тоже неравнодушны к восклицательным знакам, в точности как работники индустрии игрушек).
Так я впервые познакомилась с факториалами. На тот случай, если вам это вдруг зачем-то понадобится, факториалы вычисляются так: 3! = 3×2×1,5! = 5×4×3×2×1, 13! = 13×12×11×10×9×8×7×6×5×4×3×2×1 и так далее. На самом деле это очень даже ловко придумано. 100! — произведение всех чисел от 1 до 100 — больше, чем количество атомов в известной Вселенной. Как бы то ни было, объяснил дедушка, никто не сможет проверить все эти ключи. Это правда: даже современный компьютер провозился бы дольше, чем существует Вселенная — прикиньте, да? — чтобы выполнить подобную калькуляцию (допустим, вычисляя количество всех возможных конфигураций в «го»).
Даже после того, как дедушка объяснил мне факториалы, я была готова принять бой.
— Давай, валяй, — сказала я. — Придумай хитро-прехитро запутанный алфавит, зашифруй что-нибудь, и спорим — я разгадаю.
Он придумал, а я победила, потому что никто не разгадывает моноалфавитные шифры, пытаясь угадать ключ.
Скажем, кто-то посылает вам текст, составленный с помощью моноалфавитного шифра с подстановкой, и в тексте значится что-нибудь вроде: QEPN BVQE С ASFN AXNYN GCZ С TSYU GXQ AXQBTXA ZXN PQBUH YNCH PSVXNYZ BEASU AXN НСК ZXN YNCUUK ХСН AQ. Ваш первый шаг таков. Есть ли в тексте отдельно от других стоящая буква? Да. Это «С», она встречается дважды. Ну что ж, в английском есть только два общеупотребительных однобуквенных слова: «I» и «а». Значит, «С» означает одно из них. Потом вы ищете самые часто встречающиеся буквы. В данном шифре это «N» (9 раз), «X» (тоже 9), «С» (7), «А» (тоже 7), «Q» (5), «Y» (5) и «U» (тоже пять раз, включая появление в диграфе из двух одинаковых букв в третьем слове с конца). Диграф — это двухбуквенная комбинация. Триграф — трехбуквенная. Диграфы бывают полезны при разгадывании моноалфавитных шифров, и только некоторые буквы образуют «сдвоенные» диграфы; чаще всего встречаются пары «ss», «ее», «tt», «ff», «ll», «mm» и «оо».
Теперь вспомните: что вам уже известно об английском языке? Вы знаете, что — самые распространенные буквы во всех «нормальных» текстах. В присланной вам шифровке больше всего букв «N» и «X». Может, какая-то из них соответствует «Е» или «Т»? Самое распространенное слово в английском — «the». Есть ли в тексте какие-нибудь трехбуквенные слова, которые, судя по их виду, могли бы означать «the»? Чтобы разгадать моноалфавитный шифр, не пытаясь при этом угадать ключ, приходится быть сыщиком слов. Вы должны искать закономерности. Вам надо начать подставлять те буквы, которые, как вы считаете, подходят, и посмотреть, не выплывет ли что-нибудь осмысленное. Пойдя этим путем, вы сможете разгадать послание.
Альтернативный подход: вы всегда можете прибегнуть к частотному анализу — он особенно хорош в тех неудобных случаях, когда зашифрованный текст не разбит на отдельные слова. При частотном анализе вычисляется частота встречаемости для каждой буквы шифровки, так что у вас получается список: на первом месте — самая распространенная буква, на втором — ее главная соперница, и так далее по убывающей вплоть до самой «непопулярной» буквы текста. Потом вы берете частотную таблицу (таких таблиц существует масса; нынче люди их даже в Интернете размещают), в которой указаны частоты встречаемости букв в общеупотребительном английском. Вы берете самую «популярную» букву шифровки и заменяете ее самой «популярной» буквой из вашей таблицы. Потом заменяете вторую по встречаемости букву и так далее до конца списка. Удивительно, как часто этот метод срабатывает всего лишь с незначительными поправками. Обычно его вполне хватает, чтобы самостоятельно разобраться в шифре. Если метод выявления закономерностей похож на дедукцию Шерлока Холмса, то частотный анализ ближе к методам судебной медицины двадцать первого века.
Вот ключ, который вы обнаружите, если дешифруете это послание:
При разгадывании вигенеровых шифров, в отличие от моноалфавитных, почти всегда приходится искать ключ, хотя «ключом» к вигенерову шифру обычно является какое-нибудь простое слово, а не целый рандомизированный алфавит. Однако сам шифр намного сложнее, и его невозможно разгадать теми же методами, что и моноалфавитные шифры.
В моноалфавитных используется лишь один шифровочный алфавит. Вот почему их легко разгадать: как только выясняется, какими буквами заменены «е» и «t», понять все прочее становится не сложнее, чем завершить партию игры в «виселицу». В полиалфавитных шифрах, однако, применяются сразу несколько алфавитов. Трудно описать, каким прорывом было предположение Альберти, что можно использовать несколько алфавитов в одной шифровке. Моноалфавитные шифры всегда поддаются разгадке благодаря частотному анализу — даже если не срабатывает метод Шерлока Холмса. Но что, если «исказить» частоты встречаемости букв, сделав так, что одной и той же букве исходника будут соответствовать разные буквы на всем протяжении шифрованного текста? Этот вопрос и задал себе Альберти. И придумал метод, который… ну, гениален, иначе не скажешь. Вы чертите квадрат, состоящий из двадцати шести различных вариантов алфавита — каждый сдвинут на одну букву по отношению к соседним (см. таблицу). Потом выбираете короткое слово-ключ — скажем, RAIN — и пишете его снова и снова поверх текста, который хотите зашифровать, вот так:
Привет (англ.).
Самый трудный из всех (англ.).
Затем вы с помощью букв слова-ключа определяете, какую строчку «квадрата Вигенера» используете, чтобы зашифровать соответствующую букву сообщения. Буква «h» в слове «hello», зашифрованная по строчке «R», превратится в «Y», «Е», зашифрованная по строчке «А», так и будет «Е» (все, что попадает на строчку «А», остается без изменений, поэтому большинство слов-ключей буквы «А» не содержат). «L», зашифрованная по строчке «I», будет «Т». Однако следующая «l» будет шифроваться по строчке «N» и станет «Y». Таким образом, первое слово — «hello» — превратится в «YETYF», что совсем не похоже на моноалфавитную версию слова. Подсказки в виде сдвоенного диграфа больше нет, а «Y» означает две разные буквы.
Более длинное сообщение, приведенное выше, зашифруется так:
KHMURRLRJTWSKHMZRLT
Вам никогда этого не прочесть при помощи частотного анализа или дедукции. Вам нужно знать, что ключом было слово «RAIN». Это единственный способ справиться с вигенеровым шифром. Конечно, ключ иногда получается просто угадать. После нападения на Всемирный Торговый Центр одна фирма потеряла почти всех своих сотрудников. Немногие уцелевшие решили продолжить дела компании, но оказались перед проблемой: все пароли умерли вместе с теми, кто их знал. Тогда оставшиеся служащие сели и принялись копаться во всех аспектах жизни покойных коллег, записывая названия мест, куда те ездили по выходным, имена домашних животных и так далее, пока не угадали все пароли до единого. Эту историю мне рассказал кто-то на работе — его до глубины души тронул корпоративный дух, проявленный этими людьми. А я просто подумала, что это одна из самых жутких историй, какие я только слышала в жизни.
Хм-м… в общем, учитывая тот факт, что едва ли вы знаете слово-ключ к посланию, смысл которого от вас хотят скрыть, вам нужно пойти путем логики и искать в тексте закономерности — они могут подсказать, какое слово было ключом. Большинство шифровок, конечно, чудовищно сложнее любого учебного примера. Однако мы можем начать искать закономерности в нашем:
KHMURRLRJTWSKHMZRLT
В тексте вроде бы дважды повторен один и тот же триграф, из чего можно сделать два разных вывода. Либо это чисто случайный результат процесса шифровки, и тогда нам от него никакого проку, либо — возможно! — одно и то же слово исходника стояло под одними и теми же буквами ключа и поэтому дважды зашифровалось одинаково; если так, нам это колоссально поможет.
После того как Альберти впервые высказал свои идеи, еще добрых лет триста никто не мог понять, как «взламывать» вигенеровы шифры подобным способом. Это сделал Чарлз Бэббидж,[37] гениально-безумный изобретатель Разностного Двигателя — первой вычислительной машины. Все началось с того, что у него состоялся весьма необычный спор с одним чудаком, который считал, что первым придумал полиалфавитные шифры.
— Я изобрел новый, непробиваемый код!
— Ну, вообще-то он не столь уж нов. О нем известно уже…
— Говорят вам: мой код невозможно взломать!
— Хорошо, пусть так — но вы его не изобретали.
— Вы что, бросаете мне вызов?
— Ладно, если вам так угодно — да, я бросаю вам вызов, дурак вы этакий.
— Тогда посмотрим, как вы с ним справитесь!
Квадрат Вигенера
Так Бэббидж, который не мог не принять вызов, брошенный столь очевидно безголовым человеком, тем более что вызов был полной нелепостью, мимоходом снабдил нас нашим методом. Бэббидж вообще был тот еще тип. Помимо Разностного Двигателя он изобрел также спидометр, скотосбрасыватель (устройство, крепившееся к поездам и счищавшее рогатый скот с путей) и заложил основу современной почтовой системы, позволяющей отправить письмо в любую точку страны за одну и ту же цену. Он понял, что если вы обнаружите закономерности шифра, как в нашем примере — скажем, повторение триграфа «КНМ», — дальше вам стоит действовать следующим образом. Скорее всего, у вас в руках будет шифровка гораздо длиннее; нужно выявить в ней все повторяющиеся буквенные группы. Затем сосчитать количество букв от начала одной группы до начала следующей. В нашем примере вы обнаружите, что от первой «К» до второй — двенадцать букв. Это значит, что количество букв в слове-ключе (которое было написано раз за разом поверх исходника) наверняка является делителем двенадцати, т. е. равно 12, 6, 4, 3, 2 или 1. Такой вывод вполне логичен: если предположить, что те же самые буквы повторяются через двенадцать и в слове-ключе, и в исходнике, то, конечно, это приведет к повтору буквенных групп в шифровке. Двухбуквенный ключ уложится в интервал шесть раз; двенадцатибуквенный — только один. При работе с большим объемом текста обычно удается точно установить делитель, и длина ключа становится очевидной.
Дальше начинаются некоторые сложности. Если вы обнаружили, что ключ состоит из четырех букв, нужно пройтись по всей длине шифровки и обозначить каждую ее букву цифрами 1, 2, 3 и 4, в зависимости от того, какой по счету буквой ключа она была зашифрована. Затем вам нужно произвести частотный анализ каждой выборки; таким образом, для букв, обозначенных единицей, вы получаете вполне определенную частотную таблицу и сравниваете ее со стандартной. Вы повторяете эту операцию для всех остальных выборок и выясняете каждую букву ключа. Дело в шляпе: считайте, вы разгадали послание.
Но я поступаю иначе.
Вот порядок моих действий: сперва я иду вслед за Бэббиджем и пытаюсь угадать длину слова-ключа, подсчитывая и разлагая на множители интервал между повторяющимися группами букв. Но дальше я предпочитаю пойти напролом — я вообще поклонница этой манеры передвижения и недолюбливаю проторенные дорожки: в общем случае они означают изрядный крюк. Так что следующий мой шаг всегда таков: найти все повторяющиеся триграфы в тексте и проверить, не означают ли они «the». В нашем примере удача ждет меня с ходу, так как первое слово — конечно же, «the». Я прорабатываю буквы «КНМ», используя квадрат Вигенера (если «К» соответствует «t», то шифровочная строка — «R»; если «Н» соответствует «h», то шифровочная строка — «А», и так далее). Вскоре я располагаю уже двумя фактами, от которых танцую дальше: во-первых, количество букв в слове-ключе является делителем двенадцати; во-вторых, первые буквы в нем — вероятно, «RAI». Интуиция немедленно подсказывает мне, что это слово «RAIN». На самом деле, посмотрев в словаре, я нахожу другие подходящие слова — «RAID», «RAIL» и «RAISIN»;[38] каждое соответствует обоим условиям. Так что дальше я просто проверяю их все по очереди. И когда я располагаю слово «RAIN» вновь и вновь над шифром, тот, конечно же, с легкостью разгадывается.
Я смотрю на запись, которую сделала в книжке:
ОЦЭСЫЁВАСЙБЮЮХФДФЛВАЯЯЮИФАВН??????? ЮЮ и ЯЯ??
Текста попросту слишком мало, полезных закономерностей в нем не выявить. Да и вообще, коротких фраз, где удобно повторялись бы простые распространенные слова, раз-два и обчелся. Я зеваю. Зачем мне это подкинули? Они хотят, чтобы я это прочла, или нет? Я сижу за конторкой, слушая, как шумит темнота за окном, и думаю, какая все это глупость. Зачем посылать шифровку без ключа? В смысле, я же не похитила ее, не перехватила — ее мне прислали!
Я так пристально всматриваюсь в листок бумаги, что тот начинает расплываться перед глазами. Буквы шифра перемешиваются и сливаются с логотипом «Попс», маячащим в левом верхнем углу, и словами «Наши поздравления» в центре. И вдруг меня осеняет: а что, если ключ здесь, у меня под носом? Вигенер пользовался понятием «замаскированного ключа»; может, и здесь есть такой?
Мое сердце быстро колотит в тамтам, а мозг внезапно делает стойку; я еще раз тщательно выписываю послание на странице, а над ним — несколько раз буквы «ПОПС». Мой самопальный «квадрат Вигенера», который я нарисовала на листке бумаги, сообщает мне следующее:
Я знал, что вы сможете это прочесть. Ну что это за послание, спрашивается?
Мобильная версия
