PR
全4299文字

情報の改ざんや漏洩を防ぐ暗号技術に新たな脅威が浮上した。量子コンピューターの開発加速だ。計算能力が上がれば、短時間で暗号を解読できてしまう恐れがある。一方で、近い将来に暗号を解読できるとの主張には懐疑的な見方もある。量子コンピューターは現在の暗号を無力にするのか。その真偽と対策方法に迫った。

(写真提供:米グーグル、米IBM、イメージ写真:Getty Images)
(写真提供:米グーグル、米IBM、イメージ写真:Getty Images)

 2019年10月23日、代表的な仮想通貨(暗号資産)であるビットコイン(Bitcoin)の価格が急落した。米グーグルは同日、量子コンピューターが現行方式のコンピューターでは到達し得ない性能を持つことを指す「量子超越性」を実証したと発表していた。

 ビットコインは暗号技術で取引記録の正しさを保証している。量子コンピューターで暗号が解読されれば記録の改ざんが容易になり、不正送金につながるのではないか―― 。この連想が売り材料の1つになったとみられる。

 これまで暗号技術はスーパーコンピューター(スパコン)の性能を基準に解読のリスクを評価し、強度を決めてきた。SSL/TLS通信や電子証明書などで広く使われている2048ビットのRSA暗号は、現在の最高性能のスパコンを使っても解読に1億年以上かかると試算されている。量子コンピューターの開発が進めば、現在の暗号は本当に解読できてしまうのだろうか。

素因数分解の難しさで安全を担保

 現在普及している暗号技術には大別して2つの方式がある。1つの鍵データで情報を暗号化・復元する共通鍵方式と、データの暗号化と復元用で別の鍵を使う公開鍵方式である。

 共通鍵方式は無線LANなどに使われるAESが代表例だ。公開鍵方式にはRSA暗号のほか、ビットコインで使われている楕円曲線暗号がある。インターネットの安全利用に欠かせないSSL/TLS通信は共通鍵のAESと公開鍵のRSA暗号を組み合わせている。

 2つの方式ともに量子コンピューターで解読のリスクは高まるが、「特にリスクを考慮すべきなのがRSA暗号と楕円曲線暗号」(東京大学大学院情報理工学系研究科の高木剛教授)だ。量子コンピューターで効率的に暗号鍵を割り出せるアルゴリズムが考案されているからである。

 公開鍵暗号方式は計算が難しい数学の問題を使う。例えばRSA暗号で用いるのは大きな整数の素因数分解である。大きな素数同士をかけ算して合成数を算出するのは容易だが、合成数を素因数分解して素数を算出するには膨大な計算量が必要だ。この計算の難しさで暗号の安全性を保証する。

 現在の世界最高性能のスパコンを使えば鍵長1024ビット(10進数で308桁)のRSA暗号を1年未満で解読できる。だが現行のコンピューターを前提とする限り、RSA暗号自体の信頼性は揺るがない。鍵に使う整数の桁数を増やすことで、素因数分解の計算量を飛躍的に増やせるためだ。鍵長を2倍の2048ビット(同617桁)に増やせば、効率的なアルゴリズムでも計算量が100億(10の10乗)倍程度に増える。既にRSA暗号は解読のリスクを考慮して、2010年から2048ビットの鍵長の利用が推奨されている。

 ところが、実用的な量子コンピューターが登場すると事情が変わる。グーグルやIBMが開発を進める量子ゲート型のコンピューターでは「ショアのアルゴリズム」と呼ぶ効率的な素因数分解の計算手法を使える。計算量を大きく減らせるうえに、公開鍵のビット長を増やしても必要な計算時間があまり増えないのが特徴だ。例えば、RSA暗号の鍵ビット長を1024ビットから2048ビットに増やしても「計算時間の増加は理論上で8倍」(東京大学の高木教授)にとどまる。

図 RSA暗号方式と量子コンピューターによる解読リスク
図 RSA暗号方式と量子コンピューターによる解読リスク
鍵のビット長を増やしても安心できない
[画像のクリックで拡大表示]

この記事は有料会員限定です

「日経コンピュータ」定期購読者もログインしてお読みいただけます。

日経クロステック有料会員になると…

専門雑誌8誌の記事が読み放題
注目テーマのデジタルムックが読める
雑誌PDFを月100pダウンロード

有料会員と登録会員の違い