RSA算法流程：
    生成公钥和私钥：
        1. 随机生成大素数p,q
        2. N的欧拉函数 φ(N) = (p-1)*(q-1)
        3. n = p*q
        4. 取公钥e,使得e与φ(N)互质
        5. 计算密钥d,使得(e*d)%φ(N) = 1
        6. 公开公钥e和n, 秘密保存私钥d, 销毁oula,p,q
    加密：
        m为原文, c为密文
        c = m^e%n 即 m^e ≡ c (mod n)
    解密：
        m为原文, c为密文
        m = c^d%n 即 c^d ≡ m (mod n)
1. 随机选两个不相等的质数61和53，并计算两数的积N=61*53=3233，N的长度就是密钥长度。3233的二进制是110010100001，一共12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要的场合是2048位。
2. 计算N的欧拉函数 φ(N)=(p-1)(q-1)=60*52=3120.
3. 在1到3120上随机选择了一个随机数e与φ(N)互质,e=17。
4. 计算e对φ(N)的模反元素d，即ed-1=yφ(N)。 （ed可以被φ(N)整除余1(9可以被2整除余1) 即ed-1可以被φ(N)整除(8能被2整除) 即ed-1=yφ(N)）
即求解：17x-3120y=1.用扩展欧几里得算法求解。可以算出一组解(x,y)=(2753,-15)，即d=2753。完成计算。
其中N=3233,e=17,d=2753。所以公钥就是(N,e)=(3233,17)，私钥(N,d)=(3233,2753)。实际应用中公钥和私钥都是采用ASN.1格式表达的。

算法一： 

#代码小白
import random
from random import randint

def is_prime(n):
    """ 判断是否为素数 """
    for i in range(2, n):
        if n % i == 0:
            print('此素数输入错误')
            return 0
    print('素数输入正确')


def create_prime(start,stop):
    """ 随机生成指定范围内的素数 """
    if start < 2:
        start = 2
    for i in range(start, stop+1):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            yield i

def is_relprime(minv, maxv):
    """ 判断e与oula是否互质 """
    for i in range(2, minv + 1):
        if minv % i == 0 and maxv % i == 0:
            print('e与oula并不互为质数')
            return False
    print('e与oula互为质数')
    return True

def compute_prikey(ol,ee):
    """ 计算私钥 """
    global d, k
    k = 1
    while (k * oula + 1) % e != 0:
        k += 1
    print(f'k={k}')
    d = int((k * oula + 1) / e)
    print(f'd={d}')


p = int(input("输入一个素数p: "))
is_prime(p)
q = int(input("再输入一个素数q: "))
is_prime(q)

n = p * q
print(f'n=p*q={n}')
oula = (p - 1) * (q - 1)
print(f'oula=(p - 1) * (q - 1)={oula}')

num=[]
for x in create_prime(0, oula):
    num.append(x)
e = random.choice(num)
print(f'随机质数:e={e}')

is_relprime(e,oula)

compute_prikey(oula,e)

print(f'为你生成的公钥是：(n,e)=({n},{e})')
print(f'为你生成的私钥是：(n,d)=({n},{d})')

m = int(input("输入需要加密的数据: "))

# n = int(input("输入您的公钥前排序列: "))
# e = int(input("输入您的公钥后排序列: "))
c = (m**e)%n
print(f"您获得的密文是：{c}")

n = int(input("输入您的私钥前排序列: "))
d = int(input("输入您的私钥后排序列: "))

m = (c**d)%n
print(f'密文的解密结果为：{m}')

运行结果：（只可以数字，加密数据大会出错~~~）

算法二：

'''（复制别人的，找不到出处了~~~）'''
import random

'''  辗转相除法求最大公约数'''
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
'''
欧几里得用于求两个数的乘法逆的扩展算法
'''
""" 计算私钥 """
def multiplicative_inverse(e,r):
    for i in range(r):
        if((e*i)%r == 1):
            return i

""" 判断是否为素数 """
def is_prime(num) -> object:
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    for n in range(3, int(num ** 0.5) + 2, 2):
        if num % n == 0:
            return False
    return True

""" 判断pq是否都为素数 """
def generate_keypair(p, q):
    if not (is_prime(p) and is_prime(q)):
        raise ValueError('Both numbers must be prime.')
    elif p == q:
        raise ValueError('p and q cannot be equal')
    # n = pq
    n = p * q

    # 欧拉函数φ(n)
    oula = (p - 1) * (q - 1)

    # 选择一个整数e，使e和φ(n)为互质
    e = random.randrange(1, oula)

    # 用欧几里得算法验证e和φ(n)是互质
    g = gcd(e, oula)
    while g != 1:
        e = random.randrange(1, oula)
        g = gcd(e, oula)

    # 使用扩展欧几里得算法生成私钥
    d = multiplicative_inverse(e, oula)

    # 返回公共和私有密钥 ,公钥是(e, n)，私钥是(d, n)
    return ((e, n), (d, n))


def encrypt(pk, plaintext):
    # 将密钥解压缩到它的组件中
    key, n = pk
    #使用a^b mod m将明文中的每个字母转换为基于字符的数字
    cipher = [(ord(char) ** key) % n for char in plaintext]
    # 返回字节数组
    return cipher


def decrypt(pk1, pk2, ciphertext):
    #将密钥解压缩到其组件中
    key, n = pk1, pk2
    #根据密文和密钥使用a^b mod m生成明文
    plain = [chr((char ** key) % n) for char in ciphertext]
    # 以字符串形式返回字节数组
    return ''.join(plain)


if __name__ == '__main__':

    p = int(input("输入一个素数: "))
    q = int(input("再输入一个素数: "))

    public, private = generate_keypair(p, q)
    print('为你生成的公钥是：', public)
    print("为你生成的私钥是：", private)

    message = input("输入需要加密的数据: ")
    encrypted_msg = encrypt(public, message)
    print("您获得的密文是：", ''.join(map(lambda x: str(x), encrypted_msg)))

    privatee = []
    privatee.append(int(input('输入您的私钥前排序列')))
    privatee.append(int(input('输入您的私钥后排序列')))

    print('密文的解密结果为：', decrypt(privatee[0], privatee[1], encrypted_msg))

运行结果：（可以纯数字、纯字母~~~）

改进：使用python库gmpy2库实现加解密:

参考原文链接：RSA算法之实现篇（Python版）_qmickecs的博客-CSDN博客

import gmpy2
from gmpy2 import mpz
import binascii

def gen_prime(rs):
    """生成二进制位数为1024的随机素数"""
    p = gmpy2.mpz_urandomb(rs, 1024)
    while not gmpy2.is_prime(p):
        p = p + 1
    return p

def gen_key():
    """生成密钥"""
    rs = gmpy2.random_state()
    p = gen_prime(rs)
    q = gen_prime(rs)
    return p, q

def encrypt(e, n, message):
    """将输入消息转换成16进制数字并加密，支持utf-8字符串"""
    M = mpz(binascii.hexlify(message.encode('utf-8')), 16)
    C = gmpy2.powmod(M, e, n)
    return C

def decrypt(d, n, C):
    """对输入的密文进行解密并解码"""
    M = gmpy2.powmod(C, d, n)
    return binascii.unhexlify(format(M, 'x')).decode('utf-8')

def main():
    # 密钥生成
    p, q = gen_key()
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = gmpy2.invert(e, phi)

    # 输入消息
    message = input('输入待加密的消息：\n')

    # 加密
    C = encrypt(e, n, message)
    print('16进制密文：', hex(C))

    # 解密
    print('解密后的消息：', decrypt(d, n, C))

if __name__ == '__main__':
    main()
'''
输入待加密的消息：
34542
16进制密文： 0x56f8a6e0......
解密后的消息： 34542
-----------------
输入待加密的消息：
该如何的
16进制密文： 0x25a1bca.....
解密后的消息： 该如何的
-----------------
输入待加密的消息：
htgdhg
16进制密文： 0x6572366a62
解密后的消息： htgdhg
'''

补充：后面一篇Paillier加法同态文章中有补充验证RSA的乘法同态特性。