encryption - 量子コンピューティングと暗号解読

Question

しばらく前に、量子コンピューターは現在使用されているほとんどのタイプのハッシュと暗号化を非常に短い時間 (ほんの数分だったと思います) で解読できることを読みました。それはどのように可能ですか？私はそれについての記事を読んでみましたが、a quantum bit can be 1, 0, or something else. これが、高度な数学を使わずに平易な英語でそのようなアルゴリズムをクラックすることにどのように関連するかを誰か説明できますか?

Answer 1

前文:量子コンピュータは奇妙な獣であり、私たちはまだ実際に使いこなせるようにはなっていません。それらを支える理論は抽象的で数学的であるため、従来のコンピューターよりも効率的になる方法についての議論は、必然的に長く複雑になります。詳細を理解するには、少なくとも線形代数と量子力学の学士号の理解が必要ですが、私の限られた理解を伝えようとします!

---

量子計算の基本的な前提は、量子重ね合わせです。アイデアは、量子システム (量子ビット、または通常のビットの量子アナログであるqubit0など) は、あなたが言うように、および1状態 (システムの計算上の基底状態と呼ばれる) だけでなく、また、この 2 つを任意に組み合わせて使用​​します (それぞれに振幅が関連付けられます)。システムが誰かによって観察されると、キュービットの状態はその基底状態の 1 つに崩壊します (これに関連するシュレーディンガーの猫の思考実験について聞いたことがあるかもしれません)。

このため、キュービットのレジスターには独自の基底状態があります (これらは、レジスターが存在することを観察できる状態です。従来の n ビット整数を想像してください)。レジスターはこれらすべての状態の重ね合わせで一度に存在できるため、それらの 1 つだけではなく、すべてのレジスター状態に計算を適用することができます。これは、量子並列処理と呼ばれます。n2^n2^n

量子コンピューターのこの特性により、従来のコンピューターよりも指数関数的に速くあらゆる問題を解決できる特効薬のように思えるかもしれません。しかし、それはそれほど単純ではありません。問題は、計算の結果を観察すると、(上で述べたように) 計算の 1 つの結果だけに崩壊し、他のすべての計算の結果を失うことです。

量子計算/アルゴリズムの分野では、量子現象を操作して、従来のコンピューターよりも少ない操作で情報を抽出することにより、この問題を回避しようとしています。考えられる古典的なアルゴリズムよりも高速な「量子アルゴリズム」を考案することは非常に難しいことが判明しました。

あなたが尋ねる例は、量子暗号解読の例です。量子コンピューターは、特定の暗号化アルゴリズムを「破る」ことができると考えられています。具体的には、RSA アルゴリズムは、非常に大きな整数の素因数を見つけることの難しさに依存しています。これを可能にするアルゴリズムはショールのアルゴリズムと呼ばれ、多項式の時間計算量で整数を因数分解できます。対照的に、問題に最適な古典的アルゴリズムは (ほぼ) 指数関数的な時間の複雑さを持ち、そのため問題は「扱いにくい」と見なされます。

これをより深く理解したい場合は、線形代数と量子力学に関する本を数冊入手して、慣れてください。説明が必要な場合は、私にできることを確認します。

---

余談ですが、量子重ね合わせの考え方をよりよく理解するために、確率の観点から考えてみましょう。コインを投げて、見えないように覆われた手でそれをキャッチすると想像してください。非常に希薄なアナロジーとして、コインは表と裏の「状態」の重ね合わせにあると考えることができます。それぞれの状態の確率は 0.5 です (そして、当然のことながら、2 つの状態があるため、これらの確率の合計は 1 になります)。手を離してコインを直視すると、表の状態か裏の状態のどちらかになるので、この状態の確率は 1 になり、もう一方の状態の確率は 0 になります。観察までバランスが取れている一連のスケールであり、システムの知識が増加し、1 つの状態が「実際の」状態になるにつれて、一方の側に傾きます。

もちろん、私たちはコインを量子システムとは考えていません。実際には、たとえ見えなくても、コインには明確な状態があります。しかし、本物の量子系 (箱に閉じ込められた個々の粒子など) については、このように考えることができません。量子力学の従来の解釈では、粒子は基本的に明確な位置を持たず、すべての可能な位置に同時に存在します。観測時にのみ、その位置は空間内で制約されますが (ただし、限られた程度に限られます。不確定性原理を参照)、これでさえ純粋にランダムであり、確率によってのみ決定されます。

ちなみに、量子系は観測可能な状態が 2 つだけに制限されているわけではありません (観測可能な状態を2 レベル システムと呼びます)。大きいが有限の数を持つものもあれば、数えられるほど無限の数を持つものもあり ( 「箱の中の粒子」や調和振動子など)、数え切れないほど無限の数を持つものもあります (自由粒子の位置など)。空間内の個々のポイントに制約されません)。

Answer 2

ウィキペディアの記事は、これを非常にうまく説明しています。

つまり、N ビットの場合、量子コンピューターは同時に 2^N 状態になることができます。概念的には、従来のビットで 2^N CPU の処理を​​行うことに似ています (ただし、まったく同じではありません)。

Answer 3

この時点では非常に理論的です。Quantum Bits は暗号を破る機能を提供するかもしれませんが、明らかにその時点ではありません。

量子レベルでは、行動を支配する法則はマクロ レベルとは異なります。

あなたの質問に答えるには、まず暗号化の仕組みを理解する必要があります。

基本的なレベルでは、暗号化は 2 つの非常に大きな素数を掛け合わせた結果です。この非常に大きな結果は、1、それ自体、およびこれら 2 つの素数で割り切れます。

暗号化を破る 1 つの方法は、素数因数分解を行うことによって、2 つの素数を力ずくで推測することです。

この攻撃は遅く、より大きな素数を選択することで阻止されます。鍵のサイズは 40 ビット、56 ビット、128 ビット、そして現在は 256,512 ビット以上です。これらのサイズは、数字のサイズに対応しています。

ブルート フォース アルゴリズムは (簡略化して) 次のようになります。

for(int i = 3; i < int64.max; i++)
{
  if( key / i is integral)
  {
    //we have a prime factor
  }
}

したがって、力ずくで素数を試してみたいと思います。1 台のコンピューターでそれを行うには、しばらく時間がかかります。そのため、多数のコンピューターをグループ化して、分割して征服することを試みることができます。これは機能しますが、非常に大きなキーサイズの場合はまだ遅くなります。

同時に 0 と 1 の両方である量子ビット アドレスです。つまり、3つの量子ビットがあるとします（小さな偉業はありません）。

3 つの qbit を使用すると、プログラムは 0 ～ 7 の値を同時に持つことができます。

(000,001,010,011など)

、同時に素数 3,5,7 を含みます。

したがって、上記の単純なアルゴリズムを使用すると、毎回 i を 1 ずつ増やす代わりに、1 回除算してチェックすることができます。

0,1,2,3,4,5,6,7

すべて同時に。

もちろん、量子ビットはまだその段階に達していません。この分野でやるべきことはまだたくさんあります。しかし、これにより、量子を使用してプログラミングできれば、暗号を解読するにはどうすればよいかがわかります。

Answer 4

ほとんどすべての公開鍵暗号化 (例: RSA) は数学のみに基づいており、因数分解や離散対数の難しさに依存しています。これらは両方とも、量子コンピューターを使用して効率的に破ることができます(ただし、CS と数学の学士号を取得し、量子力学に関するいくつかのクラスを受講した後でも、私はまだアルゴリズムを理解していません)。

ただし、主に拡散と混乱に基づくハッシュ アルゴリズム (例: SHA2) と対称キー暗号化 (例: AES)は、依然として安全です。

Answer 5

量子コンピューターは、素因数分解を高速に実行できるShor のアルゴリズムを実装できます。暗号化システムは、大きな素数は従来のコンピューターでは妥当な時間内に因数分解できないという前提に基づいて構築されています。

Answer 6

最も基本的な用語では、通常の非量子コンピューターは、ブール論理を使用してビット (オンまたはオフの状態) を操作することによって機能します。大量のビットに対してこれを非常に高速に実行し、計算可能な問題のクラスのすべての問題を解決できます。

ただし、それらは「速度制限」、つまり計算の複雑さと呼ばれるものです。これは、一般的な言葉で言えば、特定のアルゴリズムについて、アルゴリズムの実行にかかる時間 (およびアルゴリズムの実行に必要なメモリ領域) に最小限界があることを意味します。 . たとえば、O(n^2) のアルゴリズムは、データ サイズが n の場合、実行に n^2 時間が必要であることを意味します。

ただし、「間に」値を持つことができるqbitで操作を行っているときに、qbit（量子ビット）がある場合、この種のウィンドウは消えます。計算の複雑さが非常に高いアルゴリズム (多くの暗号化アルゴリズムを解読するための鍵となる巨大な数の素因数分解など) は、はるかに低い計算の複雑さで実行できます。これが、量子コンピューティングが暗号化されたストリームを通常のコンピューターよりも桁違いに速くクラックできる理由です。

Answer 7

まず第一に、量子コンピューティングはまだ理論段階からかろうじて抜け出している。多くの研究が進行中で、いくつかの実験的な量子セルと回路がありますが、「量子コンピューター」はまだ存在しません。

次に、ウィキペディアの記事を読んでください: http://en.wikipedia.org/wiki/Quantum_computer

特に、「一般に、n 個の量子ビットを持つ量子コンピューターは、最大 2^n 個の異なる状態を同時に任意に重ね合わせることができます (これは、一度にこれらの 2^n 個の状態のうちの 1 つだけになることができる通常のコンピューターと比較します。 )」

暗号化を安全にするのは、非常に長い数の暗号化キーを使用することです。暗号化キーは構成要素の素数を計算に入れるのに非常に長い時間がかかります。キーは十分に長いため、可能なすべてのキー値を試してみようとすると、また、完了するのに時間がかかりすぎます。

量子コンピューティングは (理論的には) 少数のキュービット セルで多くの状態を表すことができ、それらすべての状態を同時に処理できるため、量子コンピューティングを使用してブルート フォースの try-all-possible- を実行できる可能性があるようです。非常に短い時間で Key-Value。

そのようなことが可能である場合、それは私たちが知っている暗号の終焉となる可能性があります。