首页 › 研究报告
Author：GF · 欢迎转载但请保留作者姓名
椭圆曲线密码学（Elliptic Curve Cryptography，缩写 ECC）是一种基于椭圆曲线数学的公开密钥加密算法。椭圆曲线在密码学中的使用是在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出的，其算法在 2004 年至 2005 年开始广泛应用。2009 年 1 月，比特币诞生。在比特币的内部结构中，创始人中本聪使用了公钥密码学——非对称加密算法，他具体采用的就是椭圆曲线 ECC 函数方程作为数字签名算法，而之后的几乎所有加密货币的数字签名都采用的是椭圆曲线 ECC 这一技术。
在 1994 年，美国计算机科学家 Peter Shor 在贝尔实验室的内部研讨会上提出了一个新的证明，表明量子系统能够比经典计算机更快地解决一个特定的问题。这个问题被称为离散对数问题，用经典计算机的方法无法解决，因此离散对数在当时成为了少数安全系统的基础。RSA 与 ECC 都基于这一特定问题理论被制造出来。Shor 算法的发明使得在数学理论层面将椭圆曲线 ECC 和 RSA 的算法破解复杂度大幅降低。Peter Shor 于 2022 年 9 月 23 日荣获「2023 年科学突破奖」（基础物理学突破奖）。
时间来到 2001 年，IBM 分别在 5 位 NMR 量子计算机、7 位 NMR 量子计算机上成功运行了 Shor 量子算法，成功将 21 分解为 3 和 7，将 15 分解为 3 和 5，这标志着人类首次在硬件上实现 Shor 量子算法，从而在实践层面证明了量子算力与 Shor 算法合并使用对传统公钥密码学的威胁真实存在。
The simplest meaningful instance of Shor's Algorithm is finding the factors of the number 15, which requires a seven-qubit quantum computer. IBM chemists designed and made a new molecule that has seven nuclear spins — the nuclei of five fluorine and two carbon atoms — which can interact with each other as qubits, be programmed by radio frequency pulses and be detected by nuclear magnetic resonance (NMR) instruments similar to those commonly used in hospitals and chemistry labs.
笔者按：前文提及椭圆曲线在 2004 至 2005 年被大规模应用，而 1994 年和 2001 年理论层面就破解了椭圆曲线密码学这件事在逻辑上并不冲突。因为算力的限制，人们认为离可用于实际破解现实密码学的量子计算机的发明还很遥远，所以并不担心椭圆曲线在短时间内被真正破解，在当下正常使用无需担心。
鉴于量子威胁的日益临近，美国国家技术标准局 NIST 在 2016 年发起了全球范围内征集抗量子计算破解算法的项目，目的是对新算法进行标准化，并为之后各个领域的密码学算法全面升级做好准备。抗量子破解算法，也称后量子密码学（PQC）。从形式上划分，PQC 分成公钥加密和数字签名，和加密货币有关的是数字签名算法。经过 8 年时间、3 轮淘汰赛，截止到第 3 轮，数字签名类的 3 个技术路线被确定：格 Lattice 签名、哈希 Hash 函数签名、多变量 Multivariate 签名。其中格签名 Crystal-Delithium、格签名 Crystal-Falcon、多变量签名 Rainbow 被列为正选算法，哈希签名 SPHINCS+ 为备选算法。截止 2024 年 2 月，NIST 披露尚无数字签名的标准算法完全胜选，未来还将举行第四轮竞选。
人们普遍认为，只有在量子计算机发明并被媒体广泛报道后，对传统密码学的威胁才会到来。但他们并没有用博弈的角度思考量子威胁这一问题。因为对密码学的攻击破解往往都不会是公开的炫耀，而是隐蔽的盗取，在对手不知情的情况下拥有信息差，使自己处于有利位置。
其中最经典的案例莫过于第二次世界大战期间英国科学家图灵团队对纳粹德国 Enigma 密码器的破译。英国人在破解了 Enigma 密码器后没有公开炫耀自己的成就——那样会使得德国改变自己的加密策略——而是暗暗获取德国的军事情报，将计就计。当德国计划伦敦大轰炸时，其实英国早已知晓，但是为了不让德国起疑，不能疏散全部市民，让德国轰炸机来炸一座空城。破译 Enigma 密码器的这一事件要等到 50 年后的 1990 年代才最终解密。因此，攻击型量子计算机，特别是军事用途的量子计算机（CRQC）的发明很可能不会有任何媒体报道。
此外，加密期与解密期是一个组织对机密档案管理的重要方法。假设一个机密档案离解密还有 50 年时间，攻击者可以先将被加密的档案数据包盗取下载转移到自己的存储之中。攻击者当下确实没有量子计算机可以破解该密码，传统算法破解该数据更是天方夜谭。但是大国博弈，科技是前沿，也许 20 年后随着科技的发展量子计算机就被发明甚至高度应用。这样一来，攻击者就有可能破解该数据包，而解密期要等到 50 年以后——这意味着攻击者可能会提前 30 年解密这些数据。
未雨绸缪才是应对良策，在一个黑暗森林的博弈对局中获取优势。美国国家安防备忘录 NSM-10（2022 年 5 月 4 日发布）明确了密码学从传统到后量子密码学 PQC 的迁移路线和 2035 年全美各机构全面迁移的期限，并在 Section 3-c-vii 中明确提及未来将公布易受量子攻击算法的弃用时间表（椭圆曲线函数数字签名 ECC 被归类为易受攻击的算法之内）。
在 2022 年 9 月，美国国家安全局发布了 CNSA 2.0，旨在让全美安全系统升级到 PQC 算法，并且在数字签名领域推荐使用 CRYSTALS-Dilithium 数字签名，取代之前的椭圆曲线 ECC 签名，并要求全部的合作企业（包括浏览器、云服务、操作系统、网络设备硬件）必须升级到 PQC，并给出时间表。
当下美国为代表的中心化组织已经开始动员全美各个大型机构全面迁移到 PQC，并已经有完整的计划，那么去中心化的加密货币该何去何从？椭圆曲线在实装应用了 20 年之后，面对各个国家、各个大型科技公司在量子计算研发上面的布局发力，面对海量资本向量子霸权的押注，已经开始显露疲态。加密货币这种椭圆曲线保护下的无主产品，找到新的庇护所才是重中之重。
公开密钥密码学（Public-key cryptography）也称非对称式密码学，需要两个密钥：一个是公开密钥，另一个是私有密钥；公钥用作加密，私钥则用作解密。由于加密和解密需要两个不同的密钥，故被称为非对称加密。公钥可以公开，私钥必须由用户自行严格保管。
在加密货币里面使用的都是数字签名类公钥密码。而数字签名在 PQC 之中有三个技术路线：基于格 Lattice 的数字签名、基于哈希 Hash 的数字签名、基于多变量 Multivariate 的数字签名。考量数字签名应用场景的指标有三个：私钥长度、公钥长度、签名长度。私钥储存在本地用于解密计算，对其大小没有特别要求；而公钥和签名都需要发送至通讯网络，所以对大小的要求限制非常多。
ECC256 在矩阵图的最左下方，意味着签名和公钥都很小，均不到 100 Bytes。这也就是当初中本聪选择 ECC 作为比特币基石加密算法的原因——小巧便捷易于传输，太大的 Size 会造成拥堵。
但在量子威胁之下，ECC 和 RSA 算法肯定是不安全了，即便它们有小巧的优势，那么只能在 PQC 算法里面选择。哈希签名的公钥不大，但是签名非常大；多变量签名的签名不大，但是公钥非常大；而格签名介于两者之间，其签名长度和公钥长度也要比 ECC 大 20 倍以上。也就是说 PQC 的几种方案都存在长度的问题，尽管算法方程式的参数可以调整，可数量级的大小不会改变，否则将失去安全性。
那么一定是要在工程结构上扬长避短，不让 PQC 的缺点影响到性能。公钥虽然每次都广播，但每次都是固定的，因为公钥是私钥通过一个单向函数生成的唯一解；而签名则不同，签名函数里面有私钥和消息两个变量，每次发送的消息不同，所以数字签名每次都不一样。既然公钥永远不变，那么公钥可以做一个邮政编码化——即发送地址信息，因为地址是公钥通过特定函数生成的，同样具有高度的唯一性和抗碰撞性。地址可以看作是公钥的索引，于是加密货币在使用过程中，一个地址只需要广播一次公钥即可，以后的转账无需每次都广播公钥，这就一定程度上规避了公钥过大的问题。
在采用工作量证明 POW 共识机制的加密货币中，对签名长度的要求更加敏感，因为节点众多且分布广泛，一旦签名长度超过系统的处理能力，转账系统可能会出现大规模拥堵。固定节点或者少量节点的权益证明 POS 有可能可以使用其他的数字签名。最早且市值最大的加密货币比特币采用的就是 POW 机制。
因此顺着这条路线思考，最可能用于 POW 加密货币场景升级的技术路线就是多变量签名 Multivariate：它具有和 ECC 一样数量级的签名大小，以及一个非常大的公钥，而大公钥的缺点可以通过邮政编码化的技术进行优化，把缺点压到可用范围内。
彩虹签名 Rainbow 是多变量签名的代表，根据官方介绍，它于 2004 年发明，创造者是 Jintai Ding 和 Dieter Schmidt，构筑在不平衡油醋混合签名 UOV 方案之上（后者的发明人是 Jacques Patarin）。彩虹签名于 2020 年 7 月 22 日进入 NIST 遴选算法的最终名单（Finalist）。它的理论基础基于求解一个二次多项式函数的 NP 问题，背后蕴含着重要的数学思想——代数几何学。从结果上看，该签名的长度仅仅 528 个字节，比其他的 PQC 方案都要短小许多。
J. Patarin 设计了一个新方案，称为「油与醋」，用于计算不对称签字。它很简单，可以很快地计算，在智能卡实施中需要很小的 RAM。此方案的想法包含将二次方程隐藏于有限域 K 中 n 个称为「油」的未知数和 v=n 个称为「醋」的未知数内……我们研究初始方案的某些很简单的变动，其中 v＞n（而不是 v=n）。这些方案称为「不平衡油醋」（UOV）……
| 安全等级 | 参数 (GF, v1, o1, o2) | 私钥 (kB) | 公钥 (kB) | 签名 (Bytes) |
|---|---|---|---|---|
| I | (GF(16), 36, 32, 32) | 58.8 | 101.2 (99.0) | 528 |
| III | (GF(256), 68, 32, 48) | 258.4 | 611.3 (603.0) | 1,312 |
| V | (GF(256), 96, 36, 64) | 523.5 | 1,375.7 (1,361.8) | 1,696 |
表：Key and Signature Sizes for Cyclic Rainbow。括号内为当线性映射 S 与 T 从 256 bit 种子生成时的私钥大小。
Raqcoin 的前身名为 ABCMint，在 2018 年 6 月 18 日启动，后于 2022 年经社区投票表决改名 Raqcoin，中文名：热矿币。它是当前唯一实装了多变量数字签名的加密货币，至今已稳定运行近 6 年，采用了 POW 的共识机制，是一种类比特币形式的加密货币，实现价值存储、数字黄金的功能。正常转账速度流畅，得益于它的公钥邮政编码化解决方案和多变量的短签名特性。在 Raqcoin 创造之初，数学结构由彩虹签名的作者提供，代码程序由匿名团队创建，所有代码全部开源。
在 2022 年 1 月，一个密码学团队攻击了安全等级为 1 的彩虹签名。随后 Raqcoin 将算法全面升级到更高等级，消解了该项攻击。因此当下的 Raqcoin，每一组助记词可以生成 7 个私钥对应的 7 个地址，每个地址被不同等级的多变量函数保护。用户可以自己选择将加密货币储存在哪个等级的签名之下，安全等级低的地址转账手续费会比安全等级高的手续费低。
比特币的挖矿是求解哈希函数，目前比特币矿工需要使用专业的 ASIC 矿机进行哈希计算以求解目标值，这样会增加挖矿的门槛，使得个人设备被完全排除在挖矿之外，不利于去中心化。Raqcoin 采用的是求解多项式函数，平均每 10 分钟出一个区块，当挖矿算力变高或变低时，挖矿难度自动调节以适应出块的平均时间。理论上采用笔记本电脑的显卡就可以挖矿，一定程度上更加公平。
Raqcoin 的产出总量是 2,147,483,647，是比特币总量的约 100 倍，全部挖完需要大概 90 年。每隔 5 年左右产量下降，下降比例是前一次的 73.5%。前 8 年大致会产出总供应量的 50%。目前 Raqcoin 的钱包还是独立钱包，并没有植入在主流的手机钱包当中；钱包分成 PC 端的全节点钱包与手机端的轻节点钱包两种，无论哪一种都是去中心化的，私钥需由资产主人亲自保管，遗失私钥即资产永久丢失。
后量子密码学非常前沿，从各项算法的发明时间上看，基本都在 20 年以上，密码安全不是一朝一夕可以证明的，路遥方知马力。这一次 NIST 举办了一场空前的选拔赛，全世界顶尖的大学密码学团队悉数提交了自己的方案。从结果上看：2017 年 12 月 21 日第一轮比赛时，一共有 69 个 PQC 算法参赛；到 2019 年 1 月 30 日第二轮时，只有 26 个算法在列，另外 43 种全部被破解淘汰出局，有的算法 24 小时就被破解。竞争十分残酷——在密码学领域被破解的算法一文不值，团队多年的心血之作全部归零。
截止到 2024 年 4 月，PQC 中密钥交换领域的算法已经被标准化推荐，而数字签名依然没有最终答案。未来的需求场景不同，适应的数字签名也不相同，不容易标准化、唯一化，可见选拔之艰难。
可以想象的是，当下依然有众多投资者对比特币升级到 PQC 保持着盲目乐观的态度：要么认为现在离 Q-Day 还很遥远，要么认为届时有很多解决方案如同超市商品待客挑选，要么认为临近 Q-Day 临时想办法发明一个就行。这些都是错误的认知。PQC 可以选择的方案非常少，而多变量数字签名甚至可能是加密货币场景的唯一解法。
此外，也会有很多人对 NIST 长期淘汰赛的含金量重视不足。未来一定会有某团队宣称自己发明了新的 PQC 密码系统，但是这种未经淘汰赛检测过的密码学很可能有极大安全漏洞——想想 NIST 第一轮到第二轮的惨烈程度，提交者都是顶级大学或科研院所的密码学团队，即便如此照样铩羽而归。现在还在列的算法年龄都在 20 年以上，前 10 年或 15 年在实验室学术界讨论，后 10 年参与 NIST 遴选打榜。你发明个 3–5 年，然后产品测试上运行个 6 个月，就宣称自己的算法能抗量子计算了？