The flag is padded with \x00 at the end to make the length of the flag overall becomes 100 bytes long. For each null byte appended, the value of the flag is multiplied by 256. Hence, we can retrieve the flag using Coppersmith, however there is a twist. Even if the polynomial theoretically should output some result, none is returned by the small_roots function. The solution that works seems to reduce the x that is calculated to be the smallest x possible such that the result makes sense.

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.