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個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これが同報通信の誤用である。
ここから中国の剰余定理によって上記式を満たす
を求めることができる。このときであり、またmはどの法nよりも小さいためであることから、c = me
このcのe乗根を求めることで平文mが求められる。
これはeとして特に3や65537が、2進数表示したときに1の個数が少ないために暗号化処理を高速化できるという理由から好んで用いられるために発生しうる問題である。実際の暗号への応用においてはフォーマットとして、mの一部に毎回生成する乱数を挿入することでこの攻撃を回避している。
RSA暗号の入力は、モジュラスをnとすると0〜（n-1）の範囲の整数である。n以上の値の平文を暗号化する際には、平文を分割して処理することになる。
この時に留意しなければならない点として、例えば、nが1024ビット（=128バイト）であるとき、平文を同じ1024ビット毎に分割処理するのでは十分ではないという点がある。これは、n, mが共に1024ビットであったとしても、n<mの場合には、結果として出力されるのは、m mod nに対応する暗号文であり、復号してもmは出力されないためである。
平文をビット単位（やバイト単位）で分割する際には、まず、nの下限を定めたうえで、平文の全ビットを1に（全バイトを0xFFに）してもnより小さくなるビット数（バイト数）で分割しなければならない。例えば、nの下限をn≧2^1023とした場合、平文は1023ビットごとに分割する。