用 Python 來實作 RSA 加解密

昨天看到一篇英文文章[1]，展示如何用Python 來實現RSA 演算法，程式碼的邏輯與前文一文搞懂RSA 演算法一樣，不太熟悉RSA 的朋友可以看一下一文搞懂RSA 演算法，裡面對什麼是RSA，RSA 的數學原理進行了說明，並舉了一個簡單的例子，可以說是全知乎最容易讀懂RSA 的文章了(這話來自讀者評論)。

這篇英文提供的程式碼我運行了下，發現不能加密中文，於是就修改了下加解密的函數，讓其支援中文加解密。今天的文章就分享如何用 Python 來實現 RSA 加解密的這個過程，幫助你建立 RSA 的直覺認識，程式碼裡的隨機素數產生演算法，也值得我們學習。

0、效果示範

咱們先看下效果。

原文：「有內鬼，終止交易」

#密文，根本無法破解：

解密之後：

完整程式碼公眾號碼「Python七號」回覆「rsa」取得。

1、金鑰對的產生

想法：

1)隨機找兩個質數(質數) p 和q，p 與q 越大，越安全，這裡選擇1024 位元的質數：

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

genprime() 函數的實作過程先不說。

2)計算他們的乘積 n = p * q 和 歐拉函數 lambda_n。

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

3)隨機選取一個整數 e，條件是 1 < e < lambda_n，且 e 與 lambda_n 互質。例如選擇 35537，35537 只有 16 位，必然小於 lambda_n。 < e < lambda_n，且 e 与 lambda_n 互质。比如选择 35537，35537 只有 16 位，必然小于 lambda_n。

e = 35537

4)找到一個整數 d，可以使得 e * d 除以 lambda_n 的餘數為 1，並傳回金鑰對。

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

eucalg 函數的實作放後面說。

至此，金鑰對的產生的函數如下：

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、加解密的實作

加密和解密的過程是一樣的，公鑰加密，私鑰解密，反過來也可以，私鑰加密，公鑰解密，只不過前者我們叫加密，後者我們叫簽名。

具體的函數實作如下：

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 函數，它用來計算公式 b^e % n = r 的。

• 如果是加密過程，那麼 b 是明文，(n,e)為公鑰，r 為密文。
• 如果是解密過程，那麼 b 是密文，(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、隨機質數的生成函數

隨機質數的生成函數，其中用到了矩陣乘法和斐波那契數列，可見數學對於演算法的重要性。

# 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 函數的實作

函數的本質在於求下面二元一次方程式的解:

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.py 腳本使用方法：

1）、產生金鑰

python test.py make-keys rsakey

公鑰儲存在rsakey.pub 中， 私鑰儲存在rsakey.priv中

2）、對檔案內容加密

假如有文件明文.txt：

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

將產生密文.txt

3、對文件內容解密

假如有檔案密文.txt：

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

將產生解密後.txt

最後的話

本文分享了RSA 演算法的Python的簡單實現，可以幫助理解RSA 演算法。

以上是用 Python 來實作 RSA 加解密的詳細內容。更多資訊請關注PHP中文網其他相關文章！