说在前面

大部分加密算法都是基于较为困难的数学问题来实现的，比如RSA算法，就是通过对大整数的因式分解来加密数据，这些方式，加密容易，解密较为困难，这就是加密算法的目的，可以确保数据安全，本文主要讲述椭圆曲线加密

椭圆曲线离散对数问题

椭圆曲线上的两个点P和Q，k为整数

$$Q = kP$$

此处的乘法不是传统意义上的乘法，而是一种根据图像来计算的乘法，后面会说

椭圆曲线加密的数学原理

此处，P为基点，k为私钥，Q为公钥

给定k和P，根据加法法则，计算Q很容易
但是给定P和Q，计算k难（实际运用中，质数p会非常大，穷举出k非常慢）

椭圆曲线

首先来看看什么是椭圆曲线

这是椭圆曲线方程

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

除此之外，还需要满足

$$4a^3 + 27b^2 \neq 0$$

这是为了确保曲线中不包含奇点，这也就是说，在曲线中任意一点都存在切线。

[!TIP] 其实这也可以当作是椭圆曲线的判别式

这是一个椭圆曲线的图像，其中a=-2，b=4。

首先我们观察这个图像，我们很清楚的可以看到，这个图像是关于x轴对称，有点像一个小章鱼，虽然在椭圆曲线中也使用普通的加法运算符号，但实际运算过程是不一样的

椭圆曲线的加法

如图，图像上有A,B两点，现在要计算A+B，首先我们作一条过AB的直线，并且与图像相交于第三点C点，如图所示由于图像是关于x轴对称，接下来，做点C的对称点D，如图所示点D就是A+B的计算结果

椭圆曲线的乘法

其实就是椭圆曲线的加法，只不过是重复多次，比如此时我们要计算A+A，也就是2A，根据我们刚刚对于加法的理解，我们需要找到两个点并且交于第三点，可是这里没有两个点，怎么办呢？当然是直接做A点切线啦，此时此刻我们可以找到一个与图像的交点B，如图所示接下来，做点B关于x轴的对称点C，如图所示此处，C就是2A的计算结果，如果要计算3A呢？我们只需要将2A（C）与A做一次加法，然后取交点的对称点即可，如图所示点E即为3A的计算结果，后面的计算以此类推

[!NOTE] 如果现在，将所有的辅助连线去掉，只给你点A和点E，你可以推算出计算过程吗？

很显然，以上的计算，正着计算很容易，但是逆运算却相当困难，这也是这种加密方法安全的保障，你可以看出来，上面的例子中，Q是最终运算的结果，P就是基点A，但是只给你这两点，你却很难计算出k

现在我们来看这些点的散点图

十分的杂乱无章，没有丝毫规律可言，这就是我们的目的，越杂乱，越没有规律，则越难被破解

加密过程

$$Q=kP$$

选取一条椭圆曲线Ep(a,b)，并取一个基点P，也就是上文中的A
选定一个大数k作为私钥，并生成公钥Q=kP
加密：选择随机数r，将消息M生成明文C，密文是一个点对，即为C=(rP,M+rQ)
解密：M+rQ-k(rP)=M+r(kP)-k(rP)=M

有限域

从上文我们可以知道，椭圆曲线是连续的，不适合加密，所以我们要把椭圆曲线变成离散的点，所以我们要把椭圆曲线定义在有限域上

什么是域

域是一个可以在其上进行加法，减法，乘法，和除法运算，而结果不会超出域的集合

比如：有理数集合、实数集合、复数集合都是域，但整数集合不是

[!TIP] 很显然，使用除法得到的分数或者小数已经超出整数集合

什么是有限域

如果域F只包含有限个元素，则称其为有限域。
有限域中元素的个数被称为有限域的阶
每个有限域的阶必须为素数的幂，即有限域的阶可以表示为$p^n$，其中p是素数，n是正整数，该有限域通常称为Galois域，全称为Galois Fields，记作GF($p^n$)
有限域上的圆锥曲线

在域的定义基础上，作如下修改

定义模p加法和模p乘法（加或乘的结果超过p时，模p取余数，p为素数）
集合内的元素经过加法和乘法计算，结果仍然在集合内
计算符合交换律、结合律、分配律
加法和乘法有单位元素（所有的集合内的值都有对应的附属，所有集合内非零值都有倒数）
有限域上的椭圆曲线运算

现在我们定义一条椭圆曲线，$y^2=x^3+x+1$，并且在有限域GF(23)下，我们可以写成下面这种形式

$$y^2 \equiv x^3+x+1 \pmod{23}$$ 此时椭圆曲线就已经不再是一条光滑的曲线了，而是一些不连续的点，如下图所示

Air-ban / Air-ban.github.io

浅谈椭圆曲线加密体系（一） #24