RSA密钥生成、签名和验证没有给出预期的结果。

Question

出于教育目的，我正在尝试实现RSA密钥生成，然后签署一条带有后续验证的消息。虽然，我遵循密钥生成的一般公式，但最终验证返回False。

import hashlib

def fast_modular_exponentiation(a, b, n):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % n
        a = (a * a) % n
        b //= 2
    return result

def generate_RSA_keys(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537
    d = fast_modular_exponentiation(e, phi - 1, n)
    return e, d, n

def RSA_signature_generation(message, d, n):
    digest = int.from_bytes(hashlib.sha256(message).digest(), byteorder='big')
    signature = fast_modular_exponentiation(digest, d, n)
    return signature

def RSA_signature_verification(message, e, n, signature):
    digest = int.from_bytes(hashlib.sha256(message).digest(), byteorder='big')
    verification = fast_modular_exponentiation(signature, e, n) is digest
    return verification


# generate RSA keys
e, d, n = generate_RSA_keys(23, 47)

# message to be signed
message = b"hello world"

# generate RSA signature
signature = RSA_signature_generation(message, d, n)

# verify RSA signature
verification = RSA_signature_verification(message, e, n, signature)

print(verification) # False

运行代码将产生False而不是True。

Answer 1

对于每个提出同样问题的人来说，多亏了上面的评论，我可以找到一个可行的解决方案：

import hashlib
from Crypto.Util.number import getPrime


def fast_modular_exponentiation(a, b, n):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % n
        a = (a * a) % n
        b //= 2
    return result


def extended_euclidean_algorithm(exp_encrypt, totient):
    do, dn = 0, 1
    r_old = totient  # dont overwrite original value, keep for later
    nr = exp_encrypt
    while nr > 0:
        q = r_old // nr  # thats the quotient
        do, dn = dn, do - q * dn
        r_old, nr = nr, r_old - q * nr
    return do % totient if r_old == 1 else None


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


def generate_RSA_keys():
    # select target security
    t = 2048
    # select a public exponent e
    e = 65537
    while True:
        # select a prime p of length t/2
        p = getPrime(t // 2)
        # select a prime q of length t/2
        q = getPrime(t // 2)
        # compute n = pq
        n = p * q
        # compute phi(n) = (p-1)(q-1)
        phi = (p - 1) * (q - 1)
        # check if gcd(e, phi(n)) = 1
        if gcd(e, phi) == 1:
            break
    # compute d with the extended Euclidean algorithm
    d = extended_euclidean_algorithm(e, phi)
    # return the public key (e, n) and the private key (d, n)
    return e, d, n


def rsa_encryption(message, e, n):
    return fast_modular_exponentiation(message, e, n)


def rsa_decryption(ciphertext, d, n):
    return fast_modular_exponentiation(ciphertext, d, n)


def rsa_signature_generation(message, d, n):
    digest = int.from_bytes(hashlib.sha256(message).digest(), byteorder='big')
    signature = fast_modular_exponentiation(digest, d, n)
    return signature


def rsa_signature_verification(message, e, n, signature):
    digest = int.from_bytes(hashlib.sha256(message).digest(), byteorder='big')
    verification = fast_modular_exponentiation(signature, e, n) == digest
    return verification


if __name__ == '__main__':
    # generate RSA keys
    e, d, n = generate_RSA_keys()
    print(e)
    print(d)
    print(n)

    # message to be signed
    message = b"hello world"

    # convert message to integer
    message_int = int.from_bytes(message, byteorder='big')

    # encrypt the message
    ciphertext = rsa_encryption(message_int, e, n)
    print(int.from_bytes(message, byteorder='big'))
    print(ciphertext)

    # decrypt the message
    decrypted_message = rsa_decryption(ciphertext, d, n)
    print(decrypted_message)

    # convert the decrypted message to bytes
    decrypted_message_bytes = decrypted_message.to_bytes((decrypted_message.bit_length() + 7) // 8, byteorder='big')
    print(decrypted_message_bytes)

    print("=========================================")

    # generate the signature
    signature = rsa_signature_generation(message, d, n)
    print(signature)

    # verify the signature
    verification = rsa_signature_verification(message, e, n, signature)
    print(verification)