暗号化（ 乗）は公開鍵 があれば容易に計算でき、復号（ 乗）は秘密鍵 と公開鍵 があれば容易に計算できる。しかし、秘密鍵 を知らずに解読する（法 の下で 乗根を計算する）のは、「 の素因数を知らないと難しい（大きい合成数の素因数分解も難しい）」と考えられている。つまり、「秘密鍵を用いずに暗号文から平文を得ることは難しい」と信じられている。これがRSA暗号の安全性の根拠である。
暗号の用語については暗号#用語、暗号理論#用語を参照。
歴史.
暗号方式.
鍵生成.
ここで、 のとき を整数とすると であるから に の整数倍を加えたものも改めて とできるため、 として正整数 を選択できるとした。　
以下 を 以上 未満の整数の集合とする。
暗号化.
 とし を暗号化対象の平文とする。 を計算し、 を 平文 の暗号文とする。
復号.
 を計算する。すると となり は 平文 の暗号文 の復号文となる。
完全性の証明.
定義により以下が成立する。
これにより以下も成立する。
となる。
よって
よって
よって は で割り切れるから
となる。
以上何れにしても が成り立ち、平文 の 暗号文 は 秘密鍵 と公開鍵の一つ を用いて平文 に復号できることが分かる。
性能.
として求めることがある。
素数生成.
安全性.
RSA暗号と素因数分解問題の関係.
RSA暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。
素因数分解を解けるオラクルを用いれば、 から および が計算できるので、鍵生成と同様にして秘密鍵 を知ることができる。即ち、RSA暗号が解読できる。従って、RSA仮定が証明できれば素因数分解問題の困難性が示せる。しかし、逆が成立するかどうかはよく分かっていない。ある条件下では否定的な結果もでている。
RSA暗号が選択平文攻撃に対して完全解読できない、ということとRSA仮定とは同値である。
RSA問題を解く方法として、現在知られている有力な方法は、素因数分解問題を解くことに使える方法だけである。素因数分解問題を解く方法として、楕円曲線法や数体篩法などのアルゴリズムが知られているが、これらの方法はどれも準指数関数時間アルゴリズムであり、多項式時間で素因数分解問題を解く方法は知られていない。