Идея, положенная в основу метода, состоит в том, чтобы найти такую функцию y=Φ(x), для которой получение обратной функции x=f-1(y) было бы в общем случае очень сложной задачей (NP-полной задачей). Например, получить произведение двух чисел n=p×q просто, а разложить n на множители, если p и q достаточно большие простые числа, – NP-полная задача с вычислительной сложностью ~ n10. Однако если знать некую секретную информацию, то найти обратную функцию x=f-1(y) существенно проще. Такие функции также называют односторонними функциями с лазейкой или потайным ходом.
Применяемые в RSA прямая и обратная функции просты. Они базируются на применении теоремы Эйлера из теории чисел.
Прежде чем сформулировать теорему Эйлера, необходимо определить важную функцию Φ(n) из теории чисел, называемую функцией Эйлера. Это число взаимно простых (взаимно простыми называются целые числа, не имеющие общих делителей) с n целых чисел, меньших n. Например, Φ(7)=6. Очевидно, что, если p и q – простые числа и pq, то Φ(p)=p-1, и Φ(pq)=(p-1)×(q-1).