RSA加密算法Python實現(xiàn)方式
更新時間：2024年02月18日 10:13:04 作者：安全天天學
這篇文章主要介紹了RSA加密算法Python實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
1.RSA算法簡介
1977年，三位數(shù)學家 Rivest、Shamir 和 Adleman 設計了一種算法，可以實現(xiàn)非對稱加密。
這種算法用他們?nèi)齻€人的名字命名，叫做RSA算法.RSA算法的特征如下:
- RSA算法是非對稱加密算法，及算法的加密密鑰與解密密鑰不同
- RAS是基于大數(shù)分解問題實現(xiàn)的算法，
- RSA算法的密鑰長度一般為1024位到2048位之間，密鑰很長，加密較慢
- RSA算法一般用在數(shù)字簽名比較多
- RSA還是分組密碼算法，需要對明文進行一組一組加密
2.RSA算法涉及的數(shù)學知識
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 d
2.4 取模運算
取模運算就是取余數(shù)運算
model = a % b
2.5 最大公因數(shù)
求最大公因數(shù)一般使用歐幾里得算法，歐幾里得算法又稱輾轉相除法，是指用于計算兩個非負整數(shù)a，b的最大公約數(shù)。
應用領域有數(shù)學和計算機兩個方面。
計算公式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ù)的基礎上使用的，兩個或多個整數(shù)公有的倍數(shù)叫做它們的公倍數(shù)，其中除0以外最小的一個公倍數(shù)就叫做這幾個整數(shù)的最小公倍數(shù)。
整數(shù)a，b的最小公倍數(shù)記為[a，b]，同樣的，a，b，c的最小公倍數(shù)記為[a，b，c]，多個整數(shù)的最小公倍數(shù)也有同樣的記號。
與最小公倍數(shù)相對應的概念是最大公約數(shù)，a，b的最大公約數(shù)記為（a，b）。
關于最小公倍數(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 歐幾里得算法
歐幾里得算法又稱輾轉相除法，是指用于計算兩個非負整數(shù)a，b的最大公約數(shù)。
應用領域有數(shù)學和計算機兩個方面。
計算公式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_t
3.RSA算法數(shù)學實現(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一般非常大，這里方便計算，取比較小的值，假設：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）
- 加密：假設明文 ＝ 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)
以上算法只能夠實現(xiàn)整數(shù)加密，這個算法就是演示了RSA算法的原理
4.2RSA算法代碼實現(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):
"""
米勒-拉賓素性檢驗
由于假設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:
"""
比特轉換位整數(shù)
:param xbytes:
:return:
"""
return int.from_bytes(xbytes, 'big')
def uint_to_bytes(x: int) -> bytes:
"""
整數(shù)轉換成比特的時候，一個整數(shù)對應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)
如下是結果運行圖：
總結
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
本文主要為大家介紹了Python中提供在無音頻的視頻中添加音頻的工具詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友可以參考一下2021-12-12
在本篇文章里我們給讀者們分享了關于python如何實現(xiàn)決策樹算法的相關知識點內(nèi)容，需要的朋友們參考下。2018-10-10
pip是Python包管理工具,該工具提供了對Python包的查找、下載、安裝、卸載的功能,這篇文章主要給大家介紹了關于Python?pip指定安裝源的相關資料,需要的朋友可以參考下2023-12-12
Python內(nèi)置函數(shù)delattr的具體用法
本篇文章主要介紹了Python內(nèi)置函數(shù)delattr的具體用法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11
這篇文章主要介紹了python的字典,實例分析了Python中返回一個返回值與多個返回值的方法,需要的朋友可以參考下2021-10-10
python中pandas庫中DataFrame對行和列的操作使用方法示例
這篇文章主要介紹了python中pandas庫中DataFrame對行和列的操作使用方法示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-06-06
Python列表排序 list.sort方法和內(nèi)置函數(shù)sorted用法
這篇文章主要介紹了Python列表排序 list.sort方法和內(nèi)置函數(shù)sorted用法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
計算機在開發(fā)過程中，代碼越寫越多，也就越難以維護，所以為了編寫可維護的代碼，我們會把函數(shù)進行分組，放在不同的文件里。在python里，一個.py文件就是一個模塊2019-10-10
本文主要介紹了基于OpenCV的攝像頭測距的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
本文并不會深入講解樹數(shù)據(jù)結構的基本的概念，僅是站在使用的角度說清楚動態(tài)查詢。閱讀此文之前，請預備一些樹的基礎知識。2023-01-01