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

№ п/п	Описание операции	Пример
	Выбираются два простых числа 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

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

№ п/п	Описание операции	Пример
	Выбираются простое число p и два любых случайных числа g и x меньше p.	p=23, g=3, x=5
	Вычисляется y = g^x mod p	y = 3⁵ mod 23 = 243 mod 23 = 13
	Открытый ключ - y, g и p. Причем g и p можно сделать общими для группы пользователей. Закрытый ключ - x.

Перед шифрованием вначале выбирается k взаимно простое с p-1, после чего шифрограмма генерируется по следующим формулам

a = g^k mod p, (10)

b = (y^k mod p) Å T, (11)

где a, b – зашифрованное сообщение.

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

T = (a^x mod p) Å b. (12)

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k=7 приведен в таблице. Первая часть шифрованного сообщения - a = 37 mod 23 = 2.

Таблица 8

⇐ Предыдущая 1 2 3 4 567 Следующая ⇒