7.3. Система криптографической защиты rsa.

Является наиболее распространенной системой с открытым ключом и имеет очень широкое распространение.

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

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

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

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

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

Определим такое число е, для которого является истинным следующее соотношение:

(e * d) mod ((p-1) * (q-1)) = 1.

Назовем открытым ключем числа е и 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), которые представляют собой исходный текст.

САВ-312 А-1 В-2 С-3

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

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

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

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

      С(i) = (M(i)^e) mod n.      C1=9,      C2=1,      C3= 29.

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

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

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

Одной из наиболее часто используемых в повседневной жизни является программа PGP. Эта программа была разработана в 90-е годы. Отличается хорошо продуманным и мощным механизмом обработки ключей. Что вместе с бесплатным распространением сделала её фактическим стандартом для электронной подписи.