Распределение ключей, цифровая подпись, схемы аутентификации
Функция дискретного экспоненцирования, описанная выше, широко используется в современной криптографии, в частности, при открытом распределении ключей Диффи-Хеллмана, для генерации и верификации подписей в схемах электронной цифровой подписи, для построения различных схем аутентификации сообщений, идентификации пользователей вычислительных систем и т.п. Следовательно, существует принципиальная возможность построения программных чекеров, самотестирующихся, самокорректирующихся программ. Продемонстрируем это на примере схемы цифровой подписи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-чекера
