Adrien's Signs

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....

December 5, 2022 · 2 min · qvinhprolol

Modular Binomials

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 pp and qq....

December 5, 2022 · 3 min · qvinhprolol

Legendre Symbol

We are given the prime pp and the integers to find the quadratic residue in pp. The exact values of the prime is given in this link Using Legendre Symbol and Euler’s criterion, a number aa can have three cases: (ap)ap121 if a is a quadratic residue and a≢0mod  p (\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 (ap)ap121 if a is a quadratic non-residue mod  p (\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \equiv -1 \text{ if } a \text{ is a quadratic non-residue } \mod p (ap)ap120 if a0mod  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+34k + 3, then using Euler’s criterion, if a number aa indeed has a quadratic residue, then:...

December 4, 2022 · 2 min · qvinhprolol

Tonelli-Shanks

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))

December 4, 2022 · 1 min · qvinhprolol