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

Глава 36.

Схемы шифрования RSA,
Эль Гамаля, Полига-Хеллмана

В частях 5, 6 пособия с согласия авторов использованы материалы книг и работ:

· Ю.В. Романец, П.А. Тимофеев, В.Ф. Шаньгин. Защита информации в компьютерных системах и сетях. Радио и связь, 1999;

· Грушо А.А., Применко Э.А., Тимонина Е.Е. Криптографические протоколы. Йошкар-Ола, 2001;

· Грушо А.А., Тимонина Е.Е., Применко Э.А. Анализ и синтез криптоалгоритмов, Йошкар-Ола, 2000;

· Лекции Фролова А.Б.;

· Работы Семаева И.А..

Основные понятия модулярной арифметики

Запись

a º b (mod n)

читается так: «a сравнимо с b по модулю n». Это соотношение справедливо для целых значений a,b и n ¹ 0, тогда и только тогда, если a = k∙n+ b для некоторого целого k.

Отсюда, в частности, следует n|(a – b). Это читается как «n делит (a– b)».

Если a º b (mod n), то b называют вычетом числа a по модулю n.

Операцию нахождения вычета числа a по модулю n (mod n)

называют приведением числа a по модулю n или приведением по модулю.

Множество Z/n = {0,1,2,..,,(n –1)} с бинарными операциями сложения по модулю n и умножения по модулю n называют кольцом вычетов по модулю n. Множество {0,1,2,..,,
(n –1)}называют полным набором положительных вычетов по модулю n. Это означает, что для любого целого a (a > 0) его вычет r по модулю n есть некоторое целое число из Z/n, определяемое из соотношения

a= k∙n+ r,

где k – целое число, r остаток от деления a на n. Например, для n=12 полный набор вычетов: {0,1,2,…,11}.

Приведение по модулю n является гомоморфным отображением кольца целых чисел в кольцо целых по модулю n. Поэтому мы можем либо сначала приводить по модулю n, а затем выполнять операции сложения, умножения, либо сначала выполнять операции, а затем приводить по модулю n. Легко проверяется, что

(a + b) mod n = [a (mod n) + b (mod n)] mod n,

(a – b) mod n = [a (mod n) – b (mod n)] mod n,

(a ∙ b) mod n = [a (mod n) ∙ b (mod n)] mod n,

[a ∙ (b + c)] mod n = {[a∙ b (mod n)] + [a∙ c (mod n)]} mod n.

Вычисление степени числа a по модулю n

a^x mod n

можно выполнить как ряд умножений и последним действием выполнить деление. Модно вычислить это число быстрее, производя возведение в степень как ряд последовательных умножений совместно с приведением по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более). Например, если нужно вычислить

a⁸ mod n,

не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a) mod n.

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

((a² mod n)² mod n)² mod n.

Тем же способом вычисляют

a¹⁶ mod n = (((a² mod n)² mod n)² mod n)² mod n.

Вычисление

a^x mod n,

где x не является степенью 2, лишь немного сложнее. Двоичная запись числа x позволяет представить число x как сумму степеней 2:

x = 25₍₁₀₎ ® 1 1 0 0 1₍₂₎ – двоичное представление числа 25, поэтому 25 = 2⁴ + 2³ + 2⁰.

Тогда

a²⁵ mod n = (a∙a²⁴) mod n = (a∙a⁸∙a¹⁶) mod n =

= a ∙ ((a²)²)² ∙ (((a²)²)²)² mod n = ((((a^{2 ∙} a)²)²)² ∙ a) mod n.

При разумном накоплении промежуточных результатов потребуется только шесть умножений:

(((((((a² mod n) ∙a) mod n)² mod n)² mod n)² mod n) ∙ a) mod n.

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

УТВЕРЖДЕНИЕ. Чтобы вычислить степень mⁿ, где m элемент некоторого кольца вычетов, а n – некоторое натуральное число, достаточно выполнить не более 2[log2n] умножений, где [log2n] – целая часть числа log2n.

ДОКАЗАТЕЛЬСТВО. Пусть 2^k-1 n<2^k. Тогда [log2n]=k-1. Запишем n в двоичной системе счисления

.

Теперь mⁿ можно представить в виде

mⁿ=

Для получения значений чисел 1,m, m², m⁴,…, достаточно выполнить k-1 умножений (возведений в квадрат). Для получения значения mⁿ некоторые из приведенных чисел следует перемножить. Их не более k-1. Следовательно, для получения mⁿ потребуется не более 2(k-1)= 2[log2n] умножений.

Алгоритм Евклида для нахождения наибольшего общего делителя. Целое число a делит без остатка другое целое число b, если, и только если

b = k ∙ a

для некоторого целого числа k (т.е. остаток отделения равен 0). В этом случае a называют делителем числа b или множителем в разложении числа b на множители.

Пусть a – целое число, большее 1. Тогда a является простым числом, если его единственными положительными делителями будут 1 и само a, в противном случае a называется составным.

Любое целое n >1 может быть представлено единственным образом с точностью до порядка сомножителей как произведение простых.

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма разложения чисел на множители.

Наибольший общий делитель чисел a и b, обозначаемый как НОД (a,b) или просто (a,b), – это наибольшее целое, делящее одновременно числа a и b. В эквивалентной форме (a,b) – это то единственное натуральное число, которое делит a и b и делится на любое целое, делящее и a и b. Если НОД (a,b)=1, то целые a и b – взаимно простые.

Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Опишем алгоритм Евклида для нахождения НОД(a,b). Введем обозначения: q_i – частное;
r_i – остаток. Тогда алгоритм можно представить в виде следующей цепочки равенств:

a = b ∙q₁ + r₁, 0 < r₁< b,

b = r₁ ∙ q₂ + r₂, 0 < r₂< r₁,

r₁ = r₂ ∙ q₃ + r₃, 0 < r₃< r₂,

M M

r_k–2 = r_k–1 ∙ q_k + r_k, 0 < r_k< r_k–1,

r_k–1 = r_k ∙ q_k+1.

Остановка гарантируется, поскольку остатки r_i от делений образуют строго убывающую последовательность натуральных чисел. Из этой цепочки немедленно получаем, что r_k есть общий делитель чисел a и b и, более того, что любой общий делитель чисел a и b делит и r_k. Таким образом, r_k = НОД(a, b) или r_k = (a, b).

УТВЕРЖДЕНИЕ. Пусть a и b натуральные числа, a<b. Тогда число k операций последовательного деления в алгоритме Евклида, необходимых для отыскания значения НОД (a,b), удовлетворяет неравенству

.

При операции умножения действительных чисел нетрудно вычислить мультипликативную обратную величину a^–1 для ненулевого числа a:

a^–1 =1/a или a ∙ a^–1 =1.

Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку 4 =1.

При операции умножения по модулю n в кольце Z/n={0,1,2,..,(n –1)} вычисление обратной величины является более сложной задачей. Например, решение сравнения
4∙x º1 (mod 7) эквивалентно нахождению таких значений x и k, что 4∙x º 7∙k +1, где x и k – целые числа.

Общая формулировка этой задачи – нахождение такого целого числа x, что

a∙x (mod n) =1, или a^–1 º x (mod n)

Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку 5∙3=15 º 1 (mod 14). С другой стороны, число 2 не имеет обратной величины по модулю 14. Вообще сравнение a^–1 º x (mod n) имеет единственное решение, тогда и только тогда когда a и n – взаимно простые числа.

В этом случае говорят, что элемент a обратим и его обратный элемент a^–1 равен x. Часто элемент a^–1 обозначают через . Надо всегда понимать, что это целый положительный вычет по модулю n.

Сформулируем основные способы нахождения обратных величин. Пусть aÎ{0,1,2,…,n–1}. Если НОД (a,n) =1, то a∙i (mod n) при i {0,1,2,…,n–1} является перестановкой множества {0,1,2,…,n–1}. Например, если a = 3 и n = 7 (НОД (3,7) =1), то 3∙i (mod 7) при последовательных значенияхi равных 0, 1, 2, …, 6 является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества чисел 0, 1, 2, …, 6. Это становится неверным, когда НОД (a, n) ¹ 1. Например, если a = 2 и n = 6, то 2∙i (mod 6) принимает значения 0, 2, 4, 0, 2, 4 при значениях iравных 0, 1, 2, …, 5. Если НОД (a,n) =1, то для a всегда существует обратное число a^–1, 0 < a^–1 < n, такое, что a∙a^–1 º1 (mod n).

Как уже отмечалось, набор целых чисел от 0 до n –1 называют полным набором вычетов по модулю n. Это означает, что для любого целого числа a (a>0) его вычет r = a (mod n) – это некоторое целое число в интервале от 0 до n–1.

Выделим из полного набора вычетов подмножество G вычетов, взаимно простых с n. Такое подмножество называют приведенным набором вычетов, или совместно с операцией умножения по модулю n это множество называют мультипликативной группой G кольца вычетов Z/n. Дело в том, что произведение по модулю n таких вычетов является элементом того же множества G. Например, пусть модуль n=11 – простое число. Полный набор вычетов по модулю 11 есть множество {0, 1, 2, …, 10}. При формировании приведенного набора вычетов из них удаляется только один элемент – 0. Приведенный набор вычетов по модулю 11 имеет 11 – 1 = 10 элементов, G={1, 2, …, 10}. Вообще приведенный набор вычетов по модулю простого числа n имеет n –1 элементов.

Пусть модуль n =10. Полный набор вычетов по модулю n =10 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10, то есть обратимы. Поэтому приведенный набор вычетов по модулю 10 равен G={1, 3, 7, 9}. При формировании этого приведенного набора были исключены элементы:

0 (1 элемент),

кратные 2 (4 элемента),

кратные 5 (1 элемент),

т.е. всего шесть элементов. Вычитая их из 10, получаем 10 – 1 – 4 – 1 = 4, т.е. четыре элемента в приведенном наборе (в мультипликативной группе кольца вычетов Z/10).

Для произведения простых чисел p∙q=n приведенный набор вычетов имеет (p –1)
(q –1) элементов. При n=p∙q=2∙5=10 число элементов в приведенном наборе (p – 1)(q – 1) = = (2 – 1) (5 –1) = 4. Например, приведенный набор вычетов по модулю 27=3³ имеет 18 элементов:

{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}.

Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов). Для модуля в виде простой степени n^r приведенный набор вычетов имеет n^r–1 (n –1) элементов. При n = 3, r = 3 получаем 3^3–1 (3 –1) = 3² ∙ 2 =18.

Функция Эйлера j(n) характеризует число элементов в приведенном наборе вычетов, ее значение совпадает с числом элементов |G| мультипликативной группы вычетов.

Модуль n	Функция j(n)
n – простое n2 … nr	n –1 n (n –1) … nr–1 (n – 1)
n= p∙q (p, q – простые) … n= (pi – простые)	(p – 1)(q – 1) … a

Иначе говоря, значение функция j(n) – это количество положительных целых, меньших n, которые взаимно просты с n.

Любой элемент a из группы G порождает подгруппу H =<a>={a,a²,a³,…,a^m}

Относительно умножения по модулю n порядок группы =<a>={a,a²,a³,…,a^m} (число ее элементов), которой совпадает с порядком элемента a – наименьшим натуральным числом m, при котором a^m º1 (mod n). Для g из G и H={h₁,h₂,.., h_m} положим gH={gh₁,gh₂,…gh_m}. Легко видеть, что |H|=|gH| и при g не принадлежащим H их пересечение пусто. Любая группа имеет разложение по левым (правым) смежным классам по своей подгруппе, G=e (G= ), e – нейтральный элемент (в нашем случае 1). Классы – подмножества (попарно не пересекаются и в объединении дают G). Из сказанного следует, что k|H|=|G| (теорема Лагранжа) и так как |H| в нашем случае совпадает с порядком элемента a, |H|= m, то m делит |G|=j(n). По этой причине а^j(n) =а^cm для некоторого с и а^j(n) =а^cm= º(1)^с(mod n) для любого элемента а из G. Таким образом, справедливы теоремы:

· малая теорема Ферма: если n– простое и НОД (a,n)=1, то a^n–1 º1 (mod n);

· теорема Эйлера: если НОД (a,n) =1, то a^j(n) º1 (mod n).

Основные способы нахождения обратных величин a^–1 º 1 (mod n).

1. Проверить поочередно значения 1, 2,..., n–1, пока не будет найден a^–1 º1 (mod n), такой, что a∙a^–1 (mod n) º 1.

2. Если известна функция Эйлера j(n), то можно вычислить a^–1 (mod n) º a^j(n)–1 (mod n), используя алгоритм быстрого возведения в степень.

3. Если функция Эйлера j(n) не известна, можно использовать расширенный алгоритм Евклида.

Проиллюстрируем эти способы на числовых примерах.

1. Поочередная проверка значений 1, 2,..., n – 1, пока не будет найден x = a^–1 (mod n), такой что a∙x º 1 (mod n).

Пусть n = 7, a = 5. Требуется найти x = a^–1 (mod n).

a∙ x º 1 (mod n) или 5∙x º 1 (mod 7).

Получаем x = 5^–1 (mod 7) = 3. Результаты проверки сведены в таблицу.

x	5 * x	5 * x (mod 7)
3		1

2. Нахождение a^–1 (mod n), если известна функция Эйлера j(n).

Пусть n=7, a=5. Найти x=a^–1 (mod n)=5^–1 (mod 7). Модуль n=7 – простое число.
Поэтому функция Эйлера j(n)=j(7)=n–1=6. Обратная величина от 5 по mod 7

a^–1 (mod n) = a^j(n)–1 (mod n) =

= 5^6–1 mod 7 = 5⁵ mod 7 = (5² mod 7)(5³ mod 7) mod 7 =

= (25 mod 7)(125 mod 7) mod 7 = (4 * 6) mod 7 = 24 mod 7 = 3.

Итак, x = 5^–1 (mod 7) = 3.

3. Нахождение обратной величины a^–1 (mod n) с помощью расширенного алгоритма Евклида.

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

Форма1. В этой форме во время вычисления НОД(a,b) попутно вычисляют такие целые числа u₁ и u₂, что

a∙u₁ + b∙u₂ = НОД (a,b).

Это обобщение (расширение) алгоритма Евклида удобно описать, используя векторные обозначения. При заданных неотрицательных целых числах a и b этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что

a∙u₁ + b∙u₂ = u₃ = НОД (a, b).

В процессе вычисления используются вспомогательные векторы (v₁, v₂, v₃), (t₁, t₂, t₃). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

a∙t₁ + b∙t₂ = t₃, a∙u₁ + b∙u₂ = u₃, a∙v₁ + b∙v₂ = v₃.

Для вычисления обратной величины a^–1 (mod n) используется частный режим работы расширенного алгоритма Евклида, при котором b = n, НОД (a,n) = 1, и этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что

u₃ =1, a∙u₁ + n∙u₂ = НОД (a,n) =1,

(a∙u₁ + n∙u₂) mod n º a∙u₁ (mod n) º 1,

a^–1 (mod n) º u₁ (mod n).

Шаги алгоритма:

1. Начальная установка.

Установить (u₁, u₂, u₃): = (0, 1, n),

(v₁, v₂, v₃): = (1, 0, a).

2. u₃ =1?. Если u₃ =1, то алгоритм заканчивается.

3. Разделить, вычесть.

Установить q: = [u₃/v₃].

Затем установить

(t₁, t₂, t₃): = (u₁, u₂, u₃) – (v₁, v₂, v₃)∙q,

(u₁, u₂, u₃): = (v₁, v₂, v₃),

(v₁, v₂, v₃): = (t₁, t₂, t₃).

Возвратиться к шагу 2.

Пусть з аданы модуль n = 23 и число a = 5. Найти обратное число a^–1 (mod 23), т.е. x = 5^–1 (mod 23).

Используя расширенный алгоритм Евклида, выполним вычисления, записывая результаты отдельных шагов в следующей таблице.

q	u1	u2	u3	v1	v2	v3
– –	–4 –9	–1	n = 23	–4 –9	–1	a = 5

При u₃ =1, u₁ = –9, u₂ = 2

(a∙u₁ + n∙u₂ ) mod n = (5∙(– 9) + 23∙2) mod 23 = 5∙(– 9) mod 23 º 1,

a^–1 (mod n) = 5^–1 (mod 23) = (– 9) mod 23 = (– 9 + 23) mod 23 = 14.

Итак, x = 5^–1 (mod 23) º 14 (mod 23) = 14.

Форма 2. Пусть НОД(а,n)=1, a>0, n>0. Рассматривается задача поиска целочисленного решения (x,y) уравнения a∙x-n∙y=1. Для решения задачи используют сначала алгоритм Евклида:

a = n ∙q₀ + r₁

n = r₁ ∙ q₁ + r₂

r₁ = r₂ ∙ q₂ + r₃

r₂ = r₃ ∙ q₃ + r₄

…………………

r_k–2 = r_k–1 ∙ q_k-1 + r_k

r_k–1 = r_k ∙ q_k +0

Находят последовательность q₀, q₁, q₂,…,q_k. Затем рекуррентно строят P₀,Р₁,Р₂,…,Р_k и Q₀,Q₁,Q₂,…,Q_k. Полагают

P_-2=0, P_-1=1 и P_j=q_jP_j-1+ P_j-2 для j 0,

Q_-2=1, Q_-1=0 и Q_j=q_jQ_j-1+Q_j-2 для j 0.

Искомые значения x, y находятся по формулам

.

Обратный элемент а^-1= (modn) для числа а есть решение уравнения

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

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

В криптосистеме RSA открытый ключ К_о, секретный ключ k_с, сообщение М и криптограмма С принадлежат кольцу целых чисел Z/N по модулю N

Z/N = {0, 1, 2,..., N–1},

где N= P∙Q, P и Q – случайные большие простые числа. Открытый ключ К_о выбирают случайным образом так, чтобы выполнялись условия:

1< К_о £ j (N),

НОД (К_о, j (N)) =1,

j (N)=(P –1) (Q –1),

где j (N) – функция Эйлера – количество положительных целых чисел в интервале от 1 до N взаимно простых с N.

В силу НОД (К_о, j(N)) =1 однозначно, используя расширенный алгоритм Евклида, вычисляется секретный ключ k_с, такой, что

k_с К_о º 1 (mod j(N)).

Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти j (N). Открытый ключ К_о используют для шифрования данных, а секретный ключ k_с – для расшифрования. Криптограмма С определяется через пару (открытый ключ К_о, сообщение М) C = (mod N). В качестве алгоритма быстрого вычисления значения C используют ряд последовательных возведений в квадрат целого M и умножений на M с приведением по модулю N.

Обращение функции C= (mod N), то есть определение значения M по известным значениям C, К_в и N, практически не осуществимо при N» 2 ⁵¹². Однако обратную задачу, т.е. задачу расшифрования криптограммы С, можно решить, используя пару (секретный ключ k_с, криптограмма С) по следующей формуле расшифрования: М = (mod N).

Проведем подробное обоснование справедливости этой формулы. Процесс расшифрования можно записать так:

= M (mod N).

Величина j (N) играет важную роль в теореме Эйлера, которая утверждает, что если НОД(x, N)=1, то x^j(N) º 1 (mod N), или в несколько более общей форме

x^n×j(N)+1 º x (mod N).

Но как раз из k_с∙К_о º 1 (mod j(N)) следует k_с∙К_о = n∙j (N)+1 при некотором n. Поэтому для (М, N)=1 вытекает

= М ^n×j(N)+1= ºM (mod N).

При (М, N)≠1 следует воспользоваться следующим утверждением: если P и Q – большие простые числа, К₀∙k_c(modj(N)) = 1, то для любого х, 0£ x<N, N=P∙Q:

(х ) (modN) = x.

ДОКАЗАТЕЛЬСТВО. Пусть НОД(х,N) =1. Тогда

(х ) = х = x .

Поэтому по теореме Эйлера

(х ) (modN) = (х(x (modN)))(modN)= (x×1)(modN) = x.

Если НОД(х,N) ¹ 1, то или х=0(modN), или НОД(х,N) = P, или НОД(х,N) =Q. Если
х =0(modN), то х =0(modN). Пусть НОД(х,N)=P. Тогда х=х P, где (х , N) =1.

х = x = Px P x º y(modP∙Q).

Так как (х , N) =1, то x =1 (modN).

Если x P x P=y(mod(P∙Q)), то x P x P=PQc+y, следовательно, y=Py . Тогда x P x º y (modQ). Следовательно,

x ((Pх ) ) º y (modQ).

По теореме Ферма z º 1 (modQ). Поэтому x º y (modQ) и

x= x P(mod(PQ)) = y (modN) º х (modN),

что и требовалось доказать.

Открытый и шифрованный тексты эффективно вычисляются, если известны К_о и k_c при помощи алгоритма быстрого возведения в степень. Если искать секретный ключ k_c по известному открытому ключу К_о, то надо знать j(N).

Таким образом, получатель В, который создает криптосистему, защищает два параметра: 1) секретный ключ k_в и 2) пару чисел (P,Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ К_в.

Противнику известны лишь значения К_в и N. Если бы он смог разложить число N на множители P и Q, то он узнал бы «потайной ход» – тройку чисел {P,Q,К_в}, вычислил значение функции Эйлера j (N)=(P –1) (Q –1)

и определил значение секретного ключа k_в.

Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных P и Q составляют не менее 100 десятичных знаков). Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете.

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

1. Пользователь В выбирает два произвольных больших простых числа P и Q.

2. Пользователь В вычисляет значение модуля N = P∙Q.

3. Пользователь В вычисляет функцию Эйлера j(N) = (P –1) (Q –1)

и выбирает случайным образом значение открытого ключа К_o с учетом выполнения условий: 1< К_o £ j(N), НОД (К_o, j(N)) =1.

4. Пользователь В вычисляет значение секретного ключа k_c, используя расширенный алгоритм Евклида при решении сравнения k_с º К_о^–1 (mod j(N)).

5. Пользователь В пересылает пользователю А пару чисел (N, К_o) по незащищенному каналу.

Если пользователь А хочет передать пользователю В сообщение М, он выполняет следующие шаги.

6. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа М_i {0, 1, 2,..., N –1}.

7. Пользователь А шифрует текст, представленный в виде последовательности чисел М_i по формуле C_i= (mod N) и отправляет криптограмму С₁, С₂, С₃,..., C_i,... пользователю В.

8. Пользователь В расшифровывает принятую криптограмму С₁, С₂, С₃,..., C_i,...,

используя секретный ключ k_c, по формуле М_i = (mod N).

В результате будет получена последовательность чисел М_i, которые представляют собой исходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей К_o и k_c.