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

Код представляет собой систематический способ расположения набора символов, передающего определенное значение. Как только вы начнете искать коды, вы обнаружите, что они окружают нас повсюду: штрихкоды находятся на всем, что мы покупаем, коды позволяют нам хранить музыку на 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 не только числа, но и буквы. Хотя человеческому роду код Морзе представлялся мощным инструментом для коммуникации, машины были менее приспособлены к улавливанию тонких различий между точками и тире, прописывающими буквы, и пониманию того, когда закончилась предыдущая буква и началась следующая.

Рис. 4.14. Реконструкция двоичного калькулятора Лейбница

В 1874 г. Эмиль Бодо предложил кодировать каждую букву алфавита цепочкой из пяти нулей и единиц. Благодаря одинаковой длине обозначений всех букв стало совершенно очевидно, где заканчивалась предыдущая буква и начиналась следующая. Использование пяти 0 и 1 позволило Бодо представить в общей сложности 2 × 2 × 2 × 2 × 2 = 32 различных символа. Буква Х соответствовала цепочке 10111, а Y обозначалась как 10101. Это было огромным прорывом, потому что сообщения теперь могли кодироваться на бумажной ленте, на которой перфорировались отверстия для обозначения 1, а отсутствие отверстия соответствовало 0. Машина могла считывать эту ленту и посылать сигнал по проводному соединению с высокой скоростью, а на другом конце телетайп автоматически распечатывал сообщение.

Со временем код Бодо был вытеснен на обочину огромным разнообразием других кодов, использующих ту же идею представления всего, от текста до звуковых волн, от jpeg-изображений до видеофайлов, с помощью 0 и 1. Каждый раз, когда вы заходите на iTunes и скачиваете трек Coldplay, ваш компьютер подвергается натиску огромной армии 0 и 1, которые декодируются вашим MP3-проигрывателем. Внутри этих чисел содержатся указания, предписывающие, как вибрировать вашим колонкам или наушникам, чтобы вы могли услышать сладкий голос Криса Мартина. Наверное, то обстоятельство, что в наш цифровой век музыка представляет поток 0 и 1, и вдохновило на создание обложки третьего альбома Coldplay.

Но ключом к пониманию секретного сообщения, погруженного в рисунок на обложке, служит исходный код Бодо. Узор может быть разделен на четыре столбца с пятью блоками в каждом столбце. Окрашенные блоки нужно интерпретировать как 1, а пропуски – как 0. Поскольку порою трудно сказать, какой край ленты должен быть сверху, машина перфорирует тонкую линию, отделяющую два верхних блока от трех нижних. Вот почему на рисунке обложки видна линия, разделяющая серые и цветные блоки.

Рис. 4.15. На обложке третьего альбома группы Coldplay используется код Бодо

Блоки первого столбца обложки чередуются как цветной-пустой-цветной-цветной-цветной, что переводится в 10111, а это код Бодо для Х. Последний столбец становится кодом Бодо для Y. Два средних столбца чуть интереснее. Пять нулей и единиц дают возможность закодировать 32 символа, но очень часто требуется большее, поскольку имеются числа, знаки пунктуации и другие символы, которые также хотелось бы передать. Чтобы удовлетворить этим требованиям, Бодо нашел хитрый способ расширить допустимый диапазон. Вспомните, как на клавиатуре нажимается Shift для доступа ко всему набору символов при использовании тех же клавиш, и Бодо использовал одну из цепочек из 5 нулей и единиц в качестве эквивалента Shift. Итак, если вам встретится 11011, то следующая цепочка будет относиться к расширенному набору символов.

Этот веб-сайт позволит вам создать собственные обложки альбомов в стиле Coldplay: http://bit.ly/Coldcod .

Второй столбец на обложке как раз и представляет клавишу Shift для кода Бодо. Чтобы декодировать последовательность пустой-пустой-пустой-цветной-цветной третьего столбца, нужно обратиться к расширенному набору символов, показанному на схеме ниже. И уверен, что большинство людей ожидает увидеть символ &. Но 00011 обозначает не &, а цифру 9. Итак, настоящим названием третьего альбома Coldplay, изображенным с помощью кода Бодо, будет X9Y, а не X&Y. Подшутила ли группа Coldplay над нами? Возможно, нет. Ведь код Бодо для 9 и & различается лишь на один блок, и, скорее всего, на рисунке допущена ошибка, которая наглядно иллюстрирует проблему с многими из этих кодов: трудно сказать, совершен ли промах. Именно в детектировании подобных ошибок математика кодов в полной мере проявляет себя.

Рис. 4.16. Код Бодо

 

Какое из этих чисел будет кодом книги: 0521447712 или 0521095788?

Я уверен, что вы видели ISBN, Международный стандартный книжный номер (International Standard Book Number), на обложке каждой книги. Его 10 цифр однозначно идентифицируют книгу, а также сообщают о стране происхождения и об издательстве. Но это отнюдь не все, что делает код. В ISBN также встроено немного магии.

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

Вот подлинные ISBN некоторых моих любимых книг:

Таблица 4.05

Под каждой цифрой я привел результат умножения на ее порядковый номер в коде. Так, в первом ISBN 0 умножается на 1, 5 на 2, 2 на 3 и т. д. Затем я сложил все новые числа и написал полученную сумму в конце строки. Вы заметили особенность чисел, приготовленных по этому рецепту из ISBN? А вот результат вычислений с использованием некоторых других настоящих ISBN: 264, 99, 253.

Вы подметили закономерность? Расчет всегда приводит к числу, которое делится на 11. Это не чудесное совпадение, а следствие искусного математического замысла. Информация о книге содержится только в первых девяти цифрах. А десятая цифра добавляется в ISBN таким образом, чтобы результат вычислений по данному рецепту был кратен 11. Вы могли заметить, что у некоторых книг на последней позиции находится Х вместо арабской цифры. Например, у другой моей любимой книги следующий ISBN: 080501246X. X просто обозначает 10 (вспомните римские числа). В этом случае потребовалось дописать 10 в конец ISBN, чтобы результат вычисления делился на 11.

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

Поскольку книги продолжают издаваться в больших количествах, номера ISBN начали заканчиваться. Поэтому было решено, что с 1 января 2007 г. в ISBN будет 13 цифр. 12 из них по-прежнему идентифицируют книгу, издателя и страну происхождения, а тринадцатая будет отслеживать, не вкрались ли ошибки. Но ключевым для номера ISBN теперь является делимость на 10, а не на 11. Найдите номер ISBN этой книги. В нем 13 цифр. Сложите 2, 4, 6, 8, 10 и 12-ю цифру, а сумму умножьте на 3. Теперь прибавьте к промежуточному результату все остальные цифры. Итоговый результат будет делиться на 10. Если же вы сделали ошибку при записи номера ISBN, то у вас, скорее всего, получится число, которое не делится на 10.

 

Как использовать коды для чтения мыслей

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

Таблица 4.06

Потом вы говорите: «Через минуту я попрошу тебя перевернуть одну из монет, после чего я прочитаю твои мысли и скажу, какую именно ты перевернул. Ты можешь решить, что я могу запомнить порядок 25 монет, поэтому давай сделаем мою задачу еще более сложной и увеличим квадрат».

Затем вы добавляете монеты, создав дополнительный ряд и столбец, так что получается сетка 6 × 6. На первый взгляд вы распределяете орлы и решки случайно… хотя на самом деле это вовсе не так. Вы считаете, сколько решек имеется в каждом ряду и каждом столбце начиная с первого столбца. Если в первом столбце нечетное число решек, то положите дополнительную монету в первом столбце решкой вверх. Если же число решек четно (0 считается четным числом), то положите дополнительную монету в конец первого столбца вверх орлом.

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

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

Таблица 4.07

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

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

Теперь вы, скорее всего, сумеете определить, какая монета была перевернута на данной сетке:

Таблица 4.08

В первом столбце сетки 5 × 5 четное число решек, но добавленная вами монета лежит решкой вверх, указывая, что изначально там было нечетное число решек. Итак, монета, перевернутая вашим другом, находится в первом столбце. Перейдем теперь к рядам. Во втором ряду наблюдается рассогласование: там нечетное число решек, но ваша «контрольная цифра» говорит, что должно быть четное число. Теперь вы можете прочесть мысли вашего друга и возвестить: «Ты перевернул монету в первом столбце, во втором ряду». Вас ждет взрыв аплодисментов впечатленной публики.

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

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

Таблица 4.09

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

Подобные приемы лежат в основе так называемого кода с коррекцией ошибок, применяемого компьютерами для исправления ошибок, которые могли вкрасться в сообщения при их передаче. Замените орлы и решки на нули и единицы, и внезапно сетка становится цифровым сообщением. Например, каждый столбец в сетке 5 × 5, первоначально выложенной для показа фокуса, мог бы представлять букву в коде Бодо. Тогда сетка 5 × 5 стала бы сообщением длиной в пять букв. Дополнительные строки и столбцы добавляются компьютером для отслеживания ошибок.

Следовательно, пожелай мы отправить кодированное сообщение о третьем альбоме Coldplay, можно воспользоваться тем же приемом, что и ранее, примененным к сетке 5 × 4. Это даст возможность понять, где и когда вкрадываются ошибки. Вот как должно выглядеть название альбома, если цветные блоки заменить на 1, а пропуски на 0:

Таблица 4.10

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

Таблица 4.11

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

Таблица 4.12

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

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

 

Как честно кидать монету через интернет

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

Чтобы объяснить его идею, давайте начнем с простого сценария. Я собираюсь играть в шахматы через интернет. Я живу в Лондоне, а мой соперник – в Токио. Мы хотим бросить монету, чтобы решить, кто будет ходить первым. «Орел или решка?» – спрашиваю я у своего соперника по электронной почте. «Орел», – отвечает он. Я подбрасываю монету и пишу: «Решка. Я начинаю». Существует ли возможность удостовериться, что я не сжульничал?

Как это ни поразительно, вы можете честно бросать монету через интернет. Такая возможность появляется благодаря математике простых чисел. Все простые числа нечетны за исключением 2 (это странное простое число, ведь лишь оно четно). Если мы разделим одно из этих нечетных простых чисел на 4, то получим в остатке 1 или 3. Например, остаток от деления 17 на 4 равен 1, а при делении 23 на 4 в остатке получается 3.

Как мы узнали в главе 1, две тысячи лет назад древние греки доказали, что существует бесконечно много простых чисел. Но существует ли бесконечно много тех из них, которые дают при делении на 4 остаток 1, или бесконечно много дающих остаток 3? Это один из тех вопросов, которые Пьер де Ферма поставил перед математиками 350 лет назад, однако ответ был дан лишь в XIX в. немецким математиком Густавом Лежёном Дирихле. Используя очень сложный математический аппарат, он сумел доказать, что половина простых чисел дает остаток 1, а другая половина 3 – никакой из остатков не оказывается предпочтительнее. Впрочем, не совсем легко понять, что математики имеют в виду под половиной, когда речь идет о бесконечном множестве. Но, по существу, это означает, что если вы возьмете простые числа, меньшие заданного большого числа, то почти в точности половина из них даст при делении на 4 остаток 1.

Итак, остаток 1 или 3 при делении простого числа на 4 не более «предвзят», чем выпадение орла или решки при подкидывании честной монеты. Для изучения нашей задачи по бросанию монеты давайте отождествим орлы с простыми числами, дающими остаток 1 при делении на 4, а с решками мы отождествим простые числа, дающие остаток 3. А теперь последует искусный математический пассаж. Если я возьму два простых числа, скажем 17 и 41, оба из которых относятся к орлам – они дают остаток 1 при делении на 4, – и перемножу их, то произведение также будет характеризоваться остатком 1 при делении на 4. Например, 41 × 17 = 697 = 174 × 4 + 1. Если же я возьму два простых числа, скажем 23 и 43, оба из набора решек – они дают остаток 3 при делении на 4… то получится не то, чего вы могли бы ожидать. У произведения этих двух чисел при делении на 4 также будет остаток 1: в данном случае 23 × 43 = 989 = 247 × 4 + 1. Итак, произведение простых чисел не дает намека на то, взяты ли сомножители из набора орлов или из набора решек. Этим свойством мы можем воспользоваться, чтобы играть в «орла или решку по интернету».

Если я подброшу монету и выпадет орел, я выберу два простых числа из набора орлов и перемножу их. Если выпадет решка, я выберу два простых числа из набора решек и перемножу их. После того как я подкинул свою монету и сделал вычисления, я посылаю ответ моему сопернику в Токио. Оказалось, что он равен 6497. Поскольку ответ при делении на 4 всегда дает остаток 1, мой соперник не может, не зная простых чисел, сказать, выбрал ли я их из набора орлов или же из набора решек. Теперь он может сказать «орел» или «решка».

Чтобы мой соперник убедился, что он выиграл или проиграл, мне достаточно будет выслать ему два выбранных мною простых числа. В данном случае ими были 89 и 73, два простых числа из набора орлов. Поскольку никакие другие числа при перемножении не дадут 6497, то я предоставил ему достаточно информации, чтобы доказать, что я не жульничал. С другой стороны, я не предоставил ему достаточно информации, чтобы мой соперник мог жульничать.

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

Легкое задание

Я бросил монету, выбрал два простых числа из набора орлов или из набора решек и перемножил их. У меня получилось число 13 068 221. Что выпало? Орел или решка? Постарайтесь найти ответ без компьютера (решение приведено в конце главы).

Трудное задание

А что скажете, если получилось число

5 759 602 149 240 247 876 857 994 004 081 295 363 338

151 725 852 938 901 132 472 828 171 992 873 665 524 051

005 072 817 707 778 665 601 229 693?

На этот раз можно использовать компьютер.

 

Почему разложение чисел означает взлом кода?

Боб – администратор веб-сайта, продающего футболки в Англии. Элис живет в Сиднее, и она намеревается купить футболку на сайте и при этом послать данные своей кредитной карты так, чтобы никто другой не смог увидеть их. Боб размещает специальное кодовое число на своем веб-сайте, скажем 126 619. Это кодовое число чем-то напоминает ключ, который запирает сообщение Элис и делает его защищенным. Поэтому, когда Элис посещает веб-сайт, она получает копию кодирующего ключа, опубликованного Бобом, и использует его, чтобы «запереть» свою кредитную карту.

В реальности компьютер Элис совершает специальное математическое вычисление, использующее этот ключ, 126 619, и номер ее кредитной карты. Теперь этот номер зашифрован и может быть послан открытым образом через интернет на веб-сайт Боба. (Детали упомянутого вычисления приведены в следующем разделе.) Но постойте, разве при этом не возникнет проблема? Предположим, я хакер. Тогда что помешает мне посетить веб-сайт Боба, получить копию кодирующего ключа и расшифровать сообщение? Однако кодирование в интернете устроено довольно интригующе: вам нужен другой ключ, чтобы отпереть дверь, а этот отпирающий ключ хранится в большом секрете в офисе Боба.

Декодирующий ключ представляет собой два простых числа, которые при умножении дают то самое число 126 619. В действительности Боб выбирает два простых числа 127 и 997, чтобы изготовить свой кодирующий ключ. Именно с помощью этих двух простых чисел Боб дешифрует то математическое вычисление, которое совершил компьютер Элис, чтобы закодировать номер ее кредитной карты. Боб поместил кодирующий ключ 126 619 на своем веб-сайте, но хранит в тайне декодирующие простые числа 127 и 997.

Если я смогу найти два простых числа, которые при умножении дают 126 619, я сумею получить доступ к номерам кредитных карт, посылаемым на веб-сайт Боба. Но 126 619 – достаточно небольшое число, чтобы я мог делить его на одно число за другим. Так, потратив не слишком много времени, я нашел бы два простых числа 127 и 997. Однако вы не сможете воспользоваться этим приемом на настоящих веб-сайтах, потому что их ключи основаны на значительно бо́льших числах – они настолько велики, что найти пару простых чисел методом проб и ошибок почти невозможно. Математики, придумавшие эти коды, были настолько уверены в их надежности, что на протяжении многих лет предлагали приз $ 200 000 тому, кто сможет найти два простых множителя следующего числа из 617 цифр:

25 195 908 475 657 893 494 027 183 240 048 398 571 429

282 126 204 032 027 777 137 836 043 662 020 707 595 556

264 018 525 880 784 406 918 290 641 249 515 082 189 298

559 149 176 184 502 808 489 120 072 844 992 687 392 807

287 776 735 971 418 347 270 261 896 375 014 971 824 691

165 077 613 379 859 095 700 097 330 459 748 808 428 401

797 429 100 642 458 691 817 195 118 746 121 515 172 654

632 282 216 869 987 549 182 422 433 637 259 085 141 865

462 043 576 798 423 387 184 774 447 920 739 934 236 584

823 824 281 198 163 815 010 674 810 451 660 377 306 056

201 619 676 256 133 844 143 603 833 904 414 952 634 432

190 114 657 544 454 178 424 020 924 616 515 723 350 778

707 749 817 125 772 467 962 926 386 356 373 289 912 154

831 438 167 899 885 040 445 364 023 527 381 951 378 636

564 391 212 010 397 122 822 120 720 357.

Если вы попытаетесь взломать это число из 617 цифр, поочередно пробуя одно простое число за другим, вы переберете больше чисел, чем имеется атомов во Вселенной, до того, как доберетесь до множителей. Неудивительно, что никто не подал заявку на приз, и в 2007 г. данное предложение было снято.

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

 

Что такое часовой калькулятор?

Передовые коды, которые используются в интернете, на самом деле опираются на математическое изобретение, которому сотни лет, сделанному, когда никто и не мечтал об интернете. Я имею в виду часовой калькулятор. В следующем разделе мы узнаем, как часовые калькуляторы используются при кодировании в интернете, но сначала давайте познакомимся с принципом их работы. Сперва рассмотрим случай 12-часового циферблата. Мы все знакомы со сложением на таких часах – мы понимаем, что через четыре часа после 9 будет 1 час. Это то же самое, что сложение чисел с последующим нахождением остатка при делении суммы на 12. Данное действие можно записать так:

4 + 9 = 1 (modulo 12).

Мы пишем «modulo 12», потому что 12 – это модуль, точка, после которой числа стартуют снова. Мы можем находить подобные суммы и на часах с другим количеством часовых делений, не ограничиваясь двенадцатью. Так, в случае 10 часов на циферблате:

9 + 4 = 3 (modulo 10).

А как умножаются числа на часовом калькуляторе? Умножение сводится к прибавлению определенное количество раз. Например, 4 × 9 означает, что нужно взять четыре девятки и сложить их вместе. Где окажется стрелка на 12-часовом циферблате после сложения четырех девяток? 9 + 9 – то же самое, что 6 часов. Каждый раз, когда мы прибавляем последующую девятку, часовая стрелка движется назад на 3 часа. В конце она окажется на 12 часах. Поскольку 0 – крайне важное число в математике, мы далее будем называть это положение, которое заканчивает круг и начинает следующий, 0 часов. Итак, у нас получится странный на вид ответ:

4 × 9 = 0 (modulo 12).

А как будет происходить возведение какого-либо числа в степень? Давайте рассмотрим 94, что означает перемножение четырех девяток. Мы только что научились делать модульное умножение, поэтому должны легко справиться и с этим. Поскольку числа становятся большими, будет легче взять остаток от деления на 12, чем следить за числами на часах. Начнем с 9 × 9, что равняется 81. Каков будет остаток при делении на 12, другими словами, чему соответствует 81 час на циферблате? Оказывается, остаток равен снова 9. Сколько бы мы ни перемножали 9, всякий раз мы опять придем к 9:

9 × 9 = 9 × 9 × 9 = 9 × 9 × 9 × 9 = 9 4  = 9 (modulo 12).

Ответ на часовом калькуляторе можно получить, сделав вычисления на обычном калькуляторе и затем взяв остаток от деления на число часовых делений. Но сила часового калькулятора состоит в том, что часто вам вовсе не требуется совершать вычисление на обычном калькуляторе. Вы можете найти, чему равно 799, на 12-часовом калькуляторе? Подсказка: сначала вычислите 7 × 7, а потом снова умножьте результат на 7. Вы видите закономерность?

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

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

Таблица 4.13

Поскольку число 5 – простое, при возведении 2 в пятую степень на 5-часовом калькуляторе получится снова 2. Итак, 25 =2 (modulo 5). Магия будет гарантированно работать, если на калькуляторе простое число часов. Она может не удаться, если вы возьмете калькулятор с составным числом часов. Например, 6 – составное число, и на 6-часовом калькуляторе 26оказывается равным не 2, а 4.

По мере того как стрелка перемещается по часам, начинает проступать закономерность. Поскольку после p – 1 шагов мы гарантированно возвращаемся в то место, с которого стартовали, последовательность начинает повторяться через p – 1 шаг. Порою последовательность повторяется несколько раз на протяжении p – 1 шагов. Вот что мы увидим на циферблате с 13 часами, когда будем возводить 3 в последовательные степени 3¹, 3² и так далее вплоть до 3¹³:

3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3.

Стрелка не посещает все деления на часах, тем не менее по-прежнему имеется повторяющаяся закономерность, которая приводит стрелку назад к 3 часам после перемножения тринадцати троек.

Мы уже сталкивались с похожей математикой в главе 3, когда рассматривали жульнический прием совершенных тасовок в покере. Там мы варьировали число карт в колоде и задавались вопросом, сколько совершенных тасовок необходимо сделать, чтобы карты возвратились к первоначальному расположению. В колоде с 2N картами порою необходимо выполнить все 2N – 2 совершенных тасовок, но бывает, их требуется сделать значительно меньше. Если в колоде 52 карты, то после всего лишь 8 совершенных тасовок они вернутся к исходному расположению. Но колода с 54 картами требует 52 совершенных тасовок.

Ферма никогда не излагал в полной мере свои рассуждения, поэтому он оставил в виде задания для будущих поколений математиков объяснение своего открытия, что магия всегда срабатывает для часов с простым числом делений. В конечном счете доказательство было найдено Леонардом Эйлером.

Малая теорема Ферма

Ниже приведено объяснение малой теоремы Ферма. Теорема утверждает, что в случае циферблата с простым числом p часовых делений

A p  =   A (modulo p ).

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

В качестве первого шага рассмотрим простой случай. Если A  = 0, то теорема верна, потому что сколько бы раз мы ни умножили 0 на себя, все равно получится 0. Поэтому давайте предположим, что А не равно нулю. Мы намереваемся показать, что произведение p  – 1 множителя А равно 1. Этого достаточно для доказательства теоремы, поскольку умножение 1 на А возвратит нас к А .

Теперь давайте составим список всех часов на циферблате за исключением 0. В этом списке p  – 1 элемент:

1, 2, …, p  – 1.

Теперь умножим каждое число в этом списке на А и получим

А  × 1, А  × 2, …, А  × ( p   – 1) (modulo p ).

Позвольте мне показать, что часы в этом списке будут теми же, что и в первоначальном списке 1, 2, …, p  – 1, хотя они будут расположены в другом порядке. Если бы это было не так, то либо одно из произведений равнялось бы 0, либо какие-то два произведения были равны друг другу. Не может произойти что-либо другое, поскольку на циферблате имеется лишь p часов.

Предположим, что А  ×  n и А  ×  m дают один и тот же ответ на нашем p -часовом циферблате, где n и m лежат между 1 и p  – 1 (я покажу, почему это означает, что n  =  m ). Итак, А  ×  n  –  А  ×  m  =  А  × ( n  –  m ) равно нулю на часовом калькуляторе, то есть А  × ( n  –  m ) на обычном калькуляторе делится на p .

Ключевым в следующем шаге доказательства будет использование того факта, что p  – простое число. Подобно химической молекуле, число А  × ( n  –  m ) построено из произведения атомов (простых чисел), составляющих А , и простых чисел, составляющих n – m . Но число p  – простое, атом арифметики, и его нельзя расщепить далее. Поскольку А  × ( n – m ) делится на p , это число должно быть одним из атомов, использованных при построении А  × ( n  –  m ), ведь каждое число однозначно разлагается на простые множители. Но А не делится на p без остатка, поэтому p должно входить в список атомов, использованных при построении n  –  m . Другими словами, n  –  m делится на p . Но что это означает? Это означает, что n и m соответствуют одному и тому же времени на нашем p -часовом циферблате. Вы можете использовать схожую аргументацию, чтобы показать, что А  ×  n не может быть нулем часов, если ни А , ни n не равны нулю часов.

Заметьте, что крайне важно то, что на циферблате простое число часов. Мы уже видели, что 4 × 9 равняется нулю на 12-часовом калькуляторе, хотя ни 4, ни 9 не равно нулю.

Теперь у нас есть два списка – 1, 2, …, p  – 1 и А  × 1, А  × 2, …, А  × ( p  – 1), – составленные из одних и тех же чисел, хотя и расположенных в разном порядке. Теперь мы можем воспользоваться эффектным трюком, который, вероятно, открыл сам Ферма. Если мы перемножим все числа в каждом из списков, то получим один и тот же ответ, потому что порядок перемножения не имеет значения. Первый список даст нам 1 × 2 × … × ( p –  1), что мы можем записать как ( p –  1)!. Второй список приводит к p –  1 множителю А и опять-таки произведению чисел от 1 до p –  1. После небольшой перестановки мы можем переписать это как ( p –  1)!×  А p  – 1 . И эти два ответа равны на нашем часовом калькуляторе:

(p – 1)! = ( p – 1)! ×   А p  – 1 (modulo p ).

Из этого следует, что ( p –  1)! × (1 –  А p  – 1 ) делится на p , и мы можем использовать тот же трюк, что и ранее. Никакое из чисел 1, 2, …, p  – 1 не делится на p , значит, ( p –  1)! не может делиться на p . Единственная возможность состоит в том, что 1 –  А p  – 1 делится на p . А это приводит к тому, что вычисление А p  – 1 на часовом калькуляторе всегда будет давать ответ 1 – предложением объяснить данный результат Ферма и раззадорил математиков.

В этой аргументации есть несколько интересных ингредиентов. Разумеется, немаловажно то обстоятельство, что если A  ×  B делится без остатка на простое число p , то либо А , либо B должно также делиться на данное простое число. Это следует из специального свойства простых чисел. Но мне представляется красивым взгляд на список 1, 2, …, p  – 1 с двух различных перспектив. Для меня это образец умения рассматривать задачу с разных сторон.

 

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

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

Когда вы покупаете что-либо на веб-сайте, номер кредитной карты кодируется вашим компьютером, который использует публичный часовой калькулятор данного веб-сайта. Итак, веб-сайт должен сообщить вашему компьютеру, сколько часов на его калькуляторе. Это первое из двух чисел, которые получает ваш компьютер. Давайте назовем его N. В нашем примере с веб-сайтом футболок, администратором которого был Боб, это число равнялось 126 619. Также для совершения вычисления вашему компьютеру требуется второе кодирующее число, которое мы назовем Е. Номер вашей кредитной карты C кодируется путем возведения его в степень Е, причем вычисления совершаются N-часовым калькулятором. Таким образом, получается закодированное число CE (modulo N), и именно его ваш компьютер посылает на веб-сайт.

Но как же веб-сайт декодирует это число? И снова магия простых чисел играет в этом ключевую роль. Давайте предположим, что N – простое число (позже мы увидим, что это не слишком подходит для надежного шифрования, зато данное предположение помогает понять, куда мы направляемся). Если мы перемножим числа CE достаточное количество раз, то чудесным образом снова появится число С. Но сколько множителей (D), каждый из которых представляет CE , мы должны взять? Другими словами, когда (CE )D  = C на p-часовом калькуляторе?

Конечно, последнее равенство выполнится, если E × D = p. Но p – простое число, поэтому такого числа D не может быть. Однако если мы продолжим перемножать С, то найдется другая точка, где мы гарантированно получим в ответе С. В следующий раз номер кредитной карты появится, когда мы возведем его в степень 2(p –  1) + 1. Он появится снова при возведении в степень 3(p –  1) + 1. Значит, чтобы найти декодирующее число, нам необходимо найти такое D, что E × D = 1 (modulo (p –  1)). Такое уравнение значительно легче решить. Но проблема в том, что Е и p – открытые числа, поэтому хакер также может легко найти декодирующее число D. Для безопасной процедуры мы можем воспользоваться открытием, которое сделал Эйлер о часах, на которых p × q, a не просто p часовых делений (p и q – простые числа).

Если вы возьмете время С на циферблате, где имеется p × q часов, то через сколько шагов последовательность C, C × C, C × C × C, … начнет повторяться? Эйлер обнаружил, что это произойдет через (p –  1) × (q – 1) шагов. Итак, чтобы вернуться к первоначальному времени, нужно возвести C в степень (p –  1) × (q – 1) + 1, или k × (p –  1) × (q – 1) + 1, где k – число повторений последовательности.

Теперь мы знаем, что для того, чтобы декодировать сообщение CE на часах с p × q часовыми делениями, нам требуется найти такое декодирующее число D, что E × D = 1 (modulo (p – 1) × (q – 1)). Итак, нам необходимо делать вычисления на секретном часовом калькуляторе с (p –  1) × (q – 1) часами. Хакер знает только числа N и Е, и он должен найти секретные простые числа p и q, чтобы получить секретный часовый калькулятор. Следовательно, взлом кодов интернета сводится к разложению числа N на простые множители. А как мы видели в разделе о подкидывании монеты через интернет, это фактически невозможно, когда числа достаточно большие.

Давайте посмотрим на коды интернета в действии, но для очень небольших p и q. Тогда нам легко будет проследить за происходящим. Пусть Боб выбрал для своего веб-сайта футболок простые числа 3 и 11, так что открытый часовой калькулятор, с помощью которого покупатели кодируют номера своих кредитных карт, имеет 33 часа. Боб хранит в тайне простые числа 3 и 11, потому что они являются ключом к декодированию сообщений. Но Боб не делает секрета из числа 33, ведь это число часов на открытом часовом калькуляторе. Вторая порция информации, которая доступна на веб-сайте Боба, – кодирующее число Е. Пусть оно равно 7. Каждый, кто покупает футболку на веб-сайте Боба, делает одно и то же: возводит номер своей кредитной карты в 7-ю степень на 33-часовом калькуляторе.

Сайт Боба посещает покупатель, который был одним из самых первых получателей кредитных карт, и ее номер равен 2. Возведите 2 в 7-ю степень на 33-часовом калькуляторе, что равно 29.

Вот умный способ вычислить 27 на 33-часовом калькуляторе. Мы начинаем с перемножения 2: 22 = 4, 23 = 8, 24 = 16, 25 = 32. Когда мы переходим к более высоким степеням 2, стрелка на циферблате движется дальше и дальше, и, когда мы возводим 2 в 6-ю степень, она совершает более чем оборот. Можно применить следующий небольшой трюк, из-за которого стрелка словно меняет направление движения, вместо того чтобы вращаться и дальше по часовой. Мы просто говорим, что 32 часа на нашем 33-часовом калькуляторе это –1 час. Потом, когда мы делаем два последующих умножения на 2, то получаем –4 часа, или 29 часов. Благодаря этому приему нам не требуется возводить 2 в 7-ю степень, что равно 128, и затем находить остаток при делении на 33. Для очень больших чисел подобный метод экономии неоценим для компьютерных вычислений, когда нужно сделать все как можно быстрее.

Рис. 4.17. Вычисление степеней 2 на 33-часовом калькуляторе

Но как мы можем быть уверены, что 29, закодированное число покупателя, надежно защищено? В конце концов, хакер может перехватить это число, когда оно путешествует по интернету. Также он может легко найти открытый ключ Боба, состоящий из 33-часового калькулятора и инструкции возвести номер кредитной карты в 7-ю степень. Все, что необходимо хакеру, чтобы взломать код, – найти число, 7-я степень которого, вычисленная на 33-часовом калькуляторе, равна 29.

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

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

Обобщение малой теоремы Ферма, найденное Эйлером, гарантирует существование магического декодирующего числа D. Боб может найти произведение D множителей, каждый из которых равен закодированному номеру кредитной карты, и восстановить исходный номер кредитной карты. Но вы можете определить число D, только если знаете секретные простые числа p и q. Знание этих простых чисел становится ключом к раскрытию кодов интернета, потому что вам требуется решить следующую задачу на секретном часовом калькуляторе:

E  ×   D  = 1 (modulo ( p –  1) × ( q  – 1)).

Когда мы подставим наши числа, то придем к уравнению

7 ×   D  = 1 (modulo 2 × 10).

Значит, вопрос состоит в нахождении числа, которое при умножении на 7 дает результат, который при делении на 20 дает остаток 1. D = 3 подойдет, потому что 7 × 3 = 21 = 1 (modulo 20).

И, если мы возведем закодированный номер кредитной карты в третью степень, вновь появится исходный номер:

29³ = 2 (modulo 33).

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

 

Вопрос на миллион долларов

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

Существует множество различных эллиптических кривых, но все они описываются уравнениями вида y² = x³ + ax + b. Каждая кривая соответствует различным значениям a и b: например, а = 0 и b = –2 задают y² = x³ – 2.

Это уравнение определяет кривую, которую я могу нарисовать на миллиметровке, как показано ниже, путем нахождения последовательности точек (x, y). Я ввожу значение х, рассчитываю выражение x³ – 2 и беру из него квадратный корень, чтобы найти соответствующее значение y. Так, если x = 3, мы получим x³ – 2 = 27 – 2 = 25. Чтобы получить y, мне нужно взять квадратный корень из 25, поскольку y² = x³ – 2. Итак, y равен 5 или –5 (потому что минус при умножении на минус дает плюс, всегда имеется два квадратных корня). Получившийся график симметричен относительно горизонтальной оси, потому что у каждого квадратного корня выше ее есть зеркальный отрицательный корень. Пока мы нашли две точки: (3, 5) и (3, –5).

Рис. 4.18. График эллиптической кривой

Эти точки на эллиптической кривой особенно приятны, потому что и х, и у являются целыми числами. Можете ли вы найти другие такие точки? Давайте попробуем подставить x = 2. Тогда x³ – 2 = 8–2 = 6, так что y = √6 или – √6. В первом примере у 25 был целочисленный квадратный корень, но квадратный корень из 6 не так хорош. Древние греки доказали, что не существует дроби (не говоря уже о целом числе), которая при возведении в квадрат дает 6. √6 записывается в виде десятичного числа, дробная часть которого уходит в бесконечность без появления повторяющейся последовательности:

√6 = 2,449489742783178…

Вопрос на миллион долларов связан с нахождением точек на этой кривой, где и x, и y являются целыми числами или дробями. В большинстве случаев такого не происходит, потому что, когда вы подставляете х, получающееся y не будет целым числом или даже дробью, потому что у большинства чисел нет красивого квадратного корня. Нам повезло найти красивые точки (3, 5) и (3, –5) на кривой, но будут ли другие такие точки?

Древние греки нашли красивое геометрическое построение, показывающее, как получить другие точки (x, y), где и х, и y являются дробями, если вы нашли одну такую точку. Проведите прямую линию, которая слегка касается кривой в первой найденной точке – линия не должна пересекать кривую в этой точке, а проходить под правильным углом, чтобы лишь чуть скользнуть по ней, как показано на графике ниже. Мы называем такую прямую линию касательной к кривой в данной точке. Продолжая прямую, мы найдем ее пересечение с кривой в новой точке. Удивительное открытие состоит в том, что обе координаты новой точки будут дробями.

Рис. 4.19. Как найти другие точки на эллиптической кривой, координаты которых будут дробями

Например, если мы проведем касательную к эллиптической кривой y² = x³ – 2 в точке (x, y) = (3, 5), то найдем, что она пересекает кривую в новой точке (x, y) = (129/100, 383/1000), где обе координаты являются дробями. Мы можем провести касательную и в новой точке, в результате получится еще одна точка, где х и y будут дробями:

Без этого геометрического построения было бы нелегко обнаружить, что подстановка дроби

приведет к у, который также будет дробью.

В данном случае мы можем повторять проведение касательных и получить на эллиптической кривой бесконечно много точек с координатами (x, y), задаваемыми дробями. Если вы нашли такую точку (x1, y1) на эллиптической кривой общего вида y² = x³ – ax + b, то подстановка

и

даст вам другую точку на кривой, где x2 и y2 также будут дробями.

Эта процедура генерирует для нашей кривой y² = x³ – 2 бесконечно много точек с координатами, являющимися дробями. Но есть такие эллиптические кривые, для которых невозможно получить бесконечно много точек с этим свойством. Рассмотрите, например, кривую, задаваемую уравнением

y ² =  x ³ – 43 x  + 166.

Оказывается, что на этой кривой имеется лишь конечное число точек, у которых x и y являются целыми числами или дробями:

( x , y ) = (3, 8), (3, –8), (–5, 16), (–5, –16), (11, 32), (11, –32).

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

Вопрос на миллион долларов, называемый гипотезой Бёрча – Свиннертон-Дайера, состоит в том, возможно ли сказать, на какой эллиптической кривой будет бесконечно много точек, обе координаты которых являются целыми числами либо дробями.

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

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

 

Решения

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

A mathematician, like a painter or a poet, is a maker of patterns.

If his patterns are more permanent than theirs, it is because they are made with ideas. The mathematician’s patterns, like the painter’s or the poet’s, must be beautiful; the ideas like the colours or the words, must fit together in a harmonious way. Beauty is the first test: there is no permanent place in the world for ugly mathematics.

Шифр таков:

Таблица 4.14

Легкое задание

Выпал орел. 13 068 221 = 3613 × 3617. И 3613, и 3617 – простые числа, которые дают остаток 1 при делении на 4. Существует возможность быстро разложить исходное число на множители, используя прием, найденный Ферма. Если вы возведете 3615 в квадрат, то получите 13 068 225, что на 4 больше, чем 13 068 221. 4 также является квадратом целого числа. Используйте немного алгебры, сообщающей вам, что a² – b² = (a + b) × (a – b). Вы получите:

13 068 221 = 3615² – 2² = (3615 + 2) × (3615 – 2) = 3613 × 3617.