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


Методы создания самотестирующихся


Псевдокод алгоритма AxmoduloN

Program Exp(x,N,A,R); {вход x,N,A, выход R} begin B:=1; for i:=1 to n do begin B:=(B*B)modN; if [i]=1 then B:=(A*B)modN; end; R:=B; end.

Из описания алгоритма видно, что число обращений к операции вида (A*B)moduloN будет logx+ ?(x), где ?(x) число единиц в двоичном представлении операнда x или вес Хэмминга x.

Построение самотестирующейся/самокорректирующейся программной пары для функции дискретного экспоненцирования.

Сначала рассмотрим следующие 4 алгоритма (см. рис.2.6 - 2.9). Для доказательства полноты и безопасности указанной пары доказывается сле-дующая теорема.

Теорема 2.2. Пара программ S_K_exp(x,M,q,g,?) и S_T_exp(x,M,q,g,?) является (1/288,1/8,1/8)-самокорректирующейся/ самотестирующейся про-граммной парой для функции gxmoduloM, с входными значениями, выбранными случайно и равновероятно из множества In.

Для доказательства теоремы необходимо доказать следующие две леммы.

Лемма 2.1. Программа S_K_exp(M,q,g,?) является (1/8)-самокорректирующейся программой для вычисления функции gxmoduloM в отношении равномерного распределения Dn.

Доказательство. Полнота программы S_K(') означает, что если оракульная программа P(x), обозначаемая как Exp(') выполняется корректно, то и самокорректирующаяся программа S_K(') будет выполняться кор-ректно. В данном случае полнота программы очевидна. Если P(x) коррект-но вычислима, то из следует, что

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

Рис. 2.7. Псевдокод алгоритма 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.

Рис. 2.8. Псевдокод алгоритма теста линейной состоятельности 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.

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

Для доказательства безопасности сначала необходимо отметить, что так как x1 RZq, то и x2 имеет равномерное распределение вероятностей над Zq.




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



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