# 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$$ or $$c=4$$.

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? – Hasan Iqbal 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
• @fgrieu: what if we assume $e=65537$ and $c=2$. Furthermore, suppose $n$ is the product of two safe primes. – M.S. Dousti Apr 17 '20 at 5:31
• 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 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.

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