with RSA encryption, how do I find the md5sum of the private key from the public key?

Question

This is a purely mathematical question on RSA encryption.

Having $e$ as the public key exponent and $n$ the modulus of a public key. Can I recover the md5sum of the private key $d$ (inverse of $d$ according to the modulus.)

Thanks for your help.

Answer 1

From the public key $(n,e)$ can I recover the md5sum of the private key $d$ (inverse of $d$ according to the modulus).

No, because:

1. This quantity is not well-defined for multiple reasons
   • In RSA, $d$ is not the "inverse of $d$ according to the modulus". Common definitions include:
     • $d_\varphi=e^{-1}\bmod\varphi(n)$ where $\varphi(n)$ is Euler's totient, with $\varphi(n)=(p-1)(q-1)$ when $n$ is the product of two distinct primes.
     • $d_\lambda=e^{-1}\bmod\lambda(n)$ where $\lambda$ is the Carmichael function, with $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ when $n$ is the product of two distinct primes. It holds $\lambda(n)\le\varphi(n)/2$ and often $d_\lambda<d_\varphi$.
     • In the standard definition of RSA (PKCS#1), $d$ is any integer $d$ with $0<d<n$ and $e\;d\equiv 1\pmod{\lambda(n)}$. This includes at least $d=d_\lambda$ and $d=d_\lambda+\lambda(n)$, thus $d$ is not uniquely defined.
   • MD5 hashes bitstrings, and it's not specified one of the several representations of the same $d$ as bitstring: the ASN.1 encoding of $d$, a big-endian or little-endian encoding with or without padding to a fixed length.
2. Even if we fix the above (by e.g .asking for the MD5 hash of the shortest bytestring that's a litle-endian binary representation of $d_\lambda$, which is mathematically a computable function of any $(n,e)$ forming a valid public key), it remains that the most efficient known method to compute this function (see below) factors $n$, and is thus impractical for practically useful public keys $(n,e)$.

---

If we can factor $n$, we can efficiently compute $\lambda(n)$. If further $(n,e)$ is a valid public key then we can then efficiently compute the uniquely defined $d=e^{-1}\bmod\lambda(n)$ with $0<d<\lambda(n)$, and efficiently compute its MD5 hash or md5sum using some specified convention.

Answer 2

You cannot get a hash over the entire private key if you've just got $n$ and $e$. You can however create a hash over the modulus $n$. This is sometimes used as identifier for keys within a key pair, e.g. in PKCS#11. Usually SHA-1 is used however, not MD5.

The modulus is unique for RSA key pairs and links the public key and private key together.

md5sum is a GNU utility that performs MD5, it's not an algorithm in itself.

Answer 3

You can't.

Recovering the md5sum of the private key means uncovering the private key, which is considered impossible for large values of $n$.