Cobo 密码知识讲堂｜第二讲：ECDSA 算法及其门限化设计介绍
作者：Cobo密码学团队
随着香港开始允许散户交易数字资产，数字资产也在逐步走进每个人的生活，数字资产、数字签名等新概念层出不穷。Cobo 密码知识讲堂计划推出以“门限签名”为主题的系列科普文章，旨在以深入浅出的方式，带领读者了解数字签名中门限签名的技术本质和应用原理。该系列科普文章每一篇内容相互独立又互相补充，涵盖门限签名的概念及典型应用、ECDSA 门限签名的设计及发展现状、Schnorr 门限签名的设计及发展现状、基于门限签名的账户体系构建，以及层级化门限签名设计等多个该领域的热点和难点问题，力求通过对技术研究的深层次剖析和解读，让读者对门限签名领域有更加深刻的理解。
本讲概述：ECDSA 是区块链领域最常用的数字签名算法之一，针对其的门限化设计也是当前密码学的热点研究问题。本期课程介绍 ECDSA 算法及其门限化设计：首先将介绍 ECDSA 签名算法，包括其产生背景和算法流程；其次，介绍 ECDSA 门限签名方案，包括研究现状和算法组成；再次，通过对 ECDSA 门限签名过程中的计算特征，明确其设计的关键；最后，我们给出 ECDSA 门限签名算法的评价维度。
Part 1：ECDSA 签名算法介绍
产生背景
椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm，简称ECDSA）是由 Kravitz 在 1991 年提出，是美国国家标准与技术研究院（NIST）和电气与电子工程师协会（IEEE）认定的标准数字签名算法。ECDSA 是 DSA 算法的椭圆曲线版本，不同的是其安全假设并不是普通离散对数问题或者大整数分解问题，而是椭圆曲线离散对数问题（ECDLP）。由于椭圆曲线离散对数问题远难于普通离散对数问题，因此椭圆曲线密码系统的单位比特强度要远高于传统的离散对数系统，在相同安全级别下，ECDSA 的密钥长度要比 DSA 或者 RSA 更短。因此，ECDSA 尤其适用于处理性能、存储空间、带宽及功能受限的场合。值得注意的是，ECDSA 的安全性并没有数学层面严格形式化证明，但是业内普遍认为该签名算法是安全的。
算法流程
ECDSA 由密钥生成算法、签名算法和验证算法组成（图1）。设 G 是一个椭圆曲线点群的基点，其阶为 q ，Hash 为一个安全哈希函数， M 为待签名消息，三个算法介绍如下：
Part 2：ECDSA 门限签名的介绍
研究现状
虽然 ECDSA 提出时间较早，第一个 ECDSA 门限签名算法直到 1996 年才由 R. Gennaro 等人提出。相比于 Schnorr 和 BLS 签名算法，ECDSA 本身缺乏线性化特征，因此其门限化存在一定的设计难度，即所谓的“Threshold-Unfriendly”。理论困难和缺乏直接的应用场景，使得 ECDSA 门限签名相关研究很长时间都处于停滞状态。近些年来，以比特币为代表的加密数字货币取得迅速发展，它们都使用 ECDSA 作为账户数字签名算法。这为 ECDSA 门限签名算法提供了广泛的应用场景，如区块链账户安全保障、数字资产托管、区块链跨链协议等，使其重新成为研究热点。目前学术界和产业界都在进行高效 ECDSA 门限签名算法的研究，一些研究成果已经应用到相关的产品中。
算法组成
需要说明的是，在一些 ECDSA 门限签名的论文中，还会设计密钥更新算法（常被称为 Reshare 过程）。该算法是在签名节点发生变化时，完成新节点的密钥份额生成以及旧节点密钥份额的更新。由于其实现思路与密钥生成算法非常类似，因此我们不在本文中单独描述，有兴趣读者可以参考相关论文。
Part 3：ECDSA 门限化关键设计
签名私钥的生成方式
宏观来看，ECDSA 门限签名算法的设计本质上是一个安全多方计算的典型问题。其密钥的生成过程是由多方参与，基于 Shamir 秘密分享或者 Feldman 可验证秘密分享实现。而在签名生成过程中，也是由超过门限数量的节点参与，以各自的私钥碎片作为输入，经过一系列的交互，生成对应于公钥的合法签名。因此，私钥的方式直接影响算法门限化的设计，甚至具有决定性作用。因此，采用何种秘密分享方式（如加法秘密分享还是乘法秘密分享），是 ECDSA 门限签名方案设计首先要考虑的问题。
加法、乘法、求逆运算
在确定私钥的生成方式之后，就要考虑如何以“分布式”的方式完成算法的签名过程，其核心计算包括 k × sk 和 k-1G ，需要在不暴露私钥 sk 和随机数 k 的明文情况下完成相应的计算。该过程需要非常精巧的设计，或者基于巧妙的子协议和子算法完成，或者需要引入其他密码学工具（如全同态/半同态加密算法）辅助运算。无论采取何种技术途径，都需要结合算法的整体实现思路，来确定加法、乘法、求逆运算的设计方式。
“降次”难点
Part 4：ECDSA 门限签名算法评价维度
从分布式场景应用需求出发，业界对 ECDSA 门限签名算法的性质需求主要包括门限最优、低算法复杂度、可审计性和高安全性，因此这些性质也自然成为评价不同 ECDSA 门限签名算法优劣的主要参考指标（图3）。具体介绍如下：
（1）门限最优
门限最优（Threshold Optimality）是指在 (n,t) -ECDSA 门限签名算法中，节点总数仅需满足 n≥t 。最早的 ECDSA 门限签名算法要求 n≥2t-1 ，即在 t 个节点合作能够产生完整签名情况下，需要将私钥拆分给至少 2t-1 个节点。这增加了运营成本以及私钥泄露的风险，不满足区块链应用场景需求。因此近年来提出的 ECDSA 门限签名方案中，门限最优已经成为一个基础性质。
（2）低算法复杂度
低算法复杂度内涵低通信复杂度和低计算复杂度两层涵义。低通信复杂度是指节点之间的交互次数要尽可能少，因为在分布式应用场景中，节点地理区域分布广泛，节点之间的网络连接存在不稳定性和延迟性，较少的交互次数能够有效提高算法运行的成功率；低计算复杂度是指协议运行过程中要尽量避免资源密集型的运算，因为在实际应用场景中，参与门限签名的节点可能是手机、平板电脑甚至智能手表等算力有限的终端设备，因此对协议计算复杂度提出较高要求。
（3）可审计性
可审计性是指节点在签名过程中发送数据的合法性是可验证的。这一性质在 ECDSA 门限签名算法实际应用场景中非常必要。如果没有可审计性保障，恶意节点可以通过发送错误数据导致签名失败，同时不暴露恶意身份；在可审计性保障下，恶意节点身份会因为发送错误数据而暴露，进而被诚实节点从签名节点组中排除，无法影响签名的正常生成。
（4）高安全性
高安全性是指方案在实现 ECDSA 签名的理想函数（Ideal Functionality）的基础上，是不可伪造的（Unforgeable），同时在中止情况下，并不会泄漏私钥相关的任何信息。协议的安全性证明一般的步骤包括对不可伪造等性质进行形式化定义（Game-based获Simulation-based），然后在相关的安全假设下（如 DDH 假设、Strong RSA 假设等），最后给出算法的形式化安全证明。
