RSA暗号のソースを表示

{{出典の明記|date=2017年3月7日 (火) 13:30 (UTC)}}
{{Infobox Encryption method
| name          = RSA
| designers     = [[ロナルド・リベスト]]、[[アディ・シャミア]]、[[レオナルド・エーデルマン]]
| publish date  = 1977
| type          = 公開鍵
| derived from  =
| derived to    =
| related to    =
| certification = [[PKCS|PKCS#1]],  [[ANSI X9.31]], [[P1363|IEEE 1363]]
| key size      =1,024 to 4,096 bit typical
| block size    =
| structure     =
| rounds        = 1
| cryptanalysis = 768 bit key (RSA-768)は解読済み
}}
'''RSA暗号'''とは、桁数が大きい[[合成数]]の[[素因数分解]]問題が困難であることを安全性の根拠とした[[公開鍵暗号]]の一つである。<!-- 素因数分解問題はNP困難とは予想されていない -->
暗号<ref>{{lang-en-short|cipher}}</ref>と[[デジタル署名]]を実現できる方式として最初に公開されたものである。<!-- RSA以前に同方式は発明されていたが、公開されなかった。 -->

== 概要 ==
1977年に発明され、発明者である[[ロナルド・リベスト]]、[[アディ・シャミア]]、[[レオナルド・エーデルマン]]の原語表記の頭文字をつなげてこのように呼ばれる<ref name=スチュアート2010>{{Cite book |和書 |author=イアン・スチュアート |authorlink=イアン・スチュアート |year=2010 |title=数学の魔法の宝箱 |publisher=ソフトバンク クリエイティブ |chapter=おおっぴらにできる暗号 |page=63 |isbn=978-4-7973-5982-4}}</ref>。当時、[[ホイットフィールド・ディフィー|ディフィー]]と[[マーティン・ヘルマン|ヘルマン]]によって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的な[[アルゴリズム]]を与えた。発明者3氏は、この功績によって[[2002年]]の[[チューリング賞]]を受賞した。この暗号は[[フェルマーの小定理]]に基づいている<ref name=スチュアート2010 />。

RSA暗号は次のような方式である：
鍵ペア（公開鍵と秘密鍵）を作成して公開鍵を公開する。まず、適当な正整数 ''e''（通常は小さな数。[[65537]] (= 2<sup>16</sup> + 1) がよく使われる）を選択する。また、大きな2つの素数 {''p'', ''q''} を生成し、それらの積 ''n'' (=''pq'') を求めて、{''e'', ''n''} を平文の暗号化に使用する鍵（公開鍵）とする。2つの素数 {''p'', ''q''} は、暗号文の復号に使用する鍵（秘密鍵）''d'' の生成にも使用し (<math>d=e^{-1} \pmod{(p-1)(q-1)}</math>)、秘密に保管する。

* 暗号化（[[平文]] ''m'' から暗号文 ''c'' を作成する）： <math>c = m^e \; \operatorname{mod}\; n</math>
* 復号（暗号文 ''c'' から元の平文 ''m'' を得る）： <math>m = c^d \; \operatorname{mod}\; n</math>

ここで、暗号化（''e'' 乗）は、{''e'', ''n'' } があれば容易に計算できるのに対して、復号（''e'' 乗根）は、「''n'' の素因数を知らないと難しい（大きい合成数の素因数分解も難しい）」と考えられている。つまり秘密鍵を用いずに暗号文から平文を得ることは難しい、と信じられている。これがRSA暗号の安全性の根拠である。

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

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

== 歴史 ==
歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者は{{仮リンク|ジェイムズ・エリス|en|James H. Ellis}}である。彼らはイギリス最高機密機関、[[政府通信本部|英国政府通信本部]] (GCHQ) の職員であり、その独創的な先見の明は内部文書として長い間公開されなかった。また実用にはコンピュータの性能等から機が熟していなかった。以下はその概要である。

エリスは1969年にこの理論を発見しているが、専門の数学者ではなかったため、具体的な方法を発見できなかった。幾人ものGCHQの優秀な数学者が挑戦したが、具体的な方法を提示する事はできなかった。1973年、'''突拍子もない暗号のアイデア'''としてエリスの「一方向関数（非対称性鍵の概念）・公開鍵」を用いた暗号論の話を聞かされ、わずか30分程度でモジュラー算術と素因数を用いた具体的な方法を考案したのは、GCHQ所属の若き数学者{{仮リンク|クリフォード・コックス|en|Clifford Cocks}}である（コックスは上記のリベストの計算式と同じものを発見した）。しかしエリスとコックスの業績は機密事項とされたため、1997年までは世に知られることはなかった。<ref>{{Cite book |和書 |author=イアン・スチュアート |authorlink=イアン・スチュアート |year=2010 |title=数学の魔法の宝箱 |publisher=ソフトバンク クリエイティブ |chapter=おおっぴらにできる暗号 |page=66 |isbn=978-4-7973-5982-4}}</ref>

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

=== 鍵生成 ===
<math>k</math> をセキュリティパラメータとする。

<math>p</math>、<math>q</math> (ただし <math>p\neq q</math>) を <math>k/2</math> [[ビット]]の[[素数]]とし、<math>n = pq</math> とする。<math>e</math> を <math>\phi(n)</math> 未満の正の整数で、<math>\phi(n)</math> と[[最大公約数|互いに素]]な数とし、<math>d</math> を、<math>\phi(n)</math> を法とした <math>e</math> の逆数（<math>de \equiv 1 \pmod{\phi(n)}</math>）とする。
ただしここで <math>\phi</math> は [[オイラーのφ関数]]で、この場合は <math>\phi(n)=(p-1)(q-1)</math> である。<math>d</math> は、<math>e</math>、<math>\phi(n)</math> が既知のときには[[ユークリッドの互除法#拡張された互除法|拡張されたユークリッドの互除法]]を使えば容易に求まる（<math>de</math> を <math>\phi(n)</math> で割った整数商を <math>x</math> とした場合、<math>de+(-x)\phi(n)=1</math> が成り立ち、かつ <math>e</math> の取り方から <math>\mathrm{gcd}(e, \phi(n)) = 1</math> であるのでこれを解けば良い）。<math>d</math> を秘密鍵とし、<math>n</math>、<math>e</math> を公開鍵とする (<math>p</math>と<math>q</math>が漏れると <math>d</math> が計算で求まるため、<math>p</math>と<math>q</math>は安全に破棄すること)

以下では、<math>0</math> 以上 <math>n</math> 未満の[[整数]]の集合を <math>{\Bbb Z}_n</math> で表すことにする。
[[平文空間]]および[[暗号文空間]]は <math>{\Bbb Z}_n</math>。

=== 暗号化 ===
<math>a</math> を平文空間 <math>{\Bbb Z}_n</math> の[[元 (数学)|元]]とする。<math>b = a^e \bmod n</math>（<math>n</math> を法とする[[除法#商・法・剰余|剰余]]）を計算し、<math>b</math> を出力する。

=== 復号 ===
<math>b</math> を暗号文とする。<math>a=b^d \bmod n</math> を計算し、<math>a^\prime</math> を出力する。ここで <math>a = a^\prime</math> となり復号できる。

=== 完全性の証明 ===
以下に証明を示す。ここで <math>a^\prime</math> は、<math>a^e</math> をさらに <math>d</math> 乗したものの <math>n</math> を法とする剰余で、<math>de\equiv 1\pmod{\phi(n)}</math> であるから、ある <math>x</math> が存在して

{{indent|<math>a^\prime\equiv a^{(de)} \pmod{n} \equiv a^{(x\cdot\phi(n)+1)} 
 \pmod{n}</math>
}}

ここで[[フェルマーの小定理#オイラーの定理|オイラーの定理]]により、<math>n</math> と互いに素な整数 <math>a</math> については <math>a^{\phi(n)} \equiv 1 \pmod{n}</math> であるため、

{{indent|<math>a^\prime \equiv 1^x \cdot a^1 \equiv a \pmod{n}</math>}}

となる。

<math>\mathrm{gcd}(n,a) = p</math> である整数 <math>a</math> については、

{{indent|
<math>a = p\cdot i = q \cdot j + r</math>、<br>
<math>0 < i < q</math>、<br>
<math>0 \leq r < q</math>、<br>
<math>0 \leq j < p</math>
}}

として

{{indent|<math>\begin{align}
a^\prime &\equiv 0 \pmod{p} \\
a^\prime &\equiv a \equiv r \pmod{q}
\end{align}</math>
}}

となるから[[中国の剰余定理]]により、<math>p \cdot xp = 1 + q \cdot xq</math> なる整数 <math>xp</math> と <math>xq</math> を用いて

{{indent|
<math>a^\prime \equiv 0 \cdot q \cdot xq + r \cdot p \cdot xp \equiv (p \cdot i-q\cdot j) \cdot p \cdot xp \equiv p \cdot i \cdot p \cdot xp \equiv p \cdot i \cdot (1 + q \cdot xq)\equiv p \cdot i \equiv a \pmod{n}</math>
}}

となる（<math>\mathrm{gcd}(n, a) = q</math> である整数についても同様）。ここで、<math>a^\prime</math> も <math>a</math> も <math>n</math> を法とした剰余なので、

{{indent|<math>a^\prime = a</math>}}

が成り立ち <math>b</math> は <math>d</math> と <math>n</math> を用いて <math>a</math> に復号できることが分かる。

== 性能 ==
=== ''n'' を法とする冪剰余の計算 ===
{{記事参照|冪剰余}}
<math>k = 1024</math> の場合、<math>n</math> は1024ビットサイズという大きな数となり、<math>d</math> もほぼ <math>n</math> と同サイズの数となる。
<math>a = b^d \bmod n</math> を計算するには、[[冪乗#効率的な演算法|バイナリ法]]というアルゴリズムを用いると、剰余乗算 (<math>1024\mathrm {bit} \times 1024\mathrm{bit}</math>) を、1500回程繰り返すことで実現できる。
これには相当の計算時間を要するため、[[中国の剰余定理]]を用いて、

{{indent|
<math>ap = b^{d \bmod \phi(p)} \bmod p</math><br>
<math>aq = b^{d \bmod \phi(q)} \bmod q</math><br>
<math>a^\prime = ap (q^{-1} \bmod p) q + aq (p^{-1} \bmod q) p</math>
}}

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

=== 素数生成 ===
桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成は[[ミラー–ラビン素数判定法|Miller–Rabinテスト]]などの[[素数判定#確率的素数判定法|確率的素数判定法]]によって高速に行える。確率的素数判定法をパスした自然数を確率的素数 (probable prime) という。確率的素数には、素数の他に[[フェルマーの小定理#フェルマーテスト|擬素数]]が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる。

(なお、拡張[[リーマン予想]]が正しければ、Miller–Rabinテストは素数かどうかを正しく判定する、という事実が知られている)。<!-- MRテストには幾つか変形があるので補足が必要な気がする -->

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

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

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

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

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

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

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

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

しかしShamirは、RSA問題を解くための専用装置 (''TWIRL'') を作成すれば、1024ビットの ''n'' に関するRSA問題ですら解くことができると主張している。

==== RSA暗号解読コンテスト ====
RSA社は「[[:en:RSA Factoring Challenge|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月 RSA-129 (426ビット)
* 1996年4月10日 RSA-130 (430ビット)
* 1999年2月2日 RSA-140 (463ビット)
* 2004年 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桁）
* yet RSA-180 (596ビット)
* yet RSA-190 (629ビット)
* 2005年11月2日 RSA-640 (640ビット)
* 2005年5月9日 RSA-200 (663ビット、10進200桁)
* yet RSA-210 (696ビット、10進210桁)
* yet RSA-704 (704ビット)
* 2009年12月12日 RSA-768 (768ビット)

以下は未踏
* RSA-896
* RSA-1024
* RSA-1536
* RSA-2048

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

=== RSA暗号の誤用 ===
==== パラメータの選択 ====
<!--[[Strong Prime]]-->
{{節スタブ}}

==== 特殊な(誤った)応用 ====
; 共通の法 <math>n</math>
: ユーザー管理等の利便性や素数探索の労を避ける為、法である <math>n</math> を共通として各々に個別の <math>e</math> と <math>d</math> を与えるのは誤りである。もしも法 <math>n</math> とそれに対応する <math>e</math> と <math>d</math> の組を一つでも知ることができれば、法 <math>n</math> の[[素因数分解]]が容易となり安全ではなくなるからである。
; 同報通信
: '''まったく同一の平文'''を複数の送信先へ各々の公開鍵で暗号化して同報通信するには適していない。同じ <math>e</math> を持つ公開鍵（[[ハミング重み]] <math>HW = 2</math> である <math>3</math> や <math>65537</math> が好んで用いられる）で暗号化された <math>e</math> 個以上の暗号文を手に入れたなら各々の公開鍵の法に関して[[中国の剰余定理]]を用いることで、通常の[[冪根]]によって平文を復元できるからである。詳しくは下記の同一平文を参照のこと。
:このため、現在規格化されている暗号への応用においては、パディングとして毎回[[乱数]]を生成して挿入するなどの対策がされている。

{{節スタブ}}

=== 脆弱な平文 ===
RSA暗号の安全性が素因数が不明な法<math>n</math>での[[冪根]]を求めるのが難しい事実に基づいていることから、その最大の攻撃が[[素因数分解]]であることは明白である。

しかし平文によっては、それ以外の攻撃方法でも暗号文から平文を入手することが可能である。

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

実際の暗号への応用においてはフォーマットとして <math>m</math> の一部に毎回生成する[[乱数]]を挿入することでこの攻撃を回避している(復号側で後半の乱数を無視するよう機械を設定すればよい)

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

実際の暗号への応用においてはフォーマットの一部として、''m'' の比較的高位の[[ビット]]に1を挿入することでこの攻撃を回避している。

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

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

{{indent|
<math>c_1 \equiv m^e \pmod{n_1}</math><br>
<math>c_2 \equiv m^e \pmod{n_2}</math><br>
<math>c_3 \equiv m^e \pmod{n_3}</math><br>
<br>
<math>c_e \equiv m^e \pmod{n_e}</math>
}}

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

{{indent|
<math>c \equiv m^e \pmod{ n_1 n_2 n_3 \dots n_e }</math>
}}

を求めることができる。このとき <math>c < n_1 n_2 n_3 \dots n_e</math> であり、また <math>m</math> はどの法 <math>n</math> よりも小さいため <math>m^e < n_1 n_2 n_3 \dots n_e</math> であることから、

{{indent|
<math>c = m^e</math>
}}

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

これは <math>e</math> として特に <math>3</math> や <math>65537</math> は、<math>2</math>進数表示したときに<math>1</math>の個数が少ない<!--素数である上に小さい-->ために暗号化処理を高速化できるという理由から好んで用いられるために発生しうる問題である。実際の暗号への応用においてはフォーマットとして、<math>m</math> の一部に毎回生成する[[乱数]]を挿入することでこの攻撃を回避している。

=== その他 ===
RSA暗号の入力は、モジュラスを <math>n</math> とすると <math>0</math> から (<math>n-1</math>) の範囲の整数である。<math>n</math> 以上の値の平文を暗号化する際には、平文を分割して処理することになる。

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

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

一方で、出力となる暗号文は <math>0</math> から (<math>n-1</math>) の範囲の整数になるため、先の例で（<math>n</math> の下限より小さいビット数）<math>1023</math>ビット毎に分割された <math>m</math> に対応する暗号文の中には、<math>1024</math>ビットが必要となるものがある。つまり、平文をビット単位で分割する場合には暗号化によってメッセージサイズが増加するといえる。これを回避するにはビット単位で分割するのではなく、平文 <math>m</math> を <math>n</math> 進数表示したときの各桁毎に分割すればよい。
<!-- ；書いてみたが不必要と感じたのでコメントアウト 
RSA暗号を安全に利用するためには、メッセージに乱数を付加してパディングする必要があり、平文のサイズは n のサイズよりもずっと少ない。PKCS#1 v2.1では、SHA1を用いたRSAES-OAEPの場合には、鍵長が<math>1024</math>ビット(<math>=128</math>バイト)のとき、平文のサイズは<math>86</math>バイトと定めされている。-->

=== パディング ===
RSA暗号方式は、
*平文が小さいと、暗号文から平文が容易に計算できてしまう、
*暗号文を分解して、個々の暗号文に対応する平文を入手できる（選択暗号文攻撃）と、元の暗号文に対応する平文を求めることができてしまう、
*攻撃者が暗号文を変形して、平文自体を知ることはできないが、平文を変形できてしまう（非展性がない）、
などの脆弱性があり、RSA暗号方式をそのまま利用することは好ましくない。このため、実際のRSA暗号の実装では、暗号化する前に適切なパディングを行っている。代表的なパディングとして[[Optimal Asymmetric Encryption Padding|OAEP]]があり、公開鍵暗号標準である[[PKCS]]#1（バージョン1.5以降）もこれを採用している。OAEPは確率的なパディングであり、すなわち、元の平文が同じであっても、パディングされた平文は時によって異なる（ランダムに選ばれた値に依存）。

OAEPパディングとRSA暗号の併用をRSA_OAEPと呼ぶことがある。（これに対して、パディング処理を行わない素のRSA暗号方式を生RSA、教科書的RSAということがある。）RSA_OAEPは、公開鍵暗号における最も高い安全性である「適応的選択暗号文攻撃に対する識別不可能性」を持つことが示されている<ref>{{citation |first1=英一郎 |last1=藤崎 |first2=龍明 |last2=岡本 |first3=David |last3=Pointcheval |first4=Jacques |last4=Stern |contribution=RSA-OAEP is secure under the RSA assumption |url= http://eprint.iacr.org/2000/061.pdf |title=Advances in Cryptology — CRYPTO 2001 |volume=2139 |pages=260-274 |journal=Lecture Notes in Computer Science |publisher=Springer-Verlag |year=2001 }}</ref>。

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

そのためには、公開鍵・秘密鍵を次のように使用する。
*暗号の場合
**平文 → 公開鍵（暗号化）→ 暗号文、暗号文→ 秘密鍵（復号）→ 平文
*署名の場合
**文書 → 秘密鍵（署名生成）→ 署名値、署名値→ 公開鍵（署名検証）→ 文書

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

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

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

* RSA_PSS with SHA-1

などがある。

=== RSA-129 ===
[[1977年]]、[[マーティン・ガードナー]]がコラムを連載していた[[サイエンティフィック・アメリカン]]誌に129桁の鍵を使ったRSA方式で暗号化されたメッセージを掲載。解読が成功したものに[[マサチューセッツ工科大学]]から100[[米ドル]]を与えるという懸賞金問題を掲載。当時、解読には2万年は必要だろうと予測されていたが掲載から17年後、[[オックスフォード大学|オックスフォード大]]{{仮リンク|ポール・レイランド|en|Paul Leyland}}、[[アイオワ州立大学|アイオワ州立大]]マイケル・グラフ、マサチューセッツ工科大学デレク・アトキンス、{{仮リンク|アリエン・レンスター|en|Arjen Lenstra}}らで、二次ふるい法とインターネット（600名からなる有志）を使いRSA-129に対する大規模攻撃を開始。8ヶ月で800万以上の下位問題が解かれ、スーパーコンピューターで解析、解読に成功。答えは“<code {{lang属性|en}}>The magic words are squeamish ossifrage</code>”［ossifrage（[[ヒゲワシ]]）は[[ジョーク]]で「骨折り」の意］。

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

* [[:en:Botan_(programming_library)|Botan]]
* [[:en:Bouncy_Castle_(cryptography)|Bouncy Castle]]
* [[:en:Cryptlib|cryptlib]]
* [[:en:Crypto++|Crypto++]]
* [[:en:Libgcrypt|Libgcrypt]]
* [[:en:Nettle_(cryptographic_library)|Nettle]]
* [[OpenSSL]]
* [[wolfCrypt]]

== 出典・脚注 ==
<references/>

== 参考文献 ==
=== 原論文 ===
* {{citation | first=Clifford C. | last=Cocks | url=http://web.archive.org/web/20080227001905/http://www.cesg.gov.uk/site/publications/media/notense.pdf  | title=A Note on Non-Secret Encryption | publisher=CESG | date=1973-11-20 | accessdate=2015-07-10 }}: CocksがCESG([[政府通信本部|GCHQ]]の一部局)に提出したメモ
* {{citation | url=https://people.csail.mit.edu/rivest/Rsapaper.pdf | title=A Method for Obtaining Digital Signature and Public-key Cryptsystems | first1=Ronald L. | last1=Rivest | first2=Adi | last2=Shamir | first3=Len M. | last3=Adelman | publisher=MIT Laboratory for Computer Science | journal=MIT-LCS-TM-082 | date=1977-07-04 | accessdate=2015-07-10 }} ：「日経エレクトロニクス」に全訳があるとされる。

== 関連項目 ==
*[[暗号]]
*[[暗号理論]]
*[[Optimal Asymmetric Encryption Padding|RSA-OAEP]]
*[[RSA-OAEP＋]]
*[[素因数分解]]
*[[ElGamal暗号]]
*[[楕円曲線暗号]]
*[[:en:RSA numbers]] - [[:en:RSA Factoring Challenge]]

{{cryptography navbox|public-key}}
{{DEFAULTSORT:ああるえすええあんこう}}

[[カテゴリ:暗号]]
[[カテゴリ:イギリス政府通信本部]]
[[カテゴリ:エポニム]]