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

3 Answers

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

Add your own answers!

Related Questions

What will be appropriate AES padding characters?

2  Asked on November 23, 2021 by user3769778


How does RSA signature verification work?

3  Asked on November 19, 2021


Padding Oracle Attack with AES-128-CTR and MAC

1  Asked on November 13, 2021 by answerfinder95


Generate AES key from weak string

1  Asked on November 13, 2021 by user81531


Definition of $x^u bmod k$

2  Asked on October 24, 2021


Ask a Question

Get help from others!

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