from gmpy2 import*

from Crypto.Util.number import*

c = 

s = 

n1= 

e=0x10001

e1=pow(e,e,n1)

c1=e1*s

p=gcd(c1-1,n1)

q=n1//(p*p)

phi1=p*(p-1)*(q-1)

d=inverse(e,phi1)

e=pow(c,d,n1)

print(e)

n=

c=

e=

'''发现e很大 使用维纳不行，那就博纳试试

import time

debug = True

strict = False

helpful_only = True

dimension_min = 7 

def helpful_vectors(BB, modulus):

    nothelpful = 0

    for ii in range(BB.dimensions()[0]):

        if BB[ii,ii] >= modulus:

            nothelpful += 1

    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

def matrix_overview(BB, bound):

    for ii in range(BB.dimensions()[0]):

        a = ('%02d ' % ii)

        for jj in range(BB.dimensions()[1]):

            a += '0' if BB[ii,jj] == 0 else 'X'

            if BB.dimensions()[0] < 60:

                a += ' '

        if BB[ii, ii] >= bound:

            a += '~'

        print(a)

# delete the unhelpful vectors

# we start at current = n-1 

def remove_unhelpful(BB, monomials, bound, current):

    if current == -1 or BB.dimensions()[0] <= dimension_min:

        return BB

    for ii in range(current, -1, -1):

        if BB[ii, ii] >= bound:

            affected_vectors = 0

            affected_vector_index = 0

            for jj in range(ii + 1, BB.dimensions()[0]):

                if BB[jj, ii] != 0:

                    affected_vectors += 1

                    affected_vector_index = jj

            # task 0

            if affected_vectors == 0:

                print("* removing unhelpful vector", ii)

                BB = BB.delete_columns([ii])

                BB = BB.delete_rows([ii])

                monomials.pop(ii)

                BB = remove_unhelpful(BB, monomials, bound, ii-1)

                return BB

            # task 1

            elif affected_vectors == 1:

                affected_deeper = True

                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):

                    if BB[kk, affected_vector_index] != 0:

                        affected_deeper = False

                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):

                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)

                    BB = BB.delete_columns([affected_vector_index, ii])

                    BB = BB.delete_rows([affected_vector_index, ii])

                    monomials.pop(affected_vector_index)

                    monomials.pop(ii)

                    BB = remove_unhelpful(BB, monomials, bound, ii-1)

                    return BB

    return BB

def boneh_durfee(pol, modulus, mm, tt, XX, YY):

    PR.<u, x, y> = PolynomialRing(ZZ)

    Q = PR.quotient(x*y + 1 - u) # u = xy + 1

    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts

    gg = []

    for kk in range(mm + 1):

        for ii in range(mm - kk + 1):

            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk

            gg.append(xshift)

    gg.sort()

    monomials = []

    for polynomial in gg:

        for monomial in polynomial.monomials():

            if monomial not in monomials:

                monomials.append(monomial)

    monomials.sort()

    for jj in range(1, tt + 1):

        for kk in range(floor(mm/tt) * jj, mm + 1):

            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)

            yshift = Q(yshift).lift()

            gg.append(yshift) 

    for jj in range(1, tt + 1):

        for kk in range(floor(mm/tt) * jj, mm + 1):

            monomials.append(u^kk * y^jj)

    # 构造 lattice 

    nn = len(monomials)

    BB = Matrix(ZZ, nn)

    for ii in range(nn):

        BB[ii, 0] = gg[ii](0, 0, 0)

        for jj in range(1, ii + 1):

            if monomials[jj] in gg[ii].monomials():

                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    if helpful_only:

        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)

        nn = BB.dimensions()[0]

        if nn == 0:

            print("failure")

            return 0,0

    if debug:

        helpful_vectors(BB, modulus^mm)

    det = BB.det()

    bound = modulus^(mm*nn)

    if det >= bound:

        print("We do not have det < bound. Solutions might not be found.")

        print("Try with highers m and t.")

        if debug:

            diff = (log(det) - log(bound)) / log(2)

            print("size det(L) - size e^(m*n) = ", floor(diff))

        if strict:

            return -1, -1

    else:

        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    if debug:

        matrix_overview(BB, modulus^mm)

    # LLL

    if debug:

        print("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:

        print("LLL is done!")

    if debug:

        print("looking for independent vectors in the lattice")

    found_polynomials = False

    for pol1_idx in range(nn - 1):

        for pol2_idx in range(pol1_idx + 1, nn):

            PR.<w,z> = PolynomialRing(ZZ)

            pol1 = pol2 = 0

            for jj in range(nn):

                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)

                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant

            PR.<q> = PolynomialRing(ZZ)

            rr = pol1.resultant(pol2)

            if rr.is_zero() or rr.monomials() == [1]:

                continue

            else:

                print("found them, using vectors", pol1_idx, "and", pol2_idx)

                found_polynomials = True

                break

        if found_polynomials:

            break

    if not found_polynomials:

        print("no independant vectors could be found. This should very rarely happen...")

        return 0, 0

    rr = rr(q, q)

    # solutions

    soly = rr.roots()

    if len(soly) == 0:

        print("Your prediction (delta) is too small")

        return 0, 0

    soly = soly[0][0]

    ss = pol1(q, soly)

    solx = ss.roots()[0][0]

    return solx, soly

def main():

    N = 

    # the public exponent

    e = 

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)

    delta = 0.25 # this means that d < N^delta

    # Lattice (tweak those values)

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)

    m = 4 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these

    t = int((1-2*delta) * m)  # optimization from Herrmann and May

    X = 2*floor(N^delta)  # this _might_ be too much

    Y = floor(N^(1/2))    # correct if p, q are ~ same size

    # Don't touch anything below

    # Problem put in equation

    P.<x,y> = PolynomialRing(ZZ)

    A = int((N+1)/2)

    pol = 1 + x * (A + y)

    if debug:

        print("~~~ checking values ~~~")

        print("[*] delta:", delta)

        print("[*] delta < 0.292", delta < 0.292)

        print("[*] size of e:", int(log(e)/log(2)))

        print("[*] size of N:", int(log(N)/log(2)))

        print("[*] m:", m, ", t:", t)

    # boneh_durfee

    if debug:

        print("~~~ running ~~~ ")

        start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # found a solution?

    if solx > 0:

        print("~~~ [!] found ~~~")

        if False:

            print("x:", solx)

            print("y:", soly)

        d = int(pol(solx, soly) / e)

        print("private key found:", d)

    else:

        print("[!][!][!] no solution was found ...")

    if debug:

        print("=== %s seconds ===" % (time.time() - start_time))

if __name__ == "__main__":

    main()

'''

d=

print(long_to_bytes(pow(c,d,n)))

'''

def short_pad_attack(c1, c2, e, n):

    PRxy.<x,y> = PolynomialRing(Zmod(n))

    PRx.<xn> = PolynomialRing(Zmod(n))

    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1

    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)

    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)

    h = h.univariate_polynomial()

    h = h.change_ring(PRx).subs(y=xn)

    h = h.monic()

    kbits = n.nbits()//(2*e*e)

    diff = h.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4

    return diff

def related_message_attack(c1, c2, diff, e, n):

    PRx.<x> = PolynomialRing(Zmod(n))

    g1 = x^e - c1

    g2 = (x+diff)^e - c2

    def gcd(g1, g2):

        while g2:

            g1, g2 = g2, g1 % g2

        return g1.monic()

    return -gcd(g1, g2)[0]

if __name__ == '__main__':

    n = 

    e = 7

    c1 =

    c2 = 

    diff = short_pad_attack(c1, c2, e, n)

    print("difference of two messages is %d" % diff)

    m1 = related_message_attack(c1, c2, diff, e, n)

    print("m1:", m1)

    print("m2:", m1 + diff)

    '''

m=

print(long_to_bytes(m))

from pwn import*

import string

from hashlib import*

from math import*

def pow():

    io.recvuntil('XXXX')

    str1=io.recvuntil(b"== ")[1:-5]

    sha=io.recvuntil('\n')[:-1]

    for i in a:

        for j in a:

            for k in a:

                for m in a:

                    stringa=i+j+k+m+str(str1,encoding='utf-8')

                    has=sha256(stringa.encode()).hexdigest()

                    if bytes(has,encoding='utf8')==sha:

                        io.sendline(i+j+k+m)

                        return 1

def getdata():

    io.recvuntil("?\n")

    io.recvuntil("[")

    data=[]

    for i in range(7):

        data.append(int(io.recvuntil(",")[:-1]))

    data.append(int(io.recvuntil("]")[:-1]))

    print(data)

    return data

def getdata2(n):

    io.recvuntil("win!\n[!]")

    io.recvuntil("[")

    data=[]

    for i in range(n*8+7):

        data.append(int(io.recvuntil(",")[:-1]))

    data.append(int(io.recvuntil("]")[:-1]))

    print(data)

    return data

def task1():

    charr=''

    for i in range(len(data)):

        io.sendline("1")

        io.recvuntil("x: \n[-]")

        io.sendline(str(data[i]+1).encode())

        io.recvuntil("answer:")

        num=(float(io.recvuntil("\n")[:-1]))

        cha=0

        for j in range(len(data)):

            if j==i :

                continue

            cha += 85/(data[i]-data[j])

        num=round(num-cha)

        io.recvuntil("[-]")

        charr+=(chr(num))

    print(charr)

    return charr

def task2():

    io.sendline("2")

    io.recvuntil("[-]")

    io.sendline(charr)

if __name__=="__main__":

    a=string.ascii_letters+string.digits

    while 1:

        try:

            io=remote("127.0.0.1",28735)

            pow()

            data=getdata()

            charr=task1()

            task2()

            for i in range(4):

                    data=getdata2(i+1)

                    charr=task1()

                    task2()

            io.recvuntil("flag")

            flag=b'flag'+io.recvuntil("}")

            print(flag)

            break

        except:

            continue

    io.interactive()

from Crypto.Util.number import*

from gmpy2 import*

pubkeys = [(, ), (, )]

cs = (, )

(N1,e1) = pubkeys[0]

(N2,e2) = pubkeys[1]

c1 = cs[0]

c2 = cs[1]

M = #iroot(N2,2)[0]

'''

A=Matrix(ZZ,[[M,e1,e2],[0,-N1,0],[0,0,-N2]])

A.LLL()

'''

d= A.LLL()[0][0] //M

kkk1=  A.LLL()[0][1]           

kkk2=  A.LLL()[0][2]

#d e1-k1 N1=1+k1 s1=kkk1

k1=(d*e1-kkk1)//N1

k2=(d*e2-kkk2)//N2

s1=(kkk1-1)//k1-1

s2=(kkk2-1)//k2-1

ss1=iroot(s1*s1-4*N1,2)[0]

p1=(ss1+s1)//2

q1=s1-p1

ss2=iroot(s2*s2-4*N2,2)[0]

p2=(ss2+s2)//2

q2=s2-p2

d1=inverse(e1,(p1-1)*(q1-1))

d2=inverse(e2,(p2-1)*(q2-1))

print(long_to_bytes(pow(c1,d1,N1)))

printlong_to_bytes(pow(c2,d2,N2)))