写一个基于RSA算法的数字签名的程序

以下是一个基于Python语言实现的RSA数字签名程序：

import random
import hashlib

# 生成质数
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

def generate_prime():
    while True:
        num = random.randint(100, 1000)
        if is_prime(num):
            return num

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

# 生成公钥和私钥
def generate_key_pair():
    # 随机生成两个质数p和q
    p = generate_prime()
    q = generate_prime()
    n = p * q
    phi_n = (p - 1) * (q - 1)

    # 选择一个与phi_n互质的整数e作为公钥
    while True:
        e = random.randint(2, phi_n-1)
        if extended_gcd(e, phi_n)[0] == 1:
            break

    # 计算e的模反元素d作为私钥
    gcd, d, _ = extended_gcd(e, phi_n)
    d = d % phi_n
    if d < 0:
        d += phi_n

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

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

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

# 签名
def sign(message, private_key):
    n, d = private_key
    hash = hashlib.sha256(message.encode('utf-8')).hexdigest()
    h = int(hash, 16)
    signature = pow(h, d, n)
    return signature

# 验证签名
def verify(message, signature, public_key):
    n, e = public_key
    hash = hashlib.sha256(message.encode('utf-8')).hexdigest()
    h = int(hash, 16)
    h_new = pow(signature, e, n)
    return h == h_new

# 测试
if __name__ == '__main__':
    # 生成密钥对
    public_key, private_key = generate_key_pair()

    # 待加密和签名的消息
    message = 'Hello, world!'

    # 加密
    ciphertext = encrypt(message, public_key)
    print('Ciphertext:', ciphertext)

    # 解密
    plaintext = decrypt(ciphertext, private_key)
    print('Plaintext:', plaintext)

    # 签名
    signature = sign(message, private_key)
    print('Signature:', signature)

    # 验证签名
    is_valid = verify(message, signature, public_key)
    print('Is valid:', is_valid)

在程序中，首先定义了一些辅助函数，包括生成质数、扩展欧几里得算法求解模反元素等。然后，利用这些函数实现了RSA算法的核心功能，包括生成密钥对、加密、解密、签名和验证签名。最后，在程序中进行了一个简单的测试，验证了程序的正确性。