Стандарт цифровой подписи 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. Предварительный этап - выбор параметров.

Выбираются числа р, q и g, такие, что р - простое число, 21-1 < р < 21, где 1 кратно 64 и 512 < 1 < 1024; q - простой делитель числа р - 1 длиной 160 бит (2159 < q < 2160); g - элемент порядка q в Zp. g выбирается в виде g = h(p - l)/q, где 1 < h < р — 1 и h(p - l)/q > 1. Эти три числа являются открытыми данными и могут быть общими для группы пользователей.

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

2. Выработка электронной цифровой подписи.

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

Далее подписывающий выбирает случайное или псевдослучайное значение к, 0 < к < q, вычисляет к -lmod q и вырабатывает пару значений:

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

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

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

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

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

Табл. 13.1. Обобщенные числа Марсенна для эллиптических кривых

Кривая

Р

Р-192

2192-264-1

Р-224

2224 -296+1

Р-256

2256-2224 + 2192 + 296-1

Р-384

2384-2128-296 + 232-1

Р-521

2521 - 1

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

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

Табл. 13.2. Порождающие многочлены

Кривая

Порождающий многочлен p(t)

Тип нормального базиса

К-163, В-163

U63 + t7 + t6 + t3+ 1

4 233 74

К-233, В-233

t +t+l

2 283

12 7 5

К-283, В-283

t +t+t+t+l

6 409

87

К-409, В-409

t +t+l

4 571

10 5 2

К-571,В-571

t +t+t+t+l

10

Коэффициенты b заданы для каждого размера поля. Например, кривая Р—521 задается коэффициентом

b = 051 953cb961 8clc9alf 929а21а0 Ь68540сс a2da725b 99Ь3150 Ь8Ь48991 8efl 09е 1 56193951 ec7e937b 1652c0bd 3bblbf07 3573dm 3d2c34fl ef451fd4 6Ь503ГО0 (в шестнадцатеричном виде) и имеет порядок г = 686479766013060971498I900799081393217269435300143305409394463459 1855431833976553942450577463332171975329639963713633211138647686 12440380340372808892707005449 (в десятичной записи).

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

Для каждого из полей GF(2m) в стандарте указаны по две кривых: псевдослучайная вида у2 + ху = хЗ + х2 + b и специальная кривая Коблица, или аномальная двоичная кривая вида у2 + ху = хЗ + ах2 + 1, где а = 0 или I.

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

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

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

  • 1) выбирает случайное число к, 0 < к < п - 1;
  • 2) вычисляет kG = (xl, yl), г = xl(mod п). Если г = 0, то перейти к шагу 1;
  • 166
  • 3) вычисляет к-1 (mod п);
  • 4) вычисляет е = SHA(m). Выбор варианта функции хеширования осуществляется в зависимости от используемого поля;
  • 5) вычисляет s = k -1 (с + dr ) mod n . Если s = 0, то перейти к шагу 1;
  • 6) подписью сообщения т является пара (г, s).
  • 3. Верификация ЭЦП.

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

  • 1) проверяет, что г и s лежат на интервале (0, п);
  • 2) вычисляет е = SHA(m);
  • 3) вычисляет w = s-1 mod n;
  • 4) вычисляет u 1 = ew mod п и w2 = rw mod n;
  • 5) вычисляет X = ulG + u2Q. Если X = со, то подпись отвергается,

иначе, вычислить v = xl mod п, где X = (xl, yl);

6) принять подпись, если и только если v = г.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >