Золотой билет. P, NP и границы возможного - Лэнс Фортноу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основываясь на результатах, полученных ранее Ральфом Мерклом, Диффи и Хеллман предложили обойти эту проблему при помощи так называемых криптосистем с открытым ключом. Компьютер создает два ключа – открытый и закрытый; открытый можно послать кому угодно, а закрытый хранится в тайне и по сети не передается.

Основная идея таких криптосистем состоит в том, что при шифровании применяется открытый ключ, который, однако, не подходит для дешифровки. Исходное сообщение можно восстановить лишь при наличии закрытого ключа.

Допустим, Диффи хочет отправить Хеллману такое сообщение: «Наступление в полночь». Хеллман создает пару ключей; открытый ключ он посылает Диффи и другим заинтересованным участникам, а закрытый держит в тайне. С помощью открытого ключа Диффи зашифровывает сообщение «Наступление в полночь» и отправляет результат Хеллману. Секретный ключ ему знать не нужно, поскольку для шифрования он не используется. Хакер, перехвативший шифровку, не сможет восстановить исходный текст даже в том случае, если знает открытый ключ. А вот Хеллман с помощью закрытого ключа расшифрует сообщение и узнает о том, что наступление начинается в полночь.