# 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 '15 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 Carmichael 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 '15 at 13:53

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.

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 '15 at 21:02