All Articles

RSAと安全性

RSA暗号とは何か

公開鍵暗号の最初のアルゴリズムであり、2000年に特許期間が満了し誰でも使えるようになった暗号アルゴリズムです。特徴としては暗号化と復号のアルゴリズムが同じかつ非常に単純という点が挙げられます。 RSA暗号そのものについての歴史とか概要は数多の記事があるのでそちらを見てもろて。一次情報が欲しい方はRonald Rivest, Adi Shamir, Leonard Adlemanによる論文をご覧ください。

アルゴリズム

前提条件として、公開鍵を(E,N)(E,N)、秘密鍵をDDとします。

暗号化と復号

暗号文=平文EmodN平文=暗号文DmodN\text{暗号文} = \text{平文} ^ E \bmod N\\ \text{平文} = \text{暗号文} ^ D \bmod N

何というこの単純さ。

電子署名

署名=平文DmodN平文=署名EmodN\text{署名} = \text{平文} ^ D \bmod N\\ \text{平文} = \text{署名} ^ E \bmod N

署名の場合は、ただ秘密鍵で暗号化(署名)し、公開鍵で復号(検証)するだけです。

至ってシンプルなのですが、このRSA暗号が公開鍵暗号として最初に世に出て有名になったことで「署名アルゴリズムは暗号アルゴリズムの秘密鍵で暗号化して公開鍵で復号するだけだ」という誤解が広がってしまいました。しかし、逆にすれば成立するアルゴリズムはRSAくらいで、他の公開鍵暗号では暗号化と復号で違うアルゴリズムを用いるためそのように一般化するのは間違いです。

鍵ペア作成の流れ

公開鍵ペア(E,N)(E,N)と秘密鍵DDを作る手順を説明します。

1.Nを作る

  • まず大きな素数pp,qqを用意します。通常は1024bits(=309桁)の素数を探します
  • p×qp \times qを計算し、これをNNとします

2.Lを作る

LLは鍵として使われることはありませんが、EEDDを計算する際に必要な値になるので先に計算しておきましょう。

  • 先ほどのpp,qqの最小公倍数lcm(p1,q1)lcm(p-1,q-1)LLとする

3.Eを作る

  • 1<E<L1 < E < Lを満たすEEを擬似乱数生成器で算出します
  • その上でEELL互いに素gcd(E,L)=1gcd(E,L) = 1)だったらEEとします

ここで互いに素を条件とする理由は後の安全性の節で説明します。

4.Dを作る

  • 1<D<L1 < D < Lを満たすDDを擬似乱数生成器で算出します
  • その上でE×DmodL=1E \times D \bmod L = 1を満たした値をDDとします

安全性

RSA暗号は以下2つの計算量的安全性で守られています。

離散対数問題

対数とは、7x=497^x = 49xxを求めることですが、これに余剰の計算がくっついた

7xmod13=87^x \bmod 13 = 8

このxxを求める計算を離散対数と言います。現在のコンピュータの性能でこの離散対数を現実的な時間で解く方法は見つかっていません。この困難性を離散対数問題と言います。
RSA暗号を攻撃しようと思った時、攻撃者がもっている情報は通信を盗聴して得た暗号文と、誰でも見れる公開鍵(E,N)(E,N)です。攻撃者はこの3つの情報から平文を求めようとしますが、

暗号文=平文EmodN\text{暗号文} = \text{平文}^E \bmod N

より、離散対数問題に帰着します。これが一つ目の安全性です。

素因数分解

上記のように、直接平文を求めようとすると離散対数問題に当たってしまうので、今度は秘密鍵DDを求めて暗号文を復号する方法で攻撃を試みます。といってもブルートフォースで当てずっぽうで探していては309桁×309桁なんて当たるわけがありません。そこで攻撃者はDDの式を分解して値を求める方法を探ります。
まず、鍵ペア作成の節で説明した通り、DDは以下の2つの条件を満たす値です。

1<D<LE×DmodL=11 < D < L\\ E \times D \bmod L = 1

ここでEEはすでに分かっています。LLが判明すればDDが取り得る値の可能性は狭くなり、おそらくブルートフォースの射程圏内に入るでしょう。そしてLLlcm(p1,q1)lcm(p-1, q-1)であるため、ppqqを求められれば良いことになります。ここで攻撃者はEEp×qp \times qだったことに気がつきます。こんな簡単な掛け算くらいであれば求められそうですね。
しかしこれができないのです。ppqqはどちらも素数です。かつ非常に大きな値です。EE単体からこの二つを求めるのは素因数分解であり、現代のマシンパワーで309桁×309桁の素因数分解をすることは不可能です。よってここで攻撃者は挫折し、安全性は保たれるのです。

しかしここで注意しておきたいのはRSAが計算量的安全性のみに守られていることです。この先マシンパワーはどんどん向上する、かつ量子コンピュータのように高速な計算ができるマシンが生まれてきます。そうなった時にこの困難性が破られない保証はなく、破られた時の混乱は免れません。RSA暗号を用いたソフトウェアを開発する際は常に暗号界隈に耳を傾け、くれぐれも自作のアルゴリズムなど使わないように心がけましょう。