Книга: Золотой билет

Очень краткая история классической криптографии

Очень краткая история классической криптографии

Шифрование существует столько же, сколько и переписка. Юлий Цезарь пользовался простым подстановочным шифром, в котором каждая буква заменялась на другую букву, отстоящую от нее в алфавите на три позиции.

Фраза 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-задач послужила отправной точкой в создании новых методов шифрования.

Оглавление книги