btc address: 1FmWXNJT3jVKaHBQs2gAs6PLGVWx1zPPHf
eth address: 0xd91c747b4a76B8013Aa336Cbc52FD95a7a9BD3D9
随着区块链的大热,椭圆曲线算法也成了密码学的热门话题。在Bitcoin 生成地址 中使用到了椭圆曲线加密算法。
椭圆曲线的一般表现形式:
椭圆曲线其实不是椭圆形的,而是下面的图形:
Bitcoin使用了 secp256k1 这条特殊的椭圆曲线,公式是:
这个东西怎么加密的呢?
19世纪挪威青年 尼尔斯·阿贝尔 从普通的代数运算中,抽象出了加群(也叫阿贝尔群或交换群),使得在加群中,实数的算法和椭圆曲线的算法得到了统一。是什么意思呢?
我们在实数中,使用的加减乘除,同样可以用在椭圆曲线中!
对的,椭圆曲线也可以有加法、乘法运算。
数学中的群是一个集合,我们为它定义了一个二元运算,我们称之为“加法”,并用符号 + 表示。假定我们要操作的群用𝔾表示,要定义的 加法 必须遵循以下四个特性:
如果在增加第5个条件:
交换律:a + b = b + a
那么,称这个群为阿贝尔群。根据这个定义整数集是个阿贝尔群。
岔开一下话题, 伽罗瓦 与 阿贝尔 分别独立的提出了群论,他们并称为现代群论的创始人,可惜两位天才都是英年早逝。
如上文所说,我们可以基于椭圆曲线定义一个群。具体地说:
在椭圆曲线上有 不重合且不对称的 A 、B两点,两点与曲线相交于X点, X与 x轴 的对称点为R,R即为 A+B 的结果。这就是椭圆曲线的加法定义。
因为椭圆曲线方程存在 项,因此椭圆曲线必然关于x轴对称
曲线: ,
坐标:A=(2,5),B=(3,7)
A、B正好在曲线上,因为坐标满足曲线公式
那如何找到相交的第三个点呢?
通过 A、B两点确定直线方程,
设直线方程: ,m为直线的斜率
进一步得到c=1。
联立方程:
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点。
曲线方程:
当A=(x1,y1),B=(x2,y2) ,R=A+B=(x3,y3),x1≠x2时,
, m是斜率
x3=
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椭圆曲线加密算法(二) 介绍有限域,椭圆曲线的离散对数问题,椭圆曲线加密就是应用了离散对数问题。
参考:
https://eng.paxos.com/blockchain-101-foundational-math
https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/