椭圆曲线

历史背景

椭圆曲线的概念最早可以追溯到18世纪。它起源于代数几何中的一类特殊曲线，最初被数学家用于研究整数解的问题。椭圆曲线的几何性质与代数方程的结合为后来的密码学应用奠定了基础。

椭圆曲线密码学的诞生

椭圆曲线在密码学中的应用最早出现在20世纪80年代。1970年代末期到1980年代初，随着计算机科学和密码学的发展，数学家开始研究如何将椭圆曲线应用于公钥加密系统。

发明者

• 维尔纳·斯图姆（Werner Storn） 和 爱德华·阿贝尔（Edward Abel）：提出了椭圆曲线加密方法的初步构想，最终使得椭圆曲线在密码学中的应用成为可能。
• 尼尔·克利夫兰（Neal Koblitz） 和 维基·肖（Victor Miller）：在1985年，Koblitz和Miller分别独立提出了基于椭圆曲线的公钥加密方法，标志着椭圆曲线密码学（ECC）的诞生。这个新算法具有较小的密钥尺寸和更高的安全性，迅速引起了密码学界的关注。

椭圆曲线密码学的应用

椭圆曲线密码学由于其高效性和安全性，广泛应用于现代加密协议，如：

• 椭圆曲线数字签名算法（ECDSA）
• 椭圆曲线 Diffie-Hellman 密钥交换（ECDH）
• 椭圆曲线加密（ECC）

• ECC的主要优势是它相比RSA加密算法使用较小的密钥长度并提供相当等级的安全性。

这些应用已被广泛应用于区块链、加密货币、TLS/SSL协议等安全通信系统中。

数学公式

魏尔斯特拉斯椭圆函数方程:

$$y^2 = x^3 + ax + b$$

R=P+Q加法

验证点是否在曲线上

首先，验证给定的点是否在椭圆曲线 $y^2 = x^3 - 7x + 10$ 上。

验证点 $P = (1, 2)$

代入 $x = 1$ 和 $y = 2$ 到曲线方程：

$$y^2 = x^3 - 7x + 10 \quad \Rightarrow \quad 2^2 = 1^3 - 7(1) + 10$$

$$4 = 1 - 7 + 10 \quad \Rightarrow \quad 4 = 4$$

所以 $P = (1, 2)$ 在曲线上。

验证点 $Q = (3, 4)$

代入 $x = 3$ 和 $y = 4$ 到曲线方程：

$$y^2 = x^3 - 7x + 10 \quad \Rightarrow \quad 4^2 = 3^3 - 7(3) + 10$$

$$16 = 27 - 21 + 10 \quad \Rightarrow \quad 16 = 16$$

所以 $Q = (3, 4)$ 也在曲线上。

验证点 $R = (-3, 2)$

代入 $x = -3$ 和 $y = 2$ 到曲线方程：

$$y^2 = x^3 - 7x + 10 \quad \Rightarrow \quad 2^2 = (-3)^3 - 7(-3) + 10$$

$$4 = -27 + 21 + 10 \quad \Rightarrow \quad 4 = 4$$

所以 $R = (-3, 2)$ 也在曲线上。

• 计算直线斜率 $m$：

$$m = \frac{y_2 - y_1}{x_2 - x_1} = \frac{4 - 2}{3 - 1} = \frac{2}{2} = 1$$

直线的方程是：

$$y - 2 = 1(x - 1) \quad \Rightarrow \quad y = x + 1$$

• 将直线方程 $y = x + 1$ 代入曲线方程 $y^2 = x^3 - 7x + 10$：

$$(x + 1)^2 = x^3 - 7x + 10$$

展开：

$$x^2 + 2x + 1 = x^3 - 7x + 10$$

整理得到：

$$x^3 - x^2 - 9x + 9 = 0$$

解这个方程得到根 $x = 1$、$x = -3$ 和 $x = 3$，所以 $P + Q = (3, -2)$

Q=nP标量乘法

椭圆曲线计算：$nP = 2P$

已知椭圆曲线：

$$y^2 = x^3 - 7x + 10$$

点 $P = (1, 2)$，计算 $2P = P + P$。

---

1. 验证 $P = (1, 2)$ 是否在曲线上

将 $x = 1, y = 2$ 代入椭圆曲线方程：

$$y^2 = x^3 - 7x + 10$$

$$2^2 = 1^3 - 7 \cdot 1 + 10$$

$$4 = 1 - 7 + 10 = 4$$

验证成立，因此 $P = (1, 2)$ 是椭圆曲线上的点。

---

2. 计算 $2P = P + P$

（1）切线的斜率

当计算 $2P$ 时，需要用切线法。在点 $P = (1, 2)$ 处，椭圆曲线的导数为：

$$\frac{dy}{dx} = \frac{3x^2 - 7}{2y}$$

在 $P = (1, 2)$ 处，斜率为：

$$m = \frac{3x^2 - 7}{2y} = \frac{3 \cdot 1^2 - 7}{2 \cdot 2} = \frac{3 - 7}{4} = -1$$

（2）切线方程

切线的方程为：

$$y - y_1 = m(x - x_1)$$

代入 $P = (1, 2)$ 和 $m = -1$：

$$y - 2 = -1(x - 1) \implies y = -x + 3$$

（3）切线与椭圆曲线的交点

将切线方程 $y = -x + 3$ 代入椭圆曲线方程 $y^2 = x^3 - 7x + 10$：

$$(-x + 3)^2 = x^3 - 7x + 10$$

展开并整理：

$$x^2 - 6x + 9 = x^3 - 7x + 10$$

$$x^3 - x^2 - x + 1 = 0$$

已知 $x = 1$ 是根（对应点 $P = (1, 2)$），对多项式进行因式分解：

$$x^3 - x^2 - x + 1 = (x - 1)(x^2 - 1) = (x - 1)(x - 1)(x + 1)$$

因此，切线与椭圆曲线的交点为 $x = 1$ 和 $x = -1$。其中：

• $x = 1$ 是 $P$ 自身的点。
• $x = -1$ 对应另一个交点。

（4）计算点 $R'$ 的坐标

当 $x = -1$ 时，代入椭圆曲线方程 $y^2 = x^3 - 7x + 10$ 计算 $y$：

$$y^2 = (-1)^3 - 7(-1) + 10 = -1 + 7 + 10 = 16$$

$$y = \pm 4$$

因此，交点为 $R' = (-1, 4)$ 或 $(-1, -4)$。由于加法规则需要取对称点：

$$2P = (-1, -4)$$

点 $P = (1, 2)$ 在椭圆曲线 $y^2 = x^3 - 7x + 10$ 上，计算得：

$$2P = (-1, -4)$$

$y^2 = x^3 - 7x + 10$ 进行求导

我们将 $y^2 = x^3 - 7x + 10$ 进行求导，目的是找到 $\frac{dy}{dx}$。这是一个隐函数，需使用 隐函数求导法。

步骤 1：对等式两边同时对 $x$ 求导

对等式 $y^2 = x^3 - 7x + 10$ 两边求导：

$$\frac{d}{dx}(y^2) = \frac{d}{dx}(x^3 - 7x + 10)$$

步骤 2：分别求导

• 左边：根据链式法则，$\frac{d}{dx}(y^2) = 2y \frac{dy}{dx}$。
• 右边：$\frac{d}{dx}(x^3 - 7x + 10) = 3x^2 - 7$。

将结果代入：

$$2y \frac{dy}{dx} = 3x^2 - 7$$

步骤 3：解出 $\frac{dy}{dx}$

将 $\frac{dy}{dx}$ 单独表示：

$$\frac{dy}{dx} = \frac{3x^2 - 7}{2y}$$

最终结果：

$$\frac{dy}{dx} = \frac{3x^2 - 7}{2y}$$

椭圆曲线计算：$nP = 3P$

椭圆曲线方程

已知椭圆曲线：

$$y^2 = x^3 - 7x + 10$$

点 $P = (1, 2)$，计算 $3P = P + P + P$。

---

1. 计算 $2P$

根据之前的计算，已知：

$$2P = (-1, -4)$$

---

2. 计算 $3P = 2P + P$

点 $2P = (-1, -4)$，点 $P = (1, 2)$。根据椭圆曲线加法规则，需要计算直线经过 $2P$ 和 $P$ 的斜率，然后求交点。

（1）斜率

斜率公式为：

$$m = \frac{y_2 - y_1}{x_2 - x_1}$$

其中，$2P = (-1, -4)$，$P = (1, 2)$，则：

$$m = \frac{2 - (-4)}{1 - (-1)} = \frac{2 + 4}{1 + 1} = \frac{6}{2} = 3$$

（2）直线方程

直线经过点 $P = (1, 2)$，斜率为 $m = 3$，其方程为：

$$y - y_1 = m(x - x_1)$$

$$y - 2 = 3(x - 1) \implies y = 3x - 3 + 2 \implies y = 3x - 1$$

（3）直线与椭圆曲线的交点

将直线方程 $y = 3x - 1$ 代入椭圆曲线方程 $y^2 = x^3 - 7x + 10$：

$$(3x - 1)^2 = x^3 - 7x + 10$$

展开并整理：

$$9x^2 - 6x + 1 = x^3 - 7x + 10$$

$$x^3 - 9x^2 - x + 9 = 0$$

（4）因式分解

已知 $x = 1$ 是根（对应点 $P$），对多项式进行因式分解：

$$x^3 - 9x^2 - x + 9 = (x - 1)(x^2 - 8x - 9)$$

解 $x^2 - 8x - 9 = 0$，使用求根公式：

$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} = \frac{-(-8) \pm \sqrt{(-8)^2 - 4(1)(-9)}}{2(1)}$$

$$x = \frac{8 \pm \sqrt{64 + 36}}{2} = \frac{8 \pm 10}{2}$$

$$x = 9 \quad \text{或} \quad x = -1$$

因此，交点的 $x$ 坐标为 $x = 1$、$x = -1$ 和 $x = 9$。排除 $x = 1$（点 $P$）和 $x = -1$（点 $2P$），取 $x = 9$。

（5）计算 $3P$ 的 $y$ 坐标

将 $x = 9$ 代入椭圆曲线方程 $y^2 = x^3 - 7x + 10$：

$$y^2 = 9^3 - 7 \cdot 9 + 10 = 729 - 63 + 10 = 676$$

$$y = \pm 26$$

由于加法规则需要取对称点，$3P$ 的坐标为：

$$3P = (9, -26)$$

---

3. 结果

点 $P = (1, 2)$ 在椭圆曲线 $y^2 = x^3 - 7x + 10$ 上，计算得：

$$3P = (9, -26)$$

椭圆曲线($\mathbb{F}_q$)

R=P+Q

计算 $R = P + Q$ 详细过程

给定椭圆曲线方程：

$$y^2 = x^3 + 2x + 3 \pmod{97}$$

点 $P(x_1, y_1) = (17, 10)$ 和 $Q(x_2, y_2) = (95, 31)$。

步骤 1: 确定斜率 $\lambda$

当 $P \neq Q$ 时，斜率 $\lambda$ 的公式为：

$$\lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod{97}$$

代入 $P$ 和 $Q$ 的坐标：

$$\lambda = \frac{31 - 10}{95 - 17} \pmod{97}$$

计算差值：

$$\lambda = \frac{21}{78} \pmod{97}$$

需要计算 $78^{-1} \pmod{97}$（即 $78$ 的模反元素）。

步骤 2: 计算 $78^{-1} \pmod{97}$

使用扩展欧几里得算法求解 $78^{-1} \pmod{97}$：

• 97 = 1 × 78 + 19
• 78 = 4 × 19 + 2
• 19 = 9 × 2 + 1
• 2 = 2 × 1 + 0

回代求反元素：

$$1 = 19 - 9 \times 2 = 19 - 9 \times (78 - 4 \times 19) = 37 \times 19 - 9 \times 78$$

$$1 = 37 \times (97 - 78) - 9 \times 78 = 37 \times 97 - 46 \times 78$$

因此，$78^{-1} \equiv -46 \equiv 51 \pmod{97}$。

步骤 3: 计算斜率 $\lambda$

现在可以计算斜率：

$$\lambda = 21 \times 51 \pmod{97}$$

计算：

$$21 \times 51 = 1071$$

$$1071 \pmod{97} = 1071 - 97 \times 11 = 1071 - 1067 = 4$$

所以，$\lambda = 4 \pmod{97}$。

步骤 4: 计算点 $R(x, y)$

根据公式计算点 $R$ 的坐标：

$$x_R = \lambda^2 - x_1 - x_2 \pmod{97}$$

$$x_R = 4^2 - 17 - 95 \pmod{97} = 16 - 17 - 95 \pmod{97} = -96 \pmod{97}$$

$$x_R = 97 - 96 = 1 \pmod{97}$$

然后计算 $y_R$：

$$y_R = \lambda (x_1 - x_R) - y_1 \pmod{97}$$

$$y_R = 4 \times (17 - 1) - 10 \pmod{97} = 4 \times 16 - 10 \pmod{97} = 64 - 10 \pmod{97}$$

$$y_R = 54 \pmod{97}$$

结果

因此，$R = P + Q$ 的坐标是：

$$R(1, 54)$$

R=nP