Coelacanth Vault

UIUCTF 2020
Cryptography
ac01010
July 20th, 2020
CRT


CRT Bruteforce

Download file: coelacanth_vault.zip

Coelacanth Vault

300 Points


This challenge gave you a system of congruences that you had to solve for the flag. However, it only gave you a maximum of 9 out of 15 congruences. Using the system of 9 congruences, we can bruteforce numbers with the same residue mod n1*n2*n3*...n9.

from pwn import *
from sympy.ntheory.modular import crt
def get_poss(por):
    portions = por
    a,b = [q for q,w in portions], [w for q,w in portions]
    li = crt(b,a)[0]
    prod = 1
    poss=[]
    for i in b:
        prod*=i
    poss.append(int(li))
    count = 0
    while count<250:
        count+=1
        li+=prod
        poss.append(int(li))
    return(poss)
c = remote('chal.uiuc.tf',2004)
c.recvuntil("caught? ")
c.sendline("9")
c.recvuntil("portions:\n")
for i in range(5):
    portion = c.recvline()
    poss = (get_poss(eval(portion)))
    for j in range(250):
        send = poss[j]
        c.sendline(str(send))
        if (b"unlocked" in c.recvline()):
            for i in range(3):
                r=c.recvline()
                if b"{" in r:
                    print(r.decode('utf-8'))
                    break
            break

Flag: uiuctf{small_oysters_expire_quick}