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

Стеганография

Греческий ученый Геродот, считающийся одним из величайших историков мира, в своей знаменитой хронике войны между греками и персами в V в. до н. э. упоминает два любопытных примера стеганографии, потребовавших значительной изобретательности. Первый пример описан в третьей книге «Истории» Геродота: Гистией, тиран города Милета, приказал побрить гонцу голову. Затем на коже головы написали сообщение, которое нужно было отправить, и подождали, когда волосы отрастут. После этого человека послали к месту назначения, в лагерь Аристагора.

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

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

Когда дощечки доставили в Лакедемон (Спарта), лакедемоняне долго не могли разгадать секрет, пока, наконец, как я это понимаю, Горго […] не предложила соскоблить воск с дощечек, потому что тогда, по ее словам, на дереве обнаружится сообщение».

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

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

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

Перестановочное шифрование

Во время конфликта между Афинами и Спартой для контроля над Пелопоннесом часто использовалась скитала — прибор, состоящий из цилиндра и обмотанной вокруг него по спирали узкой полоски бумаги, на которой писалось сообщение. Хотя используемый метод (то есть алгоритм шифрования) был известен противнику, не зная точных размеров скиталы, было чрезвычайно трудно расшифровать перехваченное сообщение. Толщина и длина скиталы были, в сущности, ключом к этой системе шифрования. После разматывания бумажной ленты прочитать сообщение было невозможно. На рисунке ниже передаваемое сообщение (М) выглядит так: A message encoded with a scytale («Сообщение, закодированное с помощью скиталы»), но после разматывания бумажной ленты сообщение превратилось в тарабарщину (С): anh mca eos sdc sey adt gwa eil ete.

* * *

КРОШЕЧНЫЕ БУКВЫ

В годы холодной войны герои шпионских триллеров часто использовали крошечные микрофильмы для пересылки сообщений, чтобы их было невозможно прочитать невооруженным глазом. Этот стеганографический метод, названный «микроточки», был разработан на несколько лет раньше, в Германии во время Второй мировой войны. Фотография текста сообщения уменьшалась до размеров точки, а затем прикреплялась к безобидному письму в качестве одного из многих типографских символов.

* * *

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

Чтобы получить представление о силе этого метода, рассмотрим простой пример перестановки всего трех букв: А, О и R. Быстрая проверка без каких-либо расчетов показывает, что они могут быть переставлены шестью различными способами:

AOR, ARO, OAR, ORA, ROA и RAO.

В абстрактных терминах процесс выглядит следующим образом: как только одна из трех возможных букв поставлена на первое место, что дает нам три различных возможности, остаются еще две буквы, которые в свою очередь могут быть переставлены двумя различными способами. Таким образом, общее количество составит 3 x 2 = 6 способов. В случае более длинного сообщения, например, из 10 букв, число возможных перестановок составит 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1. Такое произведение в математике записывается как 10! и дает число 3 628 800. В общем случае для сообщения из n букв существует n! различных способов изменить их порядок.

Таким образом, скромное сообщение из 40 символов имеет так много способов изменения порядка букв, что это сообщение практически невозможно расшифровать вручную. Может быть, мы нашли идеальный криптографической метод?

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

Так начались поиски идеального алгоритма, и первые успехи в этом деле были достигнуты римскими императорами.

* * *

РУКОВОДСТВО ДЛЯ МОЛОДЫХ ДАМ

Камасутра — это пространное руководство, которое посвящено, среди прочего, тому, что необходимо знать каждой женщине, чтобы быть хорошей женой. Созданное около IV в. до н. э. брамином по имени Ватьсьяяна, оно рассказывает о 64 различных навыках, в том числе о музыке, кулинарии и шахматах. Особый интерес для нас имеет навык под номером 45, потому что он представляет собой искусство тайнописи, или млеччхита-викальпа. Древний мудрец рекомендует несколько методов, в том числе такой: разделить алфавит на две части и распределить буквы по парам случайным образом. В этой системе каждое соответствие пар представляет собой ключ. Например, один из ключей может быть следующим:

Чтобы написать тайное послание, нужно просто заменить каждую букву А в оригинальном тексте буквой Е , букву Р , соответственно, буквой С , J — буквой W , и так далее.

Кесарю кесарево

Veni, vidi, vici (пришел, увидел, победил).

Юлий Цезарь

Шифры подстановки разрабатывались параллельно с перестановочным шифрованием. В отличие от перестановочного шифрования, строгий шифр подстановки заме няет каждую букву или символ на какой-то другой. В отличие от перестановочного шифрования, шифр подстановки основывается не только на буквах, которые содержатся в сообщении. В перестановочном шифровании буква меняет свое положение, но сохраняет свою роль; одна и та же литера имеет одинаковое значение в исходном сообщении и в зашифрованном. В шифре подстановки буквы сохраняют свои позиции, но меняют роли (одна и та же буква или символ имеет в исходном сообщении одно значение, а в зашифрованном — другое). Одним из первых известных алгоритмов шифра подстановки был шифр Полибия, названный в честь греческого историка Полибия (203–120 гг. до н. э.), который оставил нам его описание. Об этом методе подробно рассказано в Приложении.

Спустя примерно 50 лет после появления шифра Полибия, в I в. до н. э., возник другой шифр подстановки, известный под общим названием шифра Цезаря, потому что именно Юлий Цезарь использовал его для секретной переписки со своими генералами. Шифр Цезаря является одним из наиболее изученных в криптографии, и он очень полезен тем, что иллюстрирует принципы модульной арифметики, одной из математических основ кодированного письма.

Шифр Цезаря заменяет каждую букву другой, находящейся в алфавите на некоторое фиксированное число позиций правее. Как писал великий историк Светоний в книге «Жизнь двенадцати цезарей», Юлий Цезарь использовал для своей личной переписки следующий алгоритм подстановки: каждая буква исходного сообщения сдвигалась по алфавиту на три позиции, а именно, буква А заменялась на D, В — на Е, и так далее. Буква W превращалась в Z, а X, Y и Z возвращались к А, В и С.

* * *

ГАЙ ЮЛИЙ ЦЕЗАРЬ (100-44 гг. до н. э.)

Цезарь (на изображении справа) был военным и государственным деятелем, диктатура которого положила конец Римской республике. После службы в качестве магистрата в Дальней Испании он присоединился к двум другим влиятельным людям того времени, Помпею и Крассу, образовав Первый Триумвират, скрепленный браком Помпея с дочерью Цезаря, Юлией. Три союзника разделили между собой Римскую империю: Красе получил восточные провинции, Помпей остался в Риме, а Цезарь взял на себя военное командование Цизальпийской Галлией и управление Трансальпийской Галлией. В это время началась Галльская война. Она длилась восемь лет и завершилась завоеванием римлянами галльских территорий. После этого Цезарь со своей победоносной армией вернулся в столицу империи и назначил себя единственным диктатором.

* * *

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

Рассмотрим теперь этот процесс подробнее. В таблице ниже мы видим изначальный алфавит из 26 букв и алфавит, преобразованный шифром Цезаря, где каждая буква сдвинута на три позиции вправо (верхний ряд — алфавит открытого сообщения, а нижний — шифроалфавит).

Когда два алфавита, оригинальный (или алфавит открытого сообщения) и шифроалфавит, расположены таким образом, шифрование любого сообщения сводится к замене букв из первого алфавита буквами из второго. Ключ к такому шифру получает название по букве, соответствующей зашифрованному значению буквы А (первой буквы оригинального алфавита). В нашем случае это буква D. Известное выражение AVE CAESAR («Радуйся, Цезарь») будет зашифровано как DYH FDHVDU. Обратно, если зашифрованное сообщение выглядит как WUHH, то расшифрованный текст будет TREE («Дерево»). В случае с только что описанным шифром Цезаря криптоаналитик, который перехватил сообщение и знает используемый алгоритм, но не знает ключ к шифру, должен будет перебрать все возможные сдвиги алфавита, пока не найдет сообщение, имеющее смысл. Для этого он должен будет, в худшем случае, попробовать все возможные ключи или сдвиги. В алфавите, состоящем из n букв, существует n возможных сдвигов, то есть n ключей.

* * *

ШИФРЫ В ФИЛЬМАХ

В классическом научно-фантастическом фильме режиссера Стэнли Кубрика по мотивам повести Артура Кларка «Космическая одиссея 2001 года» (1968) наделенный сознанием суперкомпьютер космического корабля HAL 9000 сходит с ума и пытается убить человеческий экипаж.

Теперь предположим, что слово HAL закодировано шифром Цезаря со сдвигом на одну позицию. Тогда буква Н соответствует букве I , А соответствует В , a L — букве М ; другими словами, получается I BM , в то время крупнейший в мире производитель компьютеров. О чем пытался рассказать этот фильм: об опасностях искусственного интеллекта или об угрозах бесконтрольной коммерческой монополии? Или это просто совпадение?

Всевидящий глаз компьютера HAL 9000 из фильма «Космическая одиссея 2001 года»

16 = 4. Модульная арифметика и математика шифра Цезаря

16 = 4? 2 = 14? Это не ошибка и не какая-то странная система счисления. Работа шифра Цезаря может быть проиллюстрирована теорией, которая привычна для математики и в еще большей степени для криптографии — модульной арифметикой, иногда называемой часовой арифметикой. Эта теория появилась еще в работах греческого математика Евклида (325–265 гг. до н. э.) и является одной из основ современной информационной безопасности. В этом параграфе мы расскажем о базовых математических понятиях, связанных с этим особым типом арифметики.

Возьмите в качестве примера обычные часы со стрелками и сравните их с цифровыми часами. На часах со стрелками циферблат разделен на 12 частей, которые мы обозначим числами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, И. В следующей таблице можно видеть, как время на аналоговом циферблате соответствует времени после полудня на экране цифровых часов.

Когда мы говорим, например, что сейчас 14:00, мы можем также сказать, что сейчас два часа дня. Тот же принцип применяется и в случае измерения углов. Угол в 370 градусов равен углу в 10 градусов, потому что от первого значения мы должны вычесть полный оборот в 360 градусов. Заметим, что 370 = (1 х 360) + 10, то есть 10 является остатком от деления 370 на 360. Какой угол эквивалентен углу в 750 градусов? Вычитая соответствующее количество полных оборотов, мы получим, что угол в 750 градусов равен углу в 30 градусов. Мы видим, что 750 = (2 х 360) + 30, то есть 30 является остатком от деления 750 на 360. В математике это обозначается так:

750 #t.jpg_14  30 (mod 360)

Мы говорим: «750 сравнимо с 30 по модулю 360». В случае с часами мы бы написали

14 #t.jpg_13  2 (mod 12).

Мы также можем представить себе часы с отрицательными числами. В этом случае который будет час, когда стрелка показывает на —7? Или, другими словами, с каким числом сравнимо число —7 по модулю 12? Давайте посчитаем, учитывая, что на наших часах с циферблатом, разделенным на 12 частей, значение 0 соответствует 12.

— 7 = —7 + 0 = —7 + 12 = 5.

* * *

ОТЕЦ АНАЛИТИЧЕСКОЙ КРИПТОГРАФИИ

Основная работа Евклида Александрийского , «Начала», состоит из 13 томов, в которых излагаются основные факты планиметрии, теории пропорций, свойства чисел, сведения об иррациональных числах и стереометрии. Чаще всего ассоциируемые с этой последней теорией, работы греческого математика, связанные с арифметическими операциями на конечных числовых множествах, или операциями по модулю, являются одним из столпов современной теории криптографии. Известные и почитаемые еще арабскими учеными, работы Евклида впервые были изданы в Венеции в 1482 г. Вовсе не случайно, что и арабы, и венецианцы были великими мастерами криптографии.

* * *

ОПЕРАЦИИ ПО МОДУЛЮ

Как посчитать 231 по модулю 17 на калькуляторе?

Сначала мы разделим 231 на 17 и получим 13,58823529.

Затем найдем произведение 13 x 17 = 221. Таким образом мы избавимся от дробной части.

Наконец, найдем разность 231–221 = 10, получив остаток отделения.

Итак, 231 по модулю 17 равно 10. Этот результат записывается как 231  #_15.jpg_1 10 (mod 17).

* * *

Математика для расчетов на наших часах со стрелками, циферблат которых разделен на 12 частей, называется арифметикой по модулю 12. В общем случае мы говорим, что a  #_15.jpg_6 b (mod m), если остаток от деления а на m равен b, при условии что а, b и m — целые числа. Число b сравнимо с остатком от деления а на m. Следующие утверждения эквивалентны:

a  #_15.jpg_7 b (mod m)

b  #_15.jpg_8 a (mod m)

а — b  0 (mod m)

а — b кратно m

Вопрос «Которому часу на часах со стрелками соответствует время 19 часов?» эквивалентен в математических терминах следующему вопросу: «С каким числом сравнимо число 19 по модулю 12?» Чтобы ответить на этот вопрос, мы должны решить уравнение

19  #_15.jpg_13 х (mod 12).

Разделив 19 на 12, мы получим частное 1 и остаток 7, поэтому

19  #_15.jpg_14 7 (mod 12).

А в случае 127 часов? Разделив 127 на 12, мы получим частное 10 и остаток 7, поэтому

127  #_15.jpg_15 7 (mod 12).

Чтобы повторить изученное до сих пор, давайте рассмотрим следующие операции по модулю 7:

(1)  3 + 3  #_15.jpg 6

(2)  3 + 14  #_15.jpg_0 3

(3)  3 х 3 = 9  #_15.jpg_4 2

(4)  5 x 4 = 20  #_15.jpg_5 6

(5)  7  #_15.jpg_10 0

(6)  35  #_15.jpg_11 0

(7)  -44 = -44 + 0 = -44 + 7 х 7  #_15.jpg_12  5

(8)  -33 = -33 + 0 = -33 + 5 x 7  #_15.jpg_16 2

(1) 6 меньше, чем модуль, поэтому не меняется

(2)  3 + 14 = 17; 17: 7 = 2 и в остатке 3.

(3)  3 X 3 = 9; 9: 7 = 1 и в остатке 2.

(4 ) 5 х 4 = 20; 20: 7 = 2 и в остатке 6.

(5 ) 7 = 7; 7: 7 = 1 и в остатке 0.

(6)  35 = 35; 35: 7 = 5 и в остатке 0.

(7)  -44 = -44 + 0; 44 + 7 х 7  #_15.jpg_17 5.

(8)  -33 = -33 + 0; -33 + 5 x 7  #_15.jpg_18 2.

* * *

ТАБЛИЦА УМНОЖЕНИЯ ПО МОДУЛЮ 5 В EXCEL

Построить такую и подобные таблицы очень легко даже с базовыми знаниями офисной программы Excel. В нашем случае синтаксис функций для ячеек Excel (для столбцов и строк на нашем компьютере) показан ниже. Действие «остаток отделения числа на 5» переводится на язык Excel как «=ОСТАТ(число;5)». Конкретная операция по нахождению произведения 4 на 3 по модулю 5 записывается как «=ОСТАТ (4∙3;5)» и дает результат 2. Подобные таблицы очень помогают в расчетах по модульной арифметике.

* * *

Какая связь между модульной арифметикой и шифром Цезаря? Чтобы ответить на этот вопрос, мы запишем в таблице стандартный алфавит и алфавит со сдвигом на три буквы, добавив титульный ряд из 26 чисел.

Мы видим, что зашифрованное значение буквы под номером х (в стандартном алфавите) является буквой, стоящей на позиции х + 3 (также в стандартном алфавите). Поэтому необходимо найти преобразование, которое каждому числу ставит в соответствие число, сдвинутое на три единицы, и взять результат по модулю 26.

Заметим, что 3 является ключом нашего шифра. Таким образом, наша функция записывается как

C(х) = (х + 3) (mod 26),

где х — изначальное значение, а С(х) — зашифрованное значение. Теперь достаточно подставить вместо буквы ее числовое значение и применить трансформацию.

Возьмем в качестве примера слово PLAY и зашифруем его.

Буква Р стоит на позиции 15, С(15) = 15 + 3  18 (mod 26), а число 18 соответствует букве S.

Буква L стоит на позиции 11, С(11) = 11 + 3  14 (mod 26), а число 14 соответствует букве О.

Буква А стоит на позиции 0, С(0) = 0 + 3  3 (mod 26), а число 3 соответствует букве D.

Буква Y стоит на позиции 24, С (24) = 24 + 3 = 27  1 (mod 26), а число 1 соответствует букве В.

Таким образом, слово PLAY, зашифрованное с ключом 3, превратится в слово SODB.

В общем случае, если х означает позицию буквы, которую мы хотим зашифровать (0 для А, 1 для В, и т. д.), позиция зашифрованной буквы [обозначаемая С(х)] выражается формулой

С(х) = (х + k) (mod n),

где n — длина алфавита (26 в английском алфавите), a k — ключ, используемый в данном шифре.

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

С-1(х) = (х — k) (mod n).

В случае сообщения SODB, зашифрованного шифром Цезаря с ключом 3 с применением английского алфавита, то есть k = 3 и n = 26, мы получим:

С-1(х) = (х — 3) (mod 26).

Применим эту формулу следующим образом:

Для S: х = 18, С-1(18) = 18 — 3  15 (mod 26), что соответствует букве Р.

Для О: х = 14, С-1(14) = 14 — 3   11 (mod 26), что соответствует букве L.

Для D: х = 3, С-1(3) = 3–3  0 (mod 26), что соответствует букве А.

Для В: x = 1, С-1(1) = 1–3 = —2 + 26  24 (mod 26), что соответствует букве Y.

Сообщение SODB, зашифрованное шифром Цезаря с ключом 3, соответствует, как мы уже знаем, оригинальному тексту PLAY.

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

С (a,Ь) (x) = (а∙х + b) (mod n),

где а и b — два целых числа, меньших, чем число (n) букв в алфавите. Наибольший общий делитель (НОД) чисел а и n должен быть равен 1 [НОД (а, n) = 1], потому что иначе, как мы увидим позже, получится несколько возможностей для шифрования одной и той же буквы. Ключ шифра определяется парой (а, Ь). Шифр Цезаря с ключом 3 является, следовательно, аффинным шифром со значениями

а = 1 и b = 3.

Обобщенный аффинный шифр имеет более высокий уровень безопасности, чем обычный шифр Цезаря. Почему? Как мы видели, ключом аффинного шифра является пара чисел (а, b). Если сообщение написано с использованием алфавита из 26 букв и зашифровано с помощью аффинного шифра, то и а, и b могут принимать любые значения от 0 до 25. Таким образом, в этой системе шифрования с алфавитом из 26 букв возможное количество ключей составит 25 х 25 = 625. Заметим, что количество ключей для алфавита из n букв в n раз больше, чем в шифре Цезаря.

Это значительное улучшение, но аффинный шифр все еще возможно расшифровать методом перебора всех возможных вариантов.

* * *

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД)

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

Например, найдем НОД (48,30).

Разделим 48 на 30, получим остаток 18 и частное 1.

Разделим 30 на 18, получим остаток 12 и частное 1.

Разделим 18 на 12, получим остаток 6 и частное 1.

Разделим 12 на 6, получим остаток 0 и частное 2.

Мы закончили алгоритм.

НОД (48,30) = 6.

Если НОД ( а, n ) = 1, мы говорим, что а и n взаимно просты.

Соотношение Везу, имеющее большое значение в криптографии, устанавливает следующий факт: для двух целых чисел а и n , больших нуля, существуют целые числа k и q , такие что НОД ( а, n ) = kа + nq .

Игра в шпионов

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

Текст будет зашифрован с помощью аффинного шифра C(x) = 2x + 1 (mod 6).

Буква А зашифрована по формуле С(0) = 2 х 0 + 1  1 (mod 6), что соответствует букве В.

Буква В зашифрована по формуле C(1) = 2 x 1 + 1  3 (mod 6), что соответствует букве D.

Буква С зашифрована по формуле С(2) = 2 х 2 + 1  5 (mod 6), что соответствует букве F.

Буква D зашифрована по формуле С(3) = 2 х З + 1 = 7  1 (mod 6), что соответствует букве В.

Буква Е зашифрована по формуле С(4) = 2 х 4 + 1 = 9  3 (mod 6), что соответствует букве D.

Буква F зашифрована по формуле С(5) = 2 х 5 + 1 = 11  5 (mod 6), что соответствует букве F.

Предлагаемый аффинный шифр преобразует сообщения АВС и DEF в одно и то же BDF, поэтому исходное сообщение теряется. Что же случилось?

Если мы работаем с шифром, выраженным формулой С (а, b) (х) = (а∙х + b) (mod n), мы можем расшифровать сообщение однозначно, только когда НОД (а, n) = 1. В нашем примере НОД (2, 6) = 2 и, следовательно, не удовлетворяет этому условию.

Математическая операция расшифровки эквивалентна нахождению неизвестного х при данном значении у по модулю n.

С (а, b) (х)  = (ах + b) = y (mod n)

(ах + b) = у (mod n)

ах — у — b (mod n)

Другими словами, нам нужно найти значение а-1 (обратное значению а ), удовлетворяющее равенству а -1 а = 1, так что

а-1ах = а-1х(у — b)(mod n)

х = а-1(у — b)(mod n).

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

В случае аффинного шифра С (а, b) (х) = (ах + b) (mod n) обратное значение числа а будет существовать тогда и только тогда, когда НОД (а, n) = 1.

В случае аффинного шифра в нашем примере, С(х) = 2х + 1 (mod 6), мы хотим узнать, существует ли обратное значение для числа а, в нашем случае для числа 2.

То есть существует ли целое число n, которое меньше 6 и удовлетворяет выражению 2∙n = 1 (mod 6). Для ответа на этот вопрос мы подставим в данное выражение все возможные значения (0, 1, 2, 3, 4, 5):

2-0 = 0, 2–1 = 2, 2–2 = 4, 2–3 = 6  0, 2–4 = 8  2, 2–5 = 10  4.

Нет такого значения, следовательно, можно заключить, что 2 не имеет обратного числа. На самом деле мы это уже знали, так как НОД (2,6)  1.

Предположим теперь, что мы перехватили зашифрованное сообщение: YSFMG. Мы знаем, что оно было зашифровано аффинным шифром вида С(х) = 2х + 3 и изначально было написано на испанском языке с алфавитом из 27 букв (включая букву N, идущую после обычной N).

Как получить исходное сообщение?

Сначала мы посчитаем НОД (2,27), который равен 1. Значит, сообщение можно расшифровать! Для этого для функции С(х) = 2х + 3 мы должны найти обратную функцию по модулю 27:

у = 2х + 3

2х = у — 3.

Чтобы найти x, мы должны умножить обе части уравнения на число, обратное 2.

Число, обратное числу 2 по модулю 27, — это целое число n такое, что 2n  1 (mod 27), а именно 14. И действительно:

14∙2 = 28  1.

Итак, мы имеем

x = 14∙(у — 3).

Теперь мы можем расшифровать сообщение YSFMG.

Буква Y стоит на позиции 25, ей соответствует расшифрованная буква, стоящая на позиции

14∙(25—3) = 308  11 (mod 27).

Буква, стоящая в алфавите на позиции 11, — это L.

Для буквы S имеем 14∙(19—3) = 224  8 (mod 27), эта позиция соответствует букве I.

Для буквы F имеем 14∙(5–3) = 28  1 (mod 27), что соответствует букве В.

Для буквы М имеем 14∙(12—3) = 126  18 (mod 27), что соответствует букве R.

Для буквы G имеем 14∙(6–3) = 42  15 (mod 27), что соответствует букве О.

Расшифрованное сообщение является испанским словом LIBRO, что означает «книга».

За пределами аффинного шифра

Различные системы безопасности на протяжении многих веков использовали идею Цезаря и ее обобщение в виде аффинного шифра. В настоящее время любой шифр, в котором каждая буква исходного сообщения заменяется на другую букву, сдвинутую на фиксированное число позиций (не обязательно три), называется шифром Цезаря.

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

Если мы снимем какие-либо ограничения относительно порядка букв шифроалфавита, то потенциальное количество ключей резко возрастет. Количество ключей для стандартного алфавита из 26 символов (расположенных в произвольном порядке) составляет 26! = 403291461126605635584000000, то есть более 403 септиллионов ключей. Криптоаналитику, который тратит на проверку одного ключа всего лишь одну секунду, потребуется в миллиард раз больше времени, чем ожидаемое время существования Вселенной, чтобы исчерпать все возможности!

Вот один из примеров такого обобщенного шифра подстановки:

Строка (1)  — алфавит открытого сообщения. Строка (2)  — шифроалфавит.

Первые шесть букв шифроалфавита дают подсказку к выбранному порядку букв: он соответствует порядку букв на клавиатуре в стандарте QWERTY. Чтобы зашифровать известное высказывание Цезаря VENI VIDI VICI («Пришел, увидел, победил») шифром QWERTY, для каждой буквы алфавита открытого сообщения мы найдем соответствующую в шифроалфавите.

Мы получим следующее зашифрованное послание:

CTFO CORO СОЕО

Существует очень простой способ для генерации почти неисчерпаемого количества легко запоминающихся шифров для шифрования этим методом. Достаточно выбрать любое ключевое слово (это может быть даже фраза), поместить его в начале шифроалфавита и, начиная с последней буквы ключевого слова, завершить ряд буквами стандартного алфавита, следующими в обычном порядке, исключив лишь повторяющиеся буквы. Возьмем в качестве примера ключевую фразу JANUARY CIPHER («январский шифр»). Сначала мы избавимся от пробела и одинаковых букв, получив ключевое слово JNUYCIPHE. В результате наш шифроалфавит будет выглядеть так:

Сообщение VENI VIDI VICI теперь будет зашифровано как ХСМЕ XEYE XEUE. Такая система генерации шифров легко обновляется и почти исключает ошибки со стороны отправителя и получателя. В нашем примере было бы достаточно менять ключевое слово каждый месяц — JANUARY CIPHER (январский шифр), FEBRUARY CIPHER (февральский шифр), MARCH CIPHER (мартовский шифр) и т. д. — то есть после изначального выбора шифра стороны могут обойтись без дополнительных соглашений.

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

* * *

ШИФРОВАНИЕ СЛОВА БОЖЬЕГО

Средневековые криптоаналитики считали, что в Ветхом Завете тоже использовались шифры, и они не ошиблись. Существует несколько фрагментов из священных текстов, которые зашифрованы с помощью шифра подстановки, называемого атбаш. Этот шифр состоит в замене каждой буквы ( n ) другой буквой, которая находится в алфавите на таком же расстоянии от конца алфавита, как оригинальная буква — от начала. Например, в латинском алфавите буква А заменяется на Z , буква В — на Y и т. д. В оригинальном Ветхом Завете использовались буквы еврейского алфавита. Так, в книге пророка Иеремии (25:26) слово «Бабель» (Вавилон) зашифровано как «Шешах».

Еврейская Библия начала XVIII в.

Частотный криптоанализ

Коран состоит из 114 глав, каждая из которых соответствует одному из откровений, полученных пророком Мухаммедом. Эти откровения были записаны во время жизни пророка различными его спутниками и позднее собраны воедино по решению первого халифа Абу Бакра. Умар и Усман, второй и третий халифы соответственно, завершили проект. Фрагментарный характер оригинальных писаний привел к рождению области богословия, посвященной точной датировке различных откровений.

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

Рукопись Корана. XIV в.

Этот подход стал первым конкретным инструментом криптоанализа, получившим название частотного анализа. Первым человеком, оставившим письменное упоминание об этом революционном методе, был философ по имени Аль-Кинди, который родился в Багдаде в 801 г. Хотя он был астрономом, врачом, математиком и лингвистом, прославился он как создатель манускрипта по криптоанализу.

Даже если Аль-Кинди не был первым, его имя, безусловно, занимает важное место в истории криптоанализа.

До недавнего времени очень мало было известно о новаторской роли Аль-Кинди.

В1987 г. в одном из архивов Стамбула была обнаружена копия его трактата «Манускрипт о дешифровке криптографических сообщений». Он содержит краткое изложение революционного метода:

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

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

Подробный пример

Вот как встречаются буквы латинского алфавита — от наибольшей до наименьшей частоты — в текстах на английском языке: ETAOINSHRDLCUMWFGYPBVKJXQZ. Частота появления (в процентах) каждой буквы показана в следующей таблице.

Если сообщение было зашифровано с использованием шифра подстановки, как те, что описаны выше, его можно расшифровать в соответствии с относительной частотой, с которой встречаются буквы исходного сообщения. Достаточно посчитать частоту появления каждой зашифрованной буквы и сравнить ее с таблицей частот в языке, на котором сообщение было написано. Так, если буква J чаще всего встречается в зашифрованном тексте, она, скорее всего, соответствует букве Е в оригинальном сообщении (в случае английского языка). Если вторая по частоте появления в зашифрованном тексте будет буква Z, те же рассуждения приводят нас к выводу, что ей, скорее всего, соответствует буква Т. Криптоанализ завершается повторением процесса для всех букв зашифрованного текста.

Очевидно, что частотный метод не всегда может быть так легко применим. Частоты, указанные в таблице, справедливы лишь в среднем. В коротких текстах, таких как Visit the zoo kiosk for quiz tickets («Билеты викторины продаются в кассе зоопарка»), относительная частота появления букв сильно отличается от частоты, характерной для языка в целом. По сути, для текстов, содержащих менее 100 символов, такой простой анализ редко бывает полезен. Частотный анализ, однако, не ограничивается только изучением букв. Как мы видели, маловероятно, что в короткой криптограмме наиболее часто встречающейся буквой будет Е, но с большей уверенностью можно сказать, что пять наиболее часто встречающихся букв, скорее всего, будут А, Е, I, О и Т, хотя мы и не знаем, каким именно символам они соответствуют. В английском языке А и I никогда не появляются в паре, в то время как другие буквы могут. Более того, независимо от длины текста, гласные, как правило, чаще появляются в начале и в конце группы других букв, а согласные чаще встречаются с гласными или в коротких словах. Таким образом, нам, возможно, удастся отличить Т от А, Е, I и О. После успешной расшифровки некоторых букв в криптограмме появятся слова, в которых осталось расшифровать только один или два символа, что позволит нам строить гипотезы, каким буквам эти символы могут соответствовать. Скорость расшифровки увеличивается с количеством разгаданных букв.

* * *

ШЕРЛОК ХОЛМС , КРИПТОАНАЛИТИК

Расшифровка с использованием частотного анализа — очень драматичный метод, который привлекал внимание большого количества авторов. Возможно, самая известная история, основанная на криптоанализе тайного послания, описана Эдгаром Алланом По в 1843 г. в рассказе «Золотой жук». В Приложении содержится подробный разбор вымышленного послания, зашифрованного Эдгаром По, и его блестящая расшифровка с использованием частотного анализа. Другие писатели, такие как Жюль Верн и Артур Конан Дойл , использовали подобные идеи, чтобы добавить драматизма в сюжеты своих произведений. Герой рассказа Дойла «Пляшущие человечки», Шерлок Холмс, также сталкивается с шифром подстановки, что заставляет детектива обратиться к частотному анализу. Более 1000 лет спустя гениальная идея Аль-Кинди все еще привлекает людей своей красотой.

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

Полиалфавитный шифр

8 февраля 1587 г. Мария Стюарт, королева Шотландии, была обезглавлена в замке Фотерингей после признания ее виновной в государственной измене. Судебное разбирательство, приведшее к такому суровому приговору, установило, что Мария, вне всяких сомнений, была в сговоре с группой католических аристократов, возглавляемой молодым Энтони Бабингтоном. В их планы входило убийство английской королевы Елизаветы I и возведение Марии на трон католического царства, охватывающего Англию и Шотландию. Решающие доказательства были добыты контрразведкой Елизаветы во главе с лордом Уолсингемом. Из переписки между Марией и Бабингтоном стало ясно, что молодая шотландская королева знала о жестоком плане и одобрила его. Эти письма были зашифрованы с помощью алгоритма, который использовал и шифры, и коды: не только одни буквы заменялись другими, но и вместо некоторых общеупотребительных слов использовались специальные символы. Шифроалфавит Марии представлен ниже:

За исключением того, что буквы заменялись символами, шифр Марии ничем не отличался от любых других, которые криптографы во всем мире использовали в течение многих столетий. Молодая королева и ее сообщники были убеждены, что шифр надежен, но, к сожалению для них, лучший криптоаналитик Елизаветы, Томас Фелиппес, был экспертом в частотном анализе и смог расшифровать письма Марии без особых трудностей. Провал того, что стало известно как Заговор Бабингтона, показал правительствам и тайным агентам всей Европы, что обычный алгоритм шифра подстановки уже не безопасен. Криптографы оказались бессильными перед новыми методами расшифровки.

Фрагмент одного из писем шотландской королевы Марии Стюарт к ее сообщнику Энтони Бабингтону . За это письмо ее в конечном счете осудили на смерть.

Идея  Альберти

Тем не менее, средство против частотного анализа было найдено за сто лет до того, как Мария взошла на эшафот. Отцом нового шифра стал выдающийся ученый эпохи Возрождения Леон Баттиста Альберти. Более известный как архитектор и математик, внесший большой вклад в изучение перспективы, в 1460 г. Альберти разработал систему шифрования, которая состояла в использовании двух шифроалфавитов, как показано в следующей таблице:

Строка (1)  — стандартный алфавит. Строка (2)  — первый шифроалфавит. Строка (3)  — второй шифроалфавит.

Для зашифровки какого-либо сообщения Альберти предложил чередовать два шифроалфавита. Например, в случае слова SHEEP («овца») шифр для первой буквы берется из первого алфавита (V), а шифр для второй буквы — из второго алфавита (L), и так далее. В нашем примере слово SHEEP будет зашифровано как VLHCS. Преимущество такого алгоритма полиалфавитного шифрования по сравнению с предыдущими видно сразу: буква Е исходного слова шифруется двумя различными способами — как Н и С. Чтобы еще больше запутать криптоаналитика, пытающегося расшифровать этот текст, одна и та же буква криптограммы соответствует двум разным буквам оригинального текста. Частотный анализ, таким образом, теряет значительную часть своей силы. Альберти так нигде и не записал свои идеи, поэтому шифр был позже разработан примерно в одно и то же время, но независимо друг от друга двумя учеными: немцем Иоганном Тритемием и французом Блезом де Виженером.

Квадрат Виженера

В шифре Цезаря используется одноалфавитный шифр подстановки; один шифроалфавит соответствует алфавиту открытого текста, так что одна зашифрованная буква соответствует одной и той же букве исходного текста. (В классическом шифре Цезаря буква D всегда соответствует букве А, Е — В, и так далее).

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

Обратите внимание на симметрию в расположении букв. Пара (A, R) = (R, А), и это же соотношение справедливо для всех букв.

Мы видим, что квадрат Виженера содержит стандартный алфавит из n букв, повторяющийся n раз с различными увеличивающимися параметрами. Так, первый шифроалфавит получается применением шифра Цезаря с параметрами а = 1 и b = 2; второй — эквивалентен шифру Цезаря с Ь = 3 и так далее. Ключом к квадрату Виженера является правило для каждой буквы, которое указывает, на сколько строк вниз надо спуститься, чтобы найти зашифрованное значение, соответствующее этой букве. Простейший ключ состоит из движения вниз на одну строку при переходе от одной буквы исходного сообщения к другой.

Таким образом, наша классическая фраза VENI VIDI VICI будет зашифрована следующим образом:

Для шифрования первой V мы найдем соответствующую букву в строке 2: W.

Для шифрования Е мы найдем соответствующую букву в строке 3: G.

Для шифрования N мы найдем соответствующую букву в строке 4: Q.

I (строка 5): М.

V (строка 6): А.

I (строка 7): О.

D (строка 8): К.

I (строка 9): Q.

V (строка 10): Е.

I (строка 11): S.

С (строка 12): N.

I (строка 13): U.

* * *

ИГРА С ДИСКАМИ

На практике для полиалфавитного шифрования используется устройство, известное как шифровальный диск Альберти. Этот портативный прибор состоит из двух концентрических дисков: один — фиксированный, с выгравированным на нем стандартным алфавитом, второй — подвижный, с другим алфавитом. Отправитель, поворачивая подвижный диск, может сопоставить стандартный алфавит с разными шифроалфавитами в зависимости от числа поворотов диска, максимальное количество которых равно числу букв используемого алфавита. Шифр, полученный с помощью диска Альберти, очень устойчив к частотному анализу. Чтобы расшифровать сообщение, получатель должен сделать то же число оборотов, что и отправитель. Безопасность этого шифра, как всегда, зависит от сохранения в тайне кода, а именно — от расположения алфавита на подвижном диске плюс число необходимых поворотов. Диск Альберти с одним подвижным кольцом, на котором выгравирован стандартный алфавит, дает шифр Цезаря при каждом повороте. Аналогичные устройства использовались во время Гражданской войны в США, и сегодня их можно встретить в детских шпионских играх.

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

В результате наша фраза превратится в WGQM AOKQ ESNU. При этом повторяющиеся буквы исходного сообщения исчезнут. Однако каждый криптограф стремится к тому, чтобы генерировать шифры, которые легко запомнить, распространять и обновлять. Тогда стали брать ключевые слова с таким же или меньшим количеством букв, что и в исходном сообщении, чтобы строить более короткие и легкие в использовании квадраты Виженера. Ключевое слово дает первые буквы каждой строки (см. стр. 47), и строки продолжаются остатком алфавита (как они представлены в полном квадрате). Затем ключевое слово, повторенное нужное количество раз, пишется под буквами сообщения, которое необходимо было зашифровать. Буква ключевого слова под каждым символом сообщения подсказывала криптографу строку в матрице, из которой нужно было взять зашифрованное значение этой буквы.

* * *

ДИПЛОМАТ И КРИПТОГРАФ

Блез де Виженер родился во Франции в 1523 г. В 1549 г. он был послан французским правительством с дипломатической миссией в Рим, где заинтересовался криптографией и шифрованием сообщений. В 1585 г. он написал основополагающий трактат о шифрах, Traicte des Chiffres, где описывалась система шифрования, которой он дал свое имя. Эта система шифрования оставалась неподдающейся взлому на протяжении почти трех столетий, пока британцу Чарльзу Бэббиджу не удалось взломать ее в 1854 г. Любопытно, что этот факт стал известен лишь в XX в., когда группа ученых разбирала вычисления и личные заметки Бэббиджа.

* * *

Например, если мы хотим зашифровать сообщение BUY MILK TODAY («Купи сегодня молоко») с помощью ключевого слова JACKSON:

Зашифрованное сообщение будет KUAWAZXCOFKQ.

Квадрат Виженера  со строками, определенными ключевым словом JACKSON.

Как и в случае всех классических систем шифрования, расшифрованный текст сообщения, зашифрованного с помощью квадрата Виженера, является симметричным исходному тексту. Например, пусть у нас есть зашифрованное сообщение WZPKGIMQHQ, и мы знаем, что использовалось ключевое слово WINDY:

Давайте посмотрим на первый столбик. Мы хотим найти неизвестную букву «?», зная, что (? W) = W. Для этого мы посмотрим на строку W квадрата Виженера на стр. 44, найдем в этой строке букву W и определим, какому столбцу она соответствует; получим букву А. Аналогично мы ищем вторую букву «?», зная, что (? I) = Z, и получаем букву R и так далее. Таким образом мы получим исходное сообщение ARCHIMEDES («Архимед»).

Историческое значение квадрата Виженера, которое он разделяет и с другими полиалфавитными шифрами, например, с шифром Гронсфельда (разработанным примерно в то же время; мы приводим его подробное описание в Приложении), состоит в устойчивости к частотному анализу. Если одна и та же буква может быть зашифрована несколькими способами с возможностью тем не менее ее впоследствии расшифровать, как же можно такой шифр взломать? Этот вопрос оставался без ответа более 300 лет.

Классификация алфавитов

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

Одним из наиболее успешных вариантов моноалфавитного шифра был так называемый однозвучный шифр подстановки, который пытался защититься от методов статистического криптоанализа, заменяя буквы с наибольшей частотой появления несколькими разными символами. Например, частота появления буквы Е в среднем составляет 10 % в любом языке. Однозвучный шифр подстановки пытался изменить эту частоту, заменяя букву Е десятью альтернативными символами. Такие методы были популярны вплоть до XVIII в.

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

Экспертные возможности «черных кабинетов» вскоре сделали небезопасными любые формы одноалфавитного шифра подстановки, как бы он ни модифицировался.

Мало-помалу ведущие игроки на поле обмена информацией избирали полиалфавитные алгоритмы. Утратив свое самое мощное оружие, частотный анализ, криптоаналитики в очередной раз оказались беззащитными перед натиском криптографов.

* * *

КРИПТОГРАФЫ КОРОЛЯ-СОЛНЦА

Хотя мало кто за пределами королевского двора Людовика XIV знал об их существовании, Антуан и Бонавентура Россиньоль принадлежали к числу самых грозных людей Европы во времена социальных потрясений XVII в. Они обладали незаурядным криптографическим талантом, что позволяло им расшифровывать письма врагов Франции (и личных врагов монарха). Они разработали Grande Chiffre (Великий шифр), сложный алгоритм замены слогов, используемый для шифрования самых важных писем короля. После смерти Россиньоль шифр вышел из употребления и считался невзламываемым. Лишь в 1890 г. специалист по криптографии, отставной солдат Этьен Базарье взял на себя трудоемкую задачу расшифровки документов и после многих лет напряженной работы смог прочитать секретные послания Короля-Солнца.

Людовик XIV , портрет работы Миньяра

Анонимный криптоаналитик

Английский математик Чарльз Бэббидж (1791–1871) был одним из самых выдающихся научных деятелей XIX в. Он изобрел механический компьютер, названный разностной машиной, далеко опередив свое время, и в сферу его интересов входили все отрасли математики и технологии того века. Бэббидж решил применить свои знания к расшифровке полиалфавитных алгоритмов, в первую очередь квадрата Виженера (см. стр. 44 и 47). Он сосредоточил внимание на одной особенности этого шифра. Напомним, что в случае шифра Виженера длина выбранного ключевого слова определяла количество используемых шифроалфавитов. Таким образом, если ключевое слово было WALK, каждая буква исходного сообщения могла быть зашифрована четырьмя разными способами. То же самое справедливо и для слов. Эта особенность и была ключевой зацепкой для Бэббиджа, позволившей ему взломать полиалфавитный шифр. Рассмотрим следующий пример, где сообщение зашифровано с помощью квадрата Виженера.

Наше внимание сразу привлекает то, что слово BY исходного сообщения шифруется в обоих случаях одинаково — XY. Это связано с тем, что второй раз BY встречается после восьми символов, а восемь кратно количеству букв (четыре) в ключевом слове (WALK). Обладая этой информацией и имея достаточно длинный исходный текст, можно догадаться, какова длина ключевого слова. Процедура заключается в следующем: вы отмечаете все повторяющиеся символы и записываете, через сколько позиций они повторяются. Затем вы находите все делители этих чисел. Общие делители и являются кандидатами на длину ключевого слова.

Предположим, что наиболее вероятный кандидат — число 5, потому что это общий делитель, который встречается чаще всего. Теперь мы попытаемся догадаться, каким буквам соответствует каждая из пяти букв ключевого слова. Как мы помним, каждая буква ключевого слова в квадрате Виженера определяет моноалфавитный шифр для соответствующей буквы в исходном сообщении. В случае нашего гипотетического ключевого слова из пяти букв (C1, С2, СЗ, С4, С5) шестая буква (С6) шифруется тем же алфавитом, что и первая буква (С1), седьмая (С7) — тем же, что и вторая (С2), и так далее. Поэтому на самом деле криптоаналитик имеет дело с пятью отдельными моноалфавитными шифрами, каждый из которых уязвим для традиционного криптоанализа.

Процесс завершается составлением таблицы частот для всех букв в зашифрованном тексте, соответствующих буквам ключевого слова (C1, С6, С11 … и С2, С7, С12 …). Таким образом, получается пять групп букв, вместе составляющих все сообщение. Затем, чтобы расшифровать ключевое слово, эти таблицы частот сравниваются с таблицами частот языка, на котором написано исходное сообщение.

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

Поразительные работы Бэббиджа, завершенные около 1854 г., так бы и остались в безвестности. Эксцентричный британский интеллектуал не опубликовал свое открытие, и только недавние исследования его записок показали, что именно он был пионером в расшифровке полиалфавитных ключевых слов. К счастью для криптоаналитиков всего мира, несколько лет спустя, в 1863 г., прусский офицер Фридрих Касиски опубликовал аналогичный метод.

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

Рабочая часть разностной машины Бэббиджа, построенной в 1991 г. в соответствии с чертежами, оставленными ее изобретателем. Устройство позволяет находить приближенные значения логарифмических и тригонометрических функций и, следовательно, делать расчеты астрономических таблиц. Бэббидж не успел при жизни увидеть свою машину.