Следствие

Если n = pq, (p и q - отличные друг от друга простые числа) и е простое относительно (n), то отображение Е_e,n: xx ^e (mod n) является взаимно однозначным на Z _n.

Очевиден и тот факт, что если е - простое относительно (n), то существует целое d, такое, что ed = 1 (mod (n)). (3)

На этих математических фактах и основан популярный алгоритм RSA.

Пусть n = pq, где p и q - различные простые числа. Если e и d удовлетворяют уравнениям (1), (2) и (3), то отображения Е_e,n и Е_d,n являются инверсиями на Z_n. Как Е_e,n, так и Е_d,n легко рассчитываются, когда известны e, d, p, q. Если известны e и n, но p и q неизвестны, то Е_e,n представляет собой одностороннюю функцию; нахождение Е_d,n по заданному n равносильно разложению n. Если p и q - достаточно большие простые числа, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA.

Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретные ключи, выполнив следующие шаги:

1) Выберем два очень больших простых числа p и q.

2) Определим n, как результат умножения p на q (n= p*q).

3) Выберем большое случайное число, которое назовем d. Это число должно быть взаимно простым с результатом умножения (p-1)*(q-1).

4) Определим такое число е, для которого является истинным следующее соотношение (e*d) mod ((p-1)*(q-1))=1.

5) Hазовем открытым ключом числа e и n, а секретным ключом - числа d и n.

Теперь, чтобы зашифровать данные по известному ключу {e,n}, необходимо сделать следующее:

— разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0,1,2..., n-1 (т.е. только до n-1).

— зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле C(i)=(M(i)^e)mod n.

Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо выполнить следующие вычисления:

M(i) = (C(i)^d) mod n.

В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Чтобы более наглядно представить алгоритм RSA, приведем следующий пример:

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

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

2) Определим n= 3*11=33.

3) Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).

4) Выберем число е по следующей формуле: (e*3) mod 20=1. Значит, е будет равно, например, 7: (e=7).

5) Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (не забывайте, что кончается на n-1). Буква А =1, В=2, С=3.

Теперь зашифруем сообщение, используя открытый ключ {7,33}

C1 = (3^7) mod 33 = 2187 mod 33 = 9;

C2 = (1^7) mod 33 = 1 mod 33 = 1;

C3 = (2^7) mod 33 = 128 mod 33 = 29;

Расшифруем эти данные, используя закрытый ключ {3,33}

M1=(9^3) mod 33 =729 mod 33 = 3(С);

M2=(1^3) mod 33 =1 mod 33 = 1(А);

M3=(29^3) mod 33 = 24389 mod 33 = 2(В). Все данные расшифрованы.

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