Open AlexiaChen opened 4 years ago
Hi, 为什么单位圆上的两点相加仍然在单位圆里面?(0,1) + (0,-1) = (0,0)
Hi, 为什么单位圆上的两点相加仍然在单位圆里面?(0,1) + (0,-1) = (0,0)
@200930740208 , 因为这里的加法跟你理解的不一样,你把曲线看作一个集合,这个集合上的元素(点)的加法需要满足交换群的规则,所以这里的加法是通过技术手段构造出来的,群的一个基本性质就需要有封闭性。群里面的二元操作运算比较抽象的概念。你就可以理解,这个单位元是一个抽象的世界,这个世界的点的加法就是这么定义的。
ed25519公钥也满足类似于secp256聚签那种加法吗?如aG+bG=(a+b)*G
ed25519公钥也满足类似于secp256聚签那种加法吗?如aG+bG=(a+b)*G
@aranjuezzzz ECDSA签名不是线性的,当然不能聚合签名。你说的是schnorr。
ed25519公钥也满足类似于secp256聚签那种加法吗?如aG+bG=(a+b)*G
@aranjuezzzz 你看下ZenGo X的EdDSA的multi party的库。
写的真好,尤其是Gy=4/5转为有限域元素
写的真好,尤其是Gy=4/5转为有限域元素
@ylshaa 😂,能有帮助就好,但是我有一段时间没搞密码学和区块链了。
深入了解Ed25519
都知道Ed25519是一种比较新的椭圆曲线签名方案,相比ECDSA,也就是基于传统 Weierstrass形式的椭圆曲线(secp256r1 secp256k1)的签名方案,它综合对比下来是要好上不少的。它是EdDSA方案的一种实现之一。
现在ECDSA的工程实现,从效率上来看,已经被实现优化得非常快了,比如在OpenSSL等密码签名库中。
但是安全性还是有些欠缺,随着技术的改进以及CPU新指令的出现,还可以逐步提升执行速度. 然而更好安全性与更高的执行效率的诉求, 或许无法通过这种小步迭代和缝缝补补方式得到满足。同时解决前述的应用安全, 实现安全以及执行效率的问题, 要求在工程手段之外更为深度的改进, 一个自然的方向是重新构建椭圆曲线以及签名机制以便在多个层次上同时改进。
直到2007年HAROLD M. EDWARDS发表了一篇《A Normal Form For Elliptic Curves》的论文,由此引出了一种椭圆曲线的一种新的表达形式,这种形式表达的椭圆曲线就叫爱德华曲线(Edwards Curves)。这曲线是最近几年才被密码学社区广泛关注的,因为这种形式的椭圆曲线更简洁,高效,曲线上点的加法表达也更优美。
爱德华曲线是这样的:
至于为什么椭圆曲线有这样更一般化的表达形式,是因为每个在非二元域(non-binary field)的椭圆曲线在代数上同构于这个曲线在该非二元域的扩张域下的爱德华形式,甚至在多数情况下同构于该非二元域的爱德华形式。同构你可以理解成在代数上等价,或者说,在代数角度看,这两个曲线是一样的,简单点说就是它两灵魂相同但是几何形状不同。为什么在数学上要找同构? 因为就是让研究者们研究更本质的东西,去除掉这些虚有其表的肤浅的东西。在另一个简单的对象中研究一个与之本质相同的复杂的对象,化繁为简。
就在2007年的当年,随后Daniel J. Bernstein和Tanja Lange就跟进了爱德华曲线的论文研究,并在此基础上发表了《Faster addition and doubling on elliptic curves》的一篇论文,论文在研究的过程中,提到了爱德华曲线一种更加简单的形式:
由上图可以看出,随着d向负数变化(从0,-2,-10,-50,-200),曲线越来越像海星。当d = 0时,曲线就是单位圆,这个从方程里就可以看出来了,x^2 + y^2 = 1。
单位圆点上的加法当然就是显而易见的了,看下图:
设P3 = P1 + P2, P3的坐标是(x3,y3),且α是P1到圆心的连线与y轴的夹角,β是P2到圆心的连线与y轴的夹角,那么P3的坐标满足:
椭圆曲线密码学的一个共识就通过一个已知的点(G点)来构造一个新的点,爱德华曲线上点的加法就很类似单位圆点上的加法,与传统的Weierstrass或Koblitz形式的椭圆曲线上的点的加法不一样,它有自己的加法构造方式。之前我也写过一篇文章主要讲解Weierstrass形式下的椭圆曲线上点的加法运算方式,就不讲解了。
以下就是爱德华曲线的点加法运算了:
既然定义了加法,那么就可以定义二倍乘法,(x1,y1) + (x1,y1) = (x3,y3) = 2P = R
由此就定义了点的标量乘法。
当然,这个爱德华曲线上的加法证明还是非常复杂的(感兴趣可以读原论文),来源于欧拉,高斯得早期的工作,两个世纪前就被发现了,只是近几年才被引入密码学社区。这个爱德华曲线上的加法就比 Weierstrass 和 Koblitz形式的椭圆曲线简单得多,所以近几年非常受欢迎。 Koblitz形式的椭圆曲线(又叫Koblitz曲线)我貌似没有写过,有空我新开一篇来讲解。
到了这里,从原始爱德华曲线再到它的简化形式,我们都了解了一遍,紧接着下一年,也就是2008年,Daniel J. Bernstein和Tanja Lange他们就对爱德华曲线的简化形式作出了修改,经过一系列的繁琐推导和证明,并发了一篇《Twisted Edwards Curves》的论文,提出了一种叫做扭曲爱德华曲线的形式,这个是对爱德华曲线更generalization的表达,扭曲爱德华曲线方程如下:
为什么这个曲线更generalization,看论文的intro就知道了:
因为扭曲爱德华曲线囊括了更多更广的在有限域上的曲线,并且囊括了所有Montgomery形式下的任何椭圆曲线(Montgomery曲线)。你可以暂时认为它们在某种程度上等价。Montgomery曲线的原始论文叫《Montgomery curves and their arithmetic》。
上图就是扭曲爱德华曲线了,样子就像个十字路口,中间是个大转盘。爱德华曲线的简化形式就是a*x^2 + y^2 = 1 + d*x^2*y^2扭曲爱德华曲线a = 1时候的特例。
扭曲爱德华曲线上点的加法:
既然爱德华曲线的简化形式x^2 + y^2 = 1 + d*x^2*y^2是扭曲爱德华曲线的a = 1,那么把a = 1代入上面的公式,就是简化爱德华曲线上点的加法公式
最终的疑问来了,扭曲爱德华曲线既然是爱德华曲线更generalization的形式,那么它到底是用来干什么的?它其实就是EdDSA签名方案(Ed25519)的底层那条曲线,也是Curve25519这套新的ECDH算法底层依赖的那条Montgomery形式的曲线。EdDSA更快更安全,ECDSA已经比较老了,效率也差些。EdDSA是近几年才开始流行的,算是比较先进前沿了吧。
重要的终于来了,基于前面这些论文的工作,Bernstein和Tanja Lange等人发明了Ed25519算法,并发表了一篇《High-speed high-security signatures》的论文(Ed25519的原始论文),下面要开始讲解Ed25519的签名算法。
上面提到了,Ed25519推荐用扭曲爱德华曲线,而且给定了扭曲爱德华曲线的参数a和d:
然后也给出了G点(Base Point), G点在论文中描述为B,(x,4/5) ∈ E。y = 4/5 = 8/10 = (u - 1)/(u + 1),且u = 9。这个u = 9的选取来自于Curve25519的原始论文。就不说为什么了,貌似作者也没说选取的规则,因为从理论上说,G点可以是曲线上的任意一点,反正曲线是在一个素域(Fp = 2^255 - 19)上(素域也叫有限域)。G点的选取其实也不是重重之重,这个了解下就可以,并没有什么深刻的数学或者安全原理,因为椭圆曲线密码学的安全并不依赖G点。
既然G点的y坐标为4/5, 那么代入曲线方程就可以求出x了:
以上的坐标是在曲线的实数域下的运算,所以有分数,要把坐标转到有限域上来,比如y = 4/5, 可以把y = 4/5 = 4*(1/5)。这样y坐标就描述为是4乘以5的逆元了,显然在有限域下,5的逆元是是一个无比大的正整数q, 4乘以这个数q,就是G点在有限域下的y坐标:
同理,x坐标计算出来后,也要这样计算,所以,最终G点在有限域下的坐标就是:
如果细心的人会发现,他们用百度搜索,或者其他搜索引擎搜出来的Ed25519算法所依赖的曲线并不是我们上面所说的-x^2 + y ^2 = 1 - (121665/121666)*x^2*y^2这个曲线方程啊,而是y^2=x^3 + 486662*x^2 + x这个方程。太奇怪了,这两个曲线不一样。
下面我来解释下为什么,主要是这里有之前几篇论文做支撑的,大家都知道Curve25519所依赖的曲线是Montgomery Curve:
可以看出来,这个曲线与爱德华曲线是在同一个有限域下的,在论文《Faster addition and doubling on elliptic curves》中指出Curve25519所依赖的这条曲线双有理等价( birationally equivalent)这条爱德华曲线:
把Montgomery Curve的y表示成v,x表示成u:
那么从Montgomery Curve上的点等价变换到这条爱德华曲线上的点的公式就是:
细心的人也发现,Ed25519的G点的y坐标公式就是,Montgomery Curve曲线上的x坐标等于9(即u = 9)变换过来的了。
然后,这条爱德华曲线同构于以下这条扭曲爱德华曲线:
这条扭曲爱德华曲线刚好就是Ed25519给定参数的曲线。
注: 双有理等价又叫双有理同构(birationally isomorphic),是代数几何(algebraic geometry)的内容,代数几何是弦论(String Theory)的数学基础工具之一,我们不做过多讨论,把它当性质用,不要过多问为什么。读密码学的论文,里面很多东西都需要把个别一些数学性质当作黑盒来用,没必要深究,这点很重要,这是做任何领域研究的一个基本原则,没有人能搞懂所有,所谓站在巨人的肩膀上就是如此。
好了,到这里为止,有点偏题了,接下来继续讲解Ed25519签名算法。
由前面素数,以及G点的坐标可知,写成Python为:
因为Ed25519的参数a和d也知道了:
以上的d参数,就是把除法转换为分数乘法,再转换成模逆乘法,因为是在有限域下的运算。之后遇到公式里面涉及到除法,全部这样转换。
好,以下就可以根据加法公式写成python:
当然,定义好了点的加法,也间接就能定义点的标量乘法了,k*P = R,R点就相当于k个P点相加,也就是循环调用point_addition方法了:
接下来就可以通过k*G = Public Key这个公式来生成秘钥对了,k其实就是秘钥,也就是本地生成的一个256位随机数:
基础工作做好了,接下来就是签名和验证签名,在此之前需要把待签名的message编码成一个大整数表示,并且也要给message做hash, hash的目的是为了后面每个消息都有不同的随机数,这是为了安全
签名开始, 最终(R,s)这个二元组就是签名后的数据,验证者可以通过签名数据和message来验证
以下是验签:
以下给个完整的python例子:
这个验证签名的公式我就不列出来了,看了代码以后可以自己写出来。
好了,以上就是Ed25519的算法原型了,当然,实际的开源算法库的实现,会比这个复杂得多得多,用了很多高性能的方法实现pow,模逆,还有打表等方式来给这些计算加速,实际工程代码量会很大很大,也不好读懂。
当然,还有一种非常实际的方法就是,把椭圆曲线的在二维坐标(仿射坐标系)转换成其他坐标系(射影坐标系,雅可比坐标系)来处理,这样可以直接避免求逆。因为转换到这几个坐标系中,你就会发现,在二维平面上点的加法公式中的除法消失了,取而代之的是另一个坐标系下的没有除法的公式。
好奇可以看我写的这篇文章,从群环域到椭圆曲线,里面有说明。
我这里还是简单解释下,在仿射坐标系(Affine Coordinates)中,椭圆曲线的单位元O(无穷远点,point at infinity)并没有很好的表示,因为表达不出来,是个很抽象的概念。在数学上,无穷远点是在射影坐标系中衍生出来的概念,大家都见过在射影空间中的满足斯特拉斯椭圆方程(Weierstrass)的椭圆曲线,是用三维坐标表示,在几何意义上,射影空间中的点就是高一维仿射空间中过坐标原点的直线,当Z = 0时,就意味着是无穷远点。这个三维坐标不是我们平常理解的那个3D坐标,不是一个东西。Z != 0时,就是曲线上的点,在射影空间中 (1,2,1) -> (1,2,4213) -> (1,2, Z) 这两个点都是一个点,有无穷个点都是同一个点。
注: 射影坐标(Projective Coordinates)有时候也叫齐次坐标系。
所以了,实际中,因为雅可比坐标(Jacobian Coordinates)用到的更多一些,可以先将仿射坐标的点表示为雅可比坐标形式,不必求逆,因为求逆操作计算太慢了(上面python用的扩展欧几里德算法求模逆运算太慢了),计算完成得到结果,在把结果点转换为仿射坐标形式。Ed25519实际工程中的点的加法就用了齐次坐标(因为曲线不同),由RFC8032给出。
转换到另一个坐标体系下,都有固定的公式的,这个自己上网查,留个课后习题,因为python例子中,点的加法是用仿射坐标系下的公式计算的,所以把我的python算法例子,改成用雅可比坐标来加速计算 :P
参考资料