2024-07-10 2024-07-10 12526 字 26 分钟

- 数字签名

#include <iostream>
using namespace std;
int main(){
    cout << "你可以在这里编写，测试代码!" << endl;
    cout << "目前只支持c++,java和python!" << endl;
    cout << "点击右上角切换语言!" << endl;
    return 0;
}

常见签名算法

ECDSA签名

ECDSA简介：

椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线密码（ECC）对数字签名算法（DSA）的模拟。ECDSA于1999年成为ANSI标准，并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受，并且包含它的其他一些标准亦在ISO的考虑之中。与普通的离散对数问题（discrete logarithm problem DLP）和大数分解问题（integer factorization problem IFP）不同，椭圆曲线离散对数问题（elliptic curve discrete logarithm problem ECDLP）没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。

有趣的是，ECDSA的前身DSA是ElGamal和Schnorr方案的结合，而DSA签名完全是为了规避Claus Schnorr的专利而设计的。事实上，就在Schnorr的美国专利发布两个月后，DSA的创造者美国国家标准与技术研究院（NIST）也为其解决方案申请了专利。Schnorr一度对此表示不满，并直接发邮件对其进行的批评。

DSA签名方案

作为ECDSA签名的"前身"，首先对DSA签名算法做一个简单的介绍，读者可以将ECDSA签名和DSA签名算法对比学习。由于下面会详细介绍ECDSA算法，这里DSA算法的介绍不在遵循标准的签名介绍方法，二十简单对其进行介绍。

密钥生成

随机生成一个1024bit的大素数p，并找到p-1的一个160bit的素除数q 。找到一个q阶子群的生成元 $\alpha$ 并选择一个随机的整数 $d\in z_q^* $, 然后计算 $\beta \equiv \alpha^d \pmod p $ 。选择一个哈希函数 H 。则公钥为 $K_{pub}=(p,q,\alpha,\beta,H)$ , 私钥为 $k_{pr}=d$.

DSA签名

选择一个随机的整数 $k_E \in Z_q^* $,

计算 $r\equiv (\alpha^{K_E} \pmod p) \pmod q$

计算 $s\equiv (H(x)+d\cdot r)\cdot k_E^{-1} \pmod q$

最终的DSA签名结果是一对 $(r,s)$

DSA验签

计算辅助值 $w\equiv s^{-1} \pmod q$

计算辅助值 $u_1 = w\cdot H(x) \pmod q$

计算辅助值 $u_2 = w\cdot r \pmod q$

计算 $v\equiv (\alpha^{u_1} \cdot \beta^{u_2} \pmod p) \pmod q$

如果 $v=r \pmod q$ 则认为他是一个有效的签名，否则认为他是一个无效的签名。

ECDSA签名方案：

Setup

系统初始化阶段，用来生成必要的签名参数。具体过程是：选择有限域$F_p$上的一个椭圆曲线$E(a, b)：y^2=x^3+ax+b \ (mod \ p)$且对于$E(a, b)$来说，它满足$4a^3+27b^2≠0\ (mod \ p)$ 选择$E(a, b)$上的一个点 $P$ 作为生成元，其中 $P$ 的阶为$n$ 。选择一个哈希函数 H , 则最终的参数为 $Params = ( E(a, b), P , H )$ 。

KeyGen

该过程用来生成用户的公私钥对，用于后续的签名（Sign）和验签（Verify）。选择随机数 $sk$ 作为私钥(其中k<n)，计算公钥 $P_{pub}=skP$

Sign

选择随机数$r$，计算$r\cdot P=(R, y)$ .实际上 $r\cdot P$ 是一个椭圆曲线上的点，他的横坐标和纵坐标分别为 R 和 y

计算$h=H(m)$

计算$s = r^{-1}(h + sk\cdot R) \pmod n$ （这里，$k^{-1}$是k在模n下的乘法逆元）

则最终签名为$σ=(R, S)$。（注意，如果r, s中任意一个为零，重新选择随机数计算签名）

Verify

假设收到的签名是 $(m, σ)=(m, R, S)$

计算 $h = H(m)$

计算 $(s^{-1}\cdot h)P+(s^{-1}\cdot R)P_{pub}=(x_1, y_1)$

比较 $r_1≡x_1\ (mod\ p)$ 和 $r_1=R$ 是否成立，如果成立，验签成功。否则，验签失败

采用ECDSA的弊端主要有：

1）ECDSA的验签过程中，需要进行求逆运算，计算开销较高。

2）不支持批量认证，和多重签名，如果要验证多个签名，需要分别执行验证操作，验证开销随着签名的数量线性增加。

参考文献

Schnoor 签名：

Schnoor签名简介

Schnorr签名由德国数学家和密码学家Claus-Peter Schnorr于1990年在论文中提出，具有‌签名长度短、‌计算开销低、可扩展性强等优点。除此之外，Schnoor签名支持密钥聚合和批量认证。Schnoor签名的安全性基于离散对数困难问题，被广泛认为是一种安全可靠的签名方案。经过多年的发展，Schnoor签名还衍生出了多重签名、门限签名等扩展，并在身份认证、比特币、区块链等方面获得大量应用。 Schnoor签名本质上是一种零知识的技术，即Prover声称知道一个密钥x的值，通过使用Schnorr签名在不揭露x的情况下向Verifier证明其对x的知情权。（也就是证明自己拥有私钥）

作者简介

Schnoor于1970年获得University of Saarbrücken大学博士学位。Schnorr对密码学的贡献主要是对Schnorr groups的研究，这些研究被用于以他的名字命名的数字签名算法中。除此之外，Schnorr还因其对算法信息论的贡献和创建了一种算法随机序列的定义方法而闻名，该方法可替代Martin-Löf随机性的概念。 Schnoor于1993年获得莱布尼茨奖。2013年获得RSA数学卓越奖。

Schnoor在论文发表之前就申请了Schnoor签名的专利，直到2008年，该签名的专利才到期。有趣的是，2008年正是中本聪（Satoshi Nakamoto）开始创造比特币的时间。在比特币的构造过程中，需要考虑的一个关键设计是使用哪种签名方案。事实上，Schnoor签名与ECDSA相比更加适合于比特币系统的构建，但由于Schnoor签名的专利一直被Schnoor持有，而ECDSA没有专利问题，并且已经被开源加密工具OpenSSL支持，中本聪最终选择了ECDSA。直到多多年以后，Schnoor签名才被正式应用于比特币和区块链中。

签名方案

Schnoor签名分为交互式和非交互式两种，为了方便描述，我们称交互式的方案为 Schnoor 协议，非交互式的为 Schnoor签名。需要指出的是，在Schnoor签名的原始论中，作者是基于离散对数困难问题构造的签名方案，而椭圆曲线可以用更短的签名长度达到同样的安全级别，本文的介绍使用的是椭圆曲线上的Schnoor签名。

交互式的Schnorr协议

Setup

系统初始化阶段，用来生成数字签名需要用到的参数。具体过程是：选择一个p阶椭圆曲线E(a,b)以及它的生成元G，生成公共参数 pp = { E(a,b) , p , G } 并将其公布。

KeyGen

该过程用来生成用户的公私钥对，用于后续的签名（Sign）和验签（Verify）。假设要给用户 $U_a$ 生成公私钥对 , 首先生成一个随机数 $a \in_R Z_p^* $ , 计算 $PK=a*G$ , 令 $U_a$ 的公私钥对为 $(sk,PK)=(a,PK)$.

Sign & Verify

在交互式的签名过程中，签名者和验签者需要同时参与到签名的生成和验证过程中。假设Alice想要生成一个签名让Bob验证，并且共公共参数 pp Alice和Bob都知道，Alice的私钥为 a ，公钥为 PK 且 Bob已经获得了 PK 。交互式的Schnoor协议过程如下：

Alice 生成一个随机数 $r \in_R Z_p^* $ 并计算 $R=r\cdot G$, 然后将 R 发送给 Bob ；

Bob 选择一个随机数 c 作为挑战发送给 Alice ；

Alice 计算 $z=r+c\cdot sk$ 并将其发送给 Bob ;

Bob 验证等式 $z\cdot G=R+c\cdot PK $ 是否成立，如果成立，则验证签名成功。

说明

在协议开始之前，Bob知道Alice的公钥是 PK ，如果Alice知道私钥 sk ，那么它可以很容易的计算出$z=r+c\cdot sk$ ，将该等式两边同时乘G可得：$z\cdot G=c\cdot PK+R$。也就是说，如果Bob验证了上述等式，即可验证Alice确实拥有私钥sk。 (在上述协议中，验证者Bob并不能得到私钥sk的信息，因此这个过程是零知识的，且是交互式的。此协议是Sigma protocol的一个特例)

上述协议的的过程如下图所示：

该协议的一些分析

由于椭圆曲线上的离散对数问题，知道R和G的情况下通过 $R=r\cdot G$ 解出r是不可能的，因此 Bob 无法通过 z,r,c 求出 sk ，故，上述协议是零知识性。
但是上述协议存在一个很严重的问题：由于上述协议存在交互过程，因此只对参与交互的验证者有效，无法做到公开验证。
- 如果 Mallory 和 Bob 如果串通随机数c，那么不参与交互的人无法判断出证明者是否真的是Alice。因为 Mallory 和 Bob 可以按照以下过程执行协议：
  假设 Mallory 和 Bob 进行串通，约定 Bob 在协议中会回复一个特定的挑战 $c_0$。
  1. Mallory 生成一个随机数 $r \in_R Z_p^* $ 并计算 $R=r\cdot G - c_0 \cdot PK$, 然后将 R 发送给 Bob. 这里的 PK 表示 Alice 的公钥；
  2. Bob 将实现串通好的挑战 $c_0$ 发送给 Mallory ；
  3. Mallory 将 $z=r$ 发送给 Bob ;
  4. Bob 验证等式 $z\cdot G=R+c_0 \cdot PK $ 是否成立，如果成立，则验证签名成功。
  上述过程非参与方看来和 Alice 与 Bob 的交互协议没有任何区别，验证也能正常通过，但是 Mallory 并不知道 Alice 的私钥 sk 。我们将上述协议抽象为 Prover 和 Verifier 之间的协议 $\Pi$。那么上述例子表明，除了协议 $\Pi$ 中的 Verifier 之外，任意人无法通过协议 $\Pi$ 的内容判断 Prover 是不是Alice。Verifier 可以判断 Prover 身份的原因是，如果 Verifier 没有跟 Prover 串通的情况下， Prover 能生成正确的 z ，则 Prover 是合法的。
- 我们进一步分析标量 c 的随机性对协议的影响。通过上述协议不难发现，如果 Prover 能提前猜到 Verifier 选择的 c ，那么他可以伪造成任何人! 因为 Prover 知道 Verifier 会用 PK 和 R 相加然后再与z * G进行比较。所以 Prover 可以在不知道私钥 sk 的情况下按照上述串通情况下的协议 $\Pi$ 执行，Bob发现不了任何异常。
补充一点，事实上上述协议是完备的(Soundness)。如果验证者 Verifier 分别提供两个不同的挑战 $c_1$ 和 $c_2$，并要求证明者 Prover 给出同一承诺 R 下的两个响应 $z_1 = r + c_1\cdot sk$ 和 $z_2 = r + c_2\cdot sk$，那么这个验证者可计算出 sk =（z1-z2）/（c1-c2）。（在协议 $\Pi$ 中，R 称为承诺，c 称为挑战，z 称为响应。这是Simga协议中的名词，了解更多请参考Sigma协议）

非交互式的Schnorr签名

将交互式的Schnorr协议改造为非交互式 Schnoor签名非常简单。通过上述分析我们知道，保证协议中 Verifier 选择的挑战 c 的随机性是保证该协议安全的关键。Fiat-Shamir启发式方法基于随机预言机模型，它们假设存在抗碰撞的哈希函数 H，它的结果在敌手看来是随机的，由于哈希函数的不可逆性，我们可以利用 H 改造上述交互式协议如下，得到一个非交互式的 Schnoor 协议，也称 Schnoor 签名。

Alice：随机选择 r，计算$R=r*G$ （椭圆曲线上的一点）；

Alice：计算 $c = H(R, PK)$；

Alice：通过计算 $z=r+c\cdot sk$，将$(R, z)$给Bob；

Bob： Bob计算 $c=H(R,PK)$，Bob验证 $z\cdot G = c\cdot PK+R$。

需要说明的是，在正式的Schnoor签名中，存在一个被签名的消息 m ，我们需要做的是修改 c 的计算方式为 $c=H(R,PK,m)$，其余部分保持不变即可得到消息 m 的 Schnoor签名 (R,z) 。

非正式的分析：

我们粗略的分析一下上述Schnoor签名的安全性，并不是正式的安全性证明，正式的安全性证明请参考原文.

上述 Schnoor 协议之中，Prover 和 Verifier 之间进行串通能够骗过非协议交互方的原因是 Prover 提前预知（通过串通）了一个与协议其他参数无关的挑战 c ，而在 Schnoor 签名中 c 由随机预言机 H 生成，无法被 Prover 预测，故 Schnoor 签名是安全的。
在上述串通的 Schnoor 协议中，Mallory 预先串通得到 c ，通过计算 $R=r\cdot G - c \cdot PK$ 并令 z = r 使得非交互式 Schnoor 协议无法公开验证。而Schnoor签名(R,c,z)的计算过程中$c=H(R,PK)$。如果使用同样的方式进行伪造会发现，计算 R 需要用到 c ，计算 c 需要用到 R ；故导致敌手伪造 Schnoor 签名。

Sigma协议和Fiat-Shamir启发式：

https://www.yuque.com/xiaozeng-lhkfj/guc7a3/egsn1gzebrmkfcz1#fuMTK【笔记】

Schnoor签名的批量认证

Schnoor签名可以进行批量认证，这是因为它的签名具有线性性质。但是批量认证并未减少计算开销，这里不再赘述。

Schnoor 签名的扩展

Schnoor多重签名

实现Schnoor签名的一个简单思路如下：

密钥聚合与签名生成:

这里我们引入一个聚合器 Agg ，她负责执行一些特点的操作，Agg 可以由生成多重签名的某个实体担当，也可以由其他任意实体充当。Schnoor多重签名的生成过程如下：

聚合器 Agg 将签名者的公钥集合 $(PK_1,…,PK_n)$ 聚合称一个聚合公钥 $P = \sum_{i=1}^n PK_i$。
当 n 个人要生成一个多重签名时，每个用户分别选择随机数 $r_i$ 并计算 $R_i = r_iG$，随后每个人将自己的 $R_i$ 广播给其他人。
其他人收到 {$R_i$} (i ∈ [1,n]) 后计算$R=\sum_{i=1}^nR_i$ 和 $c = H(m,P,R) ; s_i = r_i + c \cdot sk_i $ 并广播自己的 Schnoor签名 $(R_i,s_i)$。
聚合器 Agg 收到 n 个人的签名 $\sigma_1,…,\sigma_n$后，计算 $z=\sum_{i=1}^nz_i$ ，最终的签名为 $(R,z)$

多重签名验证：

验证者 Verifier 计算$c = H(m,P,R)$, 然后验证等式 $z\cdot G=R+c\cdot P$ 是否成立，如果成立，则完成了对n个用户的批量认证。

上述多重签名的过程似乎并未减少总的计算开销，那么他有什么用呢？事实上，上述多重签名的生成与验证过程计算量是不对称的，生成签名的计算量很大，但是验证签名的计算量永远都是验证一个签名的计算量。这个性质在某些应用场景下是非常有用的，比如在区块链中，某一个交易可能需要多个人的签名才能生效，而交易发出去之后，所有人都需要验证这个交易的合法性，此时验证成本低廉很有用。

这里提一句，Schnoor签名可以通过Merkle树实现(m,n)多重签名，有兴趣的读者可以自行搜索。

存在的问题

上述Schnoor多重签名的生成过程需要签名方之间进行交互，当多重签名的用户比较多的时候，整个交互流程比较复杂。（暂时无法解决，最新的FROST签名可以做到半交互式）
存在流氓密钥攻击。(可通过修改方案预防，具体来说是将签名和密钥的聚合过程改成非线性的,参考《Simple Schnorr Multi-Signatures with Applications to Bitcoin》或BLS的方案)
Schnoor签名实际上是一个零知识证明，它具有soundness，也就是存在一个提取器。因此所有的签名不能使用同一个随机数 r ，否则可以提取私钥(参考零知识证明)。

参考文献：

http://blockchain.whu.edu.cn/uploads/soft/201105/1_1954088811.pdf
Schnoor签名还可以实现(t,n)门限签名，聚合签名等，读者可自信搜索。

BLS短签名

BLS签名简介

BLS签名，由斯坦福大学计算机系的Dan Boneh，Ben Lynn以及Hovav Shacham在2001年提出，其核心思想是将待签名的消息哈希到椭圆曲线上的一个点，并利用双线性映射函数e的交换性质，在不泄露私钥的情况下进行签名验证。BLS签名被称为"BLS短签名"，因为签名本身只是椭圆曲线上的一个点，是已知的签名长度最短的签名。

BLS签名具有多个有趣的特性，例如支持签名的聚合和批量验证，还可以构建门限签名等。这些特性使得它在区块链等领域得到广泛应用。作为第一个使用双线性映射的数字签名方案，BLS签名对后续的数字签名乃至密码学的发展产生了重要影响，为后续更复杂、更广泛应用的签名方案奠定了基础。

作者简介

Dan Boneh于1969年生于以色列，并于1996年从普林斯顿大学获得计算机科学博士学位、并于1997年加入斯坦福大学任教至今，在Coursera上开设了大规模的开放在线课程，出版了很多密码学相关书籍、教材，以免费在线提供他的整个密码学入门课程而闻名。

Boneh与加州大学的Matt Franklin是基于配对密码学发展的主要贡献者之一，2016年被选为美国国家工程院院士。他在基于身份的加密、广播加密、同态加密、区块链等多个密码学领域均有重要成果发表；参与设计tcpcrypt用于传输层安全的TCP协议扩展，提出了一种针对HTTP协议的侧信道攻击和对OpenSSL的时序攻击，在比特币方面也有成果产出。他曾获哥德尔奖、RSA数学杰出奖、Selfridge奖、斯隆奖、ACM计算奖等。他担任斯坦福大学区块链研究中心的联合主任，并在2002年与三名学生创办名为Voltage Security的公司，随后于2015年被惠普收购，是即会理论又能实践的大佬。

BLS具体方案

Map to point Hash函数简介

一般的hash（散列）函数的结果都是数值。在BLS签名算法中需要用的散列函数的结果是椭圆曲线上的一个点。也就是说，散列结果对应椭圆曲线上的一个点。以 ECC 和 SHA-256 为例。比特币用的椭圆曲线是secp256k1，也就是该曲线由2²⁵⁶个点组成。SHA-256普通Hash函数的结果也是256位。如果用Hash函数的数值结果，对应于椭圆曲线上点横坐标x，有两个点y和-y都在椭圆曲线y²=x³+ax+b上。说明SHA-256的结果，有50%的概率，要么找到两个点，要么找不到点。

为了解决这个问题，需要用到直接从消息计算到一个点的哈希，给定消息 m，计算H(m)，使得 H(m)∈ G，其中G是椭圆曲线点构成的群。Dan Boneh在文章中给出了一个具体的做法，例如采用的仍然是普通哈希，把结果（先看成一个数）当作是一个点的 x 坐标，然后带入椭圆曲线公式计算相应的 y 坐标。如果不存在，则把第一步的 x 坐标作为输入继续算哈希得到另一个 x 坐标，计算相应 y坐标，直到求出 y 为止。根据二次剩余理论，平均算2次即可得出一个对应的 y 。这样确保首先是一个确定性的算法，可以在有限步骤内(数学期望为2次)完成计算；其次，如果采用的哈希函数本身是安全的，则整体的计算过程也是安全的。这样整个计算称为Map-to-Point哈希。

BLS签名方案

假设Alice的私钥为$pk$，公钥为$P = pk×G$，想对消息 m 签名，则：

签名：计算$S = pk×H(m)$作为消息 m 的签名

验签：判断$e(P, H(m)) = e(G, S)$是否成立，成立则验签成功。

上述过程如下图所示：

验证过程涉及e函数，计算如下的等式是否成立：$e(P, H(m)) = e(G, S)$

证明过程如下： $e(P, H(m)) = e(pk×G, H(m)) = e(G, pk×H(m)) = e(G, S)$

证明过程示意如下：

BLS签名的扩展

BLS多重签名

多重签名定义

在数字签名应用中，有时需要多个用户对同一个文件进行签名和认证。比如，一个公司发布的声明中涉及财务部、开发部、销售部、售后服务部等部门，需要得到这些部门签名认可，那么，就需要这些部门对这个声明文件进行签名。能够实现多个用户对同一文件进行签名的数字签名方案称作多重数字签名方案。

在现实生活中，一份文件经常需要几个单位或部门分别签字(或盖章)才有效，多重签名技术就是在网络环境里解决这类问题的一种方法，用于同一文档必须经过多人的签名才有效的情形。多重签名通俗地讲就是指多个签名者共同参与对一份电子文档进行签名。简单地说，一个多重签名体制回答这样几个问题：哪些人参加签名，按照什么顺序签名，使用什么方法签名，怎么验证签名和安全性如何得到保证。BLS签名支持多重签名方案。

BLS多重签名

沿用上面的符号，我们假设有n个用户，它们的公私钥对分别为($P_i,pk_i$)，它们欲对同一个消息 $m$ 进行签名得到一个BLS多重签名。假设第 i 个用户对消息 $m$ 的 BLS 签名为 $S_i$ ，我们可以使用以下方式生成这些用户对消息 $m$ 的多重签名。

将 n 个用户的签名 $S_i$ 进行累加即可得他们对消息 m 的多重签名 $S = S_1+S_2+…+S_n$ , 其中 $S_i = pk_i×H(m)$;i={1, 2, …, n}。为了验证多重签名的合法性，首先计算 $P=\sum_{i=1}^n P_i$ 作为验证该多重签名的聚合公钥，然后验证等式 $e(G, S) = e(P, H(m))$ 是否成立即可。

我们可以看出，使用BLS多重签名可以使得 n 个人的签名大小和一个人的签名大小完全一样，并且签名的验证过程比挨个验证 n 个签名计算量少了几乎一半。正确性显然成立，这里不再证明。

问题与改进

上述最直观的BLS多重签名方案容易受到"流氓密钥攻击"。比如说，Alice公私钥对为 $(pk_1,P_1)$ , 同时 Bob 的公私钥为 $(pk_2,P_2)$ , Bob可以对外声称自己的公钥为 $P’=P_2 - P_1$, 那么他可以使用自己的私钥生成BLS签名 S 作为他与Alice的多重签名，其他人认为 $P=P_1+P’=P_2$ 是 Bob 与 Alice 的聚合公钥，并使用它验证签名 S 。很显然验证可以通过，但实际上Alice并未参与这个多重签名。如果一笔钱需要 Alice 和 Bob 共同授权才能使用，那么 Bob 可以通过这种方式独自控制这笔财产。为了防止这种攻击，可以使用非线性方式构造聚合公钥。具体方式如下:

将 n 个用户的签名 $S_i$ 进行非线性累加得 $S = a_1S_1 + … + a_nS_n$ , 其中 $S_i = pk_i×H(m)$ 且 $a_i=H(P_i,\{P_j\}) ; i,j=\{1, 2, …, n\}$。我们将 $S$ 作为这 n 个用户对消息 m 的多重签名。为了验证多重签名的合法性，验证者首先计算非线性聚合公钥 $P=\sum_{i=1}^n a_iP_i$ 作为验证该多重签名的聚合公钥，然后验证等式 $e(G, S) = e(P, H(m))$ 是否成立即可。

上述多重签名能够防止流氓攻击的关键是签名和聚合公钥的构造中，非线性系数 $a_i$ 与多重签名的所有参与者的公钥都有关，改变任何一个参与者的公钥都会导致所有系数的变化，这将导致攻击者无法同时控制自己的公钥和系数，从而大大增加了流氓密钥攻击的难度。

(m,n)多重签名

上述多重签名可以被看成是(n,n)多重签名，也就是必须要n个参与者同时签名才能生成一个有效的多重签名，这种多重签名方案的一个缺点是所有多重签名的缺点是存在单点故障问题，我们可以使用BLS(m,n)多重签名来解决这个问题，为此，我们将使用到：

正常的hash函数，输出为a number，hash(x)。

hash to the curve，输出为curve上的point， H(x)。

需要有“setup” phase，setup后不再需要communicate，可以用来sign any amount of transactions。

为了方便打字，以下以2-of-3 多重签名为例进行讲解，三个不同的密钥存储在三个不同的设备中：（可扩展至任意的 (m , n)多签）

1）Setup phase：

该系统要求每个签名方维护相同的序号 1 , 2 , 3 ，即依次为签名方1，签名方2，签名方3 。这个阶段的主要目的是通过(n,n)多重签名为每个参与者构建成员密钥 $MK_i$，拥有 $MK_i$ 的参与者被认为是一个有效的多重签名参与者，他将在生成阈值签名时起作用。具体的构建过程如下：

假设 $P = a_1 × P_1 + a_2 × P_2 + a_3 × P_3$ 其中 $a_i = hash ( P_i , P_1 , P_2 , P_3 )$。所有签名方对数字 i（其值必须在序号范围内）进行签名然后进行密钥聚合，每个签名方 i 存储与其序号一致的密钥聚合信息 $MK_i = ( a_1 ) × ( pk_1 × H ( P , i ) ) + ( a_2 ) × ( pk_2 × H ( P , i ) ) + ( a_3 ) × ( pk_3 × H ( P , i ) )$, 也即是 $MK_i = ( a_1 ⋅ pk_1 ) × H ( P , i ) + ( a_2 ⋅ pk_2 ) × H ( P , i ) + ( a_3 ⋅ pk_3 ) × H ( P , i )$。事实上，$MK_i$ 可以被理解为对 $H(P,i)$ 的多重签名，满足： $e(G,MK_i)=e(P,H(P,i))$

2）签名阶段：

如使用 $pk_1$ 和 $pk_3$ 签名，则 $S_1=pk_1\times H(P,m) + MK_1,S_3=pk_3\times H(P,m)+MK_3$ 直接累加有： $(S’,P’)=(S_1+S_3,P_1+P_3)$ 其中 P’为参与签名的签名者的聚合公钥。

3）验签阶段：

验签阶段，验证者0除了需要知道签名(P’,S’) 之外，还需要知道参与签名者的索引，如本例中的签名者索引为数字1和3。验证2-of-3 阈值签名，仅需验证下面的等式是否成立即可： $$e(G,S’)=e(P’,H(P,m))⋅e(P,H(P,1)+H(P,3))$$ 如果签名是合法生成的，那么上述等式恒成立。因为成员密钥 $$e(G,S’)=e(G,S_1+S_3) =e(G,pk_1×H(P,m)+MK_1+pk_3×H(P,m)+MK_3)$$ 即 $e(G,S’)=e(G,S_1+S_3)=e(P’,H(P,m))⋅e(P,H(P,1)+H(P,3))$

BLS签名的聚合

签名聚合是指"将多个签名聚合在一起，形成一个签名的过程"，由多个签名聚合成的最终签名被称为是聚合签名。通过聚合签名可以大大缩小存储多个签名所需要的空间，从而降低存储开销，这在区块链中是一个非常有用的性质。例如：在一个区块中有n个交易，每个交易都有独立的公钥$P_i$,私钥$pk_i$，签名 $S_i$以及交易内容$m_i$。如果需要知道区块中的交易的签名是否都正确，传统的方式，区块中的交易需要一个个的验证签名。然而，区块中需要存储所有交易的签名需要占用大量的内存。而使用BLS算法进行签名的合并只需要存储一个33个字节的BLS签名。

这里提一句，聚合签名和多重签名的区别是，多重签名是多个人对同一个消息进行签名，并最终得到一个多重签名。而聚合签名是每个人对各自的消息进行签名，最终聚合为一个聚合签名。它们的本质区别是"到底是对同一个消息签名，还是对不同的消息签名"

签名聚合

沿用上面的符号，我们假设有n个用户生成BLS签名，它们的公私钥对分别为($P_i,pk_i$)，且对消息 $m_i$ 的签名为 $S_i$ 。我们可以使用以下方式对签名进行聚合。

将n个用户的签名进行聚合得到聚合签名$S = S_1+S_2+…+S_n$, 其中 $S_i = pk_i×H(m_i)$;$i={1, 2, …, n}$。为了验证聚合后的签名S，只需要验证下面的等式是否成立即可 $$e(G, S) = e(P_1, H(m_1))⋅e(P_2, H(m_2))⋅…⋅e(P_{n}, H(m_{n}))$$

我们可以看出，使用BLS聚合签名可以使得n个人的签名大小和一个人的签名大小完全一样，并且签名的验证过程比挨个验证n个签名计算量少了几乎一半。我们这里证明上述聚合签名的验证过程是正确的：

$e(G, S) = e(G, S_1+S_2+…+S_{n}) = e(G, S_1)⋅e(G, S_2)⋅…⋅e(G, S_{n})$ $= e(G, pk_1×H(m_1))⋅…⋅e(G, pk_{n}×H(m_{n}))$ $= e(pk_1×G, H(m_1))⋅…⋅e(pk_{n}×G, H(m_{n}))$ $= e(P_1, H(m1))⋅e(P_2, H(m_2))⋅…⋅e(P_{n}, H(m_{n}))$

BLS阈值签名

阈值签名方案(TSS)是一种从多个签名者生成单一数字签名的方法。生成的签名看起来与没有使用阈值方案生成的签名一样,但它并不是由单一私钥创建的。相反,它是由多个私钥份额创建的,这些份额是分布式的,因此没有任何单一个人完全控制私钥。在阈值签名中，假设有 n 个参与者拥有秘密份额，要生成一个消息的签名, 至少需要 t 个人参与，则我们记这种阈值签名为(t,n)阈值签名。

秘密份额分发方法

要想进行阈值签名，首先要为参与者分发秘密份额，这个过程有很多方法。可以使用可验证的秘密共享进行分布式密钥协商，从而得到每个人的秘密份额。也可以使用一个秘密分发者进行秘密分发的方式进行份额的分发。它们的区别是，使用分布式秘密生成份额可以在开放的环境中进行，并且没有人知道真正的秘密值，所有人都只知道自己的秘密份额，但是这种方案计算开销较大。而是用秘密分发者的方式进行份额分发，必须在安全的环境中进行，并且秘密分发者知道所有人的份额和秘密，但计算开销很小。由于分布式秘密共享需要用到多项式承诺，并且验证过程比较负责，不是本节的主要内容，因此这里使用秘密分发者在安全通道分发秘密份额。

秘密份额分发

秘密分发者首先随机生成 $ t - 2 $ 个小于 $ p $ 的随机数 $ a_{1}, a_{2},…, a_{t - 1} $ 并构造一个 t-1 阶的多项式 $ f (x) = a_0 + a_{1} x + … + a_{t-1} x^{t-1}$ ，其中 $ f (0) = a_{0} = s $ 是群组私钥，$PK = sP$ 是群组公钥。
秘密分发者随机选取 $ n $ 个互不相同的整数 $ x_{1}, x_{2}, \cdot, x_{n} $ 并将 $ n $ 个整数代入多项式函数 $f(x)$得到 $ n $ 个值 $ sk_1 = f (x_1)$, $ sk_2 = f(x_2)$,…, $sk_{n} = f (x_{n}) $ , 然后将计算得到的 $ n $ 个坐标 $(x_i,y_i)$ 分别发给 $ n $ 各参与方并销毁 $ f (x) $，即第 $ i $ 个参与方获得 $ (x_{i}, y_{i}) $ 。为了简单起见，可以假设 $x_i = i$ ，这并不影响方案的安全性。

阈值签名的生成

case1：为了生成一个阈值签名，至少需要 t 个参与者合作，参与者 i 计算拉格朗日插值函数值 $L_i = \prod_{j\in[n]}^{j\neq i} \frac{i}{j-i}$ ，然后使用自己的秘密份额生成消息 m 的部分签名 $S_i=sk_i\cdot L_i\cdot H(m)$ 。随后将自己的部分签名广播出去。

case2: 另外，也可以把拉格朗日插值函数值的计算放到验证者哪里执行，此时签名者 i 只需要计算消息 m 正常的BLS签名 $S_i=sk_iH(m)$并广播出去。

阈值签名的验证

case1-验证：任何人在收到 t 个合法的部分签名之后可以使用群组公钥 $PK$ 验证阈值签名的合法性。验证者首先计算阈值签名 $S=S_1+…+S_t$ 。然后验证等式 $e(S,G)=e(H(m),PK)$ 是否成立，如果成立，则签名验证通过。

case2-验证：任何人在收到 t 个合法的部分签名之后可以使用群组公钥 $PK$ 验证阈值签名的合法性。验证者首先计算拉格朗日插值函数值$L_i = \prod_{j\in[n]}^{j\neq i} \frac{i}{j-i}$，然后计算阈值签名 $S=L_1S_1+…+L_tS_t$ 。然后验证等式 $e(S,G)=e(H(m),PK)$ 是否成立，如果成立，则签名验证通过。

参考文献：

ECDSA Schnoor BLS 对比

国密SM9算法

SM9简介

SM是“商密”的拼音,是我国"自主知识产权"的算法。SM9则是其中的一种基于身份的密码系统,包括加密和签名两个算法。SM的家族里还有SM1/2/3/4等对称、非对称、摘要算法，它们虽然也是ECC的一种实现，但是存在很多创新之处。当然由于RSA提出的很早并且迅速成立公司占领市场，使得它的应用非常广泛，短时间内很难被替代。因此在应用生态方面SM系列还有待努力。SM9是一种用户体验很好的算法，应该是很好的助推工具。

SM9签名算法

预备知识

PKI与IBC简介：

上面提到SM9是一种基于身份的加密算法(IBC)，这里首先对IBC进行一个解释。为此，我们首先介绍基于公钥基础设施(PKI)的密码体制。简单来说，传统的非对称密码体制需要PKI的辅助，主要是需要一个证书颁发机构CA（Certification Authority）给用户颁发证书并负责这些证书的管理个维护工作，用户之间通过证书完成身份认证、从而保证用户公钥等信息的合法性。基于PKI的公钥系统存在一个缺点，那就是用户的公钥是一段晦涩难懂的二进制字符串，而用户使用公钥加密的时候记忆公钥称为一个非常头疼的问题，正因为如此，用户无法将一个公钥与一个用户对应起来，这就需要CA为每个公钥颁发证书，保证这些公钥确实对应于某一个合法用户，这也是需要CA对公钥颁发证书的一个重要原因。

IBC密码系统是一种解决了上述问题的非对称密码系统。在IBC中，任何一个用户标识符都可以作为用户的公钥，人们可以使用自己的邮件地址，手机号码，身份证号码等作为自己的公钥，而这些信息可以很容易的与特定的用户联系在一起，因此不需要使用证书系统。一个需要解决的问题是，有了公钥之后，如何生成对应的私钥。为了实现这个功能，IBC系统中引入了一个新的实体，密钥生成中心(KGC)。用户只需要将自己的公钥给KGC，KGC就能生成一个对应的私钥返回给用户，这样用户就可以使用公私钥对完成相应的加密和签名操作了。

密码学工具简介

H(A，q)：表示一种哈希函数，对A进行哈希，得到一个小于 q 的哈希值。
KGC：密钥生成中心，用户将自己的身份作为公钥传输给KGC，KGC为其生成对应的私钥。
双线性映射: 本文使用$G_1×G_2→G_T$的双线性映射，其中$G_2$上的点的大小是$G_1$上的2倍。$G_1$和$G_2$是加法循环群，$G_T$是乘法循环群。