rsa加密算法实现代码

RSA加密算法是一种非对称加密算法，它的安全性基于两个大素数的乘积难以分解的数学难题。下面是一份Python实现的RSA加密算法代码示例：

import random

# 生成指定位数的大素数
def generate_prime_number(bits):
    while True:
        p = random.getrandbits(bits)
        if is_prime(p):
            return p

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

# 求最大公约数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 扩展欧几里得算法求模反元素
def extended_euclidean_algorithm(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        x, y, gcd = extended_euclidean_algorithm(b, a % b)
        return (y, x - (a // b) * y, gcd)

# 生成RSA公私钥对
def generate_rsa_key_pair(bits):
    p = generate_prime_number(bits//2)
    q = generate_prime_number(bits//2)
    n = p * q
    phi = (p-1) * (q-1)
    e = random.randrange(1, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)
    d = extended_euclidean_algorithm(e, phi)
    if d < 0:
        d += phi
    return (n, e), (n, d)

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

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

# 测试代码
if __name__ == '__main__':
    bits = 1024
    message = 'Hello, RSA!'
    m = int.from_bytes(message.encode(), 'big')
    public_key, private_key = generate_rsa_key_pair(bits)
    c = rsa_encrypt(m, public_key)
    decrypted_m = rsa_decrypt(c, private_key)
    decrypted_message = decrypted_m.to_bytes((decrypted_m.bit_length()+7)//8, 'big').decode()
    print('Message:', message)
    print('Encrypted:', c)
    print('Decrypted:', decrypted_m)
    print('Decrypted message:', decrypted_message)