Curve25519

在密码学中，Curve25519是一种椭圆曲线，被设计用于椭圆曲线迪菲-赫尔曼（ECDH）密钥交换方法，可用作提供256位元的安全金鑰。它是不被任何已知专利覆盖的最快ECC曲线之一。

最初的Curve25519草稿将其定义成一个迪菲-赫尔曼（DH）函数。在那之后Daniel J. Bernstein提出Curve25519应被作为底层曲线的名称，而将X25519作为其DH函数的名称。

ECDH

椭圆曲线迪菲-赫尔曼密钥交换（英语：Elliptic Curve Diffie–Hellman key exchange，缩写为ECDH），是一种匿名的密钥合意协议（Key-agreement protocol），这是迪菲－赫尔曼密钥交换的变种，采用椭圆曲线密码学来加强性能与安全性。在这个协定下，双方利用由椭圆曲线密码学建立的公钥与私钥对，在一个不安全的通道中，建立起安全的共有加密资料。

蒙哥马利曲线

蒙哥马利曲线是一类椭圆曲线，其满足的通式为 $M_{A,B}:B{y}^2=x^3+A{x}^2+x$ 其中满足 $B(A^2-4)\ne 0$。

椭圆曲线上的加法

我们定义椭圆曲线 E 上的加法是指点 $P,Q\in E$ 连成的直线 L 与椭圆曲线 E 所交的第三个点关于 x 轴的对称点。

显然根据定义我们可以知道这个加法运算满足交换律，即 P+Q=Q+P。

当点 P 与点 Q 重合的时候，我们将此时椭圆曲线上点 P 处的切线作为直线 L 与椭圆曲线求交。

当点 P 与点 Q 关于 x 轴对称（我们记为 $P=Q^{-1}$）的时候，则可能 L 与 E 没有第三个交点，这时候我们人为添加一个无穷远点 O，用来作为这种情况下的解，即 $P+P^{-1}=O$。

此外我们有

$$\begin{array}{rl}O+O& =O\\ P+O& =P\end{array}$$

经过简单推导可以看出 O 满足许多加法中零元的性质，因此我们可以将点 O 看作是由集合 $S=\{P|P\in E\}\cup \{O\}$和加法 $⟨+⟩$ 构成的群 $G=⟨S,+⟩$ 中的单位元。

Curve25519

Curve25519 指的是一条曲线，这条曲线是指一条蒙哥马利曲线

$$C:y^2=x^3+486662x^2+x$$

并且定义在质数模域 $p=2^{255}-19$ 上，故将曲线称之为 Curve25519。

该曲线在双有理几何上等同于Ed25519签名方案中使用的扭曲Edwards曲线

我们定义群 G 是由该椭圆曲线上的点和一个无穷远点 O，以及椭圆曲线上的加法运算 $⟨+⟩$ 所定义的群，根据一些我也不知道怎么推的魔法手段可以得出群 G 的阶，即 |G| = hq，其中 $h=2^c=8$ 被称为余因子（cofactor），q 是一个比较大的质数，准确来说有 $q=2^{252}+27742317777372353535851937790883648493$。

根据拉格朗日定理，我们可以知道如果群 G 有子群 E，则 $|E|$ 必为 $|G|$ 的一个因子。所以我们可以知道，对于群 G 中的任意元素的阶必定是 1,2,4,8,q,2q,4q,8q 中的一个。

椭圆曲线加密算法原理如下：

设私钥、公钥分别为k、K，即K = kG，其中G为G点。

公钥加密：
选择随机数r，将消息M生成密文C，该密文是一个点对，即：
C = {rG, M+rK}，其中K为公钥

私钥解密：
M + rK - k(rG) = M + r(kG) - k(rG) = M
其中k、K分别为私钥、公钥。

X25519 与 ECDH

优点：

1. 更强的安全性：ECDH使用椭圆曲线密码学，它基于椭圆曲线上的数学问题，这被认为比DH密钥交换中使用的大整数上的离散对数问题更难破解。因此，相同长度的密钥，ECDH提供更高的安全性。
2. 更短的密钥长度：由于其更高的安全性，ECDH可以使用更短的密钥长度达到与DH相同的安全级别。这意味着更少的数据传输和存储需求，同时保持强大的加密强度。

X25519 指的是在曲线 Curve25519 上计算的一套 ECDH 密钥交换算法，其中选择的基点是 G=(9, y)，并且可以通过计算可以知道点 G 的阶是 ord(G) = q。

ECDH 的过程如下：

1. Alice 生成自己的私钥 a，并且计算公钥 $A=a\cdot G$
2. Bob 生成自己的私钥 b，并且计算公钥 $B=b\cdot G$
3. Alice 和 Bob 将自己的公钥通过不安全信道发送给对方
4. Alice 计算 $K=a\cdot B=a\cdot (b\cdot G)=ab\cdot G$
5. Bob 计算 $K=b\cdot A=b\cdot (a\cdot G)=ab\cdot G$

Alice 和 Bob 可以得到一个相同的结果作为接下来对称加密的密钥，但是攻击者仅通过偷听到的 A 和 B 很难计算出 a, b 的值，也很难得出 K 的结果。

但是这个算法也有一些缺陷，假设 Alice 想要窃取 Bob 的密钥，那么 Alice 可以从 Curve25519 曲线中挑选出一个阶比较小的点 SS 作为自己的公钥，我们不妨设 ord(S)=8，即 $8\cdot S=O$。那么 Bob 在收到 Alice 的公钥之后会计算 $K=b\cdot S$，并将 K 作为接下来对称加密的密钥。而 Alice 知道 K 只有可能是 8 种不同的结果，并且可以根据 Bob 接下来的行为判断出 Bob 得到的是哪个密钥，从而得到 $b\mathrm{mod}8$ 的结果，相当于泄露了 3 比特的密钥信息。这种攻击手段被称为Small Subgroup Confinement Attack。

想要防范上面的攻击，可以当 Bob 收到对方密钥之后预先计算一下$K^{\prime }=h\cdot A$是否等于无穷远点 O。可以证明，如果 Alice 的公钥的阶小于等于 h，则 K’ 的结果将必定是 O。这时候 Bob 可以认为 Alice 的公钥不合法，从而拒绝接下来的通信。

X25519 并没有从上面的角度出发，而是直接钦点私钥的最低三位比特必须是 0，这样 Alice 将无法得到任何有用的信息。

此外 X25519 也指定私钥的长度为 256 位，其中最高位比特必须为 0，次高位比特必须为 1，这将密钥的空间降低到了 $2^{251}$ 级别，同时将私钥的最高有效位也固定了下来，可以防止一些旁道攻击。