Теорема 1. Малая теорема Ферма

Если р - простое число, то

x^{p -1} = 1 (mod p) (1)

для любого х, простого относительно p,

и

x^p = х (mod p) (2)

для любого х.

Определение. Функцией Эйлера φ(n) называется число положительных целых, меньших n и простых относительно n.

Теорема 2. Если n = pq, (p и q - отличные друг от друга простые числа), то

φ(n)=(p -1)(q -1).

Теорема 3. Если n = pq, (p и q - отличные друг от друга простые числа), то для любого x имеет место равенство:

x^(p-1)(q-1) mod n = 1.

Следствие. Если n = pq, (p и q - отличные друг от друга простые числа) и е простое относительно j(n), то отображение

Е_e,n: x ® x ^e (mod n)

является взаимно однозначным на Z _n.

Очевиден и тот факт, что если е - простое относительно j(n), то существует целое d, такое, что

ed = 1 (mod j(n)) (3)

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

Пусть n = pq, где p и q - различные простые числа. Если e и d удовлетворяют уравнению (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-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y):

x^{(-y)(p-1)(q-1)} mod n = 1^(-y) = 1.

Теперь умножим обе ее части на x:

x^{(-y)(p-1)(q-1)+1} mod n = 1 * x = x.

Вспомним, как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида e такое, что

e · d + (p-1)(q-1) · y = 1,

то есть

e · d = (-y)(p-1)(q-1) + 1.

А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e·d). Получаем

x^e*d mod n = x.

То есть для того чтобы прочесть сообщение c_i = m_i^e mod n достаточно возвести его в степень d по модулю n:

c_i^d mod n = m_i^e*d mod n = m_i.

По­сле шифрования, со­об­ще­ние не­воз­мож­но рас­крыть с по­мо­щью от­кры­то­го клю­ча. Даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i и возведением его в степень e или отысканием d путем разложения n на множители. Вла­де­лец же за­кры­то­го клю­ча без тру­да мо­жет рас­шиф­ро­вать при­ня­тое со­об­ще­ние.