EZsquares

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag

p=getPrime(512)
q=getPrime(512)
n0=p**2+q**2
print('n0 =',n0)

e=65537
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print('c =',c)

题目分析

一个基础的rsa加密过程，其中题目给出的信息是p^2+q^2，p，q显然是互质的，所以可以发现给出的条件符合丢番图方程中的cornacchia算法的条件。我们可以用sympy中自带的cornacchia算法库来尝试进行求解，模板如下：

from sympy.solvers.diophantine.diophantine import cornacchia
x1=cornacchia(a,b,n0) #ax**2+by**2=n0

貌似sage的two_squares也可以

WP

from Crypto.Util.number import *
from gmpy2 import *

n0 = 192573744538639130845868727014075967669513667763315934161849620531683536696376138303320681922782003088094539724238109116416456294472461075668568088688287209898850985024632463251984323888765249950269595045648435192047990940593817086918399212487934262786817996341234806934640246045717955941049031252181676005098
c = 1541487946178344665369701061600511101386703525091161664845860490319891364778119340877432325104511886045675705355836238082338561882984242433897307540689460550149990099278522355182552369360471907683216881430656993369902193583200864277424101240184767762679012998894182000556316811264544736356326198994294262682
e=65537

from sympy.solvers.diophantine.diophantine import cornacchia
x1=cornacchia(1,1,n0)
for a, b in x1:
    assert a**2+b**2==n0
    if isPrime(a)and isPrime(b):
        p,q=a,b
        n=p*q
        phi=(p-1)*(q-1)
        d=inverse(e,phi)
        print(long_to_bytes(pow(c,d,n)))

EZmatrix

from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p*q
part = [bytes_to_long(flag[16*i:16*(i+1)]) for i in range(36)]
M = Matrix(Zmod(n),[
[part[6*i+j] for j in range(6)] for i in range(6)
])
d = getPrime(920)
phi = "???????????????????"
e = inverse(d,phi)
C = M ** e
print("e = ",e)
print("n = ",n)
print("C = ",list(C))

'''
e =  75759282367368799544583457453768987936939259860144125672621728877894789863642594830153210412190846168814565659154249521465974291737543527734700545818480398345759102651419148920347712594370305873033928263715201812217658781693392922382633382112810845248038459857654576967447255765379492937162044564693535012144718871564964154729561032186045816489683161588345299569985304078255628527588710513640102450308662163641732851643593090646321420800552303398630738674858967724338819227042384745213425656939930135311339542647104499427215254435723921505189649944059658797193927706249542240737884739119223756635540945563449010120382834036979025801446796614280064172405549502694658175837126702821804106928800917035327292099385809060363635737715320709749444795680950552240184529017581997661357846852201424248086080872655164246614710423850620222735225702427025180018637830386631573912505087046428427137407828859500285127835020183526681560129322020299774376860830513167598911105104946612301909005028216010756378307303924865571457872055817289904093797943893894249094212422766513999129665299858860878710920689322752152527130981697461526170099006972245891313788064563118647308122107999430867808150749979046611265769861111738145184897880080810883790769899
n =  99231341424553040688931525316017803824870567327100041969103204566938549582832516706206735181835068382521133899811339836861525260134721134887446163174620592328661881621312114348726944317349680760092960665800660405612177225373482880941142930135489885221592416840149732795379174704611605960303340578163595465083
C =  [(60962492392910372655829579800623350869143417412923809005355225641547310999689300067771076642840347631213921261735160280073159348909580620372515144615183619484116931277062459534426852453669020768212186583219050186476749582255169630649290603191487938394564254993928830585225872994041844749592189414050346998498, 47570494768722430855321464941025696993380565713448923284620084505935271175106089198810572053594395338695564872188782440522323916637635901100372244111566233734761590240981688569861120646443206802056135646056594081150032676095454677651908656653983161086373605006880681566863747858292744224442976621418797205399, 2688181329187093888869457776665971472383024590564085347482816443420850842347573980241749337291795284050213197900458997704783513811033569074013164405426061208943782009246429930688449460037973029867946269202889059604686278471272132218340037450771429686919881716403514347492132483441838117219973263406807217974, 69152734772841729744864181378357911157430121423043131526556925765272499517864120668258106865684921607378129493604079173227751534891590136750575722628168425004031909583828469631788511241718967754283602045554638710656882949816656201393892265416912928916418003936183428716201442550333656679935723677385561024921, 87916597194547447124625284021545845894398798075569904698700457948229723401310121661631733143462834474179528341099541302790092417595967636978700000869424652408571342615122171893834241191682257315189450299073036702171002969055277890180093192346807050020075074678160917020003175299572457770301172013554859610885, 87786307503376954316030650346838348696800737186248037233105303922917125487679342882764384018020917373783494097970572084301842435397667036289687253696282531883479674194433525871169279787175003732384644823866404707423021568914833613783558731218680259786594673087000922732933203580338582174836542335256895112774), (19925935729162396840966340912353714097004160798615839580675147896543197999100114040514331382227016633727621399922875280921939403294675089237685490824481702911947235694589943642920569884248825154743655331893278941153597853907070809496035573765953115001007513406579011860142499904738601402936261081671704883289, 58482679161881651450519578125499657069493057728415805326447380380141486533923095749022382883536937182057631317376727990670863971670749991637396946761762614232393617646003704455294405699238388026259395339494678908761885707645569206191899296873833133914051981244247283254577922595285757876026540914747153605160, 7876769535761750153866264956186319035785652316141088148036849233806135397857747677246966644027825150213665232397824678749874814778004967045900692519991198396803997342682950493474998693632762775853085063006163824393616781789234994435613494739078376441202546497376889898623686582966994626392473756048641752814, 40374752091452840478156903709507048899177048294570218656121556350119195781557565218138424538202862806990185673750490061744496157480684671895195643247659670629323773035075555928457149898576983418457948777991721866891250461708466719417665721953156700367709890061169794698483650373164167487545578780062511325698, 4123966761831135761457937397066767492577970106907260057338733132356073163290362041428543487785541800166623333444500095074624068090394361249458065855973762485004782025486942019551010253665248191341796357273736185376285833313657930327592630423321995683340268803166901859312919131785819655040568361583085676057, 27583730178148494208215582336953731428677655384934947406110969819755861309635715916436503750399886946834588631955424622786954747202685007199149082525818506387606813299614560669074223670606725332129580433663793218302408230595218329795347716963182007259165979155950826829268655927501949206255488502388472700075), (56315845708240095082772501761675446313947442745181474765872020399653138411744471022394674490163519262253419142994958571123783825827944495254330717218087742852853691152509996374039921954037271141012224417462582306680805308244999271694256058220813474581635472407864886498830142166123949972548432270703952960923, 32896154872958176487612097856128071067779298934826306391422436791812001537876365873180665334382055349578758924117227229354892419126981829368419291413849009911423713613087552037524220081917635206657387768281003765094819963853123278586621439766100307324554778715337379588648264826773884692017793176376154675501, 28403727117575806889742293164072634954876499471182701829204385629161049158547263968390684814088323042021380910604906904467751008743919604654911693492973603888427448583482505774314038985928231290890291117425907291509663229092491530818877566758210084483466899541610500708571206332019126409191398637035395635692, 7821951828810668315162755325480202107754899640542890161681114897656891485110009850481857086945730357655734989848039495868447513739566035840945273281198690239884406844038006297455016615584047106189557019820282710249181355660515976689844733069965635239977868606412950428777686615619878916256034858820314322668, 76525192903457309209366743987447032158337732768547571793488111729224008602119438154849638971504949003719786026252648739617917436256435628300010323711153402229164528979259259214627588535459760359253880641429469562048622701982862831594514336875830284504454333566487968184255876886415003174627552219974082980636, 30637464791180430144279994098478365983230561289862073957684155866766012864169717451278445846218491051030419180119954192685431439312797317764656461287947635921370686618109628728836641249249386071858927735736888632316823543835130338563924434711937538665035969023712380857260473274001732469412322752873384968601), (10730358875712453042013970789576402939218800351221446191771233177536009349624025030667973532521911666593354783762941362456771050299436815799063691625091095782507693177746119034551757951243518170991606414822107132916004609627849551446847131359143181119565430368982878108761799084029033027032755115381679417096, 24507369071589713103970720335832744954845520380398828656842561115495704802037030133393011751145702976684589338927049344552393322139237977140642967325628644800492714995845105460369698708659335653391904302955502145025551463160676476446189657801618085294176671181454800483878164016749534940141884944397289890871, 92820108862600030043211342419176390123942091097153321737988513673868731991771619676009296651860321326370172965558922130850493512979555339094561381645396270883677588661828281447106070801829307329117814743685760943125981155705527918307567109500089138120007989551366153992391010620955360882383556542559392894262, 74641576048678849575812629186393953979307695146586927788280165573903662821064189347983936198087197963380651069815352351349775566210254797203960521484844402002602126951649571328507275278196835502471467819034725531964918681611446773963678730681425674462738816516031202042449731753950180027830876790421576081225, 66685821407492303211977447210040267021195326010645045932118328414906080616013267240390961550749369776862683674842903750593917463844615658362977613737130311357170777497628656513144020197746398798679807363859886437403991016453908185102814636772479260178297629433510961788244743608125906745012445887428376915629, 37645288166396858415565430454995281883016537193725289151596326083427351314771501111923193754508050507668744794821015166055917903051072319801945727142824029386542877351207944394255175419467949702189317844980323590614559226315219797417693447676522076956364574845889800486817292590561738321483697160713821529546), (9736711624136652052770116447223295880053359374932369087990200046581983386760557572632286124794444930134179594903564091220200006471388531967010990324827682059485960618855287386961552241259199988445679075595951186424593845864059162998542185539998139746836413273921569266377169025136169016355692767128488900477, 13089476325068401303987570656586592581224347700750455041713556437672762444853346450009029644985692097286649094772508755542691510307531122589433151470493395688605259544275677288082873918929554397272543678133089309672143858040052870098814015145664055945998991679722753687104989489973852117933261358247564988071, 61284598700800926964424249048307178141566077849519756690996988745704530644294308600472621437373651397677668023765897304421576611779363230148263097867987781840048890597647956492658737562151147335685622316577395377277998529914754048562837674418322097396064634364367313407061824216514715793677445932930269152481, 61301319985121628512628256322255391212515053807722664632938090246192955763394429545800696862309263991966900735678875111077481123759702692720133903430321183178233894849098114454863008686201888641863850157441070304164754292432907144839124698488730051010247980425937242664545487287543260612682886985351085138001, 47435322189871012567009786652825469952862610804330828872313845269622590943796389601479086952212526668296575803391674745677862994957044749158154034984601827088557466296368252473168676311089972605318362738347163748086202789713353987691976193103958097243650266229294687864565520648709873760054473254540098351391, 32817913908586741358496040992834207477154835734595147264489781242919114343572982132460531399879345665767073663537263426565698777735998027473421290120433416805825431315476774452072722260737533264180361001819202057517709886953362750990747046346025917668519097056756157788411735612581204089155228884131378072233), (12642425264267098423833241400926732957307073786117649292717736141221694320062979757108242390714162456346780855636174573171779655212347730635821416215537084671118355916330992142141813099104775940725892721614126911510988568345398817554586646066735943804403563179908909629802981392776238272786744291004069356775, 32752716826697049825682788062896730338057604164648704588810956358313907785865814197561208570319757370744105618622052812423057447877481397095444475610617492626525875388680227635541658500637643262806846291312209615044898925278862926827256312481616510480170805540775256088922398310392639344678087647083653765821, 3022511069721965916815622985038080358228403264264831484927372260512043862778138035440859308822033467592971930633307565996150364843965884881400481310689834508879168477508572967173126034539725429899016318805136722734731136521866714013050522337795295311863953350784370773653485436181314864092331268367915892666, 44494293452595159373079306455244053834138260846967620303725161277545981351217523341157156495183639822519882035281721714315331475283644457723353767200184408989752610854962070029226464081899523388838531578296754646973186313035869250105084114692966907900349716132438711767401573694320357418158987949401765528425, 66130193533773704471809811407675367482896080993725170656227230634400122250448911267627547029162335780439769273413020435641724884803365183531498010730643595588304390566255555816793888715047993688213860064650538998545316010718479287163068234420541010586467244361311016741807424118408290204453770332676360498896, 74649855891297747785048523345822478110464591680545397129030301786991725968732851407232435476064324066227685639784066521927825943853534396958155065514682624920312291149309530337681973006060504366672574864594730979571926592855426800301765737184843799883674936189745414847240093702374870446528449267420369306618)]
'''

题目分析

将flag分组构造6*6的矩阵，然后对矩阵求rsa加密，题目只给了n和e，要分解p,q或求解d通常会想到维纳攻击，但是n是1024bit的，而d是920bit会显得太大了，不满足维纳攻击或者boneh_durfee的条件。这时候会发现e比n还大，观察两者的bit_length。

from Crypto.Util.number import *

e =  75759282367368799544583457453768987936939259860144125672621728877894789863642594830153210412190846168814565659154249521465974291737543527734700545818480398345759102651419148920347712594370305873033928263715201812217658781693392922382633382112810845248038459857654576967447255765379492937162044564693535012144718871564964154729561032186045816489683161588345299569985304078255628527588710513640102450308662163641732851643593090646321420800552303398630738674858967724338819227042384745213425656939930135311339542647104499427215254435723921505189649944059658797193927706249542240737884739119223756635540945563449010120382834036979025801446796614280064172405549502694658175837126702821804106928800917035327292099385809060363635737715320709749444795680950552240184529017581997661357846852201424248086080872655164246614710423850620222735225702427025180018637830386631573912505087046428427137407828859500285127835020183526681560129322020299774376860830513167598911105104946612301909005028216010756378307303924865571457872055817289904093797943893894249094212422766513999129665299858860878710920689322752152527130981697461526170099006972245891313788064563118647308122107999430867808150749979046611265769861111738145184897880080810883790769899
n =  99231341424553040688931525316017803824870567327100041969103204566938549582832516706206735181835068382521133899811339836861525260134721134887446163174620592328661881621312114348726944317349680760092960665800660405612177225373482880941142930135489885221592416840149732795379174704611605960303340578163595465083
print(e.bit_length()) #4093
print(n.bit_length()) #1024

e大概是4096bit，即n^4长度，猜测这里是用n^4来做为N求到对应的phi

print(920/4096) #0.224609375

大小是小于维纳攻击或boneh_durfee的上界的，这里我用boneh_durfee攻击来求出了d。
得到d后只需要对矩阵求d次方即可。

WP

# from __future__ import print_function
# import time

# ############################################
# # Config
# ##########################################

# """
# Setting debug to true will display more informations
# about the lattice, the bounds, the vectors...
# """
# debug = True

# """
# Setting strict to true will stop the algorithm (and
# return (-1, -1)) if we don't have a correct
# upperbound on the determinant. Note that this
# doesn't necesseraly mean that no solutions
# will be found since the theoretical upperbound is
# usualy far away from actual results. That is why
# you should probably use `strict = False`
# """
# strict = False

# """
# This is experimental, but has provided remarkable results
# so far. It tries to reduce the lattice as much as it can
# while keeping its efficiency. I see no reason not to use
# this option, but if things don't work, you should try
# disabling it
# """
# helpful_only = True
# dimension_min = 7 # stop removing if lattice reaches that dimension

# ############################################
# # Functions
# ##########################################

# # display stats on helpful vectors
# 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")

# # 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)

# # tries to remove unhelpful vectors
# # we start at current = n-1 (last vector)
# def remove_unhelpful(BB, monomials, bound, current):
#     # end of our recursive function
#     if current == -1 or BB.dimensions()[0] <= dimension_min:
#         return BB

#     # we start by checking from the end
#     for ii in range(current, -1, -1):
#         # if it is unhelpful:
#         if BB[ii, ii] >= bound:
#             affected_vectors = 0
#             affected_vector_index = 0
#             # let's check if it affects other vectors
#             for jj in range(ii + 1, BB.dimensions()[0]):
#                 # if another vector is affected:
#                 # we increase the count
#                 if BB[jj, ii] != 0:
#                     affected_vectors += 1
#                     affected_vector_index = jj

#             # level:0
#             # if no other vectors end up affected
#             # we remove it
#             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

#             # level:1
#             # if just one was affected we check
#             # if it is affecting someone else
#             elif affected_vectors == 1:
#                 affected_deeper = True
#                 for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
#                     # if it is affecting even one vector
#                     # we give up on this one
#                     if BB[kk, affected_vector_index] != 0:
#                         affected_deeper = False
#                 # remove both it if no other vector was affected and
#                 # this helpful vector is not helpful enough
#                 # compared to our unhelpful one
#                 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
#     # nothing happened
#     return BB

# """ 
# Returns:
# * 0,0   if it fails
# * -1,-1 if `strict=true`, and determinant doesn't bound
# * x0,y0 the solutions of `pol`
# """
# def boneh_durfee(pol, modulus, mm, tt, XX, YY):
#     """
#     Boneh and Durfee revisited by Herrmann and May

#     finds a solution if:
#     * d < N^delta
#     * |x| < e^delta
#     * |y| < e^0.5
#     whenever delta < 1 - sqrt(2)/2 ~ 0.292
#     """

#     # substitution (Herrman and May)
#     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()

#     # x-shifts list of monomials
#     monomials = []
#     for polynomial in gg:
#         for monomial in polynomial.monomials():
#             if monomial not in monomials:
#                 monomials.append(monomial)
#     monomials.sort()

#     # y-shifts (selected by Herrman and May)
#     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) # substitution

#     # y-shifts list of monomials
#     for jj in range(1, tt + 1):
#         for kk in range(floor(mm/tt) * jj, mm + 1):
#             monomials.append(u^kk * y^jj)

#     # construct lattice B
#     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)

#     # Prototype to reduce the lattice
#     if helpful_only:
#         # automatically remove
#         BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
#         # reset dimension
#         nn = BB.dimensions()[0]
#         if nn == 0:
#             print("failure")
#             return 0,0

#     # check if vectors are helpful
#     if debug:
#         helpful_vectors(BB, modulus^mm)

#     # check if determinant is correctly bounded
#     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)")

#     # display the lattice basis
#     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!")

#     # transform vector i & j -> polynomials 1 & 2
#     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):
#             # for i and j, create the two polynomials
#             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)

#             # are these good polynomials?
#             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 example():
#     ############################################
#     # How To Use This Script
#     ##########################################

#     #
#     # The problem to solve (edit the following values)
#     #

#     # the modulus

#     n =  99231341424553040688931525316017803824870567327100041969103204566938549582832516706206735181835068382521133899811339836861525260134721134887446163174620592328661881621312114348726944317349680760092960665800660405612177225373482880941142930135489885221592416840149732795379174704611605960303340578163595465083

#     N = n^4
#     # the public exponent
#     e=75759282367368799544583457453768987936939259860144125672621728877894789863642594830153210412190846168814565659154249521465974291737543527734700545818480398345759102651419148920347712594370305873033928263715201812217658781693392922382633382112810845248038459857654576967447255765379492937162044564693535012144718871564964154729561032186045816489683161588345299569985304078255628527588710513640102450308662163641732851643593090646321420800552303398630738674858967724338819227042384745213425656939930135311339542647104499427215254435723921505189649944059658797193927706249542240737884739119223756635540945563449010120382834036979025801446796614280064172405549502694658175837126702821804106928800917035327292099385809060363635737715320709749444795680950552240184529017581997661357846852201424248086080872655164246614710423850620222735225702427025180018637830386631573912505087046428427137407828859500285127835020183526681560129322020299774376860830513167598911105104946612301909005028216010756378307303924865571457872055817289904093797943893894249094212422766513999129665299858860878710920689322752152527130981697461526170099006972245891313788064563118647308122107999430867808150749979046611265769861111738145184897880080810883790769899

#     # the hypothesis on the private exponent (the theoretical maximum is 0.292)
#     delta = .18 # 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)

#     #
#     # Find the solutions!
#     #

#     # Checking bounds
#     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 algorithm ===")
#         start_time = time.time()

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

#     # found a solution?
#     if solx > 0:
#         print("=== solution 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__":
#     example()
from Crypto.Util.number import *


C =  [(60962492392910372655829579800623350869143417412923809005355225641547310999689300067771076642840347631213921261735160280073159348909580620372515144615183619484116931277062459534426852453669020768212186583219050186476749582255169630649290603191487938394564254993928830585225872994041844749592189414050346998498, 47570494768722430855321464941025696993380565713448923284620084505935271175106089198810572053594395338695564872188782440522323916637635901100372244111566233734761590240981688569861120646443206802056135646056594081150032676095454677651908656653983161086373605006880681566863747858292744224442976621418797205399, 2688181329187093888869457776665971472383024590564085347482816443420850842347573980241749337291795284050213197900458997704783513811033569074013164405426061208943782009246429930688449460037973029867946269202889059604686278471272132218340037450771429686919881716403514347492132483441838117219973263406807217974, 69152734772841729744864181378357911157430121423043131526556925765272499517864120668258106865684921607378129493604079173227751534891590136750575722628168425004031909583828469631788511241718967754283602045554638710656882949816656201393892265416912928916418003936183428716201442550333656679935723677385561024921, 87916597194547447124625284021545845894398798075569904698700457948229723401310121661631733143462834474179528341099541302790092417595967636978700000869424652408571342615122171893834241191682257315189450299073036702171002969055277890180093192346807050020075074678160917020003175299572457770301172013554859610885, 87786307503376954316030650346838348696800737186248037233105303922917125487679342882764384018020917373783494097970572084301842435397667036289687253696282531883479674194433525871169279787175003732384644823866404707423021568914833613783558731218680259786594673087000922732933203580338582174836542335256895112774), (19925935729162396840966340912353714097004160798615839580675147896543197999100114040514331382227016633727621399922875280921939403294675089237685490824481702911947235694589943642920569884248825154743655331893278941153597853907070809496035573765953115001007513406579011860142499904738601402936261081671704883289, 58482679161881651450519578125499657069493057728415805326447380380141486533923095749022382883536937182057631317376727990670863971670749991637396946761762614232393617646003704455294405699238388026259395339494678908761885707645569206191899296873833133914051981244247283254577922595285757876026540914747153605160, 7876769535761750153866264956186319035785652316141088148036849233806135397857747677246966644027825150213665232397824678749874814778004967045900692519991198396803997342682950493474998693632762775853085063006163824393616781789234994435613494739078376441202546497376889898623686582966994626392473756048641752814, 40374752091452840478156903709507048899177048294570218656121556350119195781557565218138424538202862806990185673750490061744496157480684671895195643247659670629323773035075555928457149898576983418457948777991721866891250461708466719417665721953156700367709890061169794698483650373164167487545578780062511325698, 4123966761831135761457937397066767492577970106907260057338733132356073163290362041428543487785541800166623333444500095074624068090394361249458065855973762485004782025486942019551010253665248191341796357273736185376285833313657930327592630423321995683340268803166901859312919131785819655040568361583085676057, 27583730178148494208215582336953731428677655384934947406110969819755861309635715916436503750399886946834588631955424622786954747202685007199149082525818506387606813299614560669074223670606725332129580433663793218302408230595218329795347716963182007259165979155950826829268655927501949206255488502388472700075), (56315845708240095082772501761675446313947442745181474765872020399653138411744471022394674490163519262253419142994958571123783825827944495254330717218087742852853691152509996374039921954037271141012224417462582306680805308244999271694256058220813474581635472407864886498830142166123949972548432270703952960923, 32896154872958176487612097856128071067779298934826306391422436791812001537876365873180665334382055349578758924117227229354892419126981829368419291413849009911423713613087552037524220081917635206657387768281003765094819963853123278586621439766100307324554778715337379588648264826773884692017793176376154675501, 28403727117575806889742293164072634954876499471182701829204385629161049158547263968390684814088323042021380910604906904467751008743919604654911693492973603888427448583482505774314038985928231290890291117425907291509663229092491530818877566758210084483466899541610500708571206332019126409191398637035395635692, 7821951828810668315162755325480202107754899640542890161681114897656891485110009850481857086945730357655734989848039495868447513739566035840945273281198690239884406844038006297455016615584047106189557019820282710249181355660515976689844733069965635239977868606412950428777686615619878916256034858820314322668, 76525192903457309209366743987447032158337732768547571793488111729224008602119438154849638971504949003719786026252648739617917436256435628300010323711153402229164528979259259214627588535459760359253880641429469562048622701982862831594514336875830284504454333566487968184255876886415003174627552219974082980636, 30637464791180430144279994098478365983230561289862073957684155866766012864169717451278445846218491051030419180119954192685431439312797317764656461287947635921370686618109628728836641249249386071858927735736888632316823543835130338563924434711937538665035969023712380857260473274001732469412322752873384968601), (10730358875712453042013970789576402939218800351221446191771233177536009349624025030667973532521911666593354783762941362456771050299436815799063691625091095782507693177746119034551757951243518170991606414822107132916004609627849551446847131359143181119565430368982878108761799084029033027032755115381679417096, 24507369071589713103970720335832744954845520380398828656842561115495704802037030133393011751145702976684589338927049344552393322139237977140642967325628644800492714995845105460369698708659335653391904302955502145025551463160676476446189657801618085294176671181454800483878164016749534940141884944397289890871, 92820108862600030043211342419176390123942091097153321737988513673868731991771619676009296651860321326370172965558922130850493512979555339094561381645396270883677588661828281447106070801829307329117814743685760943125981155705527918307567109500089138120007989551366153992391010620955360882383556542559392894262, 74641576048678849575812629186393953979307695146586927788280165573903662821064189347983936198087197963380651069815352351349775566210254797203960521484844402002602126951649571328507275278196835502471467819034725531964918681611446773963678730681425674462738816516031202042449731753950180027830876790421576081225, 66685821407492303211977447210040267021195326010645045932118328414906080616013267240390961550749369776862683674842903750593917463844615658362977613737130311357170777497628656513144020197746398798679807363859886437403991016453908185102814636772479260178297629433510961788244743608125906745012445887428376915629, 37645288166396858415565430454995281883016537193725289151596326083427351314771501111923193754508050507668744794821015166055917903051072319801945727142824029386542877351207944394255175419467949702189317844980323590614559226315219797417693447676522076956364574845889800486817292590561738321483697160713821529546), (9736711624136652052770116447223295880053359374932369087990200046581983386760557572632286124794444930134179594903564091220200006471388531967010990324827682059485960618855287386961552241259199988445679075595951186424593845864059162998542185539998139746836413273921569266377169025136169016355692767128488900477, 13089476325068401303987570656586592581224347700750455041713556437672762444853346450009029644985692097286649094772508755542691510307531122589433151470493395688605259544275677288082873918929554397272543678133089309672143858040052870098814015145664055945998991679722753687104989489973852117933261358247564988071, 61284598700800926964424249048307178141566077849519756690996988745704530644294308600472621437373651397677668023765897304421576611779363230148263097867987781840048890597647956492658737562151147335685622316577395377277998529914754048562837674418322097396064634364367313407061824216514715793677445932930269152481, 61301319985121628512628256322255391212515053807722664632938090246192955763394429545800696862309263991966900735678875111077481123759702692720133903430321183178233894849098114454863008686201888641863850157441070304164754292432907144839124698488730051010247980425937242664545487287543260612682886985351085138001, 47435322189871012567009786652825469952862610804330828872313845269622590943796389601479086952212526668296575803391674745677862994957044749158154034984601827088557466296368252473168676311089972605318362738347163748086202789713353987691976193103958097243650266229294687864565520648709873760054473254540098351391, 32817913908586741358496040992834207477154835734595147264489781242919114343572982132460531399879345665767073663537263426565698777735998027473421290120433416805825431315476774452072722260737533264180361001819202057517709886953362750990747046346025917668519097056756157788411735612581204089155228884131378072233), (12642425264267098423833241400926732957307073786117649292717736141221694320062979757108242390714162456346780855636174573171779655212347730635821416215537084671118355916330992142141813099104775940725892721614126911510988568345398817554586646066735943804403563179908909629802981392776238272786744291004069356775, 32752716826697049825682788062896730338057604164648704588810956358313907785865814197561208570319757370744105618622052812423057447877481397095444475610617492626525875388680227635541658500637643262806846291312209615044898925278862926827256312481616510480170805540775256088922398310392639344678087647083653765821, 3022511069721965916815622985038080358228403264264831484927372260512043862778138035440859308822033467592971930633307565996150364843965884881400481310689834508879168477508572967173126034539725429899016318805136722734731136521866714013050522337795295311863953350784370773653485436181314864092331268367915892666, 44494293452595159373079306455244053834138260846967620303725161277545981351217523341157156495183639822519882035281721714315331475283644457723353767200184408989752610854962070029226464081899523388838531578296754646973186313035869250105084114692966907900349716132438711767401573694320357418158987949401765528425, 66130193533773704471809811407675367482896080993725170656227230634400122250448911267627547029162335780439769273413020435641724884803365183531498010730643595588304390566255555816793888715047993688213860064650538998545316010718479287163068234420541010586467244361311016741807424118408290204453770332676360498896, 74649855891297747785048523345822478110464591680545397129030301786991725968732851407232435476064324066227685639784066521927825943853534396958155065514682624920312291149309530337681973006060504366672574864594730979571926592855426800301765737184843799883674936189745414847240093702374870446528449267420369306618)]
n =  99231341424553040688931525316017803824870567327100041969103204566938549582832516706206735181835068382521133899811339836861525260134721134887446163174620592328661881621312114348726944317349680760092960665800660405612177225373482880941142930135489885221592416840149732795379174704611605960303340578163595465083
d=5625392240871591703674913289176493449351554576001933379885655076380379121373730939272476349026135584314461774818575210968383018641741768873055290364913313885973206167937229668741817076803184617448123799781711736443720192213454840474648356266384085300527439223289199819331996099
C=matrix(Zmod(n),C)
M=C^d
for i in range(6):
    for j in range(6):
        print(long_to_bytes(M[i,j]),end="")

ezsign1n

from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag
import hashlib

p = 174523845247570741054964008585718839267
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G=E(2247961404505753398791635923994899528, 108711418033303501028455466081133667288)
n=G.order()
Cofactor = E.order() // n
f = 128+1
lambda_ = 100

def retbar(P):
    index = (f + 1) // 2
    return (int(P[0]) % (2 ^ index) + 2 ^ index) % n

def genkey():
    w = randint(1, n - 1)
    W = w * G
    return (w, W)

B_pri_w, B_pub_W = genkey()
print(B_pub_W[0:2])

LS = []
LR = []
BR = []

def Exchange(i):
    A_pri_w, A_pub_W = genkey()
    A_pri_r, A_pub_R = genkey()
    B_pri_r, B_pub_R = genkey()

    sa = (A_pri_r + retbar(A_pub_R) * A_pri_w) % n
    sb = (B_pri_r + retbar(B_pub_R) * B_pri_w) % n

    Ka = Cofactor * (B_pub_R + retbar(B_pub_R) * B_pub_W) * sa
    Kb = Cofactor * (A_pub_R + retbar(A_pub_R) * A_pub_W) * sb

    assert (Ka == Kb)

    leakageS = sb >> lambda_
    leakageR = B_pri_r >> lambda_

    LS.append(leakageS), LR.append(leakageR)
    BR.append(B_pub_R[0:2])

for i in range(10): Exchange(i)

print("LS=", LS)
print("LR=", LR)
print("BR=", BR)
H=hashlib.md5()
H.update(long_to_bytes(B_pri_w))
key=H.hexdigest().encode()
aes = AES.new(key,AES.MODE_ECB)
print(aes.encrypt(flag))

题目分析

看着是一个密钥交换，但感觉后面的没啥用，关注点在于

sb = (B_pri_r + retbar(B_pub_R) * B_pri_w) % n

已知sb和B_pri_r的高位，我将他们移到同一边

我们已知sb和B_pri_r的高位，我将俩个数合在一起来看，已知高位设为h,低位为

retbar(B_pub_R)的值我们是可以求出来的，这是一个hnp问题，已知高位为28bit，未知低位为100bit，需要求的私钥B_pri_w应该也是128bit的数量级。题目中给出了十组数据

有很大概率是能规约出结果的。稍微定义下变量

以第一组为基准与其他组别的数据进行消元计算

令

可以得到

构造如下的格就有机会规约出答案

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

p = 174523845247570741054964008585718839267
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G=E(2247961404505753398791635923994899528, 108711418033303501028455466081133667288)
n=G.order()
Cofactor = E.order() // n
f = 128+1
lambda_ = 100

def retbar(P):
    index = (f + 1) // 2
    return (int(P[0]) % (2 ^ index) + 2 ^ index) % n

def genkey():
    w = randint(1, n - 1)
    W = w * G
    return (w, W)


B_pub_W=E(56142839234500040174315077324489019612, 143186177525574678948140963663687495447)
LS= [12160779, 70634852, 136488679, 93279448, 51769705, 99408367, 94011238, 46255543, 136054320, 126842658]
LR= [117789932, 85602320, 136131278, 85538539, 33115646, 15821127, 122073977, 40205177, 40509142, 121833940]
BR= [(43128875586771925869851532015581155657, 108714366549720544283054523544596695631), (166053844834143846221197595138208659402, 9389299139547698081250285594708260233), (83160043610860066750778648875060399604, 160655466348101518011620435983302563358), (18306927902958362110653472691194540502, 141566997533915037448387258113883793369), (124719869188706449552550102421264489653, 111266021208672789646176095367638959348), (62115794167524204331339724293036031704, 24476842210910012261000793337134128911), (57017187772347635647835418540384524017, 149273114828279413180900590599119201032), (141865913804035015431129030802262884043, 11219445710980991629921733217597739715), (35994282847505215202392163277052083355, 5366425669461724819918825109516828913), (72621299937996657982583201267406651177, 39297013522202608324989011761142875947)]
t=[]
ret=[]

# C=matrix(ZZ,len(LS)+2,len(LS)+2)
# for i in range(len(LS)):
#     C[i,i]=n
#     C[-2,i]=ret[i]
#     C[-1,i]=t[i]
# C[-2,-2]=1
# C[-1,-1]=n
# res=C.LLL()
# print(res)
# print(n)
x0=4119992749236879371973464970868211466#29758088288220671759512856521717250051 #1178130499626730132053516695382476673
print(x0*G)



m = 128
s = 28
B=[]
A=[]
for i in range(len(LS)):
    #t.append((abs(LS[i]-LR[i])<<100)%n)
    B.append((((LS[i]<<100)-(LR[i]<<100))))
    A.append(retbar(BR[i]))


q=n
D=[]
E=[]
n=10
for i in range(len(A)-1):
    D.append((inverse(A[0],q)*(A[i+1]*B[0]-A[0]*B[i+1]))%q)
    E.append((inverse(A[0],q)*A[i+1])%q)

L=Matrix(ZZ,n+1,n+1)
for i in range(n-1):
    L[i,i]=-q
    L[-2,i]=E[i]
    L[-1,i]=D[i]
L[-2,-2]=1
L[-1,-1]=2^128
M=L.LLL()
# print(M)
for i in M:
        if i[-1]==2^128:
            b=vector(i)
            b0 = abs(b[-2])
            x0 = (B[0]+b0) * inverse(A[0],q) % q
            print(x0)
            # break

得到了

w=1178130499626730132053516695382476673

然后用公钥验证了一下，发现不对，用自己生成的数据进行检验也存在问题，这时候对比发现低36bit不同。此时直接考虑bsgs方法，复杂度为2^18,这里用加法代替了乘法，能够提高运算速度

from tqdm import trange
x0=1178130499626730132053516695382476673
x0=x0>>36<<36

tmp=0
dic={}

for i in trange(0,2^18):
    tmp+=G
    dic[tmp]=i+1
h=B_pub_W-x0*G
top=2^18*G
hh=0
for i in trange(0,2^18):
     if(h in dic):
          print(i)
          print(dic[h])
          w=x0+i*2^18+dic[h]
          print(w)
          break
     h=h-top

得到私钥后就可以根据题意解aes得到flag了

WP

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

p = 174523845247570741054964008585718839267
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G=E(2247961404505753398791635923994899528, 108711418033303501028455466081133667288)
n=G.order()
Cofactor = E.order() // n
f = 128+1
lambda_ = 100

def retbar(P):
    index = (f + 1) // 2
    return (int(P[0]) % (2 ^ index) + 2 ^ index) % n

def genkey():
    w = randint(1, n - 1)
    W = w * G
    return (w, W)


B_pub_W=E(56142839234500040174315077324489019612, 143186177525574678948140963663687495447)
LS= [12160779, 70634852, 136488679, 93279448, 51769705, 99408367, 94011238, 46255543, 136054320, 126842658]
LR= [117789932, 85602320, 136131278, 85538539, 33115646, 15821127, 122073977, 40205177, 40509142, 121833940]
BR= [(43128875586771925869851532015581155657, 108714366549720544283054523544596695631), (166053844834143846221197595138208659402, 9389299139547698081250285594708260233), (83160043610860066750778648875060399604, 160655466348101518011620435983302563358), (18306927902958362110653472691194540502, 141566997533915037448387258113883793369), (124719869188706449552550102421264489653, 111266021208672789646176095367638959348), (62115794167524204331339724293036031704, 24476842210910012261000793337134128911), (57017187772347635647835418540384524017, 149273114828279413180900590599119201032), (141865913804035015431129030802262884043, 11219445710980991629921733217597739715), (35994282847505215202392163277052083355, 5366425669461724819918825109516828913), (72621299937996657982583201267406651177, 39297013522202608324989011761142875947)]
t=[]
ret=[]

# C=matrix(ZZ,len(LS)+2,len(LS)+2)
# for i in range(len(LS)):
#     C[i,i]=n
#     C[-2,i]=ret[i]
#     C[-1,i]=t[i]
# C[-2,-2]=1
# C[-1,-1]=n
# res=C.LLL()
# print(res)
# print(n)
x0=4119992749236879371973464970868211466#29758088288220671759512856521717250051 #1178130499626730132053516695382476673
print(x0*G)



m = 128
s = 28
B=[]
A=[]
for i in range(len(LS)):
    #t.append((abs(LS[i]-LR[i])<<100)%n)
    B.append((((LS[i]<<100)-(LR[i]<<100))))
    A.append(retbar(BR[i]))


q=n
D=[]
E=[]
n=10
for i in range(len(A)-1):
    D.append((inverse(A[0],q)*(A[i+1]*B[0]-A[0]*B[i+1]))%q)
    E.append((inverse(A[0],q)*A[i+1])%q)

L=Matrix(ZZ,n+1,n+1)
for i in range(n-1):
    L[i,i]=-q
    L[-2,i]=E[i]
    L[-1,i]=D[i]
L[-2,-2]=1
L[-1,-1]=2^128
M=L.LLL()
# print(M)
for i in M:
        if i[-1]==2^128:
            b=vector(i)
            b0 = abs(b[-2])
            x0 = (B[0]+b0) * inverse(A[0],q) % q
            print(x0)
            # break



# from tqdm import trange
# x0=1178130499626730132053516695382476673
# x0=x0>>36<<36

# tmp=0
# dic={}

# for i in trange(0,2^18):
#     tmp+=G
#     dic[tmp]=i+1
# h=B_pub_W-x0*G
# top=2^18*G
# hh=0
# for i in trange(0,2^18):
#      if(h in dic):
#           print(i)
#           print(dic[h])
#           w=x0+i*2^18+dic[h]
#           print(w)
#           break
#      h=h-top


c=b'\xd7\x8c\xf1Yx\x05W\x8ckq\xfdb\xd5\x81K"\xe7q\x88\x18\xedq\x9f\xcap\x1cTB\xc9)\xe1c\xf4~\x7f\xccwh\xfe\t\xbf\xb2!\xde\x84\xeeO\x0f8\xd1\xac\xbc\x1c \xf0F\x0c\x00\xc9\xa7\x9e\x06\xdan'
w=1178130499626730132053516693988590569
H=hashlib.md5()
H.update(long_to_bytes(w))
key=H.hexdigest().encode()
aes = AES.new(key,AES.MODE_ECB)
print(aes.decrypt(c))