Схема с восстановлением сообщения.

Абонент А, посылая сообщение M, вычисляет S = s(M) и передает результат S, где S – цифровая подпись на сообщении M. Секретность сообщения в данный момент не рассматривается, важна лишь его аутентичность. Если существенна и конфиденциальность сообщения, то его можно зашифровать (до или после подписания) используя, например, открытый ключ адресата.

Получатель подписи S применяет открытое преобразование проверки V к S и получает на выходе процедуры сообщение M и некоторый бит v, который отвечает за результат проверки подписи M,v = V(S). Если результат проверки положителен, то адресат получает уверенность в следующем:

- в целостности сообщения, то есть в том, что оно не было изменено при передаче;

- в его аутентичности, то есть в том, что оно было послано именно отправителем;

- в отсутствии отказа от авторства (ренегатства): отправитель не сможет утверждать, что не посылал сообщения.

Последнее свойство важно для электронной коммерции. Допустим невозможно отрицать факт подписания чека и пр.

Схема с восстановлением сообщения на основе RSA.

Алгоритм шифрования RSA можно непосредственно использовать в качестве алгоритма подписи с восстановлением сообщения.

- Отправитель применяет расшифровывающее преобразование RSA, чтобы поставить подпись, беря сообщение и возводя его в закрытую степень d:

S = M ^d (mod N).

- Получатель использует зашифровывающее преобразование RSA на основе открытой экспоненты E и восстанавливает оригинальное сообщение:

M = S^E (mod N).

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

Предположим, сообщение D состоит из t битов, а модуль N алгоритма RSA насчитывает k битов, причем t < k – 32. Тогда мы прибавляем к D (k – t)/8 байтов слева и получаем строку байтов вида

M = 00||01||FF||FF...||FF||00||D,

после чего подпись вычисляется посредством формулы M ^d (mod N). При проверке подписи правильность восстановления сообщения M подтверждается корректностью дополнения.

Схема подписи с восстановлением сообщения хороша для небольших сообщений (например при обмене ключами по Диффи-Хеллману). Если сообщение большое, его приходится разбивать на блоки и подписывать каждый блок отдельно, что порождает целый ряд дополнительных неудобств. В таком случае применяют схему подписи с дополнением.