暗号を行う上で問題となるのは、
どうやって暗号の鍵を他者に知られることなく、
相手と自分の間で共有するかです。
鍵さえ共有できてしまえば、
安全に文章のやり取りができますが、
そもそも鍵をどうやって安全に届けるかが問題です。
鍵も文章も安全に届けなければいけないのですが、
よく考えてみると、それぞれ性質が異なっています。
文章は、送る側の情報を途中では違う形に暗号化して、
相手には、送る側が書いた通りの情報に戻すことが必要です。
ところが、鍵については、送る側の狙った通りの情報になる必要はなく、
結果的に、送る側と受け取る側で同じ情報を共有すればいいのです。
このような違いがあることから、鍵の共有に要求されていることは、
実は文章の暗号化通信よりも緩いことが分かります。
この記事では、楕円曲線暗号を使った、
鍵の共有の仕組みについてまとめます。
鍵共有の見通し
鍵を共有するとは、
AさんとBさんの間で、
同じ数字列（文字列）を持つことです。
とはいえ、そのままその数字列をインターネットに流しては、
関係ない人まで鍵を持ってしまうので、
何か違う情報を流さないといけません。
もちろん、全く関係ない情報を流しても意味がないので、
鍵のヒントになるような情報を流すことになります。
目標としては、
二人のヒントのやり取りすることで、
同じ鍵を作りだすことができ、
一方、他の人は二人のヒントを見ても、
同じ鍵にたどり着かないことになります。
こんな方法はあるのでしょうか？
やるべきことを整理してみましょう。
AさんはAさんにしかできないことがあって、
Bさんから受け取った情報を使って、
を作ります。
BさんはBさんにしかできないことがあって、
Aさんから受け取った情報を使って、
を作ります。
もし、この作ったものが同じであれば、つまり、
であれば、これが、共有された鍵となります。
これが、鍵共有ですべきことです。
交換可能性を利用する
を目指せばいいことはわかりましたが、
まだ、具体的にどうすれば良いかが見えてきません。
別々の情報に別々の操作を加えているのに、
それが一致するなんてことがあるでしょうか？
交換する情報にちょっとした細工をすることを考えると、
より見通しが良くなります。
それは、次のような細工です。
- 交換する情報自体に共通の要素を持たせる
- 交換する情報自体に自分が後で行う操作を加えておく
つまり、共有の情報に対して、
Aさんはを、Bさんは
の処理を行って、
と
を交換するのです。
こうすることで、鍵を共有する条件は、
となり、 と
が交換可能であればよいことになります。
ただし、交換する情報に自分だけができる処理を加えているので、
処理後の情報を見た人が、どんな処理を行ったかを推測できないように注意しなければいけません。
まとめると、鍵交換では、
- Aさん、Bさんが行う処理
が交換可能であること
の二つが重要となってきます。
楕円曲線暗号
鍵の共有に、上の二つの性質が必要とわかったところで、
いよいよ、楕円曲線の登場です。
楕円曲線暗号での楕円曲線は、
交換する情報の舞台となります。
つまり、楕円曲線上の点の位置がとなります。
そして、楕円曲線上の点を別の点に移す操作が
です。
それでは楕円曲線上の操作がどのようなものか、
それが交換可能であること、
結果から処理内容が推測困難であることを見ていきましょう。
楕円曲線とは
楕円曲線とは、楕円という名前がついていますが、 一般的には下の図のような形をしています。
楕円形をしているわけではありませんが、
曲線には違いありません。
この曲線上の点が、楕円暗号で交換される
になります。
楕円曲線上の点の足し算
楕円暗号で用いる操作では、
直接、点と点の足し算をすることはありませんが、
その操作とも関係があるので、
足し算を先に見ておきましょう。
楕円曲線上の二点について、
次のようにして、点同士の足し算が定義されます。
機械的な手続きですが、そんなに難しい処理ではありません。
楕円曲線上での倍数
こちらが楕円曲線暗号で行う処理に当たり、
の中身になってきます。
先ほど、足し算を定義しましたが、同じ点を足す、
つまり2倍するをどのように定義すれば良いでしょうか？
点が一つだと直線が一つに定まりませんが、
上の図でQが限りなくPに近づいた様子を想像すると、
Pを通る接線を引けばよさそうですね。
実際、楕円曲線上での2倍は、次のように定義されます。
3倍については、2P+P、
4倍については、3P+Pと計算していくことができます。
楕円曲線暗号では、
この何倍するかをAさんとBさんがそれぞれ自分だけで決めておき、
それを、自分だけができる処理とします。
交換可能性
鍵の交換のために、の交換可能性
を満たす必要がありました。
今の場合、楕円曲線上の点Pを倍した後に、
倍するのと、
倍した後に、
倍するのが同じ点にくれば良いのですが、
これは、点の足し算が交換可能であることからただちに分かります。
点の足し算では、両方の点を通る直線を引いて点を決めるので、
足し算の順番は結果に関係しないことは明らかです。
このように、楕円曲線上で点を倍数で移す処理は、
交換可能であることが分かります。
処理内容は推測困難か？
また、鍵交換においては、の処理を行った結果を見て、
どの処理が行われたかを推測できないことが重要でした。
今の場合、共有された最初の点を
倍して点を移した時に、
その結果移った点を見て、
何倍したかが推測できるかが問題となります。
これは楕円曲線上での離散対数問題と呼ばれますが、
効率の良い計算方法が見つかっておらず、
計算に時間がかかる問題とされています。
この計算のむずかしさが、楕円曲線暗号の安全性を担保しています。
全体の流れ
改めて、全体の流れを整理しましょう。
楕円曲線暗号では、鍵の交換前に、
舞台となる楕円曲線を知らせておきます。
そして、AさんとBさんは、それぞれ、誰にも内緒で、
自分の操作を決めます。
そして、自分の操作を加えた情報を交換します。
最後に、受け取った情報に自分の処理をかければ共有鍵の完成です。
- 準備：楕円曲線と最初の点Gの位置を公開する
- 操作の決定: A,Bはそれぞれ
- 情報の交換: A,B は自分の処理をかけた
を交換する
- 共有鍵の完成: A,B は受け取った情報に自分の処理を施し、それを鍵とする
