基于ECC椭圆曲线的应用

2019/03/18 密码学

ECDSA(Elliptic Curve Digital Signature Algorithm),椭圆曲线数字签名算法,是一种广泛应用于数字签名的算法,例如比特币使用的数字签名算法便是ECDSA。ECDSA是基于椭圆曲线公钥/私钥对的数字签名,下面主要介绍椭圆曲线以及ECDSA的证明。

ECC椭圆曲线加密算法

椭圆曲线加密算法是一种公钥加密技术,它是由韦尔斯特拉斯Weierstrass方程所确定的平面曲线:

\[y^{2}=x^{3}+ax+b\]

椭圆曲线有几个重要的性质:

  1. 椭圆曲线关于X轴对称。
  2. 一条与椭圆曲线相交的直线有3个交点。
  3. 在2中,当直线与椭圆曲线相切时,认为切点是两个点的重合,第3个交点在无穷远处,称为基点。

椭圆曲线上的运算定义,其中A、B、C为椭圆曲线上的点,n是整数。

1. A+B+C = O
2. A+B = -C
3. n*A = A+A+...+A

第一条式子表明,同一条直线与椭圆曲线的三个交点A、B、C相加的结果是O基点。第二条式子表明,两个点的加法相当于是这两个点所连接的直线与椭圆曲线相交的第三个交点C对X轴的对称点。第三条式子是椭圆曲线点的乘法展开式。加法运算如下图:

更多的椭圆曲线:

在计算机的应用中,一般不会直接使用椭圆曲线,因为上述公式是连续的,计算机中不容易存储浮点数。所以实际应用中会对椭圆曲线进行离散化,通过对大素数p取模:

\[y^{2}=x^{3}+ax+b\mod p\]

类似于RSA算法中的大数分解难题,对于椭圆曲线中存在的数学难题是保证密码学上的安全性。考虑下面的情况:

\[Q=kP\] \[Q,P\in E_{p}(a,b),k<p\]

已知k和P求出Q是容易的(Q=P+P+…P,k个P相加),而已知Q和P求出k是困难的。因此可以将Q作为公钥发布出去,k作为私钥,通过公钥破解出私钥是困难的。

ECDHE椭圆曲线密钥磋商

基于模p有限域下的椭圆曲线实现DH密钥磋商:

  1. Alice和Bob共享关于椭圆曲线的参数\((p,a,b,G,n)\)。
  2. Alice选择小于n的整数\(n_{A}\),计算\(P_{A}=n_{A}\times G\),发送给Bob。
  3. 同样的,Bob选择小于n的整数\(n_{B}\),计算\(P_{B}=n_{B}\times G\),发送给Alice。
  4. Alice计算出共同密钥\(K_{A}=n_{A}\times P_{B}\),Bob计算出共同密钥\(K_{B}=n_{B}\times P_{B}\),容易证明\(K_{A}=K_{B}\),因为有\(K_{A}=n_{A}\times P_{B}=n_{A}\times (n_{B}\times G)=n_{B}\times (n_{A}\times G)= K_{B}\)

此时Alice和Bob得到共同密钥,而敌手获取的\(P_{A}\)和\(P_{B}\)无法计算出该密钥。

ECDSA椭圆曲线数字签名算法

对于模\(p\)有限域下的椭圆曲线\(E\),选择小于\(n\)的整数\(d\),生成下列参数:

\[Q=dG\] \[{E,G,d,p,Q}\]

生成签名过程,其中\(H(m)\)是对消息\(m\)进行哈希的结果。

  1. 取随机数\(k\),计算\(kG=(x_{1}, y_{1})\)
  2. 计算\(r=x_{1}\mod p\)
  3. 计算\(s=k^{-1}*(H(m)+dr)\mod p\)
  4. 签名结果为\((r,s)\)

验证签名的过程:

  1. 计算\(w=s^{-1}\mod p\)
  2. 计算\(u_{1}=wH(m)\mod p\)
  3. 计算\(u_{2}=rw\mod p\)
  4. 计算\(u_{1}G+u_{2}Q=(x_{0},y_{0})\)
  5. 令\(v=x_{0}\mod p\),如果\(v=r\),则验证签名通过。

(补充)DSA数字签名算法

生成签名过程:

  1. 取随机数\(k\),满足\(0<k<q\)。
  2. 计算\(r=(g^{k}\mod p)\mod q\)。
  3. 计算\(s=(k^{-1}(H(m)+xr))\mod q\)。
  4. 签名结果为\((r,s)\)。

验证签名的过程:

  1. 计算\(w=s^{-1}\mod q\)。
  2. 计算\(u=wH(m)\mod q\)。
  3. 计算\(v=rw\mod q\)。
  4. 判断\(((g^{u}y^{v})\mod p)\mod q=r\)是否成立,如果成立,则验证签名通过。

ECDSA的证明

已知

\[w=s^{-1}\mod p\]

\[ws\mod p = 1\]

因为

\[s=k^{-1}(H(m)+dr)\mod p\]

得到

\[wk^{-1}(H(m)+dr)\mod p = 1\] \[k^{-1}(wH(m)+wdr)\mod p = 1\]

其中

\[(wH(m)+wdr)\mod p=u_{1}+u_{2}d\mod p\]

因此

\[k=u_{1}+u_{2}d\mod p\] \[u_{1}G+u_{2}Q=u_{1}G+u_{2}dG=(u_{1}+u_{2}d)G=kG\]

得到

\[v=r\]

OpenSSL中使用ECDSA

OpenSSL中提供ECDSA的调用接口,分别是:

ECDSA_sign(int type, const unsigned char *dgst, int dgstlen, unsigned char *sig, unsigned int *siglen, EC_KEY *eckey)
ECDSA_verify(int type, const unsigned char *dgst, int dgstlen,  const unsigned char *sig, int siglen, EC_KEY *eckey)

补充

本文中使用MathJax引擎来渲染基于LaTeX的数学公式,方法是在MD文件中插入下列语句:

<script type="text/javascript" async
  src="https://lib.baomitu.com/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML">
</script>

Search

    Table of Contents