Inctf Quals 2018-MultiPrime RSA WriteUp

This year InCTF Quals really went well and I feel extremely privileged to be a part of it and conduct it. I hope everyone learned a lot more stuff after this CTF.

This blog post covers the intended solution of the challenge that I created: MultiPrime RSA. It was a medium level challenge with 3 solves. 

In this challenge you were given 2 files: chal.py and parameters.txt

When we go through the parameters.txt, we find the following values of n, e and c

n = 63503276937852850446665985957390379307440024971021230431993893491881624345662352363811917592750766531203356043483026044031384884152397966752357920486434617823027122279415036554847130392423900715402785773280279146047931988844559054831429226564586447952491921350715788091186848490634584031960739647318023686632925058823647108880767478971118608237886300608306051261004692404756371356302701018432847524301182730267480301933745056302779577973416730232149313436165949340434895975694570102514920769870034226468745369298052361213865705054347251550807
e = 65537
c = 464757bacf2e67e0e253adbd024ee12c9ab5a7250f2caadc99ba4231565635345ab549790aaf472a2efad32a81efbee50127c476c3dab7313168912a577e61012a56b1de50a72f30a23642749ad2dda71b6d11b488d79511d0298d91640fdc61fbb1332156596e75fe56776361af653c5b14a90d555e0eb6048cf28dcc89ec752a9f46bb7d8c2a5cc16d2ac0d0dafae06ef95419fca0384ed9168ecd8157a0478999cfc347bcf2487bd3171fd9723acc336a6bf5c1a27e4863a0a8f784ee85d79fe9c934190f95ddb8604a0453978df7bee1071f12aea363fadfa9e0bde9792328

When we just take a look at it we don’t find anything suspicious but try to observe the bits size of n. It is 1800. Isn’t it odd compared to the general 1024 and 2048  bits of n? Now it is time to check  chal.py


from Crypto.Util.number import *
from flag import *

def nextPrime(prim):
    if isPrime(prim):
        return prim
    else:
        return nextPrime(prim+1)

p = getPrime(256)
q = nextPrime(13*p)
r = nextPrime(p*q)
s = nextPrime(q*r)
n = p*q*r*s

phin = (p-1)*(q-1)*(r-1)*(s-1)
e = 65537
assert GCD(e,phin) == 1
m = bytes_to_long(flag)
c = pow(m,e,n)
print long_to_bytes(c).encode("hex")
print n

Now we understand why the bits size of n is odd. It’s because it’s not regular RSA encryption where 2 primes are used.
Let us take a note of the important observations that we find while going through the code: 

  • Here we are actually using multi primes. (as the name suggests 😉 )
  • Also, one can find that all the primes are related.

So, how do we use these 2 facts to find a solution to this challenge?

Let us use the fact that the primes are related and try to find a relation which helps us to find the primes.

Given that: p = getPrime(256), q = nextPrime(13p), r = nextPrime(pq), s = nextPrime(qr)
On remodelling these equations
q = 13p + i
r = pq + j = p(13p + i) + j
  s = qr + k = [13p + i][p(13p + i) + j] + k (where i,j and k are unknown variables)

Also, we know that n = p*q*r*s
On substituting the above values we get
n = p*q*rs
n = p*(13*p + i)*[p*(13*p + i) + j]*{[13*p + i]*[p*(13*p + i) + j] + k}
From the above equation, we can approximate n as 134p7
i.e n ~ 134p7
we can also write it as
p ~ (n/134)1/7 (note that we needn't expand the equation to find p)

Now that we got the approximate value of p, we will try to find the exact value of p, through which we will be able to get the values of other primes. We can do so by using Binary search


def primesgen(p):
    q = nextPrime(13*p)
    r = nextPrime(p*q)
    s = nextPrime(q*r)
    return p*q*r*s

def find_p(papprox,n):
    while True:
      n_approx = primesgen(papprox)
      if n  n_approx:
          papprox = papprox + 1
          n_approx = primesgen(papprox)
      else:
    	    return papprox

The above code snippet is a simple binary search that helps us to find the exact value of p. 

BUT HOW DOES BINARY SEARCH HELP??

Now, we know that n is dependent on the value of p. As we have the papprox we know that the papprox can be either greater than p or less than p. So we can say that if papprox > p then n_approx > n and if papprox < p then n_approx < n and finally if papprox = p then n_approx = n. We can do this using the binary search function find_p. primesgen function is used to find n_approx each time the iteration takes place

In this way we find the value of p. Using p we calculate q, r and s. Finally, we find d and perform decryption. Total exploit script is attached below.


from Crypto.Util.number import *
import gmpy2
n = 63503276937852850446665985957390379307440024971021230431993893491881624345662352363811917592750766531203356043483026044031384884152397966752357920486434617823027122279415036554847130392423900715402785773280279146047931988844559054831429226564586447952491921350715788091186848490634584031960739647318023686632925058823647108880767478971118608237886300608306051261004692404756371356302701018432847524301182730267480301933745056302779577973416730232149313436165949340434895975694570102514920769870034226468745369298052361213865705054347251550807
c = bytes_to_long("464757bacf2e67e0e253adbd024ee12c9ab5a7250f2caadc99ba4231565635345ab549790aaf472a2efad32a81efbee50127c476c3dab7313168912a577e61012a56b1de50a72f30a23642749ad2dda71b6d11b488d79511d0298d91640fdc61fbb1332156596e75fe56776361af653c5b14a90d555e0eb6048cf28dcc89ec752a9f46bb7d8c2a5cc16d2ac0d0dafae06ef95419fca0384ed9168ecd8157a0478999cfc347bcf2487bd3171fd9723acc336a6bf5c1a27e4863a0a8f784ee85d79fe9c934190f95ddb8604a0453978df7bee1071f12aea363fadfa9e0bde9792328".decode("hex"))
e = 65537

def nextPrime(n):
    num = n + 1
    while True:
        if isPrime(num):
            return num
        num += 1

def primesgen(p):
    q = nextPrime(13*p)
    r = nextPrime(p*q)
    s = nextPrime(q*r)
    return p*q*r*s

def find_p(papprox,n):
    while True:
      n_approx = primesgen(papprox)
      if n  n_approx:
          papprox = papprox + 1
          n_approx = primesgen(papprox)
      else:
    	    return papprox

papprox = gmpy2.iroot(n/pow(13,4),7)[0]
p = find_p(papprox,n)
q = nextPrime(13*p)
r = nextPrime(p*q)
s = nextPrime(q*r)
phi = (p-1)*(q-1)*(r-1)*(s-1)
d = inverse(e,phi)
pt = long_to_bytes(pow(c,d,n))
print pt


Yayy!! Here’s the flag: inctf{Mult1Pr1m3RSA_and_R3latedPr1m3s_m4d3_1t_d1ff1cult}

Just comment if you have any doubts or suggestions.

If you are interested you can also try the below challenge from ISITDTU CTF which is similar.
Link: https://ctftime.org/task/6338

Thank You!!! 😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s