RSA算法的python实现

RSA算法是一种非常常见的加密算法，它可以用于数据加密和数字签名等场景。下面是RSA算法的Python实现：

import random
import math

# 生成指定位数的质数
def get_prime(nbits):
    while True:
        # 随机生成一个nbits位的奇数
        p = random.getrandbits(nbits) | (1 << nbits - 1) | 1
        if is_prime(p):
            return p

# 判断一个数是否为质数
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# 求两个数的最大公约数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# 求模反元素
def mod_inverse(a, m):
    g, x, y = extended_euclid(a, m)
    if g != 1:
        return None
    else:
        return x % m

# 扩展欧几里得算法
def extended_euclid(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = extended_euclid(b, a % b)
        return g, y, x - (a // b) * y

# 生成RSA密钥对
def generate_keypair(nbits):
    p = get_prime(nbits // 2)
    q = get_prime(nbits // 2)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = mod_inverse(e, phi)
    return (n, e), (n, d)

# RSA加密
def encrypt(m, public_key):
    n, e = public_key
    c = pow(m, e, n)
    return c

# RSA解密
def decrypt(c, private_key):
    n, d = private_key
    m = pow(c, d, n)
    return m

# 测试代码
if __name__ == '__main__':
    nbits = 2048
    public_key, private_key = generate_keypair(nbits)
    m = 123456789
    c = encrypt(m, public_key)
    m1 = decrypt(c, private_key)
    if m == m1:
        print("RSA encryption and decryption succeed!")
    else:
        print("RSA encryption and decryption failed!")

以上代码实现了RSA算法的密钥生成、加密和解密过程，可以自行修改`nbits`来指定生成的RSA密钥的长度。