15. Криптосистема шифрования данных rsa

Алгоритм RSA предложили в 1978 г. три автора: Р.Райвест (Rivest), А.Шамир (Shamir) и А.Адлеман (Adleman). Алгоритм полу­чил свое название по первым буквам фамилий его авторов. Алго­ритм RSA стал первым полноценным алгоритмом с открытым клю­чом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Надежность алгоритма основывается на трудности факто­ризации больших чисел и трудности вычисления дискретных лога­рифмов.

Процедуры шифрования и расшифрования в криптосистеме RSA

Под простым числом будем понимать такое число, которое делится только на 1 и на само себя. Взаимно простыми числами будем называть такие числа, которые не имеют ни одного общего делителя, кроме 1.

Чтобы использовать алгоритм RSA надо сначало сгенерировать открытый и секретный ключи, выполнив следующие шаги:

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

2. Определим n как результат умножения p на q (n=p*q).

3. Выберем большое случайное число, которое назовем d. Это число должно быть взаимно простым с результатом умножения (p-1)*(q-1).

4. Определим такое число е, для которого является истинным следующее соотношение: (e*d) mod ((p-1)*(q-1)) = 1.

5. Назовем открытым ключем числа е и n, а секретным ключем числа d и n.

Теперь, чтобы зашифровать данные по известному ключу {e,n}, необходимо сделать следующее:

• разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа       M(i)=0, 1,..., n-1;

• зашифровать текст, рассматриваемый как последовательность чисел M(i), по формуле:       С(i)=(M(i)^e) mod n.

Чтобы расшифровать эти данные используя секретный ключ {d,n}, необходимо выполнить следующие вычисления: M(i)=(C(i)^d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Приведем простой пример использования метода RSA для шифрования сообщения "CAB". Для простоты будем использовать очень маленькие числа (на практике используются намного большие числа).

1. Выберем р=3 и q=11.

2. Определим n=3*11=33.

3. Найдем (р-1)*(q-1)=20. Следовательно, в качестве d выберем любое число, которое является взаимно простым с 20, например d=3.

4. Выберем число e. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (e*3) mod 20 = 1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел в диапазоне 0...32. Пусть буква A изображается числом 1, буква B - числом 2, а буква C - числом 3. Тогда сообщение можно представить в виде последовательности чисел 3 1 2.

Зашифруем сообщение, используя ключ {7,33}:

      C1=(3⁷) mod 33 = 2187 mod 33 = 9,

      C2=(1⁷) mod 33 = 1 mod 33 = 1,

      C3=(2⁷) mod 33 = 128 mod 33 = 29.

1. Попытаемся расшифровать сообщение {9,1,29}, полученное в результате зашифрования по известному ключу на основе секретного ключа {3,33}:

M1=(9³) mod 33 = 729 mod 33 = 3,

M2=(1³) mod 33 = 1 mod 33 = 1,

M3=(29³) mod 33 = 24389 mod 33 = 2.

Таким образом, в результате расшифрования сообщения получено исходное сообщение "CAB".

Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключ по известному, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Данная задача является NP - полной. Известные точные алгоритмы для решения данной задачи имеют экспоненциальную оценку вычислительной сложности, следствием чего является невозможность получения точных решений для задач большой и даже средней размерности. Более того, сам вопрос существования эффективных алгоритмов решения NP - полных задач является до настоящего времени открытым. В связи с этим для чисел, состоящих из 200 цифр (а именно такие числа рекомендуется использовать), традиционные методы требуют выполнения огромного числа операций(около 10²³).

Оценки сложности задачи ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ в зависимости от длины двоичной записи простого числа P (при правильном его выборе) приведены в таблице:

Таблица 4.1. Оценка задачи сложности дискретного логарифмирования

Длина P (в битах)	Сложность определения ключа x	Память используемая алгоритмом (в битах)	Время решения задачи на компьюре типа 109 оп/c
128	2*1012	7*106	Несколько минут
200	1016	108	Несколько месяцев
256	9*1017	109	Несколько десятков лет
512	4*1024	3*1012	Более 100 лет непрерывной работы
1024	1034	1017
1500	1041	8*1020
2000	7*1047	1024
2200	1050	1025

Все асимметричные криптосистемы пытаются взломать путем прямого перебора ключей. Поэтому в асимметричных криптосистемах используют длинные ключи. Для обеспечения эквивалентного уровня защиты ключ асимметричной криптосистемы должен быть гораздо длиннее ключа симметричной криптосистемы. Это сразу же сказывается на вычислительных ресурсах, требуемых для шифрования. Брюс Шнейер в книге "Прикладная криптография: протоколы, алгоритмы и исходный текст на C" приводит следующие данные об эквивалентных длинах ключей.

Таблица 4.1. Эквивалентные длины ключей

Длина симметричного ключа (в битах)	Длина открытого ключа (в битах)
56	384
64	512
80	768
112	1792
128	2304

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

В асимметричных криптосистемах важно, чтобы сеансовые и асимметричные ключи были сопоставимы в отношении уровня безопасности, который они обеспечивают. Если используется короткий сеансовый ключ (например, DES), то не имеет значения, насколько велики асимметричные ключи. Хакеры будут атаковать не их, а сеансовые ключи. Асимметричные открытые ключи уязвимы к атакам прямым перебором отчасти из-за того, что их тяжело заменить. Если атакующий узнает секретный асимметричный ключ, то будет скомпрометирован не только текущее, но и все последующие взаимодействия между отправителем и получателем.