ECDSA（椭圆曲线数字签名算法）

作者: 绿杨烟外晓寒轻_ | 来源:发表于2019-11-10 22:40 被阅读0次

ECDSA（Elliptic Curve Digital Signature Algorithm）

一、学习背景--数字签名

在现实工作和生活中，我们使用签名的方式表达对一份文件的认可，其他人可以识别出你的签名并且无法伪造你的签名。数字签名就是对显示签名的一种电子实现，它不仅可以完全达到现实签名的特点，甚至能够做的更好。
常用的数字签名算法有RSA（Rivest-Shamir-Adleman Scheme）、DSS（Digital Signature Standard）等。比特币使用ECDSA来生成账户的公私钥以及对交易和区块进行验证。

二、简单说一下数字签名的工作原理

1.Alice（密码学中常用A到Z开头的人名代替甲乙丙丁等，字母越靠后出现频率越低）生成一对密钥，一个是sk（signing key），是非公开的；另一个是vk（verification key），是公开的。
这一对密钥同时生成，并且在数学上是相互关联的，同时，根据vk无法推测出关于sk的任何信息。
2.数字签名算法接收两个输出：信息M和sk，生成一个数字签名Sm
3.验证函数接收信息M、Sm以及vk作为输入，，返回结果是yes或者no。这一步的目的是为了验证你看到的针对信息M的数字签名确实是由Alice的sk来签发的，用于确认信息与签名是否相符。
与手写签名不同，手写签名基本都是相似的，但是数字签名却受输入影响很大。对输入轻微的改变都会产生一个完全不同的数字签名。一般不会对信息直接进行数字签名，而是对信息的哈希值进行签名。由加密哈希函数的无碰撞性可知，这样和对原信息进行签名一样安全。

以md5加密算法为例

三、ECDSA算法

写在开头：为什么使用ECDSA算法？

两个优点
1.在已知公钥的情况下，无法推导出该公钥对应的私钥。
2.可以通过某些方法来证明某人拥有一个公钥所对应的私钥，而此过程不会暴露关于私钥的任何信息。

证明将在后面给出。

在数学上，任何满足以下方程的点所形成的曲线称为随机椭圆曲线： $y^2=x^3+ax+b$ 并且 $4a^3+27b^2≠0$ ，a和b可以为任意值。下面展示几个随机椭圆函数的示例：

y^2 =x^3−x+1

y^2=x^3-1
从图中可以看出，随机椭圆曲线都是关于x轴对称的。
ECDSA算法通过随机椭圆曲线方程的性质产生密钥，有很多的实现方案。其中比特币、以太坊以及其他一些的区块链项目使用的标准为secp256k1，它的公式为：曲线如下图：

secp256k1的曲线图

1.点的加法

在了解如何通过基于secp256k1椭圆曲线的ECDSA算法生成公私钥之前，我们需要了解在随机椭圆曲线里，点的加法是如何实现的。
首先定义椭圆曲线上点的加法。设椭圆曲线上有两点，A和B点，那么作过这两点的直线与该曲线相交于第三点（C点），然后关于X轴对称得到D点，则D为这两个点的和，记作D=A+BD=A+BD=A+B。很明显，D点也在该曲线上。所以椭圆曲线上两点之和也是曲线上的点。

加法图示

特例：
1.如果两点重合，则做该点的切线，与曲线相交点的对称点为和，即A+A=C
如图：

两点为同一点
2.如果两点关于X轴对称，定义A+B=0

2.点的乘法

有了加法以后，乘法实现是不过是进行多次加法运算。有了一个基准点P以后，我们可以对其进行乘法运算，最后可以得到曲线上的另外一个点。
设PPP是椭圆曲线上的一个点，那么正整数kkk乘以点PPP的结果由下面的式子定义，注意式子中的加法是上面提到的椭圆曲线上点的加法：
$1∗P=P$
$2∗P=P+P$
$3∗P=2∗P+P$
$…$
$k∗P=(k−1)∗P+P$

3.公钥和私钥的生成

点的运算满足结合律：
$n\cdot P+r\cdot P=(n+r)\cdot P$
很显然，通过累加 $k−1$ 的方式计算 $k∗P$ 是一种很笨的办法，其时间复杂度是线性的。上面我们提到过，椭圆曲线上点的加法是满足结合律的，即 $(A+B)+C=A+(B+C)$ ，扩展一下，就有

$P+P+P+P=(P+P)+(P+P)=2P+2P$

于是就有这么一种骚操作，比如计算 $16P$ ，我们可以先计算 $2P=P+P$ ；然后计算 $4P=P+P+P+P=2P+2P$ ；再计算 $8P=P+P...+P=4P+4P$ ；最后计算 $16P=8P+8P$ 。这里我们把15次加法减少到了4次。

当然，k的值不可能总是2的幂。实际上上面的操作可以推广到k为任意正整数的情况。比如计算23P，首先计算 $2P=P+P$ ，然后
$4P=2P+2P$
$8P=4P+4P$
$16P=8P+8P$
因为 $23=16+4+2+1$ ，所以 $23P=16P+4P+2P+P$ 。总共只需要7次加法。

分析一下，对于任意正整数k，我们都可以利用这个方法将计算k∗P所需的加法计算次数降低到 $2⋅⌊log2k⌋−1$

也就是说，从时间复杂度的角度来看，这个算法是一个 $O(logk)$ 的算法。

这个方法被称为快速幂算法，原本常用于快速计算某个数的k次幂，这里将其推广到椭圆曲线点乘的快速计算中。

为什么要在介绍了椭圆曲线上点的乘法后突然冒出一个快速幂算法？快速幂算法对于椭圆曲线加密有什么意义？因为数学家/密码学家发现，利用快速幂算法计算 $k∗P$ 的时间复杂度是对数级的，但是要在知道 $k∗P$ 和 $P$ 的前提下，倒推出 $k$ 的值，没有比挨个尝试 $k$ 的值快太多的算法。于是椭圆曲线加密依赖的数学难题就这么诞生了。

$k$ 为正整数， $P$ 是椭圆曲线上的点（称为基点），已知 $k∗P$ 和 $P$ ，计算 $k$

如果我们改一种记法，把椭圆曲线上点的加法记作乘法，原来的乘法就变成了幂运算，那么上述难题的形式跟离散对数问题应该是一致的。即：

$k$ 为正整数， $P$ 是椭圆曲线上的点，已知 $P^k$ 和 $P$ ，计算 $k=log_PP^k$

所以这个难题叫椭圆曲线上的离散对数问题。

尽管两者形式一致，但是他们并不等价。实际上这个问题比大整数质因子分解（RSA）和离散对数（DH）难题都要难得多，目前还没有出现亚指数级时间复杂度的算法（大整数质因子分解和离散对数问题都有），以致于同样的安全强度下，椭圆曲线加密的密钥比RSA和DH的短不少，这是椭圆曲线加密的一大优势。

优点1的证明

1.在已知公钥的情况下，无法推导出该公钥对应的私钥。

假设随机取一个 $0$ ~ $256$ 位之间的值x，计算 $x*P$ ，最后的结果一定会落在曲线上的一点。假设该点为 $X$ ，在公开 $X$ 以及具体曲线的方程的情况下，能否反推出最初的随机值 $x$ ？
证：寻找 $x$ 的过程只能通过暴力计算， $x$ 的可能值为 $0$ ~ $2^{256}-1$ 中的一个，平均来说需要计算 $2^{128}$ 次能够找到一次 $x$ 值。那么问题来了，运行一次 $2^{128}$ 的计算需要多长的时间呢？
假设我们使用的是超级计算机，主频为 $1THz$ （一秒钟可以进行一万亿次运算），从宇宙诞生的那一刻开始计算，到现在也就进行了 $2^{98}$ 次。找到 $x$ 值的概率为 $\frac {2^{98}}{2^{128}}=\frac 1{1073741824}$ 。这个概率和下一秒地球被巨型陨石撞击而毁灭的概率接近，既然我们读到了这里，那么说明这件事没有发生。
在上面的案例中， $x$ 是 $0$ ~ $256$ 位的一个随机数，可以作为私钥。 $X$ 是随机椭圆曲线上的一个点，也就是由私钥生成的公钥，因此优点可以1得证。

但是密码学中，并不能使用上面介绍的实数域上的椭圆曲线。因为

1.实数域上的椭圆曲线是连续的，有无限个点，密码学要求有限点。
2.实数域上的椭圆曲线的运算有误差，不精确。密码学要求精确。

所以我们需要引入有限域上的椭圆曲线。
要证明优点2，还需要将随机椭圆曲线做一些改动：为了保证最后计算出来的点的坐标值相加是512位，secp256k1引入了一个对质数取模的机制。具体来说，随机椭圆曲线从
$y^2=x^3+ax+b$ 变为了 $y^2 mod\ p=(x^3+ax+b)mod\ p$ 其中 $p=2256-232-29-28-27-26-24-1$ ，是小于 $2^{256}$ 的最大质数。
此时的随机椭圆曲线函数图如下：

有限域中的函数图像

4.数字签名

优点2的证明

2.可以通过某些方法来证明某人拥有一个公钥所对应的私钥，而此过程不会暴露关于私钥的任何信息。

具体来说，就是向别人证明我知道 $x$ ，但不暴露 $x$ 的任何信息。（有些类似于零知识证明）
证：前面介绍过结合律： $n\cdot P+r\cdot P=(n+r)\cdot P$ 添加一个hash函数，简单修改可以得出： $hash(m,r\cdot P)\cdot n\cdot P+r\cdot P=(hash(m,r\cdot P)*(n+r))\cdot P$ 使 $n*P=X$ ，那么可知 $n$ 为 $x$ 。此时方程为： $hash(m,r\cdot P)\cdot X+r\cdot P=(hash(m,r\cdot P)*(x+r))\cdot P$ 为了简单起见，我们记 $R=r\cdot P$ 和 $s=hash(m,R)*x+r$ 。此时方程化简为： $hash(m,R)\cdot X+R=s\cdot P$ 上面这个方程是什么意思呢？
可以这样假设：在已知 $m$ 的情况下，如果能够提供一个 $s$ 和 $R$ 满足上面的方程，就可以证明一个人拥有 $x$ 。这个假设有一个前提，如果一个人不知道x，那么他就无法提供 $R$ 和 $s$ 满足上面的等式。
详细探讨这个前提：如果一个人不知道x，又想计算出 $s$ 和 $R$ ，能够办到吗？结论是不能，首先我们无法从 $hash(m,R)$ 计算出 $R$ （在有限时间内）。
还有一个问题：在已知 $R$ 和 $s$ 的情况下，能否计算出关于 $x$ 的任何信息？
根据公式： $s=hash(m,R)*x+r$ 只要解出 $x=\frac {s-r}{hash(m,R)}$ 就可以了。
要想计算出x，就需要知道r，但是在r没有公开的情况下，有什么办法可以计算r吗？我们知道R=r*P；但是根据这个公式无法倒推出r（刚才介绍的那个数学难题），所以x也是安全的。
至此，可以证明算法的第二个优点。