сKс mod n = m,

то в результате восстанавливается исходный открытый текст m.

Именно поэтому для вычисления секретного ключа Кc используют соотношение (*).

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

В реальных системах алгоритм RSA реализуется следующим образом. Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В, так как в этом случае не будет необходимости в передаче секретного ключа. Рассмотрим последовательность действий пользователя В и пользователя А.

Формирование критпосистемы ( на строне получателя информации) состоит в выборе параметров алгоритма и вычислении пары ключей:

1. Пользователь В выбирает два больших простых числа p и q. Это секретные параметры алгоритма, они хранятся в секрете на стороне получатателя.

2. Пользователь В вычисляет значение модуля n криптосистемы как результат умножения первых двух чисел:

n = р·q.

Это общедоступный параметр криптосистемы. Иногда его включают в открытый ключ.

3.Пользователь В, зная секретные параметры алгоритма p и q, вычисляет функцию Эйлера:

(n)=(p-тест,1)(q-тест,1)

и выбирает случайным образом простое число e как значение открытого ключа Ко с учетом выполнения условий:

Ко< (n) и НОД(Ко, (n))=1.

4.Пользователь В вычисляет значение секретного ключа Кс = d при решении сравнения

Кс Ко-1 mod (n).

Для вычисления обратного элемента в кольце Z (n) используют частный режим работы расширенного алгоритма Евклида для определения НОД. Это можно осуществить, так как получатель В знает пару простых чисел (p,q) и может легко найти (n). Заметим, что Kc и n должны быть взаимно простыми.

(В принципе открытый и закрытый ключи можно поменять местами, главное, чтобы выполнялось соотношение e·d 1 mod (n) ).

344

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, чтобы узнать бы "потайной ход" и вычислить значение функции Эйлера как (n) = (p-тест,1) (q-тест,1).

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

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

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

2.Найдем (n) = (p-1)(q-1)= 2·10 = 20.

345