К наиболее известным схемам электронной подписи относятся схемы RSA, Рабина — Уильямса, Эль-Гамаля, Шнорра, Фиата — Шамира, а также схема электронной подписи отечественного стандарта ГОСТ Р 34.10—2012[1].
Рассмотрим подробнее три наиболее известные схемы цифровой подписи.
I. Подпись RSA. Вход: Числа п, р, q, где р и q — большие /-разрядные простые числа, п = pq. Открытый ключ р = (е, п)у секретный ключ s = d, такой что ed= 1 (mod (p (/?)) и наибольший общий делитель НОД ((р — l)(q — 1).
Генерация ключей: (d, (е, п)) = Ak(l, /?).
Подпись: mrf(modw) = с, где с — подпись сообщения т. е.
Верификация'. Ар: 1) [c*]e(mod п) = те*;
2) если те** = т*, подпись верна.
II. Подпись Эль-Гамаля. Вход: Числа р и g, где р — простое /-разрядное число, a g — первообразный корень по модулю р. Секретный ключ s = d, открытый ключ р = е, такой что е = grf(mod/?), те — подписываемое сообщение.
Генерация ключей: (d, (е, g, р)) = Ak(l, b).
Подпись: Лх: 1) г = g* (modр), где k € R Zp ,;
2) находится такое с, что те = [ кс + dr] (mod р — 1), где (с, г) — подпись сообщения т.
Верификация: Ар: если g'" ' = е’г'' (modр), то подпись верна.
III. Подпись Фиата — Шамира. Вход: Числа п, р, и q, где/? и q большие /-разрядные простые числа, открытый ключ р есть вектор (??, v2,…, vk), где Vj — квадратичные вычеты по модулю n, j = 1,…, к, секретный ключ р есть вектор (л, s2,…, sk), где каждый — наименьший квадратный корень из vj ', т — подписываемое сообщение/ — псевдослучайная функция.
Генерация ключей: ((s, s2,…, s*), (vv v2,…, vk)) = Ak(l, b). Подпись: A; 1) x; = rf (mod n), где [rv r2,…, rk] eRZ";
- 2) вычисляется значение a = f (m, xv x2,…, xjjy
- 3) выбираются первые kt битов числа a как матрица ер (i = 1,…, t, j = 1,…, k);
- 4) вычисляется г/, = ri ГГ s (mod n), где i =
e-l.
= 1, …, t.
Тогда (ejjt yj) — подпись сообщения т. е.
Верификация: А : 1)2, = [у*]2 П f (modп), где i = 1,…, t
e'rx
2) если первые kt битов значения функции /(те", г, z2, …, г,) равны е*, подпись верна.
- [1] Описана в приложении И.
