2023-1-5 量子计算攻破密码？会威胁BTC归零吗？

一、量子计算攻破RSA密码？

2023年新年伊始，一则消息在国内安全、区块链、量子计算圈子等相关的专家微信群悄悄传开，原始信息（如下图）来自国外安全技术专家Bruce Schneier的个人博客www.schneier.com，Schneier被《经济学人》称为“安全大师”，也是哈佛大学肯尼迪学院研究员。博客里提到：“一组中国研究人员刚刚发表了一篇论文，声称他们可以——尽管他们还没有这样做——打破2048位的RSA。这是一件值得认真对待的事情。这可能是不正确的，但它并非明显错的。”

我看到这则消息后，表示：如果是真的，这是大事件！因为这可能要颠覆当前的密码技术。

备注：RSA是一种公钥密码算法，它的名字由三位开发者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的；RSA被广泛用于公钥密码和数字签名。

RSA也是公司名，为累计30000家客户提供安全和数字风险管理软件；2006年9月，RSA Security以21亿美元被EMC公司收购；2022年2月，DELL公司（曾在2015年10月以670亿美元收购EMC）宣布以21亿美元的价格将RSA出售给私人股权投资公司Symphony Technology Group（STG）。

RSA从1991年开始每年召开RSA信息安全大会（RSA Conference，简称RSAC），是全球安全趋势的风向标。第32届RSAC 2022在2022年6月6日已经召开。

之后，我发现2022年12月29~31日，国内的光子盒研究院，安全圈，国外的thequantuminsider.com等网站都报道过此事，可能没引起很多人注意。下面摘录光子盒在2022年12月29日的报道《清华浙大在量子计算破解RSA密码方面取得重要突破》：

在一项最新研究中，清华大学龙桂鲁、浙江大学王浩华等组成的团队创建了一种算法，仅用10个超导量子比特就实现了48位因式分解。

大多数专家认为这项任务将需要数百万个量子比特。该团队的最新实验表明，依靠整数因子化的公钥密码技术可能很快就会受到当今原始的NISQ（含噪声中等规模）量子计算机的攻击。

据研究人员称，该算法是基于经典的Schnorr算法——使用格约化来分解整数，同时依靠量子近似优化算法（QAOA）来优化Schnorr算法中最耗时的部分，以提高因式分解的速度。

更多中文详情，参见：光子盒研究院 2022-12-30

《清华浙大在量子计算破解RSA密码方面取得重要突破》

从arxiv网站

https://arxiv.org/pdf/2212.12372.pdf能看出该论文预印本于2022年12月23日上线。真希望中国人能在破解密码上，继山东大学王小云教授破译MD5密码之后，再次领先全球。文章的标题和摘要如下（摘自kurtpan.pro）：

“在超导量子处理器上使用亚线性资源分解整数”

摘要：Shor算法对基于公钥密码体制的信息安全提出了严峻的挑战。然而，要破解广泛使用的RSA-2048方案，需要数百万的物理量子比特，这远远超出了目前的技术能力。这里，我们通过将经典格归约与量子近似优化算法 (QAOA) 相结合，报告了一种用于整数分解的通用量子算法。所需的量子比特数为 O(logN/loglogN)，这在整数 N 的比特长度上是亚线性的，使其成为迄今为止最节省量子比特的分解算法。我们通过 10 个超导量子比特将高达 48 位的整数分解（量子设备上分解的最大整数）来通过实验展示了该算法。我们估计，使用我们的算法挑战 RSA-2048 需要一个具有 372 个物理量子比特和数千深度的量子电路。我们的研究在加快当前噪声量子计算机的应用方面显示出巨大的希望，并为分解具有现实密码意义的大整数铺平了道路。

图：Workflow of the sublinear-resource quantum integer factorization (SQIF) algorithm

2023年1月4日在国外的网站，如论坛groups.google.com，安全博客schneier.com，社交新闻类reddit.com开始讨论这个话题。例如下图的谷歌论坛

翻译如下：

1)这种方法对于RSA-2048及以上版本的可行性如何？

2)一些公司已通知说，他们最早将在2025年发布1000个量子位（qubits）处理器。如果论文中的说法适用于更高的量子位，那么行业不应该更快地采用PQC（比如CNSA套件2.0时间线）

3)这种方法可经修改，打破椭圆曲线密码学吗？

4)某些更新后，本文中的方法是否可以用于对抗任何当前已知的PQC？

备注：PQC（Post-quantum Cryptography，后量子密码）是能够抵抗量子计算机对现有密码算法攻击的新一代密码算法。所谓“后”是因为量子计算机的出现，现有的绝大多数公钥密码算法（RSA、Diffie-Hellman、椭圆曲线等）能被足够大和稳定的量子计算机攻破，所以可以抵抗这种攻击的密码算法可以在量子计算和其之后时代存活下来，所以被称为“后”量子密码。也有人称之为“抗量子密码”。PQC对应的含义，也有另一种表述”Quantum-resistant cryptography”。

CNSA：美国国家安全局(NSA)的商用国家安全算法

讨论当中，也有质疑声，例如markku评论：

需要注意的是，本文并没有声称所提出的方法比经典的分解方法更快。当论文谈到“资源”时，它省略了“运行时长（running time）”；仅仅是人们所声称的是，量子电路（quantum circuit）非常小。

“亚线性”意味着它的量子位元可以比被分解的数要小。他的方法是一种混合的经典量子方法；数字N必须保存在经典计算机上。

基于非常粗略的启发式方法，它在这个设置中似乎有一个指数级的运行时间。所提出的方法与Shor的分解算法（它实际上运行在多项式时间内）没有任何关系。相反，它是基于经典的Schnorr算法（礼貌地说），这个算法是有争议的。当然，这篇论文中的实验分析存在严重缺陷，研究人员一直无法找到支持其说法的证据。Léo Ducas 有一组关于这类方法的分解的注释：https://github.com/lducas/SchnorrGate

至于对实际PQC算法的影响，没有迹象表明CVP（备注：最近向量问题）的渐近（指数）加速，这可能会影响基于格的系统。也许像“Babai优化器”这样的东西可以从具体的安全分析中减少一些bits。然而，这将仅仅是一个持续因素的改进。

下面介绍一下参与论文撰写的成员。

该团队除了清华大学龙桂鲁教授、浙江大学王浩华教授，还有来自数学工程与先进计算国家重点实验室、清华大学、浙江大学、北京量子信息科学研究院、信息工程大学和量子信息前沿科学中心的科学家。

清华大学龙桂鲁教授。龙教授1962年4月生，广西玉林人。中共党员。毕业于山东大学，1987年毕业于清华大学，获博士学位。教授。现任清华大学物理系核物理教研室主任，兼任中科院理论物理所客座研究员、兰州重离子加速器国家实验室原子核理论中心客座研究员。

如下图是浙江大学王光宇教授。王教授还是2022年“科学探索奖”获得者。

二、会威胁BTC归零吗？

很多和数字货币相关的人士，可能会意识到量子计算破解密码算法后，对于比特币的影响。我个人觉得不会导致比特币归零，但大幅震荡的影响可能会有。正如谷歌量子霸权消息传来后，BTC下跌了一阵子，后来又归于平静。

2019年10月24日集体学习后，我在10月28日撰写的《被误解的区块链》系列文章的第一篇的后半部分，特别讨论了量子计算与比特币的关系。全文原创发表于微信公众号乐生活与爱IT，但现在只能通过后期同步到其他媒体的文章阅读。用户朋友们可通过点击文末左下角“阅读原文”跳转。

下面将当时的相关段落摘抄出来：

（2019年10月28日）因为几位朋友的电话咨询，触发了一些新的思考。我个人的观点是：1、看好区块链和比特币的长期发展；2、不看好短期内中国区块链的发展。下面的截图是有关量子计算对比特币影像的逻辑推理。

最近好几位朋友通过电话，咨询我对区块链和比特币的看法。感谢他们的咨询，其实在沟通过程中有时会及时触发新的思考和观点。先分享我关于量子计算对比特币影响的观点，一家之言，不构成投资建议，仅供参考。2019年10月23日，比特币狂降500美元（8000降到7500），我猜测大概率是因为谷歌宣称“量子霸权”。

去年在一个微信群，曾有朋友提出量子计算对比特币的威胁。那时候，比特币历经九年而不倒。我个人也认为在近几十年内，唯一的威胁可能就是量子计算了。

结合之前的讨论，和最近的一些思考。关于量子计算对比特币的威胁，我个人认为：

1、技术

从可能性到落地需要很长的周期；

到底多长，不好说，至少5年，也许需要十多年。

2、成本

谁来利用量子计算对比特币进行威胁？威胁的成本有多大？

个人不太可能，如果他持有比特币，他不会做这件事；如果他不持有，他通过这种攻击瞬间获益的概率也有，但难度和风险都比较大；

政府有这种可能性，但只有事关两个国家或者几个大国之间，贸易战或金融战发展到极致，你死我活的程度，才会发生。然而战争发展到极致的概率也很小；

比特币占全球GDP不到千分之二，动用如此先进的算力，耗费成本，去威胁比特币，投资回报比有多高？对谁会有利？

备注：

2014年，当时著名矿机产商「烤猫」旗下掌握的Ghash.IO矿池曾达到了接近51％的哈希值，随后该矿池就发布自愿声明，承诺算力不会超过比特币总体哈希值的 39.99％，解除了大众的信任危机。

3、推演

魔高一尺，道高一丈。加密和解密就是孪生兄弟，永远相伴相随。如果当下的加密算法无法抵御量子计算的攻击，将会出现新的加密算法。2019年1月，NIST公布了 26 种可能抵抗量子计算机攻击的算法。之后，或将分叉出比特币的“抗量子计算版”，类似BCH之于BTC。

假设比特币的“抗量子计算版”称为BCQ (BitCoin of Quantum)，十年后BTC的共识人群数为3亿。分叉出来的BCQ，共识人群数从无到有，从少到多，逐渐或迅猛吸收了BTC的人群。原来持有BTC的人，他的数字资产不会一夜之间清零，会通过稳定币转移到BCQ。

再过几年后，BTC失去了流动和多种货币间媒介的价值，沦为纪念品或收藏品，但也不至于归零。然而，抗量子计算攻击的BCQ将所向披靡，称为新时代的“数字黄金”，它的生命周期相对BTC，可能长达数十年甚至百年以上，获得大得多的共识人群数，单个BCQ的价值将数十倍甚至百倍以上的增加。

当下，由于谷歌量子霸权的出现，势必影响大家（尤其是当下BTC共识人群）对于BTC的信仰，而BTC的价值的两大组成部分之一就是信仰就是大家业已形成的，历经十年而不倒的共识。预计，它会削弱一部分下一个牛市的封顶值。

4、风险

1）个人攻击的可能性仍然存在，也许因为某些极端的意图； 2）BTC分叉到BCQ的难度和可行性；

5、总结

个人仍看好未来十年内，比特币的价值上涨；Libra的横空出世和中国政府正面重视区块链的发展，使得共识人群数量成倍数地不断增加。未来几年，仍然会以较大幅度波动上升，但每次的底部都会高于前几次的底部；而且时不时的“黑天鹅”事件，都会刺激它抬到新一轮波动，例如2019年愚人节事件、Libra、2019年10月25日中国政府正面鼓励区块链。（2019年10月26日）

2023年1月5日补充：2022年12月23日BTC为16777美元，2023年1月4日为16842美元变化不大。当然，最关键的时间点，要看这篇论文被权威的期刊认可的时候。