区块链-比特币加密算法的椭圆曲线

内容：

内容

谈比特币的加密算法，椭圆曲线永远是一个绕不开的坑。以下笔记是通过观看比特币加密教程总结的，图片来源于网络。

ECDSA 算法

椭圆曲线乘法（又称ECDSA）是密码学中一种重要的非对称加密算法。同时，在比特币系统中，私钥是使用 ECDSA 算法生成的。比特币使用特殊的椭圆曲线和secp256k1标准定义的一系列数学常数

椭圆曲线识别椭圆曲线

椭圆曲线不是椭圆，而是满足上述方程的一组连续的 x 和 y 点。解释方程

1、x,y 是两个实数

2、a,b是两个常数，满足4a² - 27b³ ≠ 0

3、满足 y² = x³ + ax + b

4、包含无穷大点，我们定义无穷大点为0

注意：

1、椭圆曲线不是一条线，而是一个群。不同的a和b值表现出不同的曲线，如上图所示。比特币使用的曲线是secp256k1

2、连接曲线上任意两点P和Q的直线必须且只能在第三点-R与曲线相交

3、曲线不一定关于x轴对称

椭圆曲线上的点相加

注意：我们在这里讨论的加法是几何加法比特币非对称加密算法，不要与代数加法混淆。

简单来说，一条直线和一条椭圆曲线相交于3个点，分别是P、Q、-R，那么有P+Q=-R推导出P+Q+R=0；

p>

这里我们分情况讨论：

1、假设Q = 0，即Q处于无穷大，即无穷大点，则P + Q = P + 0 = P

2、假设两点关于X轴对称，如上图R，-R，则R+(-R)=0；如何理解？ R和-R用直线相连，平行于Y轴，与椭圆曲线相交于无穷远，即0

3、假设 P != Q ，则 PQ 直线与椭圆曲线在 -R 点相交，则 P + Q = R；如何理解？ P、Q、-R三点的直线在无穷远处与椭圆曲线相交，即P+Q+(-R)=0=>P+Q=R

4、假设P=Q，经过点P的切线，在-R点与椭圆曲线相交，则P+Q=-R=>2P=-R

椭圆曲线上的点相乘

现在，假设曲线上有一个点 G，我们需要曲线上的一个点 N = 8 * G ，我们可以通过加法来完成，即 N = 8 * G = G + G + G + G + G + G + G + G ;但是有一个问题，如果不是8G，而是8000G，80000G，计算量很大，所以我们可以使用“乘法”，如下图：

乘法过程如下：

1、过G点做切线，与椭圆曲线相交的点为-2G，-2G = G + G

2、-2G点上下翻转得到2G交点

3、通过2G点的切线可以计算得到-4G = -2G + - 2G

4、-4G点上下翻转得到4G交点

5、等等……

有限域的椭圆曲线

椭圆曲线是一条连续曲线，上面所有的点都是实数（带小数），但是计算机的精度误差，小数的保留是有限的，明文加解密后会有偏差，将无法获得原始明文。因此，我们需要一组离散的整数点来满足加密的要求。这是我们接下来要使用的有限域椭圆曲线。

如何得到有限域曲线，我们需要先了解几个概念：模运算、同余、有限域

简单来说就是商和余数，如：

5除以3等于1，余数=2，可以表示为5 mod 3 = 2，即取模运算。

我们组织公示 a mod b = r ，取模运算有以下特点：

(a + b) mod c = {(a mod c) + (b mod c)}mod c

(a*b) mod c = {(a mod c)*(b mod c)}mod c

(a^b) mod c = ( a mod c )^b mod c

a 和 b 两个数除以 c ，余数相同，即全等。我们可以将其表示为：a mod c = b mod c 或 a

p>

b (mod c)

如果 k ∈ Z（k 是一个整数），a

b (mod c) ka

kb (mod c)

例如 k =3 , 2

6 (mod 4) , 名称 3*2

3 * 6 (mod 4)@ >

顾名思义就是元素的有限集合，比如Z mod 7 = {1, 2, 3, 4, 5, 6}，就是一个有限域

根据椭圆曲线公式，y² = x³ + ax + b比特币非对称加密算法，设 a = -7 , b = 10 ,

确定的椭圆曲线公式，y² = x³ - 7x + 10

那么，我们如何设置有限域呢？如何只取整数点？如何使曲线离散？我们只需要这个

1、Fp 有 p（p 是素数）元素 0,1 ,2,…, p-2,p-1

2、x , y∈Fp

3、y² = x³ - 7x + 10 (mod p)

当p取不同值时，p=19,97,127,487，离散后的图如下，可见p值越大，离散点越多

@ >

你不明白为什么 mod p 是离散的和不连续的吗？我们用一个简单的公式来解释一下，假设 x, y ∈ {1, 2, 3, 4 , 5, 6} , p =3

有限域上满足方程的(x,y)点都是离散的，不能再连接成椭圆曲线，也不可能用直线连接曲线上的3个点，那么如何我们做加法吗？乘法怎么做？

显然，我们需要稍微改变加法的定义，使它在 Fp 中。对于实数，我们说三个对齐的点之和为零（P+Q+R=0）。我们可以保留这个定义，但是在 Fp 中对齐三个点是什么意思？

如果有一条直线将它们连接在一起，我们可以说所有三个点都是对齐的。但是，Fp 与 R 不同。Fp 是满足方程 ax+ bÿ+c≡0(mod p) 的点 (x, y) 的集合（这是标准线型，加上“(modp)”）。

待续……

Secp256k1 Secp256k1 曲线点操作特性 为什么椭圆曲线是不可逆的