量子計算機を使った新しい素因数分解法の提案論文を読んでみた (その2)

はじめに

こんにちは、データ＆セキュリティ研究所の山口と伊豆です。

2024年12月に中国の研究者たちが量子アニーリング計算機を使ってある条件を満たす2048ビット合成数の素因数分解に成功したという論文を発表しました。インターネット等で使用されているRSA暗号やRSA署名という暗号方式は合成数をパラメータ(公開鍵)として使用しており、この合成数の素因数分解が難しいことが安全性の根拠となっています。このため2048ビット合成数が簡単に素因数分解できてしまうとRSA暗号やRSA署名が解読されてしまい、インターネットの安全性が大きく揺らいでしまいます。本記事では本論文の提案内容を解析し、2048ビット合成数を使用するRSA暗号やRSA署名の安全性には影響がないことを説明します。

文献情報

本記事が紹介する論文の情報は以下の通りです。以下、「本論文」と呼びます。

タイトル：A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer

著者：Chao Wang, Jingjing Yu, Zhi Pei, Qidi Wang, and Chunlei Hong

論文情報：Tsinghua Science and Technology, pp.1270-1282, Volume: 30, Issue: 3, June 2025

なお本論文の正式な出版日は2025年6月ですが、2024年12月に先行公開されています。

本論文の著者と同じ研究室では2024年10月にも量子アニーリング計算機を使った素因数分解法を提案しています。内容については過去のブログ記事を参照ください。

blog.fltech.dev

論文の概要と評価

本論文は、D-Wave という量子アニーリング計算機を使ってある条件を満たす2048ビット合成数を素因数分解する手法と、実際に D-Wave を用いて10種類の2048ビット合成数を素因数分解した検証結果を報告しています。ここで「ある条件」とは2048ビット合成数が1024ビットの2つの素数の積となっており、かつ、2つの素数の下から2ビット目と3ビット目の値が異なっていることを指します (このとき2つの素数の値の差は 2 または 6 となります)。実際、検証で使用された10種類の2048ビット合成数のうち、3種類は2つの素数の差が2、残り7種類は2つの素数の差が6となっています。

なお論文のタイトルにある「RSA-2048」という表記は過去にRSA社が開催していた RSA Factoring Challenge という素因数分解コンテストで出題された合成数 RSA2048 を連想させますが、今回の検証では無関係なのでご注意下さい。一般に、ある合成数が同じビット長の2つの素数の積になっている場合、その合成数のことをRSA型合成数と呼ぶので、「RSA-2048」は「2048ビットのRSA型合成数」を意味していると解釈できます。

本論文は筆算法という(量子)アニーリング計算機向けの素因数分解法を使用しています。量子計算機による素因数分解というとショアのアルゴリズムが有名ですが、こちらは量子ゲート計算機向けであり、本論文の提案手法とは全く関係ないことにも注意が必要です。量子計算機の分類や、量子アニーリング計算機と量子ゲート計算機の違いについては過去のブログ記事を参照下さい。

本論文は、2つの素数 $p, q~(p>q)$ ) の下から2ビット目と3ビット目の値が異なっているときに、量子アニーリング計算機 D-Wave によって合成数 $N=p \times q$ が実際に素因数分解できることを検証しています。しかしRSA暗号やRSA署名においてこのような素数のペアを使うことは考えにくいです。というのも2つの素数 $p$ , $q$ の値がほぼ同じ場合、合成数 $N=p \times q$ に対してはフェルマー法という現在の計算機(古典計算機)向けの素因数分解法が有効であることが知られており、量子計算機を持ち出すまでもなく素因数分解が可能になるからです。このため、RSA暗号やRSA署名では $p$ , $q$ の差が大きくなるように選択することが多く、本論文が扱っている $p-q=2, 6$ という条件はRSA暗号・RSA署名にとっては現実性の低いケースになっています (下図参照)。

なお下位2ビット目と3ビット目の値が異なっている2つの素数 $p, q$ を生成するのは簡単です。例えば以下の2048ビットの素数 $p, q$ は下位2ビット目と3ビット目の値が異なっていて条件を満たしています。このとき4096ビットの合成数 $N=p \times q$ は提案法によって素因数分解することは可能です。従って、合成数のビット長は素因数分解における重要なパラメータですが、それだけで素因数分解の意味の大小を判断することはできず、具体的にどのような性質の合成数を素因数分解したかまで気を払う必要があると言えます。

$p= \\\ 3158424856 6211967800 6487513733 4834521522 0478129555 \\\ 6214161112 4135661703 3584762334 1717149018 5798609556 \\\ 7962349944 6239960364 2167466469 7111684418 9408220379 \\\ 8598618554 3034208382 9377165788 1340895698 4704368673 \\\ 6307677802 3759261631 1182940673 6798381606 9856817242 \\\ 4683450726 1818029516 2027893732 2301197834 0820908582 \\\ 5794100755 2332693432 5337024526 4213290421 8000592133 \\\ 0817046017 8491170626 5554895210 4550693334 1904729520 \\\ 2019261850 1776105443 0448878106 3643711453 1226807563 \\\ 5348637852 9667864096 0269168954 3064643382 2894677626 \\\ 7728546840 2294435288 4626212679 5959551859 4510049704 \\\ 4961259134 6031863061 8886053969 3563353795 5280928197 \\\ 2095040091 0159047 = q+6$

$q= \\\ 3158424856 6211967800 6487513733 4834521522 0478129555 \\\ 6214161112 4135661703 3584762334 1717149018 5798609556 \\\ 7962349944 6239960364 2167466469 7111684418 9408220379 \\\ 8598618554 3034208382 9377165788 1340895698 4704368673 \\\ 6307677802 3759261631 1182940673 6798381606 9856817242 \\\ 4683450726 1818029516 2027893732 2301197834 0820908582 \\\ 5794100755 2332693432 5337024526 4213290421 8000592133 \\\ 0817046017 8491170626 5554895210 4550693334 1904729520 \\\ 2019261850 1776105443 0448878106 3643711453 1226807563 \\\ 5348637852 9667864096 0269168954 3064643382 2894677626 \\\ 7728546840 2294435288 4626212679 5959551859 4510049704 \\\ 4961259134 6031863061 8886053969 3563353795 5280928197 \\\ 2095040091 0159041$

$N = \\\ 9975647574 9226274376 3401929215 2478747677 3282855674 \\\ 5982388666 6440843332 0776774449 7631174205 9293430550 \\\ 0586644839 3748055563 6611135464 3734657101 3182999032 \\\ 0465044079 0572171496 5316684087 2268569166 9846696996 \\\ 1562442768 0957878399 1958090306 5062318509 4904871235 \\\ 6732246748 4182256307 9110796998 3635702980 4340378514 \\\ 3914885491 3704035023 7643933941 9250091677 0401875803 \\\ 7950022300 2423691063 6640867399 3862218690 2619173986 \\\ 4801400633 9343494532 2155777351 2603028843 5819802366 \\\ 8651502183 6802723044 3639579373 8055292079 5988255749 \\\ 4952521101 0383001456 8968390673 4522135569 5370126964 \\\ 5685341465 2067588329 0837676937 2450324569 9730982521 \\\ 5333953464 4638326196 6455959998 4999316962 5419818846 \\\ 0847381060 6387705444 7576524591 6036240401 7356534674 \\\ 7265335764 3432325710 9448567256 3772877382 9957775092 \\\ 4963222195 8082965688 0828332583 4179256394 1374959022 \\\ 1007955174 2311574007 2715215319 6988911317 4486303822 \\\ 4999555253 3619748872 0470071091 7773740153 4493196190 \\\ 5608640306 7455314508 5591336585 6056188852 0468202763 \\\ 5466642742 9780129619 5280444089 6783071080 2080396465 \\\ 8890016840 9991556900 2435432416 8643401404 0989948680 \\\ 2641861934 1740728490 1473587896 9162728381 3289617775 \\\ 4473591581 1665290328 6614780126 1681972683 1610747656 \\\ 5956114733 3033034393 7811362087 4061743756 9710307653 \\\ 3655511411 2912649922 4685374993 927$

本論文の提案手法をベースにすることで、 $p-q$ が大きい場合でも素因数分解が出来るような拡張できて、RSA暗号やRSA署名で使用している合成数の素因数分解が可能になるかもしれないとの懸念を持つかもしれません。しかい本記事の後半で考察する通り、残念ながらその可能性も低いと言えます。

以上の考察により、本論文の素因数分解手法はRSA暗号・RSA署名の安全性に全く影響を与えないと結論づけることができます。

参考：特殊な合成数の利用について

本論文で提案している素因数分解法は、下位2ビット目と3ビット目が異なる2つの素数 $p,q$ を素因数にもつ特殊な合成数 $N=p \times q$ にのみ適用できる手法です。著者もこのことを触れた上で過去にもメルセンヌ合成数 [tex: N=2¹⁰³⁹-1] や [tex: N=2¹⁰⁶¹-1] を特殊数体篩法(SNFS)という素因数分解法で素因数分解する実験が行われており、特殊な合成数の素因数分解の意義を主張しています。確かにSNFSはメルセンヌ合成数などの特殊な合成数に効果のある素因数分解法ですが、素因数に関する情報は一切使っておらず、本論文で扱っている合成数とは状況がかなり異なります。一般にRSA暗号の解読(素因数分解)では素因数の情報は利用できないため、本論文のように攻撃者が素因数がある条件を満たしていることを知っているという仮定は現実性に欠けます。この意味でも提案法はRSA暗号の安全性に影響を与えないことが分かります。

技術的考察

以下では2つの素数の下位2ビット目と3ビット目が異なるという条件の導出法と, 条件の緩和方法を検討します。このため記述が専門的になることをご承知置き下さい。

筆算法の概要

(量子)アニーリング計算機は、ハミルトニアンと呼ばれる多項式の最小値を求めることに特化された計算機です。ここでハミルトニアンはバイナリ変数 (値は $0$ または $1$ ) であり、高々2次であることが必要です。筆算法は(量子)アニーリング計算機向けの素因数分解法で、乗算の筆算をもとにハミルトンを導出し、(量子)アニーリング計算機によって最小値を求めることで素因数分解を行います。

いま $l$ ビットの2つの素数 $p,q~(p>q)$ の2進展開を

$p=(p_{l-1}, p_{l-2}, ..., p_2, p_1, p_0)_2$ ,

$q=(q_{l-1}, q_{l-2},..., q_2, q_1, q_0)_2$

と表すことにします。ここで $p, q$ は $l$ ビットの素数なので、

$p_{l-1}=1$ , $p_0=1$ , $q_{l-1}=1$ , $q_0=1$

となっています。さらに $N=p \times q$ の2進展開を

$N=(n_{2l}, n_{2l-1}, ..., n_2, n_1, n_0)_2$

と表すとき、 $N=p \times q$ を計算する筆算は以下のようになります。ここで $z_{i,j}$ は $2^{i}$ の桁から $2^{j}$ の桁への繰り上がりを表すバイナリ変数です。

ここで各桁から導出される関係式を

$f_1=p_1+q_1 - n_1 - 2 z_{1,2}$

$f_2 = p_2 + p_1 q_1 + q_2 - n_2 - 2z_{2,3} - 4z_{2,4}$

$\ldots$

のようにおくと、 $f_1=f_2=\dots=0$ を満たす解から素因数分解が求められます。この解は $H= {f_1}^2 + {f_2}^2 + \dots$ の最小値を与えますので、 (量子)アニーリング計算により $H$ の最小値を与える

$p_{1}, p_{2}, ..., p_{l-2}, q_{1}, q_{2}, ..., q_{l-2}$

を求めることで素因数分解が可能となります。これが筆算法と呼ばれる素因数分解法です。なお上で定義した $H$ は一般には3次以上になりますが、適当な項 (例えば $p_1 q_1$ ) を別のバイナリ変数に置き換えることで2次以下に変換することが可能ですが、トレードオフとして変数の個数が増大します。

「ある条件」の導出

(量子)アニーリング計算では変数の個数が少ない方が効率的に解を求めることができます。そこで(量子)アニーリング計算が楽になるような $N$ に関する条件を調べます。

まず

$f_{1} = p_{1} + q_{1} - n_{1} - 2z_{1,2} = 0$

が成立する場合を考えます。 $n_{1}=0$ とおくと

$f_{1} = p_{1} + q_{1} - 2z_{1,2} = 0$

となり $z_{1,2}$ は定まりません。しかし $n_1=1$ とおくと

$f_1 = p_1 + q_1 - 1 - 2z_{1,2}=0$

となり

$z_{1,2} = 0$

が得られます。よって $n_{1}=1$ と仮定することで(量子)アニーリング計算が楽になることがわかります。このとき

$p_1 + q_1 = 1$

となっています。

なお $p, q$ の下位2ビット目だけが異なる、つまり

$p_2 = q_2, p_3 = q_3, ... ,p_{l-2}=q_{l-2}$

と仮定すると $p-q = 2$ という条件が得られます。このとき

$H=f_1^2=(p_1 + q_1 - 1)^2$

となるのですが、本論文はこのケースを検討の対象外としています。

次に

$f_{2} = p_{2} + p_1 q_{1} + q_{2} - n_{2} - 2 z_{2,3} - 4 z_{2,4} = 0$

が成立する場合を考えます。このとき $p_1 + q_1 = 1$ であることから $p_1 q_1 = 0$ であり、

$f_{2} = p_{2} + q_{2} - n_{2} - 2 z_{2,3} - 4 z_{2,4} = 0$

となっています。よって

$z_{2,4} = 0$

であり、さきほどと同じ議論により

$n_{2} = 1$

を仮定すれば $z_{2,3} = 0$ となることがわかります。このとき

$p_{2} + q_{2} = 1$

となっています。

さらに

$f_3 = p_3 + p_2 q_1 + p_1 q_2 + q_3 + 2 z_{2,3} - n_3 - 2 z_{3,4} - 4 z_{3,5} = 0$

を考えます。このとき

$z_{2,3} = z_{3,5} = 0$

なので

$f_3 = p_3 + p_2 q_1 + p_1 q_2 + q_3 - n_3 - 2 z_{3,4} = 0$

となっています。ここで

$p_{3} = q_{3}$

と仮定すると $p_3 + q_3 = 0, 2$ であり、 $n_3 = 1$ ならば $p_2 q_1 + p_1 q_2 = 1$ となり、

$p = (..., 1, 0, 1)_2, q = (..., 0, 1, 1)_2$

が得られます (このとき $p-q=2$ となっています)。ハミルトニアンは

$H = {f_1}^2 + {f_2}^2 + {f_3}^2 = (p_1 + q_1 - 1)^2 + (p_2 + q_2 - 1)^2 + (p_1 q_2 + p_2 q_1 - 1)^2$

となります。

他方で $n_3 = 0$ ならば $p_2 q_1 + p_1 q_2 = 0$ となり、

$p = (..., 1, 1, 1)_2, q = (..., 0, 0, 1)_2$

が得られます (このとき $p-q=6$ となっています)。ハミルトニアンは

$H = {f_1}^2 + {f_2}^2 + {f_3}^2 = (p_1 + q_1 - 1)^2 + (p_2 + q_2 - 1)^2 + (p_1 q_2 + p_2 q_1)^2$

となります。

このようにして2つの素数の「下位2ビット目と3ビット目が異なる」場合にハミルトニアンが簡略化できることがわかりました。

条件の緩和検討

さらなる条件を導出するにはには上のような計算を続けていく必要があります。しかしここから先は桁上がりの変数が増大してしまうため、合成数や素数に条件を課しても変数値は簡単には一意に決まりません。

われわれ富士通の研究チームは、 Digital Annealer というシミュレーティッドアニーリング計算機を用いて、筆算法によって32ビット合成数の素因数分解に成功しました。この結果から $p-q < 2^{32}$ (かつ下位32ビット目より上のビット値は全て同じ) を満たすならば今回の提案法により $N=p \times q$ の素因数分解は可能であることが予想できます。逆に考えれば $p-q > 2^{32}$ の場合の素因数分解は難しく、 RSA暗号やRSA署名で使用するような合成数に適用できないことが分かります。

また、 $p,q$ の下位2ビット目と3ビット目のような連続するビットではなく任意のビットを利用した場合が気になります。任意のビットを利用した場合、対応するハミルトニアンに共通の変数が登場しなくなるため、連続するビットを利用した場合に比べてハミルトニアンの最小値計算が難しくなり、結果として素因数分解ができにくくなります。このため任意のビットに拡張するメリットは小さいと考えられます。