We are given N, e, d of the sender and N, e of his friends. The flag is encrypted using the friend’s public keys e1, e2, ..., e5 under the same modulo N. As seen in this link, we can factorise N given e, d using the given algorithm. From that, decrypting the plaintext should be trivial. Sage Implementation (slight modification and this can work on Python too) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 from Crypto....
We are given multiple messages, but from the hint, some of the messages are repeated. Hence, it is likely some (if not all) of the messages will be the same. That is, there is a message $m$, moduli $n_i$, and ciphertext $c_i$ such that: $$ \forall i, c_i \equiv m ^ 3 \mod n_i $$ Hence, we can employ Chinese Remainder Theorem in this case. This is also a simplified form of Hastad’s broadcast attack....
RSA, except we are given a huge public exponent e that has the same number of bits as the modulus N. We can attack this using Wiener’s Attack. The condition for Wiener’s attack is $$ d \le \frac{1}{3} \sqrt[^4]{N}. $$ We can refer to the way that the attack works in the Cryptohack Book. Sage Implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 from Crypto....
Same problem as the previous similar name challenge. But there is a twist this time. There is a check of (3*d)**4 > N, which effectively renders Weiner’s attack useless. We can use Boneh-Durfee Attack. Awesome script at this link. The Github repo contains some useful scripts. Boneh-Durfee Attack limit: $$ d < N ^ {0.292} $$ From the retrieved d, we can easily recover the plaintext. Seems like there is another solution by aloof, which I am too lazy to type so here’s the screenshot of the math involved....