Decrypting small integers under RSA

First of all you cannot have $e = 2$ or $e = 4$ because in order to generate the private exponent $d$ you need $e$ to be co prime with $phi(n)$ since $d = e^{-1}$ inside $mathbb{Z}/nmathbb{Z}$

And since $n = pq$ where $p$ and $q$ are primes (thus odd),

$phi(n) = (p-1)(q-1)$, so $phi(n)$ is even.

That's why $e$ has to be odd (co prime with an even number).

With this said let's suppose a small $e > 1$ odd, like $3$.

Let $ m $ be the message, $c = m^e mod n$ the ciphertext and $d$ the private exponent.

Typical lengths in bytes of the modulus $n$ are $1024$, $2048$ and even bigger so you can imagine how big is this number.

If the encryption is made without any padding you have the chances that $m$ is not very big, for example if the message is just the conversion of the string into an integer.

In these conditions you could have that $c = m^e < n$, so $m = sqrt[e]{c}$

If this is not the case you could try some small values for $k$ such that:

$m = sqrt[e]{c + kn}$

Note that this is also possible in case $e$ is a "normal" value but $n$ is exaggeratedly big.

Also note that this is not possible in normal conditions because the message is padded so that also a small message produces a very big number. (and of course $e$ and $n$ are chosen accurately)

Yes, you can do it and it is not difficult at all (the difficulty aka slowness increases as n increases). You must know, however, that all this becomes impractical with the rsa keys used in practice, all I am about to describe you is for pure educational purposes and you can test it with low numerical values.

You're actually solving:

$$ m ^ e equiv c pmod n $$

Where you know $ e, c, n $.

I will explain all the steps supposing that you already have solid knowledge.

1. First factorize $ n $, you will have two prime numbers $ p $ and $ q $ (see RSA key generation), now calculate:

$$ phi (n) = (p - 1) (q - 1) $$

2. Now you need to verify the invertibility of your $ c $ by verifying that:

$$ gcd (c, n) = 1 $$ $$ gcd(phi(n), e) = 1 $$

3. If both are true, you have to find $ d $, the modular multiplicative inverse of $ e pmod {phi (n)} $. The modular multiplicative inverse can be found with the Extended Euclidean algorithm, it's an integer such that:

$$ c cdot d equiv 1 pmod {phi (n)} $$

4. Now all the solutions looks like this: $ S = [c^d]_n = { c^d +k cdot n, k in Bbb Z }$

5. At this point what I recommend is to find a canonical representative for your solution class.

I'll show you an example about the canonical representative. Suppose that our set of solutions is: $ S = [25^{11}]_{62} $

And $ 25^{11} = 2,3842 cdot 10 ^ {15} $ and it's not very convenient to work on it. After various calculations we verify that: $$ [25 ^ 3]_{62} = [15625]_{62} = [62 cdot 252 + 1]_{62} = [62]_{62} cdot [252]_{62} + [1]_{62} = [1]_{62} $$ So: $$ [25^{11}]_{62} = [25^{3 cdot 3 + 2}]_{62} = [25^3]^3_{62} cdot [25 ^ 2]_{62} = [1]_{62} cdot [625]_{62} = [5]_{62} $$

Of course $ [5]_{62} $ is more comfortable to handle than $ [25^{11}]_{62} $

Since the RSA problem is assumed hard, we do not know and can't find the factorization of $n$.

We know (from standard RSA) that $m=c^{left(e^{-1}bmodvarphi(n)right)}bmod n$ fulfills the requirement $cequiv m^epmod n$, but we do not know how to compute $m$ without some extra info or oracle.

Is it hard to find $m$ under the RSA assumption (or any of its variants)?

Yes, but I have no better argument than: among integers $c>1$ independent of $n$, only exact $e^text{th}$ powers are known to make it easy to solve the RSA problem for arbitrary $n$ too large to factor and odd $e>1$ making $(n,e)$ a valid RSA public key. In addition, there in no such $c$ in the interval $[2,2^e)$, which with $e=65537$ as in a comment by the OP includes about all commonly used values of $n$, thus of $c$.

Solving $cequiv m^epmod n$ for small $c$ is not necessarily hard for other $c$ and whenever $n$ is hard to factor. Proof by counterexample: $c=2$, $e=65537$, $n=(3^{65537}-2)/29$. I can't factor that $n$, yet it's easy to find the solution $m=3$.

More formally: I'm about as confident about the hardness of the RSA problem than I am about that problem restricted to small $c>1$, provided that $c$ is not a power of $e$, and that factors of $n$ are random distinct primes large enough to make factoring $n$ unfeasible. Yet I'd be quite surprised if we could prove the hardness of that restricted RSA problem on the basis of the hardness of the normal RSA problem.