Алгоритмы. 
Электронная цифровая подпись

Существует несколько схем построения цифровой подписи:

ѕ На основе алгоритмов симметричного шифрования. Данная схема предусматривает наличие в системе третьего лица — арбитра, пользующегося доверием обеих сторон. Авторизацией документа является сам факт зашифрования его секретным ключом и передача его арбитру.

ѕ На основе алгоритмов асимметричного шифрования. На данный момент такие схемы ЭП наиболее распространены и находят широкое применение.

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

Технология применения системы электронной цифровой подписи (ЭЦП) предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ [1].

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

ѕ задача факторизации (разложения на множители) больших целых чисел;

ѕ задача дискретного логарифмирования.

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. В Массачуссетском технологическом институте США. Алгоритм получил свое название по первым буквам фамилий его авторов: Rivest, Shamir и Adleman. Надежность алгоритма основывается на трудности факторизации больших чисел.

Более надежный и удобный для реализации на персональных компьютерах ЭЦП алгоритм был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем и получил название El GamalSignature Algorithm (EGSA). Идея EGSA основана на том, что для обоснования практической невозможности фальсификации ЭЦП может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа — задача дискретного логарифмирования. Кроме того Эль Гамалю удалось избежать явной слабости алгоритма ЭЦП RSA, связанной с возможностью подделки ЭЦП под некоторыми сообщениями без определения секретного ключа.

Алгоритм цифровой подписи Digital Signature Algorithm (DSA) предложен в 1991 г. в США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритма ЭЦП EGSA. По сравнению с алгоритмом ЭЦП EGSA алгоритм DSA имеет ряд преимуществ: сокращен объем памяти и время вычисления подписи. Недостатком же является необходимость при подписывании и проверке подписи выполнять сложные операции деления по модулю большого числа.

Российский стандарт цифровой подписи обозначается как ГОСТ Р 34.10−94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. Различие между этими стандартами заключается в использовании параметров ЭЦП разного порядка, что приводит к получению более безопасной подписи при использовании российского стандарта.

Алгоритмы цифровых подписей Elliptic Curve Digital Signature Algorithm (ECDSA) и ГОСТ Р 34.10−2001 являются усовершенствованием цифровых подписей DSA и ГОСТ Р 34.10−94 соответственно. Эти алгоритмы построены на базе математического аппарата эллиптических кривых над простым полем Галуа.