RSA暗号

歴史

歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者はジェイムズ・エリスである。彼らはイギリス最高機密機関、英国政府通信本部 (GCHQ) の職員であり、その独創的な先見の明は内部文書として長い間公開されなかった。また実用にはコンピュータの性能等から機が熟していなかった。以下はその概要である。
エリスは1969年にこの理論を発見しているが、専門の数学者ではなかったため、具体的な方法を発見できなかった。幾人ものGCHQの優秀な数学者が挑戦したが、具体的な方法を提示する事はできなかった。1973年、突拍子もない暗号のアイデアとしてエリスの「一方向関数（非対称性鍵の概念）・公開鍵」を用いた暗号論の話を聞かされ、わずか30分程度でモジュラー算術と素因数を用いた具体的な方法を考案したのは、GCHQ所属の若き数学者クリフォード・コックスである（コックスは上記のリベストの計算式と同じものを発見した）。しかしエリスとコックスの業績は機密事項とされたため、1997年までは世に知られることはなかった。

暗号方式

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

鍵生成

をセキュリティパラメータとする。
、 (ただし ) を  ビットの素数とし、 とする。 を  未満の正の整数で、 と互いに素な数とし、 を、 を法とした  の逆数（）とする。
ただしここで  は オイラーのφ関数で、この場合は  である。 は、、 が既知のときには拡張されたユークリッドの互除法を使えば容易に求まる（ を  で割った整数商を  とした場合、 が成り立ち、かつ  の取り方から  であるのでこれを解けば良い）。 を秘密鍵とし、、 を公開鍵とする (とが漏れると  が計算で求まるため、とは安全に破棄すること)
以下では、 以上  未満の整数の集合を  で表すことにする。
平文空間および暗号文空間は 。

暗号化

を平文空間  の元とする。（ を法とする剰余）を計算し、 を出力する。

復号

を暗号文とする。 を計算し、 を出力する。ここで  となり復号できる。

完全性の証明

以下に証明を示す。ここで  は、 をさらに  乗したものの  を法とする剰余で、 であるから、ある  が存在して
ここでオイラーの定理により、 と互いに素な整数  については  であるため、
となる。
 である整数  については、
、
、
、
として
となるから中国の剰余定理により、 なる整数  と  を用いて
となる（ である整数についても同様）。ここで、 も  も  を法とした剰余なので、
が成り立ち  は  と  を用いて  に復号できることが分かる。

素数生成

桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成は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暗号に使用する法 n を1024-4096ビット（10進数で300-1000桁程度）にすることが推奨されている。
しかしShamirは、RSA問題を解くための専用装置 (TWIRL) を作成すれば、1024ビットの n に関するRSA問題ですら解くことができると主張している。

RSA暗号の性質

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

脆弱な平文

RSA暗号の安全性が素因数が不明な法での冪根を求めるのが難しい事実に基づいていることから、その最大の攻撃が素因数分解であることは明白である。
しかし平文によっては、それ以外の攻撃方法でも暗号文から平文を入手することが可能である。

決まりきった平文

これは公開鍵暗号全般に言えることであるが、確定的暗号であれば、例えば平文が「はい」か「いいえ」のどちらかしか有り得ないなら、それぞれを暗号化したものと暗号文とを比較すれば平文を知ることができる。
実際の暗号への応用においてはフォーマットとして  の一部に毎回生成する乱数を挿入することでこの攻撃を回避している(復号側で後半の乱数を無視するよう機械を設定すればよい)

小さなm

もしも平文 m が、n の e 乗根よりも小さかったら、暗号文  となるから、通常の冪根演算によって c の e 乗根を計算するだけで平文 m が復元できてしまう。
実際の暗号への応用においてはフォーマットの一部として、m の比較的高位のビットに1を挿入することでこの攻撃を回避している。

同一平文

法  における  乗根が計算できれば、暗号文を復号できる。
当然これは（法  の素因数がわからない限り）非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。
しかし、まったく同一の平文を、異なる法において同一の  を用いて暗号化した暗号文を  個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これが同報通信の誤用である。
ここから中国の剰余定理によって上記式を満たす
を求めることができる。このとき  であり、また  はどの法  よりも小さいため  であることから、
この  の  乗根を求めることで平文  が求められる。
これは  として特に  や  は、進数表示したときにの個数が少ないために暗号化処理を高速化できるという理由から好んで用いられるために発生しうる問題である。実際の暗号への応用においてはフォーマットとして、 の一部に毎回生成する乱数を挿入することでこの攻撃を回避している。

その他

RSA暗号の入力は、モジュラスを  とすると  から () の範囲の整数である。 以上の値の平文を暗号化する際には、平文を分割して処理することになる。
この時に留意しなければならない点として、例えば、 がビット（バイト）であるとき、平文を同じビット毎に分割処理するのでは十分ではないという点がある。これは、 と  が共にビットであったとしても、 の場合には、結果として出力されるのは、 に対応する暗号文であり、復号しても  は出力されないためである。
平文をビット単位（やバイト単位）で分割する際には、まず、 の下限を定めたうえで、平文の全ビットを  に（全バイトを  に）しても  より小さくなるビット数（バイト数）で分割しなければならない。例えば、 の下限を  とした場合、平文は  ビットごとに分割する。こうすることで  の条件が常に満たされる。
一方で、出力となる暗号文は  から () の範囲の整数になるため、先の例で（ の下限より小さいビット数）ビット毎に分割された  に対応する暗号文の中には、ビットが必要となるものがある。つまり、平文をビット単位で分割する場合には暗号化によってメッセージサイズが増加するといえる。これを回避するにはビット単位で分割するのではなく、平文  を  進数表示したときの各桁毎に分割すればよい。

RSA-129

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