有限域上的椭圆曲线

RareSkills
发布于 2023-09-21 21:52
阅读 10

文章详细介绍了有限域上的椭圆曲线，包括它们的绘制、数学性质以及在密码学中的应用。通过多个示例和代码，展示了如何生成和操作这些曲线，并解释了其与有限域的循环群特性。

# 限域上的椭圆曲线是什么样子的？

可视化平滑椭圆曲线很容易，但限域上的椭圆曲线是什么样子的呢？

以下是 $y² = x³ + 3 \pmod {23}$ 的图形。

![Plot of y² = x³ + 3 \\\\pmod 23](https://img.learnblockchain.cn/2025/02/26/935a00_9b8594bdeb9b4eb580847f1d5ffcd6c0~mv2.png)

因为我们只允许整数输入（更具体地说，是有限域元素），所以我们不会获得平滑的图形。

并非每个 $x$ 值在我们解方程时都能得到一个整数 $y$ 值，因此在该值 $x$ 上不会有点。在上面的图中可以看到这样的间隙。

生成此图形的代码稍后将提供。

#### 素数大幅改变图形

以下是关于 $y² = x³ + 3$ 在模 11、23、31 和 41 下的图形。模数越高，图形包含的点越多，图形就越复杂。

![Plot of elliptic curves modulo 11, 23](https://img.learnblockchain.cn/2025/02/26/935a00_e592040ff7174e81a1f32ed7ed70a150~mv2.png)

![Plot of elliptic curves modulo 23, 31](https://img.learnblockchain.cn/2025/02/26/935a00_382bd8455deb45efba13fdb7d77517b4~mv2.png)

我们在上一篇文章中建立的椭圆曲线点通过“连接和翻转”操作形成一个群。当我们在一个有限域上执行这一操作时，它仍然保持为一个群，但它变成了一个循环群，这对于我们的应用非常有用。不幸的是，为什么它是循环的将需要一些非常复杂的数学，所以你现在只能接受这一点。但这应该不会太令人惊讶。我们有有限数量的点，所以通过执行 $(x + 1)G, (x + 2)G, \ldots, (x + \text{order} - 1)G$ 生成每个点至少应是合理的。

在密码学的应用中，$p$ 需要很大。在实际中，它超过 200 位。我们将在后面的部分中重新访问这一点。

### 背景

#### 域元素

我们在本文中将频繁使用“域元素”这一术语，希望你已经熟悉这个术语，尤其是从我们之前的教程（特别是关于 [有限域](https://learnblockchain.cn/article/11315) 的课程）。如果没有，它是一个在模运算内部的正整数。

也就是说，如果我们在模 11 下做加法，那么该集合中的有限域元素为 $\{0, 1, \ldots, 9, 10\}$。虽然我们所使用的数据类型是整数，但说“整数”并不准确。在对素数执行模加法时，不能有负的域元素（虽然整数可以是负数）。在有限域下，“负”数字仅仅是另一个数字的加法逆元，即相加后结果为零的数字。例如，在模 11 的有限域中，4 可以被视为“-7”，因为 $7 + 4 \pmod{11}$ 为 0，这在常规数字中也是 7 + (-7) 等于零的对比。

在有理数域上，乘法的身份元素是 1，而一个数字的逆是分子和分母翻转。例如，$500/303$ 是 $303/500$ 的逆，因为如果你对它们相乘，你将得到 1。

在有限域中，一个元素的逆是与之相乘以获得有限域元素 1 的数字。例如，在模 23 下，6 是 4 的逆，因为当你将它们相乘模 23 后，结果为 1。当域的阶数为素数时，每个数字（除了零）都有一个逆。

#### 循环群

一个循环 [群](https://www.rareskills.io/group-theory) 是一个群，其每个元素都可以通过从生成元元素开始并反复应用该群的二元运算来计算。

一个非常简单的例子是模 11 下的整数加法。如果你的生成元是 1，并且你不断地将生成元加给自己，那么你就可以从 0 到 10 的群中生成每个元素。

说椭圆曲线点形成一个循环群（在椭圆曲线加法下）意味着我们可以将有限域中的每个数字表示为椭圆曲线点，并像在有限域中对常规整数那样相加它们。

即，

$5 + 7 \pmod p$ 与 $5G + 7G$ 是同构的。

这只适用于点数为素数的有限域上的椭圆曲线，这正是我们在实践中使用的曲线。我们将在后面再次讨论这个问题。

### BN128 公式

BN128 曲线（以太坊预编译用来验证 ZK 证明）如下所示：

$$ p = 21888242871839275222246405745257275088696311157297823662689037894645226208583 $$

$$ y² = x³ + 3 \pmod p $$

这里 $p$ 是域模数。

`field_modulus` 不应与曲线阶数混淆，后者是曲线点的数量。

对于 bn128 曲线，曲线阶数如下：

```python
from py_ecc.bn128 import curve_order
## 21888242871839275222246405745257275088548364400416034343698204186575808495617
print(curve_order)
```

域模数非常大，这使得实验变得笨拙。在下一个部分中，我们将使用相同的公式，但模数较小，以培养对有限域中椭圆曲线点的直观理解。

### 生成椭圆曲线循环群 $y² = x³ + 3 \pmod {11}$

要解决上述方程并确定哪些 $(x, y)$ 点在曲线上，我们需要计算 $\sqrt{(x³ + 3)} \pmod{11}$。

#### 跨模平方根

我们使用 [Tonelli Shanks 公式](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) 来计算模平方根。如果你想知道该算法如何工作，可以阅读相关资料，但现在可以将其视为一个黑盒，它计算模数上一个元素的平方根，或者告知你平方根不存在。

例如，模 11 的 5 的平方根是 4 $(4 \times 4 \mod 11 = 5)$，但模 11 的 6 没有平方根。 （鼓励读者通过暴力搜索来验证这一点）。

平方根通常有两个解，一个正解和一个负解。虽然在有限域中没有负号的数字，但我们仍然可以在逆元的意义上谈论“负数”。

你可以在网上找到实现上述算法的代码，但为了避免在本教程中放入大量代码，我们将安装一个 Python 库。

```bash
python3 -m pip install libnum
```

安装完 [libnum](https://pypi.org/project/libnum/) 后，我们可以运行以下代码来演示其用法。

```python
from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power

## 函数接受的参数# has_sqrtmod_prime_power(n, field_mod, k)，其中 n**k，
## 但我们对模域中的幂没有兴趣，所以我们将 k 设置为 1
## 检查 sqrt(8) mod 11 是否存在
print(has_sqrtmod_prime_power(8, 11, 1))
## False

## 检查 sqrt(5) mod 11 是否存在
print(has_sqrtmod_prime_power(5, 11, 1))
## True

## 计算 sqrt(5) mod 11
print(list(sqrtmod_prime_power(5, 11, 1)))
## [4, 7]

assert (4 ** 2) % 11 == 5
assert (7 ** 2) % 11 == 5

## 我们预计 4 和 7 是互为反元素，因为在“常规”数学中，平方根的两个解是 sqrt 和 -sqrt。
assert (4 + 7) % 11 == 0
```

现在我们知道如何计算模平方根，我们可以遍历 $x$ 的值并根据公式 $y² = x³ + b$ 计算 $y$。求解 $y$ 只需对两边进行模平方根（如果存在）并保存结果 $(x, y)$ 的对以便后续绘制。

让我们创建一个简单的椭圆曲线图

$$y² = x³ + 3 \pmod {11}$$

```python
import libnum
import matplotlib.pyplot as plt

def generate_points(mod):
    xs = []
    ys = []
    def y_squared(x):
        return (x**3 + 3) % mod

for x in range(0, mod):
        if libnum.has_sqrtmod_prime_power(y_squared(x), mod, 1):
            square_roots = libnum.sqrtmod_prime_power(y_squared(x), mod, 1)

# 我们可能会有两个解
            for sr in square_roots:
                ys.append(sr)
                xs.append(x)
    return xs, ys

xs, ys = generate_points(11)
fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod p)');
fig.set_size_inches(6, 6);
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
plt.grid()
plt.scatter(xs, ys)
plt.plot();
```

图形结果如下所示：

![Plot of y² = x³ + 3 $mod 11$](https://img.learnblockchain.cn/2025/02/26/935a00_2355ae79d450498eb3ee5b6721634b43~mv2.png)

一些观察：

* 不会有任何 x 或 y 值大于或等于我们使用的模数
  * 就像实值图一样，模数图“看起来是对称的”

### 椭圆曲线点加法

更有趣的是，我们的“连接点和翻转”操作来计算椭圆曲线仍然有效！

但是考虑到我们在有限域上执行这一步，这并不奇怪。我们在实数上的公式使用加法和乘法的正常域运算。虽然我们使用平方根来判断一个点是否在曲线上，而平方根并不是有效的域运算符，但我们并不使用平方根来计算点的加法和翻倍。

读者可以通过从上面的图中选择两个点，然后将它们插件于以下代码中来验证这一点，看看它们总是落在另一个点上（或者如果这些点互为反元素，则落在无穷点上）。这些公式取自 [维基百科的椭圆曲线点乘法页面](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication)。

```python
def double(x, y, a, p):
    lambd = (((3 * x**2) % p ) *  pow(2 * y, -1, p)) % p
    newx = (lambd**2 - 2 * x) % p
    newy = (-lambd * newx + lambd * x - y) % p
    return (newx, newy)

def add_points(xq, yq, xp, yp, p, a=0):
    if xq == yq == None:
        return xp, yp
    if xp == yp == None:
        return xq, yq

assert (xq**3 + 3) % p == (yq ** 2) % p, "q不在曲线上"
    assert (xp**3 + 3) % p == (yp ** 2) % p, "p不在曲线上"

if xq == xp and yq == yp:
        return double(xq, yq, a, p)
    elif xq == xp:
        return None, None

lambd = ((yq - yp) * pow((xq - xp), -1, p) ) % p
    xr = (lambd**2 - xp - xq) % p
    yr = (lambd*(xp - xr) - yp) % p
    return xr, yr
```

以下是有限域中“连接与翻转”的一些可视化效果：

![examples of EC addition in a finite field](https://img.learnblockchain.cn/2025/02/26/elliptic-curve-finite-fields-example.jpg)

### 循环群中的每个椭圆曲线点都有一个“数字”

一个循环群的定义是可以通过反复将生成元相加来生成。

让我们用 $y² = x³ + 3 \pmod {11}$ 和生成点 $(4, 10)$ 来做一个实际示例。

使用上面的 Python 函数，我们可以从点 $(4, 10)$ 开始，生成群中的每个点：

```python
## 对于我们的目的，(4, 10) 是生成点 G
next_x, next_y = 4, 10
print(1, 4, 10)
points = [(next_x, next_y)]
for i in range(2, 12):
    # 反复将 G 加到下一个点以生成所有元素
    next_x, next_y = add_points(next_x, next_y, 4, 10, 11)
    print(i, next_x, next_y)
    points.append((next_x, next_y))
```

输出将是

```bash
0 4 10
1 7 7
2 1 9
3 0 6
4 8 8
5 2 0
6 8 3
7 0 5
8 1 2
9 7 4
10 4 1
11 None None
12 4 10 # 注意这是第一个点
```

观察到 $(\text{order} + 1)G = G$。就像模加法一样，当我们“溢出”时，循环会重新开始。

这里 `None` 表示无穷远点，这确实是群的一部分。将无穷远点与生成点相加返回生成点，这就是身份元应有的行为。

我们可以为每个点分配一个“数字”，根据我们加到自身生成该点的次数。

我们可以使用以下代码来绘制曲线并在旁边标注数字。

```python
xs11, ys11 = generate_points(11)

fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod 11)');
fig.set_size_inches(13, 6);

ax1.set_title("模 11")
ax1.scatter(xs11, ys11, marker='o');
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
ax1.grid()

for i in range(0, 11):
    plt.annotate(str(i+1), (points[i][0] + 0.1, points[i][1]), color="red");
```

红色文本可以被视为从身份元开始，还有多少次我们将生成元加到自身。

![plot of y^2 = x^3 + 3 $mod 11$ with the points numbered](https://img.learnblockchain.cn/2025/02/26/935a00_3e9b90d38e9c4c4a82b34d138fa9f49c~mv2.png)

#### 点的逆仍然是垂直对称的

有一个有趣的观察：注意那些共享相同 x 值的点相加等于 12，这对应于身份元（$12 \mod 12 = 0$）。如果我们将点 $(4, 1)$（曲线图中的第 11 个点）加到 $(4, 10)$，我们将得到无穷远点，这将是群中的第 12 个元素。

#### 阶数不是模数

在本例中，群的阶数是 12（群中椭圆曲线点的总数），尽管椭圆曲线的公式是在模 11 下。这将多次强调，但你不应假设椭圆曲线的模数是群阶。但是，你可以使用 [哈斯定理](https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves) 从域模数估计曲线的阶数范围。

#### 如果点的数量是素数，则点的加法行为类似于有限域

在上图中，有 12 个点（包括 0）。在模 12 下的加法不是有限域，因为 12 不是素数。

但是，如果我们仔细选择曲线的参数，可以创建一个椭圆曲线，使得点对应于有限域中的元素。也就是说，曲线的阶等于有限域的阶。

例如，$y^2 = x^3 + 7 \pmod {43}$ 创建了一个总共有 31 个点的曲线，如下图所示：

![elliptic curve with 31 points](https://img.learnblockchain.cn/2025/02/26/elliptic-curve-finitie-order-31.jpg)

当曲线的阶与有限域的阶匹配时，**你在有限域中所做的每一个操作在椭圆曲线中都有一个同构的对应**。

要从有限域转换到椭圆曲线，我们选择一个点（随意）作为生成元，然后将有限域中的元素与生成元相乘。

### 乘法实际上是重复加法

没有椭圆曲线点的乘法。当我们说“标量乘法”时，我们实际上是指重复加法。你不能把两个椭圆曲线点相乘（虽然，通过 [双线性配对](https://learnblockchain.cn/article/11321)，你可以做到这一点，但这是我们稍后要涉及的内容）。

当我们使用 Python 库执行 `multiply(G1, x)` 时，这实际上与执行 `G1 + G1 + … + G1` `x` 次是相同的。在底层，我们实际上并不进行这么多次自加，而是使用一些聪明的技巧进行点翻倍，以在对数时间内完成操作。

例如，如果我们想计算 135G，我们实际上将高效计算以下值并缓存它们，
    
    G, 2G, 4G, 8G, 16G, 32G, 64G, 128G

…然后求和 128G + 4G + 2G + G = 135G。

当我们说 `5G + 6G = 11G` 时，我们实际上只是将 G 加到自身 11 次。使用上面所示的技巧，我们可以通过对数数量的计算来计算 11G，但最终，这仅仅是重复的加法。

### Python bn128 库

EVM 实现 pyEVM 用于椭圆曲线预编译的库是 `py_ecc`，我们将大量依赖该库。下面的代码展示了生成点的样子，并演示了一些加法和标量乘法。

以下是 G1 点的样子：

```python
from py_ecc.bn128 import G1, multiply, add, eq, neg

print(G1)
## (1, 2)

print(add(G1, G1))
## (1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)

print(multiply(G1, 2))
##(1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)

## 10G + 11G = 21G
assert eq(add(multiply(G1, 10), multiply(G1, 11)), multiply(G1, 21))
```

尽管这些数字很大且难以阅读，但我们可以看到，将一个点自身相加的结果与将一个点“乘以”2得到的值是一样的。上面两个点显然是同一个点。元组仍然是一个 $(x, y)$ 对，只是在一个非常大的域中。

上面打印的数字很大，其原因如下。我们不希望攻击者能够从椭圆曲线点中推导出生成它的域元素。如果我们循环群的阶数太小，攻击者就可以使用暴力破解来查找。

以下是前 1000 个点的图形：

![plot of first 1000 points of bn128](https://img.learnblockchain.cn/2025/02/26/935a00_d9bd567f47c247f588061305dc97940e~mv2.png)

产生上图的代码如下：

```python
import matplotlib.pyplot as plt
from py_ecc.bn128 import G1, multiply, neg
import math
import numpy as np
xs = []
ys = []
for i in range(1,1000):
    xs.append(i)
    ys.append(int(multiply(G1, i)[1]))
    xs.append(i)
    ys.append(int(neg(multiply(G1, i))[1]))
plt.scatter(xs, ys, marker='.')
```

这可能看起来很可怕，但与我们在前面部分所做的唯一不同之处在于使用了更大的模数和不同的生成元。

#### 库中的加法

`py_ecc` 库使点加法变得便利，语法应该不言而喻：

```python
from py_ecc.bn128 import G1, multiply, add, eq

## 5 = 2 + 3
assert eq(multiply(G1, 5), add(multiply(G1, 2), multiply(G1, 3)));
```

有限域中的加法与椭圆曲线点之间的加法是同构的（当它们的阶相等时）。由于离散对数，另一方可以在不知道生成这些点的域元素的情况下将椭圆曲线点相加。

在此时，希望读者对加法椭圆曲线点有了良好的理论和实践理解，因为现代零知识算法在这方面的依赖非常重。

### 关于模加法与椭圆曲线加法之间同态性的实现细节

我们在这里需要进行术语的仔细区分：

**域模数**是我们在曲线上进行的模运算。**曲线阶**是曲线上的点的数量。

如果你以某个点 $R$ 为起始点并加上曲线阶数 $o$，你将得到 $R$。如果你加上域模数，你将得到另一个不同的点。

```python
from py_ecc.bn128 import curve_order, field_modulus, G1, multiply, eq

x = 5 # 随机选定
## 这通过
assert eq(multiply(G1, x), multiply(G1, x + curve_order))

## 这不通过
assert eq(multiply(G1, x), multiply(G1, x + field_modulus))
```

这意味着 $(x + y) \mod \text{curve\_order} == xG + yG$。

```python
x = 2 ** 300 + 21
y = 3 ** 50 + 11

## (x + y) == xG + yG
assert eq(multiply(G1, (x + y)), add(multiply(G1, x), multiply(G1, y)))
```

尽管 `x + y` 运算显然会在曲线阶数上“溢出”，但这并无所谓。就像在有限域中一样，这是我们所期望的行为。椭圆曲线乘法隐式执行与在进行乘法之前进行模运算一样的操作。

实际上，如果我们只关心正数，我们甚至不需要执行模运算，以下恒等式也保持成立：

```python
x = 2 ** 300 + 21
y = 3 ** 50 + 11

assert eq(multiply(G1, (x + y) % curve_order), add(multiply(G1, x), multiply(G1, y)))
```

然而，如果我们对模运算使用错误的数字（即不是曲线阶的某个数字），那么如果发生“溢出”，等式则会失效。

```python
x = 2 ** 300 + 21
y = 3 ** 50 + 11 # 这些值足够大以至于会溢出:

assert eq(multiply(G1, (x + y) % (curve_order - 1)), add(multiply(G1, x), multiply(G1, y))), "this breaks"
```

##### 编码有理数

当我们进行模运算时，我们能够编码一个除法的概念。

例如，我们使用常规整数无法做到以下事情。

```python
## 这会抛出异常
eq(add(multiply(G1, 5 / 2), multiply(G1, 1 / 2), multiply(G1, 3)
```

然而，在有限域中，可以将 1/2 理解为 2 的乘法逆。因此，$5 / 2$ 可以被编码为 $5 \cdot \mathsf{inv}(2)$。

在 Python 中，我们可以这样做：

```python
five_over_two = (5 * pow(2, -1, curve_order)) % curve_order
one_half = pow(2, -1, curve_order)

## 实际上 5/2 = 2.5# 2.5 + 0.5 = 3
## 但在有限域中我们这么做
assert eq(add(multiply(G1, five_over_two), multiply(G1, one_half)), multiply(G1, 3))
```

##### 结合律

我们知道群是结合的，因此我们期望以下人体普遍成立：

```python
x = 5
y = 10
z = 15

lhs = add(add(multiply(G1, x), multiply(G1, y)), multiply(G1, z))

rhs = add(multiply(G1, x), add(multiply(G1, y), multiply(G1, z)))

assert eq(lhs, rhs)
```

鼓励读者自行尝试不同的 `x`、`y` 和 `z` 值。

##### 每个元素都有一个逆

`py_ecc` 库提供了 `neg` 函数，通过将给定元素翻转到 y 轴上（在有限域中）来提供该元素的逆。该库将“无穷远点”编码为 Python 的 `None`。

```python
from py_ecc.bn128 import G1, multiply, neg, is_inf, Z1

## 选定一个域元素
x = 12345678 # 生成点
p = multiply(G1, x)

## 反转
p_inv = neg(p)

## 每个元素与其逆相加产生身份元
assert is_inf(add(p, p_inv))

## Z1 仅仅是 None，即无穷远点
assert Z1 is None

## 特殊情况：身份的逆是它自身
assert eq(neg(Z1), Z1)
```

就像在实数上的椭圆曲线上，椭圆曲线点的逆具有相同的 x 值，但 y 值是相反的。

```python
from py_ecc.bn128 import G1, neg, multiply

field_modulus = 21888242871839275222246405745257275088696311157297823662689037894645226208583
for i in range(1, 4):
    point = multiply(G1, i)
    print(point)
    print(neg(point))
    print('----')

# x 值是相同的
    assert int(point[0]) == int(neg(point)[0])

# y 值是彼此的逆，我们是将 y 值相加
    # 不是椭圆曲线点
    assert int(point[1]) + int(neg(point)[1]) == field_modulus
```

###### 每个元素都可以由一个生成元生成

当我们处理超过 $2^{200}$ 个点时，这无法通过暴力验证。然而，考虑 `eq(multiply(G1, x), multiply(G1, x + order))` 始终为真。这意味着我们能够生成多达阶点，然后返回到起始位置。

##### 什么是 `optimized_bn128`？

查看库，你将看到一个名为 optimized_bn128 的实现。如果你基准测试执行时间，你会发现这个版本运行得更快，这是 pyEvm 使用的实现。然而，出于教育目的，使用非优化版本是更可取的，因为它以更直观的方式构造点（通常的 x、y 元组）。优化的版本将 EC 点构造为 3 元组，较难解释。

```python
from py_ecc.optimized_bn128 import G1, multiply, neg, is_inf, Z1
print(G1)
## (1, 2, 1)
```

### 用椭圆曲线进行基本零知识证明

考虑这个相当简单的例子：

声明：“我知道两个数 $x$ 和 $y$，使得 $x + y = 15$”

证明：我将 `x` 乘以 `G1` 和 `y` 乘以 `G1`，并将其给你作为 `A` 和 `B`。

验证者：你将 15 乘以 G1，并检查 `A + B == 15G1`。

在 Python 中呈现如下：

```python
from py_ecc.bn128 import G1, multiply, add

## 证明者
secret_x = 5
secret_y = 10

x = multiply(G1, 5)
y = multiply(G1, 10)

proof = (x, y, 15)

## 验证者
if multiply(G1, proof[2]) == add(proof[0], proof[1]):
    print("声明是真的")
else:
    print("声明是假的")
```

尽管验证者不知道 `x` 和 `y` 是什么，但他们可以验证 `x` 和 `y` 相加等于 15，因此 `secret_x` 和 `secret_y` 作为有限域元素相加等于 15。

这是读者需要做更复杂的事情，例如证明一个线性方程组解的知识。

作为（非常重要的）提示，将一个数字乘以常数相当于重复加法。重复加法等同于椭圆曲线标量乘法。因此，如果 $x$ 是椭圆曲线点，那么我们可以将其乘以标量 9，例如 `multiply(x, 9)`。这与我们声称我们不能相乘椭圆曲线点相一致——实际上，我们确实将一个椭圆曲线点与标量相乘，而不是另一个点。

你能证明你知道 $x$ 使得 $23x = 161$ 吗？能不能推广到更多变量？

作为另一个提示：你（证明者）和验证者需要预先就公式达成一致，因为验证者将运行你声称知道解的原始公式的相同“结构”。

#### 安全假设

为了上述方案的安全，我们假设如果我们发布一个点，例如 `multiply(G1, x)`，攻击者无法从 $(x, y)$ 值生成的事实中推断出原始值 $x$。这被称为离散对数假设。因此，我们计算公式所需的素数必须较大，以便攻击者无法进行暴力猜测。

还有一些更复杂的算法，例如 [baby step giant step](https://en.wikipedia.org/wiki/Baby-step_giant-step) 算法可以超越暴力。

注意：BN128 的来源于它具有 128 位的安全性。椭圆曲线是在 254 位的有限域内计算的，但其被认为具有 128 位的安全性，因为存在比简单暴力破解更好的算法来计算离散对数。

#### 真实的零知识

我们还应该指出，我们的 `A + B = 15G` 示例并不是真正的零知识。如果攻击者猜测了 `a` 和 `b`，他们可以通过比较生成的椭圆曲线点来验证其猜测。

解决该问题的方法将在后面的章节中解决。

### 将椭圆曲线视为有限域的魔法黑匣子

就像你不需要知道哈希函数的内部运作原理就可以使用它一样，你也不需要知道关于如何将椭圆曲线点相加和用标量乘以它们的实现细节。

然而，你确实需要知道它们遵循的规则。冒着像断了的唱片一样的风险，它们遵循循环群的规则：

* 添加椭圆曲线点是封闭的：它产生另一个椭圆曲线点
  * 添加椭圆曲线点是结合的
  * 存在身份元素
  * 每个元素都有一个逆，添加后产生身份元素

只要你理解了这个，你就可以放心大胆地加、乘和反转而无效。每一个这样的操作在 `py_ecc` 库中都有对应的函数。

这是本课中最重要的事：

**有限域上的椭圆曲线同态加密有限域中的加法。**

#### 月亮数学：我们如何知道曲线的阶？

读者可能会想知道，我们是如何得知 bn128 曲线的阶，而不需要枚举公式的所有有效解。有效点的数量超过任何计算机可以枚举的数量，那么我们是如何得到曲线的阶数的？

这是我们试图避免的数学类型的一个例子，因为它相当高级。事实证明，计算点的数量可以通过 [Schoof 的算法](https://en.wikipedia.org/wiki/Schoof%27s_algorithm) 在多项式时间内完成。你不应期望理解该算法是如何工作的，但了解它存在就足够了。从实现的角度来看，我们到达曲线阶的方式并不重要，我们只关心设计者正确计算的事实。

这里关于 RareSkills 的材料经过精心设计，避免了这些数学雷区。

### 通过 RareSkills 学习更多

这就是我们 [零知识课程](https://www.rareskills.io/zk-bootcamp) 强调抽象代数基础的原因。了解椭圆曲线的实现细节非常困难。但理解循环群的行为，尽管一开始奇怪，对于大多数程序员来说是完全可理解的。一旦我们理解这一点，添加椭圆曲线点的一般行为就变得直观，尽管该操作难以可视化。

_最初发布于 2023 年 9 月 19 日_

>- 原文链接： [rareskills.io/post/ellip...](https://www.rareskills.io/post/elliptic-curves-finite-fields)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

限域上的椭圆曲线是什么样子的？

可视化平滑椭圆曲线很容易，但限域上的椭圆曲线是什么样子的呢？

以下是 $y² = x³ + 3 \pmod {23}$ 的图形。

$Plot of y² = x³ + 3 \\\\pmod 23$

因为我们只允许整数输入（更具体地说，是有限域元素），所以我们不会获得平滑的图形。

并非每个 $x$ 值在我们解方程时都能得到一个整数 $y$ 值，因此在该值 $x$ 上不会有点。在上面的图中可以看到这样的间隙。

生成此图形的代码稍后将提供。

素数大幅改变图形

以下是关于 $y² = x³ + 3$ 在模 11、23、31 和 41 下的图形。模数越高，图形包含的点越多，图形就越复杂。

在密码学的应用中，$p$ 需要很大。在实际中，它超过 200 位。我们将在后面的部分中重新访问这一点。

背景

域元素

我们在本文中将频繁使用“域元素”这一术语，希望你已经熟悉这个术语，尤其是从我们之前的教程（特别是关于有限域的课程）。如果没有，它是一个在模运算内部的正整数。

也就是说，如果我们在模 11 下做加法，那么该集合中的有限域元素为 ${0, 1, \ldots, 9, 10}$。虽然我们所使用的数据类型是整数，但说“整数”并不准确。在对素数执行模加法时，不能有负的域元素（虽然整数可以是负数）。在有限域下，“负”数字仅仅是另一个数字的加法逆元，即相加后结果为零的数字。例如，在模 11 的有限域中，4 可以被视为“-7”，因为 $7 + 4 \pmod{11}$ 为 0，这在常规数字中也是 7 + (-7) 等于零的对比。

在有理数域上，乘法的身份元素是 1，而一个数字的逆是分子和分母翻转。例如，$500/303$ 是 $303/500$ 的逆，因为如果你对它们相乘，你将得到 1。

循环群

一个循环群是一个群，其每个元素都可以通过从生成元元素开始并反复应用该群的二元运算来计算。

一个非常简单的例子是模 11 下的整数加法。如果你的生成元是 1，并且你不断地将生成元加给自己，那么你就可以从 0 到 10 的群中生成每个元素。

即，

$5 + 7 \pmod p$ 与 $5G + 7G$ 是同构的。

这只适用于点数为素数的有限域上的椭圆曲线，这正是我们在实践中使用的曲线。我们将在后面再次讨论这个问题。

BN128 公式

BN128 曲线（以太坊预编译用来验证 ZK 证明）如下所示：

$$ p = 21888242871839275222246405745257275088696311157297823662689037894645226208583 $$

$$ y² = x³ + 3 \pmod p $$

这里 $p$ 是域模数。

field_modulus 不应与曲线阶数混淆，后者是曲线点的数量。

对于 bn128 曲线，曲线阶数如下：

from py_ecc.bn128 import curve_order
## 21888242871839275222246405745257275088548364400416034343698204186575808495617
print(curve_order)

域模数非常大，这使得实验变得笨拙。在下一个部分中，我们将使用相同的公式，但模数较小，以培养对有限域中椭圆曲线点的直观理解。

生成椭圆曲线循环群 $y² = x³ + 3 \pmod {11}$

要解决上述方程并确定哪些 $(x, y)$ 点在曲线上，我们需要计算 $\sqrt{(x³ + 3)} \pmod{11}$。

跨模平方根

我们使用 Tonelli Shanks 公式来计算模平方根。如果你想知道该算法如何工作，可以阅读相关资料，但现在可以将其视为一个黑盒，它计算模数上一个元素的平方根，或者告知你平方根不存在。

例如，模 11 的 5 的平方根是 4 $(4 \times 4 \mod 11 = 5)$，但模 11 的 6 没有平方根。（鼓励读者通过暴力搜索来验证这一点）。

平方根通常有两个解，一个正解和一个负解。虽然在有限域中没有负号的数字，但我们仍然可以在逆元的意义上谈论“负数”。

你可以在网上找到实现上述算法的代码，但为了避免在本教程中放入大量代码，我们将安装一个 Python 库。

python3 -m pip install libnum

安装完 libnum 后，我们可以运行以下代码来演示其用法。

from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power

## 函数接受的参数# has_sqrtmod_prime_power(n, field_mod, k)，其中 n**k，
## 但我们对模域中的幂没有兴趣，所以我们将 k 设置为 1
## 检查 sqrt(8) mod 11 是否存在
print(has_sqrtmod_prime_power(8, 11, 1))
## False

## 检查 sqrt(5) mod 11 是否存在
print(has_sqrtmod_prime_power(5, 11, 1))
## True

## 计算 sqrt(5) mod 11
print(list(sqrtmod_prime_power(5, 11, 1)))
## [4, 7]

assert (4 ** 2) % 11 == 5
assert (7 ** 2) % 11 == 5

## 我们预计 4 和 7 是互为反元素，因为在“常规”数学中，平方根的两个解是 sqrt 和 -sqrt。
assert (4 + 7) % 11 == 0

让我们创建一个简单的椭圆曲线图

$$y² = x³ + 3 \pmod {11}$$

import libnum
import matplotlib.pyplot as plt

def generate_points(mod):
    xs = []
    ys = []
    def y_squared(x):
        return (x**3 + 3) % mod

    for x in range(0, mod):
        if libnum.has_sqrtmod_prime_power(y_squared(x), mod, 1):
            square_roots = libnum.sqrtmod_prime_power(y_squared(x), mod, 1)

            # 我们可能会有两个解
            for sr in square_roots:
                ys.append(sr)
                xs.append(x)
    return xs, ys

xs, ys = generate_points(11)
fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod p)');
fig.set_size_inches(6, 6);
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
plt.grid()
plt.scatter(xs, ys)
plt.plot();

图形结果如下所示：

$Plot of y² = x³ + 3 $mod 11$$

一些观察：

不会有任何 x 或 y 值大于或等于我们使用的模数
就像实值图一样，模数图“看起来是对称的”

椭圆曲线点加法

更有趣的是，我们的“连接点和翻转”操作来计算椭圆曲线仍然有效！

读者可以通过从上面的图中选择两个点，然后将它们插件于以下代码中来验证这一点，看看它们总是落在另一个点上（或者如果这些点互为反元素，则落在无穷点上）。这些公式取自维基百科的椭圆曲线点乘法页面。

def double(x, y, a, p):
    lambd = (((3 * x**2) % p ) *  pow(2 * y, -1, p)) % p
    newx = (lambd**2 - 2 * x) % p
    newy = (-lambd * newx + lambd * x - y) % p
    return (newx, newy)

def add_points(xq, yq, xp, yp, p, a=0):
    if xq == yq == None:
        return xp, yp
    if xp == yp == None:
        return xq, yq

    assert (xq**3 + 3) % p == (yq ** 2) % p, "q不在曲线上"
    assert (xp**3 + 3) % p == (yp ** 2) % p, "p不在曲线上"

    if xq == xp and yq == yp:
        return double(xq, yq, a, p)
    elif xq == xp:
        return None, None

    lambd = ((yq - yp) * pow((xq - xp), -1, p) ) % p
    xr = (lambd**2 - xp - xq) % p
    yr = (lambd*(xp - xr) - yp) % p
    return xr, yr

以下是有限域中“连接与翻转”的一些可视化效果：

循环群中的每个椭圆曲线点都有一个“数字”

一个循环群的定义是可以通过反复将生成元相加来生成。

让我们用 $y² = x³ + 3 \pmod {11}$ 和生成点 $(4, 10)$ 来做一个实际示例。

使用上面的 Python 函数，我们可以从点 $(4, 10)$ 开始，生成群中的每个点：

## 对于我们的目的，(4, 10) 是生成点 G
next_x, next_y = 4, 10
print(1, 4, 10)
points = [(next_x, next_y)]
for i in range(2, 12):
    # 反复将 G 加到下一个点以生成所有元素
    next_x, next_y = add_points(next_x, next_y, 4, 10, 11)
    print(i, next_x, next_y)
    points.append((next_x, next_y))

输出将是

0 4 10
1 7 7
2 1 9
3 0 6
4 8 8
5 2 0
6 8 3
7 0 5
8 1 2
9 7 4
10 4 1
11 None None
12 4 10 # 注意这是第一个点

观察到 $(\text{order} + 1)G = G$。就像模加法一样，当我们“溢出”时，循环会重新开始。

这里 None 表示无穷远点，这确实是群的一部分。将无穷远点与生成点相加返回生成点，这就是身份元应有的行为。

我们可以为每个点分配一个“数字”，根据我们加到自身生成该点的次数。

我们可以使用以下代码来绘制曲线并在旁边标注数字。

xs11, ys11 = generate_points(11)

fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod 11)');
fig.set_size_inches(13, 6);

ax1.set_title("模 11")
ax1.scatter(xs11, ys11, marker='o');
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
ax1.grid()

for i in range(0, 11):
    plt.annotate(str(i+1), (points[i][0] + 0.1, points[i][1]), color="red");

红色文本可以被视为从身份元开始，还有多少次我们将生成元加到自身。

$plot of y^2 = x^3 + 3 $mod 11$ with the points numbered$

点的逆仍然是垂直对称的

阶数不是模数

在本例中，群的阶数是 12（群中椭圆曲线点的总数），尽管椭圆曲线的公式是在模 11 下。这将多次强调，但你不应假设椭圆曲线的模数是群阶。但是，你可以使用哈斯定理从域模数估计曲线的阶数范围。

如果点的数量是素数，则点的加法行为类似于有限域

在上图中，有 12 个点（包括 0）。在模 12 下的加法不是有限域，因为 12 不是素数。

但是，如果我们仔细选择曲线的参数，可以创建一个椭圆曲线，使得点对应于有限域中的元素。也就是说，曲线的阶等于有限域的阶。

例如，$y^2 = x^3 + 7 \pmod {43}$ 创建了一个总共有 31 个点的曲线，如下图所示：

当曲线的阶与有限域的阶匹配时，你在有限域中所做的每一个操作在椭圆曲线中都有一个同构的对应。

要从有限域转换到椭圆曲线，我们选择一个点（随意）作为生成元，然后将有限域中的元素与生成元相乘。

乘法实际上是重复加法

没有椭圆曲线点的乘法。当我们说“标量乘法”时，我们实际上是指重复加法。你不能把两个椭圆曲线点相乘（虽然，通过双线性配对，你可以做到这一点，但这是我们稍后要涉及的内容）。

当我们使用 Python 库执行 multiply(G1, x) 时，这实际上与执行 G1 + G1 + … + G1 x 次是相同的。在底层，我们实际上并不进行这么多次自加，而是使用一些聪明的技巧进行点翻倍，以在对数时间内完成操作。

例如，如果我们想计算 135G，我们实际上将高效计算以下值并缓存它们，

G, 2G, 4G, 8G, 16G, 32G, 64G, 128G

…然后求和 128G + 4G + 2G + G = 135G。

当我们说 5G + 6G = 11G 时，我们实际上只是将 G 加到自身 11 次。使用上面所示的技巧，我们可以通过对数数量的计算来计算 11G，但最终，这仅仅是重复的加法。

Python bn128 库

EVM 实现 pyEVM 用于椭圆曲线预编译的库是 py_ecc，我们将大量依赖该库。下面的代码展示了生成点的样子，并演示了一些加法和标量乘法。

以下是 G1 点的样子：

from py_ecc.bn128 import G1, multiply, add, eq, neg

print(G1)
## (1, 2)

print(add(G1, G1))
## (1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)

print(multiply(G1, 2))
##(1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)

## 10G + 11G = 21G
assert eq(add(multiply(G1, 10), multiply(G1, 11)), multiply(G1, 21))

以下是前 1000 个点的图形：

产生上图的代码如下：

import matplotlib.pyplot as plt
from py_ecc.bn128 import G1, multiply, neg
import math
import numpy as np
xs = []
ys = []
for i in range(1,1000):
    xs.append(i)
    ys.append(int(multiply(G1, i)[1]))
    xs.append(i)
    ys.append(int(neg(multiply(G1, i))[1]))
plt.scatter(xs, ys, marker='.')

这可能看起来很可怕，但与我们在前面部分所做的唯一不同之处在于使用了更大的模数和不同的生成元。

库中的加法

py_ecc 库使点加法变得便利，语法应该不言而喻：

from py_ecc.bn128 import G1, multiply, add, eq

## 5 = 2 + 3
assert eq(multiply(G1, 5), add(multiply(G1, 2), multiply(G1, 3)));

在此时，希望读者对加法椭圆曲线点有了良好的理论和实践理解，因为现代零知识算法在这方面的依赖非常重。

关于模加法与椭圆曲线加法之间同态性的实现细节

我们在这里需要进行术语的仔细区分：

域模数是我们在曲线上进行的模运算。曲线阶是曲线上的点的数量。

如果你以某个点 $R$ 为起始点并加上曲线阶数 $o$，你将得到 $R$。如果你加上域模数，你将得到另一个不同的点。

from py_ecc.bn128 import curve_order, field_modulus, G1, multiply, eq

x = 5 # 随机选定
## 这通过
assert eq(multiply(G1, x), multiply(G1, x + curve_order))

## 这不通过
assert eq(multiply(G1, x), multiply(G1, x + field_modulus))

这意味着 $(x + y) \mod \text{curve_order} == xG + yG$。

x = 2 ** 300 + 21
y = 3 ** 50 + 11

## (x + y) == xG + yG
assert eq(multiply(G1, (x + y)), add(multiply(G1, x), multiply(G1, y)))

尽管 x + y 运算显然会在曲线阶数上“溢出”，但这并无所谓。就像在有限域中一样，这是我们所期望的行为。椭圆曲线乘法隐式执行与在进行乘法之前进行模运算一样的操作。

实际上，如果我们只关心正数，我们甚至不需要执行模运算，以下恒等式也保持成立：

x = 2 ** 300 + 21
y = 3 ** 50 + 11

assert eq(multiply(G1, (x + y) % curve_order), add(multiply(G1, x), multiply(G1, y)))

然而，如果我们对模运算使用错误的数字（即不是曲线阶的某个数字），那么如果发生“溢出”，等式则会失效。

x = 2 ** 300 + 21
y = 3 ** 50 + 11 # 这些值足够大以至于会溢出:

assert eq(multiply(G1, (x + y) % (curve_order - 1)), add(multiply(G1, x), multiply(G1, y))), "this breaks"

编码有理数

当我们进行模运算时，我们能够编码一个除法的概念。

例如，我们使用常规整数无法做到以下事情。

## 这会抛出异常
eq(add(multiply(G1, 5 / 2), multiply(G1, 1 / 2), multiply(G1, 3)

然而，在有限域中，可以将 1/2 理解为 2 的乘法逆。因此，$5 / 2$ 可以被编码为 $5 \cdot \mathsf{inv}(2)$。

在 Python 中，我们可以这样做：

five_over_two = (5 * pow(2, -1, curve_order)) % curve_order
one_half = pow(2, -1, curve_order)

## 实际上 5/2 = 2.5# 2.5 + 0.5 = 3
## 但在有限域中我们这么做
assert eq(add(multiply(G1, five_over_two), multiply(G1, one_half)), multiply(G1, 3))

结合律

我们知道群是结合的，因此我们期望以下人体普遍成立：

x = 5
y = 10
z = 15

lhs = add(add(multiply(G1, x), multiply(G1, y)), multiply(G1, z))

rhs = add(multiply(G1, x), add(multiply(G1, y), multiply(G1, z)))

assert eq(lhs, rhs)

鼓励读者自行尝试不同的 x、y 和 z 值。

每个元素都有一个逆

py_ecc 库提供了 neg 函数，通过将给定元素翻转到 y 轴上（在有限域中）来提供该元素的逆。该库将“无穷远点”编码为 Python 的 None。

from py_ecc.bn128 import G1, multiply, neg, is_inf, Z1

## 选定一个域元素
x = 12345678 # 生成点
p = multiply(G1, x)

## 反转
p_inv = neg(p)

## 每个元素与其逆相加产生身份元
assert is_inf(add(p, p_inv))

## Z1 仅仅是 None，即无穷远点
assert Z1 is None

## 特殊情况：身份的逆是它自身
assert eq(neg(Z1), Z1)

就像在实数上的椭圆曲线上，椭圆曲线点的逆具有相同的 x 值，但 y 值是相反的。

from py_ecc.bn128 import G1, neg, multiply

field_modulus = 21888242871839275222246405745257275088696311157297823662689037894645226208583
for i in range(1, 4):
    point = multiply(G1, i)
    print(point)
    print(neg(point))
    print('----')

    # x 值是相同的
    assert int(point[0]) == int(neg(point)[0])

    # y 值是彼此的逆，我们是将 y 值相加
    # 不是椭圆曲线点
    assert int(point[1]) + int(neg(point)[1]) == field_modulus

每个元素都可以由一个生成元生成

当我们处理超过 $2^{200}$ 个点时，这无法通过暴力验证。然而，考虑 eq(multiply(G1, x), multiply(G1, x + order)) 始终为真。这意味着我们能够生成多达阶点，然后返回到起始位置。

什么是 `optimized_bn128`？

from py_ecc.optimized_bn128 import G1, multiply, neg, is_inf, Z1
print(G1)
## (1, 2, 1)

用椭圆曲线进行基本零知识证明

考虑这个相当简单的例子：

声明：“我知道两个数 $x$ 和 $y$，使得 $x + y = 15$”

证明：我将 x 乘以 G1 和 y 乘以 G1，并将其给你作为 A 和 B。

验证者：你将 15 乘以 G1，并检查 A + B == 15G1。

在 Python 中呈现如下：

from py_ecc.bn128 import G1, multiply, add

## 证明者
secret_x = 5
secret_y = 10

x = multiply(G1, 5)
y = multiply(G1, 10)

proof = (x, y, 15)

## 验证者
if multiply(G1, proof[2]) == add(proof[0], proof[1]):
    print("声明是真的")
else:
    print("声明是假的")

尽管验证者不知道 x 和 y 是什么，但他们可以验证 x 和 y 相加等于 15，因此 secret_x 和 secret_y 作为有限域元素相加等于 15。

这是读者需要做更复杂的事情，例如证明一个线性方程组解的知识。

作为（非常重要的）提示，将一个数字乘以常数相当于重复加法。重复加法等同于椭圆曲线标量乘法。因此，如果 $x$ 是椭圆曲线点，那么我们可以将其乘以标量 9，例如 multiply(x, 9)。这与我们声称我们不能相乘椭圆曲线点相一致——实际上，我们确实将一个椭圆曲线点与标量相乘，而不是另一个点。

你能证明你知道 $x$ 使得 $23x = 161$ 吗？能不能推广到更多变量？

作为另一个提示：你（证明者）和验证者需要预先就公式达成一致，因为验证者将运行你声称知道解的原始公式的相同“结构”。

安全假设

为了上述方案的安全，我们假设如果我们发布一个点，例如 multiply(G1, x)，攻击者无法从 $(x, y)$ 值生成的事实中推断出原始值 $x$。这被称为离散对数假设。因此，我们计算公式所需的素数必须较大，以便攻击者无法进行暴力猜测。

还有一些更复杂的算法，例如 baby step giant step 算法可以超越暴力。

真实的零知识

我们还应该指出，我们的 A + B = 15G 示例并不是真正的零知识。如果攻击者猜测了 a 和 b，他们可以通过比较生成的椭圆曲线点来验证其猜测。

解决该问题的方法将在后面的章节中解决。

将椭圆曲线视为有限域的魔法黑匣子

就像你不需要知道哈希函数的内部运作原理就可以使用它一样，你也不需要知道关于如何将椭圆曲线点相加和用标量乘以它们的实现细节。

然而，你确实需要知道它们遵循的规则。冒着像断了的唱片一样的风险，它们遵循循环群的规则：

添加椭圆曲线点是封闭的：它产生另一个椭圆曲线点
添加椭圆曲线点是结合的
存在身份元素
每个元素都有一个逆，添加后产生身份元素

只要你理解了这个，你就可以放心大胆地加、乘和反转而无效。每一个这样的操作在 py_ecc 库中都有对应的函数。

这是本课中最重要的事：

有限域上的椭圆曲线同态加密有限域中的加法。

月亮数学：我们如何知道曲线的阶？

这是我们试图避免的数学类型的一个例子，因为它相当高级。事实证明，计算点的数量可以通过 Schoof 的算法在多项式时间内完成。你不应期望理解该算法是如何工作的，但了解它存在就足够了。从实现的角度来看，我们到达曲线阶的方式并不重要，我们只关心设计者正确计算的事实。

这里关于 RareSkills 的材料经过精心设计，避免了这些数学雷区。

通过 RareSkills 学习更多

这就是我们零知识课程强调抽象代数基础的原因。了解椭圆曲线的实现细节非常困难。但理解循环群的行为，尽管一开始奇怪，对于大多数程序员来说是完全可理解的。一旦我们理解这一点，添加椭圆曲线点的一般行为就变得直观，尽管该操作难以可视化。

最初发布于 2023 年 9 月 19 日

原文链接： rareskills.io/post/ellip...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

有限域上的椭圆曲线

限域上的椭圆曲线是什么样子的？

素数大幅改变图形

背景

域元素

循环群

BN128 公式

生成椭圆曲线循环群 $y² = x³ + 3 \pmod {11}$

跨模平方根

椭圆曲线点加法

循环群中的每个椭圆曲线点都有一个“数字”

点的逆仍然是垂直对称的

阶数不是模数

如果点的数量是素数，则点的加法行为类似于有限域

乘法实际上是重复加法

Python bn128 库

库中的加法

关于模加法与椭圆曲线加法之间同态性的实现细节

编码有理数

结合律

每个元素都有一个逆

每个元素都可以由一个生成元生成

什么是 `optimized_bn128`？

用椭圆曲线进行基本零知识证明

安全假设

真实的零知识

将椭圆曲线视为有限域的魔法黑匣子

月亮数学：我们如何知道曲线的阶？

通过 RareSkills 学习更多

0 条评论

文章目录

有限域上的椭圆曲线

限域上的椭圆曲线是什么样子的？

素数大幅改变图形

背景

域元素

循环群

BN128 公式

生成椭圆曲线循环群 $y² = x³ + 3 \pmod {11}$

跨模平方根

椭圆曲线点加法

循环群中的每个椭圆曲线点都有一个“数字”

点的逆仍然是垂直对称的

阶数不是模数

如果点的数量是素数，则点的加法行为类似于有限域

乘法实际上是重复加法

Python bn128 库

库中的加法

关于模加法与椭圆曲线加法之间同态性的实现细节

编码有理数

结合律

每个元素都有一个逆

每个元素都可以由一个生成元生成

什么是 optimized_bn128？

用椭圆曲线进行基本零知识证明

安全假设

真实的零知识

将椭圆曲线视为有限域的魔法黑匣子

月亮数学：我们如何知道曲线的阶？

通过 RareSkills 学习更多

0 条评论

文章目录

什么是 `optimized_bn128`？