36.3. Схема шифрования Эль Гамаля

Схема Эль Гамаля, предложенная в 1985 г., может быть использована как для шифрования, так и для цифровых подписей. Безопасность схемы Эль Гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле.

Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < P. Числа Р и G могут быть распространены среди группы пользователей.

Затем выбирают случайное целое число X, причем X<P. Число X является секретным ключом и должно храниться в секрете.

Далее вычисляют Y = G^X mod P. Число Y является открытым ключом.

Для того чтобы зашифровать сообщение M, выбирают случайное целое число K, 1< K< P –1, такое, что числа К и (Р –1) являются взаимно простыми.

Затем вычисляют числа

a = G^K mod P,

b = Y^K M mod P.

Пара чисел (a,b) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М.

Для того чтобы расшифровать шифртекст (a,b), вычисляют

M = mod P. ()

Поскольку

a^X  G^KX mod P,

Y^K G^KX M (mod P),

то соотношение (*) справедливо.

Пример. Выберем P=11, G=2, секретный ключ X=8. Вычисляем

Y = G^X mod P = 2⁸ mod 11 = 256 mod 11 = 3.

Итак, открытый ключ Y=3. Пусть сообщение М=5. Выберем некоторое случайное число К=9. Убедимся, что НОД (К, Р–1) =1. Действительно, НОД (9, 10) =1. Вычисляем пару чисел a и b:

a = G^K mod P = 2⁹ mod 11 = 512 mod 11 = 6,

b =Y^K M mod P = 3⁹∙5 mod 11 = 19683∙5 mod 11 = 9.

Получим шифртекст (a, b) = (6, 9). Выполним расшифрование этого шифртекста. Вычисляем сообщение М, используя секретный ключ X:

M = b/a^X mod P = 9/6⁸ mod 11.

Выражение M = 9/6⁸ mod 11 можно представить в виде 6⁸ M 9 mod 11 или 1679616  M 9 mod 11. Решая данное сравнение, находим М = 5.

36.4. Схема шифрования Полига-Хеллмана

Шифр Полига – Хеллмана похож на RSA. Она представляет собой несимметричный алгоритм, поскольку используются различные ключи для шифрования и расшифрования. В то же время эту схему нельзя отнести к классу криптосистем с открытым ключом, так как ключи шифрования и расшифрования легко выводятся один из другого. Оба ключа (шифрования и расшифрования) нужно держать в секрете.

Аналогично схеме RSA криптограмма С и открытый текст Р определяются из соотношений:

С = Р^е mod n,

P = C^d mod n,

где e∙d 1 (по модулю некоторого составного числа).

В отличие от алгоритма RSA в этой схеме число n не определяется через два больших простых числа; число n должно оставаться частью секретного ключа. Если кто-либо узнает значения e и n, он сможет вычислить значение d. Не зная значений e или d, противник будет вынужден вычислять значение e=log_P C (mod n). Известно, что это является трудной задачей.

Глава 37.

Идентификация пользователя

С каждым объектом компьютерной системы (КС) связана некоторая информация, однозначно идентифицирующая его. Это может быть число, строка символов, алгоритм, определяющий данный объект. Эту информацию называют идентификатором объекта. Если объект имеет некоторый идентификатор, зарегистрированный в сети, он называется законным (легальным) объектом; остальные объекты относятся к незаконным (нелегальным).

Идентификация объекта – одна из функций подсистемы защиты. Эта функция выполняется в первую очередь, когда объект делает попытку войти в сеть.

1 шаг. Идентификация объекта. Если подсистема защиты приняла идентификатор объекта, то данный объект считается законным для данной сети.

2 шаг. Подтверждение подлинности объекта. Проверка подлинности объекта (его аутентификация) устанавливает, является ли данный объект именно таким, каким он себя объявляет.

3 шаг. Предоставлением полномочий (авторизация) объекта. Устанавливается сфера действия и доступные объекту ресурсы КС.

Перечисленные три процедуры инициализации являются процедурами защиты и относятся к одному объекту КС. Для получения доступа к ресурсам компьютерной системы, пользователь должен пройти процесс представления компьютерной системе, который включает две стадии:

• идентификацию – пользователь сообщает системе по ее запросу свое имя (идентификатор);

• аутентификацию – пользователь подтверждает идентификацию, вводя в систему уникальную, не известную другим пользователям информацию о себе (например, пароль).

Обычно процедуры идентификации и аутентификации проводятся совместно в комплексе. Для проведения процедур идентификации и аутентификации пользователя необходимы:

• наличие соответствующего субъекта (модуля) аутентификации;

• наличие аутентифицирующего объекта, хранящего уникальную информацию для аутентификации пользователя.