Описание алгоритма

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

С = М^е (mod n)M = C^d (mod n) = (M^e)^d (mod n) = M^ed (mod n)

Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, получатель знает значение d. Таким образом, открытый ключ есть KU = {e, n} и закрытый ключ есть KR = {d, n}. При этом должны выполняться следующие условия:

1. Возможность найти значения е, d и n такие, что M^ed = M mod n для всех М < n.

2. Относительная легкость вычисления М^е и С^d для всех значений М < n.

3. Невозможность определить d, зная е и n.

Сначала рассмотрим первое условие. Нам необходимо выполнение равенства:

M^ed = М (mod n)

Рассмотрим некоторые математические понятия, свойства и теоремы, которые позволят нам определить e, d и n.

1. Если , то , если а и n взаимнопростые, т.е gcd (a, n) = 1.

2. Обозначим Z_p - все числа, взаимнопростые с p и меньшие p. Если p - простое, то Z_p - это все остатки. Обозначим w^-1 такое число, что .

Тогда

Доказательство этого следует из того, что т.к. w и p взаимнопростые, то при умножении всех элементов Z_p на wостатками будут все элементы Z_p, возможно, переставленные. Таким образом, хотя бы один остаток будет равен 1.

3. Определим функцию Эйлера следующим образом: - число положительных чисел, меньших n и взаимнопростых сn. Если p - простое, то .

Если p и q - простые, то .

В этом случае Z_p _x _q ={0, 1, ј, (p x q - 1)}.

Перечислим остатки, которые не являются взаимнопростыми с p x q:

{p, 2 x p, ј, (q-1) x p}{q, 2 x q, ј, (p-1) x q}0

Таким образом .

4. Теорема Ферма.

, если n - простое.

Если все элементы Z_n умножить на а по модулю n, то в результате получим все элементы Z_n, быть может, в другом порядке. Рассмотрим следующие числа:

{a mod n, 2 x a mod n, ј, (n-1) x a mod n} являются числами {1, 2, ј, (n-1)}, быть может, в некотором другом порядке. Теперь перемножим по модулю n числа из этих двух множеств.

n и (n-1)! являются взаимнопростыми, если n - простое, следовательно, .

5. Теорема Эйлера.

для всех взаимнопростых a и n.

Это верно, если n - простое, т.к. в этом случае . Рассмотрим множество . Теперь умножим по модулю n каждый элемент этого множества на a. Получим множество. Это множество является перестановкой множества R по следующим причинам.

Так как а является взаимнопростым с n и x_i являются взаимнопростыми с n, то a x x_i также являются взаимнопростыми с n. Таким образом, S - это множество целых, меньших n и взаимнопростых с n.

В S нет дублей, т.к. если a x x_i mod n = a x x_j mod n => x_i = x_j.

Следовательно, перемножив элементы множеств S и R, получим:

Теперь рассмотрим сам алгоритм RSA. Пусть p и q - простые.

n = p x q.

Надо доказать, что

Если gcd (M, n) = 1, то соотношение выполняется. Теперь предположим, что , т.е. . Пусть , т.е. M = c x p => gcd (M, q) = 1, так как в противном случаеM = c x p и M = l x q, но по условию M < p x q.

Следовательно,

По определению модуля это означает, что . Умножим обе части равенства на M = c x p. Получим

Или

Таким образом, следует выбрать e и d такие, что

Или

e и d являются взаимнообратными по умножению по модулю . Заметим, что в соответствии с правилами модульной арифметики, это верно только в том случае, если d (и следовательно, е ) являются взаимнопростыми с . Таким образом, .

Теперь рассмотрим все элементы алгоритма RSA.

p, q - два простых целых числа	- открыто, вычисляемо.
n = p x q	- закрыто, вычисляемо.
	- открыто, выбираемо.

	- закрыты, выбираемы.

Закрытый ключ состоит из {d, n}, открытый ключ состоит из {e, n}. Предположим, что пользователь А опубликовал свойоткрытый ключ, и что пользователь В хочет послать пользователю А сообщение М. Тогда В вычисляет С = М^е (mod n) и передает С. При получении этого зашифрованного текста пользователь А дешифрует вычислением М = С ^d (mod n).

Суммируем алгоритм RSA:

Создание ключей

Выбрать простые р и q

Вычислить n = p x q

Выбрать