Процедура создания ключей

№ п/п	Описание операции	Пример
	Выбираются два простых числа p и q. Напомним, что	p=7, q=13
	Вычисляется произведение n= p * q.	n=91
	Вычисляется функция Эйлера, равная j(n)=(p-1)(q-1)=n-p-q+1. Результат расчета данной функции равен количеству положительных чисел, не превосходящих n и взаимно простым с n.	j(n)=(7-1)(13-1)= 91-7-13+1 = 72
	Выбирается произвольное число e (0<e<n), взаимно простое с результатом функции Эйлера (e ^ j(n)).	e=5
	Расчет секретного ключа d из соотношения (d*e) mod j(n) = 1.	(d*5) mod 72 = 1, d = 29
	Публикация открытых ключей e и n в специальном хранилище, где исключается возможность его подмены (общедоступном сертифицированном справочнике).

Примечания

Простое число – целое положительное число, большее единицы и не имеющее других делителей, кроме самого себя и единицы.

Взаимно простые числа – числа, не имеющие общих делителей более 1 (например, p=3, q=5, n=15, j(n)=8 – взаимно простые с 15 – 1, 2, 4, 7, 8, 11, 13, 14).

Процедуры шифрования и дешифрования выполняются по следующим формулам

C = Т^e mod n, (8)

Т = C^d mod n. (9)

где Т, C - числовые эквиваленты символов открытого и шифрованного сообщения.

Пример шифрования по алгоритму RSA приведен в следующей таблице. Коды букв соответствуют их положению в русском алфавите.

Таблица 6

Пример шифрования по алгоритму RSA

Открытое сообщение	символ	А	Б	Р	А	М	О	В
Код символа
Шифрограмма, С = Т⁵ mod 91
Открытое сообщение, Т = С²⁹ mod 91

Следует отметить, что p и q выбираются таким образом, чтобы n было больше кода любого символа открытого сообщения. В автоматизированных системах исходное сообщение переводиться в двоичное представление, после чего шифрование выполняется над блоками бит, равной длины. При этом длина блока должна быть меньше, чем длина двоичного представления n.

В заключении следует отметить стойкость данного алгоритма. В 2003 г. Ади Шамир и Эран Тромер разработали схему устройства TWIRL, которое при стоимости $ 10 000 может дешифровать 512-битный ключ за 10 минут, а при стоимости $ 10 000 000 – 1024-битный ключ меньше, чем за год. В настоящее время Лаборатория RSA рекомендует использовать ключи размером 2048 битов.

Алгоритм шифрования Эль-Гамаля.

Стойкость данного алгоритма базируется на сложности решения задачи дискретного логарифмирования.

Порядок создания ключей приводится в следующей таблице.

Таблица 7

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: