Changing the public key in an MD5 certificate Given a valid, signed X.509 certificate using the MD5 digest algorithm and an RSA public key, how feasible would it be to generate a public key which would, all other parts of the certificate being identical, not invalidate the existing digital signature when substituted into the certificate?
Given an existing certificate, it isn’t practical.

MD5 is preimage-resistant, so it is not practical (given $x, y: x = \text{MD5}(y)$) to find $z: z \neq y \land \text{MD5}(z) = x$

But MD5 is still a TERRIBLE choice

MD5 allows for trivial collisions.  This has been used by malware to forge code-signing certificates.