自主科技| 中國研究混合算法 加速破解公開加密

PeterShor
1994年麻省理工應用數學家peter shor提出演算法可在量子電腦破解RSA加密,令舉世震驚,被認為是比千年蟲更嚴重的危機,亦令量子運算頓時炙手可熱。

[自主科技]

對於一般人,量子運算遙不可及,量子運算可解決傳統電腦不能解決的重大問題,例如發現新物質、解決糧食和能源需求,量子運算平行運算可更快找到答案。

不過最多人關心是量子電腦可快速作質因數分解,而互聯網加密,甚至加密貨幣,都基於同樣的加密原理。最早提出製作量子電腦是物理學家費曼(Richard Feynman),但是提出以量子電腦破解互聯網加密,則是麻省理工數學家秀爾(Peter Shor)。

1994年,秀爾在演算法證明了以如果有足夠快的量子電腦,可破解基於公開密鑰加密的算法(例如RSA加密演算法),這個發現引起舉世關注,甚至美國國家安全局關心,因為互聯網、以至政府和軍事加密,均基於公開密鑰加密。

2022年12月下旬,中國研究人員在arXiv網站發表了論文,聲稱發現了改良算法,估計不久將來,以372個量子比特(Qubit)量子電腦,就可破解2048-bit的RSA加密技術,引起多國的關注。

混合算法加速破解

量子電腦是通過「量子門」(Quantum gate)操縱Qubit執行計算。Qubit與傳統電腦的(Bit)比特有本質上區別,Qubit不僅可代表「0」或「1」,還可表示成任意疊加。相互糾纏的2個Qubit,電腦空間維度的增長,提供了強勁的平行計算性能。

發表上述研究的中國研究人員,來自多家著名大學及研究中心;包括河南數學工程與先進計算國家重點實驗室、清華大學、浙江大學、北京量子資訊科學研究院、資訊工程大學和量子資訊前沿科學中心。論文刊登在論文網站arXiv上,不過研究人員並沒有足夠先進量子電腦設備,只是以上述算法以透過10個Qubit量子電腦,破解48-bit質因數分解。

今次並非首次有人指RSA加密法,短期內有被破解之虞;2022年德國數學家Claus-Peter Schnorr就提出算法,試圖以傳統電腦破解RSA加密,後來功敗垂成,證明難以加速至分解大質因數。

中國研究人員改良了Schnorr算法,以量子近似優化演算法(QAOA)加速Schnorr算法最耗時部分,以提高分解速度,輔以傳統電腦處理大質因數分解。

但團隊指QAOA收斂性仍不明確,難以預測372個Qubit的量子運算的表現,算法加速性能還不清楚,不能斷言RSA 2048加密已被破解。

能否加速莫衷一是

相對而言,秀爾算法乃須要數以萬計的Qubit,才能破解48-bit質因數,一般以為RSA加密法仍屬安全。Schnorr算法能否加快了破解進呈?美國金融時報訪問了秀爾,他以為論文內容基本上正確,但無法說出此算法,多久才能獲正確答案,也許要上百萬年才能算出答案。

上述混合算法以量子運算,承擔耗時部分,再輔以傳統電腦,但團隊沒372個Qubit量子電腦,無法實證是否可行,業界人士則指多算法難以實現。

今年,IBM會發表433個qubit的Osprey,預計2025年推出4000個qubit量子電腦,如果上述論文可行,RSA加密法報廢,可能會較預期為早。

去年,美國拜登政府宣佈過渡至後量子加密法,預計超過10年時間才完成轉變,以防美國國家機密遭人竊看,估計耗資以百億美元,預計2035年前完成,問題是否趕及算法和量子電腦的出現。美國《紐約客》雜誌訪問美國政府負責後量子加密法的國家標準與技術研究院(NIST)數學家Dustin Moody指,各國政府正蒐集大量其他國家的加密數據,期望一俟量子運算成熟就解密有關文件。有專家甚至估計,可執行Shor算法的量子電腦,可能早至2029年就會面世。

Leave a Reply

Your email address will not be published. Required fields are marked *