Цифровая (электронная) подпись на основе криптосистемы rsa

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

Действительно, пусть нам необходимо заверить блок mоткрытого текста. Сам открытый текст не является секретным. Зашифруемmиспользуяdвместоe:с = m^d(mоd n). Отправим сообщение двойной длины видаm||c. Получатель имеет возможность проверить нашу подпись, поскольку после возведенияcв степеньeдолжно получаться значениеs = m(при истинной подписи) и значениеs  mв противном случае. Для нашего примераm =(3, 1, 2),c = (27, 1, 8),m || с = (3, 1, 2, 27, 1, 8).

На практике удвоение длины сообщения, очевидно, является нежелательным. Это является одной из причин, по которым вместо c = m^d(mod n)используются данные видаc = (h(m))^d(mod n). Здесь функцияh, называемаяхеш-функцией, отображает сообщения произвольной длины в короткие блоки фиксированной длины, причем так, что кроме блокаmподобрать другой блокzсо свойствомh(m) = h(z)практически невозможно.