На основе алгоритмов асимметричного шифрования

На данный момент такие схемы ЭЦП наиболее распространены и находят широкое применение.

Асимметричные схемы ЭЦП относятся к криптосистемам с открытым ключом. В отличие от асимметричных алгоритмов шифрования, в которых зашифрование производится с помощью открытого ключа, а расшифрование Ї с помощью закрытого, в схемах цифровой подписи подписывание производится с применением закрытого ключа, а проверка Ї с применением открытого.

Общепризнанная схема цифровой подписи охватывает три процесса:

• 1. Генерация ключевой пары. При помощи алгоритма генерации ключа равновероятным образом из набора возможных закрытых ключей выбирается закрытый ключ, вычисляется соответствующий ему открытый ключ.
• 2. Формирование подписи. Для заданного электронного документа с помощью закрытого ключа вычисляется подпись.
• 3. Проверка (верификация) подписи. Для данных документа и подписи с помощью открытого ключа определяется действительность подписи.

Для того, чтобы использование цифровой подписи имело смысл, необходимо выполнение двух условий:

• 1. Верификация подписи должна производиться открытым ключом, соответствующим именно тому закрытому ключу, который использовался при подписании.
• 2. Без обладания закрытым ключом должно быть вычислительно сложно создать легитимную цифровую подпись.

Обеспечение этого во всех асимметричных алгоритмах цифровой подписи опирается на следующие вычислительные задачи:

• 1. Задачу дискретного логарифмирования
• 2. Задачу факторизации, то есть разложения числа на простые множители

Вычисления тоже могут производиться двумя способами:

• 1. на базе математического аппарата эллиптических кривых
• 2. на базе полей Галуа

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

Схемы цифровой подписи могут быть одноразовыми и многоразовыми. В одноразовых схемах после проверки подлинности подписи необходимо провести замену ключей, в многоразовых схемах это делать не требуется.

В зависимости от алгоритма функция вычисления подписи может быть детерминированной (точной) или вероятностной. Детерминированные функции всегда вычисляют одинаковую подпись по одинаковым входным данным. Вероятностные функции вносят в подпись элемент случайности, что усиливает криптостойкость алгоритмов ЭЦП. Однако, для вероятностных схем необходим надёжный источник случайности (либо аппаратный генератор шума, либо криптографически надёжный генератор псевдослучайных бит), что усложняет реализацию. В настоящее время детерминированные схемы практически не используются. Даже в изначально детерминированные (точные) алгоритмы сейчас внесены модификации, превращающие их в вероятностные.