Теория и практика защиты программ



         

Построение самотестирующейся/самокорректирующейся - часть 2


t1:=t1+Rl;

end;

if t1/é576ln(4/b)ù>1/72 then output:=«false»;

for l=1 to é32(4/b)ù

begin

N_T(g,M,q,Re); {N-T -         процедура, реализующая тест единичной состоятельности, выход - Re}

t2:=t2+R;

end;

if t2/é32ln(4/b)ù>1/4 then output:= «false»

else output:=«true»

end.

Рис. 4.3. Псевдокод алгоритма S_T_exp

Program L_T(n,R); {вход g,M,q, выход Rl}

begin

x1:=random(q);

x2:=random(q);

x:=(x1+x2)modq;

Exp(g,x1,M,R1);

Exp(g,x2,M,R2);

Exp(g,x,M,R);

if R1×R2=R then Rl:=1

else Rl:=0;

end.

Рис. 4.4. Псевдокод алгоритма теста линейной состоятельности L_T

Program N_T(n,R); {вход g,M,q, выход Re}

begin

x1:=random(q);

x2:=(x1+1)modq;

Exp(g,x1,M,R1);

Exp(g,x2,M,R2);

if R1×g=R2 then Re:=1

else Re:=0;

end.

Рис. 4.5. Псевдокод алгоритма теста единичной состоятельности N_T

Для доказательства безопасности сначала необходимо отметить, что так как x1ÎRZq, то и x2 имеет равномерное распределение вероятностей над Zq. Так как вероятность ошибки e£1/8, то в одном цикле вероятность Prob[Rk=fM,g(x)]³3/4. Чтобы вероятность корректного ответа была не менее чем 1-b, исходя из оценки Чернова [Be1,BLR], необходимо выполнить не менее 12ln(1/b) циклов n.

Лемма 4.2. Программа S_T_exp(n,M,q,g,b) является (1/288,1/8)-самотестирующейся программой, которая контролирует результат вычисления значения функции gxmoduloM с любым модулем M.

Доказательство.

Полнота программы S_T(?) доказывается аналогично доказательству полноты в лемме 4.1, где x1,x2ÎRZq. Полнота теста единичной состоятельности вытекает исходя из следующего очевидного факта. Корректное выполнение теста [PM,g(x1)?PM.g(1)](mod M) соответствует вычислению функции:




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