一. 椭圆曲线加密算法
简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全,RSA加密算法也是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用。据研究,160位ECC加密安全性相当于1024位RSA加密,210位ECC加密安全性相当于2048位RSA加密(有待考证)
二. 什么是椭圆曲线
Wolfram MathWorld给出了个准确非凡的定义椭圆曲线。椭圆曲线可以暂时简单的理解为描述了特定点的集合的公式:
以下是a和b参数的变化对应的图形的示例:
b=1,a取值范围从2到-3
特殊曲线:左边参数是a=b=0,右边参数是a=-3,b=2.这两条都不是符合标准的曲线。
a和b的取值变化决定了曲线在坐标系上的不同形状。从图中可以看到,椭圆曲线是相对X轴对称。
另外定义一个无穷大的点(也可以成为理想点),以符号0,也就是零表示该点。
三. 阿贝尔群
椭圆曲线也可以有运算,像实数的加减乘除一样,这就需要使用到加群。19世纪挪威的尼尔斯·阿贝尔抽象出了加群(又叫阿贝尔群或交换群)。数学中的群是一个集合,我们为它定义了一个“加法”,并用符号+表示。假定群用 表示,则加法必须遵循以下四个特性:
封闭性:如果a和b都是 的成员,那么a+b也是 的成员;
结合律:(a + b) + c = a + (b + c);
单位元:a+0=0+a=a,0就是单位元;
逆元:对于任意值a必定存在b,使得a+b=0。
如果再增加一个条件,交换律:a + b = b + a,则称这个群为阿贝尔群,根据这个定义整数集是个阿贝尔群。
四. 椭圆的几何加法
因为椭圆曲线是阿贝尔群,所以公式P+Q+R=0 以及 P+Q=−R成立。在椭圆曲线上画出点P和点Q,连直线穿过P和Q,该直线会与椭圆曲线相较于第三个点,称之为R。根据R取得R的逆元-R,P+Q=-R。
运用几何学的方法很容易得到我们要的结果,但是我们需要再对一些更精确的解释。特别是有一些问题需要考虑:
• 如果P=0或者Q=0(0是无穷远点)呢?无法画出该直线,因为无穷远点无法体现在直角坐标系里。但是既然已经定义了无穷远点0,那么对于任意给定的P或者Q,P+0=P以及0+Q=Q都是成立的。
• 如果P=-Q呢?这种情况下该直线是与X轴是垂直的,并且不会与椭圆曲线相交于第三个点。 根据公理,P就是Q的逆元,P+Q=P+(-P)=0。
• 如果P=Q呢?这种情况下,存在无数条线穿过这个点。这里要用到极限的思维。假设线上有另外一个点Q1,让Q1不断靠近P, 随着Q1不断靠近P,最终Q1无限靠近P,产生了一条直线与椭圆曲线相切。那么可以得到 P+P=-R, 在这里R就是该直线与椭圆曲线的另外一个交点。
• 如果P≠Q,但是不存在第三个交点R呢?这种情况和上一个情况很类似。实际上,这种情况下该直线跟椭圆曲线是相切的关系。
假设P就是相切的点。在上一个情况里,有该等式P+P=-Q。而在这里变成了P+Q=-P。另一方面,如果Q是相切的点,那么P+Q=-Q。
五. 代数上的加法
要计算点的加法的话,我们必须把前面的几何学的讨论转到代数上的讨论,考虑非0,非对称的点P(x1,y1)和Q(x2,y2),R(x3,y3)为过P,Q与曲线相交点,则:
x3=k^2−x1−x2
y3=k(x1−x3)−y1
若P=Q,则k=(3x1^2+a)/2y1
若P≠Q,则k= (y2−y1)/ (x2−x1)
六. 标量乘法
同点加法,若有k个相同的点P相加,记作kP 。 P+P=2P
P+P+P=2P+P=3P
七. 有限域椭圆曲线
椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。
我们给出一个有限域Fp
1.Fp中有p(p为质数)个元素0,1,2,…, p-2,p-1
2.Fp的加法是a + b ≡ c ( m o d p )
3.Fp的乘法是a × b ≡ c ( m o d p )
4.Fp的除法是a ÷ b ≡ c ( m o d p ) , 即 a × b ^− 1 ≡ c ( m o d p ) , b^ − 1 也 是 一 个 0 到 p − 1 之 间 的 整 数 , 但 满 足 b × b ^− 1 ≡ 1 ( m o d p )
5.Fp的单位元是1,零元是 0
6.Fp域内运算满足交换律、结合律、分配律
7.椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
选择两个满足下列约束条件的小于p的非负整数a、b :
有限域椭圆曲线点的阶, 如果椭圆曲线上一点P,存在最小的正整数n使得数乘n P = O∞,则将n称为P的阶,若n不存在,则P是无限阶的.
八. 椭圆曲线加密
考虑K=kG,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(n G = O∞ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据 。
1.点G称为基点(base point)
2.k(k<n)为私有密钥(private key)
3.K为公开密钥(public key)
下面是利用椭圆曲线进行加密通信的过程(公钥加密私钥解密过程):
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(r<n)。
5、用户B计算点C 1 = M + r K和C 2 = r G。
6、用户B将C 1 、 C 2 传给用户A。
7、用户A接到信息后,计算C 1 − k C 2 ,结果就是点M。再对点M进行解码就可以得到明文。
因为C 1 − k C 2 = M + r K − k ( r G ) = M + r k G − k r G = M
九. 数字签名
数字签名是公钥密码学发展过程中最重要的概念之一,产生和使用数字签名过程的一般模型如图所示
十. 椭圆曲线数字签名算法(ECDSA)
ECDSA处理过程:
1.参与数字签名的所有通信方都使用相同的全局参数,用于定义椭圆曲线以及曲线上的基点
2.签名者首先生成一对公私钥。对于私钥,选择一个随机数或者伪随机数作为私钥,利用随机数和基点算出另一点,作为公钥
3.对消息计算Hash值,用私钥、全局参数和Hash值生成签名
4.验证者用签名者的公钥、全局参数等验证。
全局参数:
密钥生成:
每个签名者都要生成一对公私钥,假设是Bob
这里是定义在
上的椭圆曲线,椭圆曲线上的乘法运算就是多个点的累加运算,最后的结果还是椭圆曲线上的点,有了公钥之后,Bob对消息m生成320字节的数字签名:
第2步确保最后算出的公钥(椭圆曲线上的点)是落在曲线上。第5步,如果为O点也是不符合的,所以也要重新生成。
Alice在获得Bob的公钥和全局参数后,即可校验签名
该过程有效性证明如下,如果Alice收到的消息确实是Bob签署的,那么
s = (e+dr)k^-1 mod n
于是 k= (e+dr)s^-1 mod n
= (e s^-1 + dr s^-1) mod n
= (we +wdr) mod n
=(u1 + u2d) mod n
现在考虑u1G + u2Q = u1G + u2dG = (u1 + u2d)G = KG
在验证过程的步骤6中,有v = x1 mod n , 这里解点 X =(x1,y1) = u1G + u2Q。因为
R = x mod n 且x 是解点kG的x 坐标,又因为 我们已知 u1G + u2Q = KG,所以可得到 v = r。