暗号化アルゴリズムの複雑さを理解する
1. 序章
このチュートリアルでは、暗号化アルゴリズム内の計算の複雑さの問題を調べます。
議論は具体的な暗号化アルゴリズムに焦点を当てませんが、それらの基本的な一般法則を公開します。
2. 対称および公開鍵暗号システム
2人の人が、秘密の形で通信したいとします。 内容しか理解できないようにメッセージを送信したい。 これを行うために、は暗号システムまたは暗号と呼ばれるプロトコルを使用します。これは暗号化機能を介して元のメッセージの暗号文または暗号文を生成します。
復号化関数（基本的にはの逆関数）を使用して、元のメッセージを取得します。
暗号化と復号化は、従来の通信メカニズムのコーディングおよびデコードサブシステムのコンポーネントと見なすことができます。
に送信されたメッセージを傍受できる第三者がいるとします。 最も不利な条件は、とによって使用されるプロトコルを知っているという事実を考慮することを強制します。 この時点で、を適用するだけでメッセージを復号化できます。
したがって、通信を安全にするために追加の要素が必要です。 この要素は秘密鍵、または単に鍵であり、使用されている通信プロトコルを知っているにもかかわらず、メッセージを復号化することはできません。
しかし、の秘密鍵を知る必要がありますか？ 20世紀の終わりまで、ほとんどの暗号研究者はこの質問に肯定的に答えていたでしょう。 この場合、対称鍵システム について説明します。それらのセキュリティは、鍵の機密性に依存します。
1976年、DiffieとHellmanは、公開鍵暗号システムを提案した記事「暗号化の新しい方向性」を公開しました。 それらの中で、彼だけが知っている彼の秘密鍵で解読できるパブリックドメイン鍵または公開鍵でメッセージを暗号化します。 誰でも暗号化されたメッセージをに送信できますが、その内容を知ることしかできません。 これにより、対称暗号システムの弱点であるキーセキュリティの問題が解消されます。
3. クラシック対。 現代の暗号化
による潜在的な攻撃が疑われるシナリオでは、次の2つの基本的な質問をすることができます。
- 取得したメッセージと暗号文のペアで何ができるでしょうか？
- セキュリティの観点から、どの結果が満足できるでしょうか？
これらの質問にどのように答えるかによって、2つの異なるアプローチがあります。 現代の暗号。
問題を深めるために、TalbotとWelshによる優れたテキスト「複雑さと暗号化、紹介」をお勧めします。
3.1. 古典的な暗号化
情報理論に基づいており、情報理論的アプローチとして知られているシャノンによって大部分が詳しく説明されています。 基本的な前提は次のとおりです。
暗号文は、メッセージに関する情報を明らかにしてはなりません。
この仮定は、次のように形式化できる完全な秘密の概念につながります。
この式は、可能なメッセージのセット間の具体的なメッセージと、可能な暗号のセット間の具体的な暗号が与えられた場合、の確率はに依存しないことを単純に示しています。 メッセージの暗号文にアクセスできたとしても、その内容については何も知ることができません。
このアプローチの問題の1つは、完全機密システムでは、少なくともそれで覆われる可能性のあるメッセージと同じ長さのキー長が必要であり、インターネットなどの最新の通信システムには適さないことです。
3.2. 現代の暗号化
現代の暗号化は、まったく異なるアプローチを採用しています。 基本的な前提は次のとおりです。
暗号文がメッセージに関する情報を明らかにするかどうかは関係ありません。 重要なのは、この情報を効率的に抽出できるかどうかです。
が無制限の計算能力を持っていると仮定すると、前の命題は成り立たなくなります。 したがって、現代の暗号化では次のように考慮されます。
計算リソースが限られています。
ただし、これがに当てはまる場合は、とにも当てはまります。これにより、次の追加の仮定が発生します。
一方向性関数と呼ばれる、計算は簡単ですが反転が難しい数学関数があります。
このシナリオでは、少数の計算リソースでメッセージを暗号化できますが、メッセージから情報を取得できるのは、メッセージに高い計算能力がある場合のみです。 最後の仮定は、計算手順の複雑さ、したがってそれらの実装の容易さまたは困難さに関連する問題の重要性を明らかにしています。
現代の暗号化は、暗号化されたトランザクションと通信で基本的に今日使用されているものです。 ただし、量子コンピューターなど、指数関数的に増加する計算能力を可能にするシステムは、潜在的に危険にさらされています。
4. 複雑性理論のフレームワーク
暗号化システムを含むすべてのコンピューティングシステムは、計算可能な関数のみを使用できます。 重要なのは、計算のしやすさまたは難しさです。
たとえば、一連の数値を並べ替えるなど、特定の問題があるとします。 この問題をと呼びます。 複雑性理論は、次のような質問に答えようとします。
- 本質的に解決するのは簡単ですか、それとも難しいですか？
- 与えられた、そして、どちらが解決するのが簡単ですか？
答えを出すために、次のアイデアに従って、アルゴリズムをさまざまな複雑さのクラスに分類します。これらのクラスは、共通の特性を持つ計算手順をグループ化します。
- 基本操作の数でアルゴリズムの実行時間を測定します。
- アルゴリズムの実行時間は、入力のサイズによって異なります。
-表記は、これらのアイデアを表現するための象徴性を確立します。 たとえば、複雑なアルゴリズムは、入力のサイズの2乗に等しい数の基本演算を実行する必要があります。
5.複雑さのクラス
-notationを使用すると、上記の用語で複雑度クラスを定義できます。 詳細については、チュートリアル P、NP、NP完全およびNP困難コンピュータサイエンスを参照してください。
次の図は、以下で説明する複雑度クラスの構造を示しています。
5.1. Pクラス
これは、多項式時間で解けるアルゴリズムのクラスです。 定数が与えられると、時間内に実行可能なアルゴリズムが含まれます。 これらのアルゴリズムは実行可能で効率的であると考えており、決定問題（はい/いいえの答えのアルゴリズム）に還元することで理論的に研究することができます。
非常に大きな多項式問題は、正式にはクラスPに属しますが、いずれの場合も手に負えません。 多項式時間で解決できない問題は、一般に実行不可能であると考えています。
知られているように、多くの暗号化アルゴリズムの逆関数は、非常に大きな素数の因数分解にあります。 試行除算によるビットの整数の因数分解は、指数関数的な時間で発生します。これにより、数百のオーダーでも手順が実行不可能になります。
素数性テストがPにある間、最も効率的な素因数分解アルゴリズムには、多項式時間からはほど遠い時間があります。 因数分解の問題はPにはないと信じていますが、それは推測であり、したがって証拠はありません。 RSAやRabin暗号システムなどのアルゴリズムは、この推測に基づいています。
5.2. NPクラス
これは、多項式時間で検証可能な問題のクラスです。 因数分解の問題は明らかにNPにありますが、指数時間で解くことができます。一連の因子と素数が与えられると、因数を乗算するだけで、因数分解が正しいかどうかを多項式時間で検証できます。
もう1つのよく知られている例は、巡回セールスマン問題です。 セールスマンは一度都市のグループを訪問する必要があります。 問題は、最短経路につながる都市のシーケンスを特定することです。
考えられるすべてのパスを構築しようとして、素朴な方法で問題に取り組むと、適度な数でも問題が手に負えなくなることがすぐにわかります。 いくつかの教訓的な例は、地球のすべての原子をコンピューティングデバイスと見なすと、それぞれが最も強力なコンピューターよりも桁違いに高速であるとすると、宇宙の年齢のオーダーの計算時間がかかることを示しています。数百の都市。
5.3. 還元性
解決することで解決できる場合、問題は問題になります。
直感的に、還元性は、複雑さの観点から問題間の同等性のアイデアを提供します。
5.4. クラスNPCおよびNP完全性
NPおよび各NP問題がに減少する場合、問題はNP完全（NPC）であると言われます。 これらはNPで最も困難な問題であり、手に負えない可能性が最も高い問題です。
原則として、暗号化システムを構築するために望ましい複雑さのクラスですが、この目的には十分な条件ではありません。
重要な結果は、NPCの問題に対して多項式時間解法アルゴリズムが見つかった場合、すべてのNP問題をPに減らし、多項式時間でそれらを解くことができるということです。 その結果、P = NPになりますが、これはありそうもないと考えられています。
等式P=NPは、Pで計算できない逆関数にある暗号アルゴリズムの多くを無効にします。
5.5. BPPクラス
BPP（有界誤差確率多項式時間）問題のクラスには、厳密に決定論的な時間では動作しないが、計算中にランダムな選択を利用するアルゴリズムで解決可能な問題が含まれます。 詳細については説明しませんが、このトピックは、秘密鍵の選択など、暗号化システムを構成するいくつかのステップに関連しています。
理論は、NP BPPであり、仮説PNPを支持する結果であることを示しています。
6.複雑性ベースの暗号化
現在の複雑性ベースの暗号化は、いくつかの指針に従って問題に対処しています。
- 還元主義的アプローチを使用して、考えられる膨大な量の問題とその計算の側面を、それらの複雑さに関するいくつかの仮定と関連付けようとします
- 暗号化プロトコルを構築できる計算問題の基本的な特性を特定する
したがって、暗号化システムでは、暗号化機能は多項式時間で実行されますが、復号化機能は多項式時間でのみ検証可能です。 すべての可能性の組み合わせ爆発は、試行錯誤によってメッセージを解読することを不可能にします。
ただし、前述したように、暗号化プロトコルにはPNPの仮定では不十分です。 この理由は、この不等式が最悪の場合に関連しているという事実によるものです。
より正式な言い方をすれば、問題がPにない場合、どの多項式アルゴリズムでも、を解けない入力があることを意味します。 しかし、これらの状況は少数派であるか、見つけるのが非常に難しい場合があります。 計算が困難なすべての問題について、これらのインスタンスを見つけるための体系的な方法が必要です。
7. 一方向性関数
以前の異論は、一方向性関数の概念で解決できます。 同様に、それは無視できる関数の概念に基づいています。
すべての定数に対して次のようなものがある場合、関数は無視できます。
多項式の逆数よりも速く減少します。
一方向性関数は、次の条件を満たす。
- 多項式時間で計算可能
- 多項式時間では反転できません。 正式には、長さのランダムな入力とランダムに選択された確率的多項式時間アルゴリズムが与えられると、次のような無視できる関数が存在します。
入力の長さは、暗号化プロトコルのキーの長さに相当します。
NP BPPの場合、一方向性関数がないことを示すことができます。
7.1. 一方向性関数の例
よく知られている例は次のとおりです。
- 乗算、、同じ長さの素数。 の反転は因数分解の問題であり、すでに見てきたように、実行不可能と見なされます。
- サブセット和、、はビットとの整数です。 反転はサブセット和問題であり、たとえばナップザック暗号化スキームで使用されます。 これはNPの問題ですが、一方向であるかどうかは定かではありませんが、
- 離散対数収集、ここで、は巡回群であり、はとの生成元です。 反転（離散対数問題）は実行不可能です
- RSAコレクション、、は、同じ長さの2つの素数の積です。
- ラビンのコレクション、。 Rabin暗号システムおよびRabinデジタル署名スキームで使用されます。 反転は、少なくとも因数分解と同じくらい難しいです
- ハッシュ関数とブロック暗号
ほとんどの暗号化操作は一方向性関数で実行できることを示すことができます。
8. トラップドア関数
公開鍵暗号などの多くの暗号化システムでは、トラップドアプロパティなどの追加のプロパティが必要になるため、一方向性関数では不十分です。 この場合、このトラップドア情報を提供することにより、機能を簡単に元に戻すことができます。
関数のコレクションは、次のプロパティを満たしている場合、トラップドア関数のコレクションです。
- 多項式時間には確率的アルゴリズムが存在し、特定の入力が与えられると、ペアを生成します。ここで、はファミリの関数の1つのインデックスであり、はトラップドア情報です。
- 入力として与えられると、時間Pで計算することが可能です
- 入力が与えられると、無視できない確率で生成する確率的多項式時間アルゴリズムはありません。
- Pで計算することが可能であるとすると
RSAコレクションとRabinコレクションにはトラップドアプロパティがあります。モジュラスの因数分解を指定すると、多項式時間で反転できます。
これに関連して、注目すべき定理が確立されます。
トラップドア機能が存在する場合は、公開鍵暗号化スキームが存在します。
この結果は、トラップドア関数を公開鍵暗号内の自然なツールに変換します。
9. 結論
入門的な観点から、複雑さと暗号化の関係を扱いました。 2つの分野間の接点は、特定の技術またはプロトコルの選択の背後にある理由を理解するための基本です。
この一般的な議論の後、私たちが推奨する自然な道は、個々のアルゴリズムを研究することです。 読者は主題を深めるために招待されています。
