## 函数签名

当metamask小狐狸钱包要获得授权，对我们地址里面的token进行某笔操作时，往往需要首先获得我们私钥签署得到的函数签名。那么通过私钥和交易hash，是如何生成函数签名的呢？在以太坊中，我们采用了ECDSA算法来完成这一签名过程

## 椭圆曲线

椭圆曲线的一般形式为y=x^3+a*x+b(且满足4*a^3+27*b^2!=0),大家注意不要把椭圆曲线和高中的圆锥曲线混淆。下面是一组合椭圆曲线的图片

  

椭圆曲线具有如下基本性质

1. 椭圆曲线关于x轴有对称性

2. 椭圆曲线上的点构成一个群，其中加法是群运算。这个群的单位元是无穷远点 $O$，加法运算满足结合律、交换律、存在单位元和逆元等群公理。

3. 当椭圆曲线上的坐标取值限制在一个有限域上时，这个群是有限的。这个性质是椭圆曲线在密码学中应用的基础。

4. 椭圆曲线上任取两点引出一条直线必交椭圆曲线与群上另一点或无穷远点

5. 给定椭圆曲线上的两个点 $P$ 和 $Q$，找到一个整数 $k$，使得 $kP=Q$。该问题的难度在于找到 $k$ 的过程是困难的，即使知道 $P$ 和 $Q$，也很难找到 $k$。这便是椭圆曲线在函数签名中应用的理论支持

## 椭圆曲线的加法

椭圆曲线的加法不同于我们常见代数运算中坐标与坐标的相加而是通过几何上的关系实现的，如下图所示，在椭圆曲线上取一点 $P(Xp,Yp)$ ，再取一点 $Q(Xq,Yq)$ ，连接P、Q两点作一条直线，必然交椭圆曲线于第三点 $R$ （或者无穷远点），过 $R$ 点作垂直于X轴的直线，将过椭圆曲线另一点 $R'$ （一般是关于X轴对称的点）， $R$ 点则被定义为 $P+Q$ 的结果，既 $P+Q=R$ 


## 椭圆曲线的乘法

讲了加法，乘法自然也就简单了。不过椭圆曲线中的乘法可没有我们小学背的九九乘法表了，而需要通过拆分成加法来完成，椭圆曲线中 $P=k\*$表示 $P=G+G+G....+G$ 也就是过 $P$ 点做切线交椭圆曲线上另一点，取其对称点，然后继续做切线，又交椭圆曲线与另一点，再取其对称点，如此往复 $K$ 次，便可以得到最后的结果。不过我们会发现，当k比较大时，这种计算量往往是无法令人接受的，我们难以通过1次1次的加法的到最终结果，尤其是k是一个比较大的数时。引出我们因入了乘法的快速计算，我们知道 $P+P=2P$ 那么我们计算 $4P$ 时难道还需要用   $P+P+P+P$ 来计算吗？这显然过于麻烦，其实 $4P=2P+2P$ 所以我们只要对已知的 $2P$ 结果进行相加即可 $4P,8P....$ 亦是同理。比如对于基点G，计算 $11\*G$ 这个结果，我们将11转化为2进制1011，那么 $G=P+2P+8P$ 。同时注意这里对 $K$ 的大小有个要求，其必须小于 $P$ 点的阶数，阶数 $n$ 是满足 $nP=\infty$ 的最小正整数 $n$。 当我们所取生成元 $P$ 。需要注意的是，如果椭圆曲线的阶数是一个小的合数，则可以使用Pohlig-Hellman算法等攻击方法进行破解。所以我们一般在加密过程中生成元的阶数为一个大素数，大的要求是至少它要大于可能出现的私钥大小。

## 签名和验证过程

上面的基础知识铺垫完，现在就可以看看ECDSA算法在函数签名中的具体应用了。

选择椭圆曲线和生成元

1. 首先，选择一个椭圆曲线，以及在该曲线上的一个点 $G$，作为生成元。这个点 $G$ 的阶数 $n$ 应该是一个大素数，因为安全性取决于该阶数的大小。

2. 假设要对消息 $m$ 进行签名。签名过程包括以下步骤：  

2.1. 计算点 $P=kG$，其中 $k$ 是一个随机数，注意，只是一个随机数，起作用是为了放在验证者可以通过我们发去的验证信息反推出私钥，从而实现非对称加密。并将 $P$ 的横坐标 $x$ 作为签名的第一个部分。  

2.2. 计算 $e=H(m)$，其中 $H$ 是一个哈希函数， $m$ 就是我们要传递的消息。  

2.3. 计算 $s=k^{-1}(e+dx)\bmod n$，其中 $k^{-1}$ 是 $k$ 在模 $n$ 意义下的逆元， $k^{-1}*k=1$ 其中1表示基点， $k^{-1}$ 是一个大小在0到n-1之间的数。  

2.4. 签名结果为 $(x,s)$。

3. 验证过程

假设接收到了消息 $m$ 和相应的签名 $(x,s)$，验证过程包括以下步骤：  

3.1. 验证 $x$ 和 $s$ 是否在合法范围内,即 $1 \leq x < n$ 且 $1 \leq s< n$。  

3.2. 计算 $e=H(m)$。  

3.3. 计算 $w=s^{-1}\bmod n$。  

3.4. 计算点 $u_1=ew\bmod n$ 和 $u_2=xw\bmod n$。  

3.5. 计算点 $V=u_1G+u_2Q$。  

3.6. 如果 $V=\infty$，则验证失败；否则，如果 $x\equiv x_V\bmod n$，则验证成功，否则验证失败。