如何用Python實現(xiàn)RSA加密算法
更新時間：2023年06月06日 15:47:50 作者：The-Back-Zoom
RSA加密算法是一種非對稱加密算法,即使用不同的密鑰進行加密和解密,下面這篇文章主要給大家介紹了關(guān)于如何用Python實現(xiàn)RSA加密算法的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下
1.RSA算法簡介
1977年，三位數(shù)學(xué)家 Rivest、Shamir 和 Adleman 設(shè)計了一種算法，可以實現(xiàn)非對稱加密。這種算法用他們?nèi)齻€人的名字命名，叫做RSA算法.RSA算法的特征如下:
- RSA算法是非對稱加密算法，及算法的加密密鑰與解密密鑰不同
- RAS是基于大數(shù)分解問題實現(xiàn)的算法，
- RSA算法的密鑰長度一般為1024位到2048位之間，密鑰很長，加密較慢
- RSA算法一般用在數(shù)字簽名比較多
- RSA還是分組密碼算法，需要對明文進行一組一組加密
2.RSA算法涉及的數(shù)學(xué)知識
2.1互素
兩個正整數(shù)，除了1之外沒有其他公因子，我們稱這兩個數(shù)是互素的，（就是兩個數(shù)除一外沒有公約數(shù)，就是互素），如下是判斷兩個數(shù)是否互素的代碼實現(xiàn)：
def prime(a, b):
if a > b:
mid = a
a = b
b = mid
mid = b % a
while mid:
b = a
a = mid
mid = b % a
if a == 1:
print('倆數(shù)互素')
else:
print('倆數(shù)不互素')
if __name__ == '__main__':
prime(8, 3)2.2 歐拉定理
如果兩個正整數(shù)a和n互素，則n的歐拉函數(shù)φ(n)可以讓下面的式子成立
其中a上面的表達式為歐拉函數(shù)，歐拉函數(shù)的計算方法為，比如計算n的歐拉函數(shù)，就是找從1到n-1和n互素元素的個數(shù)，其中質(zhì)數(shù)的歐拉函數(shù)值為n-1，判斷一個數(shù)的歐拉函數(shù)值方法如下：
def prime(a, b):
if a > b:
mid = a
a = b
b = mid
mid = b % a
while mid:
b = a
a = mid
mid = b % a
if a == 1:
return True
else:
return False
def oula(n):
total = 0
for i in range(1, n):
if prime(i, n):
total = total + 1
return total
if __name__ == '__main__':
print(oula(8))2.3求模逆元
求模逆元就是貝祖等式，就是d*e = 1 (mod n),e,和 n知道了，求d
def invmod(e, m):
"""
求模逆元：知道x * e + y * m = g
:param e:
:param m:
:return:
"""
g, d, y = exgcd(e, m)
assert g == 1
if d < 0:
d += m
return d2.4 取模運算
取模運算就是取余數(shù)運算
model = a % b
2.5 最大公因數(shù)
求最大公因數(shù)一般使用歐幾里得算法，歐幾里得算法又稱輾轉(zhuǎn)相除法，是指用于計算兩個非負(fù)整數(shù)a，b的最大公約數(shù)。應(yīng)用領(lǐng)域有數(shù)學(xué)和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。
方法1
def gcd(a, b):
"""
求最大公約數(shù)
:param a:
:param b:
:return:
"""
if a > b:
mid = a
a = b
b = mid
y = b % a
while y:
b = a
a = y
y = b % a
return b方法二
def gcd(a, b):
"""
求最大公約數(shù)
:param a:
:param b:
:return:
"""
while b:
a, b = b, a % b
return a2.6 最小公倍數(shù)
最小公倍數(shù)是再最大公因數(shù)的基礎(chǔ)上使用的，兩個或多個整數(shù)公有的倍數(shù)叫做它們的公倍數(shù)，其中除0以外最小的一個公倍數(shù)就叫做這幾個整數(shù)的最小公倍數(shù)。整數(shù)a，b的最小公倍數(shù)記為[a，b]，同樣的，a，b，c的最小公倍數(shù)記為[a，b，c]，多個整數(shù)的最小公倍數(shù)也有同樣的記號。 與最小公倍數(shù)相對應(yīng)的概念是最大公約數(shù)，a，b的最大公約數(shù)記為（a，b）。關(guān)于最小公倍數(shù)與最大公約數(shù)，我們有這樣的定理：(a,b)x[a,b]=ab(a,b均為整數(shù))。
方法1
def lcm(a, b):
"""
求最大公倍數(shù)
:param a:
:param b:
:return:
"""
divisor = gcd(a, b)
multiple = (a * b) / divisor
return multiple方法二
def lcm(a, b):
"""
求最大公倍數(shù)
:param a:
:param b:
:return:
"""
return a // gcd(a, b) * b2.7 歐幾里得算法
歐幾里得算法又稱輾轉(zhuǎn)相除法，是指用于計算兩個非負(fù)整數(shù)a，b的最大公約數(shù)。應(yīng)用領(lǐng)域有數(shù)學(xué)和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。,上面說了
2.8 擴展歐幾里得算法
求的a和b的最大公因數(shù)，求，x，y使得
x * a + y * b= g(a,b)
def exgcd(a, b):
# a：a和b的最大公因數(shù)
old_s:
old_t:
old_s * a + old_t * b = a
"""
old_s, s = 1, 0
old_t, t = 0, 1
while b:
q = a // b
s, old_s = old_s - q * s, s
t, old_t = old_t - q * t, t
a, b = b, a % b
return a, old_s, old_t3.RSA算法數(shù)學(xué)實現(xiàn)
3.1理論
- 隨意選擇兩個大的質(zhì)數(shù)p和q，p不等于q，計算N = pq.
- 根據(jù)歐拉函數(shù)，求得φ(N)=φ§φ(q)=(p-1)(q-1)。這是一個公式如果N = pq，那么φ(N)=φ(p)φ(q)，又因為p和q都是素數(shù)，φ(p) = p-1，所以φ(N)=φ(p)φ(q)=(p-1)(q-1)
- 選擇一個數(shù)e，使e大于1，并且e小于φ(N)，找一個數(shù)d，使得ed≡1(mod φ(N))，（e,n）為公鑰，（d,e）為私鑰
- 加密：m^e ≡ c (mod n)，其中c為密文，解密：c^d ≡ m (mod n)
加解密圖解如下：
3.2實踐
首先找兩個數(shù)，及p和q，p和q一般非常大，這里方便計算，取比較小的值，假設(shè)：p ＝ 17，q ＝ 19(p,q互素)
- n = p ＊ q ＝ 323
- φ(n) = (p-1) * (q-1) = 144
- 隨機取一數(shù)e，使1 < e < φ(n)并且gcd(e,φ(n)) =1,e=5合適（還有很多數(shù)都合適，這里只取一個數(shù)）
- 取一數(shù)d，使得ed≡1(mod φ(n)),取d為29，所以公鑰為(e,n)，私鑰為（d,n）
- 加密：假設(shè)明文 ＝ 123，則 密文＝（123的5次方）mod 323=225
- 解密：明文＝（225的29次方）mod 323 =123，所以解密后的明文為123。
4.RSA算法代碼實現(xiàn)
4.1RSA算法代碼實現(xiàn)1
# 求兩個數(shù)字的最大公約數(shù)（歐幾里得算法）
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 獲取密鑰
def get_key(p, q):
n = p * q
fyn = (p - 1) * (q - 1)
e = 2
while gcd(e, fyn) != 1:
e = e + 1
d = 2
while (e*d) % fyn != 1:
d = d + 1
return (n, e), (n, d)
# 加密
def encryption(x, pubkey):
n = pubkey[0]
e = pubkey[1]
y = x ** e % n # 加密
return y
# 解密
def decryption(y, prikey):
n = prikey[0]
d = prikey[1]
x = y ** d % n # 解密
return x
if __name__ == '__main__':
p = int(input("請給定第一個質(zhì)數(shù)p的值："))
q = int(input("請給定第二個質(zhì)數(shù)q的值："))
x = int(input("請給定要加密的消息x的值："))
# 生成公鑰私鑰
pubkey, prikey = get_key(p, q)
print("加密前的消息是：", x)
y = encryption(x, pubkey)
print("加密后的消息是：", y)
after_x = decryption(y, prikey)
print("解密后的消息是：", after_x)以上算法只能夠?qū)崿F(xiàn)整數(shù)加密，這個算法就是演示了RSA算法的原理
4.1RSA算法代碼實現(xiàn)2
from random import randrange
import math
def prime(n):
"""
判斷一個數(shù)是不是素數(shù)
:param n:
:return: BOOL
"""
mid = math.sqrt(n)
mid = math.floor(mid)
for item in range(2, mid):
if n % item == 0:
return False
return True
def generate_n_bit_odd(n: int):
"""
生成大數(shù),不確定是不是素數(shù)
:param n:
:return:大數(shù)
"""
assert n > 1
return randrange(2 ** (n - 1) + 1, 2 ** n, 2)
first_50_primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223, 227, 229, 233]
def get_lowlevel_prime(n):
"""
選擇滿足不能夠整除前50個素數(shù)的大數(shù)，沒找到就一直循環(huán)
:param n:
:return:
"""
while True:
c = generate_n_bit_odd(n)
for divisor in first_50_primes:
if c % divisor == 0 and divisor ** 2 <= c:
break
return c
def miller_rabin_primality_check(n, k=20):
"""
米勒-拉賓素性檢驗
由于假設(shè)n是一個素數(shù)，n-1=a^s*d,s和d是常量，改變a的值，檢測20次
:param n:
:param k:
:return:
"""
assert n > 3
if n % 2 == 0:
return False
# 找出n-1 = 2^s*d
s, d = 0, n - 1
while d % 2 == 0:
d >>= 1
s += 1
for _ in range(k):
a = randrange(2, n - 1)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def get_random_prime(num_bits):
"""
獲取大素數(shù)
:param num_bits:
:return:
"""
while True:
pp = get_lowlevel_prime(num_bits)
if miller_rabin_primality_check(pp):
return pp
def gcd(a, b):
"""
求最大公約數(shù)
:param a:
:param b:
:return:
"""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""
求最大公倍數(shù)
:param a:
:param b:
:return:
"""
# divisor = gcd(a, b)
# multiple = (a * b) / divisor
# return multiple
return a // gcd(a, b) * b
def exgcd(a, b):
"""
擴展歐幾里得算法
:param a:
:param b:
:return:
a：a和b的最大公因數(shù)
old_s:
old_t:
old_s * a + old_t * b = a
"""
old_s, s = 1, 0
old_t, t = 0, 1
while b:
q = a // b
s, old_s = old_s - q * s, s
t, old_t = old_t - q * t, t
a, b = b, a % b
return a, old_s, old_t
def invmod(e, m):
"""
求模逆元：知道x * e + y * m = g
:param e:
:param m:
:return:
"""
g, d, y = exgcd(e, m)
assert g == 1
if d < 0:
d += m
return d
def uint_from_bytes(xbytes: bytes) -> int:
"""
比特轉(zhuǎn)換位整數(shù)
:param xbytes:
:return:
"""
return int.from_bytes(xbytes, 'big')
def uint_to_bytes(x: int) -> bytes:
"""
整數(shù)轉(zhuǎn)換成比特的時候，一個整數(shù)對應(yīng)32位比特數(shù)
:param x:
:return:
"""
if x == 0:
return bytes(1)
return x.to_bytes((x.bit_length() + 7) // 8, 'big') #做到盡量不補零
RSA_DEFAULT_EXPONENT = 65537
RSA_DEFAULT_MODULUS_LEN = 2048
class RSA:
"""
RSA算法(self.n, self.e)加密密鑰
(self.n, self.d)解密密鑰
"""
def __init__(self, key_length=RSA_DEFAULT_MODULUS_LEN,
exponent=RSA_DEFAULT_EXPONENT):
self.e = exponent
t = 0
p = q = 2
# 找出一個e使1<e<(p-1)*(q-1)
while gcd(self.e, t) != 1:
p = get_random_prime(key_length // 2)
q = get_random_prime(key_length // 2)
t = lcm(p - 1, q - 1)
self.n = p * q
self.d = invmod(self.e, t)
# 加密和解密使比特和整數(shù)之間的加解密
def encrypt(self, binary_data: bytes):
int_data = uint_from_bytes(binary_data)
return pow(int_data, self.e, self.n)
def decrypt(self, encrypted_int_data: int):
int_data = pow(encrypted_int_data, self.d, self.n)
return uint_to_bytes(int_data)
if __name__ == '__main__':
alice = RSA(512, 3)
msg = b'Textbook RSA in Python'
ctxt = alice.encrypt(msg)
m = alice.decrypt(ctxt)
print(m)
print(ctxt)如下是結(jié)果運行圖：
總結(jié)
到此這篇關(guān)于如何用Python實現(xiàn)RSA加密算法的文章就介紹到這了,更多相關(guān)Python寫RSA加密算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Pycharm開發(fā)Django項目創(chuàng)建ORM模型的問題
ORM，全稱Object Relational Mapping，通過ORM我們可以通過類的方式去操作數(shù)據(jù)庫，而不用再寫原生的SQL語句，下面通過本文給大家介紹Pycharm開發(fā)Django項目ORM模型介紹，感興趣的朋友一起看看吧2021-10-10
這篇文章主要給大家介紹了關(guān)于Python爬蟲常用小技巧之設(shè)置代理IP的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用python具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-09-09
pytorch 求網(wǎng)絡(luò)模型參數(shù)實例
今天小編就為大家分享一篇pytorch 求網(wǎng)絡(luò)模型參數(shù)實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
解決出現(xiàn)Incorrect integer value: '''' for column ''id'' at row 1
這篇文章主要介紹了解決出現(xiàn)Incorrect integer value: '' for column 'id' at row 1的問題的相關(guān)資料,希望通過本文能幫助到大家，讓大家遇到這樣的問題及時的解決，需要的朋友可以參考下2017-10-10
Python pyinstaller實現(xiàn)圖形化打包工具
這篇文章主要介紹了一個使用Python PYQT5制作的關(guān)于pyinstaller打包工具,代替?zhèn)鹘y(tǒng)的cmd黑窗口模式打包頁面,實現(xiàn)更快捷方便的python打包體驗,希望對大家有所幫助2025-01-01
這篇文章主要介紹了解決Python傳遞中文參數(shù)的問題的相關(guān)資料,需要的朋友可以參考下2015-08-08
Python操作SQLite數(shù)據(jù)庫的方法詳解【導(dǎo)入,創(chuàng)建,游標(biāo),增刪改查等】
這篇文章主要介紹了Python操作SQLite數(shù)據(jù)庫的方法,簡單說明了sqlite數(shù)據(jù)庫的相關(guān)概念,并結(jié)合實例形式較為詳細(xì)的分析了Python針對sqlite數(shù)據(jù)庫的導(dǎo)入,創(chuàng)建,游標(biāo),增刪改查等操作技巧,需要的朋友可以參考下2017-07-07
在數(shù)學(xué)中，對集合的嚴(yán)格定義可能是抽象的且難以掌握。但實際上可以將集合簡單地認(rèn)為是定義明確的不同對象的集合，通常稱為元素或成員。Python 提供了一個內(nèi)置的集合類型來將對象分組到一個集合中，快跟隨小編一起學(xué)習(xí)一下吧2022-03-03
pytorch載入預(yù)訓(xùn)練模型后,實現(xiàn)訓(xùn)練指定層
今天小編就為大家分享一篇pytorch載入預(yù)訓(xùn)練模型后,實現(xiàn)訓(xùn)練指定層，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01
好久沒帶大家實現(xiàn)Python爬蟲了,文中有非常詳細(xì)的代碼示例,對不會爬蟲的小伙伴們很有幫助哦,需要的朋友可以參考下2021-06-06