-1
$\begingroup$

How can one crack a message c_2 encoded by e_2 if one knows e_1, e_2, d_1, and both codes share common modulo n, without using factorization? Considering textbook RSA

Improve this question
$\endgroup$
10
  • $\begingroup$ Bit of an "academic" question. Knowing $e_1, d_1$ and $n$ immediately factors $n$ anyway, after which computinh $d_2$ is easy. If you can factor why is it not allowed to do it? $\endgroup$
    – Henno Brandsma
    Oct 30 '17 at 23:19
  • $\begingroup$ Because that is the assignement of it. To decrypt a message without factoring, but i have no idea as to how to proceed so i'm looking for explanation as to how to do it so i can apply it to the problem. Can you explain how do you get factors from knowing e_1 and d_1? $\endgroup$
    – Zerg Overmind
    Oct 30 '17 at 23:25
  • $\begingroup$ I explain the algorithm here $\endgroup$
    – Henno Brandsma
    Oct 30 '17 at 23:32
  • $\begingroup$ See also here (with code to do it) $\endgroup$
    – Henno Brandsma
    Oct 30 '17 at 23:40
  • $\begingroup$ Just the first message you sent me made me realise how to solve it. Thank you for the hint (and later on the fuller way to factor it). I didn't really have to factor it. I can just get the phi and from that calculate inverse without factoring. Could you write an answer with those links so i can mark it s an answer? $\endgroup$
    – Zerg Overmind
    Oct 31 '17 at 7:52
1
$\begingroup$

In this answer on math stackoverflow I explain a (probabilistic) algorithm to factor $n$ when $e$ and $d$ are both known. This answer does the same (almost) and provides Python code to do it as well, while this answer gives some references (and even a more complicated deterministic algorithm). Knowing $p$ and $q$ then allows you to find $d_2$, etc.

Without this, of course you can compute $M = e_1 d_1-1$ which must be a multiple of $\phi(n)$. Inverting $e_2$ modulo $M$ will also work as a decryption exponent, most of the time. (This inverse might not exist if $M = k\phi(n)$ and $(e_2, k) \neq 1$, say.) If you'd know $\phi(n)$ exactly, you could find $p,q$ from:

$\phi(n) = (p-1)(q-1) = pq - p - q +1$ so $p+q = n-\phi(n) + 1$ and so we can solve the quadratic $n=pq = p(n-\phi(n)+1-p)$ where $p$ is unknown and $n$ and $\phi(n)$ are known.

So to factor $n$ for an RSA system $(n,e)$ we can use $e$ and $d$ or $\phi(n)$.

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.