数论基础(二)—椭圆曲线

参考文章：

https://accu.cc/content/cryptography/ecc/

https://blog.csdn.net/qq_44925830/article/details/123300315

https://zhuanlan.zhihu.com/p/603240120

https://juejin.cn/post/7263886796756844604

椭圆曲线密码学(Elliptic Curve Cryptography, ECC) 是一种基于椭圆曲线数学的公开密钥加密算法. 针对密码学应用上的椭圆曲线通常是在有限域平面上的曲线. 椭圆曲线最出名的应用是比特币系统, 比特币使用一条名为 secp256k1 的椭圆曲线用于生成公钥/私钥和进行交易签名和验签工作.

1 有限域

我们首先简要介绍有限域(Finite field). 有限域是包含有限个元素的域. 与其他域一样, 有限域是进行加减乘除运算都有定义并且满足特定规则的集合. 有限域最常见的例子是当 p 为素数时, 整数对 p 取模形成的集合. 有限域的元素个数称为它的阶. 这种类型的有限域通常使用 Fp 表示. 有限域中包含三种计算, 分别是 addition, multiplication 和 inversion.

例: 有有限域 F₂₃, 求其阶.

答: F₂₃ = {0, 1, 2, …, 22}, 因此其阶为 23.

Fp 的三种计算操作定义如下(a, b 为 Fp 中的元素):

1
2
3

a + b:  (a + b) % p
a * b:  (a * b) % p
a.inv:  a * a.inv = 1 where a != 0 (取逆)

由三种基本计算扩展出 subtraction 和 division:

1
2

a - b:  (a - b) % p
a / b:  (a * b^(p-2)) % p

除法是一个特殊情况, 我们实际上需要求的是$b^{-1}$ . 根据费马小定理(Fermat’s little theorem), $b^{p-1}=1(\mod p )$, 因此有 $b \cdot b^{p-2}=1(\mod p)$, 因此$b^{-1}=b^{p-2}$

2.椭圆$F_p$

a 定义

${ (x,y)\in F^{2}_p|y^2=x^3+ax+b,4a^3+27b^2 \ne 0} \cup{0}$

0是无穷远处的点$a,b\in F_p$

对称性，关于$y=p/2$对称

椭圆曲线加密体系的基础源于椭圆曲线离散对数问题: 给定 P, Q ∈ E(Fp), 找到 k ∈ Z 使得 kP = Q 是困难的. 这里 k 就是所谓的离散对数, 而这里的困难是指目前还不存在低于指数级别的算法. 基于椭圆曲线离散对数问题, 通常, 用户随机生成一个整数 s 作为私钥. 然后, 对于一个公共的生成元 G, 用户将 s * G 作为公钥并公开. 由于破解椭圆曲线离散对数是困难的, 对手(adversary)无法通过公钥计算出私钥的值.

举例

给定一个非零点 Q，其逆元是具有相同横坐标但纵坐标相反的点 −Q,$-Q=(x_Q,-y_Q \mod p)$。例如，如果在 $F_{29}$中的曲线有一个点 Q=(2,5)，那么逆元$-Q=(2,-5\mod 29)=(2,4)$

另外，$P+(-P)=0$（根据逆元的定义）。

b 加法运算

定义加法运算为点加运算：

$P,Q,R$都是$E_p(a,b)$上的点，坐标分别为$(x_1,y_1)(x_2,y_2)(x_3,y_3)$

$P+Q=R$

即$(x_1,y_1)+(x_2,y_2)\equiv(x_3,y_3)$

$x_3=k^2-x_1-x_2$

$y_3=k(x_1-x_3)-y_1$

其中k是这样计算的

$P\neq Q,k=(y_2-y_1)/(x_2-x_1)$

$P=Q,k=(3x_1^2+a)/2y_1$

为什么R的坐标是这么算的，说实话，鉴于所学有限，我也没有去推理和证明，数学家已经帮我们得出了结论，就直接拿来用了。

c 乘法运算

定义了点加运算，也就得出了点乘运算：

$d*P=(P+….P)$

重合的话 就是 P+P =2P, 也就是 P点的切线 与椭圆曲线的交点, 再将这个交点做 关于 X轴的对称， 关于 x 轴的对称点 就是 2P.

有了 2P, 那么同样的方法 求出3P。 我们将 过 P点和2P点做一条直线, 这条直线与 椭圆曲线的交点的 关于 X轴 对称就是 3P, 比如下面这样:

依次类推, 我们可以画出 4P, 5P… NP, 只要不停地连接两点画直线 找出与 椭圆曲线的交点, 再关于 X轴对称即可。我们把这叫做 椭圆曲线上的乘法。

事实上计算NP并不是需要一步步进行计算, 比如计算 100P， 并不用计算 1P, 2P, 3P, …, 99P. 我可以直接告诉你一个结论 那就是 椭圆曲线上的加法符合结合律。
符合结合律有什么好处呢？好处相当地大， 我把 计算100P展开来说：

100P = 50P+50P, 而 50P =25P+ 25P , 25P =1P +24P, 24P = 12P +12P, 12P=6P+6P, 6P=3P+3P, 3P=1P+2P, 2P=1P+1P， 也就是计算 100P ，我实际上并不需要做100次加法， 而只需要做 8次加法即可，每当 NP(N为偶数时), 都可以将 NP 拆成 两个 N/2 * P 之和， 所以椭圆曲线上的乘法 Q=k*P 的时间复杂度为 O(logK)。 记住这个结论, 非常重要 !!!

c 标量乘法和循环子群

标量乘：n P = P + P + . . . + P

使用double and add algorithm算法在$O(log n)/O(k)$（k是n nn的比特长度）时间复杂度内

我们称P PP为generator 或 base point

循环子群是ECC及其他密码系统的基础

3 从 椭圆曲线上的乘法 推广到 非对称加密

给定一条椭圆曲线一个起点P, 和大的质数数k, 我们可以很容易地找到 Q=kP点(时间复杂度为 O(logK))。但是反过来, 给出终点Q 和起点P ，让你找出 k, 你只有一次次地 从 k =1, k=2, … k=N 去暴力尝试, 这个时间复杂度是 为 O(k) 级别的。

这个性质是不是很熟悉？正向容易计算, 逆向极其困难， 是不是和RSA有点像了？ RSA 根据 私钥计算公钥很容易, 公钥反推私钥几乎不可能。

如果我们将 k 看作私钥, 那么 Q 就可以被看作公钥， 这就是 椭圆曲线非对称加密算法的原理, 椭圆曲线加密算法的强度保障就在于 给定P 和 k 计算 Q是否容易, 但反之 给定Q和P 想要计算 k 则是否困难。

具体如何加解密:

• 选定一条椭圆曲线, 选定起点(也叫基点)P(通常选得非常大)， 选取一个整数 k( k<n , k通常很大, 几百bit级别, 但同样的强度相对于 RSA 又明显小一个数量级) 作为私钥, 计算公钥 Q=kP

• 加密过程如下: 选取一个随机整数r ( r<n, r 通常也很大), 使用公钥Q 和 r 对 明文$M$进行加密得到密文$C$,其由两部分组成

  $C=[C_1,C_2]=[rP,M+rQ]$

• 解密过程如下

  $M+rQ-K(rP)=M+krP-krP=M$

4椭圆曲线非对称加密 安全性分析

• 椭圆曲线参数公开, 基点P公开, Q 公开, 私钥 k 解密方保密, r 为加密方保密(一次性随机数,不存储, 不具备重放性)
• C的加密需要公开的Q，M，以及一次性随机数r
• C解密需要公开的C和私钥k
• 想要截获C破解只有两种可能
  • 想办法获取私钥 k, 若私钥不泄露则无此风险
  • 直接通过$M+rQ-rkP=M$计算这里有两层困难
    • k只能通过 终点Q 和 基点P 反推, 上面分析过极其困难
    • r只能通过 终点 rP 和 基点P 反推, 也是极其困难的, 并且r 是一次性随机数, 不能被重放

5 从连续的椭圆曲线 推广到 有限域

根据上面的分析， 你已经知道了椭圆曲线从几何意义上是如果确保 密钥的强度了。复述一遍 就是 给定基点P 和 私钥 k, 计算终点 也就是 公钥 Q 比较容易；反之知道 终点Q和基点P ，想要反推密钥 k 将极其困难。

那么如果要在计算机上面使用椭圆曲线上的 密钥体系, 则还需要解决两个问题

1. 将连续的曲线进行离散化处理，计算机是不能处理 1.111111111111111… 这种精度无穷大的小数的
2. 将离散化的曲线个数进行有限化，计算机无法处理一个无穷大的数字的

解决方法也很简单，对症下药既可：

1. 对连续的曲线进行取整, 对x只考虑整数
2. 对曲线表达式两边同时进行 取模 操作, 取模操作约束了 等式左右两边的大小

如此一来, 离散且有限的”曲线” 表达式就变成下面这样:

$$
y^2\equiv x^3+ax+b(\mod p),x\in Z & 4a^3+27*b^2\neq 0
$$

这条曲线记作 $GF(p)$ ,特别的是 p 一般取质数(实际应用中会取大质数)。 之所以取质数，是为了取值的多样性，为了取值的方碰撞性。

在$GF(p)$上的加法变成了这样:

$x_3=k^2-x_1-x_2(\mod p)$

$y_3=k(x_1-x_3)-y_1(\mod p)$

$x_1\neq x_2,k=(y_2-y_1)/(x_2-x_1)$

$x_1=x_2,y_3=k=(3x_1^2+a)/2y_1(\mod p)$

我们用 python 画一下$y^2\equiv x^3 +x+1(\mod 23)$的图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import matplotlib.pyplot as plt

# 定义有限域上的曲线方程
def curve(x):
    return (x**3 + x + 1) % 23

# 生成离散的数据点
x = []
y = []
txt = []
for i in range(23):
    for j in range(23):
        if curve(i) == j**2 % 23:
            x.append(i)
            y.append(j)
            txt.append('(' +str(i)+',' + str(j)+')')
            
# 绘制曲线图像
plt.figure(figsize=(13, 10))
plt.scatter(x, y, marker='o' , s=50)

for i in range(len(x)):
    plt.annotate(txt[i], xy = (x[i], y[i]), xytext = (x[i]+0.05, y[i]+0.1),fontsize=15) 

plt.xlabel('x', fontsize=20)
plt.ylabel('y', fontsize=20)
plt.title('y^2 ≡ x^3 + x + 1 (mod 23)',fontsize=25)
plt.xlim(-1,15)
plt.ylim(-2,24)
plt.grid(True)
plt.show()

图上每一个点都满足$y^2\equiv x^3 +x+1(\mod 23)$

我们用python计算 P, 2P, …, 22P

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

import matplotlib.pyplot as plt

# 定义有限域GF(p)
p = 23 

# 定义椭圆曲线方程 y^2 = x^3 + ax + b (mod p)
a = 1
b = 1

# 定义椭圆曲线上一个点P(x, y)
P = (3, 10) 

# 点乘运算 Q = dP
def ecc_point_multiply(P, d, a, p):
    Q = (0, 0)
    for i in range(d):
        Q = ecc_point_add(Q, P, a, p)
    return Q

# 点加法
def ecc_point_add(P, Q, a, p):
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and y1 != y2:
        return (0, 0)
    if P == Q:
        return ecc_point_double(P, a, p)

    s = (y2 - y1) * pow(x2 - x1, p - 2, p) % p
    x3 = (s*s - x1 - x2) % p 
    y3 = (s*(x1 - x3) - y1) % p
    return (x3, y3)

# 点倍运算  
def ecc_point_double(P, a, p):
    if P == (0, 0):
        return (0, 0)
    x1, y1 = P
    s = (3*x1*x1 + a) * pow(2*y1, p-2, p) % p
    x3 = (s*s - 2*x1) % p
    y3 = (s*(x1 - x3) - y1) % p
    return (x3, y3)
 

k=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27]
Q=[]
txt = []
for i  in range(len(k)):
     Q.append ( ecc_point_multiply(P, k[i], a, p) )
     txt.append(str(i+1)+'P')
        
plt.figure(figsize=(15, 10))

for i  in range(len(Q)):
    plt.scatter(Q[i][0], Q[i][1], marker='o' , s=50, color ='gray')

for i  in range(len(Q)):
    plt.annotate(txt[i], xy = (Q[i][0], Q[i][1]), xytext = (Q[i][0]+0.1, Q[i][1]+0.1),fontsize=15) 
 
for i  in range(len(Q)-1):  
    plt.plot([Q[i][0],Q[i+1][0]] , [Q[i][1],Q[i+1][1]] )

plt.xlabel('x', fontsize=20)
plt.ylabel('y', fontsize=20)
plt.title('y^2 ≡ x^3 + x + 1 (mod 23), p=（3，10), Q=kP',fontsize=20)
plt.xlim(-1,20 )
plt.ylim(-1,23)
plt.grid(linewidth=0.5, color='gray')
plt.show()

说明一下这里计算 Q=kP 还是使用了暴力计算(和逆求解k相同)，并没有使用 将 逐步二分拆解的优化(比如100P = 50P+50P, 而 50P =25P+ 25P , 25P =1P +24P, 24P = 12P +12P, 12P=6P+6P, 6P=3P+3P, 3P=1P+2P, 2P=1P+1P, 只需计算8次这种优化) 。这里的 k 和 p都 比较小, 放上代码只作为一个 demo。实际应用中还是得通过优化将为 logK。

可以看到在有限域上的乘法操作非常的无序，混乱，完全没有任何规律。这种杂乱无章的特性就非常适合用来加密， 让人无从下手，找不到任何规律，才能保障密文的安全性。