# Decrypting small integers under RSA

Cryptography Asked by M.S. Dousti on January 22, 2021

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

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)

Answered by Carlo Ramponi on January 22, 2021

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

Answered by Andrea Dipace on January 22, 2021

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.

Answered by fgrieu on January 22, 2021

## Related Questions

### Low weight linear $varepsilon$-universal hash function

0  Asked on December 2, 2021 by jaytuma

### Diffie-Hellman: difficulty of computing $g^{x^2}$ given $g^x$?

1  Asked on December 2, 2021

### In RSA, given public key $(n,e)$ and $d^ebmod n$, can we factor $n$?

1  Asked on November 30, 2021

### What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)

1  Asked on November 28, 2021

### With RSA or ECC, if I encrypt my private key with my public key, is there a way to recover my private key?

2  Asked on November 28, 2021

### What will be appropriate AES padding characters?

2  Asked on November 23, 2021 by user3769778

### Why does verifiable secret sharing with an honest majority require a broadcast channel?

1  Asked on November 23, 2021

### How does RSA signature verification work?

3  Asked on November 19, 2021

### Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

1  Asked on November 17, 2021

### Generate AES key from weak string

1  Asked on November 13, 2021 by user81531

### Are the Serpent Test Vectors incorrect?

1  Asked on November 11, 2021

### What is the best deterministic authenticated encryption algorithm to date?

0  Asked on November 8, 2021 by gtramontina

### Simple explanation of sliding-window and wNAF methods of elliptic curve point multiplication

1  Asked on November 8, 2021 by simbro

### Can repeatedly encrypting a message with a secure cipher ever produce the original input like what happens in ROT13?

1  Asked on November 8, 2021 by cm9

### Definition of $x^u bmod k$

2  Asked on October 24, 2021

### How to recover RSA messages if they are padded with spaces?

1  Asked on October 24, 2021 by aviral-gupta

### How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?

1  Asked on October 24, 2021 by user81147

### Code used for McEliece cryptosystem

1  Asked on October 24, 2021

### Chaining one-time signatures

1  Asked on October 24, 2021 by uk-ny

Get help from others!