We are given the following Python code for encrypting the flag: from random import randint a = 288260533169915 p = 1007621497415251 FLAG = b'crypto{????????????????????}' def encrypt_flag(flag): ciphertext = [] plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) print(plaintext) for b in plaintext: e = randint(1, p) n = pow(a, e, p) if b == '1': ciphertext.append(n) else: n = -n % p ciphertext.append(n) return ciphertext The way that the encryption works is that if it encounters a bit with value “1” in the binary representation of the plaintext (or the flag itself), then it appends $a^e \mod p$ to the ciphertext array, otherwise it appends $-a^e \mod p$.

This problem is the problem I did not manage to solve in NUS Greyhats GreyCTF2022. Although I am pretty close to the solution, there is one trick that I missed that is crucial to this particular type of challenge. N = p * q c1 = (2 * p + 3 * q) ** e1 mod N c2 = (5 * p + 7 * q) ** e2 mod N We are given the above system of equations, and the goal is to solve for $p$ and $q$.

We are given the prime $p$ and the integers to find the quadratic residue in $p$. The exact values of the prime is given in this link Using Legendre Symbol and Euler’s criterion, a number $a$ can have three cases: $$ (\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \equiv 1 \text{ if } a \text{ is a quadratic residue and } a \not\equiv 0 \mod p $$ $$ (\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \equiv -1 \text{ if } a \text{ is a quadratic non-residue } \mod p $$

Implementation of the algorithm is in Sagemath: # Finding quadratic residue of a mod p from sage.rings.finite_rings.integer_mod import square_root_mod_prime a = <some a> p = <some p> print(square_root_mod_prime(Mod(a, p), p))