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$
  • $\begingroup$ Is this about textbook RSA or a practical variation? $\endgroup$ – Erwin Nov 3 '15 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$ – Rohit Tiwari Nov 3 '15 at 9:16
  • $\begingroup$ Public exponents are in most cases either 3 or 65537. $\endgroup$ – user27950 Nov 3 '15 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$ – Rohit Tiwari Nov 3 '15 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 '15 at 17:58
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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ One must not try every value e, because e must be coprime to $\phi$. $\endgroup$ – user27950 Nov 4 '15 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 '15 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 '15 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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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