More than 3 years have passed since last update.

ECC 椭圆曲线加密算法(一)

Posted at 2023-03-02

椭圆曲线

椭圆曲线的一般表现形式：$y^2= x^3+ax+b$

椭圆曲线其实不是椭圆形的，而是下面的图形：

Bitcoin 使用了 secp256k1 这条特殊的椭圆曲线，公式是：
$y^2=x^3+7$
这个东西怎么加密的呢？

19 世纪挪威青年 尼尔斯·阿贝尔 从普通的代数运算中，抽象出了加群（也叫阿贝尔群或交换群），使得在加群中，实数的算法和椭圆曲线的算法得到了统一。是什么意思呢？

我们在实数中，使用的加减乘除，同样可以用在椭圆曲线中！
对的，椭圆曲线也可以有加法、乘法运算。

数学中的群是一个集合，我们为它定义了一个二元运算，我们称之为“加法”，并用符号+表示。假定我们要操作的群用𝔾表示，要定义的加法必须遵循以下四个特性：

如果在增加第 5 个条件：
交换律：a + b = b + a

那么，称这个群为阿贝尔群。根据这个定义整数集是个阿贝尔群。

岔开一下话题，伽罗瓦 与 阿贝尔 分别独立的提出了群论，他们并称为现代群论的创始人，可惜两位天才都是英年早逝。

如上文所说，我们可以基于椭圆曲线定义一个群。具体地说：

在椭圆曲线上有 不重合且不对称的 A、B 两点，两点与曲线相交于 X 点，X 与x轴的对称点为 R，R 即为 A+B的结果。这就是椭圆曲线的加法定义。

因为椭圆曲线方程存在 $y^2$项，因此椭圆曲线必然关于 x 轴对称

曲线：$y^2=x^3+5x+7$，
坐标：A=(2,5)，B=(3,7)
A、B 正好在曲线上，因为坐标满足曲线公式
$5^2=2^3+52+7=25$
$7^2=3^3+53+7=49$
那如何找到相交的第三个点呢？

通过 A、B 两点确定直线方程，
设直线方程：$y=mx+c$，m 为直线的斜率
$m=\dfrac{B_y-A_y}{B_x-A_x}=\dfrac{7-5}{3-2}=2$
进一步得到 c=1。

联立方程：

$$
\begin{equation}
\left.\begin{aligned}
y=2x+1\
y^2=x^3+5x+7\
\end{aligned}\right}
\Rightarrow x^3-4x^2+x+6=0
\end{equation}
$$

X(-1,-1) 的 x 坐标 -1 代入方式正好满足方程，所以 A、B 两点所在直线与曲线相交于 X(-1,-1)，则点 X 的关于 x 轴的对称点为 R(-1,1)，即 A(2,5)+B(3,5)=R(-1,1)。

根据椭圆曲线的**群律 (GROUP LAW)**公式，我们可以方便的计算 R 点。

曲线方程：$y^2=x^3+ax+b$
当 A=(x1,y1)，B=(x2,y2) ，R=A+B=(x3,y3)，x1≠x2 时，
$m=\dfrac{y2-y1}{x2-x1}$，m 是斜率
x3=$m^2-x1-x2$
y3=m(x1-x3)-y1

A=(2,5), B=(3,7) , R=(-1,1) 符合上面的公式。

椭圆曲线加法符合交换律么？

先计算 (A+B)，在计算 A+B+C

先计算 B+C，在计算 B+C+A

看图像，计算结果相同，大家手动算下吧。

那 A + A 呢，怎么计算呢？

当两点重合时候，无法画出“过两点的直线”，在这种情况下，
过 A 点做椭圆曲线的切线，交于 X 点，X 点关于x轴的对称点即为2A，这样的计算称为“椭圆曲线上的二倍运算”。

下图即为椭圆曲线乘法运算：

我们将在ECC 椭圆曲线加密算法 (二) 介绍有限域，椭圆曲线的离散对数问题，椭圆曲线加密就是应用了离散对数问题。

参考：