Читать «Золотой билет. P, NP и границы возможного» онлайн - страница 75

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

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

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

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

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

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

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

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

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

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