RSA暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』

RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。暗号(Cipher)とデジタル署名(Digital signature)を実現できる方式として最初に公開されたものである。

[編集] 概要

1977年に発明され、発明者であるロナルド・リベスト(Ron Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Len Adleman) の頭文字をつなげてこのように呼ばれる。当時、デフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。

RSA暗号は次のような方式である：鍵ペア（公開鍵と秘密鍵）を作成して公開鍵を公開する。適当な正整数 e（通常は小さな数。65537が良く使われる）を選択し、また大きな桁数の素数2個{p,q}を生成し、それらを暗号文の復号に使用する鍵(秘密鍵)に使用する。次に、生成した2つの素数の積 n を求めて、{e, n}を平文の暗号化に使用する鍵(公開鍵)として公開する。

平文mから暗号文cを作成する： $c = m e (mod n)$
暗号文cから元の平文mを得る： $m = c 1 / e (mod (p - 1)(q - 1)) (mod p q)$

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

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

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

[編集] 暗号方式

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

[編集] 鍵生成

k をセキュリティパラメタとする。

p, q を k/2 ビットの素数とし、n = pq とする。e を φ(n) 未満の正の整数で、φ(n) と互いに素な数とし、d を、φ(n) を法としたe の逆数（ de ≡ 1 ( mod φ(n) ) ）とする。ただしここで φ(n) は n のオイラー関数で、この場合は (p - 1)(q - 1) に等しい。d は、e, φ(n) が既知のときには拡張されたユークリッドの互除法を使えば容易に求まる（ de を φ(n) で割った整数商を x とした場合、de + (-x)φ(n) = 1が成り立つのでこれを解けば良い）。p, q, d を秘密鍵とし、n, e を公開鍵とする。

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

[編集] 暗号化

a を平文空間 ${\Bbb Z}_n$ の元とする。b = a^e mod n （n を法とする剰余）を計算し、b を出力する。

[編集] 復号

b を暗号文とする。a’ = b^d mod n を計算し、a’ を出力する。ここで a = a’ となり復号できる。

[編集] 完全性の証明

以下に証明を示す。ここで a’ は、a^e にさらに d を乗したものの n を法とする余剰で、de ≡ 1 ( mod φ(n))であるから、

a’ ≡ a^(de) (mod n) ≡ a^{( x * φ(n) + 1)} (mod n)

ここでオイラーの定理により、n と互いに素な整数 a については a^φ(n) ≡ 1 (mod n) であるため、

a’ ≡ 1^x * a¹ ≡ a (mod n)

となる。GCD(n,a) = p である整数 a については, a=p*i=aq+q*j, 0<i<q, 0<=j<p として

a’ ≡ 0 (mod p)
a’ ≡ a ≡ aq (mod q)

となるから中国の剰余定理により、p*xp=1+q*xq として

a’ ≡ 0*q*xq + aq*p*xp ≡ (p*i-q*j)*p*xp ≡ p*i*p*xp ≡ p*i*(1+q*xq) ≡ p*i + p*i*q*xq ≡ p*i ≡ a (mod n)

となる（GCD(n,a) = q である整数についても同様）。ここで、 a’ も a も n を法とした余剰なので、

a’ = a

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

[編集] 性能

[編集] n を法とするべき剰余の計算

k=1024の場合、n は1024ビットサイズという大きな数となり、d もほぼ n と同サイズの数となる。 a = b^d mod n を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算（1024bit × 1024bit）を、1500回程繰り返すことで実現できる。これには相当の計算時間を要するため、中国の剰余定理を用いて、

ap = b^{d mod φ(p)} mod p, aq = b^{d mod φ(q)} mod q, a’ = ap (1/q mod p) q + aq (1/p mod q) p

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

[編集] 素数生成

桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller-Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数（probable prime）という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる。

(なお、拡張リーマン予想が正しければ、Miller-Rabinテストは素数かどうかを正しく判定する、という事実が知られている)。

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

[編集] 安全性

[編集] RSA暗号と素因数分解問題の関係

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

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

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

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

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

RSA問題や素因数分解問題はNP問題であるので、これらの問題が(deterministicな)多項式時間では解けないことが証明できれば、P≠NP予想が肯定的に解決することになる。

[編集] 素因数分解可能な範囲

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

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

[編集] RSA Challenge 解読コンテスト結果

RSA社は「RSA Challenge 解読コンテスト」を行って、現在のコンピュータを使うとどの程度のビット数の整数なら素因数分解問題が解けるのかを調べている。

1991.04.01 RSA-100 (330ビット)
1992.04.14 RSA-110 (364ビット)
1993.06.09 RSA-120 (397ビット)
1994.04 RSA-129 (426ビット)
1996.04.10 RSA-130 (430ビット)
1999.02.02 RSA-140 (463ビット)
2004 RSA-150 (496ビット)
1999.08.22 RSA-155 (512ビット)
2003.04.01 RSA-160 (530ビット)
yet RSA-170 (563ビット)
2003.12.03 RSA-576 (576ビット,10進174桁）
yet RSA-180 (596ビット)
yet RSA-190 (629ビット)
2005.11.02 RSA-640 (640ビット)
2005.05.09 RSA-200 (663ビット,10進200桁)

以下は未踏

RSA-210
RSA-704
RSA-768
RSA-896
RSA-1024
RSA-1536
RSA-2048

[編集] RSA暗号の性質

RSA暗号は選択暗号文攻撃を行なえば完全解読できる。また、RSA暗号は選択平文攻撃に対してすらindistinguishableではない。よってRSA暗号は選択平文攻撃に対してnon-malleableでもsemantic secureでもない。

[編集] RSA暗号の誤用

[編集] パラメータの選択

Strong Prime (stub)

[編集] 特殊な(誤った)応用

共通の法n

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

同報通信

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

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

(stub)

[編集] 脆弱な平文

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

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

[編集] 決まりきった平文

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

実際の暗号への応用においてはフォーマットとしてmの一部に毎回生成する乱数を挿入することでこの攻撃を回避している。

[編集] 小さなm

もしも平文mが、nのe乗根よりも小さかったら、暗号文 $c = m e m o d n = m e$ となるから、通常の冪根演算によってcのe乗根を計算するだけで平文mが復元できてしまう。

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

[編集] 同一平文

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

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

$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}$

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

$c \equiv m^e \pmod{ n_1 \cdot n_2 \cdot n_3 \ldots n_e }$

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

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の場合には、結果として出力されるのは、m mod nに対応する暗号文であり、復号してもmは出力されないためである。

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

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

[編集] 暗号や署名への応用

[編集] RSA暗号

暗号方式のままの方式（生RSA、教科書的RSAということがある）では、

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

などの好ましくない性質があるため、実際に暗号として使用する際には、パディングなどのフォーマットを定義し、平文空間を限定することが必要である。パディングも含めたものとして、

RSA_PKCS
RSA_OAEP

などがある。

[編集] RSA署名

公開鍵と秘密鍵の役割は通常の場合においては上述の通り、公開鍵は暗号文を生成するのに使われ、秘密鍵は生成された暗号文を平文に戻すために用いられるが、暗号の方式によってはこの限りではない。 RSA暗号方式においてはそのアルゴリズムの構造上、公開鍵と秘密鍵の役割をそっくり入れ替えることが可能である。

つまり秘密鍵を用いて、任意のデータを復号して平文を作成し、公開鍵を用いて、その平文を、元のデータに戻すことができるのである。

この場合、基本的に誰もが平文を元のデータに戻すことができるが、その平文を生成することができるのは秘密鍵を持つもの（恐らくただ一人の個人または法人）だけである。一見なんの有用性もないように感じられるが、実はこれがRSA署名の原理である。

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

RSA_PSS with SHA-1