Skip to content

Instantly share code, notes, and snippets.

@divergentdave
Last active December 9, 2022 05:15
Show Gist options
  • Save divergentdave/40ac9c7224b382166c905e76595bcf73 to your computer and use it in GitHub Desktop.
Save divergentdave/40ac9c7224b382166c905e76595bcf73 to your computer and use it in GitHub Desktop.
Recover an RSA public key from its signatures
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment