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
$\begingroup$
$\endgroup$
-
$\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
$\begingroup$
$\endgroup$
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)$.
