RSA暗号

RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であることを安全性の根拠とした公開鍵暗号の一つである。暗号とデジタル署名を実現できる方式として最初に公開されたものである。
概要.
RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。前年（1976年）にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている。
RSA暗号は次のような方式である。
鍵のペア（公開鍵と秘密鍵）を作成して公開鍵を公開する。まず、適当な と互いに素な正整数 を選択する。また、大きな2つの素数の組 を生成し、それらの積 を求めて、組 を平文の暗号化に使用する鍵（公開鍵）とする。2つの素数 は秘密に保管し、暗号文の復号に使用する鍵（秘密鍵） の生成にも使用する (formula_1 、ここで formula_2)。式中の "formula_3" は剰余演算を表し、 は を法とする のモジュラ逆数である。formula_4 は の最小公倍数である。
暗号化（ 乗）は公開鍵 があれば容易に計算でき、復号（ 乗）は秘密鍵 と公開鍵 があれば容易に計算できる。しかし、秘密鍵 を知らずに解読する（法 の下で 乗根を計算する）のは、「 の素因数を知らないと難しい（大きい合成数の素因数分解も難しい）」と考えられている。つまり、「秘密鍵を用いずに暗号文から平文を得ることは難しい」と信じられている。これがRSA暗号の安全性の根拠である。
RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許（4,405,829号）を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。
暗号の用語については暗号#用語、暗号理論#用語を参照。
歴史.
歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者はである。彼らはイギリス最高機密機関・英国政府通信本部 (GCHQ) の職員であり、その独創的な先見の明は内部文書として長い間公開されなかった。また実用にはコンピュータの性能等から機が熟していなかった。以下はその概要である。
エリスは1969年にこの理論を発見しているが、専門の数学者ではなかったため、具体的な方法を発見できなかった。幾人ものGCHQの優秀な数学者が挑戦したが、具体的な方法を提示することはできなかった。1973年、突拍子もない暗号のアイデアとしてエリスの「一方向関数（非対称性鍵の概念）・公開鍵」を用いた暗号論の話を聞かされ、わずか30分程度でモジュラー算術と素因数を用いた具体的な方法を考案したのは、GCHQ所属の若き数学者である（コックスは上記のリベストの計算式と同じものを発見した）。しかしエリスとコックスの業績は機密事項とされたため、1997年までは世に知られることはなかった。
暗号方式.
鍵生成、暗号化、復号の3つのアルゴリズムで定義される。
鍵生成.
 を異なる2つの素数とし とする。 をオイラー関数とすると formula_7 となる。 を と素な正整数とすると formula_8 となる2整数 が存在する。 として1つの正整数 を選択してそのときの を とすると formula_9 となる。ここで を秘密鍵とし、 を公開鍵とする。以下 formula_10 を 以上 未満の整数の集合とする。
ここで、formula_8 のとき を整数とすると formula_12 であるから に の整数倍を加えたものも改めて とできるため、 として正整数 を選択できるとした。　
暗号化.
formula_13 とし を暗号化対象の平文とする。formula_14 を計算し、 を 平文 の暗号文とする。
復号.
formula_15 を計算する。すると となり は 平文 の暗号文 の復号文となる。
完全性の証明.
定義により以下が成立する。
これにより以下も成立する。
 が と互いに素な整数のときは が2つの素数 のそれぞれと互いに素であるから
フェルマーの小定理 により formula_18 かつ formula_19 であり
よって formula_21 は で割り切れるから formula_22 となり
となるが、formula_24 であるから
となる。
formula_26 であり、formula_27 のときは、 は 個の整数からなる集合 formula_28 の元であって、 が で割り切れるから formula_29 であり、 が素であるからフェルマーの小定理により formula_19 であり
よって
よって
よって は で割り切れるから
となるが、formula_24 であるから
となる。
formula_37 であり formula_27 のときについても同様に となる。
 のときは formula_39 であるから であり、formula_40 であるから である。つまり である。
以上何れにしても が成り立ち、平文 の 暗号文 は 秘密鍵 と 公開鍵の一つ を用いて 平文 に復号できることが分かる。
性能.
"n" を法とする冪剰余の計算.
 の場合、 は1024ビットサイズという大きな数となり、 もほぼ と同サイズの数となる。formula_41 を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算 (formula_42) を、1500回程繰り返すことで実現できる。これには相当の計算時間を要するため、中国の剰余定理を用いて、
として求めることがある。
素数生成.
桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller–Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数 (probable prime) という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる。
(なお、拡張リーマン予想が正しければ、Miller–Rabinテストは素数かどうかを正しく判定する、という事実が知られている)。
2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間で行うAKS素数判定法を発表したが、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。
安全性.
RSA暗号と素因数分解問題の関係.
RSA暗号は、安全性が素因数分解問題と同値であると期待されている暗号方式であるが、本当に両者が同値であるかどうかについては分かっていない。
素因数分解を解けるオラクルを用いれば、 から および が計算できるので、鍵生成と同様にして秘密鍵 を知ることができる。即ち、RSA暗号が解読できる。従って、RSA仮定が証明できれば素因数分解問題の困難性が示せる。しかし、逆が成立するかどうかはよく分かっていない。ある条件下では否定的な結果もでている。
RSA暗号が選択平文攻撃に対して完全解読できない、ということとRSA仮定とは同値である。
RSA問題を解く方法として、現在知られている有力な方法は、素因数分解問題を解くことに使える方法だけである。素因数分解問題を解く方法として、楕円曲線法や数体篩法などのアルゴリズムが知られているが、これらの方法はどれも準指数関数時間アルゴリズムであり、多項式時間で素因数分解問題を解く方法は知られていない。
暗号理論の世界では、多項式時間で解読することができない暗号方式を安全であると定義することがある（計算量的安全性）。この意味で、RSA暗号の安全性について、現在知られている範囲では安全であると期待されていて、その反証がないと言える。
RSA問題や素因数分解問題はNP問題であるので、これらの問題が（決定性のある）多項式時間では解けないことが証明できれば、P≠NP予想が肯定的に解決することになる。ただし、ハミルトン閉路問題など他のNP問題（NPかつNP困難なNP完全問題を含む）が多項式時間で解けることが証明されればP=NPとなってしまう。
素因数分解可能な範囲.
2004年の時点では、インターネットで公募した数多くのPCを用いると512ビット程度の数なら素因数分解できるので、RSA暗号に使用する法 は1024-4096ビット（10進数で300-1000桁程度）にすることが推奨されている。
しかしShamirは、RSA問題を解くための専用装置 ("TWIRL") を作成すれば、1024ビットの に関するRSA問題ですら解くことができると主張している。また、実用的な量子コンピュータが登場した場合には、素因数分解の桁数増に対する計算時間の増加が緩やかなと呼ばれる高速な量子コンピュータアルゴリズムが実行可能となるため、たとえ鍵のビット数を増やしてもRSA暗号の安全性が保証されなくなる可能性が指摘されている。
RSA暗号解読コンテスト.
RSA社は「」を1991年から2007年まで実施し、最新の計算機環境でどの程度のビット数の整数が素因数分解可能かを調べた。
以下は未踏
RSA暗号の性質.
RSA暗号は選択暗号文攻撃を行なえば完全解読できる。また、RSA暗号は選択平文攻撃に対してすらindistinguishable（識別不能）ではない。よってRSA暗号は選択平文攻撃に対してnon-malleable（頑強性）でも semantic secure（強秘匿性）でもない。 と の定義は公開鍵暗号に記されている。
脆弱な平文.
RSA暗号の安全性が素因数が不明な法 での冪根を求めるのが難しい事実に基づいていることから、その最大の攻撃が素因数分解であることは明白である。
しかし平文によっては、それ以外の攻撃方法でも暗号文から平文を入手することが可能である。
決まりきった平文.
これは公開鍵暗号全般に言えることであるが、確定的暗号であれば、例えば平文が「はい」か「いいえ」のどちらかしか有り得ないなら、それぞれを暗号化したものと暗号文とを比較すれば平文を知ることができる。
実際の暗号への応用においてはフォーマットとして の一部に毎回生成する乱数を挿入することでこの攻撃を回避している(復号側で後半の乱数を無視するよう機械を設定すればよい)
小さな"m".
もしも平文 が、 の 乗根よりも小さかったら、暗号文 formula_44 となるから、通常の冪根演算によって の 乗根を計算するだけで平文 が復元できてしまう。
実際の暗号への応用においてはフォーマットの一部として、 の比較的高位のビットに1を挿入することでこの攻撃を回避している。
同一平文.
法 における 乗根が計算できれば、暗号文を復号できる。当然これは（法 の素因数が分からない限り）非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。
しかし、全く同一の平文を、異なる法において同一の を用いて暗号化した暗号文を 個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これが同報通信の誤用である。
ここから中国の剰余定理によって上記式を満たす、
を求めることができる。このとき formula_47 であり、また はどの法 よりも小さいため formula_48 であることから、
この の 乗根を求めることで平文 が求められる。
これは として特に や は、進数表示したときに の個数が少ないために暗号化処理を高速化できるという理由から好んで用いられるために発生しうる問題である。実際の暗号への応用においてはフォーマットとして、 の一部に毎回生成する乱数を挿入することでこの攻撃を回避している。
その他.
RSA暗号の入力は、モジュラスを とすると から の範囲の整数である。 以上の値の平文を暗号化する際には、平文を分割して処理することになる。
この時に留意しなければならない点として、例えば、 がビット（バイト）であるとき、平文を同じ ビット毎に分割処理するのでは十分ではないという点がある。これは、 と が共に ビットであったとしても、 の場合には、結果として出力されるのは、formula_50 に対応する暗号文であり、復号しても は出力されないためである。
平文をビット単位（やバイト単位）で分割する際には、まず、 の下限を定めた上で、平文の全ビットを に（全バイトを formula_51 に）しても より小さくなるビット数（バイト数）で分割しなければならない。例えば、 の下限を formula_52 とした場合、平文は ビットごとに分割する。こうすることで の条件が常に満たされる。
一方で、出力となる暗号文は から の範囲の整数になるため、先の例で（ の下限より小さいビット数）ビット毎に分割された に対応する暗号文の中には、ビットが必要となるものがある。つまり、平文をビット単位で分割する場合には暗号化によってメッセージサイズが増加するといえる。これを回避するにはビット単位で分割するのではなく、平文 を 進数表示したときの各桁毎に分割すればよい。
パディング.
RSA暗号方式は、
などの脆弱性があり、RSA暗号方式をそのまま利用することは好ましくない。このため、実際のRSA暗号の実装では、暗号化する前に適切なパディングを行っている。代表的なパディングとしてOAEPがあり、公開鍵暗号標準であるPKCS#1（バージョン1.5以降）もこれを採用している。OAEPは確率的なパディングであり、すなわち、元の平文が同じであっても、パディングされた平文は時によって異なる（ランダムに選ばれた値に依存）。
OAEPパディングとRSA暗号の併用をRSA_OAEPと呼ぶことがある。（これに対して、パディング処理を行わない素のRSA暗号方式を生RSA、教科書的RSAということがある。）RSA_OAEPは、公開鍵暗号における最も高い安全性である「適応的選択暗号文攻撃に対する識別不可能性」を持つことが示されている。
デジタル署名方式への応用.
RSA署名.
RSA暗号が実現した公開鍵暗号方式は、従来の暗号方式（共通鍵暗号）とは異なり、暗号化は公開鍵を使って誰でもできるが、復号は秘密鍵を持つ本人だけしかできない方式である。この復号は「本人だけしかできない」という性質を利用すると、デジタル署名（あるいは認証機能）が実現できる。
そのためには、公開鍵・秘密鍵を次のように使用する。
公開鍵と秘密鍵の役割は通常の場合においては上記の通り、公開鍵は暗号化に使われ、秘密鍵は復号に用いられるが、RSA暗号においては平文と暗号文の定義域が同じ（平文空間＝暗号文空間である）ため、任意の文書（メッセージ）を暗号文とみなして復号することができる。つまり秘密鍵を用いて任意の文書について署名値を生成でき、公開鍵を用いてその署名値を"暗号化"して元の文書と一致するかを調べることで署名の検証ができる。
ただし、RSA暗号と同様に、生RSAでは、署名の潜在的偽造等の好ましくない性質があるため、パディングなどが必要である。また、暗号文空間よりも大きなメッセージを扱うためにハッシュ関数と組み合わせて使用する。
このようなパディングなども含めたものとして、
などがある。
RSA-129.
1977年、マーティン・ガードナーがコラムを連載していたサイエンティフィック・アメリカン誌に129桁の合成数 と公開鍵 を使ったRSA方式で暗号化されたメッセージを掲載した。解読が成功した者にマサチューセッツ工科大学から100米ドルを与えるという懸賞金問題だった。当時、解読には4京年（40×1015年）は必要だろうと予測されていた。掲載から16年後に、オックスフォード大学、アイオワ州立大学マイケル・グラフ、マサチューセッツ工科大学デレク・アトキンス、らが、インターネット上で（南極大陸を除くすべての大陸から20か国以上の）約600名のボランティアの協力を得て、二次ふるい法によってRSA-129に対する大規模攻撃を開始した。8か月で800万以上の下位問題が解かれ、得られた50万行50万列以上の疎行列から188614行188160列の行列による連立方程式を作った。これをスーパーコンピュータMP-1で45時間をかけて構造的ガウスの消去法によって解き、解読に成功した（1994年4月）。答えは“codice_1”［ossifrage（ヒゲワシ）はラテン語で「骨を折る者」の意。ロナルド・リベストによると暗号の答えはランダムで決められた。］
実装ライブラリ.
RSA暗号をサポートしているライブラリは以下の通り。