Стандарты цифровой подписи США (DSA) и России (ГОСТ Р 34.10)
DSA (Digital Signature Algorithm) — алгоритм с использованием открытого ключа для создания ЭЦП, но не для шифрования (в отличии от RSA и схемы Эль-Гамаля).
Алгоритм был предложен Национальным институтом стандартов и технологий (США) в августе 1991 и является запатентованным U.S. Patent 5231668 (англ.), но НИСТ сделал этот патент доступным для использования без лицензионных отчислений.
ГОСТ Р 34.10-2001 (полное название: «ГОСТ Р 34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи») — российский стандарт, описывающий алгоритмы формирования и проверки ЭЦП. Принят и введён в действие Постановлением Госстандарта России от 12 сентября 2001 года вместо ГОСТ Р 34.10-94.
ГОСТ Р 34.10-2001 основан на эллиптических кривых. Его стойкость основывается на сложности взятия дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции по ГОСТ Р 34.11-94.
ГОСТ Р 34.10 – 94
p = bq + 1 (q – простое число 256 бит; p – простое число 1024 бит)
aq (mod p) = 1
У каждого пользователя есть секретный ключ x;
он всем раздает y = ax (mod p) – открытый ключ.
Генерация подписи:
1. h = h(m); хэш-функция вычисляется в соответствии с ГОСТ Р 34.11-94 (md2, md5, rc4, rc5, а США - SHA);
2. Одноразовый ключ 0<k<q
3. Вычисляются параметры подписи
r = ak (mod p) mod q; если r = 0 – переход к шагу 2.
4. s = (h*k + x*r) mod q; если s = 0 – переход к шагу 2.
5. Посылаем m и параметры подписи r, s <m,r,s>
Проверка подписи:
1. h = h(m);
2. v1 = s*h-1 mod q; v2 = -r*h-1 mod q
3. v = (av1*yv2) mod p mod q;
4. если v = r, то подпись принимается, иначе – подпись не верна.
ГОСТ Р 34.10 – 2001
Эллиптическая кривая y2 = x3 +ax + b
p = 5; a = b =1;
Определяются точки p; [2]p; [3]p; …; [q]p = ∞ (q – 256-битное число);
XA - у каждого пользователя своя точка;
YA = [XA]p = (xA;yA), где [XA] – номер точки; (xA;yA) – ее координаты.
Генерация подписи.
1. h = h(m); хэш-функция вычисляется в соответствии с ГОСТ Р 34.11-94 (md2, md5, rc4, rc5, а США - SHA);
2. Одноразовый ключ 0<k<q;
3. G = [k]p = (xG;yG);
4. r = xG mod q;
5. s = (h*k + xA*r) mod q;
6. <m,r,s>
Проверка.
1. h = h(m);
2. v1 = s*h-1 mod q; v2 = -r*h-1 mod q;
3. G = [v1]p + [v2]YA = (x;y);
4. v = x mod q;
5. если v = r => подпись верна.