Безопасность программного обеспечения компьютерных систем


Краткое описание криптографических средств контроля целостности и достоверности программ - часть 15


Так как при случайном выборе значения d логарифм loggd может быть вычислен с вероятностью, которая не является пренебрежимо малой, это противоречит гипотезе о трудности вычисления дискретных логарифмов.

Далее доказывается, что отвергающий протокол является доказательством с абсолютно нулевым разглашением. Для этого необходимо для всякого возможного проверяющего V* построить моделирующую машину MV`, которая создает на выходе (без участия S) такое же распределение случайных величин (в данном случае, c и R), какое возникает у V* в результате выполнения протокола.

Моделирующая машина

Следующие шаги выполняются в цикле l раз.

  1. Машина MV` запоминает состояние машины V*.
  2. Получает от V* значения a, b и d.
  3. Выбирает ?R{0,1}, RRZq и вычисляет cdagR(modp) . Посылает V* значение c.
  4. Получает от V* значение e.
  5. Проверяет, было ли "угадано" на шаге 2 значение ? (это значение было "угадано", если age(modp), bwe(modp) и ?=0, либо ?re(modp), b?e(modp) и ?=1). Если да, то записывает на входную ленту значение (c,R). В противном случае "отматывает" V* на то состояние, которое было запомнено на шаге 1, и переходит на шаг 2.

Легко видеть, что распределения случайных величин (c,R), возникающее в процессе выполнения протокола и создаваемые моделирующей машиной MV`, одинаковы, поскольку R в обоих случаях - чисто случайная величина, а величина c записывается на выходную ленту машины MV` только тогда, когда ? совпало с ?.

Поскольку значение ? выбирается машиной MV` на шаге 3 случайным образом, а c не дает V* никакой информации о значении ?, на каждой итерации ? будет угадано с вероятностью 1/2. Отсюда следует, что машина MV` работает за полиномиальное в среднем время.

В работе показано, как строить схемы конвертируемой и селективно конвертируемой подписи с верификацией по запросу на основе отечественного стандарта ГОСТ Р 34.10-94. В таких схемах открытие определенного секретного параметра некоторой схемы подписи с верификацией по запросу позволяет трансформировать последнюю в обычную схему цифровой подписи.




Начало  Назад  Вперед