RSAは過去2世紀で最も重要なアルゴリズムの1つです

Diffie-Hellman暗号化アルゴリズムの欠点

[[225219]]

前回の記事では、Diffie-Hellman 鍵交換アルゴリズムについて説明しました。 (鍵交換はやや安全ではありません)。AES や DES などの対称暗号化アルゴリズムを使用して暗号化するために鍵を安全に交換することはできますが、大きな問題があります。ちくしょう、1人と通信するなら1つの鍵を節約しなくてはならないし、100人と通信するなら100個の鍵を節約しなくてはならない。遅かれ早かれAは崩壊するだろう。

キークラッシュ

RSAアルゴリズムの起源

そこで科学者たちは、鍵の数を減らすことはできるだろうかと考え始めました。 ?その時、上司は路上の郵便受けを思いつきました。

メールボックスは誰でも手紙を投函（情報を届ける）できる公共の場ですが、メールボックスを所有するメールボックス管理者だけがそれを開いて手紙を収集（情報を得る）することができます。

ただし、この例はあまり適切ではありません。しかし、一般的な考え方としては、公開暗号化キーを他の人に配布し、その人がそれを使用して暗号化し、秘密キーを持つ人だけが復号化できるようにすることは可能でしょうか?

RSA アルゴリズムについて学びましょう。

RSAA の

RSA は、1977 年に Ron Rivest、Adi Shamir、Leonard Adleman によって提案されました。当時、彼ら3人は全員MITで働いていました。 RSA は姓の最初の文字で構成されています。

しかし、RSA アルゴリズムは 1977 年に発明されたわけではありません。1973 年という早い時期に、英国通信局の数学者であるクリフォード コックスが同様のアルゴリズムを発見しました。彼の研究が発見されると、すぐに極秘と分類され、1998 年まで公開されませんでした。

RSA アプリケーション

RSA 暗号化アルゴリズムは、前世紀と今世紀で最も重要なアルゴリズムの 1 つであると言っても過言ではありません。RSA は、大きな数の因数分解に基づく非対称暗号化アルゴリズムです。デジタル署名、データ暗号化などの分野で広く使用されています。データ署名とデータ暗号化の両方を実行できる最初のアルゴリズムです。つまり、実際には公開鍵と秘密鍵は相対的な概念です。心配しないでください。このアルゴリズムは双方向です。公開鍵で暗号化されたデータは、秘密鍵でのみ復号化できます。秘密鍵で暗号化されたデータは、公開鍵でのみ復号化できます。このように、データ転送に公開鍵暗号化を適用すると暗号化（安全でないチャネルでのデータ転送の暗号化）になり、データに秘密鍵暗号化を適用するとデータ署名（特定のデータが本当に A から送信されたものかどうかを確認する）になります。

RSAの仕組み

さて、私自身を表現するために、実際に自分でやったので、証明のプロセスを説明させてください。

アルゴリズムは 5 つのステップに分かれています。

1. 比較的大きな素数pとqを選ぶ

2. n = p * qとします。 φ(n)を取る（オイラー関数はBaiduで入手可能）、

3. e ∈ 1 < e < φ(n), (n, e)を公開鍵ペアとしてとる

4. ed mod φ(n) = 1としてdを得る。(n, d)は秘密鍵ペアである。

5. p と q を破壊します。暗号文 = 平文 ^ e mod n、平文 = 暗号文 ^ d mod n

まあ、アルゴリズムはそれほど単純です。しかし、実際には簡単に証明できます。

(プレーンテキスト^ e mod n)^d mod n = (プレーンテキスト^ d mod n)^e mod n

RSA はどのように安全ですか?

どうやって解読するの？アルゴリズムはどのようにしてセキュリティを確保するのでしょうか?

上記の処理を実行すると、p、q、n、φ(n)、e、d などの多くの数値が出現することがわかります。では、秘密鍵 d を解読するにはどうすればよいでしょうか? ?

ステップ1: e*d mod φ(n) = 1。

φ(n)が既知でeが公開されている場合、dは復号化されます。

ステップ2: φ(n) = φ(p * q) = φ(p) * φ(q) = (p-1)(q-1)

さて、pqがわかれば、φ(n)も計算できます。

ステップ3: pとqを知るにはどうすればいいですか? n = p * q です。

公開データ n を因数分解すると、p と q が得られます。しかし現在、大きな数を因数分解することは世界的に大きな問題となっています。したがって、RSA キーが漏洩しない限り、情報は安全です。

RSA はなぜ暗号化および復号化できるのですか?

以下は、上記のアルゴリズムが暗号化と復号化に使用できる理由を証明します。平文が m (メッセージ)、暗号文が c (暗号化) であると仮定します。

暗号化プロセス
 
 c = m^e 法 n 
 
復号化プロセス: 
 
メートル
 
 = c ^ d mod n （cを代入） 
 
 = (m ^ e mod n)^ d mod n (モジュラー変換) 
 
 = m ^ (e * d) を法としてn 
 
 ∵ e * d mod φ(n) = 1 
 
 ∴e * d = k * φ(n) + 1 (kは整数) 
 
 ∴ 
 
メートル
 
 = m ^ (k * φ(n) + 1) 法 n 
 
 = m ^ (k * φ(n)) * m mod n 
 
 mとnが互いに素であれば、m ^ (k * φ(n)) mod n = 1（オイラーの公式）

すると、上記の式は m に直接等しくなります。元の質問は証明されました。元の RSA 論文では、m と n が互いに素である場合についてのみ説明されていましたが、Ruan Yifeng 教授は別のケース、つまり、m と n が互いに素でない場合はどうなるかというケースも証明しました。 ?この状況については上で証明しましたので、興味のある方はぜひご覧ください。

[この記事は51CTOコラムニスト「Da Jiao」によるオリジナル記事です。転載する場合は著者のWeChat公開アカウント「A Programmer Named Da Jiao」から許可を得てください。]

この著者の他の記事を読むにはここをクリックしてください