椭圆曲线加密算法

椭圆曲线加密算法椭圆曲线密码学（英语：Ellipticcurvecryptography，缩写为ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。椭圆曲线在密码学中的使用是在1985年由NealKoblitz和VictorMiller分别独立提出的。ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长1.椭圆曲线在数学上，椭圆曲线（英语：Ellipticcurve，缩写为EC）为一代数曲线，被下列式子所定义𝑦2=𝑥3+𝑎𝑥+𝑏其是无奇点的；亦即，其图形没有尖点或自相交。满足此条件的ab满足：4𝑎3+27𝑏2≠0图1在基础上需要定义一个无穷远的点，将此点作为零点：此时椭圆曲线定义为：{(𝑥,𝑦)∈ℝ2|𝑦2=𝑥3+𝑎𝑥+𝑏,4𝑎3+27𝑏2≠0}∪{0}在椭圆曲线中的群的运算律：1.所有的点都在椭圆曲线上2.0点作为群上的单元点即𝑃+0=𝑃3.P点关于X轴的对称点为P点的逆即𝑃+(−P)=04.对于位于同一条直线上的三个点P,Q,R.则有P+Q+R=0图2P+Q+R=0（无限远点PQR三个点的位置是任意的，他们满足加法的结合律，因为这个群是一个阿贝尔群。2.椭圆曲线加法当P和Q不相等时(𝑥𝑃≠𝑥𝑄)由于是在阿贝尔群上可以将P+Q+R=0改写为P+Q=−R所以在椭圆曲线上的加法定义为PQ两点加法为P,Q两点连线与曲线的交点R的关于X轴对称点−R图2-3P+Q=-RPQ两点的直线的斜率为：𝑚=𝑦𝑃−𝑦𝑄𝑥𝑃−𝑥𝑄这条线与曲线的交点为：𝑅=(𝑥𝑅,𝑦𝑅)𝑥𝑅=𝑚2−𝑥𝑃−𝑥𝑄𝑦𝑅=𝑦𝑃+𝑚(𝑥𝑅−𝑥𝑃)因此(𝑥𝑃,𝑦𝑃)+(𝑥𝑄,𝑦𝑄)=(𝑥𝑅,−𝑦𝑅)如果在图上表示即为上述的𝑃+𝑄=−𝑅当P和Q不相等时(𝑥𝑃=𝑥𝑄)(𝑦𝑃=−𝑦𝑞)因为p+(−p)=0图3PQ两点相同时直线的斜率为𝑚=3𝑥𝑃2+𝑎2𝑦𝑃经计算的𝑚=3𝑥𝑃2+𝑎2𝑦𝑃𝑥𝑅=𝑚2−𝑥𝑃−𝑥𝑄𝑦𝑅=𝑦𝑃+𝑚(𝑥𝑅−𝑥𝑃)图43.椭圆曲线标量乘法通过上面的加法运算我们可以得出其标量乘法运算可以得出𝑛𝑃=𝑃+𝑃+⋯+𝑃⏟𝑛times从上式可以看出当我们计算nP的时候需要做n次加法，如果n有k位那么的计算时间复杂度变为O(2𝑘),这显然不是快捷的方式。其中一种加快计算的方式是将这些加法运算的次数减少，我们将n写成2进制形式，然后我们按每位计算，每次复用上一次的结果如当n=151时，其二进制位100101112所以151=1⋅27+0⋅26+0⋅25+1⋅24+0⋅23+1⋅22+1⋅21+1⋅20=27+24+22+21+20所以如果运用在上面的标量乘法时，其运算可以简化为：151⋅𝑃=27𝑃+24𝑃+22𝑃+21𝑃+20𝑃4.离散空间椭圆曲线我们将曲线上的点全部局限于𝔽𝑝上此时离散形式的椭圆曲线变为：{(𝑥,𝑦)∈(𝔽𝑝)2|𝑦2≡𝑥3+𝑎𝑥+𝑏(mod𝑝),4𝑎3+27𝑏2≢0(mod𝑝)}∪{0}0仍然为无穷远点，a,b为整数图5𝑦2≡𝑥3−7𝑥+10(mod𝑝)p=19,97,127,487的图示在离散椭圆图上的加法和曲线上的加法的定义类似，在离散的椭圆曲线中，直线的方程变为𝑎𝑥+𝑏𝑦+𝑐≡0(mod𝑝)，点P，Q两点的加法的操作也是基于这个定义上下图展示了𝑦2≡𝑥3−𝑥+3(mod127)曲线上𝑃=(16,20)和𝑄=(41,120)两点之间的加法直线𝑦≡4𝑥+83(mod127)在此空间上是一组距离相等的平行线图65.离散椭圆曲线代数加法对照曲线上的加法，离散空间椭圆曲线加法公式可以写作𝑥𝑅=(𝑚2−𝑥𝑃−𝑥𝑄)𝑚𝑜𝑑𝑝𝑦𝑅=[𝑦𝑃+𝑚(𝑥𝑅−𝑥𝑃)]𝑚𝑜𝑑𝑝=[𝑦𝑄+𝑚(𝑥𝑅−𝑥𝑄)]𝑚𝑜𝑑𝑝如果𝑃≠𝑄，此时的m的值的形式为𝑚=(𝑦𝑃−𝑦𝑄)(𝑥𝑃−𝑥𝑄)−1𝑚𝑜𝑑𝑝如果P=Q时：𝑚=(3𝑥𝑃2+𝑎)(2𝑦𝑃)−1𝑚𝑜𝑑𝑝在离散型的椭圆空间里面我们知道点的数目是有限的，而这些点的个数我们称为椭圆曲线群的阶数同样的在离散空间，对于曲线上的点同样满足标量加法的法则𝑛𝑃=𝑃+𝑃+⋯+𝑃⏟𝑛times但是在离散空间椭圆曲线加法会有一个有趣的现象，对一个点进行有限次的加法，存在一个是n使得nP=P例如在曲线𝑦2≡𝑥3+2𝑥+3(mod97)的一点P=(3,6),计算其的标量乘法，计算结果如下：图7可以看出P=(3,6)经过6次加法后又回到本身，也即是5P=0所以对于P的加法可以写作kP=(kmod5)P可以证明的是一个点的加法所构成的子集是一个循环的子集首先一个点的加法所得到的点一定是有限的，因为加法所获得的点全部都在父集上的，父集的大小是有限的，所以经过有限次的加法后所获得的结果必定会重复，那么结果就会重复下去。只需证明第一个重复的值是P即可。假设第一个重复的值不是P，而是kP,那么后面的结果也必然是kP的倍数，假设重复的次数为n,如果gcd(n,k)不为1，那么存在使得kmmodn=0即kmP=0即(km+1)P=P与假设矛盾如果gcd(n,k)=1那么kmP=(mmodn)𝑘𝑃那么存在一个数使得mkmodn=1即mkP=(mkmodn)P=P与假设矛盾。在一个循环子集中将P称之为生成点或者基点，其子集的点的大小n称之为子集的阶即nP=0由拉格朗日定理可知子群的阶n是全集阶N的因子例如𝑦2=𝑥3−𝑥+3在𝔽37上N=42它的子集大小只能n=1,2,3,6,7,14,21,42为基点P=(2,3),因为𝑃≠0，2𝑃≠0…7𝑃=0所以构成的子集的大小为7如果在𝔽29上，其阶为N=37所以其子集大小只能为n=1或者37对于ECC（椭圆加密算法），需要找到一个具有高阶子集，一般情况下选择一个椭圆曲线并计算他的阶，然后找到一个数字大的因子n作为子集的阶，如果这个子集的基点为P则nP=Np=0给定n和P，那么需要计算n次计算出Q=nP,如果只给出P,Q如何计算出n这就是所谓的对数问题。这个问题也就是椭圆曲线的离散对数问题而求解这个对数问题是非常困难的，而正是由于这种困难使得我们使用椭圆加密算法变得更加可靠与其他类似的加密算法相比，破解椭圆加密算法更加困难，这也意味着更少位数的秘钥k可以达到同类算法同样的安全强度6.椭圆加密算法ECDH和ECSDA椭圆加密算法是基于有限域的离散型的椭圆曲线的循环子集上，定义一个这样的子集需要以下参数，有限域的大小素数P椭圆曲线方程a和b用于生成子集的基点G子集的阶n子集的辅因子h总的来说一个椭圆加密算法基于(𝑝,𝑎,𝑏,𝐺,𝑛,ℎ)参数上(1)ECDH同其他非对称加密算法一样，需要计算私钥和公钥，在ECC中私钥是一个随机数d来自于{1,…,𝑛−1}(n是子集的阶)公钥是曲线上的一个点H=dG（G是子集的基点）如果我们知道d和G，找到公钥H是很容易的，但是如果只知道H和G找到私钥d是及其困难的，这等同有在做离散对数问题，上文有提到这个问题在现在来说还没有有效的算法，所以是很困难的。ECDH是迪夫赫尔曼算法的一个变种，它实际上是一个秘钥共识协议，ECDH协议定义了秘钥的如何产生以及如何交换秘钥。如果Alice和Bob需要交换秘钥，中间人Hack可以在两者之间监听1.Alice和Bob使用同样参数的椭圆曲线，并且随机产生各自的秘钥𝑑𝐴和𝑑𝐵,并且计算出各自的公钥𝐻𝐴=𝑑𝐴𝐺和𝐻𝐵=𝑑𝐵𝐺,2.他们彼此交换各自的公钥𝐻𝐴和𝐻𝐵,而中间人也将他们的公钥截获，但是他们都不能从这些信息中计算出他们的私钥3.Alice计算出𝑆=𝑑𝐴𝐻𝐵，Bob计算出𝑆=𝑑𝐴𝐻𝐵，明显的是他们各自计算出的结果是一致的。𝑆=𝑑𝐴𝐻𝐵=𝑑𝐴(𝑑𝐵𝐺)=𝑑𝐵(𝑑𝐴𝐺)=𝑑𝐵𝐻𝐴而中间人不能从公钥中计算出S，所以Alice和Bob共享了密码S,这也正是迪夫赫尔曼所要解决的问题。当Alice和Bob获得了共同的秘钥S，他们就可以使用对称加密算法如AES，3DES来加密他们的信息了。(2)ECSDA签名算法在比特币的交易中，一笔交易会在整个区块链网络中传播，每个节点需要验证一笔交易的有效性，通过交易中解锁脚本去验证交易中的输入是否是有效的。这其中正是使用了ECDSA算法来验证。假如Alice需要对一个信息进行签名，Bob需要使用Alice的公钥来验证这个信息。Alice和Bob都使用的是同一个参数相同的椭圆曲线函数。ECDSA作用在的是信息的hash值上的，且这个值是被截取后的使得其大小与这个曲线的子集的阶一致。将这个截取后的hash值定义为z图8算法的流程是1.Alice随机选择一个随机数k(kn),作为本次加密的临时私钥，并对需要签名的信息作hash处理得到z。计算P=kG并将𝑟=𝑥𝑃𝑚𝑜𝑑𝑛作为临时公钥，若r=0则重新选择。2.计算𝑠=𝑘−1(𝑧+𝑟𝑑𝐴)𝑚𝑜𝑑𝑛，𝑑𝐴是Alice使用的私钥，𝑘−1是k关于n的模逆，如果s为0则重新选择k再次计算。将(r,s)作为签名信息3.Bob此时有了Alice的公钥𝐻𝐴和签名信息(r,s)，首先计算𝑢1=𝑠−1𝑧𝑚𝑜𝑑𝑛𝑢2=𝑠−1𝑟𝑚𝑜𝑑𝑛4.然后在计算𝑃=𝑢1𝐺+𝑢2𝐻𝐴如果𝑟=𝑥𝑃𝑚𝑜𝑑𝑛，则可以判定这个信息是来自于Alice的（3）算法的正确性证明从验证的步骤往前回溯有𝑃=𝑢1𝐺+𝑢2𝐻𝐴=𝑢1𝐺+𝑢2𝑑𝐴𝐺=(𝑢1+𝑢2𝑑𝐴)𝐺将𝑢1和𝑢2的等式带入得到𝑃=(𝑢1+𝑢2𝑑𝐴)𝐺=(𝑠−1𝑧+𝑠−1𝑟𝑑𝐴)𝐺=𝑠−1(𝑧+𝑟𝑑𝐴)𝐺因为对于基点G来说它的阶为n,因此为了简洁，可以省去modn由模逆运算的性质可以将𝑠=𝑘−1(𝑧+𝑟𝑑𝐴)𝑚𝑜𝑑𝑛改写为𝑘=𝑠−1(𝑧+𝑟𝑑𝐴)𝑚𝑜𝑑𝑛于是有𝑃=𝑠−1(𝑧+𝑟𝑑𝐴)𝐺=𝑘𝐺可以看出此式正是通过随机数k生成点P的运算，回溯到了最开始的计算，可以验证算法的正确性（4）算法的漏洞在ConsoleHacking2010大会上，黑客披露了一个SonyPS3的关于ECSDA的一个破解方式。造成这个漏洞的原因在于PS3在ECSDA算法中未随机的选择数字k用来生成点P,从而造成私钥泄露。在此处键入公式。假设我们有两笔使用相同k值签名的信息，这两笔信息的hash为(𝑧1,𝑧2)，他们的签名信息为(𝑟1,𝑠1)和(𝑟2,𝑠2)首先他们的𝑟1=𝑟2，因为k值相同考虑(𝑠1−𝑠2)𝑚𝑜𝑑𝑛=𝑘−1(𝑧1−𝑧2)𝑚𝑜𝑑𝑛将两边同时乘以k，𝑘(𝑠1−𝑠2)𝑚𝑜𝑑𝑛=(𝑧1−𝑧2)𝑚𝑜𝑑𝑛两边同时除以(𝑠1−𝑠2)得到𝑘=(𝑧1−𝑧2)(𝑠1−𝑠2)−1𝑚𝑜𝑑𝑛上面的最后一个式子我们可以计算得到k，从这个确定的k可以计算得出私钥𝑠=𝑘−1(𝑧+𝑟𝑑𝑆)𝑚𝑜𝑑𝑛⇒𝑑𝑆=𝑟−1(𝑠𝑘−𝑧)𝑚𝑜𝑑𝑛从上述分析可以看出相同k是可以导致私钥泄露的所以随机数k在ECSDA算法中扮有重要角色，如果在比特币的交易中