楕円曲線ディフィー・ヘルマン鍵共有

こんにちは。

以前、楕円曲線を使ったDSA署名についてご紹介しました。

しかしこれはあくまで署名用のプロトコルであり、このECDSA署名に使う鍵を暗号化に使おうとしても、役に立ちません。

それでも、分散型台帳技術・ブロックチェーンにおいては、データを暗号化して渡したい状況があるはずで、それもECDSA署名に使ってきた鍵をそのまま使いたいはずです(いちいち暗号化用の鍵を保管するのは面倒すぎる)。

そこでなんと都合の良いことに、楕円曲線DSAの鍵から、暗号化用の鍵を生成する方法があります。

楕円曲線ディフィーヘルマン鍵共有(ECDH)というものです。

今回はそれをご紹介します。

おさらい

前提知識として、ECDSAの記事を読んでいただく必要がありますが、一応おさらいしておきます。

\(G\)が楕円曲線のベースポイント

\(Q\)が公開鍵

\(d\)が秘密鍵

となります。\(d\)から\(Q\)を求めるのは\(Q=dG\)を求めるだけなので簡単ですが、\(Q\)から\(d\)を求めることは極めて難しいです。

やりたいこと

ここで、アリスとボブがいるとします。

それぞれの(秘密鍵,公開鍵)を\((d_{Alice},Q_{Alice})\)、\((d_{Bob},Q_{Bob})\)としましょう。

アリスはボブに対して、暗号化したメッセージを分散型台帳・ブロックチェーン上で送りたいと思っています。

しかし先程も言ったように、この秘密鍵・公開鍵は署名用のものであって、暗号化に役に立つ鍵ではありません。

そこで、楕円曲線ディフィー・ヘルマン鍵共有を使います。

楕円曲線ディフィー・ヘルマン鍵共有

まず、アリスとボブは、自身の公開鍵を互いに教えます。公開鍵なので、盗聴されたとしても問題ありません。

アリスが持っている情報の集合は

\(\{d_{Alice},Q_{Alice},Q_{Bob}\}\)

ボブが持っている情報の集合は

\(\{d_{Bob},Q_{Bob},Q_{Alice}\}\)

となりますね。

共通鍵

では持っているこれらの情報を使って、共通鍵を生成します。

アリスは、\(d_{Alice}Q_{Bob}\)を計算し、ボブは\(d_{Bob}Q_{Alice}\)を計算します。

ここでなんと、

\(d_{Alice}Q_{Bob}=d_{Alice}(d_{Bob}G)=d_{Bob}(d_{Alice}G)=d_{Bob}Q_{Alice}\)

が成り立ちます(!)

ここで\(d_{Alice}Q_{Bob}=d_{Bob}Q_{Alice}=K=(x_K,y_K)\)とすると、

この\((x_K,y_K)\)を、アリスとボブだけが知る共通鍵として、暗号化に使うことができるのです。

安全性

先程、盗聴されても問題ないといいましたが、これはなぜかと言うと、\(\{Q_{Alice},Q_{Bob}\}\)がわかったとしても、\(d_{Alice}\)または\(d_{Bob}\)を知ることはできないからです。

これを知るには、やはり離散対数問題を解かなくてはいけません。

離散対数問題を多項式時間で解くアルゴリズムが存在しないという仮定の下、ECDHで生成した共通鍵の暗号は安全だといえます。

ブロックチェーンで使われている例

NEMブロックチェーンでは、トランザクションに含めることができるメッセージの暗号化に、このECDHを使っています。