Примеры схем электронной подписи

К наиболее известным схемам электронной подписи относятся схемы RSA, Рабина — Уильямса, Эль-Гамаля, Шнорра, Фиата — Шамира, а также схема электронной подписи отечественного стандарта ГОСТ Р 34.10—2012^[1].

Рассмотрим подробнее три наиболее известные схемы цифровой подписи.

I. Подпись RSA. Вход: Числа п, р, q, где р и q — большие /-разрядные простые числа, п = pq. Открытый ключ р = (е, п)_у секретный ключ s = d, такой что ed= 1 (mod (p (/?)) и наибольший общий делитель НОД ((р — l)(q — 1).

Генерация ключей: (d, (е, п)) = A_k(l, /?).

Подпись: m^rf(modw) = с, где с — подпись сообщения т. е.

Верификация'. Ар: 1) [c*]^e(mod п) = те*;

2) если те** = т*, подпись верна.

II. Подпись Эль-Гамаля. Вход: Числа р и g, где р — простое /-разрядное число, a g — первообразный корень по модулю р. Секретный ключ s = d, открытый ключ р = е, такой что е = g^rf(mod/?), те — подписываемое сообщение.

Генерация ключей: (d, (е, g, р)) = A_k(l, b).

Подпись: Л_х: 1) г = g* (modр), где k € _R Z_p ,;

2) находится такое с, что те = [ кс + dr] (mod р — 1), где (с, г) — подпись сообщения т.

Верификация: А_р: если g'" ' = е’г'' (modр), то подпись верна.

III. Подпись Фиата — Шамира. Вход: Числа п, р, и q, где/? и q большие /-разрядные простые числа, открытый ключ р есть вектор (??, v₂,…, v_k), где Vj — квадратичные вычеты по модулю n, j = 1,…, к, секретный ключ р есть вектор (л, s₂,…, s_k), где каждый — наименьший квадратный корень из vj ', т — подписываемое сообщение/ — псевдослучайная функция.

Генерация ключей: ((s, s₂,…, s*), (v_v v₂,…, v_k)) = A_k(l, b). Подпись: A; 1) x_; = rf (mod n), где [r_v r₂,…, r_k] e_RZ";

• 2) вычисляется значение a = f (m, x_v x₂,…, xjjy
• 3) выбираются первые kt битов числа a как матрица е_р (i = 1,…, t, j = 1,…, k);
• 4) вычисляется г/, = r_i ГГ s (mod n), где i =

e-l.

= 1, …, t.

Тогда (e_jjt yj) — подпись сообщения т. е.

Верификация: А : 1)2, = [у*]² П f (modп), где i = 1,…, t

^e'r^x

2) если первые kt битов значения функции /(те", г, z₂, …, г,) равны е*, подпись верна.

• [1] Описана в приложении И.