RSA算法python实现

以下是Python中实现RSA算法的示例代码：

import random
import math

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

# 判断素数
def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif 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 generate_prime_number(n):
    while True:
        p = random.randint(2**(n-1), 2**n - 1)
        if is_prime(p):
            return p

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

# 求模反元素
def mod_inverse(a, m):
    d, x, y = extended_euclidean_algorithm(a, m)
    if d != 1:
        raise ValueError("a and m are not coprime")
    return x % m

# 生成公钥和私钥
def generate_key_pair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    while gcd(e, phi) != 1:
        e = random.randrange(1, phi)
    d = mod_inverse(e, phi)
    return ((n, e), (n, d))

# 加密
def encrypt(plaintext, public_key):
    n, e = public_key
    ciphertext = [pow(ord(char), e, n) for char in plaintext]
    return ciphertext

# 解密
def decrypt(ciphertext, private_key):
    n, d = private_key
    plaintext = [chr(pow(char, d, n)) for char in ciphertext]
    return ''.join(plaintext)

# 测试
if __name__ == '__main__':
    # 生成公钥和私钥
    p = generate_prime_number(32)
    q = generate_prime_number(32)
    public_key, private_key = generate_key_pair(p, q)

    # 显示公钥和私钥
    print("Public key:", public_key)
    print("Private key:", private_key)

    # 加密和解密
    plaintext = "Hello, world!"
    ciphertext = encrypt(plaintext, public_key)
    decrypted_plaintext = decrypt(ciphertext, private_key)

    # 显示加密和解密结果
    print("Plaintext:", plaintext)
    print("Ciphertext:", ciphertext)
    print("Decrypted plaintext:", decrypted_plaintext)

在此示例中，我们首先定义了一些辅助函数来实现RSA算法的各个步骤。

然后，我们使用这些函数来实现生成公钥和私钥，加密和解密的功能。

在主程序中，我们生成了一个公钥和一个私钥，并使用公钥来加密一条消息。然后我们使用私钥来解密加密后的消息，并将解密后的消息与原始消息进行比较。

请注意，此示例仅用于演示RSA算法的基本原理。在实际应用中，需要考虑许多安全问题，例如如何生成足够安全的素数，如何保护私钥等。