1977年に発明され、発明者であるロナルド・リベスト(Ron Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Len Adleman) の頭文字をつなげてこのように呼ばれる。 当時、デフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。 発明者3氏は、この功績によって2002年のチューリング賞を受賞した。
RSA暗号は次のような方式である： 鍵ペア（公開鍵と秘密鍵）を作成して公開鍵を公開する。それには、適当な正整数 e（通常は小さな数。65537が良く使われる）を選択し、また大きな桁数の素数2個{p,q}を生成し、それらを暗号文の復号に使用する鍵（秘密鍵）に使用する。次に、生成した2つの素数の積 n を求めて、{e, n}を平文の暗号化に使用する鍵（公開鍵）として公開する。
暗号化：平文mから暗号文cを作成する：c = me(mod n)
復号：暗号文cから元の平文mを得る：m = c1 / e(mod (p − 1)(q − 1))(mod pq)
ここで、暗号化（e乗）は{e,n}があれば容易に計算できるのに対して、復号は「e乗根を求めるにはnの素因数がないと難しい（桁数が大きい合成数の素因数分解も難しい）」と考えられている。従って秘密鍵を用いずに暗号文から平文を得ることは難しい、と信じられている。これがRSA暗号の安全性の根拠である。
歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者はジェイムズ・エリスである。彼らはイギリス最高機密機関、英国政府通信本部(GCHQ)の職員であり、その独創的な先見の明は英国政府の隠蔽工作により闇に消えたのである。以下はその概要である。
エリスは1969年にこの理論を発見しているが、数学者ではなかったので具体的方法を模索することができなかった。それから幾人ものGCHQの優秀な数学者が挑戦したが、具体的方式を提示する事はできなかった。過ぎること数年の1973年、ある突拍子も無い暗号のアイデアとしてエリスの「一方向関数(非対称性鍵の概念)・公開鍵」を用いた暗号論の話を聞かされ、その場の思いつきでモジュラー算術と素因数を用いた具体的な方式を考案したのは、若き天才数学者クリフォード・コックスである(コックスは上記のリベストの計算式と同じものを発見した)。が、しかし彼らの発見と発明は秘密主義の名の下に世にひろく知られることはなかった。
RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許（4,405,829号）を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。
鍵生成、暗号化、復号の3つのアルゴリズムで定義される。
k をセキュリティパラメタとする。
p, q を k/2 ビットの素数とし、n = pq とする。e を φ(n) 未満の正の整数で、φ(n) と互いに素な数とし、d を、φ(n) を法としたe の逆数（ de ≡ 1 ( mod φ(n) ) ）とする。 ただしここで φ(n) は n のオイラー関数で、この場合は (p - 1)(q - 1) に等しい。d は、e, φ(n) が既知のときには拡張されたユークリッドの互除法を使えば容易に求まる（ de を φ(n) で割った整数商を x とした場合、de + (-x)φ(n) = 1が成り立ち、かつ e の取り方から gcd(e,φ(n)) = 1 であるのでこれを解けば良い）。p, q, d を秘密鍵とし、n, e を公開鍵とする。
以下では、0 以上 n 未満の整数の集合を で表すことにする。 平文空間および暗号文空間は 。
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暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。