RSA加密算法Python实现

RSA加密算法是目前使用最广泛的加密方式，具体流程见RSA加密算法
之前想过用C语言实现，但是由于C语言对整型的位宽有要求，RSA加密算法中需要使用的数字大小远远超出C语言中long long int 的最大值，最近学习了Python之后，发现Python没有这一要求，可以较容易的实现。

以下为2022年12月31日（距离首次发布1年多）重写版本

# -*- coding:utf-8 -*-
"""
Created on Sat 31 Dec 2022 2:06
@author: Feng
"""

from random import randint

"""
RSA算法流程
    生成公钥和私钥：
        1. 随机生成大素数p,q
        2. oula = (p-1)*(q-1)
        3. n = p*q
        4. 取公钥pubkey,使得pubkey与oula互质
        5. 计算密钥prikey,使得(prikey*pubkey)%oula = 1
        6. 公开公钥pubkey和n, 秘密保存私钥prikey, 销毁oula,p,q
    加密：
        m为原文, c为密文
        c = m**pubkey%n
    解密：
        m为原文, c为密文
        m = c**prikey%n
"""

class RSA:
    """ 实现RSA算法加密和解密的类 """

    class Cipher:
        """ 表示密文内容的类 """
        def __init__(self, text):
            self._ciphertext = text

        def __str__(self):
            """ 用*代替显示具体密文字符串 """
            return str('*' *len(self._ciphertext))

    def __init__(self):
        # p,q表示大素数
        p = self._create_prime()
        q = p
        while p==q:
            q = self._create_prime()      
        oula = (p-1)*(q-1)

        self.n = p * q
        # 公钥
        self.pubkey = self._creat_pubkey(oula)
        # 私钥
        self.__prikey = self._compute_prikey(oula,self.pubkey)
        
        # 销毁p,q,oula
        del p, q, oula

    #---------------------------公开方法------------------------------
    def encrypt(self, msg):
        """ 返回加密信息的Cipher类 """
        msg = self._str2ascii(msg)
        cipher = []
        for m in msg:
            c = m**self.pubkey %self.n
            cipher.append(chr(c))
        cipher = ''.join(cipher)
        cipher = self.Cipher(cipher)
        return cipher

    def decrypt(self, cipher):
        """ 返回密文的解密字符串表示 """
        cipher = self._str2ascii(cipher._ciphertext)
        msg = []
        for c in cipher:
            m = c**self.__prikey %self.n
            msg.append(chr(m))
        return ''.join(msg)

    #---------------------------私有方法------------------------------
    def _is_prime(self, n):
        """ 判断是否为素数 """
        for i in range(2,n):
            if n % i == 0:
                return False
        return True

    def _create_prime(self):
        """ 随机生成指定范围内的素数 """
        while True:
            n = randint(10,50) #越大越安全，此处考虑计算时间，取值较小
            if self._is_prime(n):
                return n

    def _is_relprime(self, minv, maxv):
        """ 判断是否互质 """
        for i in range(2,minv+1):
            if minv % i == 0 and maxv % i == 0:
                return False
        return True

    def _creat_pubkey(self, oula):
        """ 计算公钥 """
        top = oula
        while True:
            i = randint(2,top)
            for e in range(i,top):
                if self._is_relprime(e,oula):
                    return e     
            top = i    

    def _compute_prikey(self, oula,e):
        """ 计算私钥 """
        k = 1
        while ( k*oula+1 )% e != 0:
            k+=1
        return int((k*oula+1)/e)

    def _str2ascii(self, msg):
        """ 返回msg中每个字符的ASCII码的数组 """
        result = []
        for m in msg:
            result.append(ord(m)) 
        return result
  
    
if __name__ == "__main__":
    
    r = RSA()
    msg = "Hello"
    cipher = r.encrypt(msg)
    rmsg = r.decrypt(cipher)
    print(msg, cipher, rmsg)