RSA: Construct private / public key for given cipher and plain text message let's say we are given a classical RSA encryption scheme, though we would like to "reverse" the task:

Given two messages $c, m$ choose $p, q, e$ such that $p, q$ are prime and $c ^ d \equiv m\pmod N$ with $d \cdot e \equiv 1 \pmod{(p - 1)(q - 1)}$; $N = p \cdot q$.

I was wondering how one could approach this problem? Is it even possible for some large N?

Also does the conditioning improve if we loosen the constraints of classic RSA, i.e. $GCD(e, LCM(p-1,q-1)) \neq 1$? On another question I have read, that it is possible to construct message collisions, if the parameters are ill-formed, i.e. the condition $GCD(e, LCM(p-1,q-1)) = 1$ is not satisfied. I thought it to be related, though I could not retrieve the information of how such an collision could be achieved (or if it is even feasable).
Note: klugreuter's answer outlined a different approach to the problem, that I developed here. This obsoletes the following, except perhaps when we want a small $e$.



We can compute $\mathbin|m^e-c\mathbin|$ for various small odd $e&gt;1$, and try to factor them (even partially). As soon as we get two distinct primes factors $p$ and $q$ for some $\mathbin|m^e-c\mathbin|$, with $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, $m&lt;p\,q$ (and $c&lt;p\,q$ if that's added to the problem statement), then we can compute $N$ and a $d$ matching $e$ for this $N$ by one of the methods used in RSA, and that solves the problem. That's at least sometime feasible by pulling moderate factors using ECM factoring (e.g. using GMP-ECM).

If $N$ is required to be large (including, because $m$ is; $c$ has lesser influence), it is hard to find $p$ and $q$ with large enough a product. But we can sometime find more than two distinct large primes dividing $m^e-c$, and compute $N$ and $d$ as in multi-prime RSA; that improves our chances to find $(N,e)$ passing scrutiny (but does not answer the problem as worded, since it requires $N$ to be a bi-prime).

Addition: in the question as asked, there's no requirement that $c&lt;N$ (that's normally part of RSA). When $m\ll c$, that allows to try the above with $e=1$, that is factor $c-m$, which is much smaller than above. If we get distinct prime factors $p$ and $q$ with $m&lt;p\,q$ that gives a solution. We can hide that we started from $e=1$ by adding a multiple of $\operatorname{lcm}(p-1,q-1)$ to $e$ and/or $d$.

Late addition/hint: if we are allowed to use $e=\operatorname{lcm}(p-1,q-1)+1$ as hypothesized above, then at least one choice of $e$ not discussed above is worth consideration.