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.

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

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

- Now you need to
**verify the invertibility**of your $ c $ by verifying that:

$$ gcd (c, n) = 1 $$ $$ gcd(phi(n), e) = 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)} $$

Now all the

**solutions**looks like this: $ S = [c^d]_n = { c^d +k cdot n, k in Bbb Z }$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

0 Asked on December 2, 2021 by jaytuma

1 Asked on December 2, 2021

1 Asked on November 30, 2021

1 Asked on November 28, 2021

2 Asked on November 28, 2021

2 Asked on November 23, 2021 by user3769778

1 Asked on November 23, 2021

1 Asked on November 17, 2021

1 Asked on November 13, 2021 by answerfinder95

1 Asked on November 11, 2021

0 Asked on November 8, 2021 by gtramontina

1 Asked on November 8, 2021 by simbro

1 Asked on November 8, 2021 by cm9

1 Asked on October 24, 2021 by aviral-gupta

1 Asked on October 24, 2021 by user81147

1 Asked on October 24, 2021

1 Asked on October 24, 2021 by uk-ny

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir