We are given the following code for this task:
```
#!/usr/bin/env python

import random
from Crypto.Util.number import *
from fractions import gcd
import gmpy
from 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, 512
pkey, 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 notebook
p13, q13 = ... # from our part of private key
r = next_prime(p13)
s = next_prime(q13)
for i in range(12):
r, s = (2*s - r) // 5, (3*r - s) // 5
r1 = next_prime(r - 1000)
s1 = next_prime(s - 1000)
print "Using initial values:", r1, s1
r, s = r1, s1
participants_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 * u
e0 = ... # from our part of private key
phi = 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=87995963705775252652902721333907731539211925670258267633625334592684122942357226180852429359176006366878142442513953441034915209172535208468117104886941195190984514419906417536826283135891378770042001164393213815646704419253174664971044632616940041563748768493413579796262475648325000703887764944685010024337
p=(n-phi+1-((n-phi+1)^2-4*n).nth_root(2))//2
q=n//p
print 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 flag
f2=[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!_!_!!!}```