Как взломать шифр Камасутры подсчетом

Книга: Тайны чисел: Математическая одиссея

Назад: Как использовать яйцо для отправки секретного сообщения

Дальше: Как математики способствовали победе во Второй мировой войне

B OBDFSOBDLNLBC, ILXS B QBLCDSV MV B QMSD, LE B OBXSV MH QBDDSVCE.

LH FLE QBDDSVCE BVS OMVS QSVOBCSCD DFBC DFSLVE, LD LE ASNBGES DFSJ BVS OBTS ZLDF LTSBE. DFS OBDFSOBDLNLBC’E QBDDSVCE, ILXS DFS QBLCDSV’E MV DFS QMSD’E OGED AS ASBGDLHGI; DFS LTSBE ILXS DFS NMIMGVE MV DFS ZMVTE, OGED HLD DMUSDFSV LC B FBVOMCLMGE ZBJ. ASBGDJ LE DFS HLVED DSED: DFSVS LE CM QSVOBCSCD QIBNS LC DFS ZMVIT HMV GUIJ OBDFSOBDLNE.

Походит на галиматью, но на самом деле это послание, написанное с использованием одного из самых популярных способов кодирования. Он называется шифром подстановки и состоит в замене каждой буквы алфавита какой-либо другой буквой: так, a может стать P, t может стать C и т. д. (Я использовал строчные буквы для незашифрованного сообщения – оно называется в криптографии открытым текстом – и прописные буквы для зашифрованного текста, или шифротекста.) Если отправитель и получатель сообщения заранее договорились об используемом шифре подстановки, то получатель сможет дешифровать послания, но всем остальным они будут казаться бессмысленными строками абракадабры.

Самая простая версия этих шифров называется сдвигом Цезаря – в честь Юлия Цезаря, который пользовался им для связи со своими военачальниками во время Галльских войн. Принцип его действия состоит в сдвиге каждой буквы на одинаковое число позиций в алфавите. Например, при сдвиге на 3 a становится D, b становится E и т. д. Вы можете загрузить с веб-сайта «Тайн 4исел» соответствующий файл и вырезать шифровальное колесо для создания этих простых сдвигов Цезаря.

Сдвижка на постоянное число позиций дает вам лишь 25 возможных шифров, так что, если вы понимаете, что сообщение было закодировано с помощью одного из них, становится совсем просто расшифровать его. Существует и лучший способ закодировать сообщение: вместо простого постоянного сдвига всех букв можно перемешать их и разрешить замену любой буквы произвольной другой буквой. Эта методика шифрования сообщений была предложена за несколько веков до Юлия Цезаря, удивительно, что она изложена не в военном руководстве, а в Камасутре. Хотя этот древний трактат на санскрите обычно ассоциируется с описанием плотских удовольствий, в нем описывается и несколько других искусств, которыми должна овладеть женщина: от заклинаний и игры в шахматы до переплетного дела и плотничества. А 45-я глава посвящена искусству тайных сообщений, и объясняется, насколько совершенен может быть шифр подстановки для сокрытия подробностей любовных связей.

В то время как имеется лишь 25 сдвигов Цезаря, число возможных шифров становится заметно больше, когда мы позволяем заменять любую букву любой другой. У нас есть 26 возможностей для того, что будет использовано вместо a, для каждой из этих возможностей имеется выбор из 25 букв для буквы b (одна буква уже была использована для кодирования a). Итак, имеется 26 × 25 различных способов зашифровать буквы a и b. Если мы продолжим выбирать другие буквы для оставшегося алфавита, то найдем, что имеется

26 × 25 × 24 × 23 × 22 × 21 × 20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

различных шифров Камасутры. Как мы видели на с. 40, это число обозначается 26!. Только нужно не забыть вычесть 1 из этого числа, потому что имеется вариант, когда А соответствует а, B соответствует b и так далее вплоть до Z, соответствующего z, что не является шифром. Когда мы вычислим 26! и вычтем 1, то придем к общему числу

403 291 461 126 605 635 583 999 999

различных шифров – более четырехсот миллионов миллиардов миллиардов возможностей.

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

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

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

Впервые криптоанализ, как называется наука о взламывании кода, был разработан арабами во время правления династии Аббасидов. Многогранный ученый IX в. Якуб аль-Кинди отметил, что в написанном тексте некоторые буквы появляются снова и снова, в то время как другие используются редко, как показано выше. Это то, что хорошо знакомо игрокам в скрэббл: за букву E, как за самую распространенную, дается лишь 1 очко, в то время как Z оценивается в 10 очков. В письменных текстах у каждой буквы есть выраженная «индивидуальность» – то, как часто она появляется и в каких комбинациях с другими буквами. Ключевым в анализе аль-Кинди является понимание того, что индивидуальность буквы сохраняется при ее замене другим символом.

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

Таблица 4.02. Частотное распределение букв в зашифрованном тексте

Из таблицы мы видим, что буква S встречается с частотой 13 %, это превосходит любую другую букву в шифротексте. Поэтому есть немалый шанс, что данная буква использовалась для кодирования e. (Разумеется, вам приходится надеяться, что я не выбрал для кодирования отрывок из романа Жоржа Перека «Исчезание», на всем протяжении которого не встречается буква e.) Следующей по употребительности буквой шифротекста, с частотой 12 %, является D. На втором месте по употребительности в английском языке находится буква t, поэтому она будет хорошим предположением для соответствия D. Третьей по частоте в шифротексте является буква B, которая используется в 10 % случаев, есть немалая вероятность, что она заменяет третью по употребительности букву английского языка а.

Давайте подставим эти буквы в текст и посмотрим, что у нас получилось:

a OatFeOatLNLaC, ILXe a QaLCteV MV a QMet, LE a OaXeV MH QatteVCE.

LH FLE QatteVCE aVe OMVe QeVOaCeCt tFaC tFeLVE, Lt LE AeNaGEe tFeJ aVe OaTe ZLtF LTeaE. tFe OatFeOatLNLaC’E QatteVCE, ILXe tFe QaLCteV’E MV tFe QMet’E OGEt Ae AeaGtLHGI; tFe LTeaE ILXe tFe NMIMGVE MV tFe ZMVTE, OGEt HLt tMUetFeV LC a FaVOMCLMGE ZaJ. AeaGtJ LE tFe HLVEt teEt: tFeVe LE CM QeVOaCeCt QIaNe LC tFe ZMVIT HMV GUIJ OatFeOatLNE.

Вы можете сказать, что текст по-прежнему выглядит как тарабарщина, но то обстоятельство, что буква а встречается сама по себе несколько раз, говорит нам, что, вероятно, мы декодировали ее правильно. (Конечно, могло оказаться так, что B заменяет i, в таком случае нам пришлось бы вернуться назад и попытаться еще раз.) Также мы замечаем, что довольно часто сталкиваемся со словом tFe, и можно быть уверенным, что это слово the. На самом деле буква F занимает 6 % шифротекста, а в английском языке буква h встречается в 6 % случаев.

Также мы видим слово Lt, в котором была декодирована лишь вторая буква. Есть лишь два слова из двух букв, заканчивающиеся на t: at и it. Мы уже декодировали а, значит, наверняка L нужно декодировать как i, и наша таблица частотного распределения подтверждает это. L появляется в шифротексте с частотой 8 %, и i встречается в английском языке с частотой 7 % – довольно близкое совпадение. Подобный анализ не является точной наукой, мы должны проявлять достаточную гибкость при использовании этой техники. Но чем длиннее текст, тем лучше будут подстраиваться частоты.

Давайте подставим две наши новые декодировки:

a OatheOatiNiaC, IiXe a QaiCteV MV a QMet, iE a OaXeV MH QatteVCE.

iH hiE QatteVCE aVe OMVe QeVOaCeCt thaC theiVE, it iE AeNaGEe theJ aVe OaTe Zith iTeaE. the OatheOatiNiaC’E QatteVCE, IiXe the QaiCteV’E MV the QMet’E OGEt Ae AeaGtiHGI; the iTeaE IiXe the NMIMGVE MV the ZMVTE, OGEt Hit tMUetheV iC a haVOMCiMGE ZaJ. AeaGtJ iE the HiVEt teEt: theVe iE CM QeVOaCeCt QIaNe iC the ZMVIT HMV GUIJ OatheOatiNE.

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

Простой арифметический прием подсчета букв означает, что любое сообщение, закодированное с помощью шифра подстановки, нельзя сделать секретным. Мария I, королева Шотландии, узнала это на собственном опыте. Она обменивалась посланиями, содержащими планы по убийству королевы Елизаветы I, с другим заговорщиком, Энтони Бабингтоном, при этом буквы в них заменялись странными символами (рис. 4.01).

Рис. 4.01. Шифр Бабингтона

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

Назад: Как использовать яйцо для отправки секретного сообщения

Дальше: Как математики способствовали победе во Второй мировой войне