writeups/2021/corctf/supercomputer

supercomputer

by haskal

crypto / 457 pts / 85 solves

I ran this code with a supercomputer from the future to encrypt the flag, just get your own and decryption should be simple!

provided files: supercomputer.py output.txt

solution

first, do some source review. there is not a lot of it

def v(p, k):
    ans = 0
    while k % p == 0:
        k /= p
        ans += 1
    return ans

this seems to be computing the number of times p is a factor of k

p, q, r = getPrime(2048), getPrime(2048), getPrime(2048)
print(p, q, r)
n = pow(p, q) * r

this is taking a very very large power and multiplication (don't actually run this it'll never finish lol -- it was run on a supercomputer from the future but it can't be run on our computers)

a1 = random.randint(0, n)
a2 = n - a1
assert a1 % p != 0 and a2 % p != 0
t = pow(a1, n) + pow(a2, n)
print(binascii.hexlify(xor(flag, long_to_bytes(v(p, t)))))

and here we generate a random number, subtract it from n, take the power and then use the factor-counting function to xor the flag

now i don't know how to math at all so here i decided to run this with some much smaller primes and see what happens (dynamic analysis ftw). try replacing p, q, r with combinations of 3, 5, 7, and 11. you'll notice immediately that the result is always 2q. so let's try it

[ins] In [1]: import ast

[ins] In [2]: with open("output.txt") as f:
         ...:     [p,q,r] = [int(x) for x in f.readline().strip().split(" ")]
         ...:     enc = ast.literal_eval(f.readline())

[ins] In [3]: from pwn import xor

[ins] In [4]: from binascii import unhexlify

[ins] In [5]: enc = unhexlify(enc)

[ins] In [6]: v = 2 * q

[ins] In [7]: xor(enc, v.to_bytes(v.bit_length()//8+1, "big"))
Out[7]: b'corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}\ncorctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}\ncorctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}\ncorctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}\ncorctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4'

yea