3
$\begingroup$

We know that if $n$ and $\phi$ is known, then it is possible to find $p$ and $q$ (initial prime numbers). I have following the questions:

  1. Assume the public key $e$ is not known, how difficult would it be to guess the public key using $n$, $\phi$, $p$ and $q$?
  2. Assuming we have $c_1$, $c_1 = m^e \bmod n$ is it possible to find out $m$ without knowing $e$ and $d$ ?
  3. From my point of view $ed = K*\phi(n) + 1$ it is difficult to guess $e$ and $d$ product. Will it fall into the factorization problem ? Is this the only equation with $n$ and $\phi$ that involves $e$ and $d$ ?
  4. Can we use some algorithm for guessing $e$ and $d$ ?

I know $e$ needs to be published publicly but if $e$ is lost how can it be identified?

$\endgroup$
5
  • $\begingroup$ Is this about textbook RSA or a practical variation? $\endgroup$
    – Erwin
    Nov 3, 2015 at 8:41
  • $\begingroup$ Sarien, Trying to evaluate RSA in detail and thinking about different scenarios for practical implementation. Searching a public key from the pool of public keys is what leading me to this thought. Any Suggestions ? $\endgroup$ Nov 3, 2015 at 9:16
  • $\begingroup$ Public exponents are in most cases either 3 or 65537. $\endgroup$
    – user27950
    Nov 3, 2015 at 10:21
  • $\begingroup$ Is there any definite solution ? Event if we apply brute force to find M finding M using n, phi and C1 is possible ? $\endgroup$ Nov 3, 2015 at 11:11
  • $\begingroup$ As I said, try first e=3 and e=65537. You will get in most cases the correct exponent. If that doesn't work, you can brute-force all small prime values e which are coprime to p-1 and q-1. $\endgroup$
    – user27950
    Nov 3, 2015 at 17:58

2 Answers 2

0
$\begingroup$

Assume the public key $e$ is not known, how difficult would it be to guess the public key using $n$, $\phi$, $p$ and $q$?

$e$ can be chosen completely arbitrary and independently of the modulus and related variables ($\phi,p,q$). You can't learn anything about $e$ (assuming $d$ isn't given) only with the modulus given.

Assuming we have $c_1$, $c_1 = m^e \bmod n$ is it possible to find out $m$ without knowing $e$ and $d$ ?

To recover $m$ you need to know $d$ (by the RSA assumption), so there's no way to recover $m$ without $e$ or $d$.

From my point of view $ed = K*\phi(n) + 1$ it is difficult to guess $e$ and $d$ product. Will it fall into the factorization problem ?

You can arbitrarily choose either $e$ or $d$. The other one is a direct result of the above equation. You can't learn the $K$ either (how would you?) so even the ability to factor won't help you. Even if you'd know $K$ factoring the product would still be quite infeasible as this would be of the same size as the modulus, for which factoring is considered infeasible.

Is this the only equation with $n$ and $\phi$ that involves $e$ and $d$ ?

Yes, this is the only RSA related equation involving, or rather this is the only equation: $ed\equiv1\pmod\phi$.

Can we use some algorithm for guessing $e$ and $d$ ?

If you're lucky, you can indeed. $e$ usually takes the values $3,17,65537$ and if those don't yield the correct messages, you can still try each possible (small) $e$ value until you hit a good one. If $e$ is larger than $\approx 2^{40}$ you'll have a hard time finding this value.

$\endgroup$
3
  • 1
    $\begingroup$ One must not try every value e, because e must be coprime to $\phi$. $\endgroup$
    – user27950
    Nov 4, 2015 at 10:17
  • $\begingroup$ @Cryptostasis, well, if $e$ isn't coprime then verification will fail in an early state and then you wouldn't save too much. And BTW, I think you meant "one doesn't have to try every value e,..." because in english "must not" means something like "never ever do this!". $\endgroup$
    – SEJPM
    Nov 4, 2015 at 17:42
  • $\begingroup$ Thank you for the language hint. That is not meant ironically. I am not a native speaker(as you surely noticed) and I really appreciate any hint to improve my language skills. $\endgroup$
    – user27950
    Nov 4, 2015 at 17:53
0
$\begingroup$

For the problem of determining the base ($m$), the problem is that you don't have enough information. For any valid value of $e$, there is a matching value $m$ that encrypts to the same $c$; specifically, $m = c^d \mod n$. Because there are many, many possible answers, there's no way to determine this, unless the value of $e$ is very small or predictable, as noted in other answers. You would still need a way to know whether your guess of $e$ is correct, such as an expected form of $m$.

Also consider the related problem of where you know $m$ but want to find $e$ and/or $d$. This degenerates to the discrete logarithm problem over primes $p$ and $q$. The ciphertext $c$ can be split into $p$ and $q$ "halves" as $c_p = c \mod p$ and $c_q = c \mod q$. $m$ can be split into $m_p$ and $m_q$ the same way. ($e$ and $d$ are conceptually split modulo $p-1$ and $q-1$.) Now, you'd need to calculate $e_p$ for $c_p = {m_p}^{e_p} \mod p$, which is the discrete logarithm problem. Depending upon the choice and size of $p$ and $q$, this may be infeasible.

I'm not a mathematician or cryptographer, just a programmer, so treat my answer with some skepticism.

$\endgroup$

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.