0
$\begingroup$

Let $a$ be the plaintext message, $e$ be a small prime exponent (such as 11, 13, 17 etc.), $b$ be cipher text and $n$ be a large modulo (non-prime).

Suppose that:

$b \equiv a^e \space mod \space n$

If we know $b$, $e$ and $n$, can we possibly calculate $a$?

$\endgroup$
4
  • 1
    $\begingroup$ If you know factorization of $n$ this is easy. Otherwise in general cases not. $\endgroup$ Jan 30, 2016 at 18:11
  • $\begingroup$ This is related to the RSA cryptosystem en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation . You can decrypt a message if you can factor the modulus, which is easy to factor if it has only small prime factors. If k is the number of prime factors then the smallest prime factor cannot have more than #bits(n)/k bits. So k=2 is optimal. The advantage to use a small exponent e is that encryption is very fast. But does a small e have drawbacks? It seems so: check footnote 8 of the wiki article or paragraph 4 of crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html . $\endgroup$
    – miracle173
    Jan 30, 2016 at 23:15
  • $\begingroup$ So I think answers should concentrate on the fact that e is small an not on well known requirements of the RSA. $\endgroup$
    – miracle173
    Jan 30, 2016 at 23:20
  • 1
    $\begingroup$ If $a$ is among a small known set (e.g. is the name of a classmate on the call roll per some encoding), and $n$, $e$, $b$ are known, then we much likely can find $a$ by trial and error. $\endgroup$
    – fgrieu
    Jan 31, 2016 at 18:10

3 Answers 3

1
$\begingroup$

It is conjectured to be hard to recover $a$ given only $b$, $e$, and $n$. This is called the RSA assumption. If an efficient factorization algorithm exists, this assumption is false.

However, it is possible that the RSA assumption is false and there exists no efficient factorization algorithm. In other words, the hardness of factoring might not imply the RSA assumption is true.

In your question you merely call $n$ a large non-prime modulus. You have to be a little careful about the primes that make up $n$; there are lots of ways to screw up and accidentally make it easy to factor $n$.

$\endgroup$
3
  • 1
    $\begingroup$ Note: "It is conjectured to be hard to recover a random $a$ (from the set of all possible $a$s) given only $b,e,n$." It is trivial to recover $a$ if it is low-entropy. $\endgroup$
    – SEJPM
    Apr 23, 2016 at 20:01
  • $\begingroup$ If the RSA problem is not reducible to integer factorization, then that would mean one would not necessarily have to factor the modulus to break RSA, correct? Would solving the discrete logarithm problem for composite moduli count? $\endgroup$
    – Melab
    Apr 30, 2016 at 13:33
  • $\begingroup$ Right, there might be some other, faster algorithm than factoring the modulus. I'm not sure I understand what you mean about the discrete log problem for composite moduli. $\endgroup$
    – pg1989
    Apr 30, 2016 at 21:02
0
$\begingroup$

It is closed related with the RSA problem, which is defined as follows by the Wikipedia:

The RSA problem is to efficiently compute $P$ given an RSA public key $(N, e)$ and a ciphertext $C \equiv P^e \pmod N$. [...] with N being a large semiprime, $2 < e < N$, and $e$ be coprime to $\phi(N)$

The only two differences are:

  1. You don't require $N$ to be a semiprime, instead, you just require $N$ to be non-prime, which is more general.

  2. You require $e$ to be a prime, and the RSA problem only suppose that $e$ is coprime with $\phi(N)$, a weaker hypothesis.

Furthermore, on practical implementations of the RSA, the $e$ is chosen as a small number.

So, let's call the RSA problem restricted to small values of $e$ as restricted RSA problem.

All that said, if you assume the restricted RSA problem being a hard problem, then yours is also hard. This is why some algorithm to solve your problem could be simply extended to solve the RSA problem.

Assume $A$ is a algorithm that solves your problem, so in order to find $P$ such that $C \equiv P^e (mod N)$ given $N, e$, and $C$, you could factorize $e$ (since it is assumed that $e$ is small, it is feasible) getting $e = e_1 \cdot e_2 \cdots e_k$, and so, you could rewrite the problem as

$$C \equiv ((P^{e_1})^{e_2})\ldots^{e_k} \pmod N$$

thus, calling $P_i = ((P^{e_1})^{e_2})\ldots^{e_i}$, you could use the algorithm $A$ to solve $C \equiv P_{k-1}^{e_k} \pmod N$, finding $P_{k-1}$.

Then, use $A$ to solve $C \equiv P_{k-2}^{e_{k-1}} \mod N$, finding $P_{k-2}$ and so on, until you reach the problem $P_1 \equiv P^{e_1} \pmod N$, on which you could also use $A$ to finally get $P$.

Particular cases

As pointed out in the Raoul722's answer, despite the general problem is hard, there are some particular choices of values for which it is easy to solve. For instance, if you give me a instance of your problem with $N$ being a number easy to factorize, like a product of several small primes, then, I could just calculate $\phi(n)$ and find $e^{-1} \pmod {\phi(n)}$ and recover the ciphertext.

$\endgroup$
0
$\begingroup$

I suppose your question is related to RSA cryptosystem.

To put it in a nutshell: yes we can possibly calculate $a$, but we can make this harder by fixing some properties on $n$ and $e$.

That's what is done in RSA cryptosystem which is well-known: you can find a lot of documentation about it on the internet.

But to go into further details, to calculate $a$ we need to compute $b^{e^{-1}}$ where $e$ is the modular multiplicative inverse of $e$ modulo $\phi(n)$ (to quote the case of RSA where $e$ admit an inverse modulo $\phi(n)$) where $\phi$ is the Euler's totient function.

But to compute this inverse there exists a famous and effective algorithm which is named extended Euclidean algorithm. This algorithm takes as input $e$ and $\phi(n)$ and returns $e^{-1}$.

In your question, you just define $n$ as a large non-prime number, but despite its length $\phi(n)$ can be fastly computed.

RSA algorithm defines $n$ as a semiprime because in that case, the computation of $\phi(n)$ is as difficult as the factorization $n$.

$\endgroup$
5
  • 2
    $\begingroup$ Integer factorization is in $NP \cap coNP$, but is not NP-complete. $\endgroup$
    – pg1989
    Jan 30, 2016 at 21:37
  • $\begingroup$ @pg1989: Actually, it is not known whether integer factorization is NP-complete (actually, NP-hard). $\endgroup$
    – poncho
    Mar 31, 2016 at 3:15
  • $\begingroup$ @poncho sigh yes, technically that's true, but if factoring is NP-complete NP=coNP and the whole bloody polynomial hierarchy collapses, which means it's pretty unlikely that factoring is NP-complete. $\endgroup$
    – pg1989
    Mar 31, 2016 at 14:55
  • $\begingroup$ @pg1989: actually, if factoring is NP-hard, then we don't necessarily have a complete hierarchy collapse; it would imply that $NP=coNP$ and that every problem in $NP$ can be solved in subexponential time, but it won't prove (for example) that $P = NP$ $\endgroup$
    – poncho
    Mar 31, 2016 at 15:02
  • $\begingroup$ To the uninitiated, $e^-1$ is $d$ such that $(e \times d) \mod \phi(n)=1$. $\endgroup$
    – Melab
    Apr 30, 2016 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.