*CTF-Qualifier-2023/Crypto/gcccd writeup

#!/usr/bin/env python3

from secret import flag
import socketserver
import hashlib
import signal
import random
import string
import os

p=20973268502876719886012765513713011996343752519737224550553652605696573094756255499211333096502971357908939298357512380813773140436677393056575164230564778609423872301899323721040416852230597466288892977839300189625522429038289083381035647126860128821615664730513694930502000903655609105029016636999073477487851081722316115785141
enc=lambda x:pow(17,x,p)
m=int(flag.encode().hex(),16)

def gcd(a,b,f=enc):
    if b:
        return gcd(b,a%b,f)
    else:
        return f(a)

class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def timeout_handler(self, signum, frame):
        self.request.close()

    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = hashlib.sha256(proof.encode()).hexdigest()
        self.request.send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}\n".encode()+b'Give me XXXX: ')
        x = self.request.recv(1024).strip(b'\n')
        if len(x) != 4 or hashlib.sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def handle(self):
        signal.alarm(60)

        if not self.proof_of_work():
            return

        while True:
            try:
                self.request.send(b'type:')
                t=int(self.request.recv(1024).strip(b'\n'))
                self.request.send(b'a:')
                a=int(self.request.recv(1024).strip(b'\n'))
                self.request.send(b'b:')
                b=int(self.request.recv(1024).strip(b'\n'))
                assert a>0 and b>0
                if t==1:#enc test
                    self.request.send(b'%d\n'%gcd(a,b))
                elif t==2:#leak try1
                    self.request.send(b'%d\n'%gcd(a,m))
                elif t==3:#leak try2
                    self.request.send(b'%d\n'%gcd(a,b,f=lambda x:gcd(x,m)))
                elif t==4:#leak try3
                    self.request.send(b'%d\n'%gcd(a,m,f=lambda x:gcd(x,b)))
                else:
                    self.request.close()
                    break
            except BrokenPipeError:
                break
            except:
                self.request.send(b'Bad input!\n')


class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 23333
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

p=20973268502876719886012765513713011996343752519737224550553652605696573094756255499211333096502971357908939298357512380813773140436677393056575164230564778609423872301899323721040416852230597466288892977839300189625522429038289083381035647126860128821615664730513694930502000903655609105029016636999073477487851081722316115785141
F = GF(p)
g = F.multiplicative_generator()
order = g.multiplicative_order()
order == p-1, factor(order)

def gcd_count(a, b, count=0):
    if b:
        return gcd_count(b,a%b,count+1)
    else:
        return a, count
    
gcd_count(fibonacci(1000), fibonacci(1001))

gcd_count(fibonacci(1000)*pow(2, 100), fibonacci(1001)*pow(2, 100))

fibonacci(1000).nbits()

import itertools
from pwn import *
context.log_level = 'info'
r = None
local = False

def init_connect(local):
    if local:
        r = remote("127.0.0.1", 2333)
    else:
        r = remote("122.9.153.69", 23333)
    return r
    
def proof_of_work():
    print("pow doing.")

    def receive_proof_of_work():
        r.recvuntil(b"XXXX+")
        p = r.recvuntil(b")").rstrip(b")")
        r.recvuntil(b"== ")
        h = r.recvuntil(b'\n').rstrip(b'\n')
        return p.decode(), h.decode()

    def solve_proof_of_work(p, h):
        for c in itertools.product(string.ascii_letters+string.digits, repeat=4):
            proof = "".join(c) + p
            if hashlib.sha256(proof.encode()).hexdigest() == h:
                return "".join(c)
    p, h = receive_proof_of_work()
    proof = solve_proof_of_work(p, h)
    r.sendlineafter(b'Give me XXXX: ', proof.encode())
    print("pow done.")

def enc_io(t, a, b):
    global r
    if r is None:
        r = init_connect(local)
        if not local:
            proof_of_work()
    try:
        r.recvuntil(b"type:")
        r.sendline(str(t).encode())
        r.recvuntil(b"a:")
        r.sendline(str(a).encode())
        r.recvuntil(b"b:")
        r.sendline(str(b).encode())
        return int(r.recvuntil(b'\n').rstrip(b'\n'))
    except EOFError as err:
        r = None
        return enc_io(t, a, b)
    
def test(a, b):
    return enc_io(1, a, b)

def try1(a):
    """
    gcd(a,m)
    """
    return enc_io(2, a, 1) 

def try2(a, b):
    """
    gcd(a,b,f=lambda x:gcd(x,m))
    """
    return enc_io(3, a, b) 

def try3(a, b):
    """
    gcd(a,m,f=lambda x:gcd(x,b))
    """
    return enc_io(4, a, b) 

def oracle(t, a, b, debug=False, msg=''):    
    try:
        enc_io(t, a, b)
    except ValueError as err:
        if debug:
            print(err, msg)
        return True
    return False

oracle(1, fibonacci(1024), fibonacci(1024+1), True)

fibs = {}
def fib(i):
    if i not in fibs:
        fibs[i] = fibonacci(i) 
    return fibs[i]

def guess(a, base=900):
    """
    return remote gcd iter count
    """
    for i in range(base, 1000):
        if oracle(3, fib(i)*a, fib(i+1)*a):
            return i

count_cache = {}

def clean_cache():
    global count_cache
    count_cache = {}

def gcd_count_cache(a, b, count=0):
    """
    return gcd(a, b), itercount
    """
    if (a, b) in count_cache:
        g, c = count_cache[(a, b)]
        return g, count + c
    if b:
        return gcd_count(b,a%b,count+1)
    else:
        return a, count
    
def gcd_counts_remainders(b):
    """
    base = gcd(1, b)
    return {itercount - base: remainders}
    """
#     _, base = gcd_count_cache(b, 1)
    counts = {}
    for i in range(b):
        g, count = gcd_count_cache(b, b+i)
        count_cache[(b+i, b)] = (g, count)
#         count -= base
        if count not in counts:
            counts[count] = []
        counts[count].append(i)
    return counts        

remote_base = guess(1); remote_base

counts_remainders3 = gcd_counts_remainders(3); counts_remainders3

remote_count3 = guess(3, remote_base-max(counts_remainders3))
remote_count3 = remote_base - remote_count3 + 2; remote_count3

remote_remainder3 = counts_remainders3[remote_count3]; remote_remainder3

counts_remainders5 = gcd_counts_remainders(5)
remote_count5 = guess(5, remote_base-max(counts_remainders5))
remote_count5 = remote_base - remote_count5 + 2
remote_remainder5 = counts_remainders5[remote_count5]

counts_remainders5, remote_count5, remote_remainder5

counts_remainders7 = gcd_counts_remainders(7)
remote_count7 = guess(7, remote_base-max(counts_remainders7))
remote_count7 = remote_base - remote_count7 + 2
remote_remainder7 = counts_remainders7[remote_count7]

counts_remainders7, remote_count7, remote_remainder7

def check_valid(remainders, primes, debug=False):
    assert len(remainders) > 1 and len(primes) > 1
#     if len(remainders) > 20:
#         remainders = remainders[-20:]
#         primes = primes[-20:]
    c = crt(remainders, primes)
    pi = product(primes)
    _, local_count = gcd_count_cache(pi, c)
    remote_count = guess(pi, remote_base-local_count-2)
    remote_count = remote_base - remote_count + 2
    if debug:
        print(primes[-1], remainders[-1], remote_count, local_count, remote_count == local_count + 2)
    return remote_count == local_count + 2

for remainder in [2, 3, 6]:
    check_valid([1, 2, 1, remainder], [2, 3, 5, 7], True)

def check_valid_brute(remainders, primes, debug=False):
    if len(remainders) > 5:
        remainders = remainders[:4] + remainders[-1:]
        primes = primes[:4] + primes[-1:]
    new_remainders = [remainders[-1]]
    new_primes = [primes[-1]]
    for remainder, prime in zip(remainders[:-1], primes[:-1]):
        new_remainders.append(remainder)
        new_primes.append(prime)
        if not check_valid(new_remainders, new_primes, debug):
            return False
    return True

for remainder in [2, 3, 6]:
    check_valid_brute([1, 2, 1, remainder], [2, 3, 5, 7], True)

local=False
r.close()
r=init_connect(local)
clean_cache()
remote_base = guess(1)

def generate_candidate_primes():
    candidate_primes = []
    pi = 1
    prime = 2
    while pi.nbits() < 250:
        candidate_primes.append(prime)
        prime = prime.next_prime()
        pi *= prime
    return candidate_primes

from tqdm.notebook import trange

pi = 1
prime = 2
remainders = []
primes = []

candidate_primes = generate_candidate_primes()
for _ in trange(len(candidate_primes)):
    if pi.nbits() > 250:
        break
    print("bits:", pi.nbits())
    counts_remainders = gcd_counts_remainders(prime)
    remote_count = guess(prime, remote_base-max(counts_remainders))
    remote_count = remote_base - remote_count + 2
    remote_remainders = counts_remainders[remote_count]
    valid_remainders = []
    if len(remote_remainders) == 1:
        valid_remainders = remote_remainders
    else:
        for remainder in remote_remainders:
            if check_valid_brute(remainders + [remainder], primes + [prime], False):
                valid_remainders.append(remainder)
    if len(valid_remainders) == 1:
        print("m %", prime, "=", valid_remainders[0])
        remainders.append(valid_remainders[0])
        primes.append(prime)
        pi *= prime
    else:
        print(prime, valid_remainders)
            
    prime = prime.next_prime() 

from Crypto.Util.number import long_to_bytes

long_to_bytes(crt(remainders,primes))