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