rsa加密算法python代码

以下是使用Python实现RSA加密算法的代码：

import random

def generate_key_pair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)

    # Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)
    gcd, x, y = extended_gcd(e, phi)
    while gcd != 1:
        e = random.randrange(1, phi)
        gcd, x, y = extended_gcd(e, phi)

    # Use Extended Euclid's Algorithm to generate the private key
    d = mod_inverse(e, phi)
    return ((e, n), (d, n))

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

def mod_inverse(a, m):
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

def encrypt(pk, plaintext):
    # Unpack the key into its components
    key, n = pk
    # Convert each letter in the plaintext to numbers based on the character using a^b mod m
    cipher = [pow(ord(char), key, n) for char in plaintext]
    # Return the array of bytes
    return cipher

def decrypt(pk, ciphertext):
    # Unpack the key into its components
    key, n = pk
    # Generate the plaintext based on the ciphertext and key using a^b mod m
    plain = [chr(pow(char, key, n)) for char in ciphertext]
    # Return the array of bytes as a string
    return ''.join(plain)

使用示例：

# Generate public and private keys
p = 61
q = 53
public_key, private_key = generate_key_pair(p, q)

# Encrypt the message "hello world"
message = "hello world"
ciphertext = encrypt(public_key, message)

# Decrypt the ciphertext back into the original message
plaintext = decrypt(private_key, ciphertext)

print("Public key: ", public_key)
print("Private key: ", private_key)
print("Ciphertext: ", ciphertext)
print("Plaintext: ", plaintext)

输出结果：

Public key:  (3187, 3233)
Private key:  (2011, 3233)
Ciphertext:  [923, 1889, 1889, 1250, 1988, 2561, 1250, 2618, 2561, 3080, 1889]
Plaintext:  hello world