本篇将会介绍椭圆曲线加密（ECC）的一些基本知识。

椭圆曲线的概念

一般来说，椭圆曲线是由如下方程定义的平面曲线： $$ y^2 = x^3 + ax + b $$ 其中 $$ -16(4a^3 + 27b^2) \neq 0 $$ 虽然叫椭圆曲线，但图像和椭圆关系不大，图像类似如下：

该曲线的一个特点是，在图中随机作一条直线，和曲线最多有三个交点。

椭圆曲线上的运算规则

我们基于椭圆曲线定义一个阿贝尔群（单位元定义为无穷远点），加法运算法则：任意取椭圆曲线上两点A、B （若A、B两点重合，则做A点的切线）作直线交椭圆曲线于点C，过这点做y轴的平行线交椭圆曲线于一个新的点。我们规定这个点就是A+B，如下图所示。

那么如何用公式计算呢？很简单，

第一步，

当A不等于B时，求两点连线的斜率： $$ \lambda = (y_B-y_A)/(x_B-x_A) $$ 当A和B重合时，计算过点A的切线的斜率，可以在椭圆曲线方程两边求导得到： $$ \lambda = (3x_A^2+a)/2y_A $$ 第二步，就可以计算点C=A+B的坐标，具体推导省略， $$ x_C=\lambda^2-x_A-x_B $$

$$ y_C = \lambda(x_A-x_C)-y_A $$

而对于乘法，比如B=kA，其实就是k个A相加的结果。

有限域椭圆曲线

由于椭圆曲线是连续的，上面的点可能并不适合用于加密，因为计算机无法精确保存浮点数，如果把一个浮点数作为加密密钥，那么很可能无法还原密文，所以，我们必须把椭圆曲线变成离散的点，并且要把椭圆曲线定义在有限域上。

假设椭圆曲线为$y^2=x^3+x+1$，在有限域$F(p)$上时，椭圆曲线不再是一条光滑曲线，而是一些不连续的整数点，如下图所示（这里p取23），

计算方法和上面类似，只需在计算坐标时取模， $$ x_C=\lambda^2-x_A-x_B\mod p $$

$$ y_C = \lambda(x_A-x_C)-y_A \mod p $$

这时又有个新的问题，如果取模之前不是整数怎么办？

假设求a/b mod p，可以转化成 a*k mod p (k是b的模p的乘法逆元)，k可由扩展欧几里得算法求得，这样就解决了有限域椭圆曲线上的计算问题。

To be continued…