We are given the following code for this task:```#!/usr/bin/env python
import randomfrom Crypto.Util.number import *from fractions import gcdimport gmpyfrom flag import flag
def make_participants_key(l, nbit):    while True:        p, q = getPrime(nbit), getPrime(nbit)        N, phi = p * q, (p-1)*(q-1)        x = random.randint(1, N)        if (N % 8 == 1) and (phi % 8 == 4) and (p != q):            if pow(q ** 2 * x, (p-1)/2, p) + pow(p ** 2 * x, (q-1)/2, q) == N - phi - 1:                break    participants_key = []    r, s = [getPrime(nbit) for _ in '01']    for i in range(l):        u, v = gmpy.next_prime(r), gmpy.next_prime(s)        u -= u % 4        v -= v % 8        participants_key.append((long(u), long(v)))        r, s = u + 2 * v, v + 3 * u    e0 = phi + sum([participants_key[i][0] for i in range(len(participants_key))]) + sum([participants_key[i][1] for i in range(len(participants_key))])    return (x, N), (participants_key, e0)
def encrypt(msg, pkey):    msg, C = bin(bytes_to_long(msg))[2:], []    x, N = pkey    for b in msg:        while True:            r = random.randint(1, N)            if gcd(r, N) == 1:                br = bin(r)[2:]                c = (pow(x, int(br + b, 2), N) * r ** 2) % N                C.append(c)                break    return C
l, nbit = 14, 512pkey, skeys = make_participants_key(l, nbit)enc = encrypt(flag, pkey)```We are also given the public key```(29169469951053295574081524059511535140827283191073251776995458401426751335067978224073517175066569709975139345222677517823282108654144344668206951295920733865048193562823092960410199979804386493444569565801190392203155582443887810481911785072200479531562344730825301324306290366963374793938436402536235751046L, 87995963705775252652902721333907731539211925670258267633625334592684122942357226180852429359176006366878142442513953441034915209172535208468117104886941195190984514419906417536826283135891378770042001164393213815646704419253174664971044632616940041563748768493413579796262475648325000703887764944685010024337L)```the private key of 13-th participant```[(p_1, q_1), (p_2, q_2), (p_3, q_3), (p_4, q_4), (p_5, q_5), (p_6, q_6), (p_7, q_7), (p_8, q_8), (p_9, q_9), (p_10, q_10), (p_11, q_11), (p_12, q_12), (24577912044004448595463057779637545000863729896975449607106255001057277303457321766887564462859651873899271719758660726875817220988246251622444695051161733113960L, 30101504230956252554214968662602777204908308733370256591337015850221220287755935456120201522030432241746171795099896635419686586404004906003066839175499231676280L), (p_14, q_14), 87995963705775252652902721333907731539211925670258267633625334592684122942357226180852429359176006366878142442513953441034915209172535208468117105152559536379768449721582745181807824724938894947268104359039873535516591412297194883059558364240000402862207672404172393583217829233259557249428015013428243679784]```and the encrypted flag consisting of 567 integers which is too long to list here.
The encryption scheme is known as [Goldwasser–Micali cryptosystem](https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem) . Every bit of a message is encrypted independently, zero bits are encoded as squares modulo N=pq, ones are encoded as non-squares modulo N chosen so that Jacobi symbol is still +1. Knowing the prime decomposition of N, one decrypts every bit by calculating Legendre symbol of the encoded value modulo p (+1 means zero, -1 means one), but it is unknown how to do this without knowing p and q.
The leading zeroes of the message are not encoded, so 567 components of the encrypted flag mean 71 bytes and one leading zero bit (as expected for ASCII message).
In turn, the private key encodes p+q by generating a set of 14 pairs of integers, one for every participant, and giving one pair of integers and the sum of (N-p-q+1) and all generated primes to every participant. All participants together can restore the private key by subtracting everything that was given to them.However, only one pair of numbers is actually randomly generated, all others are calculated from there. So we can restore an approximation to the initial values by working backwards. Going backwards is ambiguous due to ```next_prime``` call, but the gaps between consecutive primes are small (Cramér's conjecture states that the gap is O((log p)^2) in the worst case), so the final result should be quite close to the true value of phi = N-p-q+1.```# this and subsequent listings are from SageMath interactive notebookp13, q13 = ... # from our part of private keyr = next_prime(p13)s = next_prime(q13)for i in range(12):    r, s = (2*s - r) // 5, (3*r - s) // 5r1 = next_prime(r - 1000)s1 = next_prime(s - 1000)print "Using initial values:", r1, s1r, s = r1, s1participants_key = []for i in range(14):    u, v = next_prime(r), next_prime(s)    u -= u % 4    v -= v % 8    participants_key.append((u, v))    r, s = u + 2 * v, v + 3 * ue0 = ... # from our part of private keyphi = e0 - sum([participants_key[i][0] for i in range(len(participants_key))]) - sum([participants_key[i][1] for i in range(len(participants_key))])```After that, we know pq=N and p+q=N-phi+1; solving the quadratic equation, we get that (N-phi+1)^2-4N should be a perfect square.```n=87995963705775252652902721333907731539211925670258267633625334592684122942357226180852429359176006366878142442513953441034915209172535208468117104886941195190984514419906417536826283135891378770042001164393213815646704419253174664971044632616940041563748768493413579796262475648325000703887764944685010024337p=(n-phi+1-((n-phi+1)^2-4*n).nth_root(2))//2q=n//pprint n == p*q```Turns out that r,s generated by the procedure above give the exact needed value of phi. If that would not be the case, we would need to check some small interval containing the found value.Finally,```Fp=Integers(p)flag=[...] # encrypted flagf2=[0 if Fp(f).is_square() else 1 for f in flag]hex(int('0'+''.join(str(i) for i in f2),2))[2:-1].decode('hex')``````CCTF{gj_yOU_50lv3d__A_tHreshold_Crypt05ys73M_B4s3D_0N_F4ct0r1n9!_!_!!!}```