暗号化および暗号化入門、パート1。 Yandexでの講義

公開鍵インフラストラクチャ、ネットワークセキュリティ、およびHTTPSに関する資料をすぐに理解するには、暗号理論の基礎を知る必要があります。 それらを研究する最も速い方法の1つは、ウラジミール・イブラド・イワノフによる講義を見るか読むことです。 ウラジミールは、その保護のためのネットワークとシステムの有名な専門家です。 彼はYandexで長い間働いており、私たちの運営部門のリーダーの一人でした。





この講義をトランスクリプトとともに公開するのは初めてです。 最初の部分から始めましょう。 カットの下に、テキストとスライドの一部があります。

---

私はかつてモスクワ州立大学で地下室について講義しましたが、彼らは6ヶ月間私を占領しました。 2時間半ですべてをお伝えします。 私はこれをやったことがありません。 それでは試してみましょう。



DESとは何を理解しているのですか？ AES？ TLS？ 二項マッピング？



分解するのは難しく、深いので、一般的な言葉で話そうとします。それは十分な時間ではなく、基本的なトレーニングはかなり大きいはずです。 表面的にではなく、一般的な概念で運用します。



暗号プリミティブとは何か、あとでより複雑なもの、プロトコルを作成できる単純な小さなものについて説明します。



対称暗号化、メッセージ認証、非対称暗号化の3つのプリミティブについて説明します。 多くのプロトコルがそれらから成長します。



今日は、キーの生成方法について少しお話しましょう。 一般に、あるユーザーから別のユーザーに持っている暗号プリミティブを使用して安全なメッセージを送信する方法について説明します。



一般的に暗号について話すとき、いくつかの基本原則があります。 それらの1つは、暗号のオープンソースが非常に重要であると言っているKirkhoffsの原則です。 より具体的には、プロトコル設計に関する一般的な知識を提供します。 意味は非常に単純です。特定のシステムで使用される暗号化アルゴリズムは、その安定性を保証する秘密であってはなりません。 理想的には、暗号化側が攻撃者に完全に知られ、唯一の秘密がこのシステムで使用される暗号化キーであるようにシステムを構築することが必要です。



最新の市販の暗号化システム-すべてまたはほぼすべてまたはそれらの最高のもの-は、デバイスと動作原理がよく知られているコンポーネントから構築されています。 それらの唯一の秘密は暗号化キーです。 私に知られている唯一の重要な例外があります-さまざまな州の組織のための一連の秘密暗号プロトコルです。 米国では、これはNSAスイートBと呼ばれ、ロシアでは、これらはあらゆる種類の奇妙な秘密暗号化アルゴリズムであり、軍や政府機関によってある程度使用されています。



そのようなアルゴリズムがそれらに大きな利益をもたらすとは言いませんが、それはほぼ原子物理学に似ています。 プロトコルの設計を理解して、それを開発した人々の思考の方向を理解し、何らかの方法で反対側を追い抜くことができます。 この原則が今日の基準からどの程度関連しているかはわかりませんが、私よりもそれをよく知っている人はそれだけです。



遭遇するすべての商用プロトコルでは、状況は異なります。 どこでもオープンシステムが使用され、誰もがこの原則を順守しています。



最初の暗号プリミティブは対称暗号です。



それらは非常に単純です。 ある種のアルゴリズムがあり、その入力はプレーンテキストであり、キーと呼ばれるもの、値です。 出力は暗号化されたメッセージです。 暗号化を解除するには、同じ暗号化キーを使用することが重要です。 そして、それを別のアルゴリズムである復号化アルゴリズムに適用して、暗号文からプレーンテキストを取得します。



ここで重要なニュアンスは何ですか？ 発生する可能性のある最も一般的な対称暗号化アルゴリズムでは、暗号文のサイズは常に平文のサイズに等しくなります。 最新の暗号化アルゴリズムは、キーサイズで動作します。 キーのサイズはビット単位で測定されます。 現在のサイズは、対称暗号化アルゴリズムの場合、128〜256ビットです。 ブロックのサイズなど、残りについては後で説明します。



歴史的に、紀元前4世紀には、置換暗号と置換暗号という2つの暗号設計方法がありました。 置換暗号は、当時は何らかの原則に従ってメッセージの1文字を別の文字に置き換えるアルゴリズムです。 単純な置換暗号は、テーブルに従っています。AがIに変更され、BがYuに変更されるなどのテーブルを使用します。さらに、このテーブルで暗号化し、復号化します。



あなたの意見では、キーサイズに関して、このアルゴリズムはどのくらい複雑ですか？ 重要なオプションはいくつありますか？ アルファベットの長さの階乗順。 テーブルを取る。 どのように構築しますか？ 26文字のテーブルがあるとしましょう。 文字Aをそれらのいずれかに、文字Bを残りの25のいずれかに、Cを残りの24のいずれかに置き換えることができます... 26 * 25 * 24 * ...-つまり、26の階乗です。アルファベットの次元の階乗です。



log ₂ 26！を使用すると、非常に多くなります。 私はあなたが間違いなくおよそ100ビットの鍵の長さ、またはそれ以上を得ると思います。 強度の形式的な表現の観点から、指定された暗号化アルゴリズムはかなり良いことが判明しました。 100ビットは許容範囲です。 さらに、おそらく子供の頃や思春期の誰もが、エンコーディングに直面したときに、そのようなアルゴリズムが簡単に解読されることを見ました。 復号化に問題はありません。



長い間、さまざまな設計のあらゆる種類の置換アルゴリズムがありました。 そのうちの1つは、さらに原始的なCaesarの暗号です。テーブルは、文字のランダムな置換ではなく、3文字のシフトによって形成されます。AがDに、BがEに、など。非常に簡単：テーブルの展開とは異なり、Caesarのキーには、アルファベットの26文字のオプションが25個しかありません-それ自体の簡単な暗号化は別です。 そして、それを完全に整理することができます。 ここにはいくつかの困難があります。



テーブル拡張暗号がなぜそんなに単純なのですか？ 暗号化について何も知らなくても、テーブル置換を解読できる問題はどこで発生しますか？ ポイントは周波数分析です。 最も一般的な文字があります-いくつかのIまたはE。それらの有病率は大きく、母音は子音よりもはるかに一般的であり、自然言語では決して発生しない否定的なペアがあります-bのようなもの 私は学生に自動置換暗号デコーダを作成するタスクさえ与えました、そして、原則として、多くは対処しました。



問題は何ですか？ 暗号化されたテキストで一般的な文字が輝かないように、文字の分布の統計を歪める必要があります。 明らかな方法：1文字ではなく、たとえば5つの異なる文字で最も一般的な文字を暗号化しましょう。 文字が平均で5倍頻繁に発生する場合は、順番に見てみましょう-最初に、最初の文字を暗号化し、次に2番目、3番目などを暗号化します。 50.したがって、統計に違反しています。 これは、なんとか機能した多アルファベット暗号の最初の例です。 ただし、かなりの数の問題があり、最も重要なことは、テーブルを操作するのが非常に不便であることです。



さらに思いついたのは、このようなテーブルで暗号化するのではなく、Caesarの暗号を使用して、次の各文字のシフトを変更してみます。 結果はVigenere暗号です。



ヴァシャという言葉をキーにしています。 MASHAというメッセージを受け取ります。 シーザーの暗号を使用しますが、これらの文字から数えます。 たとえば、Bはアルファベットの3番目の文字です。 クリアテキスト内の対応する文字を3文字シフトする必要があります。 MはAのP. Aに移動します。Sh-16文字でAをジャンプし、条件付きでDを取得します。AをYに移動します。



結果の暗号で便利なものは何ですか？ 2つの同一の文字がありましたが、その結果、それらは異なる文字で暗号化されました。 これは、統計が不明瞭になるため、素晴らしいです。 この方法は19世紀頃までうまく機能しましたが、ごく最近、暗号の歴史の背景に対して、彼らはそれを破る方法を見つけました。 数十語のメッセージを見て、キーが非常に短い場合、デザイン全体はシーザーの暗号のように見えます。 私たちは言います：さて、4文字ごとに-最初、5番目、9番目-Caesarのコードと考えてみましょう。 そして、統計パターンを探してください。 間違いなく見つかります。 次に、2番目、6番目、10番目などを取ります。 もう一度検索します。 これにより、キーが復元されます。 唯一の問題は、その長さを理解することです。 それほど難しくありませんが、どれくらいの長さですか？ よく4、よく10文字。 4〜10の6つのオプションを選択するのはそれほど難しくありません。 簡単な攻撃-ペンと紙を犠牲にして、コンピューターなしで利用できました。



このことから解読不可能な暗号を作る方法は？ テキストサイズキーを取得します。 20世紀に1946年にクロードシャノンという名前のキャラクターが、数学の一分野として暗号に関する古典的な最初の研究を書き、そこで定理を定式化しました。 キーの長さはメッセージの長さと同じです-彼はアルファベットの長さに等しいモジュロ加算の代わりにXORを使用しましたが、この状況ではあまり重要ではありません。 キーはランダムに生成され、ランダムビットのシーケンスであり、出力もビットのランダムシーケンスを取得します。 定理：そのような鍵があれば、そのような設計は完全に安定しています。 証明はそれほど複雑ではありませんが、今は説明しません。



解読不能な暗号を作成できることが重要ですが、欠陥があります。 まず、キーは完全にランダムでなければなりません。 第二に、再利用することはできません。 第三に、キーの長さはメッセージの長さと等しくなければなりません。 同じキーを使用して異なるメッセージを暗号化できないのはなぜですか？ なぜなら、次回このキーを傍受すると、すべてのメッセージを解読できるからでしょうか？ いや Caesarのコードは最初の文字に表示されますか？ よくわかりません。 いいえ、そうです。



BASKYキーで暗号化されたMASHAと、BASKYキーも持つもう1つの単語がFAITHです。 私たちは以下について得ます：ZESHA。 2つのキーが相互に削除されるように、受信した2つのメッセージを合計します。 結果として、意味のある暗号文と意味のある暗号文の違いのみを取得します。 XORでは、これはアルファベットの長さを合計するよりも便利ですが、実際には違いはありません。



2つの意味のある暗号文の違いがわかると、自然言語のテキストの冗長性が高くなるため、原則として後でかなり簡単になります。 多くの場合、さまざまな仮定、仮説を立てることで何が起こるかを推測できます。 そして最も重要なことは、それぞれの真の仮説が鍵の一部を明らかにし、したがって2つの暗号文の断片を明らかにすることです。 そのようなもの。 したがって、悪い。



順列暗号に加えて、順列暗号もありました。 それらでも、すべてが非常に簡単です。 メッセージVASYAIを取得して、たとえばDIDOMなどの長さのブロックに書き込み、同じ方法で結果を読み取ります。



神は何かを知らない。 それを破る方法も理解できます-すべての可能な置換オプションをソートします。 それらの多くはありません。 ブロックの長さを取得し、選択して復元します。



次の反復として、この方法が選択されました。すべて同じものを取得し、その上にいくつかのキー-SIMONを書き込みます。 文字がアルファベット順に表示されるように列を再配置します。 その結果、キーによる新しい順列を取得します。 順列の数がはるかに多く、それを拾うことは必ずしも容易ではないため、すでに古いものよりもはるかに優れています。



現代の暗号は、何らかの形で、置換と置換という2つの原則に基づいています。 現在、それらの使用ははるかに複雑ですが、基本的な原則自体は同じままです。



最新の暗号について話すと、それらはストリームとブロックの2つのカテゴリに分類されます。 ストリーム暗号は、実際に乱数ジェネレーターであるように設計されており、その出力には、スライドに見られるように、暗号テキストでモジュロ2、「Xorim」を追加します。 先ほど、私が言った：結果のキーストリームの長さ（同じキー）が完全にランダムで、再利用されず、その長さがメッセージの長さと等しい場合、絶対的に強力な暗号があり、解読不能です。



問題は、このような暗号でランダムで長くて永遠の鍵を生成する方法ですか？ ストリーム暗号はどのように機能しますか？ 実際、これらは何らかの初期値に基づいた乱数ジェネレーターです。 初期値は暗号鍵、答えです。



この話には興味深い例外が1つあります。暗号ノートです。 これは本当のスパイ行為に関する本当のスパイ物語です。 絶対に安定したコミュニケーションを必要とする一部の人々は、乱数を生成します。たとえば、文字通りダイを投げたり、宝くじのようにドラムからボールを​​取り出したりします。 これらの乱数が印刷される2つのシートを作成します。 1枚は受信者に渡され、2枚目は送信者に残されます。 話したい場合は、この乱数のストリームをキーストリームとして使用します。 いいえ、物語は非常に遠い過去から取られていません。 2014年10月15日の実際の無線傍受があります：7 2 6、7 2 6、7 26。これはコールサインです。 4 8 3、4 8 3、4 8 3.これは暗号ブロック番号です。 5 0、5 0、50。これはワード数です。 8 4 4 7 9 8 4 4 7 9 2 0 5 1 4 2 0 5 1 4など50のそのような数値グループ。 ロシアのどこかで、普通のラジオでペンと鉛筆を使って座っていて、これらの数字を書き留めた人がどこにいるかはわかりません。 それらを書き留めて、彼は同様のものを取り出し、それらを10を法として折り畳み、彼のメッセージを受け取りました。 言い換えれば、それは本当に機能し、そのようなメッセージはハッキングできません。 本当に良い乱数が生成され、その後彼がキーで紙を燃やした場合、あなたはまったくそれを行うことができません。



しかし、かなりの数の問題があります。 1つ目は、本当に良い乱数を生成する方法です。 私たちの周りの世界は決まっています。コンピューターについて話せば、それらは完全に決まっています。



第二に、このサイズのキーを配信する... 55のデジタルグループからメッセージを送信する場合、これを行うことはそれほど難しくありませんが、数ギガバイトのテキストを転送することはすでに深刻な問題です。 したがって、実際には、いくつかの小さな初期値に基づいて擬似乱数を生成し、そのようなストリームアルゴリズムとして使用できるアルゴリズムが必要です。



この種の最も歴史的に普及しているアルゴリズムはRC4と呼ばれます。 約25年前にRon Rivestによって開発され、非常に長い間使用されてきました。これはTLSの最も一般的なアルゴリズムであり、HTTPSを含むさまざまなオプションがすべてありました。 しかし、最近、RC4はその年齢を示し始めました。 彼には多くの攻撃があります。 WEPで積極的に使用されています。 Antonによる優れた講義が1つありました。今日の標準でさえ、まともな暗号化アルゴリズムの不適切な使用は、システム全体が危険にさらされるという事実につながります。



RC4は簡単です。 このスライドは彼の作品を完全に説明しています。 256バイトの内部バイト状態があります。 この状態の各ステップには、状態内の異なるバイトへの2つのポインターという2つの数字があります。 そして、各ステップでこれらの数字の間に追加があります-それらは州のある場所に置かれます。 そこから受信したバイトは、数値シーケンスの次のバイトです。 この方法でこのノブを回転させ、各ステップで同様のアクションを実行すると、次のバイトがすべて取得されます。 ストリーム内で、数値シーケンスの次のバイトを永久に取得できます。



RC4の大きな利点は、完全にバイト幅であるということです。つまり、そのソフトウェア実装は、DESコードよりもはるかに速く、数倍、10倍ではないにしても、ほぼ同等に存在していたことを意味します。 したがって、RC4とそのような配布を受け取りました。 彼は長い間RSAの企業秘密でしたが、その後、90年代のどこかで、サイファーパンクのメーリングリストで彼のデバイスのソースコードを匿名で公開した人もいました。 その結果、多くのドラマがあり、叫び声がありました、彼らは言う、どのように、いくつかの無作法な人々がRSAの知的財産を盗み、それを公開しました。 RSAはすべての特許、あらゆる種類の法的訴追を脅かし始めました。 それらを避けるために、オープンソースにあるアルゴリズムのすべての実装はRC4ではなく、ARC4またはARCFOURと呼ばれます。 A-申し立て。 これは暗号であり、すべてのテストケースでRC4と一致しますが、技術的には一致しないようです。



SSHまたはOpenSSLを構成する場合、RC4は見つかりませんが、ARC4などが見つかります。 シンプルなデザインで、すでに古く、攻撃されているため、使用はあまりお勧めしません。



それを置き換えるいくつかの試みがありました。 おそらく、私の偏見では、Salsa20暗号と、狭い範囲で広く知られているDan Bershteinの性格からの彼のフォロワー数人が最も成功したと思われます。 Linuxでは、彼は一般にqmailの作者として知られています。



Salsa20はDESよりも複雑です。 そのブロック図は複雑ですが、いくつかの興味深いクールなプロパティがあります。 まず第一に、それは常に各ラウンドで有限時間実行されます。これはタイミング攻撃に対する保護にとって重要です。 これらは、攻撃者が暗号化システムの動作を観察し、このブラックボックスに異なる暗号文または異なるキーを送り込む攻撃です。 また、システムの応答時間または電力消費の変化を理解し、内部で発生したプロセスを正確に把握することができます。 攻撃が非常に手に負えないと考える場合、これはそうではありません。 この種のスマートカードへの攻撃は非常に広範囲に及びます-攻撃者はボックスに完全にアクセスできるため、非常に便利です。 原則として彼ができないのは、キー自体を読み取ることだけです。 これは難しいですが、彼は残りを行うことができます-そこに異なるメッセージを送信し、それらを解読しようとします。



Salsa20は、常に同じ一定時間実行されるように設計されています。 : , 2 32, 32- . Salsa20 , RC4. — cipher suite TLS, Salsa20, — . eSTREAM . , Salsa — . -. , — , — cipher suite TLS Salsa20. .



, . , , 2 ⁶⁴ . . , , .



? , , . , . — . , , . 便利に。



, , , 10 , 1 , 10 . .



Salsa , , . 20 . 20 — 512 .



— 8 . 256-, 8 — 250 251 . , , . . , , .



. , . , .



? : , Salsa, , , . . .



, — .



, . . , - .



. -. , , — . , , .



— , 128 . , , 128 256 , . — , : 128 256 , .



— DES AES. DES , RC4. DES — 64 , — 56 . IBM . IBM , 128 . , 124 192 .



DES , . 64 56 .



20 . — , , , . DES , , .



. . , . , 56 .



DES? , . . , , : . . , . .



. : F . , . .



: , . , .



? 30 , . , .



— , 16 . 16 16 , F.



— - . : 32 , , 32 . 32 , 48: , .



, — 48 , 48- .

, S- . , 48 32 .



, P. 32 . , .



S-: 6 4. , , XOR . S- , DES . , , . DES : .



S-, . , . , 10 , DES , — . : — , , 0 1 — , . , 0 1 . , DES, , , . : , 10 , , .



S- . , : S-. , .



56 — , . そしてこれは悪いです。 ?



: . Triple DES. : , . .



, . , k1 k2 k3, . , DES . , .



, 56 . — k1 k2. 56 + 56 = 112 . 112 — . , 100 . , 112 ?



DES 16 . 16 . 16 . — . , k3, , k1 k2.



. - , . , 2 ⁵⁶ . - . 2 ⁵⁶ — — k1 k2, .



— 112 , 57, . , . — , : k1, k2, k3. Triple DES. -. DES — , : , — .



Triple DES DES. .



DES? . TLS, cipher suite TLS, Triple DES DES. , . .



, , . , , . , , PIN, — . , PIN, PIN-. — , DES. , , Triple DES, DES.



DES , , . , NIST, : . AES.



DES digital encrypted standard. AES — advanced encrypted standard. AES — 128 , 64. . AES — 128, 192 256 . AES , , . 128 10 , 256 — 14.



, . — .



DES, AES . . AES , DES. 128- , 10 10 . , DES, .



. — .



AES 4 4. — . 16 128 . AES .



— .



, . 4 4. , 1 , — 2 , — 3, .



. . , . .



, — XOR . .



, . :



, . .



4 10 , 128- 128- .



AES? , , DES. AES . AES DES , AES , .



, Intel AMD, AES , . — AES . DES , , 1-2 , 10- AES- .



. 128 64 128 64 .



, , 16 ?



, , — , , , , .



, , 16 . ECB — electronic code boot, 16 AES 8 DES .



, , .



, ECB. , , , . 問題は何ですか？ , . , — .



- , , — , . CBC.



, , . . .



, 2 . — . 2 . — . 2 . . : .



, , , , . . .



CBC .



ブロックサイズについて。想像してみてください。暗号化を開始しました。DESがあるとします。DESが完全な暗号化アルゴリズムである場合、DES出力は、均等に分散された64ビット長の乱数のように見えます。64ビット長の一様に分布した乱数のサンプルで、1つの操作で2つの数値が一致する確率はどのくらいですか？1 /（2 ⁶⁴）。そして、3つの数値を比較すると？今はやめましょう。