椭圆曲线加密 ECDSA 原理简析
ECDSA
椭圆曲线加密算法是DSA
数字签名算法的变例之一,ECDSA
的基础是ECC
椭圆曲线密码学,而ECC
的理论基础是椭圆曲线上的点的倍积。
一、先验知识
1. 椭圆曲线点的倍积
**椭圆曲线的点倍积(pointy multiplication)**指的是椭圆曲线上的一个点沿着这条曲线不断的与自身相加,最终落在曲线另一个点上的过程。
假设起点是椭圆曲线点 P,终点是曲线上点 R,于是有下面的公式:
R=nP
通过上式,R 是计算不出来的,需要一些其他的准备,这里所选择的椭圆曲线的几何方程是固定的,为:
y2=x3+ax+b
方程中的 a 和 b 都是普通标量参数,a 和 b 的取值对于曲线形状是有影响的。如下图中的红线为(a, b) = (-7, 6)
,蓝线为(a, b) = (-6, 6)
。
仍然用上图为例,注意到红色曲线上的 P, Q, R 三点,P + Q = R,即两点相加得到的点 R 是 P, Q 两点直线延长线与椭圆曲线的交点的共轭点,就是关于 X 轴的对称点。从代数上计算:
P+Q=R
(xp,yp)+(xq,yq)=(xr,yr)
由于上面给定了椭圆曲线的代数式,可以得到:
xr=λ2−xp−xq
yr=λ(xp−xr)−yp
λ=xq−xpyq−yq
如果 P, Q 是同一点呢?lambda可以有特殊取值为:
λ=2yp3xp2+a
有了上面两个公式,就可以计算出点相加和点翻倍。
2. 椭圆曲线密码学
现在流行的几种密码学类型之一,通过非对称加密的形式,也就是区分公私钥来进行加密的相关操作。它是基于有限域上特定椭圆曲线进行操作的,最重要的操作是椭圆曲线的点倍积。
通过简单地逻辑推演,我们可以发现,对于点倍积 Q = nP 而言,在已知起点 P 和 终点 Q 的时,想要计算出 n 是几乎不可能实现的,比如上图中的红色曲线中,想要在左半边通过 P, Q 来计算出 n 是不可能完成的,因为 n 增大的过程总有办法保证 Q 在这个位置不动。
ECC
的使用场景包含数字签名,安全为随机数生成等,在应用中,椭圆曲线必须用完整的参数 (p, a, b, G, n, h) 来定义,其中
-
p
是一个很大的质数,用来表示曲线上所有点的范围
-
a, b
是椭圆曲线的系数
-
G
是该曲线上点倍积的基点,对于所有通过点倍积运算得到的点的集合来说,G
是生成器
-
n
是基点 G
的可倍积阶数,定义为能够使点倍积 nG 不存在的最小的整数 n
-
h
是一个整数常量,它跟椭圆曲线运算中得到点的集合以及 n 有关系,一般取值为 1
3. 椭圆曲线数字签名算法理论
相比于RSA
密码学中的DSA
,ECDSA
在计算数字签名时所需要的公钥长度可以大大缩短。比如,对于一项安全级别为80 bits的数字签名来说,ECDSA需要的公钥长度仅仅为安全级别的2倍,即160 bits,而同样安全级别要求下的RSA所需公钥长度至少为1024 bits;同时算法所生成的签名长度,不论是ECDSA还是RSA都大约是320 bits,这样一来,ECDSA相对于RSA在应用上的优势就很明显了。
安全级别:N bits的安全级别意味着攻击者大约要经过 2^N 的运算才能获得本次加密用的私钥,安全级别所代表的的bits越长,安全性也就越好。
二、数字签名的生成
假设Alice给Bob发送一则经过数字签名的消息,他们需要首先定义组共同接受的椭圆曲线加密参数,表示为:
(CURVE,G,n)
CURVE 是椭圆曲线的点域和几何方程,G 就是上面提到的生成器,n 就是该曲线的可倍积阶数。n 的作用是,使得 nG = 0 ,即点倍积 nG 的结果不存在,而对于小于 n 的任何一个正整数,点倍积 nG 都可以得到一个合理的处于该椭圆曲线上的点。
其次,Alice需要创建一对秘钥,私钥是 [1, n - 1] 内的一个随机数:
dA=rand(1,n−1)
公钥是私钥和基点的椭圆曲线点倍积:
QA=dA×G
ok,准备工作就绪,准备开始签署数字签名:
-
计算 e = HASH(m)
-
计算 z,是 e 的二进制形式下最左边(最高位)L_n个bits,L_n是上述椭圆曲线参数中的可倍积阶数n的二进制长度,z 可能大于 n,但是长度绝对不会比 n 长
-
从 [1, n-1] 内,随机选择一个符合加密学随机安全性的整数 k
-
计算椭圆曲线上点:
(x1,y1)=k×G
-
计算签名 r 值,如果 r == 0 ,返回步骤3重新计算
r=x1modn
-
计算签名 s 值,如果 s == 0 ,返回步骤3重新计算
s=k−1(z+rdA)modn
-
生成的数字签名就是 (r, s)
第3步中的 k 的选择,不仅要满足加密学的随机安全性要求,要像私钥一样保护起来,并且每次生成一个新的数字签名时,这个 k 必须每次更新。否则,通过上述数字签名过程中的算式相互换算,很容易从中破译出私钥。
三、数字签名的验证
对于Bob来说,收到的消息不只是数字签名文件,还有一份公钥。所以验证分为两部分,首先是验证公钥,然后是验证签名文件 (r, s)。
公钥的验证:
-
公钥的坐标应该是有效的,不会等于一个极限值空点
-
通过公钥的坐标验证它必须是处于该椭圆曲线上的点
-
曲线的可倍积数n与公钥的点倍积不存在
n×QA=O
签名文件的验证:
-
验证 r , s 都处于 [1, n-1] 范围内的整型数,否则验证失败
-
计算 e = HASH(n),这里的HASH函数要与签名时用到的一样
-
计算 z
-
计算参数 w :
w=s−1modn
-
计算两个参数 u1, u2 :
u1=zwmodn,u2=rwmodn
-
计算 (x1, y1),如果该点不是同一个曲线上的点,验证失败
(x1,y1)=u1×G+u2×QA
-
如果存在下面的恒等式,则验证通过,否则验证失败:
r≡x1modn
以上就是所有的签名以及签名验证过程。