この記事では、私の備忘録と理解度の確認もかねてRSA暗号について書いていきます。
整数論の知識が必要ですが、素因数分解と合同式を知っていればそれほど難しくはありません。
数式が多く出てくるので、数学が苦手な方は頭が痛くなるかもしれません。
RSA暗号とは
RSA暗号は、桁数の多い数の素因数分解が困難であることを利用したセキュリティー技術です。
10桁程度の数なら電卓でも素因数分解できますが（多少の根気はいる）、これが100桁となるとコンピューターでも難しくなります。
マサチューセッツ工科大学のリベルト、シャーベル、エードルマンの3人が発明し、RSAはそれぞれの名前の頭文字を取っています。
大まかな仕組み
公開鍵を公開する
まず、大きな異なる素数を2つ選び、2つの数の積と指数を公開します。
今回は素数をp,q、指数はrとします。
rはp-1とq-1の最小公倍数より小さく、1より大きい互いに素である数を選びます。
例えば、p=3,q=5の場合、p-1は2、q-1は4なので最小公倍数は4
1<r<4の範囲で4と互いに素（最大公約数が1）なのは3だけなので、3が指数となります。
平文を暗号化
平文とは暗号化する前の文のことで、数値に変換してから暗号化します。
平文をsとして、sのr乗を素数の積pqで割って暗号文tを導きます。
$$s^{r}\equiv t(mod pq)$$
整数論を勉強している方なら知っていると思いますが、上の式は合同式で、tはsのr乗をpqで割った余りです。
暗号文を復号
今度は暗号文を復号するために、秘密鍵uを使って復号します。
uはrとの積ruが(p-1)(q-1)を法として1と合同になるようなる数です。
式で表すと
$$ru\equiv1(mod(p-1)(q-1))$$
を満たす逆元が、復号に使用する秘密鍵になります。
暗号文tをu乗して、平文sを得ます。
$$t^{u}\equiv s(mod pq)$$
文字式だけだとわかりにくと思うので、簡単な例を出してみます。
具体例
- 公開鍵 95(p=5,q=19) r=25
- 秘密鍵 u=13
- 平文 s=17
まず、Aさんが平文17を公開鍵25で暗号化してBさんに送信します。
$$17^{25}\equiv 62(mod95)$$
暗号文62を受け取ったBさんは、公開鍵95と秘密鍵13（求め方は後述）を使って平文を復号します。
$$62^{13}\equiv 17(mod95)$$
今回は簡単な例として小さい数を使用していますが、実際には300桁以上の素数が使われます。
秘密鍵の作成方法
先ほどの例で秘密鍵13を使いましたが、1次合同式とユークリッド互除法で求めてみます。
1次合同式で導く方法
pが5、qが19なので、p-1=4、q-1=18となり、最小公倍数は36
rが25なので、秘密鍵は以下の式を解けば求められます。
$$25u\equiv1(mod36)$$
両辺を3倍して
$$75u\equiv3(mod36)$$
72u≡0(mod36)より、
$$3u\equiv3(mod36)$$
両辺を3で割りたくなりますが、3と36は互いに素ではありません。
そこで、右辺の3を左辺に移行して、
$$3u-3\equiv0(mod36)$$
3でまとめて
$$3(u-1)\equiv0(mod36)$$
つまり、u-1は12の倍数なので
$$u-1\equiv0(mod12)$$
よって、$$u\equiv13$$となります。
ユークリッド互除法を使う方法
1次不定方程式をユークリッド互除法を使って導く方法です。
36で割って1余るので、解くべき1次不定式は整数x、yを用いて
$$25x+36y=1$$
と表せます。
ここでユークリッド互除法を使います。
36=25・1+11
25=11・2+3
11=3・3+2
3=2・1+1
1=3-2・1
=3-(11-3・3)・1
=11・(-1)+3・4
=11・(-1)+(25-11・2)・4
=25・4+11・(-9)
=25・4+(36-25・1)・(-9)
=25・13+36・(-9)
よって、x=13、y=-9が整数解のひとつです。
式の説明をかなり省いているので、わかりにくいかもしれません。
RSA暗号は安全なのか？
前述したように、RSA暗号は桁数の多い数の素因数分解が困難であることを利用しています。
逆に言えば、素因数分解が容易に解ければ、RSA暗号がすぐに解読され、安全性が危ぶまれてしまいます。
ただ、素因数分解のようなNP問題を解く多項式時間アルゴリズムはまだ見つかっていないので、当分は安全とみていいと思います。
ここであまり見慣れない用語が出てきたので、少し解説します。
多項式時間とNP問題
例えば、以下の2つのアルゴリズムを比較してみます。
$${n}^5$$
$${5}^n$$
前者のように、nが大きくなっても計算処理に時間がかからないものを多項式時間、後者はnが大きくなると計算時間が指数関数的に増えていくので指数的時間といいます。
試しにn=10でやってみると、10の5乗が100000、5の10乗が9765625となります。
そして、多項式時間で解ける問題をP問題、解が正しいかどうかを多項式時間で判定できる問題をNP問題といいます。
すべてのPがNPであることはすでに証明されていますが、その逆はまだ証明されていません。
これはクレイ数学研究所が2000年に発表したミレニアム問題の1つで、P=NP（またはP≠MP）問題と呼ばれます。
なぜこんな話をしたかというと、素因数分解はNP問題であり、もしP=NPならば、方法は発見されていないが素因数分解は多項式時間で解けるということになり、RSA暗号が簡単に破られる危険性があります。
現代の数学界では、多くの方がP≠NPだと予想しています。
まとめ
今回の内容は少々専門的でわかりにくかったかもしれませんが、整数論がセキュリティーで活用されているということはわかっていただけたと思います。
P≠NP問題は解けると100万ドル（日本円で約1億）がもらえるので、興味のある方はチャレンジしてみましょう。
RSA暗号について詳しく知りたい方は、整数論や暗号の書籍を購入してみることをおすすめします。
