## Triplet### Challenge
```python#!/usr/bin/env python3
from Crypto.Util.number import *from random import randintimport sysfrom flag import FLAG
def die(*args):  pr(*args)  quit()
def pr(*args):  s = " ".join(map(str, args))  sys.stdout.write(s + "\n")  sys.stdout.flush()
def sc():  return sys.stdin.readline().strip()
def main():  border = "+"  pr(border*72)  pr(border, " hi talented cryptographers, the mission is to find the three RSA   ", border)  pr(border, " modulus with the same public and private exponent! Try your chance!", border)  pr(border*72)
  nbit = 160
  while True:    pr("| Options: \n|\t[S]end the three nbit prime pairs \n|\t[Q]uit")    ans = sc().lower()    order = ['first', 'second', 'third']    if ans == 's':      P, N = [], []      for i in range(3):        pr("| Send the " + order[i] + " RSA primes such that nbit >= " + str(nbit) + ": p_" + str(i+1) + ", q_" + str(i+1) + " ")        params = sc()        try:          p, q = params.split(',')          p, q = int(p), int(q)        except:          die("| your primes are not valid!!")        if isPrime(p) and isPrime(q) and len(bin(p)[2:]) >= nbit and len(bin(q)[2:]) >= nbit:          P.append((p, q))          n = p * q          N.append(n)        else:          die("| your input is not desired prime, Bye!")      if len(set(N)) == 3:        pr("| Send the public and private exponent: e, d ")        params = sc()        try:          e, d = params.split(',')          e, d = int(e), int(d)        except:          die("| your parameters are not valid!! Bye!!!")        phi_1 = (P[0][0] - 1)*(P[0][1] - 1)        phi_2 = (P[1][0] - 1)*(P[1][1] - 1)        phi_3 = (P[2][0] - 1)*(P[2][1] - 1)        if 1 < e < min([phi_1, phi_2, phi_3]) and 1 < d < min([phi_1, phi_2, phi_3]):          b = (e * d % phi_1 == 1) and (e * d % phi_2 == 1) and (e * d % phi_3 == 1)          if b:            die("| You got the flag:", FLAG)          else:            die("| invalid exponents, bye!!!")        else:          die("| the exponents are too small or too large!")      else:        die("| kidding me?!!, bye!")    elif ans == 'q':      die("Quitting ...")    else:      die("Bye ...")
if __name__ == '__main__':  main()```
We need to send 3 pairs of primes followed by a keypair `e,d` so that `e,d` is a valid keypair for each modulus generated by each pair.
Most easy solutions are patched out, as `e` and `d` both have to be less than the lowest phi and greater than 1.
### Solution
Our main idea for this problem is to generate `phi_1`, `phi_2` and `phi_3` in a way so that `phi_2` is a multiple of `phi_1`, and `phi_3` is a multiple of `phi_2`. In this way, any valid keypair for `phi_3` (that also satisfies the length requirement) will also be a valid keypair for `phi_1` and `phi_2` and can be used to get the flag.
We can generate primes as follows:
```pythondef phi(p,q):    return (p-1) * (q-1)
from random import randrange
def genprime(baseprime):    while True:        k = randrange(2, 1000)        p = baseprime * k + 1        if is_prime(p):            return p
p = random_prime(2^160)q = random_prime(2^160)r = genprime(p)s = genprime(q)t = genprime(r)u = genprime(s)phi_1 = phi(p,q)phi_2 = phi(r,s)phi_3 = phi(t,u)```
Now all we need to do is generate a valid keypair for `phi_3`. To do this, recall that the values $e$ and $d$ satisfy the following equation:
$$e * d \equiv 1 \mod \phi(n)$$
therefore
$$e * d = 1 + k * \phi(n)$$
If we find factors of $1 + phi(n3)$, we should be able to find two numbers that are small enough to satisfy the length requirements, as the value $k$ in the equation
$$\phi(n3) = k * \phi(n1)$$ 
should be small. We can just use something like [factordb](http://factordb.com/) for this.
Once we do that, we submit everything to the server and get our flag.
Example input:```1016528131013635090619361217720494946552931485213,14295848824482108866697287331947101841489157631576211546314237476302579971345731015750127038990912821,88600591899148434498383523736518339541553508251077939404281119755539122106076617436757845692337032242009481,2406392075980871480976096504683838101948593284099276307343589288709210633359625764026901174390804401096987086682930362519465081895858044399533,5191731325979249818708517```
##### Flag
`CCTF{7HrE3_b4Bie5_c4rRi3d_dUr1nG_0Ne_pr39naNcY_Ar3_triplets}`