4.2.2. Стандарт цифровой нодписи DSS

Новая редакция стандарта на выработку и верификацию цифровой подписи DSS (Digital Signature Standard) принята в США 7 января 2000 г. (FIPS PUB 186-2). Согласно этому стандарту, электронная цифровая подпись может вырабатывается по одному из трех алгоритмов: DSA (Digital Signature Algorithm), основанному на проблеме логарифма в конечном поле, ANSI Х9.31 (RSA DSA) или ANSI Х9.63 (ЕС DSA - алгоритм выработки подписи, основанной на проблеме логарифма в группе точек эллиптической кривой над конечным полем).

Опишем алгоритм DSA.

1. Предварительный этан - выбор параметров.

Выбираются числар, qug, такие, что р - простое число, 2 <р <2, где / кратно 64 и 512 < / < 1024; q - простой делитель числа р-1 длиной 160 бит (2 <q < 2*); g - элемент порядка qbZp. g выбирается в виде g = h~где 1 <h<p- 1 мк > 1. Эти три числа являются открытыми данными и могут быть обш,ими для группы пользователей.

Выбирается секретный ключ х, О < х < , и вычисляется открытый ключ для проверки подписи у = (mod р).

2. Выработка электронной цифровой подписи. Вычисляется значение хэш-функции от сообш,ения h(/w). При

этом используется алгоритм безопасного хэширования SHA-1 (Secure Hashing Algorithm), на который ссылается стандарт (FIPS PUB 180-1). Значение хэш-функции h(/w) имеет длину 160 бит.

Далее подписываюш,ий выбирает случайное или псевдослучайное значение к, О < к < q, вычисляет к (mod q), и вырабатывает пару значений:

г = g*" (mod p)(mod q); s = k (h(/w) + xr) (mod q)

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

3. Верификация электроппой цифровой подписи.

Пусть было принято сообш,ение т\. Тогда уравнение проверки выглядит следуюш,им образом:

(mod/>)(mod<7).

В самом деле:

h(mys-> . yr-s-> p)(jr,odq) = g*")- • g"-- (modp)(modq) =

g(k-)-Wm)xr)-(MmHxr)p)(mod) = g*(modpXmodq) Г.

Алгоритм выработ1си ЭЦП, основанный на эллиптических кривых, может быть описан следуюш,им образом: 1. Выбор параметров.

Стандарт определяет поля, над которыми задаются эллиптические кривые. Это простые поля Галуа и поля Галуа характеристики 2. Выбор полей в стандарте сделан исходя из требования повышения вычислительной эффективности машинных операций умножения в поле. Для этого в качестве простых модулей выбраны так называемые обобш,енные числа Мерсенна (Табл. 4.1).

Стандарт фиксирует кривые, которые должны использоваться в алгоритмах, и примерные базовые точки на этих кривых. Пользователь может либо воспользоваться приведенными в стандарте базовыми точками, либо сгенерировать свои, если, например, ему понадобится обеспечить криптографическое разделение сетей ЭВМ. В частности, кривые Р-192 ... Р-521 представляют собой эллиптические кривые простого порядка г вида х" -Ъх + b над полем GF{p).

Таблица 4.1.

Для задания кривых над полями характеристики 2 выбраны порождаюш,ие многочлены, указанные в табл. 4.2. При этом возможно использовать представление полей как в полиномиальном, так и в нормальном базисах.

Таблица 4.2.

Коэффициенты b заданы для каждого размера поля. Например, кривая Р-521 задается коэффициентом b = 05\ 953еЬ961 8elc9alf 929а21а0 Ь68540ее a2da725b 99b315f3 Ь8Ь48991 8efl09el 56193951 ec7e937b 1652c0bd 3bblbf07 3573dfB8 3d2c34fl ef451fd4 6b503f00 (в шестнадцатеричном виде)

и имеет порядок

г = 68647976601306097149819007990813932172694353 0014330540939446345918554318339765539424505774633321719 7532963996371363321113864768612440380340372808892707005 449 (в десятичной записи).

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

Для каждого из полей GF{2") в стандарте указаны по 2 кривых: псевдослучайная видау + ху = + + Ь, имеющая кофактор 2, и специальная кривая Коблица, или аномальная двоичная кривая вида + ху = х + ах + 1, где а = О или 1. Кофактор кривой Коблица равен 2, если а = 1 и 4, если а = 0. Например, для поля GF{l}) псевдослучайная кривая задается коэффициентом Ь2 0а601907 Ь8с953са 1481еЬ10 512f7874 4a3205fd, а кривая Коблица коэффициентом а=\.

Генерация ключевой пары. Пользователь выбирает в качестве секретного ключа целое число d, О < d < п, где п - порядок базовой точки G на эллиптической кривой. Далее он вычисляет Q = dG и публикует Q в качестве открытого ключа.

2. Выработка ЭЦП.

Для того, чтобы подписать сообщение т, пользователь:

1. выбирает случайное число k,0<k<n-\;

2. вычисляет kG = (xi, yi), г = х\ mod п. Если г = О, то перейти к шагу 1;

3. вычисляет mod п;

4. вычисляет е = SHA(/w). Выбор варианта функции хэширования осуществляется в зависимости от используемого поля.

5. вычисляет s = (е + dr) mod п. Если s = О, то перейти к шагу 1;

6. Подписью сообщения т является пара {г, s). 3. Верификация ЭЦП.

Для проверки подписи получатель сообщения выполняет следующие действия:

1. проверяет, что г и s лежат на интервале (О, п).

2. вычисляет е = SHA(/w);

3. вычисляет w = mod п;

4. вычисляет щ = ew mod nHU2 = rw mod n;

5. вычисляет X= UiG + UiQ. ЕслиХ= oo, то подпись отвергается, иначе, вычислить v = X\ mod п, где Х= {х\, У&,

6. Принять подпись, если и только если v = r. Корректность схемы доказывается несложно. Если сообщение т действительно подписано отправителем, то s = {е + dr) mod п. Откуда

к = s~{e + dr) = s~e + srd =we + wrd =u\ + ujd (mod n).

TaicHM образом, U\G + UjQ = {щ + U2d)G = kG, и поэтому v = г, как и требуется.

4.2.3. Стандарт цифровой нодписи ГОСТ Р 34.10-94

Российский стандарт ЭЦП разрабатывался позже первоначального варианта американского, поэтому параметры этого алгоритма выбраны с учетом возросших возможностей потенциального противника по вскрытию криптосистем. В частности, увеличена длина значения хэш-функции, что снижает вероятность столкновений, и, соответственно, порядок элемента-генератора, что делает более сложным решение задачи дискретного логарифма для восстановления секретного ключа При описании алгоритма будут использоваться следующие обозначения:

В - множество всех конечных слов в алфавите В = {0,1}.

А - длина слова А

Vk(2) - множество всех двоичных слов длины к. А В - конкатенация слов А и В, также обозначается как АВ. А - конкатенация к экземпляров слова А. <N>k - слово длины к, содержащее запись N(mod 2), где N -неотрицательное целое.

Ф - побитовое сложение слов по модулю 2.

[+] - сложение по правилу А [+] В = <А+В>к (к = \А\ = В).

т - передаваемое сообщение.

nil - полученное сообщение

h - хэш-функция, отображающая последовательность т в слово h{m) G У25б(2).

р - простое число, 2 <р< 2 либо 2 <р< 2\

q - простое число, 2"* < q < 2 и q является делителем для

а - целое число, \ <а<р-\, при этом a(mod р) = \. к - целое число, О < А: < q.

X - секретный ключ пользователя для формирования подписи, О < х < .

у - открытый ключ для проверки подписи, у = (/(mod р).

Система ЭЦП включает в себя процедуры выработки и проверки подписи под данным сообщением.

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

Числа р, q и а, являющиеся параметрами системы, не являются секретными. Конкретный набор их значений может быть общим для группы пользователей. Целое число к, которое генерируется в процедуре подписи сообщения, должно быть секретным и должно быть уничтожено сразу после выработки подписи. Число к снимается с физического датчика случайных чисел или вырабатывается псевдослучайным методом с использованием секретных параметров.

Процедура выработки подписи включает в себя следующие шаги:

1. Вычислить h{m) - значение хэш-функции h от сообщения т. Если h(/w)(mod q) = О, то присвоить h{m) значе-

ние Ol.

2. Выработать целое числоk,0<k<q.

3. Вычислить два значения: г = (/(mod р)иг = г (mod q). Если г = 0, то перейти к шагу 2 и выработать другое значение числа к.

4. С использованием секретного ключа х пользователя вычислить значение s = {хг + Мл{т)){той q). Если s = О, то перейти к шагу 2, в противном случае закончить работу алгоритма.

Заметим, что сообщение, дающее нулевое значение хэш-функции, не подписывается. В противном случае уравнение подписи упростилось бы до S = хг (mod q) и злоумышленник легко мог бы вычислить секретный ключ х.

Проверка цифровой подписи возможна при наличии у получателя открытого ключа отправителя, пославшего сообщение.

Уравнение проверки будет следующим:

г (а-С". у--"*"(mod p))(mod q). В самом деле.

.у-гМт)-(.jQp)){moAq) = (a*")" • а"--*")"(modp))(modq)-

= a"--\mod p)(modq) = a""-\mod p)(modq) =

k-h(m)--h(m)

(modp)(modq) = a (modp)(modq) = r.

Вычисления no уравнению проверки реализуются следующим образом:

1. Проверить условия: 0<5<иО<г<. Если хотя бы одно из этих условий не выполнено, то подпись считается недействительной.

2. Вычислить h(/wi) - значение хэш-функции h от полученного сообщения nil.

Если h(/Wi)(mod q) = О, присвоить h(/Wi) значение Ol.

3. Вычислить значение v = (h(/wi))~(mod q), что является не чем иным, как мультипликативным обратным к h(/wi) (mod q). Вообще говоря, алгоритм проверки можно несколько ускорить, если вычислять h(/wi)"(mod q) с помощью расширенного алгоритма Евклида, а не путем возведения в степень.

4. Вычислить значения: Zl = sv(mod q) и