RSA加密算法Python實(shí)現(xiàn)方式
更新時(shí)間：2024年02月18日 10:13:04 作者：安全天天學(xué)
這篇文章主要介紹了RSA加密算法Python實(shí)現(xiàn)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
1.RSA算法簡(jiǎn)介
1977年，三位數(shù)學(xué)家 Rivest、Shamir 和 Adleman 設(shè)計(jì)了一種算法，可以實(shí)現(xiàn)非對(duì)稱加密。
這種算法用他們?nèi)齻€(gè)人的名字命名，叫做RSA算法.RSA算法的特征如下:
- RSA算法是非對(duì)稱加密算法，及算法的加密密鑰與解密密鑰不同
- RAS是基于大數(shù)分解問題實(shí)現(xiàn)的算法，
- RSA算法的密鑰長(zhǎng)度一般為1024位到2048位之間，密鑰很長(zhǎng)，加密較慢
- RSA算法一般用在數(shù)字簽名比較多
- RSA還是分組密碼算法，需要對(duì)明文進(jìn)行一組一組加密
2.RSA算法涉及的數(shù)學(xué)知識(shí)
2.1互素
兩個(gè)正整數(shù)，除了1之外沒有其他公因子，我們稱這兩個(gè)數(shù)是互素的，（就是兩個(gè)數(shù)除一外沒有公約數(shù)，就是互素），如下是判斷兩個(gè)數(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 歐拉定理
如果兩個(gè)正整數(shù)a和n互素，則n的歐拉函數(shù)φ(n)可以讓下面的式子成立
其中a上面的表達(dá)式為歐拉函數(shù)，歐拉函數(shù)的計(jì)算方法為，比如計(jì)算n的歐拉函數(shù)，就是找從1到n-1和n互素元素的個(gè)數(shù)，其中質(zhì)數(shù)的歐拉函數(shù)值為n-1，判斷一個(gè)數(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 d
2.4 取模運(yùn)算
取模運(yùn)算就是取余數(shù)運(yùn)算
model = a % b
2.5 最大公因數(shù)
求最大公因數(shù)一般使用歐幾里得算法，歐幾里得算法又稱輾轉(zhuǎn)相除法，是指用于計(jì)算兩個(gè)非負(fù)整數(shù)a，b的最大公約數(shù)。
應(yīng)用領(lǐng)域有數(shù)學(xué)和計(jì)算機(jī)兩個(gè)方面。
計(jì)算公式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
- 方法2
def gcd(a, b):
"""
求最大公約數(shù)
:param a:
:param b:
:return:
"""
while b:
a, b = b, a % b
return a
2.6 最小公倍數(shù)
最小公倍數(shù)是再最大公因數(shù)的基礎(chǔ)上使用的，兩個(gè)或多個(gè)整數(shù)公有的倍數(shù)叫做它們的公倍數(shù)，其中除0以外最小的一個(gè)公倍數(shù)就叫做這幾個(gè)整數(shù)的最小公倍數(shù)。
整數(shù)a，b的最小公倍數(shù)記為[a，b]，同樣的，a，b，c的最小公倍數(shù)記為[a，b，c]，多個(gè)整數(shù)的最小公倍數(shù)也有同樣的記號(hào)。
與最小公倍數(shù)相對(duì)應(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
- 方法2
def lcm(a, b):
"""
求最大公倍數(shù)
:param a:
:param b:
:return:
"""
return a // gcd(a, b) * b
2.7 歐幾里得算法
歐幾里得算法又稱輾轉(zhuǎn)相除法，是指用于計(jì)算兩個(gè)非負(fù)整數(shù)a，b的最大公約數(shù)。
應(yīng)用領(lǐng)域有數(shù)學(xué)和計(jì)算機(jī)兩個(gè)方面。
計(jì)算公式gcd(a,b) = gcd(b,a mod b)。上面說了
2.8 擴(kuò)展歐幾里得算法
求的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_t
3.RSA算法數(shù)學(xué)實(shí)現(xiàn)
3.1理論
- 隨意選擇兩個(gè)大的質(zhì)數(shù)p和q，p不等于q，計(jì)算N = pq.
- 根據(jù)歐拉函數(shù)，求得φ(N)=φ§φ(q)=(p-1)(q-1)。這是一個(gè)公式如果N = pq，那么φ(N)=φ(p)φ(q)，又因?yàn)閜和q都是素?cái)?shù)，φ(p) = p-1，所以φ(N)=φ(p)φ(q)=(p-1)(q-1)
- 選擇一個(gè)數(shù)e，使e大于1，并且e小于φ(N)，找一個(gè)數(shù)d，使得ed≡1(mod φ(N))，（e,n）為公鑰，（d,e）為私鑰
- 加密：m^e ≡ c (mod n)，其中c為密文，解密：c^d ≡ m (mod n)
加解密圖解如下：
3.2實(shí)踐
首先找兩個(gè)數(shù)，及p和q，p和q一般非常大，這里方便計(jì)算，取比較小的值，假設(shè)：p ＝ 17，q ＝ 19(p,q互素)
- n = p ＊ q ＝ 323
- φ(n) = (p-1) * (q-1) = 144
- 隨機(jī)取一數(shù)e，使1 < e < φ(n)并且gcd(e,φ(n)) =1,e=5合適（還有很多數(shù)都合適，這里只取一個(gè)數(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算法代碼實(shí)現(xiàn)
4.1RSA算法代碼實(shí)現(xiàn)1
# 求兩個(gè)數(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("請(qǐng)給定第一個(gè)質(zhì)數(shù)p的值："))
q = int(input("請(qǐng)給定第二個(gè)質(zhì)數(shù)q的值："))
x = int(input("請(qǐng)給定要加密的消息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ù)加密，這個(gè)算法就是演示了RSA算法的原理
4.2RSA算法代碼實(shí)現(xiàn)2
from random import randrange
import math
def prime(n):
"""
判斷一個(gè)數(shù)是不是素?cái)?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ù),不確定是不是素?cái)?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個(gè)素?cái)?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):
"""
米勒-拉賓素性檢驗(yàn)
由于假設(shè)n是一個(gè)素?cái)?shù)，n-1=a^s*d,s和d是常量，改變a的值，檢測(cè)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):
"""
獲取大素?cái)?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):
"""
擴(kuò)展歐幾里得算法
: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í)候，一個(gè)整數(shù)對(duì)應(yīng)32位比特?cái)?shù)
:param x:
:return:
"""
if x == 0:
return bytes(1)
return x.to_bytes((x.bit_length() + 7) // 8, 'big') #做到盡量不補(bǔ)零
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
# 找出一個(gè)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é)果運(yùn)行圖：
總結(jié)
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
Python實(shí)現(xiàn)視頻中添加音頻工具詳解
本文主要為大家介紹了Python中提供在無音頻的視頻中添加音頻的工具詳解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友可以參考一下2021-12-12
在本篇文章里我們給讀者們分享了關(guān)于python如何實(shí)現(xiàn)決策樹算法的相關(guān)知識(shí)點(diǎn)內(nèi)容，需要的朋友們參考下。2018-10-10
pip是Python包管理工具,該工具提供了對(duì)Python包的查找、下載、安裝、卸載的功能,這篇文章主要給大家介紹了關(guān)于Python?pip指定安裝源的相關(guān)資料,需要的朋友可以參考下2023-12-12
Python內(nèi)置函數(shù)delattr的具體用法
本篇文章主要介紹了Python內(nèi)置函數(shù)delattr的具體用法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-11-11
這篇文章主要介紹了python的字典,實(shí)例分析了Python中返回一個(gè)返回值與多個(gè)返回值的方法,需要的朋友可以參考下2021-10-10
python中pandas庫中DataFrame對(duì)行和列的操作使用方法示例
這篇文章主要介紹了python中pandas庫中DataFrame對(duì)行和列的操作使用方法示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
Python列表排序 list.sort方法和內(nèi)置函數(shù)sorted用法
這篇文章主要介紹了Python列表排序 list.sort方法和內(nèi)置函數(shù)sorted用法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-03-03
計(jì)算機(jī)在開發(fā)過程中，代碼越寫越多，也就越難以維護(hù)，所以為了編寫可維護(hù)的代碼，我們會(huì)把函數(shù)進(jìn)行分組，放在不同的文件里。在python里，一個(gè).py文件就是一個(gè)模塊2019-10-10
基于OpenCV的攝像頭測(cè)距的實(shí)現(xiàn)示例
本文主要介紹了基于OpenCV的攝像頭測(cè)距的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
本文并不會(huì)深入講解樹數(shù)據(jù)結(jié)構(gòu)的基本的概念，僅是站在使用的角度說清楚動(dòng)態(tài)查詢。閱讀此文之前，請(qǐng)預(yù)備一些樹的基礎(chǔ)知識(shí)。2023-01-01