MRCTF2021 CRYPTO官方wp

 

签到

给出扩展欧几里得方法的exp：

#-*- coding: utf-8 -*-
from time import strftime
from itertools import product
from time import sleep
import hashlib

from pwn import *
import re
import json
from Crypto.Util.number import long_to_bytes

host, port = 'nairw.top', 4800
p = remote(host, port)
data = p.recv().decode()

pre = re.findall(r'SHA512\("(.*?)"', data)[0]


#密码生成器
def psgen(x):
  iter = ['1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ']
  for r in iter:
    for repeat in range(1,x+1):
      for ps in product(r,repeat=repeat):
        yield ''.join(ps)


def fx(url):
  url = url.replace("/post/readauth?url=", "")
  for ps in psgen(10):
      res=pre+ps
      d=hashlib.sha512(res.encode()).hexdigest()
      #print(res)
      #print(d)
      if d[0:5]=='11111' :
          return ps
         # return 0

url='http://www.cnblogs.com/post/readauth?url=/muer/archive/2011/11/27/factualism.html'
ps = fx(url)

print(ps)
p.sendline(ps)

data = p.recvrepeat(2).decode()
#print(data[62:])

N = data[62:-1]
N = json.loads(N)
print(N)

l = N


def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q


s = l[0]
t = l[1]
P = -sum(l[2:224])
xx, yy, bb = exgcd(s, t)

response = []
this = ""
flag = ''

#print(xx,yy)
for j in range(1, 225):
    this += (str(xx * P * j) + '\n')
    this += (str(yy * P * j) + '\n')
    for i in range(222):
        this += (str(j) + '\n')

    p.send(this)
    thisData = p.recvrepeat(1).decode()
    print(thisData)
    flag += re.findall(r': (.*?)\n', thisData, re.S)[0]
    this = ""

flag = int(flag, 2)
print(long_to_bytes(flag))

 

Common Prime RSA

先把链接贴上

[1] FURTHER ATTACKS ON SERVER-AIDED RSA CRYPTOSYSTEMS 5. The third stage of the attack

[2] Cryptanalysis of RSA and It’s Variants Theorem 11.2.2

code

纯sage跑有点低能，baby step时间翻倍（

from Crypto.Util.number import *
import time
from gmpy2 import iroot
from sys import getsizeof


'''sage
e = 3
b = 0x436f6d6d6f6e207072696d652052534120697320612076617269616e74206f66205253410000000000000000000000000000000000000000000000000000000000416e642074686520636f6d6d6f6e20666163746f722067206973206c61726765207072696d6520616e6420703d3267612b3120713d3267622b31
N = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49
c = 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156
kbits = 240

PR.<x> = PolynomialRing(Zmod(N))
f = (x * 2^464 + b)^e-c
g = int(f.monic().small_roots(X=2^kbits, beta=0.5)[0])
hex(g)
'''


g1 = 0x314678eb7386e8c9dc7042bee9e565de53074e0575ca91c83d9d117b5d

n1 = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49
c1 = 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5
n2 = 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd
c2 = 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111
e = 65537

div = (n1 - 1) // (2 * g1)
u = div // (2 * g1)
v = div % (2 * g1)

aa = g1 ** 2
bb = 2 * g1 ** 2 + 1
cc = g1 ** 2 - u
c_min = (-bb + iroot(bb ** 2 - 4 * cc * aa, 2)[0]) // (2 * aa)
c_max = (u * 1.125)**0.5 // g1
d = int(pow(c_max - c_min, 0.5)) + 1
print('d =', d)

y = pow(getRandomRange(2, n1), 2 * g1, n1)
baby = {}
baby_start = pow(y, u - c_min, n1)
gian_start = 1
y_d = pow(y, d, n1)
inv = inverse(y, n1)


# baby step
start = time.time()

for i in range(d):
    if i % (d >> 10) == 1:
        print('\r%.2f%% of baby step' % ((i + 1) / (d + 1) * 100), end='')

    baby[baby_start] = i
    baby_start = (baby_start * inv) % n1

end = time.time()
print('\nbaby step : %s Seconds' % (end - start))

print('memory size of baby :', end=' ')
print(getsizeof(baby) + sum([getsizeof(i) for i in baby.values()]) + sum([getsizeof(i) for i in baby.keys()]))


# giant step
start = time.time()

for i in range(d):
    if i % (d >> 10) == 1:
        print('\r%.2f%% of giant step' % ((i + 1) / (d + 1) * 100), end='')

    if gian_start in baby:
        r, s = i, baby[gian_start]
        break
    gian_start = (gian_start * y_d) % n1
else:
    raise RuntimeError('d is too small')

end = time.time()
print('\ngiant step : %s Seconds' % (end - start))

c = (r * d + s) + c_min
print('c =', c)

aa = 1
bb = -(v + 2 * g1 * c)
cc = u - c
a1, b1 = (-bb - iroot(bb ** 2 - 4 * cc * aa, 2)[0]) // (2 * aa), (-bb + iroot(bb ** 2 - 4 * cc * aa, 2)[0]) // (2 * aa)
p1, q1 = 2 * g1 * a1 + 1, 2 * g1 * b1 + 1

g2 = pow(c1, inverse(e, (p1 - 1) * (q1 - 1)), n1)

M = (n2 - 1) // (2 * g2)
c = M % g2

aa = 2 * g2
bb = 2 * g2 * c
cc = (n2 - 1) // (2*g2) - c
a2, b2 = (-bb - iroot(bb ** 2 - 4 * cc * aa, 2)[0]) // (2 * aa), (-bb + iroot(bb ** 2 - 4 * cc * aa, 2)[0]) // (2 * aa)

p2, q2 = 2 * g2 * a2 + 1, 2 * g2 * b2 + 1
print(long_to_bytes(pow(c2, inverse(e, (p2 - 1) * (q2 - 1)), n2)).decode())

'''
d = 11080995
100.00% of baby step
baby step : 17.612889289855957 Seconds
memory size of baby : 2507419432
6.25% of giant step
giant step : 2.964820384979248 Seconds
c = 2031938446870488
MRCTF{k33p1ng_th3_C0mm0M_f@ct0r_g_C0ncea1ed_@t_A11_t1m3s_is_Imp0rtant}
'''

sl tql

 

nomore

# -*- coding: utf-8 -*-

A = 2235930885430590738951770802593215586722001521194365487273377655750584443688709547709496531484159367793509666612116139038917661713102981488722293426038029073850795986080412124312908732573382156365974821471629333126275130148211145598662897276781331183691743094904957217401055325352877284530068805608962270139656431076370452327497416723045785664344412694060886085511378779487559306015113302658964110922621164879307182468690182325142055960562810349297544601157473985262796723316777380726315782859115449976700612343978057140270903396910431420116573138154719798955123904805279320166126412714788508008881174164656203605409187705643395043643983135944514470267283183175620492198093264226038082725867230101096344723124629565311122528005863046865164876192248803940590219355154176343702897505891392317123983475290611327887699795851456183931854177169939743970260837586185988111368384484356413787993370384262996486824251003884057486063787194241555190688935624792041028246639984544749568167915235629185515957106136630401960066317998226671344793061752525215496195839080165952892472180997564802474095868944184005854120238623750555477937802107959321257495435617363809377093354132077991399603767147974592666019334636208414969819333321639542282741932229892501074615920120228860717401055433206357806353717291748096464569063777964784860874773660469621546777686833078007220613545223169043960754010332944526795605043595879174073360317477199909570141202125189377475655277483919081658123820105695508771837612756891055031293872293977244105248233915807603916034288916844336329883443200123825714530812637709561686224468031953278836676202928878535091578725509651544544672494980806630321114490828976895602038151224026672265830787863940762596976124958000977955469148027648603199590311852993367450800166591526272653355552342455506908317529193196174849749103073968182002498580115241030154502931088245539152380579199202750010140022979979488971008874424439325749039212427088023136971891092490697689178097172878439007028844083681030357488034860471042630885195387680286557424780235116405464735985082715745087677866688657626763753940919966662710093619034074861812080778855241391731006

def f(x, k):
    return pow(x - 1, 7) + pow(k * x - 1, 5) + k - A

def binary_search(minx, maxx, k):
    l, r = minx, maxx
    while l < r:
        mid = (l + r) // 2
        if f(mid, k) < 0:
            l = mid + 1
        else:
            r = mid

    return (l, f(l, k) == 0)


maxX = 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
for k in range(1, 100000):
    (x, result) = binary_search(1, maxX, k)
    if result:
        print(x, k)
        break

解出x=3009497962071627970325880719364587885671010480057866287334251735956364570350347087026477982283392009667042015682364869764534877202626872343001563490279098970253786309533656152965171286503259912849977668331206169132653702870703716072003169079329188859516303445545911170476352380900189590650131003576924340724，k=84
那么y=kx-1=252797828814016749507373980426625382396364880324860768136077145820334623909429155310224150511804928812031529317318649060220929685020657276812131333183444313501318050000827116849074388066273832679398124139821318207142911041139112150048266202663651864199369489425856538320013599995615925614611004300461644620815

#include <cstdio>
#include <ctime>
#include <signal.h>
#include <Windows.h>
#include <cmath>

#define ULL unsigned long long int

ULL k;
int start;
ULL e, tmp;

void signal_handle(int sig) {
    if (sig == SIGINT) {
        printf("e = %llu, p + q = %llu\n", e, tmp);
        printf("time: %.2lf", (double)(clock() - start) / CLOCKS_PER_SEC);
        exit(0);
    }
}

bool solve(ULL e, ULL tmp, ULL& x1, ULL& x2) {
    ULL a = k - e * e * e;
    ULL b = tmp;
    ULL A = 1;
    ULL B = -b;
    if (a % b != 0 || (b * b - a / b) % 3 != 0) {
        return false;
    }
    ULL C = (b * b - a / b) / 3;
    ULL delta = B * B - 4 * A * C;
    ULL tmp2 = sqrt(delta);
    if (tmp2 * tmp2 != delta || (-B + tmp2) % 2 != 0 || (-B - tmp2) % 2 != 0) {
        return false;
    }

    x1 = (-B + tmp2) / 2;
    x2 = (-B - tmp2) / 2;
    return true;
}

int main() {
    signal(SIGINT, signal_handle);
    scanf("%llu", &k);
    start = clock();
    for (e = 9000; e <= 10000; e++) {
        for (tmp = 2000000; tmp <= 6000000; tmp++) {
            if (e * e * e % tmp == k % tmp) {
                ULL x1, x2;
                //printf("e = %llu, p + q = %llu\n", e, tmp);
                if (solve(e, tmp, x1, x2)) {
                    if (e * e * e + x1 * x1 * x1 + x2 * x2 * x2 == k) {
                        printf("e = %llu, p = %llu, q = %llu\n", e, x1, x2);
                        printf("time: %.2lf", (double)(clock() - start) / CLOCKS_PER_SEC);
                        return 0;
                    }
                }
            }
        }
    }
}
/*
in Python:
    1100s+

in CPP:
    32.51s
*/

解出e = 9509, p = 1866989, q = 1076303，flag也轻而易举。

 

strange_CRT

多元CopperSmith，exp如下

from Crypto_tools import *
import traceback


# display matrix picture with 0 and X
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)


beta = 0.34
delta = 0.02
amplification = 2048

N = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097\

Xp = int(N**(delta + beta))
Yp = int(N**beta)
Yq = N//Yp

modulus = e
mm = 5
ss = 0
tt = 3

P.<x, y, z> = PolynomialRing(ZZ)
Q = P.quotient(N - y * z)
pol = x * (N - y) + N
pol = Q(pol).lift()

# x-z-shifts
gg = []
monomials = []
for ii in range(mm + 1):
    for jj in range(mm - ii + 1):
        x_z_shift = z ^ ss * x ^ jj * modulus ^ (mm - ii) * pol ^ ii
        x_z_shift = Q(x_z_shift).lift()
        gg.append(x_z_shift)

# y-z-shifts (selected by Herrman and May)
for ii in range(mm + 1):
    for jj in range(1, tt + 1):
        y_z_shift = z ^ ss * y ^ jj * pol ^ ii * modulus ^ (mm - ii)
        y_z_shift = Q(y_z_shift).lift()
        gg.append(y_z_shift)

# list of monomials
for polynomial in gg:
    for monomial in polynomial.monomials():
        if monomial not in monomials:
            monomials.append(monomial)


print(monomials)
print('N =', N)
print('e =', e)

# construct lattice B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
    for jj in range(0, nn):
        if monomials[jj] in gg[ii].monomials():
            BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](Xp, Yp, Yq)

matrix_overview(BB, modulus ^ mm)

det = abs(BB.det())
bound = modulus ^ (mm * nn)
print('Bound check:', det < bound)
print(int(det).bit_length(), int(bound).bit_length())

# LLL
BB = BB.LLL()
print('LLL done')
matrix_overview(BB, modulus ^ mm)

PR.<xp, yp, zp> = PolynomialRing(ZZ)
PRQ = PR.quotient(N - yp * zp)
all_pol = []

for pol1_idx in tqdm(range(nn)):
    pol1 = 0
    for jj in range(nn):
        pol1 += monomials[jj](xp, yp, zp) * BB[pol1_idx, jj] / monomials[jj](Xp, Yp, Yq)
    all_pol.append(pol1)

I = ideal(all_pol[:5])
GB = I.groebner_basis()
print('Groebner basis:')
print(GB)
print('-' * 32)

xv, yv, zv = var("xp,yp,zp")
print('roots:')
res = solve([h_i(xv, yv, zv) for h_i in GB], xv, yv, zv)

PRRR.<w> = PolynomialRing(ZZ)
for part_res in res:
    then_res = PRRR(part_res[1](w))
    p = abs(then_res.coefficients()[0].numerator())
    q = N // p
    assert p * q == N
    print(long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), N)))

 

strange_GCD

多元CopperSmith，exp如下：

from Crypto_tools import *
from itertools import permutations


P_bits = 444
Q_bits = 666
R_bits = 333
e = 0x1337
N = [8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 9663141503982563384103774905603769762205667685102275298721284964403449121449261483138514307090449027807047697811539118959328065885920230514670112839967221129701708335087378871176539521374006686377418843364889059913595942583737991465545688834167085579154677350865488342245644093471665857007588133415608450554035129609049971856915687905, 7080633525505006454857949889380886258474613936169915325357991912983821798902257837234148311383635716165386646093418183743215120431715933036921480432793786600194625124412063608565640368381660643929081066605712749838630092722581230189543696229548387666046034403406721477818265752443487173947232032487026509033018565048660685068628813900, 6348260112940191945095264085450804431350547836448100928568733296493334845533262312663784701113046746633754397388581143523779371919889446537883618910341310362947454041409541741124231406605654693961025815677260091930522280737378333554694234586235628097018111636491016261274584391201625445101930372416766825601778759258114504767453644116, 5453076441876067965962987075376616480678826248967242473452690159966124023105342358461519279607336831463834252487811766366887983597918775466645199024629945952612311092154451713992362747056489054444283302530500475646346968235522866557033556131387030809018889094871163097069588840212411234716020934787724757538389436231926479459435139729, 8539092301764573132139384894241535432591998166686651428176862041680365196821019488767353225937458669267710968146783359781905669306801237140282934737328995064410005908343087032652676207615356474601039341695241288937409773110450995503958663731870314493254162942656333393836208952363635746218345484752702086447693272390570444229475023063, 6519174659211289290465989985638494640591837577268694359892571134942820094011179335155100770258746122812579164176239810640710311061280175847537113068566174335469669480601670136633042879486860594176408555229541384726863069317134887988109513500264430505092783429319336134768414472691544453196941818593187717904852926051114502346647888426, 6961711680362025924587083752271982856615461409839316941574792747717174299272141804413488210456939607971950020060573061131683587521057101549266612028332060247289306929784809695126285828514889617483817766102136513569391338432827451306976412448973958662677599051104723480081915666230391091496248279567627159875132838397868850500912784991, 5464727156582411007360377345208743900616053705663005668786499961992377236151787056734059201141143278419642045996194426551642956434137382420547801325331080754615348522599387497424727626522195285281557448617564720973185851757117201639221059630112719699600469361046245232476531622290326229811709079901764559526124144866364301870192468062]
C = [800378461059400239726680783421062702546581299113618553895453491207714321944554499622887232532612118204284779120928524046451494597619154079853122057618867592408424421335915888671560524092660578952242621890439766919785431411789789232309134048322721650012432166587969915464252995890054635969469155870141839815222805619769926841873928532, 8685468246369062574820183134847029157229023858170863526469628501966638181721681547114662091162797572149161013458000532984909663639626346493828947027439012131912176125653717020650233650230608573276523862941298063827867869000918623143520066067119099918633173584693454642685133071154989133688921507896223776765538029556643440655490373815, 4635611296372235589362291842711945807825964919968727011796279830725567747087132786100965922682161492876463568645940638975728831156672106717718242995621775763972524561170035488180440169190421072680121175269363490806991700969253196228364471655905426168859215651384013432550900570720981720919343406680667172355882395426739478340888619526, 742099161415136628218807400531862454374875770332166710320711769923774839345990297388615457974047093967700994503615622499139058644697776431451063778211507061619987487339659448529973693084099004007650792690143707738139278995489030445825999666762580518420739517354868021396496747289677543653758101688499365196709600349831855157276274803, 4273006447766599851029197343910625305964779588947130545729882009677080459892767902139074897266046998378948193319329776150920821074305998905666368175737032487336505440974393061632257356697260043478850055918798196360043557336723402834256592984312957607731622934368169520289756716653736422872196593367101920308166527352079412344590114695, 1337615323422531101514598853478737615483725265103339849469231329210692205474781484172946466402355800190175297435923447189337380569240535257395618353403524999296122247241720498058900285176383928871155893061316083476812641934026019749574784965397208046520128690081232283708190247657782663414534596381371506499151016470118707739609022847, 6153442337491399463730666360630451953223069596225489087488144486112604050064388945200405772892415725900338512969888610774357818442533883395713661512978158729825590405567077341407532331228257558692149544940358814513930330757334104407683768945074261746314376336567331685071086776886141587264981001140113933152084084711732651014186070962, 3604640305526232611907645024550062043296875756707299105733076926046725900367109300556792007038226350415916164581084668832286944703572581980333135146219609212135443758296278947833224676930513359604019639508959092586550129343133801670578311053639151186604019506764426302411065588655525183584977810609190948096510237056027272167828516985, 2085633143403792178757363870459578017278494765962824809917819295576034993395441252397370078671500834434293581806342828037037877739374959864038090394888141183851040814572501861997433316552606005140700519616064369570511427453278726929921212633252656552135711332324923683242632912449218888750151556281762432994484741408165895663710356342]
X = 2**R_bits
m = len(N)

PR = PolynomialRing(ZZ, names=[str('x%d' % i) for i in range(1, 1 + m)])

h = 3
u = 1
variables = PR.gens()

gg = []
monomials = [variables[0]**0]
for i in range(m):
    gg.append(N[i] - variables[i])
    monomials.append(variables[i])

print(len(monomials), len(gg))
print('monomials:', monomials)

B = Matrix(ZZ, len(gg), len(monomials))
for ii in range(len(gg)):
    for jj in range(len(monomials)):
        if monomials[jj] in gg[ii].monomials():
            B[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj]([X] * m)

B = B.LLL()
print('-' * 32)

new_pol = []
for i in range(len(gg)):
    tmp_pol = 0
    for j in range(len(monomials)):
        tmp_pol += monomials[j](variables) * B[i, j] / monomials[j]([X] * m)
    new_pol.append(tmp_pol)

if len(new_pol) > 0:
    Ideal = ideal(new_pol[:m-1])
    GB = Ideal.groebner_basis()
    function_variables = var([str('y%d' % i) for i in range(1, 1 + m)])
    res = solve([pol(function_variables) for pol in GB], function_variables)

    print('got %d basis' % len(GB))
    print('solved result:')
    print(res)
    for tmp_res in res:
        PRRR.< x, y> = PolynomialRing(QQ)
        q = abs(PRRR(res[0][0](x, y)).coefficients()[0].denominator())
        p = N[-1] // q
        flag_tail = long_to_bytes(pow(C[-1], inverse(e, (p - 1) * (q - 1)), p * q))[-5:]
        flag = b''
        for i in range(m-1):
            then_res = PRRR(res[0][i](x, y))
            q = abs(then_res.coefficients()[0].numerator())
            flag += long_to_bytes(pow(C[i], inverse(e, (p-1)*(q-1)), p * q))[-5:]
        print(flag + flag_tail)