ECC 椭圆曲线加密算法学习————从实数域到有限域的椭圆曲线
九涅·烧包包儿 / / 程序员 / 阅读量

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 运行,大概的用法如下所示:

➜  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 做到和其他加密算法一样安全级别的加密效果。

支付宝捐赠
请使用支付宝扫一扫进行捐赠
微信捐赠
请使用微信扫一扫进行赞赏
有 0 篇文章