Rating:
## Triplet
### Challenge
```python
#!/usr/bin/env python3
from Crypto.Util.number import *
from random import randint
import sys
from 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:
```python
def 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](https://factordb.com/) for this.
Once we do that, we submit everything to the server and get our flag.
Example input:
```
1016528131013635090619361217720494946552931485213,1429584882448210886669728733194710184148915763157
6211546314237476302579971345731015750127038990912821,8860059189914843449838352373651833954155350825107793
9404281119755539122106076617436757845692337032242009481,24063920759808714809760965046838381019485932840992763073
43589288709210633359625764026901174390804401096987086682930362519465081895858044399533,5191731325979249818708517
```
##### Flag
`CCTF{7HrE3_b4Bie5_c4rRi3d_dUr1nG_0Ne_pr39naNcY_Ar3_triplets}`
