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!!! 😀
