a を平文空間 の元とする。b = ae mod n （n を法とする剰余）を計算し、b を出力する。
b を暗号文とする。a’ = bd mod n を計算し、a’ を出力する。ここで a = a’ となり復号できる。
以下に証明を示す。ここで a’ は、ae にさらに d を乗したものの n を法とする余剰で、de ≡ 1 ( mod φ(n))であるから、
a’ ≡ a(de) (mod n) ≡ a( x * φ(n) + 1) (mod n)
ここでオイラーの定理により、n と互いに素な整数 a については aφ(n) ≡ 1 (mod n) であるため、
a’ ≡ 1x * a1 ≡ a (mod n)
となる。GCD(n,a) = p である整数 a については, a=p*i=aq+q*j, 0<i<q, 0<=j<p として
a’ ≡ 0 (mod p)
a’ ≡ a ≡ aq (mod q)
となるから中国の剰余定理により、p*xp=1+q*xq として
a’ ≡ 0*q*xq + aq*p*xp ≡ (p*i-q*j)*p*xp ≡ p*i*p*xp ≡ p*i*(1+q*xq) ≡ p*i + p*i*q*xq ≡ p*i ≡ a (mod n)
となる（GCD(n,a) = q である整数についても同様）。ここで、 a’ も a も n を法とした余剰なので、
a’ = a
が成り立ち b は d と n を用いて a に復号できることが分かる。
n を法とするべき剰余の計算
k=1024の場合、n は1024ビットサイズという大きな数となり、d もほぼ n と同サイズの数となる。 a = bd mod n を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算（1024bit × 1024bit）を、1500回程繰り返すことで実現できる。 これには相当の計算時間を要するため、中国の剰余定理を用いて、
ap = bd mod φ(p) mod p, aq = bd mod φ(q) mod q, a’ = ap (1/q mod p) q + aq (1/p mod q) p
として求めることがある。
桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller-Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数（probable prime）という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる。
(なお、拡張リーマン予想が正しければ、Miller-Rabinテストは素数かどうかを正しく判定する、という事実が知られている)。
2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間で行うAKS素数判定法を発表したが、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。
RSA暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。
素因数分解を解けるオラクルを用いれば、nからpおよびqが計算でき鍵生成と同様にして、秘密鍵dを知ることが出来る。即ち、RSA暗号が解読出来る。従って、RSA仮定が証明できれば素因数問題の困難性が示せる。しかし、逆が成立するかどうかはよく分かっていない。ある条件下では否定的な結果もでている。
RSA暗号が選択平文攻撃に対して完全解読できない、ということとRSA仮定とは同値である。
RSA問題を解く方法として、現在知られている有力な方法は、素因数分解問題を解くことに使える方法だけである。 素因数分解問題を解く方法として、楕円曲線法や数体篩法などのアルゴリズムが知られているが、これらの方法はどれも準指数時間アルゴリズムであり、多項式時間で素因数分解問題を解く方法は知られていない。
暗号理論の世界では、多項式時間で解読することができない暗号方式を安全であると定義することがある（計算量的安全性）。 この意味で、RSA暗号の安全性について、現在知られている範囲では、安全であると期待されていて、その反証がない、と言える。
RSA問題や素因数分解問題はNP問題であるので、これらの問題が(deterministicな)多項式時間では解けないことが証明できれば、P≠NP予想が肯定的に解決することになる。
2004年現在、インターネットで公募した数多くのPCを用いると512ビット程度の数なら素因数分解できる。 したがって、現在では、RSA暗号に使用する法 n を1024-4096ビット（10進数で300-1000桁程度）にすることが推奨されている。
しかしShamirは、RSA問題を解くための専用装置(TWIRL)を作成すれば、1024ビットの n に関するRSA問題ですら解くことができると主張している。
RSA社は「RSA Challenge 解読コンテスト」を行って、現在のコンピュータを使うとどの程度のビット数の整数なら素因数分解問題が解けるのかを調べていた。
1991.04.01 RSA-100 (330ビット)
1992.04.14 RSA-110 (364ビット)
1993.06.09 RSA-120 (397ビット)
1994.04 RSA-129 (426ビット)
1996.04.10 RSA-130 (430ビット)
1999.02.02 RSA-140 (463ビット)
2004 RSA-150 (496ビット)
1999.08.22 RSA-155 (512ビット)
2003.04.01 RSA-160 (530ビット)
yet RSA-170 (563ビット)
2003.12.03 RSA-576 (576ビット,10進174桁）
yet RSA-180 (596ビット)
yet RSA-190 (629ビット)
2005.11.02 RSA-640 (640ビット)
2005.05.09 RSA-200 (663ビット,10進200桁)
以下は未踏
RSA-210
RSA-704
RSA-768
RSA-896
RSA-1024
RSA-1536
RSA-2048
RSA暗号は選択暗号文攻撃を行なえば完全解読できる。また、RSA暗号は選択平文攻撃に対してすらindistinguishableではない。よってRSA暗号は選択平文攻撃に対してnon-malleableでもsemantic secureでもない。
Strong Prime (stub)
特殊な(誤った)応用
共通の法n
ユーザー管理等の利便性や素数探索の労を避ける為、法であるnを共通として各々に個別のe,dを与えるのは誤りである。もしも法nとそれに対応するe,dの組を一つでも知ることができれば、法nの素因数分解が容易となり安全ではなくなるからである。
同報通信
まったく同一の平文を複数の送信先へ各々の公開鍵で暗号化して同報通信するには適していない。同じeを持つ公開鍵（3や65537が好んで用いられる）で暗号化されたe個以上の暗号文を手に入れたなら各々の公開鍵の法に関して中国の剰余定理を用いることで、通常の冪根によって平文を復元できるからである。