python 实现rsa数字签名,不调用库

实现RSA数字签名的步骤如下：

1. 随机生成两个质数p和q，并计算n=p*q。同时计算phi(n)=(p-1) * (q-1)。

2. 选择一个整数e，1<e<phi(n)，且e与phi(n)互质。

3. 计算d，使得(e*d)%phi(n)=1。

4. 将n和e作为公钥，n和d作为私钥。

5. 对要签名的数据进行哈希操作，得到其摘要值。

6. 使用私钥对摘要值进行加密，得到数字签名。

7. 将数字签名和原始数据一起发送给接收方。

8. 接收方对原始数据进行哈希操作，得到摘要值。

9. 使用公钥对数字签名进行解密，得到解密后的摘要值。

10. 将解密后的摘要值与接收方计算出的摘要值进行比较，如果相同，则说明数字签名是合法的。

以下是Python实现的示例代码：

import random

# 生成指定位数的质数
def generate_prime_number(n):
    while True:
        p = random.randint(2**(n-1), 2**n-1)
        if is_prime_number(p):
            return p

# 判断是否为质数
def is_prime_number(p):
    if p == 2:
        return True
    if p < 2 or p % 2 == 0:
        return False
    for i in range(3, int(p**0.5)+1, 2):
        if p % i == 0:
            return False
    return True

# 扩展欧几里得算法求逆元
def get_inverse(e, phi_n):
    x1, y1, x2, y2 = 1, 0, 0, 1
    r1, r2 = e, phi_n
    while r2 != 0:
        q = r1 // r2
        r1, r2 = r2, r1 - q*r2
        x1, y1, x2, y2 = x2, y2, x1-q*x2, y1-q*y2
    return x1 % phi_n

# 生成RSA公私钥
def generate_rsa_key(n_bits):
    p = generate_prime_number(n_bits//2)
    q = generate_prime_number(n_bits//2)
    n = p * q
    phi_n = (p-1) * (q-1)
    e = 65537
    d = get_inverse(e, phi_n)
    return n, e, d

# 使用私钥对消息进行签名
def rsa_sign(message, n, d, hash_func):
    hash_value = hash_func(message)
    signature_value = pow(hash_value, d, n)
    return signature_value

# 使用公钥验证签名是否合法
def rsa_verify(message, signature, n, e, hash_func):
    hash_value = hash_func(message)
    decrypted_value = pow(signature, e, n)
    return hash_value == decrypted_value

# 测试代码
if __name__ == '__main__':
    # 生成RSA公私钥
    n, e, d = generate_rsa_key(2048)

    # 待签名的消息
    message = b'Hello, RSA!'

    # 选择哈希算法
    hash_func = hashlib.sha256

    # 使用私钥对消息进行签名
    signature = rsa_sign(message, n, d, hash_func)

    # 使用公钥验证签名是否合法
    print(rsa_verify(message, signature, n, e, hash_func))

该代码生成一个2048位的RSA公私钥，使用SHA256哈希算法对消息进行签名和验证。可以根据实际需要调整公私钥长度和哈希算法。