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

       

Распределение ключей, цифровая подпись, схемы аутентификации


Функция дискретного экспоненцирования, описанная выше, широко используется в современной криптографии, в частности, при открытом распределении ключей Диффи-Хеллмана, для генерации и верификации подписей в схемах электронной цифровой подписи, для построения различных схем аутентификации сообщений, идентификации пользователей вычислительных систем и т.п. Следовательно, существует принципиальная возможность построения программных чекеров, самотестирующихся, самокорректирующихся программ. Продемонстрируем это на примере схемы цифровой подписиRSA (рис. 4.10).

Пусть программа P

предположительно вычисляет RSA-функцию и для x,y,zÎZ>0 с x,y<z

и НОД(x,z)=1. Тогда чекер CPRSA(x,y,z;k) работает следующим образом [KA].

Доказательства существования чекера для RSA-криптоалгоритма приведены в работе [KA]. Там же приведены RSA-чекеры для фиксированного модуля криптосистемы.

Program C_RSA_(x,y,z;k); {вход x,y,z,k выход («Норма»,«Сбой»)}

         begin

               t1:=é-klog99/1002ù;

               t2:=é-k/log4/52ù;

               for l=1 to t1 do

          begin

                       i:=random(Z);                {random - функция случайного равновероятного выбора из [1,...,z[};

                       if P(x,i,z)º0 (mod z) output «Сбой» and STOP;

                       i,j:=random(Z);              {random - функция случайного равновероятного выбора из [1,...,z[};

                       if P(x,i,z)P(x,j,z)¹P(x,i+j,z)(mod z) output «Сбой» and STOP;

                       i:=random(Z);                {random - функция случайного равновероятного выбора из [1,...,z[};

                       if P(x,i,z)ºP(x,1,z)¹P(x,i+1,z)(mod z) output «Сбой» and STOP;

                   end;

               for l=1 to t2 do

          begin

                       r:=random(Z);               {random - функция случайного равновероятного выбора из [1,...,z[};

                       if P(x,y,z)P(x,r,z)¹P(x,y+r,z)(mod z) output «Сбой» and STOP;

                   end;

               output «Норма»;

end.

Рис.4.10. Псевдокод алгоритма RSA-чекера



Содержание раздела