グラフィカルな説明 | RSAアルゴリズムとは

[[339878]]

この記事はWeChatパブリックアカウント「Backend Technology Compass」から転載したもので、著者はCompass Krypton Gold Entranceです。この記事を転載する場合は、Backend Technology Compass の公開アカウントにお問い合わせください。

1. 数学と暗号の美しさ

少し前に、何もすることがなかったので「The Beauty of Mathematics」を読みました。第 17 章では、テレビ シリーズ「The Counterfeiter」で展開された暗号化の背後にある数学的原理がいくつか説明されています。

この本には、シーザー暗号から第二次世界大戦における連合軍と日本軍、暗号における一様分布と統計的独立性の基本理論まで、あらゆることが書かれていました。興味深く読みましたが、細かいところが理解できなかったので、記事を書くことにしました。

2. 暗号化アルゴリズムの歴史

一般的な暗号化アルゴリズムには、対称暗号化と非対称暗号化があることはご存じのとおりです。今日の主役は非対称暗号化です。

非対称暗号化は一夜にして開発されたわけではありません。1976 年以降に登場しました。非対称暗号化は対称暗号化の最適化であると言えます。

2.1 対称暗号化の欠点

対称暗号化とは、送信者がルールを使用して情報を処理し、受信者が同じルールを使用して情報を逆処理する必要があることを意味します。

対称暗号化では、通信する双方が暗号化と復号化に同じルールとキーを使用する必要があるため、キーとルールを適切に保持することが非常に重要です。

キーが漏洩すると、最も強力な対称暗号化アルゴリズムも役に立たなくなるため、対称暗号化ルールとキーを安全に交換する方法が問題となります。

安全に鍵を交換するにはどうすればいいでしょうか? 頭が痛い問題です。

2.2 鍵交換アルゴリズム

1976 年、2 人のアメリカのコンピューター科学者、ホイットフィールド ディフィーとマーティン ヘルマンが、鍵を送信せずに暗号解読を完了できる新しいアイデアを提案しました。非常に強力に思えます。これは伝説の「遠くから雄牛を撃つ」ことでしょうか。

[[339882]]

実際、これは Diffie-Hellman 鍵交換アルゴリズムと呼ばれています。Wikipedia でこの 2 人の偉大な神の紹介を見てみましょう。

この 2 人の偉大な人物は暗号化の先駆者であり、非対称暗号化アルゴリズムの明確な道筋を示しました。つまり、両者が直接鍵を交換する必要がないのです。

Diffie-Hellman 鍵交換アルゴリズムでは、通信当事者は実際に鍵を交換するのではなく、計算によって同一の共有鍵を生成します。具体的なプロセスは比較的複雑なので、ここでは詳しく説明しません。

非対称暗号化アルゴリズム RSA はこのアイデアを利用し、公開鍵と秘密鍵を使用して暗号化と復号化を完了しますが、鍵の送信は避けます。RSA アルゴリズムの公開鍵は公開されており、公開鍵で暗号化された情報は、対応する秘密鍵を使用して復号化する必要があります。

3. RSAアルゴリズム

RSA アルゴリズムは、おそらく地球上で最も重要なアルゴリズムの 1 つであり、データ通信とネットワーク セキュリティの基礎となっています。

3.1 アルゴリズム作成者

RSA は、1977 年に Ron Rivest、Adi Shamir、Leonard Adleman によって提案されました。

当時、3人はマサチューセッツ工科大学に勤務しており、彼らの名字の頭文字を組み合わせてRSAが結成されました。

[[339883]]

RSA アルゴリズムのキーが長いほど、解読が難しくなります。関連文献によると、これまでに解読された最長の RSA キーは 768 バイナリ ビットです。一般的に、1024 ビットの RSA キーは基本的に安全であり、2048 ビットのキーは極めて安全であると考えられており、RSA アルゴリズムは現在 4096 ビットの長さをサポートしています。

キーの長さは暗号化と復号化の時間に比例するため、自分のシナリオに応じてキーの長さを選択する必要があり、長いキーを追求する必要はありません。

3.2 アルゴリズムのプロセス

RSA アルゴリズムの本質は数学です。公開鍵と秘密鍵は数学的に関連しており、直接送信する必要はありません。

アルゴリズムのプロセスには、キーの生成とキーの暗号化および復号化が含まれます。

3.2.1 キー生成

RSA アルゴリズムのキーはペアになっており、公開キーは暗号化用、秘密キーは復号化用です。このキーのペアがどのように計算されるかを見てみましょう。

• 1. 2つの素数PとQをランダムに選択する

P=61、Q=53を選択し、PQの積N=PQ=61*53=3233を計算し、Nを2進数110010100001に変換します。Nの2進数の長さは12、つまりキーの長さは12です。

この記事では、アルゴリズムの原理についてのみ説明します。実際には、安全であるためにはキーの長さが 1024 ビット以上である必要があり、12 ビットは基本的に単なるデモンストレーションです。

• 2. Nのオイラー関数値Mを求める

オイラー関数の定義: 任意の正の整数 n が与えられたとき、n と互いに素である n 以下の正の整数はいくつありますか?

オイラー関数には一般的な計算式があります:

オイラー関数を証明するには、それを多くのケースに分割する必要があります。特に、n が素数の場合には、いくつかの特殊なケースが発生します。

早速結論を述べましょう。

a. kが素数の場合、φ(k) = k-1となる。

b. n = P * Qで、PとQが両方とも素数の場合、φ(n) = φ(P * Q) = φ(P)φ(Q) = (P - 1)(Q - 1)となります。

P=61、Q=53、N=3233の場合、Nのオイラー関数はM=(P-1)*(N-1) = 60*52=3120と記録されます。

• 3. Mと互いに素な整数Eを見つける

MとEは1（互いに素）とE以外に共通の約数を持たない。

• 4. 次の関係を満たす整数 D を見つけます。

(E*D) mod M = 1。言い換えれば、EとDの積をMで割った余りは1です。ここには逆数モジュラーという用語があり、これはedをφ(n)で割った余りが1になるような整数dが存在することを意味します。

これは次の計算プロセスと同等です。

E=17、M=3120、K=1、2、3...の場合、

17*D - K*M = 1。この方程式を解くと、関係を満たす D と K のセットを見つけることができます。セットの 1 つは (D,K)=(2753,15) であることが証明できます。

まとめると、互いに素な P と Q をランダムに選択することで、N、M、E、D を計算できることがわかりました。これらの数字を 2 つのグループに分けます。(E、N) と (D、N) はそれぞれ公開鍵グループと秘密鍵グループで、E は公開鍵、D は秘密鍵です。

この例では、公開鍵グループは (E, N) = (17, 3233)、秘密鍵グループは (D, N) = (2753, 3233) です。次に、この鍵のペアを暗号化と復号化に使用します。

3.2.1 暗号化プロセス

RSA アルゴリズムの本質はデジタル演算であるため、暗号化する前に文字列を数字に変換する必要があります。文字列を数字に変換するには、ASCII コード、Unicode エンコーディング、UTF-8 エンコーディングなどを使用できます。

変換された数値 X はキー グループ内の N より小さくする必要があることに注意することが重要です。文字列変換後の数値が N より大きい場合は、分割する必要があります。これが、データ量が大きい場合に、コンテンツの暗号化に対称暗号化アルゴリズムを使用し、キーの暗号化に非対称暗号化アルゴリズムを使用する理由であると考えられます。

暗号化プロセスは次の要件を満たします。

X^E 法 N = Y

ここで、X は平文、E は公開鍵、N は大きな整数、Y は暗号文、mod は剰余演算です。

3.2.3 復号化プロセス

暗号文 Y を取得した後、復号化を開始します。このプロセスは次の条件を満たします。

Y^D 法 N = X

ここで、Y は暗号文、D は秘密鍵、N は大きな整数、X は平文、mod は剰余演算です。

上記の暗号化および復号化プロセスには、フェルマーの小定理が関係しています。

3.2.4 オイラーの定理とフェルマーの小定理

これは少しわかりにくいですが、確かに RSA アルゴリズムの中核部分です。簡単に見てみましょう。

フェルマーの小定理は素数検出の特性を示し、オイラーはそれを証明しました。これがフェルマー-オイラーの定理です。

3.3 RSAアルゴリズムの信頼性分析

上記のキー生成、暗号化、復号化のプロセスの後、次の疑問が生じます。RSA アルゴリズムは信頼できるのでしょうか? 秘密キー D は公開キー グループ (E、N) から導出できるのでしょうか?

整理してみましょう:

• ed≡1 (mod φ(N)) なので、d は e と φ(N) がわかっている場合にのみ計算できます。e は公開鍵なので、φ(N) のみを知っていれば十分です。
• オイラー関数 φ(N)=(P-1)(Q-1) によれば、P と Q がわかって初めて φ(N) を計算できます。
• N=pq。N を因数分解することによってのみ、P と Q を計算できます。

したがって、大きな数 N を因数分解できれば、秘密鍵 D を計算して暗号文を解読することができます。

3.5 大きな整数の因数分解

大きな整数を因数分解することは極めて難しく、NPC 問題です。ブルート フォース クラッキング以外に良い解決策はありません。現在、人間が分解できる 2 進数の最大長は 768 ビットであり、1024 ビットの長さはまだ解読されていないため、1024 ビットの 2 進キーは安全です。

したがって、RSA アルゴリズムの安全性は、大きな整数の因数分解の難しさによって決まります。現在、RSA アルゴリズムは 4096 ビットのキー長をサポートしており、分解の難しさは想像を絶するものです。量子コンピューターの助けを借りても、難しさと時間は非常に高くなります。

4. 結論

この記事では、対称暗号化アルゴリズムによる鍵転送のセキュリティから始め、RSA アルゴリズムの公開鍵と秘密鍵のヒントとなった鍵交換ネゴシエーションのための Diffie-Hellman アルゴリズムについて説明します。

MIT の 3 人の数学者が、オイラーの定理やフェルマーの定理などの数学的な定理に基づいて、優れた RSA 非対称暗号化アルゴリズムを作成しました。

RSA アルゴリズムのセキュリティは、大きな数の素因数分解の難しさによって決まります。現在、人間は 1024 ビットのバイナリ キーを解読できません。セキュリティ上の理由から、暗号化には 2048 ビットの RSA キーを使用できます。

まさにハードコアな脳トレコンテンツです。素数って本当に魔法のようなものだなとため息をつくしかありません。私のレベルは限られているので、いくつかアイデアを出すことしかできません。以上です！