2018-03-09
113
В реальных системах алгоритм RSA реализуется следующим образом. Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В, так как в этом случае не будет необходимости в передаче секретного ключа. Рассмотрим последовательность действий пользователя В и пользователя А.
Формирование критпосистемы (на строне получателя информации) состоит в выборе параметров алгоритма и вычислении пары ключей:
1. Пользователь В выбирает два больших простых числа p и q. Это секретные параметры алгоритма, они хранятся в секрете на стороне получатателя.
2. Пользователь В вычисляет значение модуля n криптосистемы как результат умножения первых двух чисел:
n = р · q.
Это общедоступный параметр криптосистемы. Иногда его включают в открытый ключ.
|
|
|
3. Пользователь В, зная секретные параметры алгоритма p и q, вычисляет функцию Эйлера:
j (n)=(p-1)(q-1)
и выбирает случайным образом простое число e как значение открытого ключа Ко с учетом выполнения условий:
Ко < j (n) и НОД(Ко , j (n))=1.
4. Пользователь В вычисляет значение секретного ключа Кс = d при решении сравнения
Кс º Ко -1 mod j (n).
Для вычисления обратного элемента в кольце Zj (n ) используют частный режим работы расширенного алгоритма Евклида для определения НОД. Это можно осуществить, так как получатель В знает пару простых чисел (p,q) и может легко найти j (n). Заметим, что Kc и n должны быть взаимно простыми.
(В принципе открытый и закрытый ключи можно поменять местами, главное, чтобы выполнялось соотношение e · d º1 mod j (n)).
5. Пользователь В пересылает пользователю А пару чисел { e,n } по незащищенному каналу.
Шифрование информации (на строне отправителя). Если пользователь А хочет передать пользователю В сообщение m, он выполняет следующие шаги.
6. Пользователь А разбивает исходный открытый текст m на блоки mi, i =1,…, N, каждый из которых может быть представлен в виде числа меньшего n
mi Î {0, 1, 2,..., n -1}.
7. Пользователь А шифрует текст, представленный в виде последовательности чисел mi с помощью ключа Ko = е по формуле
ci = mi е mod n
и отправляет криптограмму c1, …,ci. пользователю В.
Дешифрование информации (на строне получателя):
8. Пользователь В расшифровывает принятую криптограмму c1, … ,ci, используя секретный ключ Кc = d, по формуле
mi = cid mod n.
В результате будет получена последовательность чисел, которые представляют собой исходное сообщение m.
Таким образом, когда получатель В, который создает криптосистему, он защищает следующие параметры:
|
|
|
1. секретный ключ Кс;
2. пару чисел (p, q);
Открытый ключ Ко и значение модуля n публикуются и доступны каждому, кто желает послать владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. После шифрования сообщение невозможно раскрыть с помощью открытого ключа. Владелец же закрытого ключа без труда может расшифровать принятое сообщение. Противнику же длятого, чтобы определить значение секретного ключа Кc нужно суметь разложить число n на множители р и q, чтобы узнать бы "потайной ход" и вычислить значение функции Эйлера как j (n) = (p-1) (q-1).
Пример. Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA. Зашифруем сообщение "САВ". Для простоты будем использовать маленькие числа (на практике применяются гораздо большие).
Выберем p =3 и q =11.
Определим n =3·11=33.
Найдем j (n) = (p -1)(q -1)= 2·10 = 20.
Выберем в качестве секретного ключа d произвольное число взаимно простое с j (n)=20, например, d =3.
Выберем открытый ключ е = 7. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение
е · d mod j (n) = 7·3 mod 20 = 1.
9) Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А=1, В=2, С=3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа { е =7, n =33}:
ШТ1 = (37) mod 33 = 2187 mod 33 = 9,
ШТ2 = (17) mod 33 = 1 mod 33 = 1,
ШТ3 = (27) mod 33 = 128 mod 33 = 29.
10) Расшифруем полученное зашифрованное сообщение (9, 1, 29) на основе закрытого ключа { d =3, n =33}:
ИТ1 = (93) mod 33 = 729 mod 33 = 3,
ИТ2= (13) mod 33 = 1 mod 33 = 1,
ИТ3 = (293) mod 33 = 24389 mod 33 = 2.
Надежность RSA. RSA многие годы противостоит интенсивному криптоанализу. Доказано, что раскрытие шифра RSA эквивалентно решению задачи факторизации больших (100-200 двоичных разрядов) чисел. Важно, что в этой задаче для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.
Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин популярности этой СОК на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек). В настоящее время алгоритм RSA активно реализуется как в виде самостоятельных криптографических продуктов, так и в качестве встроенных средств в популярных приложениях, а также используется во многих стандартах.
