强网杯-Qualifier-2022/强网先锋/polydiv writeup

class Polynomial2():
    '''
    模二多项式环，定义方式有三种
    一是从高到低给出每一项的系数
        >>> Polynomial2([1,1,0,1])
        x^3 + x^2 + 1

    二是写成01字符串形式
        >>> Polynomial2('1101')
        x^3 + x^2 + 1

    三是直接给出系数为1的项的阶
        >>> Poly([3,1,4])
        x^4 + x^3 + x
        >>> Poly([]) # 加法元
        0
        >>> Poly(0) # 乘法元
        1
        >>> Poly(1,2) * Poly(2,3)
        x^5 + x^3
    '''
    def __init__(self,ll):
        
        if type(ll) ==  str:
            ll = list(map(int,ll))

        self.param = ll[::-1]
        self.ones = [i for i in range(len(self.param)) if self.param[i] == 1] # 系数为1的项的阶数列表
        self.Latex = self.latex()
        self.b = ''.join([str(i) for i in ll]) # 01串形式打印系数
        
        self.order = 0 # 最高阶
        try:self.order = max(self.ones)
        except:pass
        
    def format(self,reverse = True):
        '''
            格式化打印字符串
            默认高位在左
            reverse = False时，低位在左
            但是注意定义多项式时只能高位在右
        '''
        r = ''
        if len(self.ones) == 0:
            return '0'
        if reverse:
            return ((' + '.join(f'x^{i}' for i in self.ones[::-1])+' ').replace('x^0','1').replace('x^1 ','x ')).strip()
        return ((' + '.join(f'x^{i}' for i in self.ones)+' ').replace('x^0','1').replace('x^1 ','x ')).strip()

    def __call__(self,x):
        '''
            懒得写了，用不到
        '''
        print(f'call({x})')

    def __add__(self,other):
        '''
            多项式加法
        '''
        a,b = self.param[::-1],other.param[::-1]
        if len(a) < len(b):a,b = b,a
        for i in range(len(a)):
            try:a[-1-i] = (b[-1-i] + a[-1-i]) % 2
            except:break
        return Polynomial2(a)

    def __mul__(self,other):
        '''
            多项式乘法
        '''

        a,b = self.param[::-1],other.param[::-1]
        r = [0 for i in range(len(a) + len(b) - 1)]
        for i in range(len(b)):
            if b[-i-1] == 1:
                if i != 0:sa = a+[0]*i
                else:sa = a
                sa = [0] * (len(r)-len(sa)) + sa
                #r += np.array(sa)
                #r %= 2
                r = [(r[t] + sa[t])%2 for t in range(len(r))]
        return Polynomial2(r)

    def __sub__(self,oo):
        # 模二多项式环，加减相同
        return self + oo


    def __repr__(self) -> str:
        return self.format()
    
    def __str__(self) -> str:
        return self.format()

    def __pow__(self,a):
        # 没有大数阶乘的需求，就没写快速幂
        t = Polynomial2([1])
        for i in range(a):
            t *= self
        return t
    
    def latex(self,reverse=True):
        '''
            Latex格式打印...其实就是给两位及以上的数字加个括号{}
        '''
        def latex_pow(x):
            if len(str(x)) <= 1:
                return str(x)
            return '{'+str(x)+'}'
        
        r = ''
        if len(self.ones) == 0:
            return '0'
        if reverse:
            return (' + '.join(f'x^{latex_pow(i)}' for i in self.ones[::-1])+' ').replace('x^0','1').replace(' x^1 ',' x ').strip()
        return (' + '.join(f'x^{latex_pow(i)}' for i in self.ones)+' ').replace('x^0','1').replace(' x^1 ',' x ').strip()

    def __eq__(self,other):
        return self.ones == other.ones

    def __lt__(self,other):
        return max(self.ones) < max(other.ones)

    def __le__(self,other):
        return max(self.ones) <= max(other.ones)

def Poly(*args):
    '''
        另一种定义方式
        Poly([3,1,4]) 或 Poly(3,1,4)
    '''
    if len(args) == 1 and type(args[0]) in [list,tuple]:
        args = args[0]
        
    if len(args) == 0:
        return Polynomial2('0')
    
    ll = [0 for i in range(max(args)+1)]
    for i in args:
        ll[i] = 1
    return Polynomial2(ll[::-1])

    
PP = Polynomial2
P = Poly
# 简化名称,按长度区分 P 和 PP
if __name__ == '__main__':
    p = Polynomial2('10011')
    p3 = Polynomial2('11111')
    Q = p*p3

import socketserver
import os, sys, signal
import string, random
from hashlib import sha256

from secret import flag
from poly2 import *

pad = lambda s:s + bytes([(len(s)-1)%16+1]*((len(s)-1)%16+1))
testCases = 40

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def close(self):
        self.send(b"Bye~")
        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 = sha256(proof.encode()).hexdigest()
        self.send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'Give me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def guess(self):
        from Crypto.Util.number import getPrime
        a,b,c = [getPrime(i) for i in [256,256,128]]
        pa,pb,pc = [PP(bin(i)[2:]) for i in [a,b,c]]
        r = pa*pb+pc
        self.send(b'r(x) = '+str(r).encode())
        self.send(b'a(x) = '+str(pa).encode())
        self.send(b'c(x) = '+str(pc).encode())
        self.send(b'Please give me the b(x) which satisfy a(x)*b(x)+c(x)=r(x)')
        #self.send(b'b(x) = '+str(pb).encode())
        
        return self.recv(prompt=b'> b(x) = ').decode() == str(pb)


    def handle(self):
        #signal.alarm(1200)

        if not self.proof_of_work():
            return

        for turn in range(testCases):
            if not self.guess():
                self.send(b"What a pity, work harder.")
                return
            self.send(b"Success!")
        else:
            self.send(b'Congratulations, this is you reward.')
            self.send(flag)
        
        

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

#class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

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