一、量子計(jì)算破解RSA密碼？

2023年新年伊始，一則消息在國內(nèi)安全、區(qū)塊鏈、量子計(jì)算圈子等相關(guān)的專家微信群悄悄傳開，原始信息（如下圖）來自國外安全技術(shù)專家Bruce Schneier的個(gè)人博客www.schneier.com，Schneier被《經(jīng)濟(jì)學(xué)人》稱為“安全大師”，也是哈佛大學(xué)肯尼迪學(xué)院研究員。博客里提到：“一組中國研究人員剛剛發(fā)表了一篇論文，聲稱他們可以——盡管他們還沒有這樣做——打破2048位的RSA。這是一件值得認(rèn)真對(duì)待的事情。這可能是不正確的，但它并非明顯錯(cuò)的?！?/p>

我看到這則消息后，表示：如果是真的，這是大事件！因?yàn)檫@可能要顛覆當(dāng)前的密碼技術(shù)。

備注：RSA是一種公鑰密碼算法，它的名字由三位開發(fā)者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母組成的；RSA被廣泛用于公鑰密碼和數(shù)字簽名。

RSA也是公司名，為累計(jì)30000家客戶提供安全和數(shù)字風(fēng)險(xiǎn)管理軟件；2006年9月，RSA Security以21億美元被EMC公司收購；2022年2月，DELL公司（曾在2015年10月以670億美元收購EMC）宣布以21億美元的價(jià)格將RSA出售給私人股權(quán)投資公司Symphony Technology Group（STG）。

RSA從1991年開始每年召開RSA信息安全大會(huì)（RSA Conference，簡(jiǎn)稱RSAC），是全球安全趨勢(shì)的風(fēng)向標(biāo)。第32屆RSAC 2022在2022年6月6日已經(jīng)召開。

之后，我發(fā)現(xiàn)2022年12月29~31日，國內(nèi)的光子盒研究院，安全圈，國外的thequantuminsider.com等網(wǎng)站都報(bào)道過此事，可能沒引起很多人注意。下面摘錄光子盒在2022年12月29日的報(bào)道《清華浙大在量子計(jì)算破解RSA密碼方面取得重要突破》：

在一項(xiàng)最新研究中，清華大學(xué)龍桂魯、浙江大學(xué)王浩華等組成的團(tuán)隊(duì)創(chuàng)建了一種算法，僅用10個(gè)超導(dǎo)量子比特就實(shí)現(xiàn)了48位因式分解。

大多數(shù)專家認(rèn)為這項(xiàng)任務(wù)將需要數(shù)百萬個(gè)量子比特。該團(tuán)隊(duì)的最新實(shí)驗(yàn)表明，依靠整數(shù)因子化的公鑰密碼技術(shù)可能很快就會(huì)受到當(dāng)今原始的NISQ（含噪聲中等規(guī)模）量子計(jì)算機(jī)的攻擊。

據(jù)研究人員稱，該算法是基于經(jīng)典的Schnorr算法——使用格約化來分解整數(shù)，同時(shí)依靠量子近似優(yōu)化算法（QAOA）來優(yōu)化Schnorr算法中最耗時(shí)的部分，以提高因式分解的速度。

更多中文詳情，參見：光子盒研究院 2022-12-30?

《清華浙大在量子計(jì)算破解RSA密碼方面取得重要突破》

從arxiv網(wǎng)站

https://arxiv.org/pdf/2212.12372.pdf能看出該論文預(yù)印本于2022年12月23日上線。真希望中國人能在破解密碼上，繼山東大學(xué)王小云教授破譯MD5密碼之后，再次領(lǐng)先全球。文章的標(biāo)題和摘要如下（摘自kurtpan.pro）：

“在超導(dǎo)量子處理器上使用亞線性資源分解整數(shù)”

摘要：Shor算法對(duì)基于公鑰密碼體制的信息安全提出了嚴(yán)峻的挑戰(zhàn)。然而，要破解廣泛使用的RSA-2048方案，需要數(shù)百萬的物理量子比特，這遠(yuǎn)遠(yuǎn)超出了目前的技術(shù)能力。這里，我們通過將經(jīng)典格歸約與量子近似優(yōu)化算法 (QAOA) 相結(jié)合，報(bào)告了一種用于整數(shù)分解的通用量子算法。所需的量子比特?cái)?shù)為 O(logN/loglogN)，這在整數(shù) N 的比特長度上是亞線性的，使其成為迄今為止最節(jié)省量子比特的分解算法。我們通過 10 個(gè)超導(dǎo)量子比特將高達(dá) 48 位的整數(shù)分解（量子設(shè)備上分解的最大整數(shù)）來通過實(shí)驗(yàn)展示了該算法。我們估計(jì)，使用我們的算法挑戰(zhàn) RSA-2048 需要一個(gè)具有 372 個(gè)物理量子比特和數(shù)千深度的量子電路。我們的研究在加快當(dāng)前噪聲量子計(jì)算機(jī)的應(yīng)用方面顯示出巨大的希望，并為分解具有現(xiàn)實(shí)密碼意義的大整數(shù)鋪平了道路。

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

2023年1月4日在國外的網(wǎng)站，如論壇groups.google.com，安全博客schneier.com，社交新聞?lì)恟eddit.com開始討論這個(gè)話題。例如下圖的谷歌論壇

翻譯如下：

1)這種方法對(duì)于RSA-2048及以上版本的可行性如何？

2)一些公司已通知說，他們最早將在2025年發(fā)布1000個(gè)量子位（qubits）處理器。如果論文中的說法適用于更高的量子位，那么行業(yè)不應(yīng)該更快地采用PQC（比如CNSA套件2.0時(shí)間線）

3)這種方法可經(jīng)修改，打破橢圓曲線密碼學(xué)嗎？

4)某些更新后，本文中的方法是否可以用于對(duì)抗任何當(dāng)前已知的PQC？

備注：PQC（Post-quantum Cryptography，后量子密碼）是能夠抵抗量子計(jì)算機(jī)對(duì)現(xiàn)有密碼算法攻擊的新一代密碼算法。所謂“后”是因?yàn)榱孔佑?jì)算機(jī)的出現(xiàn)，現(xiàn)有的絕大多數(shù)公鑰密碼算法（RSA、Diffie-Hellman、橢圓曲線等）能被足夠大和穩(wěn)定的量子計(jì)算機(jī)攻破，所以可以抵抗這種攻擊的密碼算法可以在量子計(jì)算和其之后時(shí)代存活下來，所以被稱為“后”量子密碼。也有人稱之為“抗量子密碼”。PQC對(duì)應(yīng)的含義，也有另一種表述"Quantum-resistant cryptography"。

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

討論當(dāng)中，也有質(zhì)疑聲，例如markku評(píng)論：

需要注意的是，本文并沒有聲稱所提出的方法比經(jīng)典的分解方法更快。當(dāng)論文談到“資源”時(shí)，它省略了“運(yùn)行時(shí)長（running time）”；僅僅是人們所聲稱的是，量子電路（quantum circuit）非常小。

“亞線性”意味著它的量子位元可以比被分解的數(shù)要小。他的方法是一種混合的經(jīng)典量子方法；數(shù)字N必須保存在經(jīng)典計(jì)算機(jī)上。

基于非常粗略的啟發(fā)式方法，它在這個(gè)設(shè)置中似乎有一個(gè)指數(shù)級(jí)的運(yùn)行時(shí)間。所提出的方法與Shor的分解算法（它實(shí)際上運(yùn)行在多項(xiàng)式時(shí)間內(nèi)）沒有任何關(guān)系。相反，它是基于經(jīng)典的Schnorr算法（禮貌地說），這個(gè)算法是有爭(zhēng)議的。當(dāng)然，這篇論文中的實(shí)驗(yàn)分析存在嚴(yán)重缺陷，研究人員一直無法找到支持其說法的證據(jù)。Léo Ducas 有一組關(guān)于這類方法的分解的注釋：https://github.com/lducas/SchnorrGate

至于對(duì)實(shí)際PQC算法的影響，沒有跡象表明CVP（備注：最近向量問題）的漸近（指數(shù)）加速，這可能會(huì)影響基于格的系統(tǒng)。也許像“Babai優(yōu)化器”這樣的東西可以從具體的安全分析中減少一些bits。然而，這將僅僅是一個(gè)持續(xù)因素的改進(jìn)。

下面介紹一下參與論文撰寫的成員。

該團(tuán)隊(duì)除了清華大學(xué)龍桂魯教授、浙江大學(xué)王浩華教授，還有來自數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室、清華大學(xué)、浙江大學(xué)、北京量子信息科學(xué)研究院、信息工程大學(xué)和量子信息前沿科學(xué)中心的科學(xué)家。

清華大學(xué) 龍桂魯教授。龍教授1962年4月生，廣西玉林人。中共黨員。畢業(yè)于山東大學(xué)，1987年畢業(yè)于清華大學(xué)，獲博士學(xué)位。教授。現(xiàn)任清華大學(xué)物理系核物理教研室主任，兼任中科院理論物理所客座研究員、蘭州重離子加速器國家實(shí)驗(yàn)室原子核理論中心客座研究員。

如下圖是浙江大學(xué) 王光宇教授。王教授還是2022年“科學(xué)探索獎(jiǎng)”獲得者。

二、會(huì)威脅比特幣歸零嗎？

很多和數(shù)字貨幣相關(guān)的人士，可能會(huì)意識(shí)到量子計(jì)算破解密碼算法后，對(duì)于比特幣的影響。我個(gè)人覺得不會(huì)導(dǎo)致比特幣歸零，但大幅震蕩的影響可能會(huì)有。正如谷歌量子霸權(quán)消息傳來后，BTC下跌了一陣子，后來又歸于平靜。

2019年10月24日集體學(xué)習(xí)后，我在10月28日撰寫的《被誤解的區(qū)塊鏈》系列文章的第一篇的后半部分，特別討論了量子計(jì)算與比特幣的關(guān)系。全文原創(chuàng)發(fā)表于微信公眾號(hào)樂生活與愛IT，但現(xiàn)在只能通過后期同步到其他媒體的文章閱讀。用戶朋友們可通過點(diǎn)擊文末左下角“閱讀原文”跳轉(zhuǎn)。

下面將當(dāng)時(shí)的相關(guān)段落摘抄出來：

（2019年10月28日）因?yàn)閹孜慌笥训碾娫捵稍?，觸發(fā)了一些新的思考。我個(gè)人的觀點(diǎn)是：1、看好區(qū)塊鏈和比特幣的長期發(fā)展；2、不看好短期內(nèi)中國區(qū)塊鏈的發(fā)展。下面的截圖是有關(guān)量子計(jì)算對(duì)比特幣影像的邏輯推理。

最近好幾位朋友通過電話，咨詢我對(duì)區(qū)塊鏈和比特幣的看法。感謝他們的咨詢，其實(shí)在溝通過程中有時(shí)會(huì)及時(shí)觸發(fā)新的思考和觀點(diǎn)。先分享我關(guān)于量子計(jì)算對(duì)比特幣影響的觀點(diǎn)，一家之言，不構(gòu)成投資建議，僅供參考。2019年10月23日，比特幣狂降500美元（8000降到7500），我猜測(cè)大概率是因?yàn)楣雀栊Q“量子霸權(quán)”。

去年在一個(gè)微信群，曾有朋友提出量子計(jì)算對(duì)比特幣的威脅。那時(shí)候，比特幣歷經(jīng)九年而不倒。我個(gè)人也認(rèn)為在近幾十年內(nèi)，唯一的威脅可能就是量子計(jì)算了。

結(jié)合之前的討論，和最近的一些思考。關(guān)于量子計(jì)算對(duì)比特幣的威脅，我個(gè)人認(rèn)為：

1、技術(shù)

從可能性到落地需要很長的周期；

到底多長，不好說，至少5年，也許需要十多年。

2、成本

誰來利用量子計(jì)算對(duì)比特幣進(jìn)行威脅？威脅的成本有多大？

個(gè)人不太可能，如果他持有比特幣，他不會(huì)做這件事；如果他不持有，他通過這種攻擊瞬間獲益的概率也有，但難度和風(fēng)險(xiǎn)都比較大；

政府有這種可能性，但只有事關(guān)兩個(gè)國家或者幾個(gè)大國之間，貿(mào)易戰(zhàn)或金融戰(zhàn)發(fā)展到極致，你死我活的程度，才會(huì)發(fā)生。然而戰(zhàn)爭(zhēng)發(fā)展到極致的概率也很??；

比特幣占全球GDP不到千分之二，動(dòng)用如此先進(jìn)的算力，耗費(fèi)成本，去威脅比特幣，投資回報(bào)比有多高？對(duì)誰會(huì)有利？

備注：

2014年，當(dāng)時(shí)著名礦機(jī)產(chǎn)商「烤貓」旗下掌握的Ghash.IO礦池曾達(dá)到了接近51％的哈希值，隨后該礦池就發(fā)布自愿聲明，承諾算力不會(huì)超過比特幣總體哈希值的 39.99％，解除了大眾的信任危機(jī)。

3、推演

魔高一尺，道高一丈。加密和解密就是孿生兄弟，永遠(yuǎn)相伴相隨。如果當(dāng)下的加密算法無法抵御量子計(jì)算的攻擊，將會(huì)出現(xiàn)新的加密算法。2019年1月，NIST公布了 26 種可能抵抗量子計(jì)算機(jī)攻擊的算法。之后，或?qū)⒎植娉霰忍貛诺摹翱沽孔佑?jì)算版”，類似BCH之于BTC。

假設(shè)比特幣的“抗量子計(jì)算版”稱為BCQ (BitCoin of Quantum)，十年后BTC的共識(shí)人群數(shù)為3億。分叉出來的BCQ，共識(shí)人群數(shù)從無到有，從少到多，逐漸或迅猛吸收了BTC的人群。原來持有BTC的人，他的數(shù)字資產(chǎn)不會(huì)一夜之間清零，會(huì)通過穩(wěn)定幣轉(zhuǎn)移到BCQ。

再過幾年后，BTC失去了流動(dòng)和多種貨幣間媒介的價(jià)值，淪為紀(jì)念品或收藏品，但也不至于歸零。然而，抗量子計(jì)算攻擊的BCQ將所向披靡，稱為新時(shí)代的“數(shù)字黃金”，它的生命周期相對(duì)BTC，可能長達(dá)數(shù)十年甚至百年以上，獲得大得多的共識(shí)人群數(shù)，單個(gè)BCQ的價(jià)值將數(shù)十倍甚至百倍以上的增加。

當(dāng)下，由于谷歌量子霸權(quán)的出現(xiàn)，勢(shì)必影響大家（尤其是當(dāng)下BTC共識(shí)人群）對(duì)于BTC的信仰，而BTC的價(jià)值的兩大組成部分之一就是信仰就是大家業(yè)已形成的，歷經(jīng)十年而不倒的共識(shí)。預(yù)計(jì)，它會(huì)削弱一部分下一個(gè)牛市的封頂值。

4、風(fēng)險(xiǎn)

1）個(gè)人攻擊的可能性仍然存在，也許因?yàn)槟承O端的意圖；? 2）BTC分叉到BCQ的難度和可行性；

5、總結(jié)

個(gè)人仍看好未來十年內(nèi)，比特幣的價(jià)值上漲；Libra的橫空出世和中國政府正面重視區(qū)塊鏈的發(fā)展，使得共識(shí)人群數(shù)量成倍數(shù)地不斷增加。未來幾年，仍然會(huì)以較大幅度波動(dòng)上升，但每次的底部都會(huì)高于前幾次的底部；而且時(shí)不時(shí)的“黑天鵝”事件，都會(huì)刺激它抬到新一輪波動(dòng)，例如2019年愚人節(jié)事件、Libra、2019年10月25日中國政府正面鼓勵(lì)區(qū)塊鏈。（2019年10月26日）

2023年1月5日補(bǔ)充：2022年12月23日BTC為16777美元，2023年1月4日為16842美元變化不大。當(dāng)然，最關(guān)鍵的時(shí)間點(diǎn)，要看這篇論文被權(quán)威的期刊認(rèn)可的時(shí)候。

索引和擴(kuò)展閱讀：

1、論文預(yù)印本網(wǎng)址

Factoring integers with sublinear resources on a superconducting quantum processor

https://arxiv.org/pdf/2212.12372.pdf

2、Bruce Schneier的個(gè)人博客之報(bào)道

Breaking RSA with a Quantum Computer

https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html#comments

3、博客報(bào)道的中文翻譯

Bruce Schneier：用量子計(jì)算機(jī)破解RSA

https://crypto.kurtpan.pro/quantum-rsa

4、龍桂魯 清華網(wǎng)站介紹

https://www.phys.tsinghua.edu.cn/info/1098/4210.htm

5、王浩華 浙大網(wǎng)站介紹

https://person.zju.edu.cn/0010051/

6、博主Bruce Schneier/布魯斯·施耐爾（美國計(jì)算機(jī)科學(xué)家、密碼學(xué)家、作家）的介紹

https://www.forwardpathway.com/91022

7、知乎《量子算法剖析: 零基礎(chǔ)搞懂Shor量子算法推演》

https://zhuanlan.zhihu.com/p/106923175

8、光子盒研究院 2022-12-30 《清華浙大在量子計(jì)算破解RSA密碼方面取得重要突破》

https://mp.weixin.qq.com/s/Mqz2A_fwle-QBpU55gGVIQ

9、《清華浙大在量子計(jì)算破解RSA密碼方面取得重要突破》

https://quantumchina.com/newsinfo/4841183.html?templateId=520429

10、谷歌網(wǎng)上論壇:? Paper claims to break RSA-2048 with only 372 physical quibits

https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/AkfdRQS4yoY

11、2022-12-29 , The Quantum Insider ：Researchers Close in on Using a Quantum Computer to Crack Common Cryptographic Scheme

https://thequantuminsider.com/2022/12/29/researchers-close-in-on-using-a-quantum-computer-to-crack-common-cryptographic-scheme/

10、2020-12-7 , Chinese Breakthrough in Quantum Computing a Warning for Security Teams

https://threatpost.com/chinese-quantum-computing-warning-security/161935/

11、2019-5-30 , How a quantum computer could break 2048-bit RSA encryption in 8 hours

https://www.technologyreview.com/2019/05/30/65724/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/

12、2020-05-15? 黑谷量子《未來的量子計(jì)算機(jī)將在8小時(shí)內(nèi)破解2048位RSA加密》

https://baijiahao.baidu.com/s?id=1666744255648037063

13、Bruce Schneier is an internationally renowned security technologist, called a "security guru" by The Economist.?

https://www.belfercenter.org/person/bruce-schneier

14、預(yù)告：1月8日晚8點(diǎn)，國內(nèi)外NFT回顧及趨勢(shì)

《元宇宙沙龍第1期講稿下載& 預(yù)約第2期 2022年國內(nèi)外NFT回顧及趨勢(shì)》

點(diǎn)擊左下角“閱讀原文”，可跳轉(zhuǎn)至《被誤解的區(qū)塊鏈》

本文使用 文章同步助手 同步