# Write-up for ISITDTU

## Share mixer 1

Repeat base from 1 to 15 times. And bruteforce $2^{13} * 6^2$ cases.

from sage.all import *
from Crypto.Util.number import *
from pwn import *
from itertools import permutations, product
import itertools
from tqdm import trange

l = 32
payload = b''

lenPay = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2]
pos = [[0, 15, 30], [1, 16, 31], [2, 17], [3, 18], [4, 19], [5, 20], [6, 21], [7, 22], [8, 23], [9, 24], [10, 25], [11, 26], [12, 27], [13, 28], [14, 29]]


for i in range(32):
    payload += (str(i + 1).encode() + b' ') * lenPay[i]

cnt = {

}

check = []

def find_string(prefix):
    chars = string.ascii_letters + string.digits
    print(chars)
    for length in itertools.count(1):
        for s in itertools.product(chars, repeat=length):
            candidate = prefix + ''.join(s)
            if hashlib.sha256(candidate.encode()).hexdigest()[:6] == "000000":
                return ''.join(s)

with remote("35.187.238.100", "5001") as io:
# with process(["python3", "chall.py"]) as io:
    io.recvuntil(b'"')
    prefix = io.recvuntil(b'"').decode()[:-1]
    print(prefix)
    hsh = find_string(prefix)
    print(hsh)
    io.sendlineafter(b'Suffix: ', hsh.encode())
    # io.interactive()
    

    io.recvuntil(b'p = ')
    p = eval(io.recvline())

    M = Matrix(GF(p), l, l)
    for i in range(l):
        for j in range(l):
            M[j, i] = pow(i + 1, j, p)

    M_inv = M.inverse()

    io.sendlineafter(b'queries: ', payload)
    io.recvuntil(b'shares = ')
    shares = eval(io.recvline())

    for i in shares:
        if i not in cnt:
            cnt[i] = 1
        else:
            cnt[i] += 1

    for i in range(l):
        tmp = []
        for key in cnt.keys():
            if cnt[key] == lenPay[i]:
                tmp.append(key)

        check.append(tmp)

    permu = []
    cases = 1
    for i in check[:15]:
        permu.append(list(permutations(i)))
        cases *= len(permu[-1])

    print(cases)

    all_combinations = list(product(*permu))

    # io.recvuntil(b'cs = ')
    # cs = eval(io.recvline())      

    for i in trange(len(all_combinations)):

        combine = all_combinations[i]
        res = [0 for _ in range(l)]
        for per in range(len(combine)):
            for test in range(len(combine[per])):
                res[pos[per][test]] = combine[per][test]

        # if res == cs:


        target = vector(GF(p), res)
        FLAG = target * M_inv
        for ele in FLAG:
            try:
                print(long_to_bytes(int(ele)).decode())
            except:
                pass        

# ISITDTU{Mix1_a5850c98ad583157f0}

## Sign

Use approximate common divisor

from Crypto.Util.number import *
from pwn import *
import itertools
from sage.all import *

def find_string(prefix):
    chars = string.ascii_letters + string.digits
    print(chars)
    for length in itertools.count(1):
        for s in itertools.product(chars, repeat=length):
            candidate = prefix + ''.join(s)
            if hashlib.sha256(candidate.encode()).hexdigest()[:6] == "000000":
                return ''.join(s)

e = 11
test = 9862367575473329864720116176962265612928498129185633554727278267677201885640835843871216251075107868557348010535247198331945666244656653166225632442153406714059715993439024686203063278317154573607195324213887807701657781568182298633373441875755667257867933914806001294826530728619710024599472778052957270972263895687764997076625053340626394499162651377968237932763002215372017270724017429855425595966850926735212281408222002367431137436615492524537261234507228769295387477023565737831161975239663349915633518538512125973772795048287847 * 10 ** 77

fakeN = 0
cnt = 0
with remote("35.187.238.100", "5003") as io:
# with process(["python3", "chall.py"]) as io:
    io.recvuntil(b'"')
    prefix = io.recvuntil(b'"').decode()[:-1]
    print(prefix)
    hsh = find_string(prefix)
    print(hsh)
    io.sendlineafter(b'Suffix: ', hsh.encode())

    # io.interactive()
    # nTest = eval(io.recvline())


    io.sendlineafter(b'> ', b'2')
    io.recvuntil(b'sig = ')
    sigFlag = int(io.recvline().decode(), 16)

    Ns = []
    testcase = 20
    for i in range(testcase):
        io.sendlineafter(b'> ', b'1')
        io.recvuntil(b'sig = ')
        n = int(io.recvline().decode(), 16)
        Ns.append(n)

    M = Matrix(ZZ, testcase, testcase)
    for i in range(testcase - 1):
        M[0, i + 1] = Ns[i + 1] ** e - test
        M[i + 1, i + 1] = Ns[0] ** e - test

    M[0, 0] = 2 ** 256
    M = M.LLL()
    n = abs(Ns[0] ** e // (M[0, 0] // 2 ** 256))
    print(n)
    # print(nTest)

    print(long_to_bytes(pow(sigFlag, e, n)))
    print(long_to_bytes(pow(sigFlag, e, n - 1)))
#     ISITDTU{h0W-d0-U-kn0W-mY-m0dUlUS??}

## Share Mixer 2

# from sage.all import *
from Crypto.Util.number import *
from pwn import *
from itertools import permutations, product
import itertools
import random

l = 32
payload = b''

while True:

    # with remote("35.187.238.100", "5003") as io:
    with process(["python3", "chall.py"]) as io:
        # io.recvuntil(b'"')
        # prefix = io.recvuntil(b'"').decode()[:-1]
        # print(prefix)
        # hsh = find_string(prefix)
        # print(hsh)
        # io.sendlineafter(b'Suffix: ', hsh.encode())
        
        io.recvuntil(b'p = ')
        p = eval(io.recvline())

        if (p - 1) % 32 != 0:
            io.close()
            continue

        print(p)

        for _ in range(50000):
            e = random.randint(2, p - 1)
            base = pow(e, (p - 1) // 32, p)
            if pow(base, 32, p) == 1 and pow(base, 16, p) != 1:
                break
        else:
            continue

        xs = [pow(base, i, p) for i in range(32)]

        payload = b''
        for i in xs:
            payload += str(i).encode() + b' '

        # io.interactive()

        io.sendlineafter(b'queries: ', payload)
        io.recvuntil(b'shares = ')
        shares = eval(io.recvline())

        FLAG = sum(shares) * inverse(32, p) % p

        try:
            print(long_to_bytes(FLAG).decode())
            exit(0)
        except:
            pass

# ISITDTU{M1x_4941n!_73360d0e5fb4}