# Common FactorHere is the challenge code and Description```How much do you know about the RSA algorithm?```
```pythonfrom Crypto.Util.number import *
from functools import reduce
def encrypt(msg, n):	enc = pow(bytes_to_long(msg), e, n)	return enc
e = 65537
primes = [getPrime(2048) for i in range(5)]n = reduce(lambda a, x: a * x, primes, 1)print(n)
x1 = primes[1] ** 2x2 = primes[2] ** 2x3 = primes[1] * primes[2]y1 = x1 * primes[2] + x2 * primes[1]y2 = x2 * (primes[3] + 1) - 1y3 = x3 * (primes[3] + 1) - 1print(x2 + x3 + y1)print(y2 + y3)
with open('flag', 'rb') as f:	flag = f.read()	print(encrypt(flag, n))```
# Solution
We have equations like this```pythonn  = primes[0] * primes[1] * primes[2] * primes[3] * primes[4]v1 = x2 + x3 + y1v2 = y2 + y3
v1 = primes[2]**2 + primes[1]*primes[2] + (primes[1]**2)*primes[2] + primes[1]*(primes[2]**2)v2 = (primes[2]**2)*primes[3] + primes[2]**2 + primes[1]*primes[2]*primes[3] + primes[1]*primes[2] - 2```
We know that `n` and `v1` both are divisible by `primes[2]` so we can calculate Greatest Common Factor of `n` and `v1` `gcd(v1,n)` to find `primes[2]````python# p2p2 = gcd(n, v1)if n % p2 == 0: # confirm for correct p2 value	print(p2)```
Then by having `primes[2]` and `v1` we can calculate `p1` with 2 degree equations solves```# p1a1 = p2b1 = p2**2 + p2c1 = p2**2 - value1delta1 = b1**2 - 4*a1*c1
p1 = (-b1 + nth_root(delta1, 2)) // (2*a1)if n % p1 == 0: # confirm for correct p2 value	print(p1)```
By having `primes[1]` and `primes[2]` we also can find `primes[3]` through v2 linear equations```python# p3p3 = (value2 - (p2**2 + p1*p2) + 2) // (p1*p2 + p2**2)if n % p3 == 0: # confirm for correct p3 value	print(p3)```
OK, we have 3 factors of our 5 factor n, But to decrypt the flag that's enough and no need for other factors [link](https://crypto.stackexchange.com/questions/44110/rsa-with-3-primes)```pythonphi1 = (p1-1)*(p2-1)d1 = inverse(e, phi1)flag = pow(enc % p1, d1, p1)print(long_to_bytes(flag))```
and here is the flag```flag: b'TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}'```
[solution code](https://github.com/KooroshRZ/CTF-Writeups/blob/main/TMU2021/Crypto/CommonFactor/solve.py)
> KouroshRZ for **AbyssalCruelty**