【ITニュース解説】Why is ECDSA not quantum-resistant?

今日のデジタル社会において、データ通信の安全性は極めて重要だ。私たちがインターネットバンキングで送金したり、オンラインショッピングで買い物をしたり、あるいはスマートフォンのロックを解除したりする際に、背後で情報を守っているのが暗号技術である。その中でも「ECDSA（Elliptic Curve Digital Signature Algorithm）」は、特に電子署名という形で広く使われている。これは、あるデータが確かに特定の発信者から送られたものであり、途中で改ざんされていないことを保証するための技術で、ビットコインをはじめとする多くのブロックチェーン技術の根幹を支えている。しかし、この強固に見えるECDSAが、やがて登場するとされる「量子コンピュータ」の前には無力になる可能性があるという問題が、いま注目されている。

まず、ECDSAがどのように安全性を保っているのかを理解しよう。ECDSAは公開鍵暗号というカテゴリーに属する。公開鍵暗号では、誰にでも公開できる「公開鍵」と、本人だけが持つ「秘密鍵」のペアを使う。例えば、電子署名の場合、メッセージの送信者は秘密鍵を使ってメッセージに署名を作成し、その署名とメッセージを公開鍵と一緒に受信者に送る。受信者は、送信者の公開鍵を使ってその署名が正しいか、メッセージが改ざんされていないかを確認する。この仕組みの安全性が保たれるのは、公開鍵から秘密鍵を特定することが、現在のコンピュータでは極めて困難な数学的問題に基づいているからだ。

ECDSAが利用する数学的な困難性は「楕円曲線上の離散対数問題（ECDLP）」と呼ばれる。これは、楕円曲線という特定の幾何学的な図形上の点で定義される問題で、ある公開された点Pと、秘密鍵に対応するある整数kを掛け合わせた点Qが与えられたとき、QとPからkを効率的に見つけることが非常に難しい、という性質を利用している。現在の高性能なコンピュータを使っても、このkを総当たりで見つけ出すには、宇宙が誕生してから現在までの時間よりもはるかに長い時間がかかるとされており、事実上解読不可能とされている。この計算の困難性が、ECDSAのセキュリティの基盤となっている。

しかし、この前提を根底から覆す可能性を持つのが「量子コンピュータ」だ。従来のコンピュータが情報を「0」か「1」のどちらかで表現する「ビット」を用いるのに対し、量子コンピュータは「0」と「1」の状態を同時に重ね合わせて持つことができる「量子ビット（キュービット）」を利用する。この「重ね合わせ」や、複数の量子ビットがお互いに影響しあう「量子もつれ」といった量子力学特有の現象を利用することで、従来のコンピュータでは考えられないような並列計算能力を発揮できる。まだ実験段階ではあるものの、特定の種類の計算においては、その計算能力は既存のスーパーコンピュータをはるかに凌駕すると期待されている。

量子コンピュータが登場すると、なぜECDSAが安全でなくなるのだろうか。その鍵となるのが「ショアのアルゴリズム（Shor's algorithm）」という量子アルゴリズムだ。ショアのアルゴリズムは、1994年にピーター・ショアによって考案されたもので、大きな整数の素因数分解問題や、従来の離散対数問題を、量子コンピュータであれば非常に効率的に解けることを示した。そして、ECDSAの安全性の根拠となっている楕円曲線上の離散対数問題（ECDLP）も、このショアのアルゴリズムの適用範囲に含まれることが判明している。つまり、もし実用的な量子コンピュータが開発され、ショアのアルゴリズムを実行できるようになれば、ECDSAで使われている公開鍵から秘密鍵を短時間で割り出すことが可能になり、現在のECDSAによる電子署名は容易に偽造されたり、解読されたりする危険性が出てくるのだ。これは、たとえ鍵の長さをどれほど長くしても、ショアのアルゴリズムの前では本質的な意味を持たず、現在の暗号システムのほとんどが一夜にして無力になることを意味する。

このような量子コンピュータによる暗号の脅威に対抗するために、世界中で「量子耐性暗号（Post-Quantum Cryptography: PQC）」、または「耐量子計算機暗号」と呼ばれる新しい暗号技術の研究開発が盛んに進められている。これは、量子コンピュータがもたらすであろう計算能力をもってしても、その安全性を保つことができる暗号アルゴリズムを目指すものだ。具体的には、格子暗号、ハッシュベース暗号、多変数多項式暗号、符号ベース暗号など、現在の暗号とは全く異なる数学的問題を安全性の根拠とする様々な方式が提案され、国際的な標準化に向けた動きも加速している。アメリカ国立標準技術研究所（NIST）は、いくつかの量子耐性暗号アルゴリズムを次世代の標準として選定するためのプロセスをすでに開始している。

現時点では、大規模な汎用量子コンピュータはまだ実用段階には至っていない。しかし、その技術的な進歩は著しく、いつ実用化されるか予測が難しい状況だ。もし量子コンピュータが実用化された後になってから対策を始めても、それでは遅すぎる可能性がある。なぜなら、現在暗号化されている重要なデータが、将来量子コンピュータによって解読される可能性を考慮に入れる必要があるからだ。これは「Harvest Now, Decrypt Later（今すぐ収集し、後で解読する）」という攻撃シナリオとしても知られている。つまり、現在の通信内容を収集・保存しておき、将来的に量子コンピュータが実用化されたときにそれらを解読するという脅威だ。

したがって、システムエンジニアを目指す私たちにとって、量子コンピュータの登場は単なるSFの世界の話ではなく、現在の暗号技術の限界と、将来のセキュリティシステムをどのように構築していくかを真剣に考えるべき重要な課題である。既存のシステムに依存するだけでなく、量子耐性暗号へのスムーズな移行計画を立て、新しい技術動向を常に学び続けることが、これからのデジタル社会の安全を守る上で不可欠となるだろう。