# Decrypting small integers under RSA

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)?

• shouldn't the security depend on the choice of n? Apr 17 '20 at 0:26
• Depends on the magnitude of $e$ and to a lesser degree of $n$. Illustration: $e=3$, $n$ the product of two large distinct primes $p$ and $q$ with $p\equiv q\equiv5\pmod 6$, $c=8$.
– fgrieu
Apr 17 '20 at 5:14
• By definition n should always be a very large number, resulting on the multiplication of two big primes (p and q).
– Maf
Apr 19 '20 at 16:46

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.

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)

• Notice that the OP has added this comment stating that $e=65537$, $c=2$, and $(p-1)/2$ and $(q-1)/2$ are both primes (the later ensures that $e$ is a valid RSA public exponent if $n$ is large enough to be hard to factor). This makes it unlikely that the attacks in the answer apply.
– fgrieu
Apr 20 '20 at 14:01

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

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

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

1. 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)}$$

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

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

• If one can factor $n$ as assumed in this answer, the RSA assumption does not hold, and the question contains "under the RSA assumption".
– fgrieu
Apr 19 '20 at 22:32