用python实现 RSA，参数p、q选取3位的十进制数；不使用python库函数

好的，RSA算法是一种非对称加密算法，需要选取两个大质数p和q，然后求出N=p*q，再选取e作为公钥，d作为私钥。下面是Python实现RSA的代码：

import random

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

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

def generate_key(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)

    # Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)

    # Use Euclid's Algorithm to verify that e and phi(n) are coprime
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)

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

    # Return public and private keypair
    return ((e, n), (d, n))

def mod_inverse(a, m):
    """
    Return the modular inverse of a % m
    """
    if gcd(a, m) != 1:
        return None  # no mod inverse if a & m aren't relatively prime
    # Calculate using the Extended Euclidean Algorithm:
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3  # floor division
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

p = 103
q = 107
public_key, private_key = generate_key(p, q)
print("Public key:", public_key)
print("Private key:", private_key)

message = 123
encrypted_msg = pow(message, public_key[0], public_key[1])
print("Encrypted message:", encrypted_msg)

decrypted_msg = pow(encrypted_msg, private_key[0], private_key[1])
print("Decrypted message:", decrypted_msg)

在这里，我们选取了两个三位的质数103和107，并使用generate_key函数生成了公钥和私钥。然后，我们选择一个数字作为明文，对其进行加密并输出密文。最后，我们将密文解密并输出原始消息。

请注意，由于p和q的大小只有3位，因此生成的密钥非常容易破解。在实际使用中，应该选择更大的质数。