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




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


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

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

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

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

  • Машина MV` запоминает состояние машины V*.
  • Получает от V* значения a, b и d.
  • Выбирает ?R{0,1}, RRZq и вычисляет cdagR(modp) . Посылает V* значение c.
  • Получает от V* значение e.
  • Проверяет, было ли "угадано" на шаге 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. В таких схемах открытие определенного секретного параметра некоторой схемы подписи с верификацией по запросу позволяет трансформировать последнюю в обычную схему цифровой подписи.




    Содержание  Назад  Вперед