昨日、Python を使用して RSA アルゴリズムを?qū)g裝する方法を示した英語の記事 [1] を見ました。コードのロジックは、前の記事「RSA アルゴリズムを理解する」と同じです。RSA に詳しくない友人でも読むことができます。記事「Understanding the RSA Algorithm.」は、RSA とは何か、RSA の數(shù)學(xué)的原理を説明し、簡(jiǎn)単な例を示しており、Quanzhihu で RSA を理解するのに最も簡(jiǎn)単な記事と言えます (これは読者のコメントから來ています)。

英語で提供されたコードを?qū)g行したところ、中國語を暗號(hào)化できないことが判明したため、中國語の暗號(hào)化と復(fù)號(hào)化をサポートするように暗號(hào)化と復(fù)號(hào)化の関數(shù)を修正しました。今日の記事では、Python を使用して RSA 暗號(hào)化および復(fù)號(hào)化プロセスを?qū)g裝する方法を共有し、RSA を直感的に理解できるようにします。コード內(nèi)のランダムな素?cái)?shù)生成アルゴリズムも學(xué)ぶ価値があります。

0. 効果デモ

まずは効果を見てみましょう。

原文：「モグラがいます、取引を終了します」

暗號(hào)文は全く解読できません：

復(fù)號(hào)後:

完全なコード公開アカウント「Python No. 7」は、「rsa」と返信することで取得できます。

1. 鍵ペアの生成

アイデア:

1) ランダムに 2 つの素?cái)?shù) (素?cái)?shù)) p と q を見つけます。p と q が大きいほど安全です。ここでは 1024 ビットの素?cái)?shù)を選択します:

p = genprime(1024)
q = genprime(1024)

genprime() 関數(shù)の実裝プロセスについては觸れません。

2) それらの積 n = p * q とオイラー関數(shù) lambda_n を計(jì)算します。

n = p * q
lambda_n = (p - 1) * (q - 1)

3) 整數(shù) e をランダムに選択します。條件は 1 < e < lambda_n で、e と lambda_n は互いに素です。たとえば、35537 を選択した場(chǎng)合、35537 には 16 ビットしかなく、lambda_n より小さい必要があります。 < e < lambda_n，且 e 與 lambda_n 互質(zhì)。比如選擇 35537，35537 只有 16 位，必然小于 lambda_n。

e = 35537

4) e * d を lambda_n で割った余りが 1 になるような整數(shù) d を見つけ、キー ペアを返します。

d = eucalg(e, lambda_n)[0]
if d < 0: d += lambda_n
return (d, n), (e, n)

eucalg 関數(shù)の実裝については後で説明します。

この時(shí)點(diǎn)で、キー ペア生成関數(shù)は次のとおりです:

def create_keys():
 p = genprime(1024)
 q = genprime(1024)
 n = p * q
 lambda_n = (p - 1) * (q - 1)
 e = 35537
 d = eucalg(e, lambda_n)[0]
 if d < 0: d += lambda_n
 return (d, n), (e, n)

2. 暗號(hào)化と復(fù)號(hào)化の実裝

暗號(hào)化と復(fù)號(hào)化のプロセスは同じ、公開キーです。暗號(hào)化、秘密鍵暗號(hào)化、鍵復(fù)號(hào)、その逆の秘密鍵暗號(hào)、公開鍵復(fù)號(hào)がありますが、前者を暗號(hào)化、後者を署名と呼びます。

具體的な関數(shù)の実裝は次のとおりです:

def encrypt_data(data,key):
e_data = []
for d in data:
 e = modpow(d, key[0], key[1]) 
 e_data.append(e)
return e_data

## 加密和解密的邏輯完全一樣
decrypt_data = encrypt_data

ここでは modpow 関數(shù)が使用されており、式 b^e % n = r を計(jì)算するために使用されます。

• 暗號(hào)化プロセスの場(chǎng)合、b は平文、(n,e) は公開鍵、r は暗號(hào)文です。
• これが復(fù)號(hào)化プロセスの場(chǎng)合、b は暗號(hào)文、(n, d) は秘密鍵、r は有名なテキストです。

modpow は次のように定義されます:

def modpow(b, e, n):
 # find length of e in bits
 tst = 1
 siz = 0
 while e >= tst:
tst <<= 1
siz += 1
 siz -= 1
 # calculate the result
 r = 1
 for i in range(siz, -1, -1):
r = (r * r) % n
if (e >> i) & 1: r = (r * b) % n
 return r

3. ランダムな素?cái)?shù)の生成関數(shù)

行列乗算とフィボナッチ數(shù)列を使用したランダムな素?cái)?shù)の生成関數(shù)アルゴリズムに対する數(shù)學(xué)の重要性を示しています。

# matrix multiplication
def sqmatrixmul(m1, m2, w, mod):
 mr = [[0 for j in range(w)] for i in range(w)]
 for i in range(w):
for j in range(w):
 for k in range(w):
mr[i][j] = (mr[i][j] + m1[i][k] * m2[k][j]) % mod
 return mr

# fibonacci calculator
def fib(x, mod):
 if x < 3: return 1
 x -= 2
 # find length of e in bits
 tst = 1
 siz = 0
 while x >= tst:
tst <<= 1
siz += 1
 siz -= 1
 # calculate the matrix
 fm = [
# function matrix
[0, 1],
[1, 1]
 ]
 rm = [
# result matrix
# (identity)
[1, 0],
[0, 1]
 ]
 for i in range(siz, -1, -1):
rm = sqmatrixmul(rm, rm, 2, mod)
if (x >> i) & 1:
 rm = sqmatrixmul(rm, fm, 2, mod)

 # second row of resulting vector is result
 return (rm[1][0] + rm[1][1]) % mod

def genprime(siz):
 while True:
num = (1 << (siz - 1)) + secrets.randbits(siz - 1) - 10;
# num must be 3 or 7 (mod 10)
num -= num % 10
num += 3 # 3 (mod 10)
# heuristic test
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
 return num
num += 5 # 7 (mod 10)
# heuristic test
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
 return num

4. eucalg 関數(shù)の実裝

関數(shù)の本質(zhì)は、次の 2 つの変數(shù)の線形方程式の解を見つけることです:

e * x - lambda_n * y =1

具體的なコード:

def eucalg(a, b):
 # make a the bigger one and b the lesser one
 swapped = False
 if a < b:
a, b = b, a
swapped = True
 # ca and cb store current a and b in form of
 # coefficients with initial a and b
 # a' = ca[0] * a + ca[1] * b
 # b' = cb[0] * a + cb[1] * b
 ca = (1, 0)
 cb = (0, 1)
 while b != 0:
# k denotes how many times number b
# can be substracted from a
k = a // b
# swap a and b so b is always the lesser one
a, b, ca, cb = b, a-b*k, cb, (ca[0]-k*cb[0], ca[1]-k*cb[1])
 if swapped:
return (ca[1], ca[0])
 else:
return ca

5 、test

test.py スクリプトの使用方法:

1)、キーを生成

python test.py make-keys rsakey

公開キーは rsakey.pub に保存され、秘密キーは rsakey.priv 中

2 に保存されます)、ファイルの內(nèi)容を暗號(hào)化します

プレーン テキスト .txt ファイルがある場(chǎng)合:

python test.py encrypt 明文.txt from rsakey to 密文.txt

は暗號(hào)文を生成します.txt

3. ファイルを暗號(hào)化します コンテンツの復(fù)號(hào)化

ファイル ciphertext.txt:

python test.py decrypt 密文.txt as rsakey to 解密后.txt

がある場(chǎng)合は、復(fù)號(hào)化された .txt

Final が生成されます。言葉

この記事では、RSA アルゴリズムの Python について説明します。簡(jiǎn)単な実裝は、RSA アルゴリズムを理解するのに役立ちます。

以上がPython を使用して RSA 暗號(hào)化と復(fù)號(hào)化を?qū)g裝するの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。