比特币源码研读(6)—— 椭圆曲线加密法

比特币私钥生成公钥,用到的方法就是椭圆曲线加密法。椭圆曲线加密法是一种基于离散对数问题的非对称加密法,只能从私钥推出公钥,不能从公钥逆推出私钥。这是一个复杂的加密法,我们可以先从简单的类比开始。

简单的理解

均益在知乎上看到一个简单类比

 
先看一个栗子:
小明就读于小学二年级,会计算加法,但是不会计算除法。你是小明的怪蜀黍大强,你想出一道题给他做,让他虽然能理解题目意思但是做起来有难度:
强:“小明小明,过来,叔叔问你,1+1等于几?”
明:“叔叔的大学白念了吧,我幼儿园就会了,等于2。”
强:“那考你个难的,7+7等于几?”
明:“切,你当人家上课啃铅笔头,下课帮小红写作业都是白干的是吧。手指都不用数,等 于14呗。”
强:“行,有叔叔当年的风采,那叔叔再问你,几个7相加等于56?”
明:“……”,默默掏出草稿纸、铅笔、手指头、脚趾头,进行了10分钟的深度计算:2个7等于14,3个7等于21,4个7等于28……。“叔叔,我算出来了,是8个,对不对?”
强:“好小子,叔叔就不信考不倒你。几个7相加等于864192?”
你心中默念,以小明的计算能力,要算到这个数恐怕得一年半载的。
明:“叔叔好厉害呀,我算不出来。”
明天去考考小红看她会不会算几个7等于56,不会算我就教她,嘿嘿。”

与上述例子相同的是,椭圆曲线密码也是一个基于加法阶数难求问题的密码方案。 对于椭圆曲线密码来讲,椭圆曲线的基点就是例子里面的7,而私钥就是基点的加法阶数(例子里面的8),公钥是基点(7)进行对应阶数的加法(8次)得到的结果(56)。

椭圆曲线加密法的原理

椭圆曲线加密法的定义的加法,与我们日常熟悉的加法不一样。椭圆曲线的加法在几何上的定义,如下图

两个不同的点相加
图一:两个不同的点相加
两个相同的点相加
图二:两个相同的点相加

两个点的加法结果是指这两点的连线和曲线的交点关于x轴的镜像。
若两个点相同,则取这个点切线相交的点。该切线的斜率可用微积分求得。即使限制曲线点为两个整数坐标也可求得斜率!
为什么要定义如此复杂的加法?就是为了制造不会“除法”(由公钥计算私钥)。

secp256k1

比特币使用了secp256k1标准所定义的一种特殊的椭圆曲线和一系列数学常数。该标准由美国国家标准与技术研究院 (NIST)设立。
secp256k1 椭圆曲线域E(Fp)的描述参数:
E : y^2 ≡ x^3 + ax + b (mod p)

mod p(素数p取模)表明该曲线是在素数阶p的有限域内
为描述特定的椭圆曲线域,需明确六个参数:T = (p, a, b, G, n, h)

p: 代表有限域Fp的那个质数
a,b:椭圆方程的参数
G: 椭圆曲线上的一个基点G = (xG, yG)
n:G在Fp中规定的序号,一个质数。
h:余因数(cofactor),控制选取点的密度。

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
= 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1
a = 0
b = 7

xG = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
yG = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01

secp256k1标准定义的椭圆曲线几何图类似于下图

椭圆曲线的示例
椭圆曲线的示例

生成公钥

K = k * G

其中k是私钥,G是生成点,在该曲线上所得的点K是公钥。因为所有比特币用户的生成点是相同的,一个私钥k乘以G将得到相同的公钥K。k和K之间的关系是固定的,但只能单向运算,即从k得到K。这就是可以把比特币地址(K的衍生) 与任何人共享而不会泄露私钥(k)的原因。
下图显示了在曲线上得到 G、2G、4G 的几何操作。
在曲线上得到 G、2G、4G 的几何操作
提示比特币用的是libsecp256k1加密库,计算得到公钥。

参考链接:
https://www.zhihu.com/question/22399196
https://en.bitcoin.it/wiki/Secp256k1
http://book.8btc.com/books/6/masterbitcoin2cn/_book/ch04.html

Leave a Reply

Your email address will not be published. Required fields are marked *