(то есть зашифровала) Алиса. Подпись является функцией сообщения, поэтому она уникальна для сообщений: злостный фальсификатор не может снять подпись Алисы с одного документа и поместить ее на другой. Подпись – это функция личного ключа Алисы, то есть она уникальна для нее.
Конечно, реальные системы более сложны. Так же как Алиса не зашифровывает сами сообщения при помощи алгоритмов шифрования с открытым ключом (она зашифровывает только ключ сообщения), она и не подписывает непосредственно сообщение. Вместо этого она вычисляет одностороннюю хэш-функцию сообщения и затем ее подписывает. Опять же, подписывание хэш-значения на несколько порядков быстрее, и надо иметь в виду, что существует математическая проблема защиты при подписывании сообщений напрямую.
Таким образом, большинство алгоритмов цифровых подписей на самом деле не зашифровывают подписанные сообщения. Идея та же, но математическое исполнение отличается. Для того чтобы создать подпись, Алиса производит некоторые вычисления исходя из сообщения и своего личного ключа. Эта подпись прикрепляется к сообщению. Боб проделывает другие вычисления, основываясь на сообщении, подписи и открытом ключе Алисы, чтобы проверить подпись. Ева, которая не знает личного ключа Алисы, может проверить подпись, но не может подделать сообщение или полноценную подпись.
В настоящее время применяются несколько алгоритмов цифровой подписи. Наиболее популярен RSA. Алгоритм цифровой подписи американского правительства (Digital Signature Algorithm, DSA), который применяют в стандарте цифровой подписи (Digital Signature Standard, DSS), также используется часто. Вы можете иногда встретить алгоритм Эль-Гамаль. А еще существуют алгоритмы подписей, в основе которых лежит криптография эллиптических кривых; они похожи на все прочие, но в некоторых ситуациях работают эффективнее.
Хотя алгоритмы цифровой подписи с открытым ключом похожи на MAC, они лучше в одном важном нюансе. Используя MAC, Алиса и Боб применяют совместный секретный ключ для аутентификации сообщений. Если Алиса получит сообщение и проверит его, она будет знать, что сообщение пришло от Боба.
Но она не сможет доказать это правосудию. В чем можно его убедить – это в том, что письмо пришло или от Боба, или от Алисы: как-никак оба они знали ключ MAC. При помощи MAC можно убедить получателя, что письмо поступило от отправителя, но MAC нельзя использовать для убеждения третьей стороны. Цифровые подписи позволяют уверить третью сторону, решающую проблему отказа от подписи: Алиса не может отправить Бобу письмо, а позднее утверждать, что никогда его не посылала.