“博客是写给别人看的，笔记是写给自己看的。”

by Ancker-0

Hello，Curve25519

Curve25519 是一个为 Diffie-Hellman 密钥交换协议而提出的椭圆曲线，其运算在 ${\mathbb{Z}}_p$ 上进行，其中 $p=2^{255}-19$ 。这个曲线定义如下：

$$y^2=x^3+A{x}^2+x$$

其中 $A=486662$ 是质数。此外，用 $x=9$ 这一点生成的子群大小 $q=2^{252}+27742317777372353535851937790883648493$ 也是质数。

我们知道，DH 密钥交换协议是定义在有限群上的，那么 Curve25519 上怎么定义一个群呢？考虑方程

$$\begin{array}{}\text{(1)}& \begin{array}{rl}{y}^2& =x^3+A{x}^2+x\\ y& =\lambda x+c\end{array}\end{array}$$

在一般情况下有三个解 $P=(x_1,y_1),Q=(x_2,y_2),R=(x_3,y_3)$ （有可能产生相等的根），于是令 $P\circ Q\circ R=1$ ，其中 $1$ 是一个特殊的元素，又写作 $\mathrm{\infty }$ ，称为无穷远点（事实上，这个元素似乎是射影坐标为 $(0,\xi ,0)$ 的点），是该群的单位元。再令 $(x,y{)}^{-1}=(x,-y)$ 。可以验证 ^{然而并不那么容易} ，满足上述性质的运算 $\circ$ 可以作为群运算，且该运算是交换的，证明在此略去。

Associative?

这里简述一个初等的方法，证明上述运算结合，从而可以作为群运算。

首先证明 grid theorem ，这个定理叙述如下：

三条直线 $A_1,A_2,A_3$ 和三条直线 $B_1,B_2,B_3$ 两两相交得到九个交点。若一个三次曲线经过了九个交点中的八个，那么它必然经过剩下的那个交点。

我们知道，三次曲线可以用关于 $x$ 和 $y$ 的三次多项式的零点表示，而三次多项式有 10 个系数，因此三次多项式构成了维度是 10 的向量空间。设九个交点是 $v_1,v_2,\dots ,v_9$ ，所有经过 $v_j$ 的三次多项式构成的子空间为 $V_j$ 。我们断言 $\dim (V_1\cap V_2\cap \cdots \cap V_8)=2$ 。若不然，则（重排后）有 $V_1\cap V_2\cap \cdots V_7\subseteq V_8$ ，这意味着任意一个经过某七个交点的三次多项式必然经过第八个交点，而我们可以构造反例说明这是不可能的，详见 参考文献 。另一方面，设 $A_1,A_2,A_3$ 对应的多项式为 $\alpha$ ， $B_1,B_2,B_3$ 对应的多项式为 $\beta$ ，那么 $\{A\alpha +B\beta \mid A,B\in \mathbf{F}\}\subseteq V_1\cap V_2\cap \cdots \cap V_8$ ，因为前者必然经过 $v_1,v_2,\dots ,v_8$ 。事实上 $\{A\alpha +B\beta \mid A,B\in \mathbf{F}\}=V_1\cap V_2\cap \cdots \cap V_8$ ，因为二者维度都是 2。上述过程交点的顺序是任意的，故 $\{A\alpha +B\beta \mid A,B\in \mathbf{F}\}=V_1\cap V_2\cap \cdots \cap V_9$ ，这就完成了证明。

现在，借助 grid theorem，我们可以证明 $(P\circ Q)\circ R=P\circ (Q\circ R)$ 。对九点 $\left[\begin{array}{ccc}P& Q& (P\circ Q{)}^{-1}\\ 1& R& R^{-1}\\ P^{-1}& (Q\circ R{)}^{-1}& T\end{array}\right]$ 应用 grid theorem，可知 $T$ 也在曲线上，这意味着 $T=(P\circ Q)\circ R=P\circ (Q\circ R)$ ，也就说明运算结合。

遗憾的是，以上证明只对九点两两不同成立。如果有重复的点（例如 $P=Q$ ），仍然需要更强的定理， Cayley–Bacharach theorem ，或者 更复杂的分类讨论 。事实上，grid theorem 是 Cayley-Bacharach theorem 的特殊情形。

Naive Implementation

想要实现这个群的运算，我们可以直接用 $(x,y)$ 表示该群的元素，下面我们推导 $(x_1,y_1)\circ (x_2,y_2)$ 的表达式。我们将借助 $(x_1,y_1)\circ (x_2,y_2)\circ (x_3,y_3)=0$ 得到 $(x_1,y_1)\circ (x_2,y_2)=(x_3,-y_3)$

联立 $\text{(???)}$ 可得

$$x^3+(A-{\lambda }^2)x^2+(1-2\lambda c)x-c^2=0$$

由韦达定理， $x_3={\lambda }^2-A-x_1-x_2$ ，从而得到 $y_3=\lambda (x_3-x_1)+y_1。\mathrm{因}\mathrm{此}\mathrm{只}\mathrm{需}\mathrm{求}\mathrm{出}$ $\lambda$ 。当 $x_1\ne x_2$ 时，显然有 $\lambda =\frac{y_1-y_2}{x_1-x_2}$ 。当 $x_1=x_2$ 时，若 $y_1\ne y_2$ ，那么必有 $y_1+y_2=0$ ，因此 $(x_1,y_1)\circ (x_2,y_2)=1$ ，若 $y_1=y_2$ ，即两根相等的情况，如果考虑 $\mathbb{R}$ 上的曲线，那么 $\lambda$ 就是曲线在 $(x_1,y_1)$ 处的切线，因此有

$$\lambda =\frac{x_1^2+x_1{x}_2+x_2^2+A(x_1+x_2)+1}{y_1+y_2}=\frac{3x_1^2+2A{x}_1+1}{2y_1}$$

事实证明，这一定义在 ${\mathbb{Z}}_p$ 上也成立。这样，我们就完成了朴素的运算定义。

按照以上定义，我用 Racket 写了一个 朴素的实现 ，包括 ECDH 和 ECDSA^{by 2024-11-11} 。这个实现尚不能抵抗 timing attack。

测试 ECDH

(let* ([u (generate-key)]
       [v (generate-key)]
       [k1 (X25519 (car u) (cdr v))]
       [k2 (X25519 (car v) (cdr u))])
  (assert (CV-= k1 k2))
  (printf "Established shared key ~a\n" k1))

测试 ECDSA

(let* ([msg (random-natural Q)]
       [key (generate-key)]
       [sign (ED25519-sign msg (cdr key))]
       [success? (ED25519-verify msg sign (car key))])
  (assert success?)
  (display "Signature verified!\n"))

Enhanced Implementation

待续...

后记 - 我们为什么需要 DH

因为 DH 可以在无需交互的情况下实现前向保密，这在 Signal 或者 Matrix 这样的加密聊天软件是重要的。

参考文献

• Implementing Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography
• Curve25519 - Wikipedia
• Elliptic Curve Cryptography: ECDH and ECDSA
• The grid theorem
• The elliptic curve group law
• An elementary linear-algebraic proof without computer-aided arguments for the group law on elliptic curves
• Pappus’s theorem and elliptic curves - Terry Tao