椭圆曲线 零知识证明的基础

Site

1. 零知识证明 - 椭圆曲线基础
2. 椭圆曲线 ECC 签名算法的数学原理
3. Elliptic Curve point addition (ℝ)
4. https://www.cnblogs.com/weikunpeng/p/14117834.html

椭圆曲线不是椭圆啊 🤣

确实，椭圆曲线并不是椭圆形的曲线，这是一个常见的误解。椭圆曲线的名称来源于“椭圆积分”，这是在研究椭圆周长时首次引入的积分类型，而椭圆曲线在数学和密码学中的定义与椭圆形状无关。

椭圆曲线的定义

在数学中，特别是在代数几何和密码学中，椭圆曲线是一个平滑的，非奇异的二次维射代数曲线，它满足下列形式的方程： $y^2 = x^3 + ax + b$ 这里 $a$ 和 $b$ 是系数，这个方程需要满足一个条件，即其判别式 $\Delta = -16(4a^3 + 27b^2)$ 不为零，这确保了曲线没有奇点（即没有尖点或自相交点）。

椭圆曲线的性质

椭圆曲线上的点（包括一个无穷远点，通常记为 $O$，作为曲线上的单位元或“零点”）形成了一个阿贝尔群，这意味着其上的加法运算满足以下性质：

• 封闭性：任意两点的和仍然是曲线上的一个点。
• 存在单位元：对于任何曲线上的点 $P$，存在 $O$ 使得 $P + O = P$。
• 存在逆元：对于每个点 $P = (x, y)$，存在一个点 $-P = (x, -y)$，使得 $P + (-P) = O$。
• 交换律：$P + Q = Q + P$。
• 结合律：$(P + Q) + R = P + (Q + R)$。

椭圆曲线的应用

在密码学中，椭圆曲线被用于椭圆曲线密码学（ECC），它是基于椭圆曲线上的点加法运算的困难性（即椭圆曲线离散对数问题）构建的。ECC 提供了与传统公钥加密方法相比在相同密钥长度下更高的安全性，因此可以使用更短的密钥来达到相同的安全级别，从而提高效率。

因此，尽管名字可能会引起混淆，椭圆曲线是现代密码学中非常重要的一个概念，与真正的椭圆形状没有直接关系。

---

公私钥密钥对都是在椭圆曲线上的？

在椭圆曲线密码学（Elliptic Curve Cryptography, ECC）中，公私钥密钥对确实都与椭圆曲线有关，但它们的具体形式和关系有所不同。这里是基本的概念和流程：

私钥

私钥通常是一个随机选择的大整数。在 ECC 中，私钥 $d$ 是一个介于 1 和 $n-1$ 之间的整数，其中 $n$ 是椭圆曲线的阶，即曲线上点的总数。私钥是保密的，只有密钥的持有者知道。

公钥

公钥在椭圆曲线密码学中是一个点，不是一个数。具体来说，公钥 $Q$ 是椭圆曲线上的一个点，它是基点 $G$（一个预先定义的曲线上的点，通常在曲线的标准定义中给出）与私钥 $d$ 的乘积。即 $Q = dG$，这里的乘法是指椭圆曲线上的标量乘法。

关系和运算

• 生成密钥对：首先随机选择一个私钥 $d$，然后计算公钥 $Q = dG$。这个操作涉及椭圆曲线上的点乘运算。
• 加密：使用接收者的公钥对数据进行加密，确保只有拥有对应私钥的人才能解密。
• 解密：使用自己的私钥对接收到的加密数据进行解密。
• 签名生成：使用自己的私钥生成对数据的数字签名。
• 签名验证：使用公钥来验证数字签名的真实性。

优势

椭圆曲线密码学的主要优势之一是它相比于其他类型的非对称加密算法（如 RSA）在相同安全级别下可以使用更短的密钥长度。这意味着在处理速度和存储需求上可以更加高效。

总结来说，椭圆曲线密码学中的公私钥密钥对都与椭圆曲线紧密相关，私钥是一个随机数，而公钥则是曲线上的一个点。这种密钥对的关系基于椭圆曲线上的数学运算，特别是点乘运算。

$Q = dG$ 一定在椭圆曲线上？

是的，公钥 $Q = dG$ 一定在椭圆曲线上。这是由椭圆曲线的数学性质决定的。下面是详细解释：

椭圆曲线的定义

椭圆曲线通常在一个有限域上定义，例如 $\mathbb{F}\_p$（素数 $p$ 定义的有限域）。曲线的一般形式（在仿射坐标中）为： $y^2 = x^3 + ax + b$ 这里的 $a$ 和 $b$ 是曲线参数，$x$ 和 $y$ 是曲线上点的坐标。

点加运算

椭圆曲线上定义了一个“加法”运算，用于计算曲线上任意两点 $P$ 和 $Q$ 的和 $R = P + Q$。这个加法运算满足交换律和结合律。如果 $P$ 和 $Q$ 都在曲线上，那么它们的和 $R$ 也一定在曲线上。

标量乘法

椭圆曲线上的标量乘法可以视为点加运算的重复。例如，计算 $dG$ 实际上是将点 $G$ 与自身相加 $d$ 次。由于点加运算的结果仍然在曲线上，重复这一运算仍然会产生曲线上的点。因此，无论 $d$ 是多少，$dG$ 的结果必然是曲线上的一个点。

基点 $G$

基点 $G$ 是椭圆曲线上的一个特定点，通常在曲线的定义中给出。这个点的选择保证了它有良好的数学性质，如具有较大的阶（即需要多次将 $G$ 加到自身才能回到起点）。基点 $G$ 和它的所有标量乘积 $dG$ 由定义都在椭圆曲线上。

结论

因此，$Q = dG$（公钥）一定在椭圆曲线上，因为它是通过在曲线上定义的点 $G$ 上执行定义良好的曲线运算（标量乘法）得到的。这是椭圆曲线密码学中非常重要的性质，确保了公钥的合法性和操作的安全性。

点加运算推导

椭圆曲线上的加法运算的推导涉及到几何和代数的一些概念。这里我将简要介绍如何推导两个曲线上的点 $P$ 和 $Q$ 的和 $R = P + Q$。我们假设曲线的方程为 $y^2 = x^3 + ax + b$，定义在实数域或某个有限域上。

推导过程

1. 点加运算

假设我们有两个不同的点 $P = (x_1, y_1)$ 和 $Q = (x_2, y_2)$，且 $P \neq Q$。我们要找到 $R = P + Q$。

1. 计算斜率： 斜率 $\lambda$ 的计算基于直线的斜率公式，由于 $P$ 和 $Q$ 在曲线上，我们可以通过连接这两点得到一条直线。斜率 $\lambda$ 由下式给出：

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

2. 计算 $R$ 的坐标： 设 $R = (x_3, y_3)$，则 $x_3$ 和 $y_3$ 可以通过以下公式计算：

   $x_3 = \lambda^2 - x_1 - x_2$

   $y_3 = \lambda (x_1 - x_3) - y_1$

   注意 $y_3$ 的表达式是通过将 $x_3$ 值代入直线方程 $y - y_1 = \lambda (x - x_1)$ 得到的。

2. 点加自身（点倍运算，即 $P + P = 2P$）

如果 $P = Q$，则我们需要计算点 $P$ 加自身的结果 $2P$。这通常称为点的“倍化”。

1. 计算斜率： 斜率 $\lambda$ 在这种情况下由下式给出，这里使用了曲线方程的导数：

   $\lambda = \frac{3x_1^2 + a}{2y_1}$

2. 计算 $2P$ 的坐标： 使用与上面相同的 $x_3$ 和 $y_3$ 的公式：

   $x_3 = \lambda^2 - 2x_1$

   $y_3 = \lambda (x_1 - x_3) - y_1$

性质

• 交换律：$P + Q = Q + P$。这是因为无论 $P$ 和 $Q$ 的顺序如何，斜率 $\lambda$ 和 $x_3, y_3$ 的计算都是相同的。
• 结合律：$(P + Q) + R = P + (Q + R)$。这可以通过代数验证，但在实际应用中通常通过软件来保证其准确性。

这样，我们就可以看到椭圆曲线上的加法运算是如何定义的，并且确保了运算结果仍然位于椭圆曲线上。

P、Q、R 都在椭圆上

在椭圆曲线 $y^2 = x^3 + ax + b$ 上计算两个点 $P = (x_1, y_1)$ 和 $Q = (x_2, y_2)$ 的和 $R = (x_3, y_3)$ 涉及到计算斜率和 $R$ 的坐标。这里将详细解释如何进行这些计算：

1. 计算斜率（$\lambda$）

斜率 $\lambda$ 的计算取决于两种情况：当 $P$ 和 $Q$ 是不同的点时，以及当 $P$ 和 $Q$ 是相同的点（点加自身，即点倍运算）时。

当 $P \neq Q$ 时：

斜率 $\lambda$ 是通过连接 $P$ 和 $Q$ 的直线的斜率来计算的，公式为：

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

这里，分子是 $y$ 坐标的差，分母是 $x$ 坐标的差。

当 $P = Q$ 时（点倍运算）：

此时，斜率是通过曲线在点 $P$ 处的切线的斜率来计算的。使用函数 $f(x) = x^3 + ax + b$ 的导数 $f'(x)$ 来帮助找到这个斜率：

$\lambda = \frac{3x_1^2 + a}{2y_1}$

这里，分子是 $x_1$ 处 $f(x)$ 的导数，分母是 $2y_1$，即点 $P$ 的 $y$ 坐标的两倍。

2. 计算 $R = (x_3, y_3)$

使用斜率 $\lambda$，我们可以计算 $R$ 的 $x$ 坐标和 $y$ 坐标。

$x_3$ 的计算：

$x_3 = \lambda^2 - x_1 - x_2$

这里 $\lambda^2$ 是斜率的平方，从中减去 $P$ 和 $Q$ 的 $x$ 坐标。

$y_3$ 的计算：

$y_3 = \lambda(x_1 - x_3) - y_1$

这里 $\lambda(x_1 - x_3)$ 是通过点斜式 $y - y_1 = \lambda(x - x_1)$ 计算 $x_3$ 处的 $y$ 值，然后从中减去 $y_1$。

结论

通过这些步骤，我们可以确保 $R$ 也在椭圆曲线上。这种加法运算保证了椭圆曲线上的闭合性，即所有通过这种方式计算的点都仍然位于曲线上。这也是椭圆曲线加密（ECC）中关键的数学基础。

$Q = dG$ 怎么推导的

在椭圆曲线密码学（ECC）中，表达式 $Q = dG$ 是基于椭圆曲线上的点乘运算。这里，$Q$ 和 $G$ 都是椭圆曲线上的点，而 $d$ 是一个整数。这个表达式的含义是将点 $G$ 与自身相加 $d$ 次，这是椭圆曲线上的标量乘法的一个例子。这个操作是许多椭圆曲线密码系统的基础，特别是在公钥加密和数字签名算法中。下面是这个过程的详细解释：

点乘运算

标量乘法，也称为点乘运算，定义为将椭圆曲线上的一个点 $G$ 与一个整数 $d$ 相乘，结果是点 $G$ 加到自身 $d$ 次的总和： [ Q = dG = G + G + \ldots + G ]（共 $d$ 次）

这里的 $G$ 通常被选为椭圆曲线群的生成元，这意味着通过从 $G$ 出发并应用椭圆曲线上的加法运算，可以生成曲线上的所有其他点。

ECC 中的作用

在椭圆曲线密码学中，$G$ 是一个公开知道的基点，$d$ 是私钥，而 $Q$ 是由私钥 $d$ 生成的公钥。因此，只要知道 $G$ 和 $d$ ，就可以通过重复加 $G$ 到自己上 $d$ 次来计算 $Q$ 。但是，给定 $G$ 和 $Q$ ，在没有其他信息的情况下，想要找出 $d$ 是非常困难的。这个问题被称为椭圆曲线离散对数问题，是椭圆曲线密码学安全性的基础。

计算效率

尽管定义上 $Q = dG$ 看起来需要进行多次点加运算，但在实际应用中，为了提高计算效率，通常使用称为“倍增法”（double-and-add method）的算法来计算这个乘法。这个方法类似于二进制乘法，可以在对数时间内完成计算。

总结

表达式 $Q = dG$ 在椭圆曲线密码学中描述了如何从私钥 $d$ 和基点 $G$ 计算出公钥 $Q$ 。这个过程利用了椭圆曲线上的点加法和标量乘法的性质，同时保证了基于椭圆曲线离散对数问题的计算难度，为现代加密通信提供了坚实的安全基础。