Генерация подписи

I. Генерация подписи. Пусть каждый пользователь S имеет один открытый ключ P и два секретных ключа S1 и S2. Ключ S1 всегда остается в секрете, он необходим для генерации подписи. Ключ S2 может быть открыт для того, чтобы конвертировать схему подписи с верификацией по запросу в обычную схему электронной цифровой подписи.

Вместе с обозначениями секретного и открытого ключей xRZq и yRZp (взятых из отечественного стандарта на электронную цифровую подпись) введем также обозначения S1=x и S2=u, uRZq, а также открытый ключ P=(g, y, w), где wgu(mod p). Открытый ключ P публикуется в открытом сертифицированном справочнике.

Подпись кода m вычисляется следующим образом. Выбирается kRZq и вычисляется rgk(mod p). Затем вычисляется s[xr+mku](mod q). Пара (r, s) является подписью для кода m. Подпись считается корректной тогда и только тогда, когда rugswyrw, где wm1(mod q).

Проверка подписи (с участием подписывающего) осуществляется посредством следующего интерактивного протокола.

II. Протокол верификации. Абонент вычисляет γ gswyrw(mod p) и просит абонента S доказать, что пара (r, s) есть его подпись под кодом m. Эта задача эквивалентна доказательству того, что дискретный логарифм γ по основанию r равен (по модулю p) дискретному логарифму w по основанию g, то есть, что logg(p)wlogr(p)γ. Для этого:

  1. Абонент V выбирает a, bRZq, вычисляет δ ragb(mod p) и посылает δ абоненту S.
  2. Абонент S выбирает tRZq, вычисляет h1δ g1(mod p), h2h1u(mod p) и посылает h1 и h2 абоненту V.
  3. Абонент V высылает параметры a и b.
  4. Если δ ragb(mod p), то абонент S посылает V параметр t; в противном случае останавливается.
  5. Абонент V проверяет выполнение равенств h1ragb+1(mod p) и h2γawb+1(mod p).

Если проверка завершена успешно, то подпись принимается как корректная.

III. Отвергающий протокол. В отвергающем протоколе S доказывает, что logg(p)wlogr(p)γ. Следующие шаги выполняются в цикле l раз.

  1. Абонент V выбирает d, eRZq, d1, βR{0,1}. Вычисляет age(mod p), bwe(mod p), если β=0 и are(mod p), e(mod p), если β=1. Посылает S значения a, b, d.
  2. Абонент S проверяет соотношение au(mod p)b. Если оно выполняется, то a=0, в противном случае a=1. Выбирает RRZq, вычисляет cdagR(mod p) и посылает V значение c.
  3. Абонент V посылает абоненту S значение e.
  4. Абонент S проверяет, что выполняются соотношения из следующих двух их пар: age(mod p), bwe(mod p) и are(mod p), e(mod p). Если да, то посылает V значение R. Иначе останавливается.
  5. Абонент V проверяет, что dβgRc.

Если во всех l циклах проверка в п.5 выполнена успешно, то абонент V принимает доказательства.

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

Доказательство. Требуется доказать, что вышеприведенный протокол удовлетворяет трем свойствам: полноты, корректности и нулевого разглашения [27,29].

Полнота означает, что если оба участника (V и S) следуют протоколу и (r, s) корректная подпись для сообщения m, то V примет доказательство с вероятностью близкой к 1. Из описания протокола верификации очевидно, что абонент S всегда может надлежащим образом ответить на запросы абонента V, то есть доказательство будет принято с вероятностью 1.

Корректность означает, что если V действует согласно протоколу, то какие действия не предпринимал бы S, он может обмануть V лишь с пренебрежимо малой вероятностью. Здесь под обманом понимается попытка S доказать, что logg(p)wlogr(p)γ, когда на самом деле эти логарифмы не равны.

Предположим, что logg(p)wlogr(p)γ. Ясно, что для каждого a существует единственное значение b, то которое дает данный запрос δ. Поэтому δ не содержит в себе никакой информации об a. Если S смог бы найти h1, h2, t1 и t2 такие, что

где a1a2, то тогда выполнялось бы соотношение

logg(p)r[(a1a2)1((b2b1)+(t2t1))](modq)logw(p)γ.

Отсюда, очевидно, следует, что logg(p)wlogr(p)γ. В самом деле, пусть logw(p)γ logg(p)r λ. Тогда

что противоречит предположению. Следовательно, какие бы h1, h2, t1 и t2 не выбрал S, проверка, которую проводит V, может быть выполнена только для одного значения a. Отсюда вероятность обмана не превосходит 1/q. Отметим, что протокол верификации является безусловно стойким для абонента V, то есть доказательство корректности не зависит ни от каких предположений о вычислительной мощности доказывающего (S).

Свойство нулевого разглашения означает, что в результате выполнения протокола абонент V не получает никакой полезной для себя информации (например, о секретных ключах, используемых S). Для доказательства нулевого разглашения необходимо для любого возможного проверяющего V построить моделирующую машину MV, которая является вероятностной машиной Тьюринга, работает за полиномиальное в среднем время и создает на выходе (без участия S) такое же распределение случайных величин, которое возникает у V в результате выполнения протокола. В нашем случае, случайные величины, которые "видит" V, это h1, h2, и t. Необходимо доказать, что протокол верификации является доказательством с абсолютно нулевым разглашением, то есть моделирующая машина создает распределение случайных величин (h1, h2, t), которое в точности совпадает с их распределением, возникающим при выполнении протокола. Моделирующая машина MV использует в своей работе V в качестве "черного ящика".


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок