DAY 16- DHKE、ECDH、ElGamal

有趣的简写越来越多了，而且越来越长了...

我个人认为这个章节应该摆在对称加密和非对称密码的中间来介绍，
不过因为我想要将椭圆曲线密码学的东西纳进来一起讲，
所以只好先介绍完椭圆曲线。

想法是这样的：
两个人只能在不安全通道上进行通讯（也就是没有安全通道传递密钥）、而且没有事先协议的情况之下，
有没有可能进行安全通讯。

答案是可以的，我们可以在不安全的通道上进行密钥的协议。

DHKE（Diffie–Hellman key exchange）

换一个说法是，
如果攻击者可以窃听两人之间的通讯讯息，
他也没办法得到密钥。

DHKE方法可以让两个人协议出密钥，在用此密钥进行对称式加密。
假设 Alice 和 Bob 在不安全通道上进行通讯。
这里有一个比较生动的表示方法。

两个人一开始都有一杯同样颜色的颜料，
也各自有自己的秘密颜料，没有人知道秘密的颜色。
接着将共有颜料跟秘密颜料混和在一起，
并传给对方。
拿到对方混和颜料的两人都各自将自己的秘密颜料加到里面。
於是两人得到共同的秘密。
（这杯共同秘密颜料里面有：共同颜料+两人的秘密颜料）

ＯＳ：到底是谁想到这种表示方法的...

以上的说明只是一种比喻，这个比喻的漏洞就是调色是可以逆推的，
而 DHKE 的运算是不可逆推的。

来看看这个交换密钥的方法，

首先两人都拥有的数字是 和p 、

两人各自的秘密（私钥）是 a 和 b。

（以下的运算都要 mod p）

於是第一步两人分别将 提升到 a 次方及 b 次方，成为公钥（称为A及B）。

接着交换公钥。

收到对方公钥之後，两人在各自将公要提升到自己的私要次方，即得到共享秘密。

而共享秘密即是：

而运用这个共享秘密两人就可以进行对称式加密通讯。
如果你想要实际操作DHKE的话，可以找一个人陪你玩（？）。
如果没有人要陪你玩的话，你可以到下面这个网站实际操作看看，
（只是比较无聊一点）

https://www.irongeek.com/diffie-hellman.php

ECDH（Elliptic Curve Diffie–Hellman key exchange）

昨天讲了椭圆曲线密码学的基础，
今天就要来实际看他可以干嘛。

ECC可以运用在密钥的交换上，因为他具有很好的不可逆运算性质，
因此可以套用在原本使用离散对数的 DHKE 上面，称作ECDH。
有了ECC的基本概念，ECDH 其实会比 DHKE 还要好理解。

其实跟DHKE一样，两人有各自的私钥（a, b），还有公开的基点（G）
藉由倍数关系，

获得共同的密钥，进行对称式加密 ( AES )。
要注意的是，椭圆曲线上的运算结果是一个座标，我们用算出来的 x 座标当密钥。

DHKE这样看似公钥密码系统的密钥协定算法，其实是在 RSA 公布前就出现了，
而他最後所达成的是对称式密钥的交换，不能完全算是非对称式加密。
以下要介绍的演算法，是基於DHKE的非对称式加密演算法。

ElGamal Encryption Scheme

ElGamal是埃及密码学家طاهر الجمل 的英文翻译，
他将 DHKE 延伸成一种加密演算法。
ElGamal 大致上和 DHKE 一模一样，只是他减少了讯息需要被传送的次数，
以及最後是直接用此共同密钥加密传送讯息。

可以看到这个图片上所表示的，
接收者先公开自己的公钥，也就是上图的 (a, p, y) （对应到以上所提的 ,p,A）
传送者将要传送的讯息加密後连同提升过的 一起传送给对方。
接收者就可以运用已有的方式解密。

先前说过，对称式加密的好处是速度快，而非对称式安全性较高，
因此就很适合用非对称式加密将「对称式密钥（比如说AES的密钥）」加密後传送，
再使用该密钥进行快速的对称式加密。

结束。
之後来讲杂凑函数，掰掰~

图片来源：
https://warroom.rsmus.com/encryption-basics-dhke/
https://www.researchgate.net/figure/The-DHKE-algorithm-51_fig21_331287260
http://cryptowiki.net/index.php?title=El_Gamal_Scheme
https://billatnapier.medium.com/little-protects-you-on-line-like-ecdh-lets-go-create-it-a14188eabded