COMPFEST CTF 2020
This is writeup for COMPFEST CTF 2020. It’s such a long time I haven’t taken part in any CTFs. Actually, I have some knowledge and experience about cryptography but I haven’t used it for years. I want to refine it.
So, let’s get it.
I-Hope-It-Is-Easy
Challenge gives us 2 files: prob.py and encrypted.txt.
Here is the prob.py
:
import random
def f(n):
c = 0
for i in range(2, n):
if (n^0 == n):
if (n*n // n == n):
if (2*n != n-1):
if (n**0 + 1 != 1):
m = n
while (m > 0):
m -= i
if (m == 0):
c += 1
if (c == 1):
return True
else:
return False
FLAG = open('flag.txt', 'rb').read()
encrypted = []
a = 10**400
b = 10**500
n = random.randint(a, b)
for c in FLAG:
while(not(f(n))):
n = random.randint(a, b)
encrypted.append(c ^ n)
n += 1
txtFile = open('encrypted.txt', 'w')
txtFile.write(', '.join(list(map(str, encrypted))))
Let’s look at function f(n)
:
- The
if
sequence is alwaysTrue
- The next
while
andif
is to testm
is divisible byi
.
So, f
returns True
only if n
has only one divisor that’s greater than 1. Hence, n
is square number. Now, we have a condition to verify n
for each cipher number in encrypted.txt
Below is python script to solve this challenge.
# brute force in printable character set
# find n by XOR cipher with character
# if n is square number returns the corresponding character
def solve_single(c):
for i in string.printable:
n = ord(i) ^ c
if gmpy2.is_square(n):
return i
return None
#
def get_flag():
encrypted = open('encrypted.txt').read()
ciphers = encrypted.split(", ")
flag = []
for c in ciphers:
ch = solve_single(int(c))
if f is not None:
flag.append(ch)
return ''.join(flag)
print get_flag() # COMPFEST12{ez_pz_lemonade_squeez_a42447}
Mutual-Friend
The challenge provides us a zip archive which contains 5 files.
After quick glance at those files, we can conclude:
primes.txt
has 4000 primesmain.py
applies the RSA encryption with pair of primes fromprimes.txt
.
So, if server returns 2 N
that has the same one factor, we can find another factor then decrypt the corresponding cipher.
Below is dummy script to solve the challenge.
import socket
import gmpy2
HOST = '128.199.157.172'
PORT = 27268
try:
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
print "Socket successfully created"
except socket.error as err:
print "socket creation failed with error %s" %(err)
s.connect((HOST, PORT))
requested = False
N = None
c = None
e = 65537
while True:
# dummy check
if not requested:
d = s.recv(4096)
s.sendall('\n')
requested = True
recv = s.recv(8192)
if not repr(recv).__contains__("N ="):
s.sendall(b'\n')
continue
data = repr(recv).split('\\n')
data = data[1:-2]
# get the first N
if N is None:
N = int(data[0].split(' = ')[1])
c = int(data[-1].split(' = ')[1])
s.sendall(b'\n')
continue
N1 = None
for d in data:
if d.__contains__("N = "):
N1 = int(d.split(' = ')[1])
break
if N1 is None:
continue
gcd = gmpy2.gcd(N, N1)
# find another N that has the same factor
if gcd != 1:
print "Found " + "="*81
p = gcd
q = gmpy2.div(N, gcd)
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
plain_text = hex(gmpy2.powmod(c, d, N))[2:].decode("hex")
print plain_text # COMPFEST12{Euclid_W0ulD_b_Pr0Ud_Ov_4l1_7h3sE_MetH_eXpeRt5_a39e7a}
break
s.sendall(b'\n')
That’s 2 challenges I solved. The mutual-friend
makes me realize that I’ve lost really much. I have to re-read about RSA to solve this.
Shame on me.