Security of such cryptosystem design?

Question

Is one able to reveal $m$ when

$$С = (m + r)^e \bmod N$$

1. $C$ is known
2. $r$ is known
3. $e$ is known
4. $N$ is known and not prime

Answer 1

Assuming we are additionally given that $0\le m<N$, then, yes, it is possible to reveal $m$: Just try the candidates one by one and check if $(m+r)^e\bmod B$ turns out to be $C$. Mathematically, this solves the problem. Also, we have found an explicit algorithm, albeit with exponential running time ($O(N)$, which is linear in $N$, but exponential in the number of bits used to represent $N$).

If we expect to be posed many questions for the same $N$ and $e$, just with different $C$, then the follwoing method saves some time: Find the prime factorization of $N$, use that to compute $\phi(N)=N\cdot\prod_{p\mid N}(1-\tfrac 1p)$ and find $d$ with $ed\equiv 1\pmod{\phi(N)}$. Once you have that, you can always find $m+r=C^d\bmod N$ (with some special care for the - presumably rare - cases when $\gcd(C,N)>1$). A straightforward method to factoring $N$ is trial division up to $\sqrt N$, thus giveing a run time $O(\sqrt N)$ for the first decoding and all later decodings are "for free".

Practically (i.e., for the cryptographic application), the methods described so far make it unfeasible to find $m$ within reasonable time. However, this does not constitute a proof that it is impossible. For example, some factorization methods work extremely fast if the factorization of $N$ was not chosen wisely (e.g., the product of two twin primes). So unless one considers and avoids all known factorization attacks when generating $N$, an attacker may be able to factor $N$ and decode the message. Also, unless the sender takes care with padding (e.g., by picking $r$ suitably) it is not unlikely that every now and then the clear text message is $<\sqrt[e]N$ so that $C=(m+r)^e$ without taking remainders; this allows us to find $m$ just by taking an $e$th root.

And then there is the possibility that someone someday finds an extremely fast general factorization algorithm. This is deemed unlikely but not impossible - the difficulty of factoring integers has not been proven, heck, we don't even know if it is not possible to turn any exponential algorithm into a polynomial one ("$P=NP$").