1
$\begingroup$

Suppose I intercept the same message m sent to 2 friends. I know what the message is and I know the used modulus n, as well as the ciphertexts but I don't know the respective public exponents. I.e. my system of equations is:

  • $c_1 = m^{e_1} \ mod \ n$
  • $c_2 = m^{e_2} \ mod \ n$

Is there a way to retrieve the public exponents, without using bruteforce?

A practical example:

  • $n = 221$
  • $m = 127$
  • $c_1 = 155$
  • $c_2 = 43$
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This is equivalent to asking to find the private exponent - if you assume random choice of $e$ and $m$ and proper choice of $n$. So, are there assumptions that you can make on the structure of $e$ (e.g. it being a small value)? $\endgroup$
    – SEJPM
    May 24, 2020 at 10:51

2 Answers 2

Reset to default
2
$\begingroup$

Hint: seen as a discrete logarithm problem, there's an attack of cost $O(\sqrt{\min(e_1,e_2)})$.

I see no improvement on the asymptotic cost without factoring $n$.

Update: I think it is rigorously provable that if one could solve this problem in polynomial time with sizable probability for proper choice of $n$ and random other parameters, then we could factor $n$. Proof is left as an exercise to the reader by the usual method: invoke the hypothetical algorithm solving the problem in a polynomial-time algorithm that factors $n$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Do you want to rely on this theorem? "If we know both public and private key of plain RSA, then we can probably factor $n$ [Trappe and Washigton]?" In this question, private key is also unknown, so the theorem holds even when public key is known. But I think you are just reusing this: _If we can solve discrete logarithm problem, we can solve factorization problem_(Reduction of factorization to DLP). If this is the case, the first problem still exist: "Is this question equal to DLP?" I suppose this is the part which needs proof, not the relation between DLP and factorization. $\endgroup$
    – ssss1
    May 25, 2020 at 14:45
  • $\begingroup$ Do you mean the theorem I wrote in the first line? I didn't used the word "reduction" for that. It was for another assumption about your answer. But, if you are relying on the theorem that I wrote on the first line, I think it is not possible. Because even if we assume we can compute public keys here, the theorem still holds. It just needs not to be able to find private key (actually, "at least" one of the private/public keys). $\endgroup$
    – ssss1
    May 25, 2020 at 15:03
  • $\begingroup$ Yes I used "Reduction" but not for "Trappe and Washigton". In that comment I asked: you are using 1. "Trappe and Washigton"... or 2. Reduction? I suppose this kind of reduction does not work here. Since you are implicitly just reducing DLP to factorization problem. As I said, if you want to use this (I mean your updated main answer) as a reduction, you need to show that the main question is equal to DLP. Then, when you show that, we know DLP is hard! so, there is no need to reduce it to factorization. Good Luck (both for your homework and proof of this question) $\endgroup$
    – ssss1
    May 25, 2020 at 15:39
  • $\begingroup$ @ssss1: [edited for clarity]. Yes, the theorem I use is a rephrasing of your "Trappe and Washigton" theorem in the first line of your first comment. Again, I use it to prove that solving the question's problem allows to factor $n$, just not the way that I think that you are thinking. If I was not suspecting homework/CTF, I'd explain exactly how I hope that my proof works, its kinda fun, I like this problem. Will do, sometime. Added a marker not to forget. $\endgroup$
    – fgrieu ♦
    May 25, 2020 at 15:40
  • $\begingroup$ AHA! thanks for your clarification. I think it was useful to avoid ambiguity for other readers also. $\endgroup$
    – ssss1
    May 25, 2020 at 15:44
0
$\begingroup$

  • As fgrieu said, this seems as DLP. discrete logarithm problem for composite modulo is not necessarily harder that then discrete logarithm of prime modulo.

  • The discrete logarithm problem cant be solved efficiently. It means that there is no known polynomial time algorithm to solve it.

  • Discrete Logarithm Problem: we have $\alpha= \beta^ x mod p$. Given $\alpha$, $\beta$ and $p$, find $x$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Known plaintext attack (without extra weaknesses like small exponents, ...) is not possible on RSA. even when the public key is known! In your problem public key is also unknown. Security of public key methods against eavesdropping implies this security also. $\endgroup$
    – m123
    May 25, 2020 at 14:15

Your Answer

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

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