【打破砂鍋】量子電腦已成功破解 AES 加密？真的假的？

量子電腦正對當代密碼學造成嚴重威脅，現在大家每天都在用，讓電子交易及身分識別得以實現的加密與數位簽章技術，將會在量子電腦成熟後瞬間瓦解。(如果你對此事還一無所悉，推薦以下這兩篇)

• 閒聊 - Y2Q 倒數與 Q-Day，當代資訊安全防線即將崩潰
• PQC 筆記1 - 靠近一點看量子電腦對當代密碼學的威脅

不過，這裡有個重點。量子電腦對當代密碼學所造成的威脅，精確一點來說指的是現行「部分」密碼學演算法在量子電腦技術成熟後會變得不堪一擊。如先前文章所提，量子電腦並非無堅不摧，對 RSA、DSA、ECDSA 這類公開金鑰演算法較具威脅，對 SHA 雜湊及 AES 加解密的影響有限。至少在人類現有的知識領域，只要長度夠長，SHA 及 AES 還是十分安全的。

今天看到兩則新聞，一句話驚醒我夢中人，嚇得我屁滾尿流失了魂...

花惹發! 量子電腦技術已經進步到能破解 AES256？這完全巔覆我對後量子電腦密碼學(PQC)的理解，我的認知錯了？還是新聞又在亂寫？

既然是學術研究就好辦，真相都在論文裡，找到原始論文，雖然看不懂其中的數學咒語，但摘要就有答案：

D-Wave 专用量子计算机的原理量子退火凭借独特的量子隧穿效应可跳出传统智能算法极易陷入的局部极值，可视为一类具有全局寻优能力的人工智能算法。本文研究了两类基于量子退火的 RSA 公钥密码攻击算法（分解大整数 N=PQ）：一是将密码攻击数学方法转为组合优化问题或指数级空间搜索问题，通过 Ising 模型或 QUBO 模型求解，提出了乘法表的高位优化模型，建立新的降维公式，使用 D-Wave Advantage 分解了 200 万整数 2269753。大幅度超过普渡大学、Lockheed Martin 和富士通等实验指标，且 Ising 模型系数 α 范围缩小了 84%，系数 β 范围缩小了 80%，极大地提高了分解成功率，这是一类完全基于 D-Wave 量子计算机的攻击算法；二是基于量子退火算法融合密码攻击数学方法优化密码部件的攻击，采用量子退火优化 CVP 问题求解，通过量子隧穿效应获得比 Babai 算法更近的向量，提高了 CVP 问题中光滑对的搜索效率，在 D-Wave Advantage 上实现首次 50 比特 RSA 整数分解。实验表明，在通用量子计算机器件进展缓慢的情况下，D-Wave 表现出更好的现实攻击能力，且量子退火不存在 NISQ 量子计算机 VQA 算法的致命缺陷——贫瘠高原问题：算法会无法收敛且无法扩展到大规模攻击。

從頭到尾論文就只提到 RSA，用 D-Wave Adavnage 量子電腦完成 50 bit RSA 整數分解，一則距現今主流的 RSA 2048 bit 仍有相當距離，二來完全沒講到 AES 呀~

進一步追查，這幾篇中文報導應都翻譯自 tom's HARDWARE 這篇：Chinese scientists use quantum computers to crack military-grade encryption — quantum attack poses a "real and substantial threat" to RSA and AES 其中有段確實提到 AES-256：

The second proposed attack incorporates classical computing-based cryptographic technology, such as the Schnorr signature algorithm and the Babai rounding technique, layered with a quantum annealing algorithm, to work “beyond the reach of traditional computing methods.”Applying the above techniques, with the help of the D-Wave quantum computer, the team led by Wang Chao of Shanghai University claim to have successfully breached the widely used SPN structure. Wang refused to give further details to the SCMP due to the sensitivity of this topic. However, the direction of travel means that AES-256 and other ‘military grade’ encryption algorithms are closer than ever before to being cracked. Moreover, quantum-reliant and quantum-aided techniques, as discussed in the paper, quantum-reliant and quantum-aided techniques could bring forward the day when current military and enterprise-grade encryption tech is good enough.

大意是研究團隊聲稱找到新方法(結合 Schnorr、Babai、量子電腦退火演算法)成功破解 SPN 結構(Substitution-Permutation Network，替換置換網絡，AES 加密過程會用它混淆擴散資料達到加密目的)，但拒絕向南華早報(SCMP)透露更多細節，而且研究人員也只提了 SPN，並未宣稱已成功破解 AES。至於文章提到 AES-256 的意思應是「此一發展方向意味著離成功破解 AES256 及其他軍事級加密比以往又更推進了一點(Closer)」。AES 可被量子電腦破解一事，一來研究團隊沒這麼說，二則沒有技術細節，真確性無從驗證，從科學角度不應採信；而 tom's HAREWARE 關於破解 AES-256 一事的評論僅是「接近一點」，更是與「成功破解」天差地遠。

【結論】目前並無量子電腦可破解 AES 的可信理論及證據，新聞亂寫。