用 Python 來實現(xiàn) RSA 加解密

昨天看到一篇英文文章^[1]，展示了如何用 Python 來實現(xiàn) RSA 算法，代碼的邏輯與前文一文搞懂 RSA 算法一樣，不太熟悉 RSA 的朋友可以看一下一文搞懂 RSA 算法，里面對什么是 RSA，RSA 的數(shù)學原理進行了說明，并舉了一個簡單的例子，可以說是全知乎最容易讀懂 RSA 的文章了（這話來自讀者評論），要是看不懂，你加我微信「somenzz」交流一下。

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

0、效果演示

咱們先看下效果。

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

密文，根本無法破解：

解密之后：

完整代碼公眾號「Python七號」回復「rsa」獲取。

1、密鑰對的生成

思路：

1）隨機找兩個質(zhì)數(shù)（素數(shù)） p 和 q，p 與 q 越大，越安全，這里選擇 1024 位的質(zhì)數(shù)：

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

genprime() 函數(shù)的實現(xiàn)過程先不說。

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

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

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

e?=?35537

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

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

eucalg 函數(shù)的實現(xià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、加解密的實現(xiàn)

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

具體的函數(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ù)，它用來計算公式 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、隨機質(zhì)數(shù)的生成函數(shù)

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

#?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?<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ù)的實現(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???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、對文件內(nèi)容加密

假如有文件 明文.txt：

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

將生成 密文.txt

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

假如有文件 密文.txt：

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

將生成 解密后.txt

最后的話

本文分享了 RSA 算法的 Python 的簡單實現(xiàn)，可以幫助理解 RSA 算法，獲取完整代碼關注公眾號「Python七號」，回復「rsa」獲取。

留言交流

掃碼關注

參考資料