ECDH密钥协商协议

一元三次方程

配方法

对于一元二次方程 $ax^2+bx+c=0$，核心思想是配方：

\[x^2 + \frac{b}{a}x + \frac{c}{a} = 0 \implies \left(x + \frac{b}{2a}\right)^2 = \dots\]

通过换元 $y = x + \frac{b}{2a}$，成功消去了一次项，将方程形式转换成 $y^2 = K$。

困境：对于三次方程 $ax^3+bx^2+cx+d=0$，能否“配立方”？

展开 $(x+k)^3 = x^3 + 3kx^2 + 3k^2x + k^3$。

若设 $x = t - \frac{b}{3a}$（Tschirnhaus 变换），代入原方程，可以消去二次项（$t^2$ 项系数为0），但一次项通常依然存在。最终得到：

\[t^3 + pt + q = 0\]

这是三次方程的标准型。如果能解出它，就能解出所有三次方程。

Cardano公式

面对 $t^3 + pt + q = 0$，单个变量 $t$ 无法分离。Cardano（基于 Tartaglia 的发现）引入了两个变量来增加自由度。

1. 假设：设 $t = u + v$。

2. 代入：

   \[(u+v)^3 + p(u+v) + q = 0\] \[u^3 + v^3 + 3uv(u+v) + p(u+v) + q = 0\] \[u^3 + v^3 + (3uv+p)(u+v) + q = 0\]
3. 增加约束：为了解出两个未知数 $u, v$，人为制造第二个方程(用掉之前多余的自由度)。
   令 \(3uv + p = 0 \implies uv = -\frac{p}{3}\)
4. 化简：原方程变为： \(u^3 + v^3 = -q\)
5. 二次方程： 已知 $u^3 + v^3 = -q$ 且 $u^3v^3 = (-p/3)^3$。
   根据韦达定理，$u^3$ 和 $v^3$ 是二次方程 \(Z^2 + qZ - \left(\frac{p}{3}\right)^3 = 0\) 的两个根：
6. 求解： \(Z = \frac{-q \pm \sqrt{q^2 + 4(p/3)^3}}{2} = -\frac{q}{2} \pm \sqrt{\left(\frac{q}{2}\right)^2 + \left(\frac{p}{3}\right)^3}\) 于是 $t = u + v = \sqrt[3]{Z_1} + \sqrt[3]{Z_2}$。

结论（Cardano 公式）： \(t = \sqrt[3]{-\frac{q}{2} + \sqrt{\Delta}} + \sqrt[3]{-\frac{q}{2} - \sqrt{\Delta}}\) 其中 $\Delta = (q/2)^2 + (p/3)^3$ 是判别式。

椭圆曲线与加法群

椭圆曲线的 Weierstrass 标准型

回到由 Tschirnhaus 变换得到的方程：

\[t^3 + pt + q = 0\]

如果不让右边等于 0，而是让它等于一个变量的平方呢？

通常我们将变量写为 $x, y$，即：

\[E: \quad y^2 = x^3 + ax + b\]

（需满足判别式 $(a/3)^3 + (b/2)^2 \neq 0$ 以保证曲线光滑，无尖点）。

这就是著名的 椭圆曲线（Elliptic Curve） 的 Weierstrass 标准型。

定义加法

我们要在曲线上的点之间定义一种加法，使其构成一个阿贝尔群（Abelian Group）。

几何定义：

1. 取点：取曲线 $E$ 上的两点 $P$ 和 $Q$。
2. 连线：作直线 $L$ 穿过 $P, Q$。根据代数基本定理，三次曲线与直线应有 3 个交点（计入重数）。设第三个交点为 $R’$。
3. 反射：取 $R’$ 关于 $x$ 轴的对称点 $R$。
4. 结果：定义 $P + Q = R$。

特殊情况：

• 点加自己 ($P+P$)：作 $P$ 点的切线，用切线代替割线。
• 单位元 ($\mathcal{O}$)：规定无穷远点为零元。
  • 若 $P$ 和 $Q$ 关于 x 轴对称（如 $(x,y)$ 和 $(x,-y)$），则 $P + Q = \mathcal{O}$
• 三点共线定理：若 $P, Q, R’$ 共线，则 $P + Q + R’ = \mathcal{O}$。
• 负元：$-P = (x, -y)$

坐标公式

设 $P=(x_1, y_1), Q=(x_2, y_2)$，求 $R=(x_3, y_3) = P+Q$。

1. 求斜率 $\lambda$：
   • 若 $P \neq Q$：$\lambda = \frac{y_2 - y_1}{x_2 - x_1}$
   • 若 $P = Q$（切线斜率）：对 $y^2 = x^3+ax+b$ 隐函数求导，$2yy’ = 3x^2+a \implies \lambda = \frac{3x_1^2+a}{2y_1}$

2. 求 $x_3$： 将直线 $y = \lambda(x-x_1)+y_1$ 代入曲线方程： \((\lambda(x-x_1)+y_1)^2 = x^3 + ax + b\) 整理得 $x^3 - \lambda^2 x^2 + \dots = 0$。 根据韦达定理，三根之和 $x_1 + x_2 + x_3 = \lambda^2$

   \[x_3 = \lambda^2 - x_1 - x_2\]

3. 求 $y_3$： 算出 $R’$ 的纵坐标 $y_3’ = \lambda(x_3 - x_1) + y_1$。 因为 $R$ 是 $R’$ 的反射，所以

   \[y_3 = -y_3' = \lambda(x_1 - x_3) - y_1\]

如果 $P, Q$ 的坐标是有理数，那么 $R$ 的坐标也是有理数。这证明了有理点集在加法下是封闭的。

---

案例：对于曲线 $y^2 = x^3 - 2$。

• 整数点：通过尝试小整数，发现 $(3, 5)$ 和 $(3, -5)$ 是解。
• 生成有理点：计算 $2P = P + P$，其中 $P=(3,5)$。
  • 斜率 $\lambda = \frac{3(3)^2}{2(5)} = \frac{27}{10}$
  • $x_{new} = (\frac{27}{10})^2 - 3 - 3 = \frac{729}{100} - 6 = \frac{129}{100}$
  • $y_{new} = \dots$
  • 得到了一个新的有理点, 重复此过程可生成无穷多解。

有限域上的椭圆曲线

为了用于密码学，我们不能使用实数（有舍入误差）或有理数（分子分母无限精度无法表示）。

我们将曲线定义在有限域 $\mathbb{F}_p$ 上（模素数 $p$）。

\[y^2 \equiv x^3 + ax + b \pmod{p}\]

所有点 $(x, y)$ 满足该同余式，且 $x, y \in {0, 1, \dots, p-1}$。

• 点集是有限的（大约 $p$ 个点）。
• 加法规则完全相同，只是所有运算都 mod $p$（加减乘除、求逆元）。
• 除法 = 乘以模逆元（可用扩展欧几里得算法计算）。

ECDH 密钥交换

背景问题：

Alice 和 Bob 想通过公开信道协商一个共享密钥，但攻击者能监听所有通信。

利用椭圆曲线上的离散对数难题（ECDLP）

离散对数问题 (ECDLP)：

• 加法（易）：已知 $P$，求 $Q = P + P + \dots + P$ ($n$ 次) = $nP$。速度极快（$O(\log n)$）。
• 除法（难）：已知 $P$ 和 $Q$，且已知 $Q=nP$，求 $n$？

  目前没有已知的高效算法, 最优$O(\sqrt{N})$

朴素暴力穷举：$O(N)$

假设椭圆曲线上的点构成一个阶为 $N$ 的循环群（即总共有 $N$ 个点，且由基点 $G$ 生成）。

已知：

• $P = G$（基点）
• $Q = nG$，其中 $1 \leq n < N$

依次计算
\(G,\ 2G,\ 3G,\ \dots,\ kG,\ \dots\)
直到某个 $kG = Q$，那么 $n = k$。

对大 $N$（比如 $N \approx 2^{256}$, 现代 ECC 的标准安全级别）完全不可行。

Pollard’s rho 算法：$O(\sqrt{N})$

核心思想来自生日悖论（Birthday Paradox）：

在一个大小为 $N$ 的集合中，随机选大约 $\sqrt{N}$ 个元素，就有很高概率出现“碰撞”（两个相同）。

Pollard’s rho 利用这一点，在群中构造一个伪随机序列，寻找满足某种关系的“碰撞”，从而解出 $n$。

• Pollard’s rho 解 ECDLP 的期望时间复杂度是 $O(\sqrt{N})$ 次群运算。
• 这是目前已知最优的经典（非量子）算法用于一般椭圆曲线。

• 它所需的存储空间很小（$O(1)$），适合实际攻击。

• Pollard’s rho：约需 $\sqrt{2^{256}} = 2^{128}$ 次运算。
  • $2^{128}$ 仍然是一个天文数字（约 $3.4 \times 10^{38}$）
  • RSA / DH 需要 3072 位密钥 ≈ 128 位安全, ECC 只需 256 位密钥 ≈ 128 位安全

ECDH 步骤（两人密钥协商）：

1. 公开参数：
   • 一个大素数 $p$
   • 椭圆曲线 $E: y^2 = x^3 + ax + b \pmod{p}$
   • 一个基点 $G$（曲线上的一个固定点，阶很大）
2. Alice：
   • 私钥：选一个随机整数 $a$
   • 公钥：计算 $A = aG$
3. Bob：
   • 私钥：选一个随机整数 $b$
   • 公钥：计算 $B = bG$

4. 交换公钥：Alice 发 $A$ 给 Bob，Bob 发 $B$ 给 Alice

5. 各自计算共享密钥：
   • Alice 计算：$S = aB = a(bG) = abG$
   • Bob 计算：$S = bA = b(aG) = abG$

两人得到相同的密钥 $S$

攻击者视角

• 攻击者知道：$G, A = aG, B = bG$
• 但要算出 $S = abG$，必须知道 $a$ 或 $b$
• 而从 $A = aG$ 反推 $a$ 就是求离散对数，目前计算不可行

附录

生日悖论（Birthday Paradox）

问题设定

假设有一个大小为 $ N $ 的有限集合。我们从中独立且均匀地随机选取元素，问：期望多少次采样后会出现重复？

碰撞概率

设我们选取了 $ k $ 个元素，且全部不同的概率为：

\[P(\text{无碰撞}) = \frac{N}{N} \cdot \frac{N-1}{N} \cdot \frac{N-2}{N} \cdots \frac{N - k + 1}{N} = \prod_{i=0}^{k-1} \left(1 - \frac{i}{N}\right)\]

利用不等式 $ 1 - x \le e^{-x} $，有：

\[P(\text{无碰撞}) \le \prod_{i=0}^{k-1} e^{-i/N} = e^{-\frac{1}{N} \sum_{i=0}^{k-1} i} = e^{-\frac{k(k-1)}{2N}} \approx e^{-k^2/(2N)}\]

我们希望碰撞概率 ≥ 1/2，即：

\[P(\text{碰撞}) = 1 - P(\text{无碰撞}) \ge \frac{1}{2} \Rightarrow P(\text{无碰撞}) \le \frac{1}{2}\]

令：

\[e^{-k^2/(2N)} \le \frac{1}{2} \Rightarrow \frac{k^2}{2N} \ge \ln 2 \Rightarrow k \ge \sqrt{2N \ln 2} \approx 1.177 \sqrt{N}\]

期望碰撞时间

虽然“50% 概率”对应 $ \sim 1.177\sqrt{N} $，但期望首次碰撞时间（expected number of samples until first collision）同样为 $ \Theta(\sqrt{N}) $。可证明：

\[\mathbb{E}[T] \approx \sqrt{\frac{\pi N}{2}} \approx 1.253 \sqrt{N}\]

因此，在大小为 $ N $ 的空间中，随机采样约 $ O(\sqrt{N}) $ 次即可高概率发生碰撞。

---

Pollard’s rho 算法（用于 ECDLP）

问题定义：椭圆曲线离散对数问题（ECDLP）

给定：

• 椭圆曲线 $ E $ 定义在有限域上
• 基点 $ P \in E $，阶为素数 $ n $（即 $ nP = \mathcal{O} $，单位元）
• 点 $ Q = dP $，其中 $ d \in {0, 1, …, n-1} $ 未知

目标：求 $ d $

这是一个在一般椭圆曲线上被认为困难的问题。

Pollard’s rho 的核心思想

• 利用生日悖论：在大小为 $ n $ 的群中，构造一个伪随机游走序列 $ X_0, X_1, X_2, \dots \in \langle P \rangle $
• 每个 $ X_i $ 都表示为 $ X_i = a_i P + b_i Q $，即 $ X_i = (a_i + b_i d) P $
• 由于群大小为 $ n $有限，序列必会循环
• 一旦出现碰撞：$ X_i = X_j $（但 $ i \ne j $），则有： \(a_i + b_i d \equiv a_j + b_j d \pmod{n} \Rightarrow (b_i - b_j) d \equiv a_j - a_i \pmod{n}\)
• 若 $ b_i \not\equiv b_j \pmod{n} $，则可解出： \(d \equiv (a_j - a_i)(b_i - b_j)^{-1} \pmod{n}\)

算法步骤（Floyd 循环检测）

1. 定义伪随机函数 $ f: G \to G $

将群 $ G = \langle P \rangle $ 划分为三个（或更多）不相交子集 $ S_0, S_1, S_2 $（通常按 x 坐标模 3 划分）。

定义迭代函数：

\[f(X) = \begin{cases} X + P & \text{if } X \in S_0 \\ 2X & \text{if } X \in S_1 \\ X + Q & \text{if } X \in S_2 \\ \end{cases}\]

同时维护对应的系数 $ (a, b) $，使得 $ X = aP + bQ $。

更新规则（初始 $ X_0 = \mathcal{O} $, $ a_0 = 0 $, $ b_0 = 0 $）：

• 若 $ X \in S_0 $：$ a \gets a + 1 \mod n $
• 若 $ X \in S_1 $：$ a \gets 2a \mod n $, $ b \gets 2b \mod n $
• 若 $ X \in S_2 $：$ b \gets b + 1 \mod n $

2. 使用 Floyd 的“龟兔赛跑”检测碰撞

• 龟（slow）：每次走 1 步 → $ X_i $
• 兔（fast）：每次走 2 步 → $ X_{2i} $
• 迭代直到 $ X_i = X_{2i} $

3. 一旦碰撞，解线性同余式

设龟：$ X_i = a_i P + b_i Q $
兔：$ X_{2i} = a_{2i} P + b_{2i} Q $

若 $ X_i = X_{2i} $，则：

\[(a_i - a_{2i}) P + (b_i - b_{2i}) Q = \mathcal{O} \Rightarrow (a_i - a_{2i}) + (b_i - b_{2i}) d \equiv 0 \pmod{n}\]

即：

\[d \equiv (a_{2i} - a_i)(b_i - b_{2i})^{-1} \pmod{n}\]

前提是 $ b_i \not\equiv b_{2i} \pmod{n} $。若分母为 0（即 $ b_i \equiv b_{2i} $），则失败，需重启（换初始点或划分方式）。