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


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


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

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

  1. Запоминает состояние машины V*, то есть содержимое всех ее лент, внутреннее состояние и позиции головок на лентах. Затем получает от V* значение ? и после этого снова запоминает состояние машины V*.
  2. Выбирает ?RZq и вычисляет h`1g?(modp) и h`2`r?(modp).
  3. Получает от V* значения a и b. Если ?ragb(modp) , то MV` останавливается.
  4. Машина MV` "отматывает" V* на состояние, которое было запомнено в конце шага 1. Выбирает tRZq и вычисляет h1ragb+1(modp) и h2?awb+1(modp).
  5. Машина MV` передает V* h1, h2 и получает ответ (a`,b`). Возможны два варианта:
      5.1. a=a` , b=b` . В этом случае моделирование закончено и MV` записывает на выходную ленту тройку (h1,h2,t) и останавливается.

      5.2. aa` или bb` . Отсюда следует, что ?ragbra`gb`(modp) . Предположим, что bb`. Из этого следует, что aa`. Следовательно, MV` может вычислить rg(b-b`)/(a-a`)(modp). Отсюда (b`-b)/(a-a`)=l - дискретный логарифм r по основанию g.

  6. Машина MV` "отматывает" V* на состояние, которое было за-полнено в начале шага 1. Получает от V* значение ?.
  7. Выбирает ?RZq вычисляет h1g?(modp) и h2w?(modp) и передает их V*.
  8. Получает от V* значения a и b. Если ?ragb(modp) , то MV` останавливается.




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



    Книжный магазин