rsa算法python代码实现

RSA算法是一种非对称加密算法，用于数据加密和解密。以下是使用Python实现RSA算法的代码示例：

import random

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def multiplicative_inverse(e, phi):
    def extended_gcd(a, b):
        if b == 0:
            return (a, 1, 0)
        else:
            d, x, y = extended_gcd(b, a % b)
            return (d, y, x - (a // b) * y)

    d, x, _ = extended_gcd(e, phi)
    return x % phi if d == 1 else None

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 = 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 = multiplicative_inverse(e, phi)

    return ((e, n), (d, n))

def encrypt(public_key, plaintext):
    e, n = public_key
    encrypted_msg = [pow(ord(char), e, n) for char in plaintext]
    return encrypted_msg

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

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

# 示例用法
p = 61
q = 53

public_key, private_key = generate_keypair(p, q)

message = "Hello, RSA!"
encrypted_message = encrypt(public_key, message)
decrypted_message = decrypt(private_key, encrypted_message)

print(f"Original message: {message}")
print(f"Encrypted message: {encrypted_message}")
print(f"Decrypted message: {decrypted_message}")

注意，这只是一个简单的RSA实现示例，仅用于学习和理解RSA算法的基本概念。在实际使用中，需要考虑更多的安全性和性能方面的因素。