5.4. Асимметричные системы шифрования

Наиболее перспективными системами криптографической защиты данных являются системы с открытым ключом, который начали интенсивно развиваться с 1976 года, когда два американца Диффи и Хелман разработали основы использования двухключевой криптографии. В таких системах для шифрования данных используется один ключ, а для расшифровки другой. Первый ключ не является секретным и может быть опубликован для использования всеми пользователями системы, которые зашифровывают данные. Расшифровка данных с помощью известного ключа невозможна. Для расшифровки данных получатель зашифрованной информации использует второй ключ, который является секретным. Разумеется, ключ расшифровки не может быть определен из ключа шифрования. Использование двух ключей позволяет решить проблемы распространения ключей для абонентов, находящихся на географическом отдалении друг от друга.

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

Шифр Ривеста - Шамира – Алдемана RSA.

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году система RSA. Ее название происходит от первых букв фамилий авторов Rivest, Shamir и Aldeman, которые придумали ее во время совместных исследований в Массачусетском Технологическом институте в 1977 году. Она основана на вычислительной сложности задачи разложения очень больших целых чисел на простые сомножители. Алгоритм ее работает следующим образом:

Генерация параметров метода.

1. Выбираем два больших простых числа p и q.

2. Вычисляем N = p ∙q, и функцию Эйлера (значение равно количеству натуральных чисел k < N, взаимно простых с N).

3. Находим число e, взаимно-простое с ,

4. Находим число d из условия наибольший общий делитель e ∙ d = 1 mod . Для нахождения d используем расширенный алгоритм Евклида. Для этого решим в целых числах уравнение . (*)

5. Значение d положим равным найденному b. Если множитель b окажется меньшим нуля, следует заменить его на .

Пара (N,e) объявляется открытым ключом и используется для шифрования. Параметр d является секретным и используется для расшифровки данных.

Шифрование.

Шифрование производится по формуле , где x – код исходного символа. Обратное раскодирование производится по формуле , и основано на теореме Эйлера .

Проверим вычисление. Из формулы (*) получим

.

5.5. Алгоритм ЭльГамаля.

В 1985 году Т.Эль-Гамаль (США) предложил следующую схему шифрования на основе возведения в степень по модулю большого простого числа P. Алгоритм Эль-Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется большое простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется .

Общедоступными ключами являются y, g и p, а секретным ключом является х. Для шифрования сообщения M выполняем следующее:

1. Выбираем случайное число k, взаимно простым с p-1, т.е. Н.О.Д.(k, p-1)=1.

2. Вычисляем ,

3. Вычисляем . Пара (a, b) является шифротекстом.

Для расшифровки шифротекста, вычисляем

.

Сделаем проверку:

Пример. Выберем p=11, g=2, секретный ключ x=8. Вычисляем . Начальные параметры шифрования подготовлены.

Пусть cообщение M=5. Выбираем случайное число K=9. Убедимся, что Н.О.Д.(k, p-1)=

Н.О.Д.(9, 10)=1. Вычисляем пару (a, b):

, , (a, b)=(6, 9)-шифрограмма.

Для расшифровки сообщения (a, b), находим

, откуда, . Поскольку, , то , откуда M=5.