Арифметические свойства российского стандарта цифровой подписи

Механизм цифровой подписи.Задаются следующие параметры, используе­мые алгоритмом: p — простое число, 2(\⁵⁰⁹⁾ <р<2(\⁵¹²⁾ либо 2(\¹⁰²⁰⁾ < р< 2(\¹⁰²⁴⁾; q — простое число, 2(\²⁵⁴⁾ < q < 2(\²⁵⁶⁾; а — целое число в пределах 1 < а < p -1 такое, что a(\^q) mod p = 1; x — целое число в пределах 0 < x < q; у — це­лое число, равное а(\^х) mod p; Μ — целое число в пределах 0 < Μ < q.

Число x называют секретным ключом пользователя, у — открытым ключом пользователя, Μ — сообщением. В соответствии с алгоритмом проверки подписи в ГОСТ Ρ 34.10—94 электронную подпись можно ввести следующим образом.

Пусть дано сообщение М. Подписью к Μ называется пара целых чисел (r,s) таких, что

1<r<q, 0<s<q

r=(a(\sM(\q-2) mod q)y(\-rM(\q-2) mod q) mod p) mod q

Теорема 14.7.1.Пусть задано целое Μ(0 < Μ < q). Тогда существует ровно q различных решений (r(/k),s(/k))(\q-1)(/k=0) уравнения (14.7.2), причем

r(/k)=(a(\k) mod q), s(/k)=(x*n(/k)+kM) mod q

Доказательство.Легко проверить путем подстановки, что все пары (r(/k),s(/k)) заданные по формулам (14.7.3) и (14.7.4), удовлетворяют равенству (14.7.2). Все эти пары различны. Действительно, если (r(/i),s(/i))=(r(/j),s(/j)) при некоторых i<>j

то, используя (14.7.4), получаем xr(/i)+iM=(\-)xr(/j)+jM(mod q), откуда следует:

(i - j)M=(\-)0(mod q), что вместе с (M,q)=1 дает i=(\-)j (mod q). Последнее сравне-

ние возможно, только если i = j. Таким образом, чтобы доказать утверждение, достаточно показать, что сравнение (14.7.2) имеет не более q решений.

Будем рассматривать циклическую подгруппу группы Z(\*)(/p):

<a>(/p)={a(\k) mod p: k=0, .., q-1}

порожденную элементом а. Для mE{0, .., q-1}определим функцию кси(m) как

число различных элементов группы <a>(/p), которые по модулю q дают остаток т.

Очевидно, равенство SUM(/m=0)(\q-1)кси(m)=q.Пусть Φ — количество решений (14.7.2),

Ф(r) — количество различных s (0<=s<q) таких, что пара (r,s) есть решение

(14.7.2). Тогда Ф=SUM(/r=0)(\q-1)Ф(r)

Зафиксируем r. Поскольку у = а(\^х) тоd р, то имеем равенство

a(\sM(\q-2) mod q)y(\-rM(\q-2) mod p)=a(\a(s-rx)M(\q-2) mod p)

Когда s пробегает значения от 0 до q-1, то v=(s-rx)M(\q-2) также пробегает

(в другом порядке) эти значения. Тогда a(\v) mod p пробегает все элементы груп­пы <a>(/p), когда s изменяется от 0 до q -1. Количество различных sтаких, что

r=(a(\sM(\q-2) mod q)y(\-rM(\q-2) mod q) mod p) mod q

есть Φ (r), с одной стороны, и кси(r) — с другой. Тогда

Ф=SUM(/r=0)(\q-1)Ф(r)=SUM(/r=0)(\q-1)кси(r)=q

Итак, количество различных решений сравнения (14.7.2) равно q, и все эти решения описаны по формулам (14.7.3) и (14.7.4).

Введем множества

R(M)={(r(/k),s(/k)):r(/k)=(a(\k) mod p) mod q, s(/k)=(xr(/k)+kM) mod q, 0<=k<=q-1}

S(M)={(r,s)ER(M)r-1)rs<>0}.

Тогда множество R(M) состоит из всех решений уравнения (14.7.2), a S(M) — из всех подписей к М.

Чтобы сформировать подпись к сообщению М, необходимо решить сравне­ние (14.7.2) относительно (r, s). Такую пару можно вычислить по формулам (14.7.3) и (14.7.4). Но для этого необходимо знать значение секретного ключа x и параметра к. Таким образом, получаем следующие алгоритмы.