Modular Arithmetic

We are given the following Python code for encrypting the flag: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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....

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. 1 2 3 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$$ $$(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \equiv 0 \text{ if } a \equiv 0 \mod p$$ But when the prime is of the form $4k + 3$, then using Euler’s criterion, if a number $a$ indeed has a quadratic residue, then:...

Implementation of the algorithm is in Sagemath: 1 2 3 4 5 6 7 # 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))