Perface
椭圆曲线加密算法,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全,RSA加密算法也是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用。
据研究,160位ECC加密安全性相当于1024位RSA加密,210位ECC加密安全性相当于2048位RSA加密(有待考证)。
比特币Bitcoin使用了 secp256k1这条特殊的椭圆曲线:
流程
椭圆加密算法(Elliptic curve cryptography,简称Ecc)是一种公钥加密体系,算法的基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。以下是Ecc算法的基本流程:
- 随机生成一个整数r,该整数在1到n-1之间,n是一个素数。
- 计算椭圆曲线点C1 = [r]G,其中G是基点,得到(x1,y1)。
- 计算椭圆曲线点C2 = [r],得到(x2,y2)。
- 将C1和C2的数据类型转换为比特串。
- 计算 C3 = M*x2(mod p),其中M是要加密的明文信息。
- 输出密文C = (x1,y1,C3)。
- 在解密过程中,从密文C中取出C1(x1,y1),使用私钥k计算点C4(x2,y2)=kC1=k(x1,y1),然后计算明文P = C3,解密完成。
以上是Ecc算法的基本流程,具体实现过程可能会因应用场景的不同而有所差异。
一、阿贝尔群
椭圆曲线也可以有运算,像实数的加减乘除一样,这就需要使用到加群。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,则称这个群为阿贝尔群,根据这个定义整数集是个阿贝尔群。
二、椭圆曲线的加法
过曲线上的两点A、B画一条直线,找到直线与椭圆曲线的交点,交点关于x轴对称位置的点,定义为A+B,即为加法。如下图所示:A + B = C
三、椭圆曲线的二倍运算
上述方法无法解释A + A,即两点重合的情况,因此在这种情况下,将椭圆曲线在A点的切线,与椭圆曲线的交点,交点关于x轴对称位置的点,定义为A + A,即2A,即为二倍运算。
四、同余运算
同余就是有相同的余数,两个整数 a、 b,若它们除以正整数 m所得的余数相等,则称 a, b对于模m同余。
五、有限域
椭圆曲线是连续的,并不适合用于加密;所以必须把椭圆曲线变成离散的点,要把椭圆曲线定义在有限域上。
而椭圆曲线密码所使用的椭圆曲线是定义在有限域内,有限域最常见的例子是有限域GF§,指给定某质数p,由0,1,2…p-1共p个元素组成的整数集合中加法、二倍运算。例如GF(233)就是
六、乘法逆元
在模7乘法中:
- 1的逆元为1 (1*1)%7=1
- 2的逆元为4 (2*4)%7=1
- 3的逆元为5 (3*5)%7=1
- 4的逆元为2 (4*2)%7=1
- 5的逆元为3 (5*3)%7=1
- 6的逆元为6 (6*6)%7=1
七、数学解释
并不是所有的椭圆曲线都适合加密
y^2 = x^3 + ax + b
这个类可以用来加密的椭圆曲线,也是最为简单的一类。
针对曲线Ep(a,b)表示为
P为质数,该曲线关于x轴对称。选择两个满足下列条件的小于p(p为素数)的非负整数a、b,要求满足以下条件
- 1、有限域的负元
- 2、有限域的加法P+Q
- 3、斜率计算(P=Q即要计算P点切线,需要求导)
八、椭圆曲线加解密算法原理
设私钥、公钥分别为d、Q,即Q = dG,其中G为基点,椭圆曲线上的已知G和dG,求d是非常困难的,也就是说已知公钥和基点,想要算出私钥是非常困难的。
- 公钥加密:选择随机数r,将消息M生成密文C,该密文是一个点对,C = {rG, M+rQ},其中Q为公钥。
- 私钥解密:M + rQ - d(rG) = M + r(dG) - d(rG) = M,其中d、Q分别为私钥、公钥。
九、椭圆曲线签名算法原理
椭圆曲线签名算法(ECDSA)。设私钥、公钥分别为d、Q,即Q = dG,其中G为基点。
私钥签名:
- 选择随机数r,计算点rG(x, y)。
- 根据随机数r、消息M的哈希h、私钥d,计算s = (h + dx)/r。
- 将消息M、和签名{rG, s}发给接收方。
公钥验证签名:
- 接收方收到消息M、以及签名{rG=(x,y), s}。
- 根据消息求哈希h。
- 使用发送方公钥Q计算:hG/s + xQ/s,并与rG比较,如相等即验签成功。
原理:hG/s + xQ/s = hG/s + x(dG)/s = (h+xd)G/s = r(h+xd)G / (h+dx) = rG
10、签名过程
假设要签名的消息是一个字符串:“Hello World!”。DSA签名的第一个步骤是对待签名的消息生成一个消息摘要,不同的签名算法使用不同的消息摘要算法,而ECDSA256使用SHA256生成256比特的摘要。
摘要生成结束后,应用签名算法对摘要进行签名:
- 产生一个随机数k
- 利用随机数k,计算出两个大数r和s。将r和s拼在一起就构成了对消息摘要的签名。
这里需要注意的是,因为随机数k的存在,对于同一条消息,使用同一个算法,产生的签名是不一样的。从函数的角度来理解,签名函数对同样的输入会产生不同的输出。因为函数内部会将随机值混入签名的过程。
11、验证过程
关于验证过程,这里不讨论它的算法细节。从宏观上看,消息的接收方从签名中分离出r和s,然后利用公开的密钥信息和s计算出r。如果计算出的r和接收到的r值相同,则表示验证成功,否则,表示验证失败。