Решения
Лотерея «Тайн 4исел»
Выигрышные номера: 2, 3, 5, 7, 17, 42.
Задача коммивояжера
Вот маршрут протяженностью 238 миль:
Рис. 3.23
15 + 55 + 28 + 12 + 24 + 35 + 25 + 17 + 4 + 5 + 18 = 238
Глава 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-я глава посвящена искусству тайных сообщений, и объясняется, насколько совершенен может быть шифр подстановки для сокрытия подробностей любовных связей.
