中国の研究者が量子コンピューターでRSA暗号の解読手法を構築

素因数分解の困難さを安全性の根拠とした暗号「RSA暗号」について、量子コンピューターを使用することで解読手法の構築に至ったと上海大学のワン・チャオ氏らが発表しました。

基于 D-Wave Advantage 的量子退火公钥密码 攻击算法研究
(PDFファイル)http://cjc.ict.ac.cn/online/onlinepaper/wc-202458160402.pdf

Chinese researchers break RSA encryption with a quantum computer | CSO Online
https://www.csoonline.com/article/3562701/chinese-researchers-break-rsa-encryption-with-a-quantum-computer.html

Chinese Scientists Report Using Quantum Computer to Hack Military-grade Encryption
https://thequantuminsider.com/2024/10/11/chinese-scientists-report-using-quantum-computer-to-hack-military-grade-encryption/

中国の学術誌「Chinese Journal of Computers」に掲載された査読付き論文によると、ワン氏らはカナダに拠点を置くD-Wave Systems社の量子コンピューター「D-Wave Advantage」を使用し、古典的アルゴリズムや量子アニーリングなどの手法を統合することで、いくつかの暗号アルゴリズムに対するシステムの最適化に成功したとのこと。

量子コンピューターは既存の暗号をいずれ解読する可能性があると考えられていましたが、今回の研究により、そのような脅威が発生する時期が予想よりもはるかに早く訪れる可能性があることが示唆されました。

専門家によればワン氏らの研究の意義は「量子アニーリング・アルゴリズムと従来の数学的アプローチを組み合わせ、新しい計算アーキテクチャを作り上げ、暗号化問題を量子コンピューターに適した二項最適化問題として設定したこと」にあるといいます。

ワン氏らが対象としたアルゴリズムは軍事および金融の暗号化プロトコルに広く導入されているシステムの基礎となっているものであり、中には「現在利用できる最も安全なもの」と考えられているものもありましたが、ワン氏らは「量子コンピュータが近いうちに安全性を脅かす可能性があることを示唆している」と指摘しています。

ワン氏らが研究対象としたのは2種類の量子アニーリングに基づくRSA公開鍵攻撃アルゴリズムです。1つ目は、暗号攻撃の数学的手法を組み合わせて最適化問題または指数空間探索問題に変換し、イジングモデルまたはQUBOモデルといった既存の手法による解決を可能にするモデルです。このモデルをD-Wave Advantageに適用したところ、22ビットのRSA整数である2269753の因数分解に成功したとのこと。これは既存の実験指数を大きく上回り、イジングモデルに関係する係数の範囲を80～84％縮小し、分解の成功率を大幅に向上させたといいます。

2つ目は量子アニーリングアルゴリズム融合暗号攻撃と呼ばれるもの。ワン氏らは量子アニーリングと古典的アルゴリズムを組み合わせることで近似最近傍アルゴリズムを最適化し、10個の論理量子ビットと16個の物理量子ビットを用いて、845546611823483=40052303×21111061という50ビットの整数の因数分解に成功しました。ワン氏らは4～50ビットの範囲内でRSA整数分解をランダムに選択するというアプローチを行いましたが、これはアルゴリズムの普遍性と拡張性を証明する実証実験の意味合いも大きかったとのことです。

記事作成時点で使われている2048ビット以上の鍵を破るには大きな技術的ブレイクスルーが求められますが、ワン氏らの手法は将来的に64ビット以上のRSA整数の因数分解にも応用できる可能性があるため、ワン氏らは「現在暗号化されているデータであっても、将来的に解読可能になることを見越して盗まれることがあり、こうしたデータは危険にさらされる可能性があります。量子攻撃が現実のものとなるにつれ、組織はデータの安全性をどのように確保するか再考する必要があります」と警告しました。