一、概述

椭圆曲线加密算法ECC与RSA算法一样,都属于公钥加密(或非对称加密)算法。它能用相对RSA“较短的密钥长度(如160位,RSA通常为1024位)”、“更快的计算速度”,提供与RSA难度相当或者更高等级的安全。比特币正是采用ECC算法作为它的公钥加密技术。

椭圆曲线加密算法ECC的加密原理,是基于《近世代数基础》中“射影平面”坐标系下的椭圆曲线的加、乘、除运算。简单来说就是:k作为私钥,G是椭圆曲线上的点(称之为基点),K作为公钥,其中K = kG。

密码难以破解是因为根据私钥k和基点G计算K很容易,反之根据基点G和公钥K计算私钥k则变得很困难。

二、数学原理

(1)射影平面坐标系与无穷远点

中学时代我们知道,平面上两条平行的线永不相交。但这只是一个公理(人们理性地不证自明的事实),并没有严密的逻辑证明。既然我们可以认为平行线永不相交,我们同样也可以认为平行线相交于无穷远点(想象一下)。为了表示无穷远点,数学符号用O∞表示,数学家们发明了射影响平面坐标系:对笛卡尔直角坐标系的扩展,增加了无穷远点的概念。将传统二维平面坐标系下的坐标(x, y)通过以下方式转化为射影响平面坐标:

x = X/Z,y = Y/Z,其中Z ≠ 0,则将(X:Y:Z)称为传统平面坐标(x, y)对应的射影平面坐标。

我们知道传统平台坐标下的直线可以用以下方式表示:ax + by + c = 0,将(x = X/Z,y = Y/Z,其中Z ≠ 0)代入后得到直线在射影平面的方式为:aX + bY + cZ = 0。 那么在这个射影平面上,无穷远点怎么表示呢?根据无穷远点的定义,假设两条平行线为:

aX + bY + c1Z = 0 和 aX + bY + c2Z = 0,c1≠ c2根据交点的定义,将这两个式子联立,得到:c1Z = c2Z = -(aX + bY),又因为c1≠ c2,所以(aX + bY) = Z = 0,无穷远点的坐标就是这种形式:(X:Y:0)。

Z = 0表示无穷远直线:所有无穷远点形成的直线(想象一下)。

(2)椭圆曲线

椭圆曲线是在射影平面坐标系下的曲线方程。之所以叫它是椭圆曲线方程,不是因为它形状像椭圆,而是它的方程的结构类似于计算椭圆曲线周长的方程。

椭圆曲线方程的定义:

一条椭圆曲线是在射影平面上满足方程

Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3   —————————(1)

的所有点的集合,且曲线上每个点都是非奇异(或光滑)的点。

所谓“非奇异”或“光滑”的,在数学中是指曲线上任意一点的偏导数Fx(x,y,z),Fy(x,y,z),Fz(x,y,z)不能同时为0。如果你没有学过高等数学,可以这样理解这个词,即满足方程的任意一点都存在切线。

方程(1)是Weierstrass方程(维尔斯特拉斯,Karl Theodor Wilhelm Weierstrass,1815-1897),是一个齐次方程。

为了便于计算,我们需要将射影平面坐标系上的椭圆曲线方程转化为笛卡尔直角坐标系下的曲线方程,将(x = X/Z,y = Y/Z,其中Z ≠ 0)代入方程(1)后得到:

y2+a1xy+a3y = x3+a2x2+a4x+a—————————(2)

笛卡尔坐标系下满足方程(2)的光滑曲线加上一个无穷远点O∞,组成了射影平面坐标系下的椭圆曲线方程。

再进一步,(0:1:0)代入方程(1)等式成立,可知它是该方程代表的椭圆曲线上的一个无穷远点。因此,可以用方程笛卡尔直角坐标系下的方程(2)和它上面的一个无穷远点(0:1:0)来代表射影平面坐标系上的椭圆曲线方程(1)。

(3)加法法则

运算法则:任意取椭圆曲线上两点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;

三、密码学中的椭圆曲线

前面学到的椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点。因此,我们要把椭圆曲线定义在有限域上(顾名思义,有限域是一种只有由有限个元素组成的域)。

域的概念是从我们的有理数,实数的运算中抽象出来的,严格的定义请参考近世代数方面的数。简单的说,域中的元素同有理数一样,有自己得加法、乘法、除法、单位元(1),零元(0),并满足交换率、分配率。

(1)定义

在有限域Fp中定义一个椭圆曲线,常用y2=x3+ax+b

  1. Fp中只有p个元素,p为素数
  2. Fp中,a+b≡c (mod p),a×b≡c (mod p),a/b≡c (mod p)
  3. 4a3+27b2≠0 (mod p) a,b是小于p的非负整数。 (这个条件是为了避免奇异点)。△ = 4a3+27b2是方程x3+ax+b= 0 的判别式。
  4. x,y属于0到p-1间的整数,曲线标记为Ep(a,b)

阶:椭圆曲线上一点P,存在正整数n,使得nP=O∞,则n为P的阶,若n不存在,则P是无限阶的,有限域上定义的椭圆曲线上所有点的阶都存在。

(2)椭圆曲线难题

K=kG,其中K,G为Ep(a,b)上的点,k为小于n的整数,n是点G的阶,给定k和G,计算K容易,但是给定K和G,求k就很难了!

因此,设K为公钥,k为私钥,G为基点。

(3)加密过程

  1. A选定一条椭圆曲线Ep(a,b),并取曲线上一点作为基点G
  2. A选择一个私钥k,并生成公钥K=kG
  3. A将Ep(a,b)和k,G发送给B
  4. B收到后将明文编码到Ep(a,b)上一点M,并产生一个随机数r
  5. B计算点C1=M+rK,C2=rG
  6. B将C1,C2传给A
  7. A计算C1-kC2=M+rkG-krG=M
  8. A对M解码得到明文

攻击者只能得到Ep(a,b),G,K,C1,C2,没有k就无法得到M。

(4)签名验签流程

  1. A选定一条椭圆曲线Ep(a,b),并取曲线上一点作为基点G
  2. A选择一个私钥k,并生成公钥K=kG
  3. A产生一个随机数r,计算R(x,y)=rG
  4. A计算Hash=SHA(M),M‘=M(modp)
  5. A计算S=(Hash+M’k)/r(modp)
  6. B获得S和M’,Ep(a,b),K,R(x,y)
  7. B计算Hash=SHA(M),M’=M(modp)
  8. B计算R’=(Hash*G+M’*K)/S=(Hash*G+M’*kG)*r/(Hash+M’k)=rG=R(x,y),若R’=R,则验签成功。

以上加解密和签名验签流程只是一个例子,具体应用时可以利用K=kG这一特性变幻出多种加解密方式。

参考文献

ECC加密算法 作者  :ZMWorm[CCG]

ECC算法介绍

刘启林的知乎专栏——椭圆曲线的密码体制 作者:刘启林  https://zhuanlan.zhihu.com/p/42629724

区块链背后的信息安全(3)椭圆曲线加解密及签名算法的技术原理及其Go语言实现

ECC椭圆曲线详解(有具体实例)