RSA暗号
RSA暗号(RSAあんごう)とは、桁数が大きい合成数の素因数分解が現実的な時間内で困難であることを安全性の根拠とした公開鍵暗号の一つである。
暗号とデジタル署名を実現できる方式として最初に公開されたものである。
RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。前年(1976年)にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている。
RSA暗号は次のような方式である。
鍵のペア(公開鍵と秘密鍵)を作成して公開鍵を公開する。まず、適当な\phi と互いに素な正整数 e を選択する。また、大きな2つの素数の組 \{p, q\} を生成し、それらの積 n\ (=pq) を求めて、組 \{e, n\} を平文の暗号化に使用する鍵(公開鍵)とする。2つの素数 \{p, q\} は秘密に保管し、暗号文の復号に使用する鍵(秘密鍵) d の生成にも使用する (d = e^{-1} \; \operatorname{mod}\; \phi 、ここで \phi = \operatorname{lcm}{(p-1,\ q-1)})。式中の "\operatorname{mod}" は剰余演算を表し、d は \phi を法とする e のモジュラ逆数である。\operatorname{lcm}{(p-1,\ q-1)} は、p-1 と q-1 の最小公倍数である。
暗号化(平文 m から暗号文 c を作成する): c = m^e \; \operatorname{mod}\; n
復号(暗号文 c から元の平文 m を得る):  m = c^d \; \operatorname{mod}\; n
暗号化(e 乗)は公開鍵 \{e, n\} があれば容易に計算でき、復号(d 乗)は秘密鍵 d と公開鍵 n があれば容易に計算できる。しかし、秘密鍵 d を知らずに解読する(法 n の下で e 乗根を計算する)のは、「n の素因数を知らないと難しい(大きい合成数の素因数分解も難しい)」と考えられている。つまり、「秘密鍵を用いずに暗号文から平文を得ることは難しい」と信じられている。これがRSA暗号の安全性の根拠である。
RSA暗号のアルゴリズムは、1983年9月20日にアメリカ合衆国で特許(4,405,829号)を取得し、RSA Security 社がライセンスを独占していたが、特許期間満了に伴って2000年9月6日からは誰でも自由に使用できるようになった。
暗号の用語については、暗号の用語、暗号理論の用語を参照。
歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者はジェイムズ・エリスである。彼らはイギリス最高機密機関・英国政府通信本部 (GCHQ) の職員であり、その独創的な先見の明は内部文書として長い間公開されなかった。また実用にはコンピュータの性能等から機が熟していなかった。以下はその概要である。
エリスは1969年にこの理論を発見しているが、専門の数学者ではなかったため、具体的な方法を発見できなかった。幾人ものGCHQの優秀な数学者が挑戦したが、具体的な方法を提示する事はできなかった。1973年、突拍子もない暗号のアイデアとしてエリスの「一方向関数(非対称性鍵の概念)・公開鍵」を用いた暗号論の話を聞かされ、わずか30分程度でモジュラー算術と素因数を用いた具体的な方法を考案したのは、GCHQ所属の若き数学者クリフォード・コックスである(コックスは上記のリベストの計算式と同じものを発見した)。しかしエリスとコックスの業績は機密事項とされたため、1997年までは世に知られることはなかった。
鍵生成、暗号化、復号の3つのアルゴリズムで定義される。
p , q を異なる2つの素数とし n = p \cdot q とする。 \phi をオイラー関数とすると \phi(n) = (p-1) \cdot (q-1) となる。 e を \phi(n) と素な正整数とすると \alpha \cdot e + \beta \cdot \phi(n) = 1 となる2整数 \alpha , \beta が存在する 。 \alpha として1つの正整数 d を選択してそのときの \beta を -x とすると d \cdot e = x \cdot \phi(n) + 1 となる。ここで d を秘密鍵とし、 n , e を公開鍵とする。
以下 {\Bbb Z}_n を 0 以上 n 未満の整数の集合とする。
ここで、 \alpha \cdot e + \beta \cdot \phi(n) = 1 のとき iを整数とすると (\alpha + i \cdot \phi(n)) \cdot e + (\beta - i \cdot e) \cdot \phi(n) = 1 であるから \alpha に \phi(n) の整数倍を加えたものもあらためて \alpha とできるため、 \alpha として正整数 d を選択できるとした。
a \in {\Bbb Z}_n とし a を暗号化対象の平文とする。b \in \{z \in  {\Bbb Z}_n|z \equiv a^e\pmod{n} \} を計算し、b を 平文 a の暗号文とする。
a^\prime \in \{z \in  {\Bbb Z}_n|z \equiv b^d\pmod{n} \} を計算する。すると a^\prime = a となり
a^\prime は 平文 a の暗号文 b の復号文となる。
定義により以下が成立する。
a^\prime \equiv a^{(d \cdot e)} \pmod{n} = a^{(x\cdot\phi(n)+1)} = (a^{\phi(n)})^x \cdot a
これにより以下も成立する。
\begin{align}
a^\prime \equiv (a^{\phi(n)})^x \cdot a \pmod{p} \\
a^\prime \equiv (a^{\phi(n)})^x \cdot a \pmod{q} \\
\end{align}
a が n と互いに素な整数のときは a が2つの素数 p,q のそれぞれと互いに素であるから
フェルマーの小定理 により a^{p-1} \equiv 1 \pmod{p} かつ a^{q-1} \equiv 1 \pmod{q} であり
\begin{align}
a^{\phi(n)} = (a^{p-1})^{q-1} \equiv 1^{(q-1)} \pmod{p} = 1 \\
a^{\phi(n)} = (a^{q-1})^{p-1} \equiv 1^{(p-1)} \pmod{q} = 1 \\
\end{align}
よって (a^{\phi(n)}-1) は p,q で割り切れるから a^{\phi(n)} \equiv 1 \pmod{n} となり
a^\prime \equiv (a^{\phi(n)})^x \cdot a \pmod{n} \equiv 1^x \cdot a \pmod{n} = a
となるが、 a,a^\prime \in {\Bbb Z}_n であるから
\begin{align}
a^\prime = a
\end{align}
となる。
\mathrm{gcd}(n,a) = p であり a \in {\Bbb Z}_n - \{0\} のときは
a は q-1 個の整数からなる 集合 \{1 \cdot p,2 \cdot p,3 \cdot p,...,(q-1) \cdot p\} の元であって、
a が p で割り切れるから a \equiv 0 \pmod{p} であり、
a と q が素であるから フェルマーの小定理 により a^{q-1} \equiv 1 \pmod{q} であり
\begin{align}
a^{\phi(n)} = (a^{q-1})^{p-1} \equiv 1^{(p-1)} \pmod{q} = 1
\end{align}
\begin{align}
a^\prime \equiv (a^{\phi(n)})^x \cdot a \pmod{p} \equiv (a^{\phi(n)})^x \cdot 0 \pmod{p} = 0 \\
a^\prime \equiv (a^{\phi(n)})^x \cdot a \pmod{q} \equiv 1^x \cdot a \pmod{q} = a \\
\end{align}
\begin{align}
a^\prime \equiv 0 \pmod{p} \equiv a \pmod{p} \\
a^\prime \equiv a \pmod{q} \\
\end{align}
よって (a^\prime-a) は p,q で割り切れるから
\begin{align}
a^\prime \equiv a \pmod{n} \\
\end{align}
となるが、 a,a^\prime \in {\Bbb Z}_n であるから
\begin{align}
a^\prime = a
\end{align}
となる。
\mathrm{gcd}(n,a) = q であり a \in {\Bbb Z}_n - \{0\} のときについても同様に a^\prime = a となる。
a = 0  のときは b \in \{z \in  {\Bbb Z}_n|z \equiv 0^e\pmod{n} \}=\{0\} であるから b=0 であり
a^\prime \in \{z \in  {\Bbb Z}_n|z \equiv 0^d\pmod{n} \}=\{0\} であるから a^\prime=0  である。つまり a^\prime=a=0  である。
以上何れにしても a^\prime = a が成り立ち
平文 a の 暗号文 b は 秘密鍵 d と 公開鍵の1つ n を用いて 平文 a に復号できることが分かる。
k = 1024 の場合、n は1024ビットサイズという大きな数となり、d もほぼ n と同サイズの数となる。
a = b^d \bmod n を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算 (1024\mathrm {bit} \times 1024\mathrm{bit}) を、1500回程繰り返すことで実現できる。
これには相当の計算時間を要するため、中国の剰余定理を用いて、
\begin{align}
ap &= b^{d \bmod \phi(p)} \bmod p \\
aq &= b^{d \bmod \phi(q)} \bmod q \\
a^\prime &= ap (q^{-1} \bmod p) q + aq (p^{-1} \bmod q) p
\end{align}
として求めることがある。
桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成は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桁程度)にすることが推奨されている。
しかしShamirは、RSA問題を解くための専用装置 (TWIRL) を作成すれば、1024ビットの n に関するRSA問題ですら解くことができると主張している。
また、実用的な量子コンピュータが登場した場合には、素因数分解の桁数増に対する計算時間の増加が緩やかなショアのアルゴリズムと呼ばれる高速な量子コンピュータアルゴリズムが実行可能となるため、たとえ鍵のビット数を増やしてもRSA暗号の安全性が保証されなくなる可能性が指摘されている。
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 乗根よりも小さかったら、暗号文 c = m^e \; \operatorname{mod}\; n = m^e となるから、通常の冪根演算によって c の e 乗根を計算するだけで平文 m が復元できてしまう。
実際の暗号への応用においてはフォーマットの一部として、m の比較的高位のビットに1を挿入することでこの攻撃を回避している。
法 n における e 乗根が計算できれば、暗号文を復号できる。
当然これは(法 n の素因数がわからない限り)非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。
しかし、まったく同一の平文を、異なる法において同一の e を用いて暗号化した暗号文を e 個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これが同報通信の誤用である。
\begin{align}
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{align}
ここから中国の剰余定理によって上記式を満たす、
c \equiv m^e \pmod{ n_1 n_2 n_3 \dots n_e }
を求めることができる。このとき c < n_1 n_2 n_3 \dots n_e であり、また m はどの法 n よりも小さいため m^e < n_1 n_2 n_3 \dots 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 \bmod n に対応する暗号文であり、復号しても m は出力されないためである。
平文をビット単位(やバイト単位)で分割する際には、まず、n の下限を定めたうえで、平文の全ビットを 1 に(全バイトを \mathrm{FF_{16} に)しても n より小さくなるビット数(バイト数)で分割しなければならない。例えば、n の下限を 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は、公開鍵暗号における最も高い安全性である「適応的選択暗号文攻撃に対する識別不可能性」を持つことが示されている。
RSA暗号が実現した公開鍵暗号方式は、従来の暗号方式(共通鍵暗号)とは異なり、暗号化は公開鍵を使って誰でもできるが、復号は秘密鍵を持つ本人だけしかできない方式である。この復号は「本人だけしかできない」という性質を利用すると、デジタル署名(あるいは認証機能)が実現できる。
そのためには、公開鍵・秘密鍵を次のように使用する。
平文 → 公開鍵(暗号化)→ 暗号文、暗号文→ 秘密鍵(復号)→ 平文
文書 → 秘密鍵(署名生成)→ 署名値、署名値→ 公開鍵(署名検証)→ 文書
公開鍵と秘密鍵の役割は通常の場合においては上記の通り、公開鍵は暗号化に使われ、秘密鍵は復号に用いられるが、RSA暗号においては平文と暗号文の定義域が同じ(平文空間=暗号文空間である)ため、任意の文書(メッセージ)を暗号文とみなして復号することができる。つまり秘密鍵を用いて任意の文書について署名値を生成でき、公開鍵を用いてその署名値を暗号化して元の文書と一致するかを調べることで署名の検証ができる。
ただし、RSA暗号と同様に、生RSAでは、署名の潜在的偽造等の好ましくない性質があるため、パディングなどが必要である。また、暗号文空間よりも大きなメッセージを扱うためにハッシュ関数と組み合わせて使用する。
このようなパディングなども含めたものとして、
RSA_PSS with SHA-1
などがある。
1977年、マーティン・ガードナーがコラムを連載していたサイエンティフィック・アメリカン誌に129桁の合成数 n と公開鍵 e=9007 を使ったRSA方式で暗号化されたメッセージを掲載した。解読が成功した者にマサチューセッツ工科大学から100米ドルを与えるという懸賞金問題だった。当時、解読には2万年は必要だろうと予測されていた。掲載から16年後に、オックスフォード大ポール・レイランド、アイオワ州立大マイケル・グラフ、マサチューセッツ工科大学デレク・アトキンス、アリエン・レンストラらが、インターネット上で(南極大陸を除くすべての大陸から20か国以上の)約600名のボランティアの協力を得て、二次ふるい法によってRSA-129に対する大規模攻撃を開始した。8か月で800万以上の下位問題が解かれ、得られた50万行50万列以上の疎行列から188614行188160列の行列による連立方程式を作った。これをスーパーコンピュータMP-1で45時間をかけて構造的ガウスの消去法によって解き、解読に成功した(1994年4月)。答えは“The magic words are squeamish ossifrage" [ossifrage(ヒゲワシ)はジョークで「骨折り」の意] 。
RSA暗号をサポートしているライブラリは以下の通り。