Лэнс Фотноу - Золотой билет

Фраза The early bird gets the worm («Кто рано встает, тому бог дает») после такой кодировки превращается в Wkh hduob elug jhwv wkh zrup . Способ шифрования, при котором все буквы циклически сдвигаются на определенное число позиций, стали называть шифром Цезаря.

В Древнем Риме этот метод работал хорошо. Зашифрованные сообщения выглядели как случайный набор букв, а люди пока еще не обладали необходимыми навыками для взлома шифров. К IX веку математики разработали методы восстановления исходного сообщения; эти методы учитывали частоту появления букв и анализировали короткие слова. Глядя на фразу Wkh hduob elug jhwv wkh zrup , можно заметить, что буква h встречается четыре раза, т. е. чаще остальных. Самая распространенная буква английского алфавита – это e , ее частота составляет примерно 12 процентов. Вы можете предположить, что буква h кодирует букву e , – и будете совершенно правы. Сочетание wkh встречается дважды; вы уже знаете, что h – это e , поэтому делаете вывод, что wkh – это, наверно, the . Еще чуть-чуть – и исходное сообщение будет восстановлено!

Рис. 8.1.Шифр Цезаря

В XV веке, в эпоху Возрождения, итальянский ученый Леон Баттиста Альберти разработал более сложный метод. Это был шифр многоалфавитной замены, в котором сообщение разбивалось на несколько частей, и для каждой части использовался свой алфавит подстановки. Система Альберти практически не поддавалась взлому вплоть до XIX века, когда на шифры началось систематическое наступление.

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

В 1903 году выходят «Пляшущие человечки» Конан Дойля, где Шерлок Холмс взламывает подстановочный шифр, состоящий из странных пляшущих фигурок.

Наступила эра механики; люди начали изобретать машины, способные создавать ключи для шифровки и дешифровки. Самая известная шифровальная машина – это, пожалуй, «Энигма», первую версию которой в 1918 году в Германии разработал Артур Шербиус.

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

Рис. 8.2.Пляшущие человечки

Рис. 8.3.Шифровальная машина «Энигма»

У немцев во время Второй мировой большинство сообщений шифровалось при помощи «Энигмы». Незадолго до начала войны Великобритания получила от польской разведки описание машины и некоторых методов дешифровки. Британское правительство запустило засекреченный проект с кодовым названием «Ультра», целью которого был взлом шифров «Энигмы». В штат набирали известных шахматистов, чемпионов по решению кроссвордов и, конечно, талантливых математиков, среди которых был и основоположник теории вычислений Алан Тьюринг. В рамках проекта был спроектирован и построен «Колоссус» – первый в мире программируемый цифровой компьютер. «Именно благодаря проекту „Ультра“ мы выиграли войну», – скажет позже Уинстон Черчилль.

Криптография всегда была – и будет – чем-то вроде игры в кошки-мышки между теми, кто создает шифры, и теми, кто их взламывает. Впрочем, в семидесятых годах XX века игра заметно усложнилась, поскольку трудоемкость некоторых NP-задач послужила отправной точкой в создании новых методов шифрования.

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

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

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

Компьютерные сети создают дополнительные трудности, поскольку на их безопасность нельзя положиться. В конце XX века сети работали преимущественно через телефонные линии, подключиться к которым было не так уж и сложно. А сейчас любой посетитель кофейни может перехватить все данные, отправляемые вашим компьютером через местный Wi-Fi.