ショアのアルゴリズム: RSA 暗号解読の「不滅の神話」

RSA 暗号化は、かつては最も信頼性の高い暗号化アルゴリズムと考えられていましたが、Shor のアルゴリズムの出現により、RSA の不滅の神話は打ち砕かれました。

[[145987]]

RSA 暗号化 VS ショアのアルゴリズム

RSA 暗号化技術の終焉である「読み取るには操作が多すぎる」ショアのアルゴリズムは、ブルートフォースによって最終的なパスワードを見つけるのではなく、量子コンピューティングの並列処理を使用して公約数を素早く因数分解し、RSA アルゴリズムの基礎を破壊します (つまり、既知の整数を効果的に因数分解できないと仮定します)。同時に、ショアのアルゴリズムは因数分解の問題が量子コンピュータ上で非常に効率的に解決できることを示しており、十分に大きな量子コンピュータであれば RSA を解読することができます。

RSA 暗号化がかつて非常に強力であった理由は、非常に大きな整数を因数分解することが難しいため、RSA アルゴリズムの信頼性が決まるからです。 2 つの素数を掛け合わせるのは簡単ですが、大きな数の素因数を見つけるのは非常に困難です。これは現代の多くのテクノロジーが依存しているものであり、RSA 暗号化はそのシンプルさから急速に普及しました。

しかし、RSA 暗号化を無効にする技術があります。 Shor のアルゴリズムは RSA を破ることができますが、実際にはどのように機能するのでしょうか?

一度にすべての素因数を試すことをお勧めしているわけではありません。

代わりに、（比較的）簡潔な文を使用してください。

次の周期関数の周期を素早く求めれば、

f(x) = m^x (Nを法とする)

すると、RSA 暗号化を解読できるようになります。

ショアファイブステップ

では、ショアのアルゴリズムはどのように機能するのでしょうか? ショアの 5 ステップ方式では、量子コンピューターを使用する必要があるのは 1 ステップのみで、他のステップは従来の方法で解決できます。

***ステップ：

ユークリッドの互除法とも呼ばれる従来の *** 共通約数分解 (gcd) アルゴリズムを使用します。 N は試す必要がある因子の数であり、m は N 未満のランダムな正の整数です。

gcd(m,N)=1 の場合は続行します。 gcd を使用して因数を見つけると、非自明な因数が得られ、作業は完了です。

ステップ2:

周期Pを求める

m を法として N、m^2 を法として N、m^3 を法として N

これは量子コンピューティングの使用に向けた一歩です。

ステップ3:

周期 P が奇数の場合は、手順 1 に戻り、別のランダムな整数を選択します。そうでない場合は、次の手順に進みます。

ステップ4:

テスト

真の場合、手順 5 に進みます。それ以外の場合は、手順 1 に戻ります。

ステップ5:

解く

非自明な素因数 N を解くと、RSA 暗号を解読できます。

2 番目のステップはどのように達成されますか?

では、量子コンピューターは関数の周期をどうやって見つけるのでしょうか? そして、それがなぜそれほど重要なのでしょうか?

期間Pを見てみましょう。

m を法として N、m^2 を法として N、m^3 を法として N

(これは指数関数なので、複素素数を双曲正弦、双曲余弦に変換して周期を求めることができます)

このサイクルを発見するプロセスは、量子コンピューターが同時に多くの状態、つまり状態の「重ね合わせ」を計算する能力に依存しており、これにより方程式の周期を見つけることができます。

これを実行する必要があります:

1. アダマールゲートを適用して量子重ね合わせ状態を作成する

2. 量子変換により方程式が機能する

3. 量子フーリエ変換の実行

従来の場合と同様に、これらの変換後の測定値は、方程式の周期に近い値になります (フーリエ変換のように「ピーク」を得ることができますが、精度は少し高くなります)。量子フーリエ変換を使用すると、同じ問題であるソート問題と因数分解問題を解くことができます。量子フーリエ変換により、量子コンピュータは位相推定（ユニタリ演算子の固有値の近似）を実行できるようになります。

量子部分 (ステップ 2) を完了したら、期間の有効性を確認し、別の従来の *** 公約数アルゴリズムを使用してキーの素因数を取得できます。

興味深いことに、この手法はすべての潜在的な素因数を見つけることではなく、潜在的なサイクルを見つけることなので、N の適切な素因数を見つけるまで、多くの乱数を試す必要はありません。 Pが奇数の場合は、ステップ1に戻って

K は N とは異なる質的要因です。したがって、キーの長さ (N) を 2 倍にしても、素因数を見つけるのに速度が低下することはありません。 RSA は安全ではなく、キーの長さを 2 倍にしても量子コンピューティングの猛攻に抵抗してセキュリティを確保することはできません。

「従来のコンピュータでは、RSA-2048（2048ビット）キーを解読するのに10億年かかるかもしれないが、量子コンピュータではわずか100秒で解読できる。」

—クリスタ・スヴォア博士、マイクロソフトリサーチ

量子フーリエ変換は量子回路の構築に使用され、ショアのアルゴリズムの物理的な実装は量子コンピューターにとって最も簡単なタスクの 1 つになります。

量子フーリエ変換：オリジナルよりも優れている

ショアのアルゴリズムの中核は順序を発見することであり、これはアベルの隠れた部分群問題を軽減し、量子フーリエ変換を使用して解決することができます。 ——NIST 量子ワールド

量子フーリエ変換は多くの量子アルゴリズムの鍵となります。従来のフーリエ変換の検索を高速化することはできませんが、単一の量子振幅内でフーリエ変換を実行できます。量子フーリエ変換は量子コンピュータ上で指数関数的に高速に処理できます。古典的なフーリエ変換を直接マッピングする範囲を超えていますが、量子コンピューターは他のこともできます。たとえば、隠れた部分群の問題 (つまり、離散対数の問題) を解くことや、計数の問題 (この問題を解くことで、現代の暗号における他の多くの形式のコードを解くことができます) を解くことなどです。さらに重要なことは、量子フーリエ変換は機械学習、化学、材料科学、量子システムのシミュレーションに応用できることです。

ショアのアルゴリズムでは、量子コンピュータで完了する必要があるのは 1 つのステップのみで、残りは通常のスーパーコンピュータで完了できます。量子コンピュータはサブルーチンの実行を終えると、計算プロセスを続行できるように結果をスーパーコンピュータに返します。量子コンピュータは単独で存在することは決してないかもしれませんが、常にスーパーコンピュータと連携してタスクを実行し、そのような連携を通じて RSA キーを解読することができます。

スペースが限られているため、多くの数学的な詳細と証明プロセスは繰り返せません。これらの数学的な説明に興味があり、線形代数、群論、高度な数学の知識がある場合は、以下を参照してください。

量子コンピュータサイエンス

量子情報と量子計算

NIST Quantum Zoo — すべての量子アルゴリズムのリスト