RSAと安全性

RSA暗号とは何か

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

アルゴリズム

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

暗号化と復号

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

何というこの単純さ。

電子署名

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

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

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

鍵ペア作成の流れ

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

1.Nを作る

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

2.Lを作る

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

• 先ほどの$p$,$q$の最小公倍数$lcm(p-1,q-1)$を$L$とする

3.Eを作る

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

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

4.Dを作る

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

安全性

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

離散対数問題

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

$$7^x \bmod 13 = 8$$

この$x$を求める計算を離散対数と言います。現在のコンピュータの性能でこの離散対数を現実的な時間で解く方法は見つかっていません。この困難性を離散対数問題と言います。

RSA暗号を攻撃しようと思った時、攻撃者がもっている情報は通信を盗聴して得た暗号文と、誰でも見れる公開鍵$(E,N)$です。攻撃者はこの3つの情報から平文を求めようとしますが、

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

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

素因数分解

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

まず、鍵ペア作成の節で説明した通り、$D$は以下の2つの条件を満たす値です。

$$1 < D < L\\ E \times D \bmod L = 1$$

ここで$E$はすでに分かっています。$L$が判明すれば$D$が取り得る値の可能性は狭くなり、おそらくブルートフォースの射程圏内に入るでしょう。そして$L$は$lcm(p-1, q-1)$であるため、$p$と$q$を求められれば良いことになります。ここで攻撃者は$E$が$p \times q$だったことに気がつきます。こんな簡単な掛け算くらいであれば求められそうですね。

しかしこれができないのです。$p$と$q$はどちらも素数です。かつ非常に大きな値です。$E$単体からこの二つを求めるのは素因数分解であり、現代のマシンパワーで309桁×309桁の素因数分解をすることは不可能です。よってここで攻撃者は挫折し、安全性は保たれるのです。

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