ECDSA算法

椭圆曲线乘法（又称为ECDSA）是密码学重要的非对称加密算法，同时在比特币系统中，私钥的生成使用的也是ECDSA算法。比特币使用了secp256k1标准定义的一条特殊的椭圆曲线和一系列数学常数。

在讲解ECDSA算法之前，先了解一下计算机是如何实现乘法和除法的。

计算机所能完成的基本操作是：+、- 和左移、右移。在计算机中所有的操作都是以二进制的形式在运行，那么对于数字的操作也同样也是这样。

乘法实现

对于计算机而言左移一位代表乘以2，右移一位代表除以2。对于a乘以x而言，只是将a左移x为1的位并累加可得到最后的结果。例如：拿53为例
5的二进制数：0101
3的二进制：0011
则乘法实现的步骤：
1、3的第0位为1，则将5（0101）左移0位，结果仍为5（0101）；
2、3的第2位为1，则将5（0101）左移一位，结果为10（1010）–左移一位相当于52=10；
3、将两次结果相加为1111=15

除法实现

计算机除法的实现相对较为复杂，它也可以理解用乘法来实现。
例如：51/3
51的二进制：110011
3的二进制：11
1、从51的第1位开始（从左往右），第一位为1，小于11，结果为0，余数为1
2、从第二位开始，余数2+1=11（3），等于11，结果为1，余数为0
3、从第三位开始，余数2+0=0，结果为0，余数为0
4、从第四位开始，余数2+0=0，结果为0，余数为0
5、从第五位开始，余数2+1=1，小于11，结果为0，余数为1
6、从第六位开始，余数*2+1=11，等于11，结果为1，余数为0
将结果位相连（从1到6），为10001=17

椭圆曲线乘法

依据上述对计算机的乘法和除法描述，我们发现，虽然除法可以用乘法实现，但本质上都是加法的实现，因此除法的实现要复杂很多。椭圆曲线乘法就是利用除法计算困难的特性来保证密钥对的安全性。
举个例子：
7+7=14，也就是2个7相加等于14，同理，可用加法算出8个7相加等于56，那么多少个7相加等于864192呢，因为计算机的这种实现都是用加法来计算。如果是人来算，就需要一定的计算力才能很快得出答案。
椭圆曲线乘法就时利用这个原理，它是一个基于加法阶数难求问题的密码方案。以上面的这个例子为基础，椭圆曲线的基点就时例子里面的7，而私钥就是基点的加法阶数（也就是8），公钥是基点（7）对应阶数的加法得到的结果（56）。
但是ECDSA与上述描述又有所不同，它的加法建立在“有限域上的二元三次曲线上的点”上，组成一个“有限加法循环群”，形象的说就是两个点的加法结果是指这两点的连线和曲线的交点关于x轴的镜像。
下述的图就是椭圆曲线乘法的大概情况：

secp256k1曲线由下述函数定义，该函数可产生一条椭圆曲线：
y²=(x³+7)over(F_p)
或
y²mod p=(x³+7)mod p
上述mod p（素数p取模）表明该曲线在素数阶p的有限域内，也写作F_p，其中p=2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1
以一个随机生成的私钥k为起点，我们将其与曲线上已定义的生成点G想成以获得曲线上的另一点，也就是相应的公钥K，生成点是secp256k1标准的一部分，比特币密钥的生成点都是相同的：

{K = k * G}

其中k是私钥，G是生成点，在该曲线上所得的点K是公钥，因为所有比特币用户的生成点是相同的，一个私钥k乘以G将得到相同的公钥K，k和K的关系是固定的，但只能单向运算，即从k得到K，这就是可以把比特币地址（K的衍生）与任何人共享而不会泄露私钥（k）的原因。

ECDSA这样定义加法有两个目的：

对求逆运算（由公钥推私钥）制造困难，如果一直用算力来做加法，是不现实的
简化正向运算（由私钥计算公钥），这样做是能够使用一些基本的运算，比如结合律、减法等

因此，正向计算的定义就很简单了，私钥为k属于 [0,n); 基点为点P;公钥点Q定义为K个P相加：

k就是私钥，Q就是公钥。

从难度上来说：除法>乘法>加法，因此要想从公钥推私钥是有一定难度的，目前由ECDSA求私钥的最有效的算法复杂度为O（√p），其中p是阶数n的最大素因子（这里n累加的次数，相当于K）。当参数选的足够好让p>2¹⁶⁰时，以目前的计算力，攻破ECDSA是不现实的。

上述这就是ECDSA算法生成密钥对的大致过程。