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


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


В противном случае вычисляет t=[?-al-b](mod q), выдает (h1,h2,t) на выходную ленту и останавливается.

К пп. 7 и 8 необходимо сделать следующее пояснение. Поскольку logg(p)wlogr(p)?, из этого следует, что logw(p)?logg(p)r. Отсюда

h2w?wb+1walwb+1?a(modp)

Из описания моделирующей машины MV` очевидно, что она работает за полиномиальное время. Величины (h1,h2,t) на шаге 5.1 выбираются в точности как в протоколе и поэтому имеют такое же распределение вероятностей. Кроме того, значения (h1,h2), выбираемые на шаге 7, имеют такое же распределение, как и в протоколе. Чтобы показать что и t имеет одинаковое распределение, достаточно заметить, что машина V* не может по h1 и h2 определить, с кем она имеет дело - с S или MV`.Поэтому, даже если бы V* могла каким-либо "хитрым" образом строить a и b с учетом (h1,h2), распределение вероятностей величин a и b в обоих случаях одинаковы. Но значение t определяется однозначно четверкой величин a, b, h1, h2, при условии выполнения проверки на шаге 5 протокола.

Таблица 3.2. Отвергающий протокол является протоколом доказательства с абсолютно нулевым разглашением.

Доказательство. Полнота протокола очевидна. Если абоненты S и V следуют протоколу, тогда абонент V всегда примет доказательства абонента S.

Для доказательства корректности прежде всего заметим, что если logg(p)wlogr(p)?, то a и b, выбираемые абонентом V на шаге 1, не несут в себе никакой информации о значении ?. Поэтому, если S может "открыть" c, сгенерированное им на шаге 2, лишь единственным образом (то есть выдать на шаге 4 единственное значение R, соответствующее данному a), то проверка на шаге 5 будет выполнена с вероятностью 1/2 в одном цикле и с вероятностью 1/2l во всех l циклах.

Если же S может сгенерировать c таким образом, что с вероятностью, которая не является пренебрежимо малой, он может на шаге 4 "открыть" оба значения ?, то есть найти R1 и R2 такие, что и , то алгоритм, который использует S для этой цели, можно использовать для вычисления дискретных логарифмов: loggd=R2-R1.




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