使用 Python 實現 RSA 加密

楔子

本次來聊一聊如何用 Python 實現 RSA，我們知道 RSA 是一種非對稱加密算法，並且應用非常廣泛，比如 HTTPS。

所以在介紹 RSA 之前，需要先解釋一下什麼是對稱加密和非對稱加密。

對稱加密

在重要信息的傳遞過程中，人們總是希望信息不會被偷看、不會被篡改，僞造等。爲了達到這個要求人們一直在不斷努力着。

電報加密所使用的密碼本，就是初代網絡安全所使用的加密方式，用法爲：發信時將內容翻譯爲密文發出，收到電報的一方，使用相同的密碼本才能解密出正確的信息，否則看到的就是一堆亂碼。

這種傳統的加密方式叫做對稱加密，而對稱加密所使用的算法包括：DES、3DES、AES、DESX、Blowfish、RC4、RC5、RC6，這些算法就可以看成密鑰、或者理解爲上面的密碼本。這些算法也被稱爲: "對稱加密算法" 或者 "傳統加密算法"，一方使用算法進行加密，然後另一方使用相同的算法進行解密。

我們以《福爾摩斯探案集之跳舞的小人》一案中出現的小人爲例。

每一個小人都代表一個英文字符，至於小人手中的旗子則是用來分隔單詞的、也就是表示一個單詞的邊界。傳遞信息的時候，將信息用小人來代替，然後另一方看到小人的時候，再將出現的小人解析成信息。順便一提，劇中的女主是黑幫首領的女兒，犯人就是使用這些小人來向女主傳遞信息，威脅她回去。

這些小人和英文字符之間的對應關係就相當於密鑰，此時就屬於對稱加密。因爲無論是發信人還是收信人，使用的是相同的密鑰，即：小人代表的含義都是一樣的。

因此不難看出，對稱加密的安全性非常依賴於密鑰，泄漏密鑰就意味着任何人都可以對發送或接收的消息進行解密，所以密鑰的保密性對通信安全來說至關重要。福爾摩斯在解析出這些小人代表的含義之後，用這些小人發送信息將犯人引誘了出來。因此對於這種對稱加密來說，密鑰的安全是極其重要的。

那麼對稱加密有哪些優缺點呢？

• 優點：計算量小、加密速度快、加密效率高；

• 缺點：密鑰需要傳遞，難以確保密鑰安全性。缺乏簽名功能，不能覈對發信人身份；

非對稱加密

在對稱加密中，密鑰（也就是使用的加密算法，如發電報時的密碼本、小人和英文字符的對應關係）的保密性至關重要。戰爭時期，電報密碼本需要通過人工渠道傳遞，這樣發報雙方纔能放心地使用。

但在如今的網絡通信中，顯然不可能再使用人工渠道的方式來傳遞密鑰，只有通過網絡來傳遞才高效快捷。這樣就有了一個矛盾：密鑰是用來保證網絡傳輸安全的，這個對於網絡安全至關重要的密鑰又需要網絡來傳遞給對方。

保存密鑰最安全的方式就是不告訴任何人，不進行傳遞，但對稱加密中，解密方必須要得到對應的密鑰，這就又要求密鑰必須進行傳遞，可一旦傳遞密鑰就有丟失的風險。這個 "雞生蛋、蛋生雞" 的問題一直困擾着人們，直到出現了一種算法，這套算法生成的密鑰分爲兩個部分：公鑰和私鑰。

這個一分爲二的密鑰對有如下特點：

• 公鑰和私鑰是一個算法中兩個不同、但內在又相關聯的參數集合，同時生成，但可以獨立使用；

• 公鑰加密的數據只有對應的私鑰纔可以解密（公鑰加密後公鑰也不能解密）；

• 私鑰加密的數據也只有對應的公鑰纔可以解密；

常見的非對稱加密算法有：RSA、DSA、ECC、Diffie-Hellman、El Gamal 等。

RSA 算法概述

對稱加密的模式很好理解，但非對稱加密算法的上述特點卻讓我們感覺很神奇，下面就來簡單看看，上述這些特點在數學上是怎樣實現的吧。在非對稱加密算法中 RSA 是使用最廣泛的一種，我們就以 RSA 爲例，一會兒再介紹怎麼用 Python 實現它。

RSA 算法是 1977 年由共同在麻省理工學院工作的羅納德 · 李維斯特（Ron Rivest）、阿迪 · 薩莫爾（Adi Shamir）和倫納德 · 阿德曼（Leonard Adleman）一起提出的。RSA 就是他們三人姓氏開頭字母拼在一起組成的。

RSA 加密利用了 "單向函數" 正向求解很簡單，反向求解很複雜的特性。思想如下：

• p1*p2 = n，已知 p1、p2 求 n 簡單，已知 n 求 p1、p2 很難；

• (m^e) % n = c，已知 m、e、n 求 c 簡單，已知 e、n、c 求 m 很難；

這個應該很好理解，然後是 RSA 的工作原理，以下是 ChatGPT 告訴我的，我們不懂也沒關係。

• 選擇兩個大的質數 p 和 q，且通常這兩個數的大小相近。

• 計算這兩個數的乘積 n = p * q，這個 n 將作爲公鑰和私鑰的一部分。

• 計算 n 的歐拉函數 ϕ(n) = (p - 1) * (q -1)。

• 選擇一個整數 e，使得 1 < e < ϕ(n) 且 e 與 ϕ(n) 互質，e 通常選取 65537，因爲它是一個質數，且爲形式爲 2 的冪次方加 1。

• 計算 e 關於 ϕ(n) 的模逆元 d，即找到 d 使得 e * d = 1 % ϕ(n)。

然後便可得到公鑰 (e, n) 和私鑰 (d, n)，而它們滿足如下關係。

其中 M 是明文，C 是密文，明文 M 用公鑰加密得到密文 C，密文 C 用私鑰解密得到明文 M。當然這個過程反過來也是一樣，也可以用私鑰進行加密，公鑰進行解密，這個過程一般用作簽名。

RSA 算法的安全性基於 RSA 問題的困難性，也就是基於大整數因子分解的困難性上。這種算法非常可靠，密鑰越長，它就越難破解。根據已經披露的文獻，目前被破解的最長 RSA 密鑰是 768 個二進制位。

也就是說，長度超過 768 位的密鑰，還無法破解（至少沒人公開宣佈）。因此可以認爲，1024 位的 RSA 密鑰基本安全，2048 位的密鑰極其安全。

非對稱加密的算法比對稱加密要複雜且耗時，位數越多越耗時。因此在實際使用中，一般是先用非對稱加密過程傳遞對稱加密的密鑰，之後再使用對稱加密來保證後續的通信，這樣安全性與速度就可以達到一個平衡，HTTPS 所使用的就是這種方式。

Python 實現 RSA

首先需要安裝一個庫：pycryptodome，直接 pip 安裝即可，這個庫裏面包含了大量實現好的加密算法。

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import binascii

def generate_keys():
    # 生成長度爲 2048 的祕鑰
    key = RSA.generate(2048)
    # 生成公鑰
    private_key = key.export_key()
    # 生成私鑰
    public_key = key.publickey().export_key()
    return private_key, public_key

def encrypt_message(public_key, message):
    cipher = PKCS1_OAEP.new(RSA.import_key(public_key))
    # 使用公鑰加密，得到密文（bytes 對象）
    encrypted_message = cipher.encrypt(message.encode())
    # 一般會轉成十六進制進行傳輸
    return binascii.hexlify(encrypted_message).decode()

def decrypt_message(private_key, encrypted_message):
    cipher = PKCS1_OAEP.new(RSA.import_key(private_key))
    # 解密
    decrypted_message = cipher.decrypt(
        binascii.unhexlify(encrypted_message)
    )
    return decrypted_message.decode()

# 生成密鑰
private_key, public_key = generate_keys()
message = "高老師總能分享出好東西"
# 使用公鑰加密
encrypted = encrypt_message(public_key, message)
print(encrypted)
"""
41bc8709cb82e1f9a13d18f101538c536f760210c11···
"""
print(len(encrypted))
"""
512
"""
# 使用私鑰解密
decrypted = decrypt_message(private_key, encrypted)
print(decrypted)
"""
高老師總能分享出好東西
"""

以上就是使用 Python 實現 RSA 算法。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/nSvmq5ma78axSottjEaMUA