暗号化の技術
素因数分解を活用したRSA暗号
プログラミングなどに携わっている人は、「RSA暗号」という言葉を聞いたことがある人は多いかと思います。
公開鍵と秘密鍵を用意して暗号化するアレです。サーバ認証とかいろいろなところで使われています。
仕組みはいたって簡単で、素因数分解が元になっています。
素因数分解
素数はご存じのとおり、1と自分以外に約数を持たない数のこと。2、3、5、7、11、13、17…と無限に存在します(らしい)。
そして素因数分解というのは、ある数字を「素数の掛け算に分解する」ことです。たとえば6なら
6 = 2 × 3に素因数分解できます。一見簡単そうな計算なのですが、素数というのは桁が大きくなるほどに判別がとても難しくなります。
556974を素因数分解をしてみます。 基本的には小さい素数から割れるだけ割っていく方法をとるしかないです。とにかく素数で割ってみるしかないという総当たり戦になります。
- 556974 / 2 = 278487
- 278487 / 2 割り切れない
- 278487 / 3 = 92829
- 92829 / 3 = 30943
- 30943 / 3 割り切れない
- 30943 / 5 割り切れない
- 30943 / 7 割り切れない
- 30943 / 11 = 2813
- 2813 / 11 割り切れない
- 2813 / 13 割り切れない
- 2813 / 17 割り切れない
- 2813 / 19 割り切れない
- 2813 / 23 割り切れない
- 2813 / 29 = 97
- 97 / 29 割り切れない
- …
- …
- 97 / 97 = 1
556974を素因数分解すると 2 * 3 * 3 * 11 * 29 *97になることがわかりましました。このくらいなら何とか手動でも計算できそうですが、一桁増えることに難易度がグンとあがることがわかっていただけるかと思います。
もちろんパソコンなら人間よりもっと多くの桁数を素因数分解できるはずです。しかし、RSA暗号で使用される数字の桁数は300桁～1000桁ぐらいになります。
300桁と簡単に言いますが、大きい数であろう1兆でも13桁なので、300桁はとんでもないくらいの大きな数字であることは間違いないです。１兆の１兆倍を二十回以上繰り返して到達する領域です。
この桁数を素因数分解するのは並大抵の労力ではないです。
さっき556974を素因数分解したときのように、この計算は試行回数が桁数によって飛躍的に増えます。また掛ける数字が素数であるかどうかの認定が難しいです。小さい数であれば素数であること既知だけど、大きい数字なるとそれが素数なのかどうかの判定までしないといけません。
という訳で300桁の数字を素因数分解するには、コンピューターをもってしても、それこそ五劫の擦り切れぐらいの時間が必要となるのです。
こういった性質が解読が困難という訳で暗号に用いられるようになったのです。
実際どうやって暗号が作られているのか
暗号文の生成には素因数分解のほかにmodular arithmetic(モジュラー算術)を使う。これは剰余のことです。エクセルなんかでも余りを求めるときmod関数があったと思います。そのmodのことです。
暗号は以下の式で作られ、復号されます。
暗号文 = 情報のX乗 mod N元の情報 = 暗号文のy乗 mod N
つまり公開鍵はxとNの組み合わせ、秘密鍵はyとNの組わせということになります。
暗号化したい情報は「150」と仮定します。
Nはこれまで説明してきた素因数分解される数字です。Nは素数A×素数Bであらわすことができます。AとBは本来、百数十桁以上なのですが、ここでは説明の為に小さい数字、13と17にします。つまりNは221になります。
次にNを求めます。 Nは求めるのに手順があります。まず素数A素数Bから1を引くとA=12とB=16になります。この数字の最小公倍数を求めると48になります。 Nは「1 < N < 48 」かつ「Nと48の最大公約数が1」を満たす数字である必要があります。
この場合であれば、5、7、11、13、19、23、29、31、37、41、43が候補にあがります。今回は5としてみます。これで暗号化するための道具がそろいましました。150を暗号化すると以下のようになります。
63 = 150＾5 mod 221「150」が「63」になりました。暗号化されたわけです。
こんどは復号です。
150 = 63^y mod 221が成り立つようにしなくてはいけません。yは 「1 < y < 48 」かつ「5 × y mod 48 = 1」満たす必要があります。計算してみると29だということがわかります。( 5 × 29 mod 48 = 1 = 145 mod 48 = 1 )なので、yは29です。
150 = 63^29 mod 221これで復号ができましました。
まとめ
もともと１９６０代後半には理論が存在していたのだそうですが、暗号という性質上またコンピューターの性能がこの暗号を使うまでに至っていませんでしました。理由で秘匿されていたようです。しかし、1970年代になってこの理論を聞いたある研究者が、わずか３０分程度で素因数分解とmodを使ったアイデアで具体案を示したというから驚きです。
このRSA暗号も万能ではなく、解読されてしまう可能性はあります。計算するのではなく、比べることで解読する攻撃方法があるのだそうです。暗号化は誰でもできるし、同じ公開鍵で暗号化すれば、同じ情報は同じ暗号になります。そうするといくつか暗号を作って照らし合わせれば、推測することが出来なくはないということだそうです。
今ではコンピューターも進化して桁数によっては解読できうるRSA暗号の種類もありますが、やはり桁数が大きくなるとスーパーコンピューターをもってしても解読は困難なようです。
