ECC算法和加密应用大全

ECC算法和加密应用大全（一）基本原理ECC（EllipticCurvesCryptography）加密算法是一种公钥加密算法，与主流的RSA算法相比，ECC算法可以使用较短的密钥达到相同的安全程度。近年来，人们对ECC的认识已经不再处于研究阶段，开始逐步进入实际应用，如国家密码管理局颁布的SM2算法就是基于ECC算法的。下面我们来认识一下ECC的工作原理。椭圆曲线定义在引入椭圆曲线之前，不得不提到一种新的坐标系-------射影平面坐标系，它是对笛卡尔直角坐标系的扩展，增加了无穷远点的概念。在此坐标系下，两条平行的直线是有交点的，而交点就是无穷远点。两者的变换关系为：笛卡尔坐标系中的点a（x,y），令x=X/Z，y=Y/Z，则射影平面坐标系下的点a的坐标为（X,Y,Z)，如点（2,3）就转换为（2Z,3Z,Z）。椭圆曲线定义：一条椭圆曲线在射影平面上满足方程：Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3的所有点的集合，且曲线上每个点都是非奇异的。该方程有名维尔维斯特拉斯方程，椭圆曲线的形状不是椭圆，只是因为其描述的方程类似于计算一个椭圆周长的方程。转换到笛卡尔坐标系下的方程为：y2+a1xy+a3y=x3+a2x2+a4x+a6加法法则运算法则：任意取椭圆曲线上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R。我们规定P+Q=R。（如图）此处+不是简单的实数相加，是抽象出来的O∞+P=P，O∞为零元曲线上三个点A,B,C处于一条直线上，则A+B+C=O∞下面，我们利用P、Q点的坐标(x1,y1)，(x2,y2)，求出R=P+Q的坐标(x4,y4)。P,Q,R'共线，设为y=kx+b，若P≠Q，k=(y1-y2)/(x1-x2)若P=Q，k=(3x2+2a2x+a4-a1y)/(2y+a1x+a3)解方程组得到：x4=k2+ka1-a2-x1-x2;y4=k(x1-x4)-y1-a1x4-a3;密码学中的椭圆曲线定义在有限域Fp中定义一个椭圆曲线，常用y2=x3+ax+bFp中只有p个元素，p为素数Fp中，a+b≡c(modp)，a×b≡c(modp)，a/b≡c(modp)4a3+27b2≠0(modp)a，b是小于p的非负整数x，y属于0到p-1间的证书，曲线标记为Ep（a，b）阶：椭圆曲线上一点P，存在正整数n，使得nP=O∞，则n为P的阶，若n不存在，则P是无限阶的，有限域上定义的椭圆曲线上所有点的阶都存在。椭圆曲线难题K=kG，其中K,G为Ep（a,b）上的点，k为小于n的整数，n是点G的阶，给定k和G，计算K容易，但是给定K和G，求k就很难了！因此，设K为公钥，k为私钥，G为基点。加密过程A选定一条椭圆曲线Ep（a,b），并取曲线上一点作为基点GA选择一个私钥k，并生成公钥K=kGA将Ep（a,b）和k，G发送给BB收到后将明文编码到Ep（a,b）上一点M，并产生一个随机数rB计算点C1=M+rK，C2=rGB将C1，C2传给AA计算C1-kC2=M+rkG-krG=MA对M解码得到明文攻击者只能得到Ep（a,b），G，K，C1，C2，没有k就无法得到M。签名验签流程A选定一条椭圆曲线Ep（a，b），并取曲线上一点作为基点GA选择一个私钥k，并生成公钥K=kGA产生一个随机数r，计算R(x,y)=rGA计算Hash=SHA(M)，M‘=M(modp)A计算S=（Hash+M'k）/r(modp)B获得S和M'，Ep(a,b)，K，R(x,y)B计算Hash=SHA(M)，M'=M(modp)B计算R'=（Hash*G+M'*K）/S=(Hash*G+M'*kG)*r/(Hash+M'k)=rG=R（x,y），若R'=R，则验签成功。以上加解密和签名验签流程只是一个例子，具体应用时可以利用K=kG这一特性变幻出多种加解密方式。好了ECC加密算法的介绍就到这里了。（二）羽毛币应用ECC算法是基于有限域的椭圆曲线上的数学算法。关于ECC算法基本原理的介绍，请参考《ECC加密算法入门介绍》（），本文重点介绍Bitcoin系统中采用的公钥密码学方案和签名算法的实现细节。一、公钥(pubkey)、私钥(privkey)是什么公开密钥加密（public-keycryptography，也称为非对称(密钥)加密），是指存在一对数学算法相关的密钥，使用其中一个密钥加密后所得的信息，只能用另一个密钥才能解密。如果其中一个公开后并不会危害到另外一个的秘密性质，则称公开的密钥为公钥，不公开的密钥为私钥。公钥的主要作用：加密；验证签名。私钥的主要作用：签名；解密。特性：通过私钥可以计算出公钥，反之则不行。公钥加密：公钥加密的内容可以用私钥来解密——只有私钥持有者才能解密。私钥签名：私钥签名的内容可以用公钥验证。公钥能验证的签名均可视为私钥持有人所签署。以上特性通过数学算法来保证。公钥密码学的实现方案有很多种，常见的有RSA、ElGamal、迪菲－赫尔曼密钥交换协议中的公钥加密算法、椭圆曲线加密算法（ECC）。网银系统中主要使用的是RSA方案。比特币系统则使用的是ECC方案，在核心实现中并不使用加密，只使用了签名算法来确保交易的真实性和所有权的认证。二、椭圆曲线加密算法(ECC)简介ECC方案通常包含有三方面内容，数字签名方案、加密和密钥传输方案、以及密钥协商方案。本文只涉及到比特币系统所使用的数字签名方案。（一）有限域(FiniteField)：(最近有一些关于量子攻击的讨论中涉及到这一概念，有一定数学基础的和毫无数学基础的可以跳过这一小节）域(Field)的特性是集合F中的所有元素经过定义后的加法和乘法运算，所得结果仍包含于F（在加法和乘法上封闭）。无限域的元素个数无限，比如有理数域、实数域。有限域的元素个数有限，这就出现一个问题，假设F为从0至9的整数集合，那么5，6都属于F，但常规的加法定义5+6=11，11不属于F。因而，有限域需要定义加法和乘法，使其满足对加法和乘法的封闭。目前已发现，当且仅当元素个数q为质数或某个质素的n次幂时，必有一个元素个数为q的有限域存在。另外，对于每一个符合这一条件的q值，都恰有一个有限域。含有q个元素的有限域记作：Fq。ECC方案中只使用了两类有限域：一种称为质数有限域Fp，其中q=p,p为一个质数；另一种称为基于特征值2的有限域F2^m，其中q=2^m,m1。比特币系统使用的是第一种。Fp是一个{0,1…,p-1}的整数集合，有限域Fp中定义了加法：a+b≡r(modp)乘法：ab≡s(modp).（二）基于有限域Fp的椭圆曲线域E(Fp)：椭圆曲线：y^2≡x^3+ax+b(modp)当：a,b∈Fp且满足4a^3+27b^2≠0(modp).，x,y∈Fp时，这条曲线上的点的集合P=(x,y)就构成了一个基于有限域Fp的椭圆曲线域E(Fp)，元素个数记作#E(Fp)。问：这和比特币系统有什么关系吗？答：公钥即为该曲线上的某个点Q=(x,y)的二进制输出格式。公钥可以压缩，是因为y可以根据x通过曲线函数计算出来。（三）椭圆曲线域E（Fp)的描述参数：E:y^2≡x^3+ax+b(modp)为描述特定的椭圆曲线域，需明确六个参数：T=(p,a,b,G,n,h)p:代表有限域Fp的那个质数a,b：椭圆方程的参数G:椭圆曲线上的一个基点G=(xG,yG)n：G在Fp中规定的序号，一个质数。h：余因数（cofactor），控制选取点的密度。h=#E(Fp)/n。比特币系统选用的secp256k1中，参数为p=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F=2^256−2^32−2^9−2^8−2^7−2^6−2^4−1a=0，b=7G=0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141h=01问：n和比特币系统有什么关系？答：比特币系统规定私钥的取值范围最大不能超过n。（四）公钥和私钥：随机从[1,n-1]中选取一个数d,计算Q=dG。其中，d就是私钥，而Q即为公钥。这一算式看起来很简单，但这怎样保证由Q不能算出d呢？有限域中的加法和乘法是有特殊规定的。基于Fp的椭圆曲线点的集合域中，加法运算是：不同的点相加：(x1,y1)∈E(Fp)，(x2,y2)∈E(Fp)，x1≠x2(x1,y1)+(x2,y2)=(x3,y3)，其中，x3≡λ^2−x1−x2(modp),y3≡λ(x1−x3)−y1(modp),而λ≡（y2−y1）/（x2−x1）(modp).相同点叠加：(x1,y1)∈E(Fp),y1≠0.(x1,y1)+(x1,y1)=(x3,y3),其中，x3≡λ^2−2×1(modp),y3≡λ(x1−x3)−y1(modp),andλ≡(3×1^2+a)/2y1(modp).dG是一个标量乘法，可以转化为加法运算，如果有爱好者想由公钥逆推出私钥，可以根据这些公式来尝试一下（笔者本人已经放弃了这种努力）。三、椭圆曲线数字签名算法(ECDSA)：用户的密钥对:（d,Q）；(d为私钥，Q为公钥)待签名的信息：M；签名：Signature(M)=(r,s)签名过程：1、根据ECC算法随机生成一个密钥对(k,R),R=(xR,yR)2、令r=xRmodn，如果r=0，则返回步骤13、计算H=Hash(M)4、按照数据类型转换规则，将H转化为一个bigendian的整数e5、s=k^-1(e+rd)modn，若s=0,则返回步骤16、输出的S=(r,s)即为签名。验证过程：1、计算H=Hash(M)2、按照数据类型转换规则，将H转化为一个bigendian的整数e3、计算u1=es^-1modn,u2=rs^-1modn4、计算R=(xR,yR)=u1G+u2Q,如果R=零点，则验证该签名无效5、令v=xRmodn6、若v==r，则签名有效，若v≠r,则签名无效。ECC加密算法入门介绍前言同RSA（RonRivest，AdiShamir，LenAdleman三位天才的名字）一样，ECC（EllipticCurvesCryptography，椭圆曲线密码编码学）也属于公开密钥算法。目前，国内详细介绍ECC的公开文献并不多（反正我没有找到）。有一些简介，也是泛泛而谈，看完后依然理解不了ECC的实质（可能我理解力太差）。前些天我从国外网站找到些材料，看完后对ECC似乎懵懂了。于是我想把我对ECC的认识整理一下，与大家分享。当然ECC博大精深，我的认识还很肤浅，文章中错误一定不少，欢迎各路高手批评指正，小弟我洗耳恭听，并及时改正。文章将采用连载的方式，我写好一点就贴出来一点。本文主要侧重理论，代码实现暂不涉及。这就要求你要有一点数学功底。最好你能理解RSA算法，对公开密钥算法有一个了解。《近世代数基础》《初等数论》之类的书，最好您先翻一下，这对您理解本文是有帮助的。别怕，我尽量会把语言通俗些，希望本文能成为学习ECC的敲门砖。一、从平行线谈起。平行线，永不相交。没有人怀疑把：）不过到了近代这个结论遭到了质疑。平行线会不会在很远很远的地方相交了？事实上没有人见到过。所以“平行线，永不相交”只是假设（大家想想初中学习的平行公理，是没有证明的）。既然可以假设平行线永不相交，也可以假设平行线在很远很远的地方相交了。即平行线相交于无穷远点P∞（请大家闭上眼睛，想象一下那个无穷远点P∞，P∞是不是很虚幻，其实与其说数学锻炼人的抽象能力，还不如说是锻炼人的想象