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

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.)

-
Besides the quite obvious issue with regards to recovering the private exponent (or CRT parameters) first, you can only create a hash over a binary representation of a key. Sometimes a hash over the modulus of a key pair is used as identifier, you might mean that... –  Maarten Bodewes May 10 at 19:05

The standard definition of RSA (PKCS#1) has two formats for a private key corresponding to public key $(n,e)$ with $n=p\;q$ where $p$ and $q$ are distinct odd primes:

• $(n,d)$ where $e\;d\equiv 1\pmod{\operatorname{lcm}(p-1,q-1)}$ and $0<d<n$, from which it follows there are at least two private keys in this format;
• $(p,q,dp,dq,qInv)$ where $e\;dp\equiv 1\pmod{(p-1)}\;$, $e\;dq\equiv 1\pmod{(q-1)}\;$, $q\;qInv\equiv 1\pmod p$ and $0<dp<p\;$, $0<dq<q\;$, $0<qInv<p\;$; both orders of $p$ and $q$ are valid, and there are two private keys in this format.

There is a single, well defined DER encoding of each of these at least 4 private keys corresponding to public key $(n,e)$. Each will most likely have a distinct MD5 hash. Hence " the md5sum of the private key " asked in the question's title is not well defined.

Neither is " the md5sum of the private key $d$ " of the question's body well defined: we have several $d$, the question does not define which $d$, nor the meaning of md5sum applied to an integer (notice that MD5 is defined for bitstrings, but there are several integer-to-bitstring conversion conventions around; and md5sum is only defined for bytestrings, and there are even more integer-to-bytestring conversion conventions around).

We could polish the question so that it asks for something well-defined, like the MD5 (or equivalently md5sum) hash of the shortest bytestring holding a big-endian binary representation of the smallest $d$ making $(n,d)$ a working private key, and that would mathematically be a computable function of any $(n,e)$ forming a valid public key. However 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)\;$ , the Charmichael function, with $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ when $n$ factors as $p\;q$ with $p$ and $q$ distinct primes. 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.

-
I understand it is possible to factore n if we find another key that has the same GCD, is there a tool online that could process that? –  user3714670 May 12 at 13:53

You can't.

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

-
Technically, I am not aware of any proof that you can't. It is however highly plausible that this is impossible. –  yyyyyyy May 10 at 21:02

You cannot, you can however create a hash over the modulus. This is sometimes used as identifier for a key pair, e.g. in PKCS#11. The modulus is unique for RSA key pairs.

-