Recover an RSA public key from its signatures

recover_pubkey.py

#!/usr/bin/env python3
"""
This script recovers the RSA public key that was used to make signatures, given
any two such signatures in X.509 certificates. Python 3 is required, along with
recent versions of pyasn1, pyasn1-modules, and pyprimes. Runtime is nearly
instantaneous when the public key uses e=3, and 3+ hours when the public key
uses e=65537. (This could be vastly improved by using a more efficient GCD
library function) To recover a public key, run this script with the file names
of two certificates as command line arguments. Certificates can be in PEM or
DER format.

To recover the RSA public key, this script parses the certificates, calculates
the expected hash of the to-be-signed portion of the certificate, DER-encodes
the hash in the appropriate ASN.1 structure and pads it with PKCS#1 v1.5, and
parses the signature into a native Python integer. The script then guesses a
value for the public exponent (only 3 and 65537 are considered), raises each
signature to the power of the public exponent, and subtracts each plaintext
padded value from the result. Through some algebra, we know that both of these
differences are multiples of the public modulus. Thus, the script next
computes the greatest common divisor of the two differences. If the two
differences are coprime, that means the public exponent guess was wrong
(or the two signatures were not actually produced by the same public key),
otherwise the public modulus is calculated by dividing small primes out of
the GCD result.

Once the whole public key is known, it is printed out in decimal and
hexadecimal formats, along with hashes of the corresponding
SubjectPublicKeyInfo structure.
"""

import argparse
import binascii
import fractions
import hashlib

import pyasn1.codec.der.decoder
import pyasn1.codec.der.encoder
import pyasn1.type.univ
import pyasn1_modules.pem
import pyasn1_modules.rfc2315
import pyasn1_modules.rfc2437
import pyasn1_modules.rfc2459
import pyasn1_modules.rfc5280
import pyprimes

HASH_OID_LOOKUP = {
    pyasn1_modules.rfc2437.sha1WithRSAEncryption:
    pyasn1_modules.rfc2437.id_sha1,
    pyasn1.type.univ.ObjectIdentifier("1.2.840.113549.1.1.11"):
    pyasn1.type.univ.ObjectIdentifier("2.16.840.1.101.3.4.2.1")
}

HASH_CONSTRUCTOR_LOOKUP = {
    pyasn1_modules.rfc2437.sha1WithRSAEncryption:
    hashlib.sha1,
    pyasn1.type.univ.ObjectIdentifier("1.2.840.113549.1.1.11"):
    hashlib.sha256,
}


def bytes_to_integer(x):
    accum = 0
    for b in x:
        accum <<= 8
        accum |= b
    return accum


def load_cert(path):
    with open(path, "rb") as f:
        data = f.read()
    if data.startswith(b"-----BEGIN"):
        # decode PEM
        with open(path, "r") as f:
            return pyasn1_modules.pem.readPemFromFile(f)
    else:
        # assume it's binary DER-encoded data
        return data


def hex_string(buf):
    return binascii.hexlify(buf).decode("ascii")


def wrap_spki(n, e, n_bits):
    null, _ = pyasn1.codec.der.decoder.decode(
            b"\x05\x00",
            pyasn1.type.univ.Null())
    pk = pyasn1_modules.rfc2437.RSAPublicKey()
    pk["modulus"] = n
    pk["publicExponent"] = e
    pk_bytes = pyasn1.codec.der.encoder.encode(pk)
    pk_string = "'{}'H".format(hex_string(pk_bytes))
    spki = pyasn1_modules.rfc5280.SubjectPublicKeyInfo()
    spki["algorithm"]["algorithm"] = pyasn1_modules.rfc2437.rsaEncryption
    spki["algorithm"]["parameters"] = null
    spki["subjectPublicKey"] = pk_string
    return pyasn1.codec.der.encoder.encode(spki)


def parse_certificate(cert_data):
    cert, _ = pyasn1.codec.der.decoder.decode(
            cert_data,
            pyasn1_modules.rfc5280.Certificate())
    algorithmIdentifier = cert["signatureAlgorithm"]
    signature_algorithm = algorithmIdentifier["algorithm"]
    pyasn1.codec.der.decoder.decode(
            algorithmIdentifier["parameters"],
            pyasn1.type.univ.Null())
    tbs_der = pyasn1.codec.der.encoder.encode(cert["tbsCertificate"])
    return (tbs_der,
            int(cert["signature"]),
            len(cert["signature"]),
            signature_algorithm)


def pkcs1_15_pad(message, modulus_bits):
    k = (modulus_bits + 7) // 8
    ps = b"\xff" * (k - 2 - 1 - len(message))
    padded = b"\x00\x01" + ps + b"\x00" + message
    return padded


def hash_tbs(tbs, signature_algorithm):
    digest = HASH_CONSTRUCTOR_LOOKUP[signature_algorithm]()
    digest.update(tbs)
    return digest.digest()


def spki_hashes(data):
    digest = hashlib.sha1()
    digest.update(data)
    digest256 = hashlib.sha256()
    digest256.update(data)
    return digest.digest(), digest256.digest()


def wrap_hash(hash_bytes, signature_algorithm):
    null, _ = pyasn1.codec.der.decoder.decode(
            b"\x05\x00",
            pyasn1.type.univ.Null())

    algorithmIdentifier = pyasn1_modules.rfc2315.DigestAlgorithmIdentifier()
    algorithmIdentifier["algorithm"] = HASH_OID_LOOKUP[signature_algorithm]
    algorithmIdentifier["parameters"] = null
    digestInfo = pyasn1_modules.rfc2315.DigestInfo()
    digestInfo["digestAlgorithm"] = algorithmIdentifier
    digestInfo["digest"] = hash_bytes
    return pyasn1.codec.der.encoder.encode(digestInfo)


def slow_divisor_search(s1, c1, s2, c2):
    e_guesses = [3, 0x10001]
    for e in e_guesses:
        diff1 = pow(s1, e) - c1
        diff2 = pow(s2, e) - c2
        candidate = fractions.gcd(diff1, diff2)
        if candidate == 1:
            continue
        if candidate == 0:
            continue
        for prime in pyprimes.primes_below(1000000):
            while candidate % prime == 0:
                candidate //= prime
        if pow(s1, e, candidate) == c1:
            if pow(s2, e, candidate) == c2:
                return candidate, e


def main():
    parser = argparse.ArgumentParser(
            description="Recovery of public modulus from RSA signatures")
    parser.add_argument(
            "certs",
            nargs=2,
            metavar="path",
            help="Certificate file")
    args = parser.parse_args()

    cert1 = load_cert(args.certs[0])
    (
        tbscert1,
        signature1,
        modulus_bit_length_1,
        signature_algorithm_1
    ) = parse_certificate(cert1)
    hash1 = hash_tbs(tbscert1, signature_algorithm_1)
    message1 = wrap_hash(hash1, signature_algorithm_1)
    c1 = bytes_to_integer(pkcs1_15_pad(message1, modulus_bit_length_1))

    cert2 = load_cert(args.certs[1])
    (
        tbscert2,
        signature2,
        modulus_bit_length_2,
        signature_algorithm_2
    ) = parse_certificate(cert2)
    hash2 = hash_tbs(tbscert2, signature_algorithm_2)
    message2 = wrap_hash(hash2, signature_algorithm_2)
    c2 = bytes_to_integer(pkcs1_15_pad(message2, modulus_bit_length_2))

    assert signature_algorithm_1 == signature_algorithm_2
    assert modulus_bit_length_1 == modulus_bit_length_2
    n, e = slow_divisor_search(signature1, c1, signature2, c2)

    print("n={} e={}".format(n, e))
    print("n=0x{:x} e=0x{:x}".format(n, e))

    spki = wrap_spki(n, e, modulus_bit_length_1)
    spki_sha1_hash, spki_sha256_hash = spki_hashes(spki)
    print("SHA-1 hash of SubjectPublicKeyInfo: {}"
          .format(hex_string(spki_sha1_hash)))
    print("SHA-256 hash of SubjectPublicKeyInfo: {}"
          .format(hex_string(spki_sha256_hash)))


if __name__ == "__main__":
    main()