昨天看到一篇英文文章[1]，展示了如何用 Python 來(lái)實(shí)現(xiàn) RSA 算法，代碼的邏輯與前文一文搞懂 RSA 算法一樣，不太熟悉 RSA 的朋友可以看一下一文搞懂 RSA 算法，里面對(duì)什么是 RSA，RSA 的數(shù)學(xué)原理進(jìn)行了說(shuō)明，并舉了一個(gè)簡(jiǎn)單的例子，可以說(shuō)是全知乎最容易讀懂 RSA 的文章了(這話來(lái)自讀者評(píng)論)。

這篇英文提供的代碼我運(yùn)行了下，發(fā)現(xiàn)不能加密中文，于是就修改了下加解密的函數(shù)，讓其支持中文加解密。今天的文章就分享一下如何用 Python 來(lái)實(shí)現(xiàn) RSA 加解密的這一過(guò)程，幫助你建立 RSA 的直觀認(rèn)識(shí)，代碼里的隨機(jī)素?cái)?shù)生成算法，也值得我們學(xué)習(xí)。

0、效果演示

咱們先看下效果。

原文：“有內(nèi)鬼，終止交易”

密文，根本無(wú)法破解：

解密之后：

完整代碼公眾號(hào)「Python七號(hào)」回復(fù)「rsa」獲取。

1、密鑰對(duì)的生成

思路：

1)隨機(jī)找兩個(gè)質(zhì)數(shù)(素?cái)?shù)) p 和 q，p 與 q 越大，越安全，這里選擇 1024 位的質(zhì)數(shù)：

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

genprime() 函數(shù)的實(shí)現(xiàn)過(guò)程先不說(shuō)。

2)計(jì)算他們的乘積 n = p * q 及 歐拉函數(shù) lambda_n。

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

3)隨機(jī)選擇一個(gè)整數(shù) e，條件是 1 < e < lambda_n，且 e 與 lambda_n 互質(zhì)。比如選擇 35537，35537 只有 16 位，必然小于 lambda_n。

e = 35537

4)找到一個(gè)整數(shù) d，可以使得 e * d 除以 lambda_n 的余數(shù)為 1，并返回密鑰對(duì)。

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

eucalg 函數(shù)的實(shí)現(xiàn)放后面說(shuō)。

至此，密鑰對(duì)的生成的函數(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、加解密的實(shí)現(xiàn)

加密和解密的過(guò)程是一樣的，公鑰加密，私鑰解密，反過(guò)來(lái)也可以，私鑰加密，公鑰解密，只不過(guò)前者我們叫加密，后者我們叫簽名。

具體的函數(shù)實(shí)現(xiàn)如下：

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ù)，它用來(lái)計(jì)算公式 b^e % n = r 的。

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

隨機(jī)質(zhì)數(shù)的生成函數(shù)，其中用到了矩陣乘法和斐波那契數(shù)列，可見(jiàn)數(shù)學(xué)對(duì)于算法的重要性。

# 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í)現(xiàn)

函數(shù)的本質(zhì)在于求下面二元一次方程的解:

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、測(cè)試

test.py 腳本使用方法：

1）、生成密鑰

python test.py make-keys rsakey

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

2）、對(duì)文件內(nèi)容加密

假如有文件 明文.txt：

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

將生成 密文.txt

3、 對(duì)文件內(nèi)容解密

假如有文件 密文.txt：

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

將生成 解密后.txt

最后的話

本文分享了 RSA 算法的 Python 的簡(jiǎn)單實(shí)現(xiàn)，可以幫助理解 RSA 算法。

以上是用 Python 來(lái)實(shí)現(xiàn) RSA 加解密的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！