Tags: rsa crypto

Rating:

# Common Factor
Here is the challenge code and Description

How much do you know about the RSA algorithm?


python
from 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] ** 2
x2 = primes[2] ** 2
x3 = primes[1] * primes[2]
y1 = x1 * primes[2] + x2 * primes[1]
y2 = x2 * (primes[3] + 1) - 1
y3 = x3 * (primes[3] + 1) - 1
print(x2 + x3 + y1)
print(y2 + y3)

with open('flag', 'rb') as f:
print(encrypt(flag, n))


# Solution

We have equations like this
python
n = primes[0] * primes[1] * primes[2] * primes[3] * primes[4]
v1 = x2 + x3 + y1
v2 = 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
# p2
p2 = 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

# p1
a1 = p2
b1 = p2**2 + p2
c1 = p2**2 - value1
delta1 = 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
# p3
p3 = (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)
python
phi1 = (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}'


> KouroshRZ for **AbyssalCruelty**

Original writeup (https://kooroshrz.github.io/CTF-Writeups/TMU2021/Crypto/CommonFactor/).