UIUCTF 2020
Cryptography
ac01010
July 20th, 2020
CRT

CRT Bruteforce

# 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)
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}