桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成は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個以上の暗号文を手に入れたなら各々の公開鍵の法に関して中国の剰余定理を用いることで、通常の冪根によって平文を復元できるからである。このため、現在規格化されている暗号への応用においては、パディングとして毎回乱数を生成して挿入するなどの対策がされている。
(stub)
RSA暗号の安全性が素因数が不明な法nでの冪根を求めるのが難しい事実に基づいていることから、その最大の攻撃が素因数分解であることは明白である。
しかし平文によっては、それ以外の攻撃方法でも暗号文から平文を入手することが可能である。
これは公開鍵暗号全般に言えることであるが、確定的暗号であれば、例えば平文が「はい」か「いいえ」のどちらかしか有り得ないなら、それぞれを暗号化したものと暗号文とを比較すれば平文を知ることができる。
実際の暗号への応用においてはフォーマットとしてmの一部に毎回生成する乱数を挿入することでこの攻撃を回避している。
もしも平文mが、nのe乗根よりも小さかったら、暗号文c = memodn = meとなるから、通常の冪根演算によってcのe乗根を計算するだけで平文mが復元できてしまう。
実際の暗号への応用においてはフォーマットの一部として、mの比較的高位のビットに1を挿入することでこの攻撃を回避している。
法nにおけるe乗根が計算できれば、暗号文を復号できる。 当然これは（法nの素因数がわからない限り）非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。
しかし、まったく同一の平文を、異なる法において同一のeを用いて暗号化した暗号文をe個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これが同報通信の誤用である。
ここから中国の剰余定理によって上記式を満たす