PythonはRSAアルゴリズムを実装します

この記事の例では、Python での RSA アルゴリズムの実装について説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

1. 基本的な数論

1. 逆素関係

• 2 つの正の整数に 1 以外の共通約数がない場合、これら 2 つの数値は 共素 と呼ばれます。たとえば、15 と 32 には共通約数がないため、互いに素です。これは、素数でなくても互いに素の関係を形成できることを示しています。

2. オイラー関数

• 定義: 任意の正の整数 n が与えられたとき、n 以下の正の整数のうち、n と互いに素の関係にあるものはいくつありますか? （例えば、1～8のうち、8と互いに素の関係にある数はいくつありますか？） この値を求める方法をオイラー関数といい、φ(n)で表されます。

• オイラー関数とその性質の求め方:

1. 素数 p の場合、φ(p)=p-1、 2 つの素数 p、q、φ (pq)= pq-1, オイラー関数は積分関数ですが、完全な積分関数ではありません

2. 正の整数 N の素数分解の場合、N=P1^q1*。 P2^q2*.. .*Pn^qn、すると φ(N)=N*(1-1/P1)*(1-1/P2)*…*(1-1/Pn).

3. N= 2 を除き、φ(N) はすべて偶数です

4. n が 2 つの互いに素な整数の積 n = p1 × p2 に分解できる場合、φ(n) = φ( p1p2) = φ(p1) φ(p2)

2. RSA暗号化

最初のステップは、2つの等しくない素数pとqをランダムに選択することです。

アリスは 61 と 53 を選びました。 (実際のアプリケーションでは、これら 2 つの素数が大きいほど、解読は難しくなります。)

2 番目のステップは、p と q の積 n を計算することです。

アリスは61と53を掛けただけです。

n = 61×53 = 3233

nの長さが鍵の長さです。 3233 を 2 進数で書くと 110010100001 となり、合計 12 桁になりますので、キーは 12 桁になります。実際のアプリケーションでは、RSA キーは通常 1024 ビットですが、重要な場合は 2048 ビットになります。

3 番目のステップは、n のオイラー関数 φ(n) を計算することです。

式によると:

φ(n) = (p-1)(q-1)

アリスは、φ(3233)が60×52、つまり3120に等しいと計算しました。

4 番目のステップは、整数 e をランダムに選択することです。条件は 1

アリスは 1 ～ 3120 の間で、ランダムに 17 個が選ばれました。 (実際のアプリケーションでは、65537 が選択されることが多いです。)

5 番目のステップは、φ(n) に関する e の剰余逆元 d を計算することです。

いわゆる「剰余逆元」とは、edをφ(n)で割った余りを1にできる整数dが存在することを意味します。

ed ≡ 1 (mod φ(n))

この式は、

ed - 1 = kφ(n)

と同等です。したがって、モジュラー逆要素 d を求めることは、本質的に次のようになります。 2 つの変数で。

ex + φ(n)y = 1

e=17, φ(n)=3120,

17x + 3120y = 1

この方程式は「拡張」で使用できます。ユークリッドアルゴリズム」「解くための具体的な処理はここでは省略します。要約すると、アリスは整数解のセットを (x,y)=(2753,-15)、つまり d=2753 として計算します。

これですべての計算が完了しました。

6 番目のステップは、n と e を公開鍵に、n と d を秘密鍵にカプセル化することです。

アリスの例では、n=3233、e=17、d=2753なので、公開鍵は(3233,17)、秘密鍵は(3233,2753)となります。

実際のアプリケーションでは、公開鍵と秘密鍵のデータはASN.1形式で表現されます(例)。

7. RSA アルゴリズムの信頼性

上記の鍵生成手順を確認すると、合計 6 つの数字が表示されます。

p
q
n
φ(n)
e
d

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

では、n と e がわかっているときに d を推測することは可能でしょうか?

(1)ed≡1 (mod φ(n))。 e と φ(n) を知ることによってのみ、d を計算できます。

(2)φ(n)=(p-1)(q-1)。 p と q を知ることによってのみ、φ(n) を計算できます。

(3) n=pq。 n を因数分解することによってのみ、p と q を計算できます。

結論: n を因数分解できれば、d を計算できます。これは、秘密鍵が解読されたことを意味します。

しかし、大きな整数の因数分解は非常に難しいものです。現時点では、総当たりクラッキング以外に有効な方法は見つかっていません。 Wikipedia には次のように書かれています:

非常に大きな整数を因数分解する難しさは、RSA アルゴリズムの信頼性を決定します、つまり、非常に大きな整数を因数分解するのが難しいほど、RSA アルゴリズムの信頼性が高くなります。高速ファクタリング アルゴリズムが見つかると、RSA の信頼性は非常に低くなりますが、2008 年現在、世界中で短い RSA キーのみを解読できる可能性は非常に低いです。 RSA アルゴリズム。キーの長さが十分に長い限り、RSA で暗号化された情報を復号化することはできません。たとえば、3233 (61×53) を因数分解することはできます。ただし、次の整数は因数分解できません。

12301866845301177551304949

58384962720772853569595334

79219732245215172640050726

36575187452 97864693899

56474942774063845925192557

32630345373154826850791702

61221429134616704292143116

0222 8 9081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
3674604366679959 0428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092

798736308917

実際、これはおそらく人間が因数分解した最大の整数です (10 進数 232 桁、2 進数 768 桁)。これより大きな因数分解は報告されていないため、これまでに解読された最長の RSA キーは 768 ビットです。

8. 暗号化と復号化

公開鍵と鍵を使用して、暗号化と復号化を行うことができます。

(1) 暗号化には公開鍵 (n,e) が必要です

ボブが暗号化された情報 m をアリスに送信したいと仮定すると、m を暗号化するにはアリスの公開鍵 (n,e) を使用する必要があります。ここで、m は整数でなければならず (文字列は ASCII 値または Unicode 値を取ることができます)、m は n 未満でなければならないことに注意してください。

いわゆる「暗号化」とは、次の式のcを計算することです:

m^e≡ c (mod n)

アリスの公開鍵は(3233, 17)、ボブのmは65, すると、次の方程式が計算できます:

65¹⁷ ≡ 2790 (mod 3233)

したがって、c は 2790 に等しく、ボブは 2790 をアリスに送信します。

(2) 復号化には秘密鍵 (n, d) が必要です

アリスはボブから送信された 2790 を取得した後、自分の秘密鍵 (3233, 2753) を使用してそれを復号化します。次の方程式が成り立つことが証明できます:

c^d ≡ m (mod n)

つまり、c の d 乗を n で割った余りが m です。ここで、c は 2790 で、秘密鍵は (3233, 2753) となります。すると、アリスは

2790²⁷⁵³ ≡ 65 (mod 3233)

と計算します。 したがって、アリスは、暗号化前のボブの元のテキストが 65 であることを知っています。

この時点で、「暗号化-復号化」のプロセス全体が完了します。

d が不明な場合、c から m を見つける方法がないことがわかります。前述したように、d を知るには n を分解する必要がありますが、これは非常に困難であるため、RSA アルゴリズムによって通信のセキュリティが確保されます。

公開鍵 (n,e) は n より小さい整数 m しか暗号化できないのですが、n より大きい整数を暗号化したい場合はどうすればよいのかと疑問に思われるかもしれません。解決策は 2 つあります。1 つは長いメッセージをいくつかの短いメッセージに分割し、各セグメントを個別に暗号化する方法です。もう 1 つは、最初に「対称暗号化アルゴリズム」(DES など) を選択し、このアルゴリズムのキーを使用してメッセージを暗号化する方法です。次に、RSA 公開キーを使用して DES キーを暗号化します。

9.秘密鍵復号の証明

最後に、なぜ秘密鍵で復号すると正しくmが得られるのかを証明します。それは次の公式を証明することです:

c^d≡ m (mod n)

なぜなら、暗号化ルールによれば

ｍ^e≡ c (mod n)

So, cは次の形式で記述できます:

c = m^e - kn

証明したい復号ルールに c を代入します:

(m^e - kn)^d≡ m ( mod n)

それは

m^ed≡ m (mod n)

since

ed ≡ 1 (mod φ(n))

So

ed を証明するのと同じです= h φ(n) +1

ed を次のように配置します:

m^hφ(n)+1 ≡ m (mod n)

次に、上の式を2つのケースで証明してみます。

(1) m と n は互いに素です。

オイラーの定理によれば、このとき

m^φ(n)≡ 1 (mod n)

が得られます

(m^φ(n))^h× m ≡ m ( mod n)

元の公式が証明されました。

(2) m と n は互いに素ではありません。

このとき、nは素数pとqの積に等しいので、mはkpまたはkqに等しくなければなりません。

例として、m = kp を考えます。このとき k と q は互いに素でなければならないと考えると、オイラーの定理に従って、次の式が成り立ちます:

(kp)^q-1 ≡ 1 (mod q)

furtherget

[（kp）

q-1

]^h（p-1）×kp pr kp（mod q）

（kp） (mod q)

これを次の方程式に書き換えます

^(kp)ed

= tq + kp

このとき、tはpで割り切れなければなりません、つまり、t=t'p

^(kp) ed

= t'pq + kp

m=kp、n=pqなので

m^ed ≡ m (mod n)

元の式が証明される。

Pythonの実装

強力なPythonには、暗号技術の実装に特化したpycryptoサードパーティライブラリがありますが、rsaの実装にはそのようなハイエンドツールは必要ありません。 、rsa をロードするだけで済みます。サードパーティのライブラリで十分です。

コードを見せてください、いいえ bb:

#实现公钥加密 RSA

import rsa
import time
#计算下时间

start_time = time.time()
key = rsa.newkeys(1024) #数字代表 p * q 产生的存储空间 bit 大小, 也就是密文长度，数字越大，时间越长
privateKey = key[1]
publicKey = key[0]
#print(privateKey)
#print(publicKey)
end_time = time.time()
print("make a key:", end_time - start_time)
#产生公钥和私钥

message = 'Taiyuan is the best city of China.'
message = message.encode()

cryptedMessage = rsa.encrypt(message, publicKey)
print("crypted:", cryptedMessage)
print("length of cryptedMessage：", len(cryptedMessage))
# 加密的过程

decrypetdMessage = rsa.decrypt(cryptedMessage, privateKey)
print("decrypet:", decrypetdMessage)
# 解密的过程

now_time = time.time()
print("crypt and decrypt:", now_time - end_time)

関連する推奨事項:

RSA アルゴリズムの原理を徹底的に理解してください

RSA 暗号化アルゴリズム

25 行 このコードは完全な RSA アルゴリズムを実装しています

RSA アルゴリズムと C 言語実装の詳細な説明

以上がPythonはRSAアルゴリズムを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。