この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "RSA暗号" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2017年3月）

RSA一般
設計者ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマン
初版発行日1977
認証PKCS#1, ANSI X9.31, IEEE 1363
暗号詳細
鍵長1,024 to 4,096 bit typical
ラウンド数1
最良の暗号解読法
829 bit key (RSA-250)は解読済み

RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であると信じられていることを安全性の根拠とした公開鍵暗号の一つである。暗号[1]とデジタル署名を実現できる方式として最初に公開されたものである。
概要

RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる[2](p63)。前年（1976年）にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている[2][要ページ番号]。

RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許（4,405,829号）を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。

暗号の用語については暗号#用語、暗号理論#用語を参照。

なお、RSA暗号を最初に考案したのはGCHQに所属するジェイムズ・エリス（英語版）とクリフォード・コックス（英語版）であるという説がある。エリスは1969年に公開鍵暗号に相当する理論を考案したが、エリスは専門の数学者ではなく、GCHQの数学者たちも公開鍵暗号の具体的な方法を提示することはできなかった。1973年にコックスはエリスが考案した暗号の理論を聞かされ、わずか30分程度でリベストの計算式と同様の方法を考案した。しかし、エリスとコックスの業績は機密事項とされたため、1997年までは世間に知られることはなかった[2](p66)。また、当時はRSA暗号を使用するには高価なコンピュータが必要であり、公に知られている限り、実用に供されることは無かった。
暗号方式

鍵生成、暗号化、復号の3つのアルゴリズムで定義される。
鍵生成

p, q を異なる2つの素数とし n = pq とし λ(n) = (p ? 1)(q ? 1) とする。e を λ(n) と素な正整数とすると α ? e + β ? λ(n) = 1 となる2整数 α, β が存在する[3]。α として1つの正整数 d を選択してそのときの β を ?x とすると d ? e = x ? λ(n) + 1 となる。ここで d を秘密鍵とし、n と e を公開鍵とする。

ここで、α ? e + β ? λ(n) = 1 のとき i を整数とすると (α + i ? λ(n)) ? e + (β ? i ? e) ? λ(n) = 1 であるから α に λ(n) の整数倍を加えたものも改めて α とできるため、α として正整数 d を選択できるとした。　

以下 ?n を 0 以上 n 未満の整数の集合とする。
暗号化

a ∈ ?n とし a を暗号化対象の平文とする。b = ae mod n ∈ ?n を計算し、b を 平文 a の暗号文とする。
復号

a′ = bd mod n ∈ ?n を計算する。すると a′ = a となり a′ は 平文 a の暗号文 b の復号文となる。
完全性の証明

定義により以下が成立する。 a ′ ≡ a ( d ⋅ e ) ( mod n ) = a ( x ⋅ λ ( n ) + 1 ) = ( a λ ( n ) ) x ⋅ a {\displaystyle a'\equiv a^{(d\cdot e)}{\pmod {n}}=a^{(x\cdot \lambda (n)+1)}=(a^{\lambda (n)})^{x}\cdot a}

これにより以下も成立する。 a ′ ≡ ( a λ ( n ) ) x ⋅ a ( mod p ) a ′ ≡ ( a λ ( n ) ) x ⋅ a ( mod q ) {\displaystyle {\begin{aligned}a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {p}}\\a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {q}}\end{aligned}}}

a が n と互いに素な整数のときは a が2つの素数 p, q のそれぞれと互いに素であるから

フェルマーの小定理 により a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} かつ a q − 1 ≡ 1 ( mod q ) {\displaystyle a^{q-1}\equiv 1{\pmod {q}}} であり a λ ( n ) = ( a p − 1 ) q − 1 ≡ 1 ( q − 1 ) ( mod p ) = 1 a λ ( n ) = ( a q − 1 ) p − 1 ≡ 1 ( p − 1 ) ( mod q ) = 1 {\displaystyle {\begin{aligned}a^{\lambda (n)}=(a^{p-1})^{q-1}\equiv 1^{(q-1)}{\pmod {p}}=1\\a^{\lambda (n)}=(a^{q-1})^{p-1}\equiv 1^{(p-1)}{\pmod {q}}=1\end{aligned}}}

よって ( a λ ( n ) − 1 ) {\displaystyle (a^{\lambda (n)}-1)} は p, q で割り切れるから a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} となり a ′ ≡ ( a λ ( n ) ) x ⋅ a ( mod n ) ≡ 1 x ⋅ a ( mod n ) = a {\displaystyle a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {n}}\equiv 1^{x}\cdot a{\pmod {n}}=a}