Алгоритм rsa

Диффи и Хеллман определили новый подход к шифрованию, что вызвало к жизни разработку алгоритмов шифрования, удовлетворяющих требованиям систем с открытым ключом. Одним из первых результатов был алгоритм, разработанный в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.

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

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n.

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

Алгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа 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. Если (а · b) (a · c) mod n, то b c mod n, если а и n взаимнопростые, т.е gcd (a, n) = 1.

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

Тогда w Z_p z: w · z 1 mod p

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

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

Если p и q - простые, то Φ(p · q) = (p-1) · (q-1).

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

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

{p, 2 · p, ј, (q-1) · p}

{q, 2 · q, ј, (p-1) · q}

0

Таким образом Φ(p · q) = p · q - [(q-1) + (p-1) + 1] = p · q - (p+q) + 1 = (p-1) · (q-1).

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

a^n-1 1 mod n, если n - простое.

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

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

[(a mod n) · (2a mod n) · ... · (n-1)a mod n]

mod n (n-1)! mod n(n-1)! a^n-1 (n-1)! mod n

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

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

a^Φ(n) 1 mod n для всех взаимнопростых a и n.

Это верно, если n - простое, т.к. в этом случае Φ(n) = n-1. Рассмотрим множество R = {x₁, x₂, ј, xΦ(n)}. Теперь умножим по модулю n каждый элемент этого множества на a. Получим множество S = {a · x₁ mod n, a · x₂ mod n, ј, a · xΦ(n) mod n}. Это множество является перестановкой множества R по следующим причинам.

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

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

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

Φ(n) Φ(n)

∏ (a · x_i mod n) ∏ x_i mod n

i=1 i=1

Φ(n) Φ(n)

( ∏ a · x_i ∏ x_i ) mod n

i=1 i=1

Φ(n) Φ(n)

( a^Φ(n) · ∏ x_i ∏ x_i ) mod n

i=1 i=1

( a^Φ(n) 1) mod n

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

n = p · q.

Надо доказать, что M < n: M^Φ(n) = M^{(p-1) · (q-1)} 1 mod n

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

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

M^Φ(q) 1 mod q

(M^Φ(q))(p) 1 mod q

M^Φ(n) 1 mod q

По определению модуля это означает, что M^Φ(n) = 1 + k · q. Умножим обе части равенства на M = c · p. Получим

M^Φ(n)+1 = c · p + k · q · c · p.

M^Φ(n) 1 mod n

Или

M^Φ(n)+1 M mod n

Таким образом, следует выбрать e и d такие, что е · d 1 mod (n)

Или e d-1 mod Φ(n)

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

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

p, q - два простых целых числа	- открыто, вычисляемо.
n = p · q	- закрыто, вычисляемо.
d, gcd (Φ(n), d) = 1;	- открыто, выбираемо.
1 < d < Φ(n)
е d-1 mod Φ(n)	- закрыты, выбираемы.

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

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

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

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

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

Выбрать d     gcd (Φ(n), d) = 1; 1 < d < Φ(n)

Вычислить е     е = d^-1 mod Φ(n)

Открытый ключ KU = {e, n}

Закрытый ключ KR = {d, n}

Шифрование

Незашифрованный текст: М < n

Зашифрованный текст: С = М ^е (mod n)

Дешифрование

Зашифрованный текст: С

Незашифрованный текст: М = С^d (mod n)

Рассмотрим конкретный пример:

Выбрать два простых числа: р = 7, q = 17.

Вычислить n = p · q = 7 · 17 = 119.

Вычислить Φ(n) = (p - 1) · (q - 1) = 96.

Выбрать е так, чтобы е было взаимнопростым с Φ(n) = 96 и меньше, чем Φ(n): е = 5.

Определить d так, чтобы d · e 1 mod 96 и d < 96.

d = 77, так как 77 · 5 = 385 = 4 · 96 + 1.

Результирующие ключи открытый KU = {5, 119} и закрытый KR = {77, 119}.

Например, требуется зашифровать сообщение М = 19.

19⁵ = 66 (mod 119); С = 66.

Для дешифрования вычисляется 66⁷⁷ (mod 119) = 19.