1
$\begingroup$

I am currently working on a broadcast attack on RSA. This is what I have:

  1. 17 ciphertexts $C_i$ and corresponding moduli $N_i$ for a single common message $m$.
  2. Public key $e = 17$

The first part (of the exercise) asks me to attack the first 17 ciphers. I programmed it with sage using the CRT. The CRT returns a result $x$ where I applied the 17th root on it, revealing the encrypted message. Everything good so far.

The second part asks me to again recover the message, but the ciphertexts and one modulus got changed. I tried to do the same as in the first part but I don't get a solution.

I already read different articles and books to figure out what the problem is, but I can't find anything :(

Could someone help me with that one?

This is the first one: Part 1 This is the second one: Part 2

$\endgroup$
3
$\begingroup$

Your solution works for Part 1 because (there) for each $i \neq j$ holds $gcd(N_i,N_j) = 1$. In Part 2 $gcd(N_7, N_{13})$ is not equal to $1$. $N_{13}$ is a product of two primes ($q = gcd(N_7, N_{13})$ and $p = N_{13}/q$). Using that information you can recover the secret key $d$ (simply invert $e$ modulo $(p-1)(q-1)$ as during the key generation of RSA) and from that you can recover $m = C_{13}^d (mod\ N_{13})$. We did not use the broadcast attack in this case (I am not sure if you can make it work).

$\endgroup$
  • $\begingroup$ Hi Markus and welcome, nice start here at crypto.SE; we can always use some more mathematicians posting over here :) $\endgroup$ – Maarten - reinstate Monica May 2 '17 at 0:11

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.