Can I switch out a private RSA Key, so that when decrypting a message, it is decrypted to a different message? Here's a task I've been struggling with: 
Say I have an encrypted message $c$, and a desired plaintext $m$. How can I define a valid private RSA Key $(d,N)$, so that $c^d \bmod N = m$

Note that the key needs to be valid!
My approach was to write the modulo equation as
$y \times N + m = x \times N + c^d$ so I get $c^d-m'=(y-x) \times N$. So I can simply set some value for $d$ and try to factorize the result to get $N$, but this factorization can be extremely hard because numbers are huge. Is there a better way to approach this?
Update: This other answer (temporarily hidden on request of the organizer of a CTF) details a different approach to the problem, working for all values of $m$ and $c$, yielding valid keys, that even are plausible except for a larger-than-customary $e$. These private keys will work nicely for those RSA implementations (including OpenSSL, pycrypto, and many others) accepting values of $e$ up to about $N/2$ (which is well within PKCS#1 limits). That's what the OP was asking for, rather than the following exploration.



In both crypto Catch-The-Flags and actual security attacks, it is important to determine what makes values accepted or not. Here two things matter most:


Will something check that $c&lt;N$ (which is often a requirement in actual uses of RSA). A comment by the OP suggests there's no such check.
What makes a private key unacceptable. Practice varies widely from most¹ to less stringent.


It happens that pycrypto (last indicated as applicable in a comment by the OP) is lenient on imported RSA keys, at least when using it's reference _slowcrypto.py code. See _importKeyDER and rsa_construct: as long as $N$, $e$, $d$, $p$ and $q$ are given, they are accepted as is. $d_p$, $d_q$, $q_\text{inv}$ are recomputed if imported from a key file or missing.

With such freedom, and $c^d\bmod N=m$ the only constraint involving $c$, if in the givens $m&lt;c$ (which I'll assume) then we can choose $N=c-m$ and $d=1$ (with other key parameters 42). The condition $c^d\bmod N=m$ gets met, success!

However, that can fail if the RSA private key is used in CRT form (using $p$, $q$, $d_p$, $d_q$, $q_\text{inv}$), which is common². We may be able to improve on this by searching a small $k\in[1,c/m)$ dividing $c−m$ and making $N=(c−m)/k$ odd and composite (if these are requirements). For $p$ and $q$, any decomposition as $N=p\,q$ with $p&gt;1$, $q&gt;1$, and $\gcd(p,q)=1$ should do. We'd set $e=d=1$, passing a test $e\,d\equiv1$ for any modulus. The key import will recompute $d_p=d_q=1$ and $q_\text{inv}=q^{-1}\bmod p$ as needed. The key should now work with or without using the CRT. I do not rule out that we could get away with $p=1$ or $q=1$ (with the other equal to $N$); or that, if we got blocked by a test that $e\ge3$, it could be circumvented with $e=p\,q-p-q+2$ or $e=\lambda(N)+1$.



¹ Testing that the key was generated per FIPS&nbsp;186-4 would include verifying that $N$ has exactly 1024, 2048 or 3072 bits, $N=p\,q$ with $p$ and $q$ primes each in interval $\left(2^{\left(\left\lceil\log_2(N)\right\rceil-1\right)/2},2^{\left\lceil\log_2(N)\right\rceil/2}\right)$, $e$ is odd and in $\left(2^{16},2^{256}\right)$, $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, $d_p=e^{-1}\bmod(p-1)$, $d_q=e^{-1}\bmod(q-1)$, $q_\text{inv}=q^{-1}\bmod p$. For 1024-bit $N$ the standard sets some extra requirement about $p\pm1$ and $q\pm1$, but these are never tested when accepting a key (contrary to the previous ones), because that would be very compute-intensive.

² We must however suppose that the advisable and common check that no fault crept in the computation of $m$ is skipped. That's performed by verifying $c=m^e\bmod N$, and that would fail even if we set an appropriate $e$ like $e=1$ or $e=\lambda(N)+1$. That would insure $c\equiv m^e\pmod N$, but not $c=m^e\bmod N$, since $c\ge N$ with our choice of $N$.