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 = a^e mod n ∈ ℤ_n を計算し、b を 平文 a の暗号文とする。

a′ = b^d mod n ∈ ℤ_n を計算する。すると a′ = a となり a′ は 平文 a の暗号文 b の復号文となる。

定義により以下が成立する。

${\displaystyle a'\equiv a^{(d\cdot e)}{\pmod {n))=a^{(x\cdot \lambda (n)+1)}=(a^{\lambda (n)})^{x}\cdot a}$

これにより以下も成立する。

${\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 のそれぞれと互いに素であるから

フェルマーの小定理 により ${\displaystyle a^{p-1}\equiv 1{\pmod {p))}$ かつ ${\displaystyle a^{q-1}\equiv 1{\pmod {q))}$ であり

${\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))}$

よって ${\displaystyle (a^{\lambda (n)}-1)}$ は p, q で割り切れるから ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n))}$ となり

${\displaystyle a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {n))\equiv 1^{x}\cdot a{\pmod {n))=a}$

となるが、${\displaystyle a,a'\in \mathbb {Z} _{n))$ であるから

${\displaystyle a'=a}$

となる。

${\displaystyle \gcd(n,a)=p}$ であり、${\displaystyle a\in \mathbb {Z} _{n}-\{0\))$ のときは、a は q − 1 個の整数からなる集合 ${\displaystyle \{1\cdot p,2\cdot p,3\cdot p,\cdots ,(q-1)\cdot p\))$ の元であって、a が p で割り切れるから ${\displaystyle a\equiv 0{\pmod {p))}$ であり、a, q が素であるからフェルマーの小定理により ${\displaystyle a^{q-1}\equiv 1{\pmod {q))}$ であり

${\displaystyle a^{\lambda (n)}=(a^{q-1})^{p-1}\equiv 1^{(p-1)}{\pmod {q))=1}$

よって

${\displaystyle {\begin{aligned}a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {p))\equiv (a^{\lambda (n)})^{x}\cdot 0{\pmod {p))=0\\a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {q))\equiv 1^{x}\cdot a{\pmod {q))=a\end{aligned))}$

よって

${\displaystyle {\begin{aligned}a'\equiv 0{\pmod {p))\equiv a{\pmod {p))\\a'\equiv a{\pmod {q))\end{aligned))}$

よって a' − a は p, q で割り切れるから

${\displaystyle a'\equiv a{\pmod {n))}$

となるが、${\displaystyle a,a'\in \mathbb {Z} _{n))$ であるから

${\displaystyle a'=a}$

となる。

${\displaystyle \gcd(n,a)=q}$ であり ${\displaystyle a\in \mathbb {Z} _{n}-\{0\))$ のときについても同様に a' = a となる。

a = 0 のときは ${\displaystyle b\in \{z\in \mathbb {Z} _{n}\mid z\equiv 0^{e}{\pmod {n))\}=\{0\))$ であるから b = 0 であり、${\displaystyle a'\in \{z\in \mathbb {Z} _{n}\mid z\equiv 0^{d}{\pmod {n))\}=\{0\))$ であるから a' = 0 である。つまり a′ = a = 0 である。

以上何れにしても a' = a が成り立ち、平文 a の 暗号文 b は 秘密鍵 d と公開鍵の一つ n を用いて平文 a に復号できることが分かる。

記事参照

冪剰余

セキュリティパラメータが1024の場合、n は1024ビットという大きな桁数の数となり、d も n とほぼ同じ桁数の数となる。${\displaystyle a=b^{d}{\bmod {n))}$ を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算 (${\displaystyle 1024\mathrm {bit} \times 1024\mathrm {bit} }$) を、1500回程繰り返すことで実現できる。これには相当の計算時間を要するため、中国の剰余定理を用いて、

${\displaystyle {\begin{aligned}ap&=b^{d{\bmod {\lambda ))(p)}{\bmod {p))\\aq&=b^{d{\bmod {\lambda ))(q)}{\bmod {q))\\a'&=ap(q^{-1}{\bmod {p)))q+aq(p^{-1}{\bmod {q)))p\end{aligned))}$

として求めることがある。

桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller–Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数 (probable prime) という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる（なお、拡張リーマン予想が正しければ、Miller–Rabinテストは素数かどうかを正しく判定する、という事実が知られている^[要出典]）。

2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間で行うAKS素数判定法を発表した^[要出典]が、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。

RSA暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。

素因数分解を解けるオラクルを用いれば、n から p および q が計算できるので、鍵生成と同様にして秘密鍵 d を知ることができる。即ち、RSA暗号が解読できる。従って、RSA仮定が証明できれば素因数分解問題の困難性が示せる。しかし、逆が成立するかどうかはよく分かっていない。ある条件下では否定的な結果もでている。

RSA暗号が選択平文攻撃に対して完全解読できない、ということとRSA仮定とは同値である。

RSA問題を解く方法として、現在知られている有力な方法は、素因数分解問題を解くことに使える方法だけである。素因数分解問題を解く方法として、楕円曲線法や数体篩法などのアルゴリズムが知られているが、これらの方法はどれも準指数関数時間アルゴリズムであり、多項式時間で素因数分解問題を解く方法は知られていない。

暗号理論の世界では、多項式時間で解読することができない暗号方式を安全であると定義することがある（計算量的安全性）。この意味で、RSA暗号の安全性について、現在知られている範囲では安全であると期待されていて、その反証がないと言える。

RSA問題や素因数分解問題はNP問題であるので、これらの問題が（決定性のある）多項式時間では解けないことが証明できれば、P≠NP予想が肯定的に解決することになる。ただし、ハミルトン閉路問題など他のNP問題（NPかつNP困難なNP完全問題を含む）が多項式時間で解けることが証明されればP=NPとなってしまう。

2004年の時点では、インターネットで公募した数多くのPCを用いると512ビット程度の数なら素因数分解できるので、RSA暗号に使用する法 n は1024-4096ビット（10進数で300-1000桁程度）にすることが推奨されている。

しかしシャミアは、RSA問題を解くための専用装置 (TWIRL) を作成すれば、1024ビットの n に関するRSA問題ですら解くことができると主張している。また、実用的な量子コンピュータが登場した場合には、素因数分解の桁数増に対する計算時間の増加が緩やかなショアのアルゴリズム（英語版）と呼ばれる高速な量子コンピュータアルゴリズムが実行可能となるため、たとえ鍵のビット数を増やしてもRSA暗号の安全性が保証されなくなる可能性が指摘されている^[4]。

RSA社は「RSA Factoring Challenge」を1991年から2007年まで実施し、最新の計算機環境でどの程度のビット数の整数が素因数分解可能かを調べた。

• 1991年4月1日 RSA-100 (330ビット)
• 1992年4月14日 RSA-110 (364ビット)
• 1993年6月9日 RSA-120 (397ビット)
• 1994年4月26日 RSA-129 (426ビット)
• 1996年4月10日 RSA-130 (430ビット)
• 1999年2月2日 RSA-140 (463ビット)
• 2004年4月16日 RSA-150 (496ビット)
• 1999年8月22日 RSA-155 (512ビット)
• 2003年4月1日 RSA-160 (530ビット)
• 2009年12月29日 RSA-170 (563ビット)
• 2003年12月3日 RSA-576 (576ビット、10進174桁）
• 2010年5月8日 RSA-180 (596ビット)
• 2010年11月8日 RSA-190 (629ビット)
• 2005年11月2日 RSA-640 (640ビット)
• 2005年5月9日 RSA-200 (663ビット、10進200桁)
• 2013年9月26日 RSA-210 (696ビット、10進210桁)
• 2012年7月2日 RSA-704 (704ビット)
• 2016年5月13日 RSA-220 (729ビット）
• 2018年8月15日 RSA-230 (762ビット）
• 2020年2月17日 RSA-232 (768ビット）
• 2009年12月12日 RSA-768 (768ビット)
• 2019年12月2日 RSA-240 (795ビット）
• 2020年2月28日 RSA-250 (829ビット）

以下は未踏

• RSA-896
• RSA-1024
• RSA-1536
• RSA-2048

RSA暗号は選択暗号文攻撃を行なえば完全解読できる。また、RSA暗号は選択平文攻撃に対してすらindistinguishable（識別不能）ではない。よってRSA暗号は選択平文攻撃に対してnon-malleable（頑強性）でも semantic secure（強秘匿性）でもない。non-malleable と semantic secure の定義は公開鍵暗号に記されている。

共通の法 n

ユーザー管理等の利便性や素数探索の労を避けるため、法である n を共通として各々に個別の e と d を与えるのは誤りである。もしも法 n とそれに対応する e と d の組を一つでも知ることができれば、法 n の素因数分解が容易となり安全ではなくなるからである。

同報通信

全く同一の平文を複数の送信先へ各々の公開鍵で暗号化して同報通信するには適していない。同じ e を持つ公開鍵（ハミング重み HW = 2 である 3 や 65537 が好んで用いられる）で暗号化された e 個以上の暗号文を手に入れたなら各々の公開鍵の法に関して中国の剰余定理を用いることで、通常の冪根によって平文を復元できるからである。詳しくは下記の同一平文を参照のこと。

このため、現在規格化されている暗号への応用においては、パディングとして毎回乱数を生成して挿入するなどの対策がされている。

RSA暗号の安全性は素因数分解の困難さ（より正確には素因数が不明な法 n での冪根を求めることの難しさ）に基づいている。 しかし、平文の内容によっては、素因数分解をせずとも暗号文から平文を入手できる。

公開鍵暗号全般に言えることであるが、確定的暗号（例えば平文が「はい」か「いいえ」のどちらかしか有り得ない）であれば、それぞれを暗号化したものと暗号文とを比較すれば容易に平文を知ることができる。

実用上は、m の一部に毎回生成する乱数を挿入することで、この攻撃を回避できる（復号側で乱数部分を無視するよう処理すればよい）。

平文 m が、n の e 乗根よりも小さいと、暗号文 ${\displaystyle c=m^{e}\;\operatorname {mod} \;n=m^{e))$ となるから、通常の冪根演算によって c の e 乗根を計算するだけで平文 m が復元できてしまう。

実用上は、m の比較的高位のビットに1を挿入することでこの攻撃を回避できる。

法 n における e乗根が計算できれば、暗号文を復号できる。当然これは（法 n の素因数が分からない限り）非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。

しかし、全く同一の平文を、異なる法において同一の e を用いて暗号化した暗号文を e 個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これを同報通信の誤用と呼ぶ。

${\displaystyle {\begin{aligned}c_{1}&\equiv m^{e}{\pmod {n_{1))}\\c_{2}&\equiv m^{e}{\pmod {n_{2))}\\c_{3}&\equiv m^{e}{\pmod {n_{3))}\\\\c_{e}&\equiv m^{e}{\pmod {n_{e))}\end{aligned))}$

ここから中国の剰余定理によって上記式を満たす、

${\displaystyle c\equiv m^{e}{\pmod {n_{1}n_{2}n_{3}\dotsm n_{e))))$

を求めることができる。このとき ${\displaystyle c<n_{1}n_{2}n_{3}\dotsm n_{e))$ であり、また m はどの法 n よりも小さいため ${\displaystyle m^{e}<n_{1}n_{2}n_{3}\dotsm n_{e))$ であることから、

${\displaystyle c=m^{e))$

この c の e 乗根を求めることで平文 m が求められる。

e として 3 や 65537 は、2進数表示したときに 1 の個数が少なく暗号化処理を高速化できるという理由から好んで用いられるが、上記の問題がある。

実用上は、m の一部に毎回生成する乱数を挿入することでこの攻撃を回避できる。

RSA暗号の入力は、公開鍵の法を n とすると 0 から n − 1 の範囲の整数である。n 以上の値の平文を暗号化する際には、平文を分割して処理することになる。

この時に留意しなければならない点として、例えば、n が1024ビット（= 128バイト）であるとき、平文を同じ 1024ビット毎に分割処理するのでは十分ではないという点がある。これは、n と m が共に 1024ビットであったとしても、n < m の場合には、結果として出力されるのは、${\displaystyle m{\bmod {n))}$ に対応する暗号文であり、復号しても m は出力されないためである。

平文をビット単位（やバイト単位）で分割する際には、まず、n の下限を定めた上で、平文の全ビットを 1 に（全バイトを ${\displaystyle \mathrm {FF_{16)) }$ に）しても n より小さくなるビット数（バイト数）で分割しなければならない。例えば、n の下限を ${\displaystyle n\geq 2^{1023))$ とした場合、平文は 1023 ビットごとに分割する。こうすることで m < n の条件が常に満たされる。

一方で、出力となる暗号文は 0 から n − 1 の範囲の整数になるため、先の例で（n の下限より小さいビット数）1023ビット毎に分割された m に対応する暗号文の中には、1024ビットが必要となるものがある。つまり、平文をビット単位で分割する場合には暗号化によってメッセージサイズが増加するといえる。これを回避するにはビット単位で分割するのではなく、平文 m を n 進数表示したときの各桁毎に分割すればよい。

RSA暗号方式は、

• 平文が小さいと、暗号文から平文が容易に計算できてしまう、
• 暗号文を分解して、個々の暗号文に対応する平文を入手できる（選択暗号文攻撃）と、元の暗号文に対応する平文を求めることができてしまう、
• 攻撃者が暗号文を変形して、平文自体を知ることはできないが、平文を変形できてしまう（非展性がない）、

などの脆弱性があり、RSA暗号方式をそのまま利用することは好ましくない。このため、実際のRSA暗号の実装では、暗号化する前に適切なパディングを行っている。代表的なパディングとしてOAEPがあり、公開鍵暗号標準であるPKCS#1（バージョン1.5以降）もこれを採用している。OAEPは確率的なパディングであり、すなわち、元の平文が同じであっても、パディングされた平文は時によって異なる（ランダムに選ばれた値に依存）。

OAEPパディングとRSA暗号の併用をRSA_OAEPと呼ぶことがある（これに対して、パディング処理を行わない素のRSA暗号方式を生RSA、教科書的RSAということがある）。RSA_OAEPは、公開鍵暗号における最も高い安全性である「適応的選択暗号文攻撃に対する識別不可能性」を持つことが示されている^[5]。

RSA暗号が実現した公開鍵暗号方式は、従来の暗号方式（共通鍵暗号）とは異なり、暗号化は公開鍵を使って誰でもできるが、復号は秘密鍵を持つ本人だけしかできない方式である。この復号は「本人だけしかできない」という性質を利用すると、デジタル署名（あるいは認証機能）が実現できる。

そのためには、公開鍵・秘密鍵を次のように使用する。

• 暗号の場合

  平文 → 公開鍵（暗号化）→ 暗号文、暗号文→ 秘密鍵（復号）→ 平文

• 署名の場合

  文書 → 秘密鍵（署名生成）→ 署名値、署名値→ 公開鍵（署名検証）→ 文書

公開鍵と秘密鍵の役割は通常の場合においては上記の通り、公開鍵は暗号化に使われ、秘密鍵は復号に用いられるが、RSA暗号においては平文と暗号文の定義域が同じ（平文空間＝暗号文空間である）ため、任意の文書（メッセージ）を暗号文とみなして復号することができる。つまり秘密鍵を用いて任意の文書について署名値を生成でき、公開鍵を用いてその署名値を暗号化して元の文書と一致するかを調べることで署名の検証ができる。

ただし、RSA暗号と同様に、生RSAでは、署名の潜在的偽造等の好ましくない性質があるため、パディングなどが必要である。また、暗号文空間よりも大きなメッセージを扱うためにハッシュ関数と組み合わせて使用する。

このようなパディングなども含めたものとして、

• RSA_PSS with SHA-1

などがある。

1977年、マーティン・ガードナーがコラムを連載していたサイエンティフィック・アメリカン誌に129桁の法 n と公開指数 e = 9007 を使ったRSA方式で暗号化されたメッセージを掲載した^[6]。解読が成功した者にマサチューセッツ工科大学から100米ドルを与えるという懸賞金問題だった^[6]。当時、解読には4京年（40×10¹⁵年）は必要だろうと予測されていた^[6]。掲載から16年後に、オックスフォード大学ポール・レイランド（英語版）、アイオワ州立大学マイケル・グラフ、マサチューセッツ工科大学デレク・アトキンス、アリエン・レンストラ（英語版）らが、インターネット上で（南極大陸を除くすべての大陸から20か国以上の）約600名のボランティアの協力を得て、二次ふるい法によってRSA-129に対する大規模攻撃を開始した。8か月で800万以上の下位問題が解かれ、得られた50万行50万列以上の疎行列から188614行188160列の行列による連立方程式を作った。これをスーパーコンピュータMP-1で45時間をかけて構造的ガウスの消去法によって解き、解読に成功した（1994年4月）^[7]。答えは“The magic words are squeamish ossifrage”［ossifrage（ヒゲワシ）はラテン語で「骨を折る者」の意。ロナルド・リベストによると暗号の答えはランダムで決められた。^[8]

RSA暗号をサポートしているライブラリは以下の通り。

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• Libgcrypt
• Nettle
• OpenSSL
• wolfCrypt
• GnuTLS

• Cocks, Clifford C. (1973-11-20), A Note on Non-Secret Encryption, CESG, https://web.archive.org/web/20080227001905/http://www.cesg.gov.uk/site/publications/media/notense.pdf 2015年7月10日閲覧。 ：CocksがCESG（GCHQの一部局）に提出したメモ
• Rivest, Ronald L.; Shamir, Adi; Adelman, Len M. (1977-07-04), “A Method for Obtaining Digital Signature and Public-key Cryptsystems”, MIT-LCS-TM-082 (MIT Laboratory for Computer Science), https://people.csail.mit.edu/rivest/Rsapaper.pdf 2015年7月10日閲覧。 ：「日経エレクトロニクス」に全訳があるとされる。

• 暗号
• 暗号理論
• Optimal Asymmetric Encryption Padding (RSA-OAEP)
• 素因数分解
• ElGamal暗号
• 楕円曲線暗号
• en:RSA numbers - en:RSA Factoring Challenge

• 『RSA暗号の仕組みと安全性・具体例』 - 高校数学の美しい物語

表 話 編 歴 公開鍵暗号 アルゴリズム Cramer-Shoup暗号 ディフィー・ヘルマン鍵共有（楕円DH） Digital Signature Algorithm（楕円DSA） エドワーズ曲線デジタル署名アルゴリズム ElGamal暗号（ElGamal署名） EPOC (暗号) Merkle-Hellmanナップサック暗号 NTRU暗号 Paillier暗号 Rabin暗号 RSA暗号 ランポート署名 理論 離散対数 素因数分解 楕円曲線暗号 標準化 CRYPTREC IEEE P1363（英語版） NESSIE NSA Suite B（英語版） CNSA 関連項目 デジタル署名 Optimal Asymmetric Encryption Padding 指紋 公開鍵基盤

表 話 編 歴 暗号 暗号史 暗号解読 Cryptography portal en:Outline of cryptography 共通鍵暗号 ブロック暗号 ストリーム暗号 暗号利用モード 公開鍵暗号 暗号学的ハッシュ関数 メッセージ認証コード 認証付き暗号 乱数生成器 ステガノグラフィー

カテゴリ