My Write-up on SECCON CTF Qualification 2015: Find The Prime Numbers (Crypto 200)

A few weeks ago, I took time to play SECCON 2015 CTF Quals. At this CTF, challenge that I can finish is Find the Prime Numbers.

Challenge

$ Cp pq.cgi /var/www/pq.cgi.txt

http://pailler.quals.seccon.jp/%5Bpq.cgi%5D(./pq.cgi).txt

http://pailler.quals.seccon.jp/cgi-bin/%5Bpq.cgi%5D(./pq.cgi)

Completion

Known algorithm on this URL and output on this URL.

To get the flag, we must know the value of v[“num”]. How do I found it? Let’s explore.

From the output we know value of variables c, o, and p in the equation below:

q = "%019d + %019d = %019d" % (c, o, h)

Next step is find value of variable n, I used a congruence modular techniques on following equation:

h = (c * o)% (n * n)

Furthermore, we must look value of the variable x in the equation below using same technique:

o = (pow (n + 1, 1, n * n) * x)% (n * n)

The final step, after we know the value of the variable x, we can look for v[‘num’] in the equation below using modular congruence technique and Pohlig-Hellman algorithm.

c = (pow (n + 1, int (v ["num"]), n * n) * x)% (n * n)

After knowing the value of v [‘num’] we can access the flag as shown below:

Thank you for reading this article.