Solution for Cyber Security Rumble CTF 2020 - Pady McPadface

main.c

#!/usr/bin/env python3
from pwn import *

n = 23946008544227658126007712372803958643232141489757386834260550742271224503035086875887914418064683964046938371640632153677880813529023769841157840969433316734058706481517878257755290676559343682013294580085557476138201639446709290119631383493940405818550255561589074538261117055296294434994144540224412018398452371792093095280080422459773487177339595746894989682038387107119249733105558301840478252766907821053044992141741079156669562032221433390029219634673005161989684970682781410366155504440886376453225497112165607897302209008685179791558898003720802478389914297472563728836647547791799771532020349546729665006643

def get_ciphertexts():
    conn = remote('chal.cybersecurityrumble.de', 34187)

    while (conn.recvline()) != b'~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n':
        pass
    conn.recvline();
    conn.recvline();

    ciphertexts = []
    while True:
        try:
            ciphertexts += [int(conn.recvline(), 10)]
        except EOFError:
            break

    return ciphertexts

threshold = 20
ciphertexts = []
for i in range(0, threshold):
    ciphertexts += [get_ciphertexts()]

# Source: https://rosettacode.org/wiki/Jacobi_symbol#Python
def jacobi(a, n):
    if n <= 0:
        raise ValueError("'n' must be a positive integer.")
    if n % 2 == 0:
        raise ValueError("'n' must be odd.")
    a %= n
    result = 1
    while a != 0:
        while a % 2 == 0:
            a //= 2
            n_mod_8 = n % 8
            if n_mod_8 in (3, 5):
                result = -result
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            result = -result
        a %= n
    if n == 1:
        return result
    else:
        return 0

bitstring = '0'
for i in range(0, len(ciphertexts[0])):
    one = False
    for t in range(0, threshold):
        if jacobi(ciphertexts[t][i], n) == -1:
            one = True
            break

    if one:
        bitstring += '1'
    else:
        bitstring += '0'

def decode_binary_string(s):
    return ''.join(chr(int(s[i*8:i*8+8],2)) for i in range(len(s)//8))

print(decode_binary_string(bitstring))