TCR (Taurus Cybersecurity Research)

これは、ポスト量子暗号（Post Quantum Cryptography (PQC）について、更に、従来の暗号アルゴリズムからPQCアルゴリズムへの移行に関するシリーズの第1回です。

暗号の安全性について

まず、暗号アルゴリズムには大きく分けて2つの種類があります（暗号化、署名、鍵の共有等）。

• 共通鍵暗号
• 公開鍵暗号

これた2つのうち、共通鍵暗号の方がより分かりやすく、実際ローマ時代から何世紀にもわたって存在してきました。この方式では、メッセージを暗号化および復号化する鍵が同じものである、ということです。言ってみれば玄関のドアを施錠・解錠するための家の鍵のように、非常にわかりやすいと思います。通信システムでの前提では、メッセージの送信者と受信者の双方が、何らかの方法でこの鍵を共有しているということです。Advanced Encryption Standard（AES）は2001年に米国国立標準技術研究所（NIST）によって標準化され、現在最も広く使用されている共通鍵暗号アルゴリズムです。

一方、公開鍵暗号は（1976年にようやく登場したばかりの！）比較的新しい概念であり、ここではメッセージの暗号化と復号化には異なる鍵が使われます。家の鍵に例えるなら、ドアを施錠するための鍵と解錠するための鍵が異なるというわけです。これは、（1976年に有名なディフィー・ヘルマンの論文が発表されるまでは）そのようなことが可能だとは誰も考えていなかったという点で、非常に画期的な概念です。これには、公開鍵と秘密鍵という2つの鍵が関わっています。その名の通り、公開鍵は誰にも共有することができますが、一方、それに対応する秘密鍵は所有者のみが保持するものです。通信システムでは、送信者は公開鍵を使ってメッセージを暗号化し、受信者（公開鍵と秘密鍵のペアの所有者）は秘密鍵を使ってそれを復号します。

公開鍵暗号の安全性は、秘密鍵の機密性に依存しています。つまり、もし秘密鍵が解読されてしまえば、誰でもその鍵の正当な所有者を装うことが可能になってしまいます。RSA、ディフィー・ヘルマン鍵交換、エル・ガマル、楕円曲線暗号（ECC）は、公開鍵暗号の一種です。

公開鍵暗号の根本的な特徴は、いくつかの数学的問題の解くことの難しさに基づいている点です。具体的には、特定の数学的演算の一方向性（逆演算が困難であること）が、その重要な構成要素となっています。要するに、逆演算を行うのに極めて長い時間がかかる場合（例えば、最高性能のコンピュータでも必要な計算に数千年以上を要するといった場合）、そのアルゴリズムは現実では事実上安全であると見なされます。これは相対的な概念です。時間はかかるかもしれませんが理論上は依然として可能であり、その安全性は既存の（最高性能の）コンピュータの性能制限によって守られているとも言えます。言い換えれば、この前提が成り立たなくなれば、このセキュリティの原則は崩壊してしまうことになります。

そのような数学的問題には、(1) 巨大な数の因数分解（RSA、ディフィー・ヘルマン）、および (2) 離散対数問題（ディフィー・ヘルマン、エル・ガマル、ECC）があります。これらのアルゴリズムの詳細については、別のブログ記事で取り上げる予定です。ここでは、ごく大まかな概要にとどめておきます。

１．巨大な数の因数分解

2つの整数 $p$ と $q$ があるとき、これらを掛けることはいたって簡単です。

掛け算のやり方は誰もが知っていることです。たとえ両方の数が大きくても、計算することは可能です。ただし、手計算だとすぐに面倒で時間がかかのでやめてしまいますが（コンピュータにとっては依然として簡単な処理です）。一方、整数の因数分解は、数が大きくなるにつれて非常に時間がかかり、「難しい」ものになります。例えば、143の因数分解なら、紙とペンを使わずにも頭の中で計算できるレベルです（11 × 13）。しかし、477,568,881,191の因数分解ははるかに難しく、間違いなく時間がかかります（477,577 × 999,983）。もし紙とペンしか使えなければ、そもそもやろうとも思わないでしょうし、暗算で解くことなど論外です。600桁を超える10進数（つまり2048ビットの2進数で表される数）の因数分解などまったく想像もつきませんね。¹ 同様の状況がコンピュータにも当てはまります。巨大な数を因数分解するための効果的で高速なアルゴリズムが存在しないため、桁数が増えるにつれて、因数分解には非常に長い時間がかかるということになります。

2．離散対数問題

もう一つの一方向性の問題として、いわゆる離散対数問題があります。これは、剰余演算を用いた次の式で表されます。

ここで、$n$ は大きな素数であり、$a$ と $x$ は、$x$ の値が大きくなるように、$a$ が $n$ より小さい数（つまり、$a<n$）となるように定義されます。この式において、$a,\,x,\,n$ が分かっていれば、$c$ を計算するのは容易です。しかし、$c,\,a,\,n$ が与えられたとしても、そこから$x$（大きな数）を求めるのは困難です。この難しさの一因は、モジュラー算術（すなわち $(mod\, n)$ の部分）にあります。これは、$a^x$ の値が $n$ を何周するかを「隠してしまう」ためです。$x$が大きな数である場合、その$x$ のすべての値を総当たりで試すことは、非常に時間のかかる作業となります。

量子コンピュータの登場

さて問題は、十分に高性能な量子コンピュータが現実のものとなった場合、これら2つの「難問」の想定されていた安全性が脅かされるという点です。量子コンピュータはすでに存在していますが、膨大な桁数が関わるこれらの問題を解くには、さらにはるかに高性能な量子コンピュータが必要になると予想されています。現在の量子コンピュータの中には、物理的な量子ビット（qbit）の数が最大1万個程度に達するものもあると言われています。しかし、物理量子ビットは非常に脆弱でエラーが発生しやすく、実用上は信頼性が低いものです。そのため、実際に利用可能にするには、エラー訂正機能を備えた、より安定して信頼性の高い論理量子ビットに変換する必要があります。現在の論理量子ビットの数は、100個未満程度とされています。

1994年に発表されたショアのアルゴリズムは、量子コンピュータが多項式時間で大きな数を因数分解できることを示しました。これは事実上、「困難な」問題に依存するアルゴリズムが、量子コンピュータの前ではもはや安全ではないことを意味します。これは大きなパラダイムシフトであり、「数千年以上かかる極めて時間のかかる計算」とされてきた前提が崩れることになります。したがって、十分に強力な量子コンピュータでショアのアルゴリズムを実行すれば、従来想定されていたアルゴリズムの安全性はもはや成り立たなくなることを意味します。

「今保存し、後で復号する」（”Store now, decrypt later”, SNDL）あるいは「今収集し、後で復号する」（”Harvest now, decrypt later”, HNDL）という攻撃は、すでに差し迫った懸念となっています。特に政府、軍、諜報機関など、極めて機密性の高い情報を扱う組織においては危急の問題となります。この場合、現時点では復号できないものの、攻撃者は将来そのような強力な量子コンピュータが利用可能になった際に復号できるよう、暗号化されたデータ（メッセージなど）を保存するという考えに基づいているものです。

もちろん、そのような十分な性能を持つ量子コンピュータがいつ登場するかという点には大きな疑問が残ります。これについては、共通の見解が定まっていないため、誰に聞くかによって答えは異なります。しかし、セキュリティコミュニティは常に先手を打つことを目指しており、そのような高性能な量子コンピュータが現実のものとなったとしても安全性を保てる新しい暗号アルゴリズムの策定を進めてきました。実際、2016年にNISTは、ポスト量子暗号（PQC）アルゴリズムを選定するためのコンテスト形式の選考プロセスを開始しました。そして2022年、いくつかのアルゴリズムを選定しました。

共通鍵暗号に対する脅威は？

前述したように、公開鍵暗号アルゴリズムは、巨大な数の因数分解問題と離散対数問題のいずれかで構成されています。では、共通鍵暗号についてはどうでしょうか？　共通鍵暗号において、その安全性は暗号鍵を解読することの難しさにかかっています。最も単純なアプローチは、正しい鍵が見つかるまですべての鍵の値を試し尽くすこと、いわゆるブルートフォース攻撃です。ここでは正しい鍵を見つけるための平均試行回数は $n/2$となります（$n$ は鍵の長さ）。つまり、平均値として、正しい鍵にたどり着くまですべての可能な鍵の値の半分を試す必要があります。一方、この探索を高速化する最もよく知られた効率的なアルゴリズムは「グローバーのアルゴリズム」と呼ばれ、これにより巨大な鍵を解読する時間を $n/2$ ではなく$\sqrt[2]{n}$ まで短縮できます。これにより、実質的にセキュリティレベルは鍵長の半分のレベルまで低下することになります。これの意味するところは、量子コンピュータが登場しても、同じレベルのセキュリティを維持するには、単に鍵長を倍にすればよいことを意味します。言い換えれば、128ビットAESと同等のセキュリティ保護を維持するには、鍵長を256ビットに変更するだけで対応可となります。このような状況のため、量子コンピュータは共通鍵暗号に対して差し迫った脅威とはなっていません。

次回のブログでは、こうした数学的な「難問」の詳細について、もう少し詳しく解説します。

1. ちなみに、地球上の砂粒の数は$7.5×10^{18}$（つまりたった(!)の18桁程度の数）に過ぎないと言われています