CTFZone - MPRSA Task write up

In this Task we were given a file that contain 3 files
The first one is Cipher
The second one is the Encrypted file
The last one is Modulus N and public exponent e
okay now take a look at the encrypted file

class MPRSA(object):
    def __init__(self):
        self.public_key = None
        self.secret_key = None

    def key_gen(self, bits, prime_numbers=4):
        delta = randint(5, 15)
        bit_prime = int(bits // prime_numbers)

        P = [next_prime(number.getPrime(bit_prime) + 1)]
        for i in range(1, prime_numbers):
            P.append(next_prime(P[i - 1] * delta))
        n = self.__compute_module(P)
        phi = self.__compute_phi(P)

        for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
            g, e, __ = gcdext(d_next, phi)
            if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):
                d = d_next
                break

        self.public_key = (e, n)
        self.secret_key = (d, n)

    def import_keys(self, public_key, secret_key):
        self.public_key = public_key
        self.secret_key = secret_key

    def export_keys(self):
        return self.public_key, self.secret_key

    @staticmethod
    def __compute_module(primes):
        n = 1
        for prime in primes:
            n *= prime
        return n

    @staticmethod
    def __compute_phi(primes):
        phi = 1
        for prime in primes:
            phi *= (prime - 1)
        return phi

    @staticmethod
    def __encode_message(data):
        return int(hexlify(data), 16)

    @staticmethod
    def __decode_message(data):
        return unhexlify(format(data, "x"))

Look at func key_gen, we can know that:
1. Primes have 4 prime

2. Bit_primes is random

3 They calculate 4 prime with the fomular:
P[i] = next_prime ( P[i-1]*delta )
and delta is a random number from range ( 5, 16 )

4, Modulus N is calculated by func  __compute_module(P)
n = 1
n*= p1*p2*p3*p4

5. Phi is calculated by func __compute_phi(P)
phi = 1
phi* = (p1 - 1) * (p2-1) * (p3-1) * (p4-1)

6. We got Publickey ( e , n )
now we need to find d to get Secretkey ( d , n )
and d is calculated :
for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
            g, e, __ = gcdext(d_next, phi)
            if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):
                d = d_next
                break
Okay, so we need to know P[0] or in this case, it is the first prime in P, we can call that p1

So now we need to find P = [p1,p2,p3,p4] , Phi
We know N = p1*p2*p3*p4
and luckily, N can be factorized with factordb.com

The two big number factorized should be the multiple of p1*p4 and p2*p3 so that their length can almost the same
Now we go back to the generate prime function :
for i in range(1, prime_numbers):
            P.append(next_prime(P[i - 1] * delta))
Assume we got p2 and p3

p3 = nextprime ( p2*delta )
So :  p3 > p2*delta
<=> p3*p3 > p2*p3*delta
Assume :  X = p2*p3
-> pow(p3,2) > X*delta
<=> p3 > sqrt(X*delta)
So now, we can calculate the floor of p3, we can use next_prime, and if one of the two big number % x == 0 -> it's p3

def findP3(num):
  for delta in range(5,16):
    x = num*delta 
    x = isqrt(x)
    k = 0
    while ( k <= 10 ):
        k+= 1
        x = next_prime(x)
        if num % x == 0 :
            print delta
   return x 

i use this script to find P3, now we can get either Delta and P3
i named num1 and num2 for the two big number
now i will try one by one to see which one is the multiple of p2*p3

we got P3 and Delta
now we can easy calculate P2 and P4
P4 = next_prime(P3*14)
and P2 = num2 / P3
num2 = p2*p3
-> num1 = p1*p4
-> p1 =  num1/p4
we got p1 , now we get d with this script they already gave us

for d_next in count(int(pow(P[0] // 2, 0.5)), -1):
            g, e, __ = gcdext(d_next, phi)
            if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):
                d = d_next
                break

Change P[0] to P[1]
 and phi = (p1 - 1) * (p2-1) * (p3-1) * (p4-1)
we got both d and phi
after that we can decode the messege : pow ( c  , d , n )
now just decrypt and we got our flag

Flag:  ctfzone{3177809746931830}

Script