無論是微信聊天還是網(wǎng)上購物，密碼都在保護(hù)著我們的財產(chǎn)與隱私安全。這種精巧而復(fù)雜的數(shù)學(xué)算法是現(xiàn)代信息社會的安全基石，但量子計算的迅猛發(fā)展正讓這一切經(jīng)受挑戰(zhàn)。
密碼
現(xiàn)代社會的安全基石
小到個人通訊，大到機(jī)要信息傳輸，都需要嚴(yán)格的密碼保護(hù)。目前，常用的RSA加密算法基于一個簡單的數(shù)論事實(shí)：即將兩個大素數(shù)相乘十分容易，但是想要對其乘積進(jìn)行質(zhì)因數(shù)分解卻極其困難，因此可以將乘積公開作為加密密鑰。
圖片來自網(wǎng)絡(luò)
例如在一套RSA算法下，給定一對3*5=15相關(guān)的公私密鑰，選定其中一個作為私鑰由用戶自己保存，另一個密鑰作為公鑰公開。
當(dāng)把3和5更換為2048位的素數(shù)A和B時，用C表示A和B的乘積。那么驗(yàn)證A乘以B是否等于C，是一件計算起來比較簡單的事，即檢驗(yàn)用戶輸入密鑰正確性輕而易舉；但是要從C倒推回A和B，卻及其困難，單個經(jīng)典計算機(jī)所需運(yùn)算時間超過10^14年，所以以此密鑰進(jìn)行的加密幾乎無法被經(jīng)典計算破解。
此外，ECC算法也是目前主流的非對稱加密算法，通常被用于密匙協(xié)商和數(shù)字簽名。其特點(diǎn)為加密復(fù)雜，基于橢圓曲線有限域進(jìn)行運(yùn)算，因而難以被針對整數(shù)域加密的常規(guī)算法破解。
相較于RSA算法，ECC算法優(yōu)勢是可以使用更短的密鑰，得到與RSA算法相當(dāng)或更高的安全性。
圖片來自網(wǎng)絡(luò)
基于這種極高破解難度帶來的強(qiáng)大安全性，RSA和ECC算法成為了現(xiàn)代電子信息加密的基礎(chǔ)。這兩種算法被廣泛應(yīng)用于智能卡密鑰、二代身份證、虛擬貨幣、匿名網(wǎng)絡(luò)、數(shù)字證書和通信保密協(xié)議等硬件和軟件領(lǐng)域中，對相關(guān)的金融、互聯(lián)網(wǎng)等行業(yè)的信息安全極為關(guān)鍵。
量子計算
正嚴(yán)重威脅信息安全
在經(jīng)典計算時代，這種精巧而復(fù)雜的數(shù)學(xué)算法能夠抵抗絕大多數(shù)密碼攻擊。但量子計算以及相應(yīng)量子算法的出現(xiàn)讓RSA加密在源頭上出現(xiàn)了危機(jī)。
Peter Shor提出了Shor算法。圖片來自網(wǎng)絡(luò)
量子計算基于量子疊加特性，“量子比特”可以同時是0和1，其計算效率遠(yuǎn)遠(yuǎn)高于經(jīng)典計算機(jī)。
1994年，美國科學(xué)家Peter Shor提出了著名的Shor算法，在理論上展示了一個足夠強(qiáng)大的量子計算機(jī)能將質(zhì)因數(shù)分解的時間復(fù)雜性降到多項(xiàng)式時間內(nèi)。
Shor算法的出現(xiàn)，意味著RSA加密在理論上已經(jīng)不再安全。隨著量子計算軟硬件技術(shù)飛速發(fā)展，現(xiàn)代密碼體系的崩潰也不再是理論上的風(fēng)險。
密碼量子破譯
研究進(jìn)展
1997年，Peter Shor進(jìn)一步提出了基于量子計算的大數(shù)質(zhì)因子分解算法可應(yīng)用于質(zhì)因子分解和離散對數(shù)問題，而橢圓曲線加密（ECC）算法的底層實(shí)質(zhì)上也是一種離散對數(shù)問題（DLP）。這就使得另一種主流加密方案也出現(xiàn)了危機(jī)。
2016年，美國麻省理工學(xué)院與奧地利因斯布魯克大學(xué)的研究者，第一次以可擴(kuò)展的方式在量子計算機(jī)中實(shí)現(xiàn)了Shor算法。
2017年到2019年，瑞士皇家理工學(xué)院的Eker和Hast d先后發(fā)表了關(guān)于Shor算法的改進(jìn)文章，提出了專注于DLP的改進(jìn)量子算法。該算法大大降低了Shor算法的復(fù)雜度。
2019年12月，Eker與IBM合作發(fā)表了關(guān)于目前主流使用的最長的2048位RSA密碼的量子破譯算法理論評估文章，指出使用約2000萬個噪聲量子比特可以在8小時之內(nèi)完成相關(guān)破譯工作。
2021年3月，巴黎薩克雷大學(xué)和吉夫續(xù)爾伊凡特理論物理研究所的相關(guān)研究人員發(fā)表了關(guān)于使用13436個物理量子比特在177天內(nèi)完成2048位RSA密碼破譯的理論文獻(xiàn)。
2021年4月，本源量子公司與國內(nèi)多家金融機(jī)構(gòu)以及相關(guān)合作伙伴發(fā)起了量子破密算法的研究合作，并于近日取得重要進(jìn)展，減少了運(yùn)行算法所需的量子比特數(shù)量。
本源量子金融行業(yè)生態(tài)應(yīng)用聯(lián)盟
量子計算
破密原理
量子計算機(jī)如何破解RSA密碼呢？我們以Shor算法破解RSA加密為案例進(jìn)行講解。
RSA加密的核心環(huán)節(jié)是由兩個質(zhì)數(shù)相乘得到大數(shù)的過程，正向簡單而逆向極其困難。因此，如何由給定大數(shù)分解得到兩個質(zhì)因數(shù)是破解RSA加密的關(guān)鍵。
1994年P(guān)eter Shor提出了一種破解思路，將原質(zhì)因數(shù)分解問題切換為量子計算機(jī)便于求解的離散對數(shù)問題。
