如何用Python實(shí)現(xiàn)RSA加密算法

更新時(shí)間：2023年06月06日 15:47:50 作者：The-Back-Zoom

RSA加密算法是一種非對(duì)稱加密算法,即使用不同的密鑰進(jìn)行加密和解密,下面這篇文章主要給大家介紹了關(guān)于如何用Python實(shí)現(xiàn)RSA加密算法的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

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ù)分解問(wèn)題實(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之外沒(méi)有其他公因子，我們稱這兩個(gè)數(shù)是互素的，（就是兩個(gè)數(shù)除一外沒(méi)有公約數(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

方法二

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

方法二

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)。,上面說(shuō)了

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.1RSA算法代碼實(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ù)，沒(méi)找到就一直循環(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)