少し前から暗号に興味を持ち始めました。少しだけ。
その中でもわりと有名な公開鍵暗号というものを実装してみたいと思います。

実装例としてはsslやsshですかね。
通信を暗号化するための鍵を、安全に共有するために公開鍵暗号が使われています。

どういうものなのか調べてみて簡単なような難しいような、でも仕組みが少し面白かったのでアウトプットもかねてここに残しておこうと思います。

実装もしたいと思いますが、そこそこ長くなりそうなので実装は別の記事に書こうと思います。

公開鍵暗号とは

暗号化と復号化に別々の鍵を使用する暗号化方式です。
対になる？暗号化方式として共有鍵暗号というものがあり、こちらは暗号化と復号化に同じ鍵を使用します。
それで公開鍵暗号は共有鍵暗号を行うために使われていたりします。
共有鍵暗号で人々が通信を行う際にメッセージを暗号化したい場合、その暗号化に使う鍵（共有鍵）を事前に共有しておく必要があります。
ただ鍵を共有する際に盗聴でもされたらメッセージを秘匿できなくなってしまいます。
そこで公開鍵暗号を使用します。

流れをアリスとボブで説明しますと

1　アリスが公開鍵をボブに渡す。
2　ボブはもらった公開鍵でメッセージを暗号化し、アリスに送る。
3　アリスは受け取ったメッセージを秘密鍵で復号化する。

1の時点で公開鍵をボブに渡していますがこの際に盗聴されていても問題はありません。
公開鍵があったところでメッセージの復号化はできないからです。
公開鍵によって暗号化されたメッセージを復号化できるのはその公開鍵と対になる秘密鍵だけなのです。

公開鍵と秘密鍵をつくる

公開鍵と秘密鍵が数学的な関係があるようです。
なので滅茶苦茶な組み合わせでは公開鍵暗号は機能しません。
そこそこ面倒な計算をする必要があります。

1　大きな素数pとqを求める
2　p*q=Nとする
3　ｐ-1とq-1の最大公約数を求めめこれをLとする
4　3で作ったLとの最小公倍数が、1となり、かつ1<E<LとなるようなEをもとめる
5　1<D<Lとなり、かつE*D mod L = 1となるようなDを求める
6　EとNを公開鍵、DとNを秘密鍵とする

暗号化と復号化のアルゴリズム

意外とこれが簡単です。

暗号化
　平文をE乗し、Nであまりをとる
復号化
　暗号文をD乗し、Nであまりをとる

単なる冪剰余計算ですね

最後に

説明だけ見ると仕組み自体は簡単に思えますが、
実装がそこそこ手間がかかるためここでは簡単にまとめるだけにしておきたいと思います。

それにしても他にいろいろ暗号化方式があるようですが、どうやら素数というものが暗躍しているようです。
この辺りも理解できればいいんですが