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

Сотой Маркус дю

Глава 4

Случай кода, не поддающегося взлому

 

 

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

Код представляет собой систематический способ расположения набора символов, передающего определенное значение. Как только вы начнете искать коды, вы обнаружите, что они окружают нас повсюду: штрихкоды находятся на всем, что мы покупаем, коды позволяют нам хранить музыку на MP3-плеерах и просматривать информацию в интернете. Даже эта книга написана кодом: английский язык – это попросту код, использующий 26 букв алфавита, а наши «допустимые кодовые слова» собраны в Оксфордском словаре английского языка. Коды содержатся даже в наших телах – ДНК представляет собой код для воспроизведения живых существ. ДНК состоит из четырех органических химических веществ, называемых основаниями: аденина, гуанина, цитозина и тимина, для краткости обозначаемых A, G, C и Т.

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

 

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

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

В 499 г. до н. э. тиран по имени Гистией захотел послать тайное сообщение своему племяннику Аристагору, чтобы побудить его к восстанию против персидского царя. Гистией находился в Сузах, на территории современного Ирана, а его племянник был дома в Милете, который теперь принадлежит Турции. Но как же передать послание племяннику, чтобы персидские власти не перехватили его? Гистией придумал хитрый план. Он повелел своему верному слуге обрить голову и вытатуировал сообщение на его голой голове. Когда волосы отросли снова, Гистией отправил слугу к племяннику. Как только слуга приехал в Милет, племянник обрил ему голову, прочел послание и начал восстание против правившего персидского царя.

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

Более изощренный способ прятать сообщения был развит спартанцами в V в. до н. э. Они использовали специальный деревянный цилиндр, называемый «скитала». Вокруг него по спирали наматывалась узкая полоска пергамента. Затем секретное сообщение писалось на ней вдоль оси цилиндра. После того как полоска разматывалась, послание походило на тарабарщину. Требовалось намотать полоску на скиталу с такими же размерами, чтобы буквы снова правильно выстроились.

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

 

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

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. Шифр Бабингтона

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

 

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

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

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

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

Французский дипломат XVI в. Блез де Виженер считал, что для воспрепятствования частотному анализу будет достаточно переключаться между несколькими шифрами подстановки. Хотя шифр Виженера, как он стал известен, на самом деле является значительно более надежной формой кодирования, его все же можно взломать. Британский математик Чарльз Бэббидж в конечном счете нашел метод, позволяющий сделать это. Бэббидж по праву считается дедушкой компьютерного века: он был убежден, что машины можно использовать для автоматических вычислений, а в лондонском Музее науки можно увидеть реконструкцию его «Разностной машины» – механического аппарата для проведения вычислений. Именно систематический подход к решению задач способствовал тому, что в 1854 г. у него появилась идея, как взломать шифр Виженера.

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

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

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

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

Можно понять принцип работы машины «Энигма», если представить большой цилиндр, составленный из трех вращающихся барабанов. На верхнем основании цилиндра вблизи края расположены 26 отверстий, помеченных буквами алфавита. Чтобы закодировать букву, вы роняете шар в отверстие, соответствующее данной букве. Шар падает в первый барабан, у которого 26 отверстий вдоль обода наверху и 26 отверстий вдоль обода внизу. Верхние и нижние отверстия соединены трубками, которые не ведут напрямую от верхних отверстий к нижним, а извиваются сложным образом. В результате шар, попадающий наверху в барабан, выйдет внизу совершенно в другом положении. Средний и нижний барабан устроены схожим образом, но трубки, соединяющие их верхние и нижние отверстия, проложены по-своему. Когда шар падает из отверстия на дне третьего барабана, он попадает в конечную часть устройства, где 26 отверстий опять-таки помечены буквами алфавита.

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

Если бы устройство оставалось в таком же положении, то его действие сводилось бы к усложненному воспроизведению шифра подстановки. Но гениальность конструкции «Энигмы» состоит в том, что всякий раз, когда шар проходит через цилиндр, первый барабан поворачивается на 1/26 оборота. Поэтому, когда опускается следующий шар, первый барабан пошлет его совершенно по другому пути. Например, в первый раз буква а могла быть закодирована как С, но после того, как первый барабан повернулся на одну позицию, шар, брошенный в отверстие а, выйдет внизу в другом месте. Вот так и действовала машина «Энигма»: после кодирования первой буквы первый вращающийся диск поворачивался на одну позицию.

Вращение дисков в каком-то смысле соответствует одометру: после того как первый диск поворачивается на все 26 позиций и возвращается в начальное положение, он поворачивает второй диск на 1/26 оборота. Итак, имеется 26 × 26 × 26 различных способов шифровать буквы. Кроме того, оператор «Энигмы» мог менять порядок расположения дисков, что сводится к умножению количества возможных шифров подстановки на 6 (или 3! различных способов расположения трех дисков).

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

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

Польские математики поняли, что каждая из установок дисков характеризовалась своими особенностями в закодированных сообщениях, и этими закономерностями можно было воспользоваться для декодирования сообщений. Если, к примеру, оператор печатал а, то в зависимости от установки дисков эта буква кодировалась, скажем, как D. Затем первый диск поворачивался на одну позицию. Если оператор еще раз нажимал а и она кодировалась как Z, то в каком-то смысле связь D с Z определяется установкой дисков.

Мы могли бы исследовать это с помощью нашего приспособления. Устанавливая барабаны в требуемое положение и опуская по очереди в каждое из отверстий два шара, мы могли бы составить полный набор взаимосвязей, который мог бы выглядеть следующим образом (см. таблицу 4.03).

Таблица 4.03

Каждая буква появляется в каждой строке один, и только один, раз, потому что каждая строка соответствует одному шифру подстановки.

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

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

Для онлайн-моделирования работы машины «Энигма» воспользуйтесь ссылкой http://bit.ly/BletchleyPark . С веб-сайта «Тайн 4исел» вы можете загрузить PDF-файл с инструкциями, как сделать собственную машину «Энигма».

 

Передача сообщения на расстояние

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

Визуальные коды, основанные на флагах, восходят к 1684 г., когда Роберт Гук, один из самых знаменитых ученых ХVII в., представил эту идею Лондонскому Королевскому обществу. Изобретение телескопа сделало возможным передавать оптические сигналы на большие расстояния, но Гука подстегнуло то, что привело к многим техническим достижениям, – война. В предшествовавшем году Вена чуть не была захвачена турецкой армией, в то время как вся Европа не знала об этой опасности. Внезапно стало крайне необходимым придумать способ быстрой передачи сообщений на большие расстояния.

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

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

Рис. 4.03. Код братьев Шапп передавался с помощью шарнирно скрепленных деревянных планок

Братья разработали код для подвижной системы шарнирно скрепленных деревянных планок, чтобы обозначать различные буквы или некоторые слова. Основная поперечина могла быть установлена под четырьмя различными углами, в то время как у каждой из двух меньших планок было семь различных положений, что в общей сложности предоставляло возможность передавать 7 × 7 × 4 = 196 различных символов. Хотя часть кода использовалась для передачи публичных сообщений, 92 символа, объединенные в пары, представляли секретный код, что давало 92 × 92 = 8464 различных слова и фразы.

Рис. 4.04. Представление букв и цифр в коммуникационной системе братьев Шапп

Во время первого испытания 2 марта 1791 г. братья Шапп успешно передали сообщение «Если преуспеете, то покроете себя славой» на расстояние в 10 миль (160 км). Правительство было весьма впечатлено предложением братьев, и через четыре года во Франции была воздвигнута система башен и планок, протянувшаяся через всю страну. В 1794 г. одна из линий башен успешно передала менее чем за час на расстояние в 143 мили (230 км) сообщение о том, что французы отвоевали у австрийцев город Конде-сюр-л’Эско. К сожалению, успех не привел к славе вопреки предсказанию первого сообщения. Клод Шапп впал в такую депрессию от слухов, будто он украл многое из существовавшей у военных семафорной системы, что утопился в колодце.

Но вскоре деревянные планки на верхушках башен стали вытесняться флагами, их же стали использовать моряки для обмена сообщениями на море, ведь требовалось только помахать ими, находясь в поле видимости других судов. Наверное, самое знаменитое кодированное сообщение, которое было послано кораблям посредством флагов, изображено на рис. 4.05. Оно было передано 21 октября 1805 г. в 11:45.

Рис. 4.05. Знаменитое послание адмирала Нельсона «Англия ждет, что каждый выполнит свой долг»

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

Код был основан на комбинациях десяти различных флагов, причем каждый из них представлял одну из цифр от 0 до 9. Флаги поднимались на мачты корабля тройками, таким образом обозначая число от 000 до 999. Получатель сообщения глядел в свой кодовый словарь, чтобы понять, какое из слов было зашифровано. England (Англия) кодировалась числом 253, а для слова every (каждый) использовалось число 261. Некоторых слов, к примеру duty (долг), не было в словаре, и их нужно было набрать флагами, зарезервированными для отдельных букв. Первоначально Нельсон хотел послать сообщение «Англия верит, что каждый выполнит свой долг», имея в виду, что Англия была уверена. Но сигнальный офицер, лейтенант Джон Паско, не мог найти слова confides (верит) в кодовом словаре. Вместо того чтобы набирать его по буквам, он вежливо предложил Нельсону употребить имевшееся в словаре слово expects (ждет), как более уместное.

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

Рис. 4.06. Семафорная азбука

Чтобы узнать, как выглядит то или иное сообщение на семафоре, посетите сайт http://bit.ly/Scoutsemaphore  или воспользуйтесь смартфоном и сосканируйте QR-код.

NUJV!

The Beatles на обложке своего альбома Help! , очевидно, используют семафор, чтобы объявить название. Но, если вы декодируете показываемые ими семафорные знаки, то получится не HELP, a NUJV (рис. 4.07). Роберт Фримен, в голову которому пришла идея о семафоре на обложке, объяснял: «Когда дело дошло до фотографирования, то расположение рук с правильными буквами выглядело не слишком хорошо. Поэтому мы решили импровизировать, и остановились на визуально оптимальном положении рук». На самом деле они должны были показывать так (рис. 4.08):

Рис. 4.07

Рис. 4.08

Как мы увидим, The Beatles – вовсе не единственный ансамбль, неправильно использовавший код на обложке альбома.

Рис. 4.09. Знаете ли вы, что пацифистский символ, использующийся Движением за ядерное разоружение, на самом деле задействует семафорную азбуку? Он представляет буквы N и D (Nuclear Disarmament, ядерное разоружение), объединенные в один символ

 

Какое сообщение закодировано в Симфонии № 5 Бетховена?

Начало Симфонии № 5 Бетховена – три короткие ноты, за которыми следует длинная, – одно из самых знаменитых в истории музыки. Но почему радиостанция Би-би-си начинала каждый выпуск новостей во время Второй мировой войны с известного мотива Бетховена? Ответ состоит в том, что в нем содержалось закодированное сообщение. Этот новый код опирался на технику, умевшую посылать сигналы по проводам в виде последовательности электромагнитных импульсов.

Одним из первых людей, экспериментировавших с этим видом связи, был Карл Фридрих Гаусс. С его исследованиями по простым числам мы познакомились в главе 1. Но Гаусс интересовался не только математикой, но и физикой, включая развивавшуюся область электромагнетизма. Он и физик Вильгельм Вебер протянули километр провода от лаборатории Вебера в Гёттингене до обсерватории, где жил Гаусс, чтобы посылать сообщения друг другу.

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

Таблица 4.04. Код Гаусса – Вебера

Вебер был настолько воодушевлен потенциалом их открытия, что пророчески заявил:

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

Для реализации потенциала электромагнетизма по передаче сообщений было предложено множество различных кодов. Однако код, разработанный американцем Сэмюэлом Морзе в 1838 г., был настолько успешен, что вытеснил все остальные. Подобно схеме Гаусса – Вебера, в нем каждая буква превращалась в комбинацию длинных и коротких импульсов электричества – тире и точек.

Рис. 4.10. Код Морзе

Логика, которой руководствовался Морзе при создании кода, в чем-то соответствует частотному анализу, используемому дешифровщиками для того, чтобы взломать шифр подстановки. Наиболее употребительные буквы английского алфавита – e и t, поэтому имеет смысл использовать максимально короткие последовательности для их кодирования. Поэтому e представляется точкой, коротким импульсом электричества, а t – тире, длинным импульсом. Для менее употребительных букв задействуются более длительные последовательности. Так, z соответствует тире-тире-точка-точка.

С помощью кода Морзе мы можем расшифровать сообщение, спрятанное в Симфонии № 5 Бетховена. Если мы интерпретируем драматичное начало этого произведения как код Морзе, то соотнесем последовательность точка-точка-точка-тире с буквой v, которой Би-би-си символизировала победу (victory).

Разумеется, Бетховен не собирался прятать в своей музыке сообщения на морзянке, ведь он умер до того, как она была изобретена. Но другие композиторы использовали ее ритмическую структуру, чтобы придать дополнительный смысл своим произведениям. Мелодия, сопровождающая знаменитый детективный сериал «Инспектор Морс» (Inspector Morse), совершенно оправданно начинается с ритмической последовательности, воспроизводящей фамилию детектива на коде Морзе:

Рис. 4.11. Код Морса

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

Несмотря на то что код Морзе крайне широко использовался, причем не только композиторами, но и телеграфными операторами по всему миру, в нем имеется врожденная проблема. Если вы приняли точку, за которой следует тире, то как нужно декодировать эту последовательность? С одной стороны, она отвечает букве a, с другой стороны, это может быть буква e, за которой следует t. В результате математики предложили иной вид кода, использующий последовательности 0 и 1, который лучше подходит для восприятия машинами.

 

Как называется третий альбом группы Coldplay?

Когда фанаты устремились за покупкой третьего альбома группы Coldplay, выпущенного в 2005 г., они были сильно заинтригованы рисунком на обложке, пытаясь постичь его смысл. На нем были изображены расположенные на сетке разноцветные прямоугольники. В чем же заключалось значение картинки? Оказалось, она представляла название альбома, написанное с помощью одного из первых двоичных кодов, предложенного в 1870 г. французским инженером Эмилем Бодо. Цвета на рисунке не имели значения: смысл был лишь в том, что каждый прямоугольник представлял 1, а каждый пропуск нужно было истолковать как 0.

Немецкий математик XVII в. Готфрид Лейбниц одним из первых осознал приспособленность нулей и единиц к эффективному хранению информации. Он почерпнул эту идею из китайской «И цзин» – «Книги перемен», где исследуется динамический баланс противоположностей. В ней имелись 64 графических символа, называемые гексаграммами, каждый из которых представляет ту или иную ситуацию с точки зрения ее развития. Именно они побудили Лейбница создать двоичную математику (с ней мы познакомились в предыдущей главе, когда изучали выигрышную стратегию «Ним»). Каждая гексаграмма представляет стопку из шести горизонтальных линий, причем любая из линий либо цельная, либо прерванная посередине. В «И цзин» объясняется, как эти символы могут использоваться для гадания, в котором также совершаются подбрасывания монеток и веточек.

Например, если у прорицателя выпадет гексаграмма, изображенная на рис. 4.12, то она будет означать «тяжбу».

Но если линии сложатся иным образом и цельные поменяются с прерванными (рис. 4.13), то получится «поражение света».

Рис. 4.12

Рис. 4.13

Однако Лейбница больше заинтересовало то обстоятельство, что, как отметил Шао Юн, китайский философ XI в., каждому символу может быть приписано число. Если вы будете обозначать единицей сплошную линию, а нулем прерванную, то первая гексаграмма при чтении сверху вниз даст вам 111010. В числах, записанных в десятичной системе, каждый разряд соответствует степени 10, и число в этом разряде говорит вам, сколько этих степеней десяти нужно взять. Так, 234 обозначает 4 единицы, 3 десятка и 2 сотни.

Но Лейбниц и Шао Юн работали не в десятичной, а в двоичной системе, где каждый разряд соответствовал степени 2. Число 111010 в двоичной системе обозначает отсутствие единиц, одну двойку, отсутствие четверки, одну восьмерку, один набор из 16 и один набор из 32. При сложении мы получим 2 + 8 + 16 + 32 = 58. Красота двоичной записи заключается в том, что для представления любого числа нужны лишь два символа, вместо десяти в десятичной системе. Два (десятичных) набора по 16 становятся одним набором следующей степени 2, то есть 32.

Лейбниц понял, что этот способ представления чисел становится крайне действенным, если вы хотите автоматизировать вычисления. Правила сложения двоичных чисел крайне просты. В каждом разряде 0 + 1 = 1, 1 + 0 = 1 и 0 + 0 = 0. Четвертая возможность заключается в 1 + 1 = 0, что сопровождается эффектом домино – 1 переносится и прибавляется к следующему разряду слева. Например, когда мы прибавляем 1000 к 111010, то видим каскад перемещений 1 к высшим разрядам:

1000 + 111010 = 10000 + 110010 = 100000 + 100010 = 1000000 + 000010 = 1000010.

Лейбниц сконструировал великолепные механические калькуляторы. В одном из них использовались шарики для обозначения 1, а отсутствие шарика представляло 0, так что процесс сложения напоминал фантастическую машину для пинбола. Лейбниц полагал, что «не пристало одаренному человеку тратить, подобно рабу, часы на вычислительный труд, который можно надежно доверить любому лицу при использовании машин». Я думаю, что большинство математиков согласятся с этим.

Люди начали обозначать цепочками 0 и 1 не только числа, но и буквы. Хотя человеческому роду код Морзе представлялся мощным инструментом для коммуникации, машины были менее приспособлены к улавливанию тонких различий между точками и тире, прописывающими буквы, и пониманию того, когда закончилась предыдущая буква и началась следующая.