昨天看到一篇英文文章[1]，展示如何用Python 來實現RSA 演算法，程式碼的邏輯與前文一文搞懂RSA 演算法一樣，不太熟悉RSA 的朋友可以看一下一文搞懂RSA 演算法，裡面對什麼是RSA，RSA 的數學原理進行了說明，並舉了一個簡單的例子，可以說是全知乎最容易讀懂RSA 的文章了(這話來自讀者評論)。
這篇英文提供的程式碼我運行了下，發現不能加密中文，於是就修改了下加解密的函數，讓其支援中文加解密。今天的文章就分享如何用 Python 來實現 RSA 加解密的這個過程，幫助你建立 RSA 的直覺認識，程式碼裡的隨機素數產生演算法，也值得我們學習。
咱們先看下效果。
原文：「有內鬼，終止交易」
#密文，根本無法破解：
解密之後：
完整程式碼公眾號碼「Python七號」回覆「rsa」取得。
想法：
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)
加密和解密的過程是一樣的，公鑰加密，私鑰解密，反過來也可以，私鑰加密，公鑰解密，只不過前者我們叫加密，後者我們叫簽名。
具體的函數實作如下：
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 的。
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
隨機質數的生成函數，其中用到了矩陣乘法和斐波那契數列，可見數學對於演算法的重要性。
# 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
函數的本質在於求下面二元一次方程式的解:
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
test.py 腳本使用方法：
python test.py make-keys rsakey
公鑰儲存在rsakey.pub 中， 私鑰儲存在rsakey.priv中
假如有文件明文.txt：
python test.py encrypt 明文.txt from rsakey to 密文.txt
將產生密文.txt
假如有檔案密文.txt：
python test.py decrypt 密文.txt as rsakey to 解密后.txt
將產生解密後.txt
最後的話
本文分享了RSA 演算法的Python的簡單實現，可以幫助理解RSA 演算法。
以上是用 Python 來實作 RSA 加解密的詳細內容。更多資訊請關注PHP中文網其他相關文章！
