Decrypting small integers under RSA

Question

Let $(n,e)$ be an RSA public key. Suppose $c = m^e \pmod n$, where $c>1$ is a very small integer. For concreteness, say $c=2$ and that $e = 65537$.

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

Answer 1

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}\bmod\varphi(n)\right)}\bmod n$ fulfills the requirement $c\equiv m^e\pmod 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 $c\equiv m^e\pmod 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 for small fixed odd $e>1$ [that is: solving for $m$ the equation $c=m^e\bmod n$ for random $c$ when $n$ is constructed as the product of large primes $p_i$ chosen at random among those such that $\gcd(p_i-1,e)=1$ ] as I am about that problem restricted to small $c>1$. Yet I'd be quite surprised if we could prove that hardness of the former problem implies hardness of the later.

Answer 2

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}/n\mathbb{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)

Answer 3

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} $