Звучит нелепо? Это кажется невозможным. Если бы вы спросили шифровальщиков со всего света в 1975 году, все они сказали бы, что это невозможно. Так что можете себе представить всеобщее изумление, когда в 1976 году Витфилд Диффи и Мартин Хеллман объяснили, как это сделать. Или удивление британской разведки, когда Джеймс Эллис, Клиффорд Кок и М. Д. Уильямсон осуществили то же самое на несколько лет раньше.
Основная идея в том, чтобы использовать математическую функцию, которую просто вычислять в одном направлении и тяжело – в другом. Одна из таких функций – разложение целых чисел на множители. Если даны два числа, их легко перемножить и найти произведение. Но если дано только произведение, практически невозможно разложить число на множители и определить исходные числа. Как раз такого плана математику можно применять для создания шифрования с открытым ключом: в нее входят арифметические операции над абсолютными значениями чисел, возведение в степень и большие многоразрядные (до нескольких тысяч битов) исходные числа. Сегодня существует добрые полдюжины алгоритмов с названиями вроде RSA, Эль-Гамаль и алгоритм эллиптических кривых. (Алгоритмы, в основе которых лежит так называемая «задача о ранце», конкурировали с ними на ранних стадиях, но по прошествии 20 лет их так или иначе взломали.) Математика для каждого алгоритма своя, но концептуально они все одинаковы.
Вместо единственного ключа совместного пользования у Алисы и Боба есть два ключа: один для шифрования, а другой для расшифровки. Ключи различны, и невозможно, зная один ключ, вычислить другой. То есть если у вас есть ключ для шифрования, вы не сумеете найти ключ для расшифровки.
Вот в этом-то и есть самое интересное. Боб может создать пару таких ключей. Он может взять и обнародовать ключ для шифрования. Он может послать его друзьям, опубликовать на своем веб-сайте или поместить в телефонной книге. Алиса может найти этот ключ. Она может с его помощью зашифровать сообщение для Боба. Затем она может послать ему сообщение. Боб, используя свой ключ расшифровки (который он предусмотрительно не размещал на веб-сайте), сможет расшифровать и прочитать послание Алисы. Заметим, что Алисе не приходится встречаться с Бобом в какой-нибудь темной аллее и договариваться об общем секрете. Бобу даже не обязательно знать Алису. И, как ни странно, даже Алисе не обязательно знать Боба. Если Алиса сможет найти ключ, который Боб обнародовал, она сможет послать ему тайное сообщение, которое никто, кроме Боба, не сможет прочитать. Такое постоянно происходит с пользователями PGP; один из их ключей находится на каком-либо сервере, и тогда совершенно посторонний человек может отправить им зашифрованные сообщения. Даже если вы что-то смыслите в математике, это не менее удивительно.
Детали этого процесса содержат в себе целую кучу хитростей. Например, я не рассказал, как Боб создал открытый и закрытый ключи и как он сделал свой личный ключ секретным. (Он не может его помнить – ведь ключ состоит из более чем тысячи случайных цифр.) И я пропущу здесь рассказ о невероятно сложной задаче – как Алиса узнает, что она получила именно ключ Боба, а не какой-то старый, или неправильный, или ключ какого-либо злоумышленника. Мы вернемся к этому позднее.
А сейчас я хочу обратить ваше внимание на то, что никто не применяет шифрование с открытым ключом для кодирования сообщений. Все операционные системы используют гибридные технологии, в которых задействованы оба типа криптографии. Причина интереса к этому подходу в его эффективности. На самом деле, когда Алиса хочет послать сообщение Бобу, она зашифровывает сообщение при помощи симметричного алгоритма, используя произвольный ключ, который создает «из воздуха» (так называемый сеансовый ключ). Она зашифровывает этот произвольный ключ при помощи открытого ключа Боба, а затем отправляет вместе зашифрованный ключ и зашифрованное сообщение для Боба. Когда Боб их получает, он производит обратную операцию. При помощи личного ключа он расшифровывает произвольный симметричный ключ, а затем использует его для расшифровки сообщения.
Это может показаться сверхъестественным, но все совершенно нормально. Повторюсь, никто не использует криптографию с открытым ключом непосредственно для шифрования сообщений. Все применяют гибридные технологии. Так устроены все программы, обеспечивающие безопасность электронной почты, – PGP, РЕМ, S/MIME и любые другие. Так обеспечивается защита сообщений Веб, TCP/IP, телефонной связи и всего остального.
Шифрование с открытым ключом – вещь довольно удивительная, но цифровые подписи (сигнатуры) – еще более интересный и важный инструмент. Цифровые подписи обеспечивают тот же уровень аутентификации сообщений, что и MAC. А в современном бизнесе аутентификация намного важнее секретности,
Как и шифрование с открытым ключом, цифровые подписи используют пару ключей: открытый и закрытый. Вы также не можете установить по одному ключу другой. Но в этом случае ключи меняются местами.
У Алисы есть открытый текст сообщения. Применяя свой закрытый ключ, она сообщение зашифровывает. Поскольку это ее личный ключ, то только им можно зашифровать сообщение абсолютно тем же способом. Таким образом, зашифрованное сообщение становится Алисиной подписью на сообщении. Открытый ключ Алисы общедоступен. Кто угодно способен достать этот ключ и расшифровать сообщение, удостоверившись таким образом, что его подписала (то есть зашифровала) Алиса. Подпись является функцией сообщения, поэтому она уникальна для сообщений: злостный фальсификатор не может снять подпись Алисы с одного документа и поместить ее на другой. Подпись – это функция личного ключа Алисы, то есть она уникальна для нее.
Конечно, реальные системы более сложны. Так же как Алиса не зашифровывает сами сообщения при помощи алгоритмов шифрования с открытым ключом (она зашифровывает только ключ сообщения), она и не подписывает непосредственно сообщение. Вместо этого она вычисляет одностороннюю хэш-функцию сообщения и затем ее подписывает. Опять же, подписывание хэш-значения на несколько порядков быстрее, и надо иметь в виду, что существует математическая проблема защиты при подписывании сообщений напрямую.
Таким образом, большинство алгоритмов цифровых подписей на самом деле не зашифровывают подписанные сообщения. Идея та же, но математическое исполнение отличается. Для того чтобы создать подпись, Алиса производит некоторые вычисления исходя из сообщения и своего личного ключа. Эта подпись прикрепляется к сообщению. Боб проделывает другие вычисления, основываясь на сообщении, подписи и открытом ключе Алисы, чтобы проверить подпись. Ева, которая не знает личного ключа Алисы, может проверить подпись, но не может подделать сообщение или полноценную подпись.
В настоящее время применяются несколько алгоритмов цифровой подписи. Наиболее популярен RSA. Алгоритм цифровой подписи американского правительства (Digital Signature Algorithm, DSA), который применяют в стандарте цифровой подписи (Digital Signature Standard, DSS), также используется часто. Вы можете иногда встретить алгоритм Эль-Гамаль. А еще существуют алгоритмы подписей, в основе которых лежит криптография эллиптических кривых; они похожи на все прочие, но в некоторых ситуациях работают эффективнее.
Хотя алгоритмы цифровой подписи с открытым ключом похожи на MAC, они лучше в одном важном нюансе. Используя MAC, Алиса и Боб применяют совместный секретный ключ для аутентификации сообщений. Если Алиса получит сообщение и проверит его, она будет знать, что сообщение пришло от Боба.
Но она не сможет доказать это правосудию. В чем можно его убедить – это в том, что письмо пришло или от Боба, или от Алисы: как-никак оба они знали ключ MAC. При помощи MAC можно убедить получателя, что письмо поступило от отправителя, но MAC нельзя использовать для убеждения третьей стороны. Цифровые подписи позволяют уверить третью сторону, решающую проблему отказа от подписи: Алиса не может отправить Бобу письмо, а позднее утверждать, что никогда его не посылала.