比特币采用了椭圆曲线签名算法来签署交易,这节我们来看看椭圆曲线加密的数学原理,看看在选定了私钥之后,如何运算出公钥。

椭圆曲线的点相加定理

首先来聊聊什么是椭圆曲线,以及椭圆曲线上两点相加是一个什么概念。

由方程 y² = x³+ax+b 所描述的曲线就叫做椭圆曲线 ,椭圆曲线相对于 x 轴对称,随着 a、b 取值的不同,方程对应不同的曲线。比特币使用的曲线方程是 y² = x³+7,这条曲线被命名为 secp256k1。

下面就描述一下什么是椭圆曲线的点相加定理。

若在椭圆曲线上选出两个点,点相加定理规定了如何得到这两个点相加的结果。首先我们要把这两个点用一条直线连接起来,那么在通常条件下可以得到这条直线与椭圆曲线相交的第三个点。然后再找到第三个点相对 x 轴的对称点,这个点也在椭圆曲线上,就是之前两点相加的结果。那么这个规则就是椭圆曲线的点相加定理。

点相加定理的一种特殊情况是我们只在椭圆曲线上选出一个点 P,如果我们想得到 P+P 的结果,就需要在 P 点做椭圆曲线的切线,这样在通常条件下也可以得到这条切线和椭圆曲线的另外一个交点,找到这个交点相对 x 轴的对称点 Q,那么 Q=P+P=2*P

这样点相加定理就介绍完毕。

优化点相加运算过程

已知比特币的私钥 x ,要运算公钥 X,就需要用到点相加定理。具体做法就是选定一个点 P,那么 X=x*P。x 是一个32字节的整数,所以很可能是一个非常大的数,但是运算 x*P 的时候我们可以找到优化的点相加的运算过程。

例如,我们要运算 10*P ,直观上我们会认为要进行9次点相加运算,但是实际上只需要4次,这是因为点相加满足 n*P+r*P = (n+r)*P 。所以,运算 10*P 的最快方式是分解为下面四步:

P+P = 2*P
2*P+2*P = 4*P
4*P+4*P = 8*P
2*P+8*P=10*P

而对于 x*P,我们可以推导出这样的结论,对于任意的私钥 x,要运算出公钥 X,最多只需要进行510步的点相加运算,所以对于计算机来说并不是一个很大的计算任务。比特币对于 P 的取值是有明确规定的,在 secp256k1 曲线上, P 点的 x 坐标 和 y 坐标分别为:

x 坐标: 55066263022277343669578718895168534326250603453777594175500187360389116729240

y 坐标: 32670510020758816978083085130507043184471273380659243275938904335757337482424

x 和 P 以及椭圆曲线确定之后,就可以运算 X 了。X 是椭圆曲线上的一个点,这样比特币公钥就是这个点的 x 和 y 坐标值拼接起来的整数。 优化椭圆曲线模型 现在遗留的问题是由于 x 取值的可能性很多,那么 x*P 得到的点的 x 和 y 值很可能不能被保存成一个标准的512 bit 的公钥,所以就要对我们的椭圆曲线模型做一下优化。

优化方案是把椭圆曲线定义在一个有限域内,目的是要确保只有整数点,并且每个点的横纵坐标值都不会过大。具体的规定请查看文末的参考链接。我们只需要知道模型在优化之后,之前讨论的各种操作依然是可行的。

总结

以上介绍了椭圆曲线的加密原理,我们了解了从私钥运算公钥的基本过程,但是没有论述二者是不是合格的非对称加密的秘钥对,例如,由公钥是不是很难运算出私钥,以及论述用私钥是否可以生成出可以被公钥验证的数字签名。关于这些问题,我们将在下一篇文章中介绍。

参考