RSA という高度な暗号化アルゴリズムをご存知ですか?

以前、RSA アルゴリズムの説明をしてほしいと頼まれたことがあります。今日は私が学んだことに基づいて説明します。まず、RSA について理解しましょう。

RSA は、1977 年に Ronald Rivest、Adi Shamir、Leonard Adleman によって提案された非対称暗号化アルゴリズムです。そのため、この非対称暗号化アルゴリズムは、3 人の姓の頭文字をとって RSA アルゴリズムと名付けられました。

[[359956]]

非対称暗号化を理解するには、対称暗号化とは何かを理解する必要があります。ツイ・ハーク監督の映画「虎山を攻略せよ」の中のセリフについてお話しましょう。

• 盗賊：天の王と地の虎！
• 楊子栄：塔が川の怪物を鎮圧する！
• 山賊: キジは頭を下げたまま、どうやって山を登れるんだ？
• 楊子栄：地面には米がたっぷりある。ほら、基礎があるじゃないか！
• 盗賊: 私の母に会ったことがありますか?
• 楊子栄：彼の家の屋根には瓦が積まれていない。いやいやいやいや！

彼らの会話から、盗賊たちが楊子栄の正体を試していることがわかります。賊が「天王が地を覆い、虎がそれをする」と言うとき、私は「塔が河の怪物を抑える！」と言わなければなりません。つまり、双方ともこの文の意味を理解しています。プログラマーの用語に翻訳すると、これは両方の当事者が暗号化キーを持っていることを意味します。そのため、対称暗号化は秘密トレーダーのための秘密コードとも言えます。

しかし、対称暗号化には大きな問題があります。それは、鍵が簡単に漏洩してしまうことです。楊子栄は盗賊たちの秘密のコードを知っていたので、彼らの信頼を得るのは簡単でした。

RSA暗号化

数学の先生に返す知識を事前に確認する必要があります。

オイラー関数

数論では、正の整数 n があり、n より小さく n と互いに素な正の整数の数は n のオイラー関数と呼ばれ、φ(n) と表記されます。例えば：

• φ(7) 7には7より小さく、7と互いに素な数が6つあります。1、2、3、4、5、6です。したがって、φ(7)=6です。
• φ(8) 8には8より小さく8と互いに素な数が4つある：1、3、5、7、したがってφ(8)=4である。
• φ(9) 9には9より小さく9と互いに素な数が7つある：1、2、4、5、6、7、8、したがってφ(9)=7。

一般式（PはNの素因数）

• φ(10)=10×(1-1/2)×(1-1/5)=4;
• φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
• φ(49)=49×(1-1/7)=42です。

mn が互いに素である場合: φ(n * m)=φ(n)* φ(m)、n が素数である場合、φ(n)=n-1。

因数分解して評価します: φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 - 2^1 ) * (3^1 - 3^0)=4。

オイラーの定理

2 つの正の整数 m と n が互いに素である場合、n に関する m の φ(n) 乗の係数は 1 に等しくなります。 m^φ(n)%n≡1です。

フェルマーの小定理

素数 p が存在し、整数 a が p の倍数でない場合、a^(p-1)%p≡1 が存在します。フェルマーの小定理はオイラーの定理の特殊なケースです。なぜなら、φ(p)=p-1 だからです (任意の数は素数と互いに素です)。

モジュラーアンチエレメント

2 つの正の整数 e と x が互いに素である場合、ed-1 が x で割り切れる整数 d が存在する必要があり、d は x に関する e のモジュラー逆元と呼ばれます。 e * d % x≡1 ならば、e * d ≡ k*x+1 です。

上記の定理から次の式が導かれます。

1. m^φ(n)%n≡1
2. m^(k * φ(n))%n≡1 両端にmを掛ける
3. m^(k * φ(n)+1)%n≡m
4. e * d ≡ k * x + 1
5. m^e * d%n≡mはステップ3 k * φ(n)+1を置き換える

そして、m^e*d%n≡m は、必要な非対称暗号化式です。 m はプレーンテキスト、e と d はそれぞれ公開鍵と秘密鍵に対応します。 Diffie Kalman 鍵交換式の詳細:

• m^e%n=c 暗号化
• c^d%n=m 復号化

ここで、c は e によって暗号化された暗号文であり、平文 m は d によって復号化できます。したがって：

• 公開鍵: e, n
• キー: d、n
• プレーンテキスト: m
• 暗号文: c

RSA暗号化プロセス

1. 2つの素数p1とp2を取ります。
2. n の値を決定します。n = p1 * p2 です。n の値は一般に非常に大きく、長さは一般に 1024 バイナリ ビットです。
3. φ(n)を決定する、φ(n)=(p1-1) * (p2-1)；
4. eの値を決定する、1
5. d値を決定する、e*d%φ(n)=1;
6. 暗号化 c=m^e%n;
7. 復号化されたm=c^d%n。

実際の検証：

1. p1=3、p2=7;
2. n=p1 * p2=3 * 7=21;
3. φ(n)=(p1-1) * (p2-1)=2*6=12;
4. 1
5. e * d % φ(n)=5 * d % 12=1なので、d=17;
6. 平文をm=3に設定すると、c = m^e % n = 3^5 % 21=12;
7. 復号された暗号文 m=c^d % n=12^17 % 21=3。

上記の説明から、RSA 暗号化には 6 つのパラメータが使用されることがわかります。

 1ページ目 
 2ページ目 
ん 
 φ(n)  
 e  
 d

これら 6 つの数字のうち、2 つ (n と e) は公開鍵で使用され、残りの 4 つの数字は公開されません。最も重要なのは d です。なぜなら、n と d は秘密鍵を構成するからです。d が漏洩すると、秘密鍵も漏洩します。

では、n と e がわかっている場合、d を推測することは可能ですか?

1. e*d%φ(n)=1 (eとφ(n)がわかっている場合にのみdを計算できます。)
2. φ(n)=(p1-1) * (p2-1) （φ(n)はp1とp2がわかっている場合にのみ計算できます。）
3. n=p1*p2 (n を因数分解することによってのみ、p と q を計算できます。)

結論: n を因数分解できる場合、d を計算できるため、秘密鍵が解読されたことになります。

しかし、大きな整数を因数分解するのは非常に難しい作業です。現時点では、ブルートフォースクラッキング以外の有効な方法は見つかっていない。 Wikipedia には次のように記されている:

「非常に大きな整数を因数分解する難しさが、RSA アルゴリズムの信頼性を決定します。言い換えれば、非常に大きな整数を因数分解するのが難しいほど、RSA アルゴリズムの信頼性が高くなります。」

誰かが高速因数分解アルゴリズムを発見した場合、RSA の信頼性は大幅に低下します。しかし、そのようなアルゴリズムが見つかる可能性は非常に低いです。現在、ブルートフォース攻撃に使用できるのは短い RSA キーのみです。 2008 年現在、RSA アルゴリズムを攻撃する信頼できる方法はありません。

キーの長さが十分に長い限り、RSA で暗号化された情報は事実上解読不可能です。 「

おそらく、これを読んでもまだ信じられないでしょう。プログラムを書いて、一つずつ解読してみることはできないでしょうか。たとえば、21 は 3×7 にすぐに分解できるかもしれません。しかし、もう少し大きい数字、たとえば素数 2^57,885,161-1 の場合は、桁数が 1,700 万を超えます。従来のコンピューターで素数かどうかを検証すると、おそらく永遠にかかるでしょう。