共有鍵(Shared Key)<Diffie-Hellman,Elliptic Curve>

# 共有鍵(Shared Key)

最近学んだので備忘録的に書きます。

共有鍵の良いところは、通信経路上には公開鍵しか流さないけど
お互いに、秘密鍵が共有できるというところです。

TLSとかに使われています。

https://github.com/tnakagawa/ecdhsample

## Diffie-Hellman

原理としては、案外簡単です。

```math
\begin{align*}
& p \text{ : 素数(prime number)}\\
& g \text{ : generator}\\
&\ \\
& a \text{ : aliceの秘密鍵(private key)}\\
& g^a\text{ : aliceの公開鍵(public key)}\\
&\ \\
& b \text{ : bobの秘密鍵(private key)}\\
& g^b\text{ : bobの公開鍵(public key)}\\
&\ \\
& (g^b)^a = (g^a)^b = g^{ab}
\end{align*}
```
最初の素数で冪剰余（べきじょうよ）、modの表記は省略してあります。

相手の公開鍵に、自分の秘密鍵を累乗すれば、お互いに同じ値が取れるというものです。

素数(p)と生成元(g)をお互いが事前に知っておく必要があります。
これは、知られていても特に問題ないそうです。
これらは、いくつかの公開文章に記載されています。

今回は、以下のRFCにある「ffdhe2048」を使ってみます。
https://tools.ietf.org/html/rfc7919

```text
Diffie-Hellman
pri1:74532bd4082fdea88e6a196f725a6f932a69dffb93ec5d5fe08a99c82b72fec3
pub1:d8e6cd15999fcff9bbfecb5ae6d231a60516db633fc620fe2c33fec96d1758b1d29932b683186f9c766c0b51b440d3d5e1a22e7825a034fef8678bccc7b56e76b4f83db031224c77660555941a89cecdc20faa8334ba8003bae654930818d4a24b4e27827c42a7dd73cdfad18d4036d6edeb260b47ff9e511a5ef7503afcb98347f009e753d282a66ddff73e4232db5d5c83ea4ed0e0508b701ef0a21490e1b9b87e71b9f0508bf595e818d75f13f22ed7738554cc650930f6a0fe9dd12a37b04dbef4210935f029e59254236a09665100855c7f0ea4290fe1b33ba051937302c8ac4cfadee37e16a139a2c9cebcf4c97973d3af84fc951022705648c7f6d8d2
pri2:70c6b097ed017c03bb07d5f91331af3abcc681ad2fff2e447874a9fa9cac396
pub2:d2ea1f21e8edab14e3af4b2cf5baff3d3f4970bb5743f7d8fb7eb14507383790877ff656a347ea21085f4c7cec7526c33f2981f0212a1bfc7259e437100f085b4f8e0dc8b24b22fab1a3d02b8fe57666c730e7b4da23d74612ae5d8d934e3545c781496632b7f37110a677bd196b5669194bcfb31bff74755fd2bbc76bfccf4217a45e68fa0e12bdb14bffacd45f5f52ccf23264e627a0aa51f6056d8951be2094ea583ba796626d69852c6bd46f1cc268bd4ae12f53692370243acb233b4daf0611c1bf41f95809605323b8f5a19a3337c7895fc4e5ac10a8279f98794dd0c144e18902e2ea255792734d72f8997ab053c258fe540d5b8405e40bd093bc2414
sha1:abe62004a446dca65c83390849311d4fc0ab8f7a32611a52ff50e6ebca3f60d6bcdec854f1bec54afb67bac321fbded9dfe1a9d936db1c3b629a3f6d06d196d2c42ecfe85183f3e383f1613a767a4b006782d6530f2394d85892c7d41f6e1ee678bcca5265c63f87955c24ea926f599c6b3f91b89ab6be1a88cc159e5f228d72ad173c9213653c45b0be72e0a582c36a0b04188bcca75f62a0139e5b07566ce3cd62c75cd7a7e295af4393971e38472b20381c6ef524a4032d689179af2cac9e02ffc40dd6c05eaa91220e80a2c8ca6224dcbf615de8a847c47a03974f1650741170d2a7acac30012f8b1caf9dfa128aac3a9acbd15330ad111292ddbebb267b
sha2:abe62004a446dca65c83390849311d4fc0ab8f7a32611a52ff50e6ebca3f60d6bcdec854f1bec54afb67bac321fbded9dfe1a9d936db1c3b629a3f6d06d196d2c42ecfe85183f3e383f1613a767a4b006782d6530f2394d85892c7d41f6e1ee678bcca5265c63f87955c24ea926f599c6b3f91b89ab6be1a88cc159e5f228d72ad173c9213653c45b0be72e0a582c36a0b04188bcca75f62a0139e5b07566ce3cd62c75cd7a7e295af4393971e38472b20381c6ef524a4032d689179af2cac9e02ffc40dd6c05eaa91220e80a2c8ca6224dcbf615de8a847c47a03974f1650741170d2a7acac30012f8b1caf9dfa128aac3a9acbd15330ad111292ddbebb267b
```

長いけど、共有鍵が導き出されて、同じである事がわかります。

## 楕円曲線(Elliptic Curve)

楕円曲線でも同じことができます。
こちらを利用すると、Diffie-Hellmanより少ないデータで表せます。（強度は同じくらいらしい）

原理としては、Diffie-Hellmanと同じです。
数値の累乗から楕円曲線の点（EC point）の積に変ります。

```math
\begin{align*}
& G \text{ : generator(EC point)}\\
&\ \\
& a \text{ : aliceの秘密鍵(private key)}\\
& aG\text{ : aliceの公開鍵(public key/EC point)}\\
&\ \\
& b \text{ : bobの秘密鍵(private key)}\\
& bG\text{ : bobの公開鍵(public key/EC point)}\\
&\ \\
& a(bG) = b(aG) = abG
\end{align*}
```

これについても楕円曲線が何であるのか、お互いが事前に知っている必要があります。

以下に記載されている「secp256k1」を使ってみます。
http://www.secg.org/SEC2-Ver-1.0.pdf

```text
Elliptic Curve
pri3:49f92709e6eb03a4ebb67b276cbbfa5f7bf080cae636dda1f84f199c626d80bf
pub3:03d4c2421f013d37b7e8c07802659dabf7cff86990b7ee19da86252be9d24fd9dd
pri4:215cbcc7720960c710200a9a6ef3b810826ff37157280d8f4c5c8f5fe7bfbe7f
pub4:028136eb84f09ee6e8dafaa9dac3b9dd27b27ee73e08916b3d73c18d53b11e7750
sha3:03afee54c3e2416579c6a18e6b8a3406a3c2273a7643d793afec486f793cd0dcc6
sha4:03afee54c3e2416579c6a18e6b8a3406a3c2273a7643d793afec486f793cd0dcc6
```

かなり、コンパクトにまとまってます。

ただ、Diffie-Hellmanにくらべてパフォーマンスは落ちます。
私の作ったコードは、wikipediaに乗っている式を単純に当てはめただけなので、くっそ遅いです。
ライブラリを使えるのであれば、そちらを使った方が早く演算できます。

# まとめ

メールに添付した暗号ZIPのパスワードをメールで再度送るとかって意味の無いルールが
いまだにあって、そういうのに使えます。
とか、言ってみたものの、意味のないルールを使っている人が、この価値をわかってくれないだろうなぁとも
思う今日この頃です。