Cobo 密码知识讲堂|第二讲:ECDSA 算法及其门限化设计介绍
2023-6-15 20:10:46 Author: Cobo Global(查看原文) 阅读量:14 收藏

随着香港开始允许散户交易数字资产,数字资产也在逐步走每个人的生活,数字资产、数字签名等新概念层出不穷。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)。设  是一个椭圆曲线点群的基点,其阶为  ,  为一个安全哈希函数,  为待签名消息,三个算法介绍如下:
(1)密钥生成算法
随机选取  ,计算  , 即为  用户私钥,   用户公钥。
(2)签名算法
随机选取  ,计算  ,设置  为点  的横坐标,计算  ,其中  ,最终签名  。
(3)验证算法
将签名  解析为  ,计算  ,设置  为   的横坐标,如果等式  成立,则验证通过,反之验证不通过。
图1 ECDSA算法流程
Part 2:ECDSA 门限签名的介绍
研究现状
虽然 ECDSA 提出时间较早,第一个 ECDSA 门限签名算法直到 1996 年才由 R. Gennaro 等人提出。相比于 Schnorr 和 BLS 签名算法,ECDSA 本身缺乏线性化特征,因此其门限化存在一定的设计难度,即所谓的“Threshold-Unfriendly”。理论困难和缺乏直接的应用场景,使得 ECDSA 门限签名相关研究很长时间都处于停滞状态。近些年来,以比特币为代表的加密数字货币取得迅速发展,它们都使用 ECDSA 作为账户数字签名算法。这为 ECDSA 门限签名算法提供了广泛的应用场景,如区块链账户安全保障、数字资产托管、区块链跨链协议等,使其重新成为研究热点。目前学术界和产业界都在进行高效 ECDSA 门限签名算法的研究,一些研究成果已经应用到相关的产品中。
算法组成
不妨将 ECDSA 算法用三元组  表示,其中  是指密钥生成算法,  为签名算法,  为签名验证算法。对于 ECDSA 门限签名,其将签名的权力分散到一组节点,所产生的签名与普通 ECDSA 算法签名结果是一致的,因此可以用三元组  来表示。介绍如下:
  1.   :分布式密钥生成算法,以安全参数作为输入,输出签名公钥  和   个私钥碎片,每个私钥碎片  仅被节点  掌握,且  个私钥碎片共同构成签名私钥  的秘密分享,需要注意的是,  只是理论存在,不会在密钥生成或者签名过程中出现;
  2.   :分布式签名算法,以待签名的消息和不少于  个私钥碎片作为输入,输出一个合法签名;
  3.   :签名验证算法,和普通 ECDSA 算法一致。
需要说明的是,在一些 ECDSA 门限签名的论文中,还会设计密钥更新算法(常被称为 Reshare 过程)。该算法是在签名节点发生变化时,完成新节点的密钥份额生成以及旧节点密钥份额的更新。由于其实现思路与密钥生成算法非常类似,因此我们不在本文中单独描述,有兴趣读者可以参考相关论文。
Part 3:ECDSA 门限化关键设计
签名私钥的生成方式
宏观来看,ECDSA 门限签名算法的设计本质上是一个安全多方计算的典型问题。其密钥的生成过程是由多方参与,基于 Shamir 秘密分享或者 Feldman 可验证秘密分享实现。而在签名生成过程中,也是由超过门限数量的节点参与,以各自的私钥碎片作为输入,经过一系列的交互,生成对应于公钥的合法签名。因此,私钥的方式直接影响算法门限化的设计,甚至具有决定性作用。因此,采用何种秘密分享方式(如加法秘密分享还是乘法秘密分享),是 ECDSA 门限签名方案设计首先要考虑的问题。
加法、乘法、求逆运算
在确定私钥的生成方式之后,就要考虑如何以“分布式”的方式完成算法的签名过程,其核心计算包括  和  ,需要在不暴露私钥  和随机数  的明文情况下完成相应的计算。该过程需要非常精巧的设计,或者基于巧妙的子协议和子算法完成,或者需要引入其他密码学工具(如全同态/半同态加密算法)辅助运算。无论采取何种技术途径,都需要结合算法的整体实现思路,来确定加法、乘法、求逆运算的设计方式。
“降次”难点
在 ECDSA 门限签名方案设计中,“降次”是关键设计部分,也是整个方案中的难点所在,其直接决定方案是否满足门限最优的性质(具体见图2)。  和  均是以 Shamir 秘密碎片的形式由各签名节点掌握,分别对应与多项式  和  ,二者次数均为  次。在签名过程中,需要计算   ,如果直接将二者的碎片相乘,即   ,该碎片对应的多项式为  。显然   的次数为  ,这代表需要至少  个节点参与才能够完成签名过程。如果定义恢复私钥所需最少节点个数为安全门限,定义完成签名所需最少节点个数为功能门限,显然安全门限为  ,而功能门限为  ,二者的不一致会引发实际应用的安全风险。因此,如何在计算  秘密碎片过程中实现“降次”,是需要重点考虑的问题。
图2 ECDSA门限签名次数提升原因
Part 4:ECDSA 门限签名算法评价维度
从分布式场景应用需求出发,业界对 ECDSA 门限签名算法的性质需求主要包括门限最优、低算法复杂度、可审计性和高安全性,因此这些性质也自然成为评价不同 ECDSA 门限签名算法优劣的主要参考指标(图3)。具体介绍如下:
1)门限最优
门限最优(Threshold Optimality)是指在  -ECDSA 门限签名算法中,节点总数仅需满足  。最早的 ECDSA 门限签名算法要求   ,即在  个节点合作能够产生完整签名情况下,需要将私钥拆分给至少   个节点。这增加了运营成本以及私钥泄露的风险,不满足区块链应用场景需求。因此近年来提出的 ECDSA 门限签名方案中,门限最优已经成为一个基础性质。
(2)低算法复杂度
低算法复杂度内涵低通信复杂度和低计算复杂度两层涵义。低通信复杂度是指节点之间的交互次数要尽可能少,因为在分布式应用场景中,节点地理区域分布广泛,节点之间的网络连接存在不稳定性和延迟性,较少的交互次数能够有效提高算法运行的成功率;低计算复杂度是指协议运行过程中要尽量避免资源密集型的运算,因为在实际应用场景中,参与门限签名的节点可能是手机、平板电脑甚至智能手表等算力有限的终端设备,因此对协议计算复杂度提出较高要求。
(3)可审计性
可审计性是指节点在签名过程中发送数据的合法性是可验证的。这一性质在 ECDSA 门限签名算法实际应用场景中非常必要。如果没有可审计性保障,恶意节点可以通过发送错误数据导致签名失败,同时不暴露恶意身份;在可审计性保障下,恶意节点身份会因为发送错误数据而暴露,进而被诚实节点从签名节点组中排除,无法影响签名的正常生成。
(4)高安全性
高安全性是指方案在实现 ECDSA 签名的理想函数(Ideal Functionality)的基础上,是不可伪造的(Unforgeable),同时在中止情况下,并不会泄漏私钥相关的任何信息。协议的安全性证明一般的步骤包括对不可伪造等性质进行形式化定义(Game-based获Simulation-based),然后在相关的安全假设下(如 DDH 假设、Strong RSA 假设等),最后给出算法的形式化安全证明。
图3 ECDSA 门限签名算法评价维度

Cobo 是全球信赖的数字资产托管解决方案领导者。Cobo 成立于 2017 年,总部位于新加坡,凭借行业领先的托管技术,通过实现安全高效的数字资产管理以及与 Web 3.0 的交互,我们推动增强用户对数字资产的信任。

作为开创性的全能型托管平台,Cobo 提供为满足机构的独特需求而专门设计的全方位托管技术。从基于银行级硬件安全模块 (HSM) 的中心化托管,到基于先进多方计算 (MPC) 技术的协同托管,以及基于智能合约的完全去中心化自托管,Cobo 赋予机构强大的安全保护和管理其数字资产的能力。此外,Cobo 还提供钱包即服务(WaaS)、SuperLoop(交易所场外托管与结算网络)和 Argus(基于角色的访问控制的链上DeFi投资策略和工具)等产品。
Cobo 深受 500 多家机构客户信赖,托管资产达数十亿美元。客户群涵盖交易所、矿池、投资基金、Web3 开发者、原生加密公司以及传统机构,客户遍布亚洲、欧洲、中东、北美和南美。
Cobo 始终致力于安全与合规,通过了 SOC 2 Type 1 和 SOC 2 Type 2 合规性认证,并在美国、新加坡、香港、立陶宛和迪拜(虚拟资产许可证的原则性批准)持有相应牌照。
Cobo 获得 DST Global、A&T Capital、IMO Ventures 和 DHVC Capital 等世界顶级投资机构的支持,2021 年 9 月完成 B 轮 4000 万美元融资。
了解更多 Cobo 数字资产托管技术和解决方案信息,请访问 Cobo 官网:https://www.cobo.com/

文章来源: http://mp.weixin.qq.com/s?__biz=Mzk0OTI3NDAzMQ==&mid=2247484752&idx=1&sn=770b55b2b939480e43bd82c3b3a23350&chksm=c35b9190f42c18860cd74dc56daa46a961f41634250314add7d489b5f5317d1520aeca4d8e85#rd
如有侵权请联系:admin#unsafe.sh