Long challenge name, but short story. We are given an article at this link, outlining the difficulties in generating RSA keys such that there are no two public keys using the same prime. Because if that’s the case, one can very efficiently recover the factorisation by doing Euclid’s Algorithm, which runs in polynomial time (and thus much faster compared to factorising), to obtain one of the two primes used in the modulus.

I hate recursion depths. Sage on Windows sucks at configuring anything related to this. The challenge gives a peculiar way of generating primes def get_complex_prime(): D = 427 while True: s = random.randint(2 ** 1020, 2 ** 1021 - 1) tmp = D * s ** 2 + 1 if tmp % 4 == 0 and isPrime((tmp // 4)): return tmp // 4 And given the name of the challenge, we are pretty sure that this leads to a vulnerability.

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) from Crypto.Util.number import long_to_bytes from sage.

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: from Crypto.Util.number import long_to_bytes def wiener(e, n): # Convert e/n into a continued fraction cf = continued_fraction(e/n) convergents = cf.