椭圆曲线加密算法与聚合签名原理解析_musig2聚合签名算法

椭圆曲线加密算法（Elliptic Curve Cryptography，ECC）是基于椭圆曲线数学原理实现的一种非对称加密算法。

1 椭圆曲线

椭圆曲线可用以下方程式表示：

y2 = ax3 + bx2 + cx + d
1

定义椭圆上两点相加A+B如下：
过A、B两点的直线，与曲线的交点，关于x轴对称的点为A+B。
对于A+A，即两点重合的情况，则是取A点的切线：

将A关于x轴对称位置的点定义为-A，即椭圆曲线的正负取反运算：

综上，给定椭圆曲线上的某一个点G，可以计算出2G=G+G，3G=G+2G，…，以此类推。即给定G点，已知k，就可以计算出kG；而已知kG，却很难计算出k值，这是离散对数困难问题。这就符合非对称加密的特点，私钥可以推出公钥，公钥不能推出私钥，其中，大数k就为私钥，kG即为公钥。

2 椭圆曲线加解密算法

已知：给定G点，私钥k，公钥P=kG
公钥加密：对消息m进行加密，生成随机数 r，密文C={rG，m+rP}，
私钥解密：m+rP - k(rG) = m + rP - r(kG) = m

注：公布的是rG，而不是r，根据rG很难算出r。随机数r不可暴露，否则rP可被计算出，起不到加密效果。

3 椭圆曲线签名算法

椭圆曲线签名算法有很多种，这里以Schnorr签名为例。

3.1 签名过程

签名其实就是为了向验证方保证这是我发送的消息，但又不能暴露私钥。
从最原始的公私钥关系开始推起：P = kG。
比如我要对m消息，做个签名，我可以这样吗：
计算出
$$e=hash(m)$$

$$s=ke$$
然后把 消息m 和 签名s 发送给对方，对方收到后，计算：
$S_1=sG$
$S_2=eP$
因为s、G、P，都是已知的，e可以根据m计算出，所以S1和S2都可以很快计算出，计算之后，只需要验证S1=S2即可，原理：
$sG=(ke)G=e(kG)=eP$
是不是非常巧妙？

---

但是其中问题非常明显，眼尖的朋友可能早就可以看出，s = ke，e是可以计算出的，把s发送出去之后，明显私钥k也可以很容易计算出来：

$$k=s/e$$

这是简单的除法运算。
那怎么解决这个问题呢？其实问题就出在s = ke里面只有一个未知数k，如果再引入一个未知数，k就无法被计算出来了：
$$s=r+ke$$
其中r是可以是一个随机数。
但这样的话，接收方又要怎么验证呢？
试试：
sG = (r + ke)G = rG + eP
可见，还需要rG的值才可以验证，记R = rG。这同样利用了椭圆曲线的性质，已知rG很难计算出r。
所以，签名就包含两个部分，一个由随机数r计算出的点R，还有由随机数r、私钥k和消息哈希e计算出的s，记为<R, s>，其中：
$$r=random$$

$$e=hash(m)$$

$$R=rG$$

$$s=r+ke$$

---

这样，是不是就没问题了呢？
我们来看一下，假如我们对同一个数据m，进行两次签名：
$s_1-s_2=r_1-r_2+k(e_1-e_2)$
因为是同一个数据，按照上面的计算，$e_1=e_2$，此时：
$s_1-s_2=r_1-r_2$
因为s是签名的一部分，是已知的，那么$r_1$和$r_2$的差值就可以被计算出来，从而可能推算出随机数的计算方法，一旦随机数可预测，则引入的这个随机数自然也起不到作用了。
当然，这可以解决，有两种方法：

① $e=hash(R,m)$
e的计算增加元素R，就会使得即使对于同一个消息m，计算出的e也不一样，就不会有上述问题。

②$r=hash(k,m)$
这种方式计算出的伪随机数，对于同一个私钥对同一个消息签名，生成的r是一样的，就不会有什么随机数会被预测的问题，并且由于私钥对外是未知的，所以r也无法计算得出。

---

问题：随机数可以每次都一样吗？即固定一个随机数，不对外公布即可。
对于这个问题，我们看一下，假如我们对两条不同的消息进行签名：
s 1 − s 2 = r 1 − r 2 + k ( e 1 − e 2