2023-01-23 富士通株式会社
富士通は、量子コンピュータによる既存暗号解読の懸念に対し、自社開発の39量子ビットの量子コンピュータシミュレータ（以下、量子シミュレータ）を活用し、現在普及しているRSA暗号（注1）の安全性を定量的に評価する実験を2023年1月に実施し、安全性評価に成功しました。
実験では、RSA暗号を解読する量子アルゴリズムであるショアのアルゴリズム（注2）を量子シミュレータ上に実装し、必要なリソースを定量的に評価した結果、現在一般的な鍵長（注3）2,048ビットのRSA暗号の解読には、およそ1万の量子ビットと、およそ2兆2,300億の量子ゲートもの膨大な規模を有する誤り耐性量子コンピュータが必要なことが判明しました。これは、試算すると約104日の間、量子ビットを誤りなく保持する必要があり、現状、このような大規模かつ長時間にわたり安定稼働する量子コンピュータの実現は短期的には困難であることから、RSA暗号がショアのアルゴリズムに対して安全であることが定量的に証明できました。
富士通は今後、量子コンピュータが暗号の安全性にもたらす影響を継続的に調査するとともに、2023年度第1四半期までに量子シミュレータを40量子ビットまで拡張するほか、材料分野などでの活用を見据えて、国立研究開発法人理化学研究所（注4）様の協力のもと、2023年度中に64量子ビットの超伝導量子コンピュータの実現を目指します。
富士通は、本成果の一部を、2023年1月24日（火曜日）から1月27日（金曜日）まで福岡県北九州市およびオンラインにて開催される「2023年 暗号と情報セキュリティシンポジウム（SCIS2023）」にて発表します。
背景
インターネットにおける標準暗号の一つであるRSA暗号は、データの秘匿性や完全性を保証する技術として、オンラインショッピングにおけるクレジットカード情報の送受信や、SNSにおけるメッセージ交換の際など、世界中で広く利用されています。RSA暗号が鍵として使用する巨大な合成数には素因数分解が困難な特性があり、現在のコンピュータによる素因数分解記録が829ビット（注5）であることから、将来の計算能力の向上などを考慮して、鍵長2,048ビットのRSA暗号の利用が推奨されています。
一方で、理想的な量子コンピュータ（注6）を用いた場合、巨大な合成数であっても容易に素因数分解が可能なことが知られており、長期的にはRSA暗号から耐量子計算機暗号などの代替技術への移行が必要とされています。しかし、2,048ビットの合成数を実際に素因数分解する量子コンピュータについては、実験事例が少ないなどの理由から計算リソースの見積もりが難しく、代替技術への移行時期の明確化も困難でした。
量子シミュレータを用いたRSA暗号の安全性評価について
上記の課題に対し、当社は、2022年9月に開発した39量子ビットの量子シミュレータを用いて、RSA暗号の安全性を確認するため、素因数分解の実験を行いました。
実験では、入力された合成数を素因数分解する量子回路を生成する汎用的なプログラムをショアのアルゴリズムを用いて実装し、量子シミュレータ上において素因数分解の実験を行った結果、9ビットのRSA型合成数（2つの異なる奇素数）であるN=15からN=511までの96個の素因数分解に成功し、汎用的なプログラムが正しい量子回路を生成できることを確認しました。
さらに、上記の汎用的なプログラムを用いて、10ビットから25ビットのいくつかの合成数を素因数分解する量子回路を実際に生成し、その計算リソースから2,048ビット合成数の素因数分解に必要な量子回路の計算リソースを見積もった結果、2,048ビットの合成数を素因数分解するにはおよそ1万量子ビットに加え、ゲート数がおよそ2兆2,300億、深さ（注7）がおよそ1兆8,000億の量子回路が必要なことが判明しました。これは、試算すると約104日の間、量子ビットを誤りなく保持する必要があり、現時点では、これほど大規模かつ長時間にわたり安定稼働する量子コンピュータを短期的に実現することは困難であることから、RSA暗号がショアのアルゴリズムに対して安全であると定量的に証明できました。
なお、本実験では、スーパーコンピュータ「富岳」（注8）のCPU「A64FX」の高速性と当社の大規模並列計算技術を活かした、世界最速レベルの量子コンピュータシミュレータシステムを使用しました。「A64FX」を搭載した512ノードの「FUJITSU Supercomputer PRIMEHPC FX700」で構成されたクラスタシステムに加え、新規に開発した量子ビットの状態情報の再配置を自動で効率的に実行する技術を使用することで、64ノードで再配置を行わない場合と比較して100倍以上の高速化を達成し、従来16時間を要していたN=253の素因数分解を463秒で実行しました。
商標について
記載されている製品名などの固有名詞は、各社の商標または登録商標です。
注釈
注1 RSA暗号：
開発者の Rivest、Shamir、Adleman の頭文字から命名されている暗号システムで、暗号化を行う際の鍵を公開し、復号化には秘密鍵を使用する方式。暗号鍵を公開しても、素因数分解の困難性から、秘密鍵を持ったもののみが正しく情報を受け取ることができる。
注2 ショアのアルゴリズム：
米国の理論計算機科学者、数学者のピーター・ショアが1994年に考案した、整数の素因数分解を高速に実行可能な量子アルゴリズム。
注3 鍵長：
公開鍵、暗号鍵の長さ。RSA暗号では、使用する合成数のビット長が鍵長となる。RSA暗号を使用する場合には、鍵長を2,048ビット以上に設定することが推奨されている。
注4 国立研究開発法人理化学研究所：
本部 埼玉県和光市、理事長 五神 真。
注5 現在のコンピュータによる素因数分解記録が829ビット：
出典 [Cado-nfs-discuss] Factorization of RSA-250 (archive.org)
注6 理想的な量子コンピュータ：
量子ビットのノイズや量子ゲート数の上限値などの制約がない量子コンピュータのこと。理論的な解析を行う際に利用される。
注7 深さ：
量子回路において、量子計算を行うために必要なステップ数のこと。
注8 スーパーコンピュータ「富岳」：
スーパーコンピュータ「京」の後継機として国立研究開発法人理化学研究所様と当社が共同で開発し、2021年3月から共用開始された計算機。2020年6月から2021年11月にかけて世界のスーパーコンピュータに関するランキングの主要4部門において4期連続で1位を獲得するなど、世界トップクラスの性能を持つ。
本件に関するお問い合わせ
富士通研究本部 データ＆セキュリティ研究所
