Алгоритмы электронной цифровой подписи

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

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

Определение. Схема цифровой подписи представляет собой конструк­цию вида

(K, M, S, P_K, V_K), где

• К — пространство ключей, его элементы имеют вид k=(k_o,k_c), где
k_o назы­вается открытым ключом (public key) или открытой компонентой ключа,
k_c называется секретным ключом (secret key) или секретной ком­понентой ключа;

• M  — пространство сообщений;

• S   — пространство под­писей;

• функция построения подписи      P_K: M ® S
эффективно строится по закрытому ключу k_c;

• функция проверки подписи          V_K:{M x S}®{0;1}
 эффективно строится по открытому ключу k_o; и " m ÎM и " s ÎS

V_K(m, s) = l   <=> s = P_K(m);

иначе V_K(m, s) = 0.

• не существует эффективного способа найти без знания закрытого ключа значение s для заданного m так, чтобы V_K(m, s)=l.

Последнее требование к цифровой подписи может быть усилено, а имен­но: требуется невозможность найти хотя бы одну пару (m, s) такую, что

V _k (m, s) = l («экзистенциальная подделка»).

Цифровая подпись позволяет участнику А передать участнику В сообще­ние в виде . Тогда получатель может быть уверен, что сообщение отправлено именно владельцем закрытого ключа, и даже доказать это в суде.

Если цифровая подпись используется совместно с шифрованием, то следует вычислять подпись под открытым текстом, а потом выпол­нять шифрование. То есть передавать сообщение в виде

, а не .

Подписывать шифртексты на рекомендуется, так как при этом не удается хранить расшифрованные сообщения вместе с подписями.

Кроме того, в этом случае от используемой криптосистемы требует­ся стой­кость к атакам с известным сообщением. В противном случае, если по заданной шифрограмме с и заданному сообщению т можно подобрать ключ k такой, что E _k (m)= c, злоумышленник Z может перехватить подпись , для любого сообщения т' подобрать ключ k такой, что , зарегис­трировать этот ключ в качестве своего и утверждать, что А послал ему сообщение с .