ECC 椭圆曲线加密算法学习————从实数域到有限域的椭圆曲线

标签（空格分隔）： ecc Crypto

****
> File Name: ECC 椭圆曲线加密算法学习————从实数域到有限域的椭圆曲线
> Author: shaobaobaoer
> Mail: shaobaobaoer@126.com
> WebSite: shaobaobaoer.cn
> Time: Sunday, 24. March 2019 11:53AM
****

0x00 前言

我好像很久没有自己学点东西了，从寒假上来就一直在做期末大作业然后考试。现在算是考完了，但是也要意味着考研复习要彻底拉开帷幕了。很多想去复现的CVE只能在计划本上越排越后面。有个东西一直想去看看，就是ECC。上学期学了数论的选修课，

参考的网站

预先准备的数学概念

群 Group

这个概念来自于离散数学，有所困惑还请多翻翻书。对于一个阿贝尔群（有些书上管它叫交换群或者加群，相信学过离散数学的你对它一定记忆犹新）它的性质包括

具有封闭性
满足结合律
存在单位元
每个数存在逆元（备注，知乎上的翻译翻错了）
满足交换律

整数域和有限域

首先，有限域是一个带有有限元素的集合。比如，有一个有限域是整数模p的集合（integers mod p,p是素数），可表示为 $\mathbb {Z}/p,GF(p)$ 或 $\mathbb {F}_{p}$ ,一般用后者。

模运算 mod

这个概念来自于数论，有所困惑的还请找潘兄弟俩的书看看。
需要用到的知识在下面罗列

模运算的加法
模运算的乘法
乘法逆元，简称逆元
- $ 45 \times x \equiv 1 (mod ;23) $
- 得出 $ x = -1 $所以，-1是45对模23的逆元
- 关于乘法逆元可以用辗转欧几里得算法来快速求出。代码在misc/shaobaobaoer_math_lab.py下。

形如$ y^2 ;\equiv ;A;(;mod;p;)$的同余方程求解问题

参考网站
https://www.johndcook.com/blog/quadratic_congruences/?tdsourcetag=s_pctim_aiomsg
https://blog.csdn.net/ACdreamers/article/details/10182281
C代码模板：
https://blog.csdn.net/Quack_quack/article/details/50189111

其中p是一个奇素数。其中需要用到一些二次剩余得知识证明。在两篇文章中都有说，这里就记录一些结论。

确定方程是否有解？

方程有解当且仅当 $A^{\frac{p-1}{2}}\equiv 1 (mod p)$

确定方程的解

如何计算方程的解呢？
网上搜下来都是ACM的题目了。顿时感觉自己血菜。在ACMer的博客里看到了 cipolla算法。代码量用python写起来不是很复杂，但是这个东西暂时还看不懂，魔改了一下 cipolla 的模板。之后也许会填坑

三次一元方程解的形式

对于如下形式的方程
$$ ax^3 + bx^2 + cx + d = 0$$
存在如下结论
$x1+x2+x3=-b/a$
$x1x2+x2x3+x3x1=c/a$
$x1x2*x3=-d/a$

现在，方程变为如下形式
$$ (kx + c)^2 = x^3 + ax +b ;;; \Longleftrightarrow ;;;x^3 - k^2x^2 + (a-2kc)x + b - c^2 = 0$$

可以得到如下结论，该结论可以节省很多解方程的时间

$$x3= k^2 - x1 - x2$$

0x01 椭圆曲线定义

首先来看下椭圆曲线的标准形式公式：

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

其中 $4a^3 + 27b^2 \ne 0 $ 这个限定条件保证曲线不包含奇点。
这样的椭圆曲线被称为 Weierstrass 标准形式。

当然，为了定义椭圆曲线，还需要一个无穷远的点作为曲线的一部分，在这里用符号 $\odot$ 表示。

最终，将表达式可以精炼为
$$\left{ (x, y) \in \mathbb{R}^2\ |\ y^2 = x^3 + ax + b,\ 4 a^3 + 27 b^2 \ne 0 \right}\ \cup\ \left{ \odot \right}$$

根据解析式，不难发现该曲线关于x轴对称，之后会用到其性质

1.1 标准形式的椭圆曲线绘制

执行如下代码可以画出来一个椭圆曲线。

# draw_curve/draw.py
from matplotlib import pyplot as plt
import numpy as np
a = -2
b = 3
y, x = np.ogrid[-5:5:100j, -5:5:100j]
plt.contour(x.ravel(), y.ravel(), pow(y, 2) - pow(x, 3) - x * a - b, [0])
plt.grid()
plt.legend()
plt.show()

image_1d6kcqrgb13j7sbbqsl5pq1t449.png-24kB

1.2 椭圆曲线上的群G

之后，有了这个可爱的曲线之后，我们定义一个群G

群众元素满足上头的表达式，也就是说，群中元素是椭圆曲线上的点
单位元$e$是无穷远处的点$\odot$
逆元$p$是原坐标点关于x轴对称的那一点。
定义一种在该群上的加法，取一条与曲线相交于三点的直线，记交点为$P,Q,R$，他们的总和等于0，就是说$P+Q+R=0$。这三点没有顺序，所以可以证明该椭圆曲线满足交换律。

之后，可以证明这个群是一个典型的阿贝尔群。

1.3 群G上加法运算的各种情况

为了方便表示，可以把该加法写成$P+Q=-R$
这样写，其中的-R有几何含义，也就是R关于X轴对称的一点，如图

image_1d6ke29sgttoe4f1jmf1j7e18cnm.png-60.9kB

之后，讨论三种情况。

CASE 1 P = Q :

$k = \cfrac{3x^2_0 + a }{2y_0}$

得知直线方程后，计算$R_x= k^2 - x1 - x2$

CASE 2 P != Q 并且 P + Q = -R:

$k = \cfrac{y_P - y_Q}{ x_P - x_Q}$

得知直线方程后，计算$R_x= k^2 - x1 - x2$

CASE 3 P != Q 并且 P + Q = -P OR P + Q = -Q:

这就是之前说到的第三种情况，在这种情况下，只需要计算

$ \cfrac{3x^2_0 + a }{2y_0} - \cfrac{y_P - y_Q}{ x_P - x_Q} $是否等于零

这种情况下，$P,Q$必有一点满足上式。将该点坐标的纵坐标求反即得到 -R。实际运算的时候可以和CASE2合并。

之后，就可以写一个函数来计算-R的值了，在此就罗列一些关键代码

def get_three_pionts(self, P, Q):
    if P == (0, 0) or Q == (0, 0):
        return Q if P == (0, 0) else P

    if self.__check_on_curve(P) and self.__check_on_curve(Q):
        if P == Q:
            # CASE 1
            k = (3 * P[0] ** 2 + self.a) / (2 * P[1])
            b = P[1] - k * P[0]
            x = k ** 2 - P[0] - Q[0]
            y = k * x + b
            R = (x, -y)
        else:
            # CASE 2
            k = (P[1] - Q[1]) / (P[0] - Q[0])
            b = P[1] - k * P[0]
            x = k ** 2 - P[0] - Q[0]
            y = k * x + b
            R = (x, -y)
        return R
    else:
        raise ValueError

1.4 标量积与对数问题

定义一种变量积如下所示，实际上可以用快速幂来解决这个数乘问题 $$nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}$$

OK，对于给定的$Q$（$Q=nP$）和$P$是否能够找到这个n呢？当然，这玩意儿不叫除，而是叫对数。（为了和其他密码中“幂”的说法保持一致，从某种程度上而言，这个也算是幂而非数乘）

刚才说了，加法是有特殊的定义的。然而一个个加P又非常蠢，有什么好的方法呢？其中一个比较好的算法是倍加算法。原理很简单，可以看如下公式

n = 151, 二进制表示： $10010111_2$ ，这个二进制也可以表示成幂次加和：

$\begin{array}{rcl} 151 & = & 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 \ & = & 2^7 + 2^4 + 2^2 + 2^1 + 2^0 \end{array}$

简化一下：

$151 \cdot P = 2^7 P + 2^4 P + 2^2 P + 2^1 P + 2^0 P$

在之后，可以写一下小把戏来达成这个加法,bits函数其实就是一个迭代器。而每次更新P和R的值。R是最后的结果，而P则是每次自加，形如$2^n P$,n为迭代次数。

def get_scalar_multiplication(self, n, P):
    """
    Returns the result of n * x, computed using
    the double and add algorithm.
    """
    self.R = (0, 0)
    self.P = P
    for bit in bits(n):
        if bit == 1:
            self.R = self.get_three_pionts(self.P, self.R)
        self.P = self.get_three_pionts(self.P, self.P)
    return self.R

在连续曲线上，这个n是非常好找的，（当然你要算很多次）但是如果在离散领域呢？就会变得更加复杂。这是椭圆曲线加密算法的核心所在。

0x02 有限域和离散对数领域的椭圆曲线

之前说了关于标量积的相关知识，在看这节之前，还需要知道数论的相关知识

之后，将椭圆曲线和有限域 $\mathbb {F}{p}$结合起来，在$\mathbb {F}{p}$上定义椭圆曲线，形式是点集。于是它变成了这样子，注意，在计算 $y^2 \equiv A (mod ;p)$的时候推荐用前文说到的cipolla算法

image_1d6kgl87h19krnf911311hvhej613.png-8.7kB

参考一些图片如下所示：这就是画出来的图
a=-7;b=10;p=19
discreteEC_-7_10_19_12_48AM.png-13.2kB
a=-7;b=10;p=97
discreteEC_-7_10_97_12_48AM.png-13.7kB

$\mathbb {F}_{p}$本身是一个阿贝尔群。不难证明对于在离散对数域内的椭圆曲线，仍然是一个阿贝尔群。【证明在最后】

另外，回到之前刚刚说的奇点，所谓奇点，就是说在曲线中会算出来在(0,0)处的点。注意我们定义的单位元$\odot $ 的位置就是(0,0)。为了不让曲线上的点与单位元重合，所以要排除掉含有奇点的曲线。比如说曲线线$$y^2 \equiv x^3 (mod;29)$$，令$x=0$,$y=\pm 0$，可以发现在（0，0）处有三个点（别忘了还有一个单位元）。所以是一个无效的椭圆曲线

2.1 离散域上点的加法

之前谈及过，$P + Q =-R$这玩意儿在实数域自然没有问题。在有限域之内也可以参照相同的定义

对此，设$L : ax + by + c \equiv 0 (mod ; p)$为$\mathbb {F}_{p}$ 上一条线。同样可以通过两点确定一条直线。

和之前证明的东西类似，只不过都需要加上$mod;p$。

对此，主要讨论之前出现的两种情况，大胆利用实数域的做法，实际上方法一样。

CASE 1 P = Q :

$k \equiv \cfrac{3x^2_0 + a }{2y_0} (mod ; p)$

得知直线方程后，计算$R_x \equiv k^2 - x1 - x2 (mod ;p )$

CASE 2 P != Q 并且 P + Q = -R:

$k \equiv \cfrac{y_P - y_Q}{ x_P - x_Q} (mod ; p)$

得知直线方程后，计算$R_x \equiv k^2 - x1 - x2 (mod ;p )$

CASE 3 P != Q 并且 P + Q = -P OR P + Q = -Q:

这就是之前说到的第三种情况，在这种情况下，只需要计算

$ \cfrac{3x^2_0 + a }{2y_0} (mod ; p) - \cfrac{y_P - y_Q}{ x_P - x_Q} (mod ; p) \equiv 0 (mod ; p)$

这种情况下，$P,Q$必有一点满足上式。将该点坐标的纵坐标求加法逆元即得到 -R。实际运算的时候可以和CASE2合并。

之后，就可以写一个函数来计算-R的值了，在此就罗列一些关键代码

def get_three_pionts(self, P, Q):
    R = (0, 0)
    if P == (0, 0) or Q == (0, 0):
        return Q if P == (0, 0) else P
    if self.__check_on_curve(P) and self.__check_on_curve(Q):
        # CASE 1 P == Q
        if P == Q:
            k = (3 * P[0] ** 2 + self.a) * egcd(2 * P[1], self.p)
            k %= self.p
            b = P[1] - k * P[0]
            b %= self.p
            x = k ** 2 - P[0] - Q[0]
            y = k * x + b
            R = (positive_mod(x, self.p), positive_mod(self.p - y, self.p))
        else:
            # CASE 2 P != Q
            k = (P[1] - Q[1]) * egcd(P[0] - Q[0], self.p)
            k %= self.p
            b = P[1] - k * P[0]
            b %= self.p
            x = k ** 2 - P[0] - Q[0]
            y = k * x + b
            R = (positive_mod(x, self.p), positive_mod(self.p - y, self.p))
        return R
    else:
        raise ValueError

2.2 椭圆曲线阶

既然是在有限域$\mathbb {F}_{p}$内，那么椭圆曲线应该是有限个点构成的，所以，到底有多少个点呢？

对于一个群而言，有多少点就叫做这个群的阶。比如模13群的阶为 13。同样，对于有限域$\mathbb {F}_{p}$上的椭圆曲线而言，也有对应的阶。枚举当然是很蠢的，有种算法叫做Schoof算法，它的复杂度是多项式时间，算法比较复杂。可以在github上找到其代码https://github.com/pdinges/python-schoof

注意需要用 Linux 和 python3 运行，大概的用法如下所示：

1 2	➜ python-schoof git:(master) ✗ python3 naive_schoof.py 23 4 2 Counting points on y^2 = x^3 + 4x + 2 over GF<23>: 21

2.3 从数乘到循环子群

之前实现了连续域内的数乘，离散领域内容也是类似，利用相同的幂次加和来计算nP。唯一需要注意的就是对于n=0而言，直接返回单位元$\odot$（0,0）即可。主要代码如下：

def get_scalar_multiplication(self, n, P):
    if n == 0: return 0, 0
    self.R = (0, 0)
    self.P = P
    for bit in bits(n):
        if bit == 1:
            self.R = self.get_three_pionts(self.P, self.R)
        self.P = self.get_three_pionts(self.P, self.P)
    return self.R

实际上还有一些优化策略，会在之后讨论。

当写完这个函数后，会发现椭圆曲线上有个很有意思特点，任取一条曲线如：
$$ y^2 \equiv x^3 + 2x + 3 (mod ;97)$$
已知点P(3,6)在该曲线上。

我们来算算 $nP$是多少。

$0P \rightarrow \odot$
$1P \rightarrow (3,6)$
$2P\rightarrow (80,10)$
$3P\rightarrow (80,87)$
$4P\rightarrow (3,91)$
$5P\rightarrow \odot$ 备注：计算斜率的会出现(n * x + p * y) % p != gcd的情况，这也就意味着该点位于无穷远处
$1P \rightarrow (3,6)$
$2P\rightarrow (80,10)$
$3P\rightarrow (80,87)$
$9P\rightarrow (3,91)$
$10P \rightarrow \odot$

不难发现P的倍乘是一个5阶循环群，生成元是$\langle \odot \rangle$,$\langle P \rangle$,$\langle 2P \rangle$,$\langle 3P \rangle$,$\langle 4P \rangle$

同时可以发现，P的加法是一个闭环。也就意味着数乘的数字是可以提取的，如下面的公式所示：
$$mP + nP = \underbrace{P + P + \cdots + P}{m\ \text{times}} + \underbrace{P + P + \cdots + P}{n\ \text{times}} = (m + n)P $$

于是，可以证明 nP的集合是椭圆曲线形成的群里的一个具有循环性质的子群（the set of the multiples of P is a cyclic subgroup of the group formed by the elliptic curve.） 这里的P是生成元，或者叫基点。

也就是说，如果我们知道它是多少阶的循环群的话，计算 nP的代码就可以更加精简。

2.4 循环子群的阶讨论

之前不难发现，P生成子群地阶是多少。之前那个P的倍乘是一个5阶循环子群，对于其他的P和曲线而言不一定适用。那么，如何去计算阶数n呢？显然用 Schoof算法不可行，毕竟它是对于一整个椭圆曲线适用，对于其子群无效。

设一个群G的阶为N。任取一个生成自群G的循环子群，设它的阶数是n，生成元为P， n,P 满足的条件是 nP=0 。就好像之前的 5P=0 。（这里的群说的是有限域内的椭圆曲线，只说思路，没加证明）
P 的阶和椭圆曲线是有联系的，根据拉格朗日定理，子群的阶是父群的阶的因子。换句话说，如果一个椭圆曲线包含 N 个点，它的一个子群包含 n 个点，那么 n 是 N 的因子。

结合上述两个定律，那么n的计算可以通过如下步骤

用 Schoof 计算椭圆曲线的阶 $N$
从小到大遍历 $N$ 的所有因子
找到最小的$n$ 使得 $nP = 0$

2.5 寻找子群与离散对数问题

之前讨论了很多椭圆曲线上的东西。那么，如何利用ECC去加密解密呢？

首先补充一点拉格朗日定理的东西。拉格朗日定理证明$h = N/n$永远是一个整数，称 $h$为辅因子。引入$h$。那么可以得到$n(hP)=0$

由此，总结一下ECC的算法步骤

计算椭圆曲线的阶 $N$
选择一个阶为 $n$ 的子群，n为素数且为$N$的因子。
计算辅因子 $h = N/n$
在曲线上选择一个基点 P
计算 $G = hP$
如果G是0，那么重新选择基点否则找到了阶为$n$，生成元为$P$的子群

。

现在，假设有一条的在有限域$\mathbb {F}_{p}$上的椭圆曲线，要解决的问题是：
如果我们已知 P和Q ，对于 Q = kP ，我们应该怎么去计算这个 k ?
这个是椭圆曲线中大名鼎鼎的离散对数问题。也是其最为核心之处。

ECC有趣的地方在于，它的离散问题看上去比其他密码学中的离散问题难多了。这就说明我们可以用更少的位数的整数 k 做到和其他加密算法一样安全级别的加密效果。

ECC 椭圆曲线加密算法学习————从实数域到有限域的椭圆曲线

0x00 前言

参考的网站

相关代码

预先准备的数学概念

群 Group

整数域和有限域

模运算 mod

形如$ y^2 ;\equiv ;A;(;mod;p;)$的同余方程求解问题

三次一元方程解的形式

0x01 椭圆曲线定义

1.1 标准形式的椭圆曲线绘制

1.2 椭圆曲线上的群G

1.3 群G上加法运算的各种情况

CASE 1 P = Q :

CASE 2 P != Q 并且 P + Q = -R:

CASE 3 P != Q 并且 P + Q = -P OR P + Q = -Q:

1.4 标量积与对数问题

0x02 有限域和离散对数领域的椭圆曲线

2.1 离散域上点的加法

CASE 1 P = Q :

CASE 2 P != Q 并且 P + Q = -R:

CASE 3 P != Q 并且 P + Q = -P OR P + Q = -Q:

2.2 椭圆曲线阶

2.3 从数乘到循环子群

2.4 循环子群的阶讨论

2.5 寻找子群与离散对数问题