Золотой билет - Страница 42

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

Современная криптография

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

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

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

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

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

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

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

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

Неужели можно шифровать сообщения ключом, который все знают?! Можно – но только если P и NP не равны: в противном случае закрытый ключ легко и быстро восстанавливается по открытому.

В 1976 году большинство ученых уже склонялись к тому, что P ≠ NP, а потому системы с открытым ключом имеют право на жизнь. Диффи и Хеллман такую систему предложили, однако более широкое распространение получила криптосистема RSA, которую в 1978 году разработали Рональд Ривест, Ади Шамир и Леонард Адлеман. Система была названа по первым буквам фамилий ее создателей – Rivest, Shamir, Adleman.

В основе алгоритма RSA лежит тот факт, что умножать легко, а раскладывать на множители – очень трудно. Возьмем, к примеру, два достаточно больших простых числа, 5754853343 и 2860486313. Найти их произведение легко: это 16461679220973794359. А вот с обратным процессом все обстоит гораздо сложнее – попробуйте-ка по числу 16461679220973794359 восстановить сомножители 5754853343 и 2860486313! В системе RSA используются громадные простые числа, состоящие, как правило, из нескольких сот цифр. Нельзя утверждать, что разложение на простые множители практически неразрешимо, пока неравенство классов P и NP остается недоказанным; однако по мнению ученых задача эта представляет огромную вычислительную трудность.

За свое изобретение Ривест, Шамир и Адлеман в 2002 году получили премию Тьюринга.

Удивительный факт: позднее выяснилось, что впервые подобную криптосистему описал в 1973 году Клиффорд Кокс, работавший в то время в Центре правительственной связи Великобритании. Эта информация была обнародована лишь в 1997 году.